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