HDK
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
UT_ArraySet.h
Go to the documentation of this file.
1 /*
2  * PROPRIETARY INFORMATION. This software is proprietary to
3  * Side Effects Software Inc., and is not to be reproduced,
4  * transmitted, or disclosed in any way without written permission.
5  *
6  * NAME: UT_ArraySet.h (UT Library, C++)
7  *
8  * COMMENTS: Flat-array-based hash set implementation.
9  */
10 
11 #pragma once
12 
13 #ifndef __UT_ArraySet__
14 #define __UT_ArraySet__
15 
16 #include "UT_ArrayHelp.h"
17 #include "UT_Assert.h"
18 #include <SYS/SYS_Inline.h>
19 #include <SYS/SYS_Math.h>
20 #include <SYS/SYS_StaticAssert.h>
21 #include <SYS/SYS_Types.h>
22 #include <functional>
23 #include <limits>
24 #include <stdint.h>
25 #include <utility>
26 
27 namespace UT {
28 
29 template<typename T>
30 struct DefaultClearer;
31 
32 template<typename S>
33 struct DefaultClearer<S*>
34 {
35  static void clear(S*&v) { v = nullptr; }
36  static bool isClear(S *v) { return v == nullptr; }
37  static void clearConstruct(S**p) { clear(*p); }
38 
39  static const bool clearNeedsDestruction = false;
40 };
41 
42 template<typename T>
44 {
45  static void clear(T &v)
46  {
47  if (std::numeric_limits<T>::has_quiet_NaN) {
48  // Use QNaN as unused floating-point marker.
49  // NOTE: All NaNs get treated as unused, even if they're not
50  // the representative QNaN.
51  v = std::numeric_limits<T>::quiet_NaN();
52  }
53  else if (std::numeric_limits<T>::is_signed) {
54  // Use min as unused signed integer marker.
56  }
57  else {
58  // Use max as unused unsigned integer marker.
60  }
61  }
62  static bool isClear(T v)
63  {
64  if (std::numeric_limits<T>::has_quiet_NaN) {
65  // NOTE: All NaNs get treated as unused, even if they're not
66  // the representative QNaN.
67  return SYSisNan(v);
68  }
69  if (std::numeric_limits<T>::is_signed) {
70  return (v == std::numeric_limits<T>::min());
71  }
72  return (v == std::numeric_limits<T>::max());
73  }
74  static void clearConstruct(T *p) { clear(*p); }
75 
76  static const bool clearNeedsDestruction = false;
77 };
78 
79 template<> struct DefaultClearer< int8_t > : public NumericClearer< int8_t > {};
80 template<> struct DefaultClearer<uint8_t > : public NumericClearer<uint8_t > {};
81 template<> struct DefaultClearer< int16_t> : public NumericClearer< int16_t> {};
82 template<> struct DefaultClearer<uint16_t> : public NumericClearer<uint16_t> {};
83 template<> struct DefaultClearer< int32_t> : public NumericClearer< int32_t> {};
84 template<> struct DefaultClearer<uint32_t> : public NumericClearer<uint32_t> {};
85 template<> struct DefaultClearer< int64_t> : public NumericClearer< int64_t> {};
86 template<> struct DefaultClearer<uint64_t> : public NumericClearer<uint64_t> {};
87 template<> struct DefaultClearer<float> : public NumericClearer<float> {};
88 template<> struct DefaultClearer<double> : public NumericClearer<double> {};
89 template<> struct DefaultClearer<long double> : public NumericClearer<long double> {};
90 
91 /// NOTE: It may seem silly to have bool here, but things like
92 /// std::pair<T,bool> should work automatically, so they need some
93 /// default behaviour for bool.
94 template<>
95 struct DefaultClearer<bool>
96 {
97  static void clear(bool&v) { v = false; }
98  static bool isClear(bool v) { return !v; }
99  static void clearConstruct(bool *p) { clear(*p); }
100 
101  static const bool clearNeedsDestruction = false;
102 };
103 
104 template<typename S0,typename S1>
105 struct DefaultClearer<std::pair<S0,S1> >
106 {
107  static void clear(std::pair<S0,S1> &v)
108  {
109  DefaultClearer<S0>::clear(v.first);
110  DefaultClearer<S1>::clear(v.second);
111  }
112  static bool isClear(const std::pair<S0,S1> &v)
113  {
114  return DefaultClearer<S0>::isClear(v.first) && DefaultClearer<S1>::isClear(v.second);
115  }
116  static void clearConstruct(std::pair<S0,S1>*p) {
119  }
121 };
122 
123 /// This is close to a drop-in replacement for std::unordered_set,
124 /// except that it uses a single array of items and empty spaces
125 /// marked with a dedicated "clear" value.
126 /// It also has a fixed maximum load factor, and doesn't store a
127 /// hasher, comparator, or allocator object as member data,
128 /// avoiding unnecessary overhead, but these differences introduce
129 /// some interface incompatibilities.
130 ///
131 /// The incompatibility that will probably be encountered most often
132 /// is the lack of time guarantees. This structure is more efficient in
133 /// many common cases, due to better memory coherency and fewer
134 /// memory allocations, but cannot guarantee as good time scaling in
135 /// worst or even average case as std::unordered_set guarantees for most
136 /// functions.
137 ///
138 /// Because there is only space for one item in each bucket, if a collision
139 /// is hit on insertion, the structure will scan forward until a "clear"
140 /// bucket is found. However, items in a contiguous block will always
141 /// be sorted in the order of their ideal bucket numbers.
142 /// If the end of the array is reached without finding a clear bucket,
143 /// instead of the obvious approach of wrapping to the beginning of the
144 /// array, the block will be shifted backward, so some items in this
145 /// block at the end may be earlier than their ideal bucket number.
146 /// This is about as complicated as wrapping, or not sorting, but avoids
147 /// an awkward issue when erasing while iterating where an item might get
148 /// visited multiple times due to the wrapping, or items might be missed
149 /// due to the lack of order. Even still, unlike
150 /// std::unordered_set, erase may invalidate other iterators and references.
151 /// Also, insert may invalidate other iterators and references.
152 template<
153  typename Key,
154  bool MULTI=false,
155  std::size_t MAX_LOAD_FACTOR_256=128,
156  typename Clearer=DefaultClearer<Key>,
157  class Hash=std::hash<Key>,
158  class KeyEqual=std::equal_to<Key>
159 >
160 class ArraySet
161 {
162 public:
164  typedef Key key_type;
165  typedef Key value_type;
166  typedef std::size_t size_type;
167  typedef std::ptrdiff_t difference_type;
168  typedef Hash hasher;
169  typedef KeyEqual key_equal;
171  typedef const value_type& const_reference;
172  typedef value_type *pointer;
173  typedef const value_type *const_pointer;
174  typedef Clearer clearer_type;
175 
177  : myBuckets(nullptr)
178  , myNumBuckets(0)
179  {
180  UT_ASSERT_COMPILETIME(MAX_LOAD_FACTOR_256 <= 256);
181  }
182  explicit ArraySet(size_type init_bucket_count)
183  : myBuckets(nullptr)
184  , myNumBuckets(0)
185  {
186  if (init_bucket_count != 0)
187  setNumBuckets(init_bucket_count);
188  }
189 
190  /// Move constructor, destroying the source.
192  : myBuckets(that.myBuckets)
193  , myNumBuckets(that.myNumBuckets)
194  {
195  that.myBuckets = nullptr;
196  that.myNumBuckets = 0;
197  }
198 
199  /// Copy constructor.
200  /// Avoid accidental copying by making the constructor explicit.
201  explicit ArraySet(const set_type &that)
202  : myBuckets(nullptr)
203  , myNumBuckets(0)
204  {
205  *this = that;
206  }
207 
208  /// Inserts all of the items in the range [start_input,end_input).
209  template<typename INPUT_ITERATOR>
210  ArraySet(INPUT_ITERATOR start_input, INPUT_ITERATOR end_input, size_type init_bucket_count = 0)
211  : myBuckets(nullptr)
212  , myNumBuckets(0)
213  {
214  // Preallocate enough buckets, instead of waiting for
215  // insert to potentially hit collisions.
216  size_type ninput_items = std::distance(start_input, end_input);
217  setNumBuckets(SYSmax(init_bucket_count, minBuckets(ninput_items)));
218 
219  // Now, just insert them all, (no need to realloc)
220  for (; start_input != end_input; ++start_input)
221  {
222  pointer pdest;
223  bool success = insertHelper<!MULTI,false>(myBuckets,myNumBuckets,*start_input,pdest);
224  if (success)
225  *pdest = *start_input;
226  else
227  --ninput_items;
228  }
229  *((size_type*)(myBuckets+myNumBuckets)) = ninput_items;
230  }
231  /// Constructs a set from an initializer list, with an optional
232  /// bucket count, e.g.:
233  /// UT::ArraySet<int> some_set({5,123,500}, 20);
234  ArraySet(std::initializer_list<value_type> init, size_type init_bucket_count = 0)
235  : myBuckets(nullptr)
236  , myNumBuckets(0)
237  {
239  if (init_bucket_count == 0 || init_bucket_count < init.size()) {
240  bucket_count = minBuckets(init.size());
241  }
242  else {
243  bucket_count = init_bucket_count;
244  }
245  setNumBuckets(bucket_count);
246  for (auto &&p = init.begin(); p != init.end(); ++p) {
247  insert(*p);
248  }
249  }
250 
252  {
253  if (this == &that)
254  return *this;
255 
256  clear();
258 
259  if (!myBuckets)
260  return *this;
261 
262  size_type size = that.size();
263  *((size_type*)(myBuckets+myNumBuckets)) = size;
264 
265  if (size)
266  {
267  // Now, just copy them all, (no need to realloc)
268  const_pointer srcp = that.myBuckets;
270  for (pointer destp = myBuckets; destp != pend; ++destp, ++srcp)
271  {
272  *destp = *srcp;
273  }
274  }
275  return *this;
276  }
277 
278  set_type &operator=(std::initializer_list<value_type> init)
279  {
280  clear();
281  insert(init.begin(), init.end());
282  return *this;
283  }
284 
286  {
287  destroy();
288  myBuckets = that.myBuckets;
289  myNumBuckets = that.myNumBuckets;
290  that.myBuckets = nullptr;
291  that.myNumBuckets = 0;
292  return *this;
293  }
294 
295  bool operator==(const set_type &that) const
296  {
297  if (size() != that.size())
298  return false;
299 
300  // Check if one has no allocation (both empty)
301  if (!myBuckets || !that.myBuckets)
302  return true;
303 
304  const const_pointer pend = myBuckets + myNumBuckets;
305  for (const_pointer p = myBuckets; p != pend; ++p)
306  {
307  if (Clearer::isClear(*p))
308  continue;
309  // NOTE: Don't just use that.contains(*p), in case it doesn't check the whole item contents!
310  const_iterator it = that.find(*p);
311  if (it.atEnd())
312  return false;
313  if (*p != *it)
314  return false;
315  }
316  return true;
317  }
318  bool operator!=(const set_type &that) const
319  {
320  return !(*this == that);
321  }
322 
323  /// Swaps another set with this one
324  void swap(set_type &that)
325  {
326  pointer temp_buckets = that.myBuckets;
327  size_type temp_numbuckets = that.myNumBuckets;
328  that.myBuckets = myBuckets;
329  that.myNumBuckets = myNumBuckets;
330  myBuckets = temp_buckets;
331  myNumBuckets = temp_numbuckets;
332  }
333 
335  {
336  destroy();
337  }
338 
339  /// Returns true iff there are no items in the set
340  bool empty() const
341  {
342  return !myBuckets || (*((const size_type*)(myBuckets+myNumBuckets)) == 0);
343  }
344 
345  /// Returns the number of items in the set
346  size_type size() const
347  {
348  return myBuckets ? *(const size_type*)(myBuckets+myNumBuckets) : 0;
349  }
350 
351  /// This only exists because the standard requires it.
352  /// The only hard limit is what memory will allow.
354  {
356  }
357 
358  /// Removes all items from the set, but does not free the memory.
359  /// Call destroy() to free all the memory.
360  void clear()
361  {
362  if (!myBuckets)
363  return;
364  pointer p = myBuckets;
365  pointer pend = p+myNumBuckets;
366  if (*((const size_type*)pend) == 0)
367  return;
368  while (p != pend)
369  {
370  Clearer::clear(*p);
371  ++p;
372  }
373  *((size_type*)pend) = 0;
374  }
375 
376  /// Removes all items from the set and frees all the memory.
377  void destroy()
378  {
379  if (!myBuckets)
380  return;
381  if (!std::is_trivially_destructible<value_type>::value && (Clearer::clearNeedsDestruction || !empty()))
382  {
383  pointer p = myBuckets;
384  const_pointer pend = p+myNumBuckets;
385  while (p != pend)
386  {
387  // I'm assuming that in some cases, it's faster to check isClear than to call the destructor,
388  // even if it's only because of a better chance of inlining.
389  if (Clearer::clearNeedsDestruction || !Clearer::isClear(*p))
390  p->~value_type();
391  ++p;
392  }
393  }
394  free(myBuckets);
395  myBuckets = nullptr;
396  myNumBuckets = 0;
397  }
398 
399  /// Returns the current number of buckets.
401  {
402  return myNumBuckets;
403  }
404 
405  /// This only exists because the standard requires it.
406  /// The only hard limit is what memory will allow.
408  {
410  }
411 
412  /// This only exists because the standard requires it.
413  /// This function doesn't really make sense for this implementation,
414  /// but it returns 1 if the bucket is occupied, and 0 if it is not.
416  {
417  if (i >= myNumBuckets) {
418  return 0;
419  }
420  if (Clearer::isClear(myBuckets[i])) {
421  return 0;
422  }
423  return 1;
424  }
425 
426  /// Returns the portion of buckets that need to be occupied before
427  /// reallocation occurs.
428  /// Unlike in the standard, the maximum load factor is a constant
429  /// in this implementation, so max_load_factor() is a static function.
430  static float max_load_factor()
431  {
432  return float(MAX_LOAD_FACTOR_256)/256;
433  }
434 
435  /// Returns the current portion of buckets that are occupied.
436  float load_factor() const
437  {
438  return float(size())/float(myNumBuckets);
439  }
440 
441  /// Sets the number of buckets to larger of new_num_buckets and the
442  /// required minimum number of buckets for size() items, unless
443  /// that number is the same as the current number of buckets.
444  void rehash(size_type new_num_buckets)
445  {
446  size_type min_buckets = minBuckets(size());
447  if (new_num_buckets < min_buckets) {
448  new_num_buckets = min_buckets;
449  }
450  if (myNumBuckets == new_num_buckets) {
451  return;
452  }
453  setNumBuckets(min_buckets);
454  }
455 
456  /// Sets the number of buckets to the required minimum number of buckets
457  /// for the larger of num_items and size().
458  void reserve(size_type num_items)
459  {
460  size_type min_buckets = minBuckets(SYSmax(size(),num_items));
461  setNumBuckets(min_buckets);
462  }
463 
464  /// Sets the number of buckets to new_num_buckets, regardless of the
465  /// required minimum number of buckets for size() items, though
466  /// you probably shouldn't be calling it with num_new_buckets < size(),
467  /// except that if num_new_buclets==0, this calls destroy().
468  void setNumBuckets(size_type new_num_buckets)
469  {
470  if (new_num_buckets == myNumBuckets)
471  return;
472  if (new_num_buckets == 0)
473  {
474  // Assume that the caller wants to delete everything
475  destroy();
476  return;
477  }
478 
479  size_type old_size = size();
480  if (new_num_buckets < old_size)
481  {
482  UT_ASSERT_MSG(0,"What does the caller expect to happen when setting the number of buckets lower than the size, but not to zero?\nThis class doesn't support multiple items per bucket.");
483  new_num_buckets = old_size;
484  }
485 
486  // NOTE: I'm assuming that the caller, in explicitly calling
487  // setNumBuckets, doesn't want to be limited by MAX_LOAD_FACTOR_256,
488  // so don't check against it.
489 
490  pointer new_buckets = (pointer)malloc(new_num_buckets*sizeof(value_type) + sizeof(size_type));
491  pointer new_end = new_buckets + new_num_buckets;
492  for (pointer p = new_buckets; p < new_end; ++p)
493  {
494  Clearer::clearConstruct(p);
495  }
496 
497  if (old_size)
498  {
499  // Move items over and clear them from myBuckets
501  for (pointer srcp = myBuckets; srcp < pend; ++srcp)
502  {
503  if (!Clearer::isClear(*srcp))
504  {
505  value_type v;
506  Clearer::clear(v);
507  // Need to make sure that *p is set to clear,
508  // as opposed to whatever std::move leaves it as,
509  // so swap with clear.
510  std::swap(*srcp, v);
511  pointer destp;
512  insertHelper<false,false>(new_buckets, new_num_buckets, v, destp);
513  *destp = std::move(v);
514  }
515  }
516 
517  // Temporarily set the size to 0, so that destroy() won't re-destruct them.
518  *((size_type*)pend) = 0;
519  }
520  // Don't worry; this will just destruct the current buckets
521  destroy();
522 
523  myBuckets = new_buckets;
524  myNumBuckets = new_num_buckets;
525  *((size_type*)new_end) = old_size;
526  }
527 
528  /// This increases the number of buckets, if needed, for
529  /// the specified number of items
530  void bumpNumBuckets(size_type new_num_items)
531  {
532  size_type num_buckets = minBuckets(new_num_items);
533  if (num_buckets <= myNumBuckets)
534  return;
535  // Although UT_Array normally bumps up by about 12.5% each time,
536  // and so does UTbumpAllocToPrime, to reduce significant rehashing
537  // overhead, we bump to at least twice the previous size.
538  num_buckets = SYSmax(num_buckets, 2*myNumBuckets);
539  num_buckets = UTbumpAllocToPrime(num_buckets);
540  setNumBuckets(num_buckets);
541  }
542 
543  /// Set iterator class
544  template<bool constant_type>
546  {
547  public:
548  typedef std::forward_iterator_tag iterator_category;
549  typedef std::ptrdiff_t difference_type;
553 
554  iterator_t() = default;
555  iterator_t(pointer current, const_pointer end, bool scan=true)
556  : myCurrent(current)
557  , myEnd(end)
558  {
559  UT_ASSERT_MSG_P(scan || current == end || !Clearer::isClear(*current), "An iterator can't point to a clear item!");
560  if (scan)
561  {
562  while (myCurrent != myEnd && Clearer::isClear(*myCurrent))
563  {
564  ++myCurrent;
565  }
566  }
567  }
568  iterator_t(const iterator_t &) = default;
569  iterator_t(iterator_t &&) = default;
570  iterator_t &operator=(const iterator_t &) = default;
571  iterator_t &operator=(iterator_t &&) = default;
572  bool operator==(const iterator_t &that) const
573  {
574  UT_ASSERT_MSG_P(myEnd == that.myEnd, "Probably unintentional: Comparing against iterator from different set or iterator invalidated by reallocation!");
575  return (myCurrent == that.myCurrent);
576  }
577  bool operator!=(const iterator_t &that) const
578  {
579  UT_ASSERT_MSG_P(myEnd == that.myEnd, "Probably unintentional: Comparing against iterator from different set or iterator invalidated by reallocation!");
580  return (myCurrent != that.myCurrent);
581  }
582  bool atEnd() const
583  {
584  return myCurrent == myEnd;
585  }
587  {
588  UT_ASSERT_MSG_P(myCurrent < myEnd, "Incrementing end iterator!");
589  if (myCurrent == myEnd) {
590  return *this;
591  }
592  do {
593  ++myCurrent;
594  } while (myCurrent != myEnd && Clearer::isClear(*myCurrent));
595  return *this;
596  }
597 
598  // This is intentionally not implemented to force its non-use but we
599  // keep it here just in case there's weird C++ rules on iterator
600  // requirements
602 
604  {
605  UT_ASSERT_MSG_P(myCurrent < myEnd, "Dereferencing end iterator!");
606  return *myCurrent;
607  }
609  {
610  UT_ASSERT_MSG_P(myCurrent < myEnd, "Dereferencing end iterator!");
611  return myCurrent;
612  }
613  operator pointer() const
614  {
615  UT_ASSERT_MSG_P(myCurrent <= myEnd, "Dereferencing iterator past end!");
616  return myCurrent;
617  }
619  {
620  UT_ASSERT_MSG_P(myCurrent <= myEnd, "Dereferencing iterator past end!");
621  return myCurrent;
622  }
624  {
625  return myEnd;
626  }
627  private:
628  friend class iterator_t<!constant_type>;
629 
630  pointer myCurrent;
631  const_pointer myEnd;
632  };
633 
634  /// Iterator type for iterating over non-constant elements.
635  typedef iterator_t<false> iterator;
636 
637  /// Iterator type for iterating over constant elements.
638  /// It may be useful to convert an iterator to a const_iterator,
639  /// so making this a subclass lets us add a constructor for that.
640  class const_iterator : public iterator_t<true>
641  {
642  public:
644 
645  const_iterator() = default;
646  const_iterator(const iterator &non_const_it)
647  : iterator_t<true>(non_const_it.getCurrent(), non_const_it.getEnd(), false)
648  {}
649  };
650 
651  /// Returns a non-const iterator for the beginning of the set.
653  {
655  }
656  /// Returns a const iterator for the beginning of the set.
657  const_iterator cbegin() const
658  {
659  return const_iterator(myBuckets,myBuckets+myNumBuckets,true);
660  }
661  /// Returns a const iterator for the beginning of the set.
662  const_iterator begin() const
663  {
664  return const_iterator(myBuckets,myBuckets+myNumBuckets,true);
665  }
666  /// Returns a non-const end iterator for the set.
668  {
670  return iterator(pend,pend,false);
671  }
672  /// Returns a const end iterator for the set.
673  const_iterator cend() const
674  {
676  return const_iterator(pend,pend,false);
677  }
678  /// Returns a const end iterator for the set.
679  const_iterator end() const
680  {
682  return const_iterator(pend,pend,false);
683  }
684 
685  /// Returns an iterator to the first item matching key,
686  /// or an end iterator if no items match key.
687  /// @{
688  iterator find(const Key &key)
689  {
690  UT_ASSERT_MSG_P(!Clearer::isClear(key),"Don't query a clear key!");
691 
692  const pointer pstart = myBuckets;
693  if (!pstart)
694  return iterator(nullptr,nullptr,false);
695 
696  const pointer pend = pstart + myNumBuckets;
697 
698  const pointer search_start = searchStart(key);
699  for (pointer p = search_start; p != pend; ++p)
700  {
701  if (key_equal()(key,*p))
702  return iterator(p,pend,false);
703  if (Clearer::isClear(*p))
704  return iterator(pend,pend,false);
705  }
706  // Hit the end, so search back from before the start of the block.
707  for (pointer p = search_start-1; p >= pstart; --p)
708  {
709  if (key_equal()(key,*p))
710  return iterator(p,pend,false);
711  if (Clearer::isClear(*p))
712  return iterator(pend,pend,false);
713  }
714  return iterator(pend,pend,false);
715  }
716  const_iterator find(const Key &key) const
717  {
718  UT_ASSERT_MSG_P(!Clearer::isClear(key),"Don't query a clear key!");
719 
720  const const_pointer pstart = myBuckets;
721  if (!pstart)
722  return const_iterator(nullptr,nullptr,false);
723 
724  const const_pointer pend = pstart + myNumBuckets;
725 
726  const_pointer search_start = searchStart(key);
727  for (const_pointer p = search_start; p != pend; ++p)
728  {
729  if (key_equal()(key,*p))
730  return const_iterator(p,pend,false);
731  if (Clearer::isClear(*p))
732  return const_iterator(pend,pend,false);
733  }
734  // Hit the end, so search back from before the start of the block.
735  for (const_pointer p = search_start-1; p >= pstart; --p)
736  {
737  if (key_equal()(key,*p))
738  return const_iterator(p,pend,false);
739  if (Clearer::isClear(*p))
740  return const_iterator(pend,pend,false);
741  }
742  return const_iterator(pend,pend,false);
743  }
744  /// @}
745 
746  /// Returns the number of entries matching key.
747  /// If MULTI is false, this will only return either 0 or 1.
748  size_type count(const Key &key) const
749  {
750  UT_ASSERT_MSG_P(!Clearer::isClear(key),"Don't query a clear key!");
751 
752  if (!myBuckets)
753  return 0;
754 
755  const const_pointer pstart = myBuckets;
756  const const_pointer pend = pstart + myNumBuckets;
757  const_pointer search_start = searchStart(key);
758  size_type count = 0;
759  for (const_pointer p = search_start; p != pend; ++p)
760  {
761  if (key_equal()(key,*p))
762  {
763  if (!MULTI)
764  return 1;
765  ++count;
766  }
767  else if (Clearer::isClear(*p))
768  return MULTI ? count : 0;
769  }
770  // Hit the end, so search back from before the start of the block.
771  for (const_pointer p = search_start-1; p >= pstart; --p)
772  {
773  if (key_equal()(key,*p))
774  {
775  if (!MULTI)
776  return 1;
777  ++count;
778  }
779  else if (Clearer::isClear(*p))
780  return MULTI ? count : 0;
781  }
782  return MULTI ? count : 0;
783  }
784 
785  /// Returns true iff the set contains the given key.
786  /// This should be faster than count() if MULTI is true.
787  bool contains(const Key &key) const
788  {
789  UT_ASSERT_MSG_P(!Clearer::isClear(key),"Don't query a clear key!");
790 
791  if (!myBuckets)
792  return false;
793 
794  const const_pointer pstart = myBuckets;
795  const const_pointer pend = pstart + myNumBuckets;
796  const_pointer search_start = searchStart(key);
797  for (const_pointer p = search_start; p != pend; ++p)
798  {
799  if (key_equal()(key,*p))
800  return true;
801  if (Clearer::isClear(*p))
802  return false;
803  }
804  // Hit the end, so search back from before the start of the block.
805  for (const_pointer p = search_start-1; p >= pstart; --p)
806  {
807  if (key_equal()(key,*p))
808  return true;
809  if (Clearer::isClear(*p))
810  return false;
811  }
812  return false;
813  }
814 
815  /// Returns a pair of iterators representing the range of values matching
816  /// key, as [first,second).
817  /// @{
818  std::pair<const_iterator,const_iterator> equal_range(const Key &key) const
819  {
820  UT_ASSERT_MSG_P(!Clearer::isClear(key),"Don't query a clear key!");
821 
822  const const_pointer pstart = myBuckets;
823  const const_pointer pend = pstart + myNumBuckets;
824  if (!pstart)
825  return std::make_pair(const_iterator(nullptr,nullptr,false), const_iterator(nullptr,nullptr,false));
826 
827  const const_pointer search_start = searchStart(key);
828  if (!MULTI)
829  {
830  for (const_pointer p = search_start; p != pend; ++p)
831  {
832  if (key_equal()(key,*p))
833  return std::make_pair(const_iterator(p,pend,false), const_iterator(p+1,pend,true));
834  if (Clearer::isClear(*p))
835  return std::make_pair(const_iterator(pend,pend,false), const_iterator(pend,pend,false));
836  }
837  // Hit the end, so search back from before the start of the block.
838  for (const_pointer p = search_start-1; p >= pstart; --p)
839  {
840  if (key_equal()(key,*p))
841  return std::make_pair(const_iterator(p,pend,false), const_iterator(p+1,pend,true));
842  if (Clearer::isClear(*p))
843  return std::make_pair(const_iterator(pend,pend,false), const_iterator(pend,pend,false));
844  }
845  return std::make_pair(const_iterator(pend,pend,false), const_iterator(pend,pend,false));
846  }
847 
848  // MULTI is true, so we might have multiple matches
849  const_pointer first_found = nullptr;
850  const_pointer end_found = pend;
851  for (const_pointer p = search_start; p != pend; ++p)
852  {
853  if (key_equal()(key,*p))
854  {
855  if (!first_found)
856  first_found = p;
857  }
858  else if (first_found)
859  {
860  if (first_found != search_start)
861  return std::make_pair(const_iterator(first_found,pend,false), const_iterator(p,pend,true));
862 
863  end_found = p;
864  break;
865  }
866  else if (Clearer::isClear(*p))
867  {
868  // NOTE: first_found must be false
869  return std::make_pair(const_iterator(pend,pend,false), const_iterator(pend,pend,false));
870  }
871  }
872 
873  // Hit the end, so search back from before the start of the block.
874  for (const_pointer p = search_start-1; p >= pstart; --p)
875  {
876  if (!key_equal()(key,*p))
877  {
878  return std::make_pair(const_iterator(p+1,pend,false), const_iterator(end_found,pend,true));
879  }
880  }
881  return std::make_pair(const_iterator(pstart,pend,false), const_iterator(end_found,pend,true));
882  }
883  std::pair<iterator,iterator> equal_range(const Key &key)
884  {
885  UT_ASSERT_MSG_P(!Clearer::isClear(key),"Don't query a clear key!");
886 
887  const pointer pstart = myBuckets;
888  const pointer pend = pstart + myNumBuckets;
889  if (!pstart)
890  return std::make_pair(iterator(nullptr,nullptr,false), iterator(nullptr,nullptr,false));
891 
892  const pointer search_start = searchStart(key);
893  if (!MULTI)
894  {
895  for (pointer p = search_start; p != pend; ++p)
896  {
897  if (key_equal()(key,*p))
898  return std::make_pair(iterator(p,pend,false), iterator(p+1,pend,true));
899  if (Clearer::isClear(*p))
900  return std::make_pair(iterator(pend,pend,false), iterator(pend,pend,false));
901  }
902  // Hit the end, so search back from before the start of the block.
903  for (pointer p = search_start-1; p >= pstart; --p)
904  {
905  if (key_equal()(key,*p))
906  return std::make_pair(iterator(p,pend,false), iterator(p+1,pend,true));
907  if (Clearer::isClear(*p))
908  return std::make_pair(iterator(pend,pend,false), iterator(pend,pend,false));
909  }
910  return std::make_pair(iterator(pend,pend,false), iterator(pend,pend,false));
911  }
912 
913  // MULTI is true, so we might have multiple matches
914  pointer first_found = nullptr;
915  pointer end_found = pend;
916  for (pointer p = search_start; p != pend; ++p)
917  {
918  if (key_equal()(key,*p))
919  {
920  if (!first_found)
921  first_found = p;
922  }
923  else if (first_found)
924  {
925  if (first_found != search_start)
926  return std::make_pair(iterator(first_found,pend,false), iterator(p,pend,true));
927 
928  end_found = p;
929  break;
930  }
931  else if (Clearer::isClear(*p))
932  {
933  // NOTE: first_found must be false
934  return std::make_pair(iterator(pend,pend,false), iterator(pend,pend,false));
935  }
936  }
937 
938  // Hit the end, so search back from before the start of the block.
939  for (pointer p = search_start-1; p >= pstart; --p)
940  {
941  if (!key_equal()(key,*p))
942  {
943  return std::make_pair(iterator(p+1,pend,false), iterator(end_found,pend,true));
944  }
945  }
946  return std::make_pair(iterator(pstart,pend,false), iterator(end_found,pend,true));
947  }
948  /// @}
949 
950  /// Inserts the given value into the set, unless MULTI is false and
951  /// there's already an item for which key_equal()(value,other)
952  /// returns true. Returns a pair of iterator to the inserted value
953  /// (or the existing item if not inserted), and a bool that's true
954  /// iff the item was inserted.
955  /// @{
956  std::pair<iterator, bool> insert(const value_type &value)
957  {
958  pointer p;
959  bool success = insertHelper(myBuckets, myNumBuckets, value, p);
960  if (success)
961  {
962  *p = value;
964  }
965  return std::make_pair(iterator(p,myBuckets+myNumBuckets,false),success);
966  }
967  std::pair<iterator, bool> insert(value_type &&value)
968  {
969  pointer p;
970  bool success = insertHelper(myBuckets, myNumBuckets, value, p);
971  if (success)
972  {
973  *p = std::move(value);
975  }
976  return std::make_pair(iterator(p,myBuckets+myNumBuckets,false),success);
977  }
978  /// @}
979 
980  /// Inserts all of the items in the range [start_input,end_input).
981  template<typename INPUT_ITERATOR>
982  void insert(INPUT_ITERATOR start_input, INPUT_ITERATOR end_input)
983  {
984  // Preallocate enough buckets, instead of waiting for
985  // insert to potentially hit collisions.
986  size_type ninput_items = std::distance(start_input, end_input);
987  if (!ninput_items)
988  return;
989 
990  size_type new_size = size() + ninput_items;
991  if (myNumBuckets < minBuckets(new_size))
992  bumpNumBuckets(new_size);
993 
994  // Now, just insert them all, (no need to realloc)
995  for (; start_input != end_input; ++start_input)
996  {
997  pointer pdest;
998  bool success = insertHelper<!MULTI,false>(myBuckets,myNumBuckets,*start_input,pdest);
999  if (success)
1000  *pdest = *start_input;
1001  else
1002  --new_size;
1003 
1004  }
1005  *((size_type*)(myBuckets+myNumBuckets)) = new_size;
1006  }
1007  /// Inserts all of the items from the initializer_list.
1008  void insert(std::initializer_list<value_type> list)
1009  {
1010  // Just delegate to the iterator range insert function.
1011  insert(list.begin(),list.end());
1012  }
1013 
1014  /// Inserts an element constructed with the given arguments.
1015  /// Maybe the standard implementation can somehow get a speedup
1016  /// from this, but we need the item's hash before inserting,
1017  /// so it needs to be constructed first.
1018  template <typename... Args>
1019  std::pair<iterator,bool> emplace(Args&&... args)
1020  {
1021  return insert(value_type(std::forward<Args>(args)...));
1022  }
1023 
1024  /// Removes the item at the specified iterator location,
1025  /// returning an iterator to the next item.
1026  ///
1027  /// Unlike std::unordered_set::erase(const_iterator), this may
1028  /// invalidate iterators and references to other items in the
1029  /// map, if they are in a contiguous block of non-empty items
1030  /// with the item that iter points to. Also, this only
1031  /// accepts an iterator, instead of a const_iterator.
1032  /// (Why would std::unordered_set::erase accept a const_iterator?)
1034  {
1035  const pointer pstart = myBuckets;
1036  const pointer pend = pstart + myNumBuckets;
1037 
1038  const pointer p = (pointer)iter;
1039 
1040  UT_ASSERT_MSG_P(p >= pstart && p < pend && !Clearer::isClear(*p), "An iterator to erase can't point to a clear item!");
1041 
1042  // Actually erase the item
1043  Clearer::clear(*p);
1044  size_type new_size = --*((size_type*)(myBuckets+myNumBuckets));
1045 
1046  if (new_size == 0)
1047  return iterator(pend,pend,false);
1048 
1049  // Check for the common, simple case, where there's nothing after p in
1050  // the block of possible conflicts, and p isn't at the end.
1051  pointer pnext = p+1;
1052  bool end_case = (pnext == pend);
1053  if (!end_case)
1054  {
1055  if (Clearer::isClear(*pnext))
1056  return iterator(pnext,pend,true);
1057 
1058  // Now, for the hard case... -_-
1059 
1060  // If we're not right at the end of the array already,
1061  // find the end of the block, and check if it's the end of the array.
1062  // pnext is already clear, else we'd have returned above.
1063  do
1064  {
1065  ++pnext;
1066  end_case = (pnext == pend);
1067  } while (!end_case && !Clearer::isClear(*pnext));
1068  }
1069 
1070  if (end_case && (p != pstart) && !Clearer::isClear(*(p-1)))
1071  {
1072  // If this is a block right at the end of the array, there may be earlier
1073  // items that are too early, in which case, we need to shift
1074  // everything after that down one, into the empty spot.
1075 
1076  // Find the start of the block.
1077  pointer pprev = p-1;
1078  while (pprev != pstart && !Clearer::isClear(*(pprev-1)))
1079  {
1080  --pprev;
1081  }
1082 
1083  // Find the earliest item that should go at or after
1084  // its current bucket.
1085  do
1086  {
1087  // Check where this item ideally belongs.
1088  size_type hash = hasher()(*pprev);
1089  size_type ideal_bucket_num = hash%myNumBuckets;
1090  if (ideal_bucket_num > (pprev-pstart))
1091  {
1092  // Shift everything later by one and return.
1093  for (pointer pdest = p; pdest != pprev; --pdest)
1094  {
1095  *pdest = std::move(*(pdest-1));
1096  }
1097  Clearer::clear(*pprev);
1098  return iterator(p+1,pend,true);
1099  }
1100 
1101  ++pprev;
1102  } while (pprev != p);
1103  }
1104 
1105  if (p+1 != pend)
1106  {
1107  // We're not at the end of the array, or there were no items before
1108  // this block to move into the empty space, but there is at least
1109  // one item after p, so shift items backward until there's one
1110  // that doesn't belong earlier than it is now.
1111 
1112  size_type empty_bucket_num = p-pstart;
1113 
1114  // NOTE: pnext points to the end of this block.
1115  for (pointer pdest = p; pdest+1 != pnext; ++pdest)
1116  {
1117  // Check where this item ideally belongs.
1118  size_type hash = hasher()(*(pdest+1));
1119  size_type ideal_bucket_num = hash%myNumBuckets;
1120  if (ideal_bucket_num > empty_bucket_num)
1121  {
1122  Clearer::clear(*pdest);
1123  return iterator(p+(pdest==p),pend,false);
1124  }
1125 
1126  *pdest = std::move(*(pdest+1));
1127  ++empty_bucket_num;
1128  }
1129  Clearer::clear(*(pnext-1));
1130  // p now contains an item that was previously after it.
1131  return iterator(p,pend,false);
1132  }
1133 
1134  // p is still empty, but there's an item (or the end pointer)
1135  // right after it.
1136  return iterator(p+1,pend,false);
1137  }
1138 
1139  /// Removes all items in the range [start_iter,end_iter),
1140  /// and returns an iterator immediately following that range.
1141  ///
1142  /// Unlike std::unordered_set::erase(const_iterator,const_iterator),
1143  /// this may invalidate iterators and references to other items in the
1144  /// map, if they are in a contiguous block of non-empty items
1145  /// with the items in the erased range. Also, this only
1146  /// accepts iterator's, instead of const_iterator's.
1147  /// (Why would std::unordered_set::erase accept a const_iterator?)
1148  iterator erase(iterator start_iter, iterator end_iter) {
1149  if (start_iter == end_iter)
1150  return end_iter;
1151 
1152  const pointer pstart = myBuckets;
1153  const const_pointer pend = pstart + myNumBuckets;
1154 
1155  const pointer prange_start = (pointer)start_iter;
1156  const pointer prange_end = (pointer)end_iter;
1157 
1158  UT_ASSERT_MSG_P(prange_start >= pstart && prange_start < prange_end && prange_end <= pend && !Clearer::isClear(*prange_start), "An iterator to erase can't point to a clear item!");
1159 
1160  // Actually erase the items
1161  size_type nremoved_items = 1;
1162  size_type nitems_in_last_block = 1;
1163  Clearer::clear(*prange_start);
1164  for (pointer p = prange_start+1; p != prange_end; ++p)
1165  {
1166  if (!Clearer::isClear(*p))
1167  {
1168  Clearer::clear(*p);
1169  ++nitems_in_last_block;
1170  ++nremoved_items;
1171  }
1172  else
1173  {
1174  nitems_in_last_block = 0;
1175  }
1176  }
1177 
1178  size_type new_size = (*((size_type*)(myBuckets+myNumBuckets)) -= nremoved_items);
1179 
1180  if (new_size == 0)
1181  {
1182  // This must be pointing to the end of the array.
1183  return end_iter;
1184  }
1185 
1186  pointer block_end = prange_end;
1187 
1188  if (prange_end != pend)
1189  {
1190  // NOTE: If prange_end is not pend, it is always occupied, because
1191  // it came from an iterator, which should be dereferenceable.
1192  // However, if there was a gap between the last removed item
1193  // and prange_end, we can still exit early.
1194  if (nitems_in_last_block == 0)
1195  return end_iter;
1196 
1197  // Find the end of the block
1198  do
1199  {
1200  ++block_end;
1201  } while (block_end != pend && !Clearer::isClear(*block_end));
1202  }
1203  else {
1204  // If end_iter is at the array end, and there's at least one empty
1205  // spot in the given range, we're done, because the last block
1206  // was completely eliminated.
1207  if (nitems_in_last_block != prange_end-prange_start)
1208  return end_iter;
1209  }
1210 
1211  UT_ASSERT_P(nitems_in_last_block > 0);
1212 
1213  // If the end of the block is the array end and
1214  // nitems_in_last_block == prange_end-prange_start (no gaps),
1215  // find the beginning of the block, and if there are any items that
1216  // belong in later buckets:
1217  // 1) shift everything after to the end of the clear block.
1218  // 2) move them backward to where they belong, as available.
1219  // 3) if there is still an item in the last cleared spot, return.
1220  if (block_end == pend && nitems_in_last_block == prange_end-prange_start && prange_start != pstart && !Clearer::isClear(*(prange_start-1)))
1221  {
1222  // Find the start of the block.
1223  pointer block_start = prange_start;
1224  do
1225  {
1226  --block_start;
1227  } while (block_start != pstart && !Clearer::isClear(*(block_start-1)));
1228 
1229  UT_ASSERT_MSG(0,"FIXME: Implement this!!!");
1230  }
1231 
1232  // Move items backward until there's one that doesn't
1233  // need to be moved backward.
1234  UT_ASSERT_MSG(0,"FIXME: Implement this!!!");
1235  return end_iter; // This is probably incorrect, but just to get it to compile
1236  }
1237 
1238  /// Removes all items matching key and returns
1239  /// the number of items removed.
1240  size_type erase(const Key &key)
1241  {
1242  if (!MULTI)
1243  {
1244  iterator it = find(key);
1245  if (it.atEnd())
1246  return 0;
1247  erase(it);
1248  return 1;
1249  }
1250 
1251  std::pair<iterator,iterator> its = equal_range(key);
1252  size_type count = std::distance(its.first, its.second);
1253  erase(its.first, its.second);
1254  return count;
1255  }
1256 
1257  /// NOTE: std::unordered_set::hash_function() isn't static,
1258  /// but here, we're not storing a hasher as
1259  /// a data member, so it's independent of the instance.
1261  {
1262  return hasher();
1263  }
1264 
1265  /// NOTE: std::unordered_set::key_eq() isn't static,
1266  /// but here, we're not storing a key_equal as
1267  /// a data member, so it's independent of the instance.
1269  {
1270  return key_equal();
1271  }
1272 
1273  /// Returns the amount of memory used by this, excluding any memory that might be
1274  /// allocated by any of the items, themselves.
1275  int64 getMemoryUsage(bool inclusive) const
1276  {
1277  int64 mem = inclusive ? sizeof(*this) : 0;
1278  mem += sizeof(value_type)*myNumBuckets;
1279  return mem;
1280  }
1281 
1282  template<typename FUNCTOR>
1284  void forEach(FUNCTOR &&functor) const
1285  {
1287  const const_pointer pend = p + myNumBuckets;
1288  for (; p != pend; ++p)
1289  {
1290  if (!Clearer::isClear(*p))
1291  functor(*p);
1292  }
1293  }
1294 
1295 protected:
1297  {
1298  // If there are only 0-2 elements, there might as well only be
1299  // that many buckets.
1300  if (size <= 2)
1301  return size;
1302 
1303  // Simpler case if MAX_LOAD_FACTOR_256 evenly divides 256
1304  if ((256%MAX_LOAD_FACTOR_256) == 0)
1305  // +1 because otherwise it's guaranteed to be composite.
1306  return size * (256/MAX_LOAD_FACTOR_256) + 1;
1307 
1308  return (size*256 + MAX_LOAD_FACTOR_256-1)/MAX_LOAD_FACTOR_256;
1309  }
1310  pointer searchStart(const Key &key)
1311  {
1312  const size_type hash = hasher()(key);
1313  return myBuckets + (hash%myNumBuckets);
1314  }
1315  const_pointer searchStart(const Key &key) const
1316  {
1317  const size_type hash = hasher()(key);
1318  return myBuckets + (hash%myNumBuckets);
1319  }
1320 
1321  template<bool fail_on_equal=!MULTI,bool check_realloc=true>
1322  bool insertHelper(pointer pstart, size_type nbuckets, const value_type &value,pointer &destp)
1323  {
1324  UT_ASSERT_P(!Clearer::isClear(value));
1325 
1326  if (check_realloc && nbuckets == 0)
1327  {
1328  setNumBuckets(1);
1329  destp = myBuckets;
1330  return true;
1331  }
1332 
1333  const pointer pend = pstart + nbuckets;
1334  const size_type hash = hasher()(value);
1335  const size_type ideal_bucket = (hash%nbuckets);
1336  pointer init_searchp = pstart + ideal_bucket;
1337  pointer searchp = init_searchp;
1338 
1339  if (Clearer::isClear(*searchp))
1340  {
1341  // Don't bother checking MAX_LOAD_FACTOR_256 if exact match is clear,
1342  // since there's no harm in perfect hashes... unless it fills up and
1343  // people do a lot of querying keys that aren't in the set.
1344  // If that ends up being a bottleneck, feel free to change this.
1345  destp = searchp;
1346  return true;
1347  }
1348 
1349  if (fail_on_equal && key_equal()(*searchp,value))
1350  {
1351  destp = searchp;
1352  return false;
1353  }
1354 
1355  if (!fail_on_equal)
1356  {
1357  // We're always adding one.
1358  size_type new_size = size() + 1;
1359  if (check_realloc && nbuckets < minBuckets(new_size)) {
1360  bumpNumBuckets(new_size);
1361  // Delegate to version that doesn't check for realloc.
1362  return insertHelper<fail_on_equal,false>(myBuckets,myNumBuckets,value,destp);
1363  }
1364  // We're not reallocating in this case.
1365  }
1366 
1367  // Find the place where our ideal bucket is less than the next
1368  // item's ideal bucket.
1369  if ((hasher()(*searchp)%nbuckets) <= ideal_bucket)
1370  {
1371  while (true)
1372  {
1373  ++searchp;
1374  if (searchp == pend || Clearer::isClear(*searchp))
1375  break;
1376 
1377  const size_type other_hash = hasher()(*searchp);
1378  if (fail_on_equal && other_hash==hash && key_equal()(*searchp,value))
1379  {
1380  destp = searchp;
1381  return false;
1382  }
1383  if (ideal_bucket < (other_hash%nbuckets))
1384  break;
1385  }
1386  }
1387  pointer insertp = searchp;
1388 
1389  // Find the end of the block
1390  while (searchp != pend && !Clearer::isClear(*searchp))
1391  {
1392  ++searchp;
1393  }
1394 
1395  if (searchp != pend)
1396  {
1397  // Common case: block end is not the array end.
1398 
1399  if (fail_on_equal)
1400  {
1401  // We're always adding one.
1402  size_type new_size = *((const size_type*)pend) + 1;
1403  if (check_realloc && nbuckets < minBuckets(new_size))
1404  {
1405  bumpNumBuckets(new_size);
1406  // Delegate to version that doesn't check for realloc.
1407  return insertHelper<fail_on_equal,false>(myBuckets,myNumBuckets,value,destp);
1408  }
1409  // We're not reallocating in this case.
1410  }
1411 
1412  // Move items later by one.
1413  while (searchp != insertp)
1414  {
1415  *searchp = std::move(*(searchp-1));
1416  --searchp;
1417  }
1418  destp = insertp;
1419  return true;
1420  }
1421 
1422  // Less common case: block end is the array end.
1423  // insertp may actually need to go earlier, because
1424  // we can't move items later, else they'd be past the end.
1425  if (insertp == init_searchp)
1426  {
1427  // There should always be a space somewhere if !fail_on_equal,
1428  // because reallocation was handled above.
1429  UT_ASSERT_P(insertp-1 >= pstart || (fail_on_equal && insertp == pstart));
1430  while ((!fail_on_equal || insertp != pstart) && !Clearer::isClear(*(insertp-1)))
1431  {
1432  const size_type other_hash = hasher()(*(insertp-1));
1433  if (fail_on_equal && other_hash == hash && key_equal()(*(insertp-1),value))
1434  {
1435  destp = insertp-1;
1436  return false;
1437  }
1438  if ((other_hash%nbuckets) <= ideal_bucket)
1439  break;
1440  --insertp;
1441  UT_ASSERT_P(insertp-1 >= pstart || (fail_on_equal && insertp == pstart));
1442  }
1443  }
1444 
1445  if (fail_on_equal)
1446  {
1447  // We're always adding one.
1448  size_type new_size = *((const size_type*)pend) + 1;
1449  if (check_realloc && nbuckets < minBuckets(new_size))
1450  {
1451  bumpNumBuckets(new_size);
1452  // Delegate to version that doesn't check for realloc.
1453  return insertHelper<fail_on_equal,false>(myBuckets,myNumBuckets,value,destp);
1454  }
1455  // We're not reallocating in this case.
1456  }
1457 
1458  pointer blockstart = init_searchp;
1459  // NOTE: blockstart shouldn't hit pstart, because myNumBuckets > size()
1460  UT_ASSERT_P(blockstart-1 >= pstart);
1461  while (!Clearer::isClear(*(blockstart-1)))
1462  {
1463  --blockstart;
1464  UT_ASSERT_P(blockstart-1 >= pstart);
1465  }
1466  // Move items earlier by one.
1467  while (blockstart != insertp)
1468  {
1469  *(blockstart-1) = std::move(*blockstart);
1470  ++blockstart;
1471  }
1472  destp = insertp-1;
1473  return true;
1474  }
1475 
1476 protected:
1479 };
1480 
1481 template<
1482  typename Key,
1483  bool MULTI,
1484  std::size_t MAX_LOAD_FACTOR_256,
1485  typename Clearer,
1486  class Hash,
1487  class KeyEqual
1488 >
1489 struct DefaultClearer<ArraySet<Key,MULTI,MAX_LOAD_FACTOR_256,Clearer,Hash,KeyEqual> >
1490 {
1493  static void clear(TheType&v) { v.destroy(); }
1495  static bool isClear(TheType &v) { return v.bucket_count() == 0; }
1497  static void clearConstruct(TheType *p) { new((void *)p) TheType(); }
1498 
1499  static const bool clearNeedsDestruction = false;
1500 };
1501 
1502 } // namespace UT
1503 
1504 template<typename Key,
1505  bool MULTI = false,
1506  int MAX_LOAD_FACTOR_256 = 128,
1507  typename Clearer = UT::DefaultClearer<Key>,
1508  class Hash = std::hash<Key>,
1509  class KeyEqual = std::equal_to<Key> >
1511 
1512 namespace std {
1513  template<typename Key,
1514  bool MULTI,
1515  int MAX_LOAD_FACTOR_256,
1516  typename Clearer,
1517  class Hash,
1518  class KeyEqual>
1519  void swap(
1522  {
1523  a.swap(b);
1524  }
1525 }
1526 
1527 #endif
float load_factor() const
Returns the current portion of buckets that are occupied.
Definition: UT_ArraySet.h:436
const_iterator find(const Key &key) const
Definition: UT_ArraySet.h:716
#define SYSmax(a, b)
Definition: SYS_Math.h:1367
const_pointer searchStart(const Key &key) const
Definition: UT_ArraySet.h:1315
pointer myBuckets
Definition: UT_ArraySet.h:1477
static void clearConstruct(bool *p)
Definition: UT_ArraySet.h:99
ArraySet(const set_type &that)
Definition: UT_ArraySet.h:201
ArraySet(size_type init_bucket_count)
Definition: UT_ArraySet.h:182
std::ptrdiff_t difference_type
Definition: UT_ArraySet.h:549
void clear()
Definition: UT_ArraySet.h:360
std::pair< iterator, bool > insert(const value_type &value)
Definition: UT_ArraySet.h:956
size_type size() const
Returns the number of items in the set.
Definition: UT_ArraySet.h:346
iterator erase(iterator start_iter, iterator end_iter)
Definition: UT_ArraySet.h:1148
UT_API exint UTbumpAllocToPrime(exint current_size)
void setNumBuckets(size_type new_num_buckets)
Definition: UT_ArraySet.h:468
static const bool clearNeedsDestruction
Definition: UT_ArraySet.h:76
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:1519
pointer getCurrent() const
Definition: UT_ArraySet.h:618
const GLdouble * v
Definition: glcorearb.h:836
static void clearConstruct(T *p)
Definition: UT_ArraySet.h:74
static size_type max_bucket_count()
Definition: UT_ArraySet.h:407
std::pair< iterator, bool > insert(value_type &&value)
Definition: UT_ArraySet.h:967
static void clear(S *&v)
Definition: UT_ArraySet.h:35
static void clear(bool &v)
Definition: UT_ArraySet.h:97
set_type & operator=(set_type &&that)
Definition: UT_ArraySet.h:285
GLboolean GLboolean GLboolean GLboolean a
Definition: glcorearb.h:1221
bool SYSisNan(const F f)
Definition: SYS_Math.h:173
bool empty() const
Returns true iff there are no items in the set.
Definition: UT_ArraySet.h:340
iterator end()
Returns a non-const end iterator for the set.
Definition: UT_ArraySet.h:667
iterator_t & operator=(const iterator_t &)=default
png_uint_32 i
Definition: png.h:2877
static bool isClear(bool v)
Definition: UT_ArraySet.h:98
GLsizeiptr size
Definition: glcorearb.h:663
std::ptrdiff_t difference_type
Definition: UT_ArraySet.h:167
bool insertHelper(pointer pstart, size_type nbuckets, const value_type &value, pointer &destp)
Definition: UT_ArraySet.h:1322
static bool isClear(const std::pair< S0, S1 > &v)
Definition: UT_ArraySet.h:112
ArraySet< Key, MULTI, MAX_LOAD_FACTOR_256, Clearer, Hash, KeyEqual > set_type
Definition: UT_ArraySet.h:163
iterator erase(iterator iter)
Definition: UT_ArraySet.h:1033
void insert(INPUT_ITERATOR start_input, INPUT_ITERATOR end_input)
Inserts all of the items in the range [start_input,end_input).
Definition: UT_ArraySet.h:982
long long int64
Definition: SYS_Types.h:107
iterator_t(pointer current, const_pointer end, bool scan=true)
Definition: UT_ArraySet.h:555
std::size_t size_type
Definition: UT_ArraySet.h:166
static size_type minBuckets(size_type size)
Definition: UT_ArraySet.h:1296
reference operator*() const
Definition: UT_ArraySet.h:603
static void clearConstruct(std::pair< S0, S1 > *p)
Definition: UT_ArraySet.h:116
T distance(const UT_Vector4T< T > &v1, const UT_Vector4T< T > &v2)
Definition: UT_Vector4.h:698
const std::enable_if<!VecTraits< T >::IsVec, T >::type & max(const T &a, const T &b)
Definition: Composite.h:133
#define UT_ASSERT_P(ZZ)
Definition: UT_Assert.h:125
void destroy()
Removes all items from the set and frees all the memory.
Definition: UT_ArraySet.h:377
static bool isClear(S *v)
Definition: UT_ArraySet.h:36
ArraySet(std::initializer_list< value_type > init, size_type init_bucket_count=0)
Definition: UT_ArraySet.h:234
GLuint GLuint end
Definition: glcorearb.h:474
iterator begin()
Returns a non-const iterator for the beginning of the set.
Definition: UT_ArraySet.h:652
#define SYS_FORCE_INLINE
Definition: SYS_Inline.h:45
Set iterator class.
Definition: UT_ArraySet.h:545
size_type myNumBuckets
Definition: UT_ArraySet.h:1478
set_type & operator=(const set_type &that)
Definition: UT_ArraySet.h:251
set_type & operator=(std::initializer_list< value_type > init)
Definition: UT_ArraySet.h:278
static key_equal key_eq()
Definition: UT_ArraySet.h:1268
static void clearConstruct(S **p)
Definition: UT_ArraySet.h:37
void bumpNumBuckets(size_type new_num_items)
Definition: UT_ArraySet.h:530
const_iterator cbegin() const
Returns a const iterator for the beginning of the set.
Definition: UT_ArraySet.h:657
GLboolean GLboolean GLboolean b
Definition: glcorearb.h:1221
const_iterator cend() const
Returns a const end iterator for the set.
Definition: UT_ArraySet.h:673
iterator find(const Key &key)
Definition: UT_ArraySet.h:688
std::conditional< constant_type, const value_type, value_type >::type & reference
Definition: UT_ArraySet.h:551
GLint GLsizei count
Definition: glcorearb.h:404
std::forward_iterator_tag iterator_category
Definition: UT_ArraySet.h:548
int64 getMemoryUsage(bool inclusive) const
Definition: UT_ArraySet.h:1275
ArraySet(set_type &&that)
Move constructor, destroying the source.
Definition: UT_ArraySet.h:191
size_type count(const Key &key) const
Definition: UT_ArraySet.h:748
GLsizei const GLfloat * value
Definition: glcorearb.h:823
bool operator!=(const set_type &that) const
Definition: UT_ArraySet.h:318
value_type & reference
Definition: UT_ArraySet.h:170
size_type bucket_size(size_type i) const
Definition: UT_ArraySet.h:415
#define UT_ASSERT_MSG(ZZ, MM)
Definition: UT_Assert.h:129
std::pair< iterator, bool > emplace(Args &&...args)
Definition: UT_ArraySet.h:1019
std::conditional< constant_type, const typename ArraySet::value_type, typename ArraySet::value_type >::type value_type
Definition: UT_ArraySet.h:550
SYS_FORCE_INLINE void forEach(FUNCTOR &&functor) const
Definition: UT_ArraySet.h:1284
void insert(std::initializer_list< value_type > list)
Inserts all of the items from the initializer_list.
Definition: UT_ArraySet.h:1008
const value_type * const_pointer
Definition: UT_ArraySet.h:173
const_pointer getEnd() const
Definition: UT_ArraySet.h:623
std::pair< const_iterator, const_iterator > equal_range(const Key &key) const
Definition: UT_ArraySet.h:818
static bool isClear(T v)
Definition: UT_ArraySet.h:62
iterator_t< constant_type > & operator++()
Definition: UT_ArraySet.h:586
void swap(set_type &that)
Swaps another set with this one.
Definition: UT_ArraySet.h:324
const value_type & const_reference
Definition: UT_ArraySet.h:171
pointer operator->() const
Definition: UT_ArraySet.h:608
GLint GLint GLsizei GLint GLenum GLenum type
Definition: glcorearb.h:107
static void clear(std::pair< S0, S1 > &v)
Definition: UT_ArraySet.h:107
static size_type max_size()
Definition: UT_ArraySet.h:353
void rehash(size_type new_num_buckets)
Definition: UT_ArraySet.h:444
std::pair< iterator, iterator > equal_range(const Key &key)
Definition: UT_ArraySet.h:883
static float max_load_factor()
Definition: UT_ArraySet.h:430
std::conditional< constant_type, typename set_type::const_pointer, typename set_type::pointer >::type pointer
Definition: UT_ArraySet.h:552
static hasher hash_function()
Definition: UT_ArraySet.h:1260
static void clear(T &v)
Definition: UT_ArraySet.h:45
const_iterator begin() const
Returns a const iterator for the beginning of the set.
Definition: UT_ArraySet.h:662
iterator_t< false > iterator
Iterator type for iterating over non-constant elements.
Definition: UT_ArraySet.h:635
bool operator!=(const iterator_t &that) const
Definition: UT_ArraySet.h:577
bool contains(const Key &key) const
Definition: UT_ArraySet.h:787
UT_ASSERT_COMPILETIME(BRAY_EVENT_MAXFLAGS<=32)
size_type bucket_count() const
Returns the current number of buckets.
Definition: UT_ArraySet.h:400
const std::enable_if<!VecTraits< T >::IsVec, T >::type & min(const T &a, const T &b)
Definition: Composite.h:129
KeyEqual key_equal
Definition: UT_ArraySet.h:169
pointer searchStart(const Key &key)
Definition: UT_ArraySet.h:1310
const_iterator(const iterator &non_const_it)
Definition: UT_ArraySet.h:646
bool operator==(const iterator_t &that) const
Definition: UT_ArraySet.h:572
size_type erase(const Key &key)
Definition: UT_ArraySet.h:1240
ArraySet(INPUT_ITERATOR start_input, INPUT_ITERATOR end_input, size_type init_bucket_count=0)
Inserts all of the items in the range [start_input,end_input).
Definition: UT_ArraySet.h:210
Clearer clearer_type
Definition: UT_ArraySet.h:174
const_iterator end() const
Returns a const end iterator for the set.
Definition: UT_ArraySet.h:679
bool operator==(const set_type &that) const
Definition: UT_ArraySet.h:295
#define UT_ASSERT_MSG_P(ZZ, MM)
Definition: UT_Assert.h:128
void reserve(size_type num_items)
Definition: UT_ArraySet.h:458
value_type * pointer
Definition: UT_ArraySet.h:172