HDK
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
denseHashSet.h
Go to the documentation of this file.
1 //
2 // Copyright 2016 Pixar
3 //
4 // Licensed under the terms set forth in the LICENSE.txt file available at
5 // https://openusd.org/license.
6 //
7 #ifndef PXR_BASE_TF_DENSE_HASH_SET_H
8 #define PXR_BASE_TF_DENSE_HASH_SET_H
9 
10 /// \file tf/denseHashSet.h
11 
12 #include "pxr/pxr.h"
14 #include "pxr/base/tf/hashmap.h"
15 
16 #include <memory>
17 #include <vector>
18 
20 
21 /// \class TfDenseHashSet
22 ///
23 /// This is a space efficient container that mimics the TfHashSet API that
24 /// uses a vector for storage when the size of the set is small.
25 ///
26 /// When the set gets bigger than \p Threshold a TfHashMap is allocated
27 /// that is used to accelerate lookup in the vector.
28 ///
29 /// \warning This differs from a TfHashSet in so far that inserting and
30 /// removing elements invalidate all iterators of the container.
31 ///
32 template <
33  class Element,
34  class HashFn,
35  class EqualElement = std::equal_to<Element>,
36  unsigned Threshold = 128
37 >
39 {
40 public:
41 
43 
44 ////////////////////////////////////////////////////////////////////////////////
45 
46 private:
47 
48  // The vector type holding all data for this dense hash set.
49  typedef std::vector<Element> _Vector;
50 
51  // The hash map used when the map holds more than Threshold elements.
53 
54 ////////////////////////////////////////////////////////////////////////////////
55 
56 public:
57 
58  /// An iterator type for this set. Note that this one is const as well,
59  /// as we can't allow in-place modification of elements due to the
60  /// potentially allocated hash map.
61  typedef typename _Vector::const_iterator iterator;
62 
63  /// A const_iterator type for this set.
64  typedef typename _Vector::const_iterator const_iterator;
65 
66  /// Return type for insert() method.
67  typedef std::pair<const_iterator, bool> insert_result;
68 
69 public:
70 
71  /// Ctor.
72  ///
73  explicit TfDenseHashSet(
74  const HashFn &hashFn = HashFn(),
75  const EqualElement &equalElement = EqualElement())
76  {
77  _hash() = hashFn;
78  _equ() = equalElement;
79  }
80 
81  /// Copy Ctor.
82  ///
84  : _storage(rhs._storage) {
85  if (rhs._h) {
86  _h = std::make_unique<_HashMap>(*rhs._h);
87  }
88  }
89 
90  /// Move Ctor.
91  ///
92  TfDenseHashSet(TfDenseHashSet &&rhs) = default;
93 
94  /// Construct from range.
95  ///
96  template <class Iterator>
97  TfDenseHashSet(Iterator begin, Iterator end) {
98  insert(begin, end);
99  }
100 
101  /// Construct from an initializer_list.
102  ///
103  TfDenseHashSet(std::initializer_list<Element> l) {
104  insert(l.begin(), l.end());
105  }
106 
107  /// Copy assignment operator.
108  ///
110  if (this != &rhs) {
111  TfDenseHashSet temp(rhs);
112  temp.swap(*this);
113  }
114  return *this;
115  }
116 
117  /// Move assignment operator.
118  ///
119  TfDenseHashSet &operator=(TfDenseHashSet &&rhs) = default;
120 
121  /// Assignment from an initializer_list.
122  ///
123  TfDenseHashSet &operator=(std::initializer_list<Element> l) {
124  clear();
125  insert(l.begin(), l.end());
126  return *this;
127  }
128 
129  /// Equality operator.
130  ///
131  bool operator==(const TfDenseHashSet &rhs) const {
132 
133  if (size() != rhs.size())
134  return false;
135 
136  //XXX: Should we compare the HashFn and EqualElement too?
137  const_iterator tend = end();
138 
139  for(const_iterator iter = begin(); iter != tend; ++iter) {
140  if (!rhs.count(*iter))
141  return false;
142  }
143 
144  return true;
145  }
146 
147  bool operator!=(const TfDenseHashSet &rhs) const {
148  return !(*this == rhs);
149  }
150 
151  /// Erases all of the elements
152  ///
153  void clear() {
154  _vec().clear();
155  _h.reset();
156  }
157 
158  /// Swaps the contents of two sets.
159  ///
160  void swap(TfDenseHashSet &rhs) {
161  _storage.swap(rhs._storage);
162  _h.swap(rhs._h);
163  }
164 
165  /// \c true if the \c set's size is 0.
166  ///
167  bool empty() const {
168  return _vec().empty();
169  }
170 
171  /// Returns the size of the set.
172  ///
173  size_t size() const {
174  return _vec().size();
175  }
176 
177  /// Returns an const_iterator pointing to the beginning of the set.
178  ///
180  return _vec().begin();
181  }
182 
183  /// Returns an const_iterator pointing to the end of the set.
184  ///
185  const_iterator end() const {
186  return _vec().end();
187  }
188 
189  /// Finds the element with key \p k.
190  ///
191  const_iterator find(const Element &k) const {
192 
193  if (_h) {
194  typename _HashMap::const_iterator iter = _h->find(k);
195  if (iter == _h->end())
196  return end();
197 
198  return _vec().begin() + iter->second;
199  }
200 
201  typename _Vector::const_iterator iter, end = _vec().end();
202 
203  for(iter = _vec().begin(); iter != end; ++iter)
204  if (_equ()(*iter, k))
205  break;
206 
207  return iter;
208  }
209 
210  /// Returns the number of elements with key \p k. Which is either 0 or 1.
211  ///
212  size_t count(const Element &k) const {
213  return find(k) != end();
214  }
215 
216  /// Returns a pair of <iterator, bool> where iterator points to the element
217  /// in the list and bool is true if a new element was inserted.
218  ///
220 
221  if (_h) {
222 
223  // Attempt to insert the new index. If this fails, we can't
224  // insert v.
225 
226  std::pair<typename _HashMap::iterator, bool> res =
227  _h->insert(std::make_pair(v, size()));
228 
229  if (!res.second)
230  return insert_result(_vec().begin() + res.first->second, false);
231 
232  } else {
233 
234  // Bail if already inserted.
235  const_iterator iter = find(v);
236  if (iter != end())
237  return insert_result(iter, false);
238  }
239 
240  // Insert at end and create table if necessary.
241  _vec().push_back(v);
242  _CreateTableIfNeeded();
243 
244  return insert_result(std::prev(end()), true);
245  }
246 
247  /// Insert a range into the hash set. Note that \p i0 and \p i1 can't
248  /// point into the hash set.
249  ///
250  template<class IteratorType>
251  void insert(IteratorType i0, IteratorType i1) {
252  // Assume elements are more often than not unique, so if the sum of the
253  // current size and the size of the range is greater than or equal to
254  // the threshold, we create the table immediately so we don't do m*n
255  // work before creating the table.
256  if (size() + std::distance(i0, i1) >= Threshold)
257  _CreateTable();
258 
259  // Insert elements.
260  for (IteratorType iter = i0; iter != i1; ++iter)
261  insert(*iter);
262  }
263 
264  /// Insert a range of unique elements into the container. [begin, end)
265  /// *must not* contain any duplicate elements.
266  ///
267  template <class Iterator>
268  void insert_unique(Iterator begin, Iterator end) {
269  // Special-case empty container.
270  if (empty()) {
271  _vec().assign(begin, end);
272  _CreateTableIfNeeded();
273  } else {
274  // Just insert, since duplicate checking will use the hash.
275  insert(begin, end);
276  }
277  }
278 
279  /// Erase element with key \p k. Returns the number of elements erased.
280  ///
281  size_t erase(const Element &k) {
282 
283  const_iterator iter = find(k);
284  if (iter != end()) {
285  erase(iter);
286  return 1;
287  }
288  return 0;
289  }
290 
291  /// Erases element pointed to by \p iter.
292  ///
293  void erase(const iterator &iter) {
294 
295  // Erase key from hash table if applicable.
296  if (_h)
297  _h->erase(*iter);
298 
299  // If we are not removing that last element...
300  if (iter != std::prev(end())) {
301  using std::swap;
302 
303  // ... move the last element into the erased placed.
304  // Note that we can cast constness away because we explicitly update
305  // the TfHashMap _h below.
306  swap(*const_cast<Element *>(&(*iter)), _vec().back());
307 
308  // ... and update the moved element's index.
309  if (_h)
310  (*_h)[*iter] = iter - _vec().begin();
311  }
312 
313  _vec().pop_back();
314  }
315 
316  /// Erases a range from the set.
317  ///
318  void erase(const iterator &i0, const iterator &i1) {
319 
320  if (_h) {
321  for(const_iterator iter = i0; iter != i1; ++iter)
322  _h->erase(iter->first);
323  }
324 
325  const_iterator vremain = _vec().erase(i0, i1);
326 
327  if (_h) {
328  for(; vremain != _vec().end(); ++vremain)
329  (*_h)[*vremain] = vremain - _vec().begin();
330  }
331  }
332 
333  /// Optimize storage space.
334  ///
335  void shrink_to_fit() {
336 
337  // Shrink the vector to best size.
338  _vec().shrink_to_fit();
339 
340  if (!_h)
341  return;
342 
343  size_t sz = size();
344 
345  // If we have a hash map and are underneath the threshold, discard it.
346  if (sz < Threshold) {
347 
348  _h.reset();
349 
350  } else {
351 
352  // Otherwise, allocate a new hash map with the optimal size.
353  _h.reset(new _HashMap(sz, _hash(), _equ()));
354  for(size_t i=0; i<sz; ++i)
355  (*_h)[_vec()[i]] = i;
356  }
357  }
358 
359  /// Index into set via \p index.
360  ///
361  const Element &operator[](size_t index) const {
362  TF_VERIFY(index < size());
363  return _vec()[index];
364  }
365 
366 ////////////////////////////////////////////////////////////////////////////////
367 
368 private:
369 
370  // Helper to access the storage vector.
371  _Vector &_vec() {
372  return _storage.vector;
373  }
374 
375  // Helper to access the hash functor.
376  HashFn &_hash() {
377  return _storage;
378  }
379 
380  // Helper to access the equality functor.
381  EqualElement &_equ() {
382  return _storage;
383  }
384 
385  // Helper to access the storage vector.
386  const _Vector &_vec() const {
387  return _storage.vector;
388  }
389 
390  // Helper to access the hash functor.
391  const HashFn &_hash() const {
392  return _storage;
393  }
394 
395  // Helper to access the equality functor.
396  const EqualElement &_equ() const {
397  return _storage;
398  }
399 
400  // Helper to create the acceleration table if size dictates.
401  inline void _CreateTableIfNeeded() {
402  if (size() >= Threshold) {
403  _CreateTable();
404  }
405  }
406 
407  // Unconditionally create the acceleration table if it doesn't already
408  // exist.
409  inline void _CreateTable() {
410  if (!_h) {
411  _h.reset(new _HashMap(Threshold, _hash(), _equ()));
412  for(size_t i=0; i < size(); ++i)
413  (*_h)[_vec()[i]] = i;
414  }
415  }
416 
417  // Since sizeof(EqualElement) == 0 and sizeof(HashFn) == 0 in many cases
418  // we use the empty base optimization to not pay a size penalty.
419  // In C++20, explore using [[no_unique_address]] as an alternative
420  // way to get this optimization.
421  struct ARCH_EMPTY_BASES _CompressedStorage :
422  private EqualElement, private HashFn {
424  "EqualElement and HashFn must be distinct types.");
425  _CompressedStorage() = default;
426  _CompressedStorage(const EqualElement& equal, const HashFn& hashFn)
427  : EqualElement(equal), HashFn(hashFn) {}
428 
429  void swap(_CompressedStorage& other) {
430  using std::swap;
431  vector.swap(other.vector);
432  swap(static_cast<EqualElement&>(*this),
433  static_cast<EqualElement&>(other));
434  swap(static_cast<HashFn&>(*this), static_cast<HashFn&>(other));
435  }
436  _Vector vector;
437  friend class TfDenseHashSet;
438  };
439  _CompressedStorage _storage;
440 
441  // Optional hash map that maps from keys to vector indices.
442  std::unique_ptr<_HashMap> _h;
443 };
444 
446 
447 #endif // PXR_BASE_TF_DENSE_HASH_SET_H
_Base::const_iterator const_iterator
Definition: hashmap.h:266
void erase(const iterator &i0, const iterator &i1)
Definition: denseHashSet.h:318
bool operator==(const TfDenseHashSet &rhs) const
Definition: denseHashSet.h:131
void swap(UT::ArraySet< Key, MULTI, MAX_LOAD_FACTOR_256, Clearer, Hash, KeyEqual > &a, UT::ArraySet< Key, MULTI, MAX_LOAD_FACTOR_256, Clearer, Hash, KeyEqual > &b)
Definition: UT_ArraySet.h:1699
const GLdouble * v
Definition: glcorearb.h:837
const_iterator end() const
Definition: denseHashSet.h:185
GLsizei const GLfloat * value
Definition: glcorearb.h:824
void erase(const iterator &iter)
Definition: denseHashSet.h:293
void shrink_to_fit()
Definition: denseHashSet.h:335
std::pair< const_iterator, bool > insert_result
Return type for insert() method.
Definition: denseHashSet.h:67
IMATH_HOSTDEVICE constexpr bool equal(T1 a, T2 b, T3 t) IMATH_NOEXCEPT
Definition: ImathFun.h:105
TfDenseHashSet(const TfDenseHashSet &rhs)
Definition: denseHashSet.h:83
const_iterator find(const Element &k) const
Definition: denseHashSet.h:191
size_t count(const Element &k) const
Definition: denseHashSet.h:212
void insert(IteratorType i0, IteratorType i1)
Definition: denseHashSet.h:251
GLuint GLuint end
Definition: glcorearb.h:475
const Element & operator[](size_t index) const
Definition: denseHashSet.h:361
GLint i1
Definition: glad.h:2724
Definition: path.h:273
TfDenseHashSet & operator=(const TfDenseHashSet &rhs)
Definition: denseHashSet.h:109
TfDenseHashSet(const HashFn &hashFn=HashFn(), const EqualElement &equalElement=EqualElement())
Definition: denseHashSet.h:73
size_t size() const
Definition: denseHashSet.h:173
TfDenseHashSet & operator=(std::initializer_list< Element > l)
Definition: denseHashSet.h:123
PXR_NAMESPACE_CLOSE_SCOPE PXR_NAMESPACE_OPEN_SCOPE
Definition: path.h:1425
TfDenseHashSet(Iterator begin, Iterator end)
Definition: denseHashSet.h:97
GLuint index
Definition: glcorearb.h:786
TfDenseHashSet(std::initializer_list< Element > l)
Definition: denseHashSet.h:103
_Vector::const_iterator iterator
Definition: denseHashSet.h:61
#define PXR_NAMESPACE_CLOSE_SCOPE
Definition: pxr.h:74
void swap(TfDenseHashSet &rhs)
Definition: denseHashSet.h:160
size_t erase(const Element &k)
Definition: denseHashSet.h:281
Element value_type
Definition: denseHashSet.h:42
bool operator!=(const TfDenseHashSet &rhs) const
Definition: denseHashSet.h:147
bool empty() const
Definition: denseHashSet.h:167
void insert_unique(Iterator begin, Iterator end)
Definition: denseHashSet.h:268
insert_result insert(const value_type &v)
Definition: denseHashSet.h:219
SIM_API const UT_StringHolder distance
const_iterator begin() const
Definition: denseHashSet.h:179
_Vector::const_iterator const_iterator
A const_iterator type for this set.
Definition: denseHashSet.h:64