WPILibC++  2019.3.1
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Modules Pages
DenseMap.h
1 //===- llvm/ADT/DenseMap.h - Dense probed hash table ------------*- C++ -*-===//
2 //
3 // The LLVM Compiler Infrastructure
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 //
10 // This file defines the DenseMap class.
11 //
12 //===----------------------------------------------------------------------===//
13 
14 #ifndef WPIUTIL_WPI_DENSEMAP_H
15 #define WPIUTIL_WPI_DENSEMAP_H
16 
17 #include "wpi/DenseMapInfo.h"
18 #include "wpi/EpochTracker.h"
19 #include "wpi/AlignOf.h"
20 #include "wpi/Compiler.h"
21 #include "wpi/MathExtras.h"
22 #include "wpi/PointerLikeTypeTraits.h"
23 #include "wpi/type_traits.h"
24 #include <algorithm>
25 #include <cassert>
26 #include <cstddef>
27 #include <cstring>
28 #include <iterator>
29 #include <new>
30 #include <type_traits>
31 #include <utility>
32 
33 namespace wpi {
34 
35 namespace detail {
36 
37 // We extend a pair to allow users to override the bucket type with their own
38 // implementation without requiring two members.
39 template <typename KeyT, typename ValueT>
40 struct DenseMapPair : public std::pair<KeyT, ValueT> {
41  KeyT &getFirst() { return std::pair<KeyT, ValueT>::first; }
42  const KeyT &getFirst() const { return std::pair<KeyT, ValueT>::first; }
43  ValueT &getSecond() { return std::pair<KeyT, ValueT>::second; }
44  const ValueT &getSecond() const { return std::pair<KeyT, ValueT>::second; }
45 };
46 
47 } // end namespace detail
48 
49 template <
50  typename KeyT, typename ValueT, typename KeyInfoT = DenseMapInfo<KeyT>,
51  typename Bucket = detail::DenseMapPair<KeyT, ValueT>, bool IsConst = false>
53 
54 template <typename DerivedT, typename KeyT, typename ValueT, typename KeyInfoT,
55  typename BucketT>
56 class DenseMapBase : public DebugEpochBase {
57  template <typename T>
58  using const_arg_type_t = typename const_pointer_or_const_ref<T>::type;
59 
60 public:
61  using size_type = unsigned;
62  using key_type = KeyT;
63  using mapped_type = ValueT;
64  using value_type = BucketT;
65 
67  using const_iterator =
69 
70  inline iterator begin() {
71  // When the map is empty, avoid the overhead of advancing/retreating past
72  // empty buckets.
73  if (empty())
74  return end();
75  return makeIterator(getBuckets(), getBucketsEnd(), *this);
76  }
77  inline iterator end() {
78  return makeIterator(getBucketsEnd(), getBucketsEnd(), *this, true);
79  }
80  inline const_iterator begin() const {
81  if (empty())
82  return end();
83  return makeConstIterator(getBuckets(), getBucketsEnd(), *this);
84  }
85  inline const_iterator end() const {
86  return makeConstIterator(getBucketsEnd(), getBucketsEnd(), *this, true);
87  }
88 
89  LLVM_NODISCARD bool empty() const {
90  return getNumEntries() == 0;
91  }
92  unsigned size() const { return getNumEntries(); }
93 
96  void reserve(size_type NumEntries) {
97  auto NumBuckets = getMinBucketToReserveForEntries(NumEntries);
99  if (NumBuckets > getNumBuckets())
100  grow(NumBuckets);
101  }
102 
103  void clear() {
104  incrementEpoch();
105  if (getNumEntries() == 0 && getNumTombstones() == 0) return;
106 
107  // If the capacity of the array is huge, and the # elements used is small,
108  // shrink the array.
109  if (getNumEntries() * 4 < getNumBuckets() && getNumBuckets() > 64) {
110  shrink_and_clear();
111  return;
112  }
113 
114  const KeyT EmptyKey = getEmptyKey(), TombstoneKey = getTombstoneKey();
115  if (isPodLike<KeyT>::value && isPodLike<ValueT>::value) {
116  // Use a simpler loop when these are trivial types.
117  for (BucketT *P = getBuckets(), *E = getBucketsEnd(); P != E; ++P)
118  P->getFirst() = EmptyKey;
119  } else {
120  unsigned NumEntries = getNumEntries();
121  for (BucketT *P = getBuckets(), *E = getBucketsEnd(); P != E; ++P) {
122  if (!KeyInfoT::isEqual(P->getFirst(), EmptyKey)) {
123  if (!KeyInfoT::isEqual(P->getFirst(), TombstoneKey)) {
124  P->getSecond().~ValueT();
125  --NumEntries;
126  }
127  P->getFirst() = EmptyKey;
128  }
129  }
130  assert(NumEntries == 0 && "Node count imbalance!");
131  }
132  setNumEntries(0);
133  setNumTombstones(0);
134  }
135 
137  size_type count(const_arg_type_t<KeyT> Val) const {
138  const BucketT *TheBucket;
139  return LookupBucketFor(Val, TheBucket) ? 1 : 0;
140  }
141 
142  iterator find(const_arg_type_t<KeyT> Val) {
143  BucketT *TheBucket;
144  if (LookupBucketFor(Val, TheBucket))
145  return makeIterator(TheBucket, getBucketsEnd(), *this, true);
146  return end();
147  }
148  const_iterator find(const_arg_type_t<KeyT> Val) const {
149  const BucketT *TheBucket;
150  if (LookupBucketFor(Val, TheBucket))
151  return makeConstIterator(TheBucket, getBucketsEnd(), *this, true);
152  return end();
153  }
154 
160  template<class LookupKeyT>
161  iterator find_as(const LookupKeyT &Val) {
162  BucketT *TheBucket;
163  if (LookupBucketFor(Val, TheBucket))
164  return makeIterator(TheBucket, getBucketsEnd(), *this, true);
165  return end();
166  }
167  template<class LookupKeyT>
168  const_iterator find_as(const LookupKeyT &Val) const {
169  const BucketT *TheBucket;
170  if (LookupBucketFor(Val, TheBucket))
171  return makeConstIterator(TheBucket, getBucketsEnd(), *this, true);
172  return end();
173  }
174 
177  ValueT lookup(const_arg_type_t<KeyT> Val) const {
178  const BucketT *TheBucket;
179  if (LookupBucketFor(Val, TheBucket))
180  return TheBucket->getSecond();
181  return ValueT();
182  }
183 
184  // Inserts key,value pair into the map if the key isn't already in the map.
185  // If the key is already in the map, it returns false and doesn't update the
186  // value.
187  std::pair<iterator, bool> insert(const std::pair<KeyT, ValueT> &KV) {
188  return try_emplace(KV.first, KV.second);
189  }
190 
191  // Inserts key,value pair into the map if the key isn't already in the map.
192  // If the key is already in the map, it returns false and doesn't update the
193  // value.
194  std::pair<iterator, bool> insert(std::pair<KeyT, ValueT> &&KV) {
195  return try_emplace(std::move(KV.first), std::move(KV.second));
196  }
197 
198  // Inserts key,value pair into the map if the key isn't already in the map.
199  // The value is constructed in-place if the key is not in the map, otherwise
200  // it is not moved.
201  template <typename... Ts>
202  std::pair<iterator, bool> try_emplace(KeyT &&Key, Ts &&... Args) {
203  BucketT *TheBucket;
204  if (LookupBucketFor(Key, TheBucket))
205  return std::make_pair(
206  makeIterator(TheBucket, getBucketsEnd(), *this, true),
207  false); // Already in map.
208 
209  // Otherwise, insert the new element.
210  TheBucket =
211  InsertIntoBucket(TheBucket, std::move(Key), std::forward<Ts>(Args)...);
212  return std::make_pair(
213  makeIterator(TheBucket, getBucketsEnd(), *this, true),
214  true);
215  }
216 
217  // Inserts key,value pair into the map if the key isn't already in the map.
218  // The value is constructed in-place if the key is not in the map, otherwise
219  // it is not moved.
220  template <typename... Ts>
221  std::pair<iterator, bool> try_emplace(const KeyT &Key, Ts &&... Args) {
222  BucketT *TheBucket;
223  if (LookupBucketFor(Key, TheBucket))
224  return std::make_pair(
225  makeIterator(TheBucket, getBucketsEnd(), *this, true),
226  false); // Already in map.
227 
228  // Otherwise, insert the new element.
229  TheBucket = InsertIntoBucket(TheBucket, Key, std::forward<Ts>(Args)...);
230  return std::make_pair(
231  makeIterator(TheBucket, getBucketsEnd(), *this, true),
232  true);
233  }
234 
240  template <typename LookupKeyT>
241  std::pair<iterator, bool> insert_as(std::pair<KeyT, ValueT> &&KV,
242  const LookupKeyT &Val) {
243  BucketT *TheBucket;
244  if (LookupBucketFor(Val, TheBucket))
245  return std::make_pair(
246  makeIterator(TheBucket, getBucketsEnd(), *this, true),
247  false); // Already in map.
248 
249  // Otherwise, insert the new element.
250  TheBucket = InsertIntoBucketWithLookup(TheBucket, std::move(KV.first),
251  std::move(KV.second), Val);
252  return std::make_pair(
253  makeIterator(TheBucket, getBucketsEnd(), *this, true),
254  true);
255  }
256 
258  template<typename InputIt>
259  void insert(InputIt I, InputIt E) {
260  for (; I != E; ++I)
261  insert(*I);
262  }
263 
264  bool erase(const KeyT &Val) {
265  BucketT *TheBucket;
266  if (!LookupBucketFor(Val, TheBucket))
267  return false; // not in map.
268 
269  TheBucket->getSecond().~ValueT();
270  TheBucket->getFirst() = getTombstoneKey();
271  decrementNumEntries();
272  incrementNumTombstones();
273  return true;
274  }
275  void erase(iterator I) {
276  BucketT *TheBucket = &*I;
277  TheBucket->getSecond().~ValueT();
278  TheBucket->getFirst() = getTombstoneKey();
279  decrementNumEntries();
280  incrementNumTombstones();
281  }
282 
283  value_type& FindAndConstruct(const KeyT &Key) {
284  BucketT *TheBucket;
285  if (LookupBucketFor(Key, TheBucket))
286  return *TheBucket;
287 
288  return *InsertIntoBucket(TheBucket, Key);
289  }
290 
291  ValueT &operator[](const KeyT &Key) {
292  return FindAndConstruct(Key).second;
293  }
294 
295  value_type& FindAndConstruct(KeyT &&Key) {
296  BucketT *TheBucket;
297  if (LookupBucketFor(Key, TheBucket))
298  return *TheBucket;
299 
300  return *InsertIntoBucket(TheBucket, std::move(Key));
301  }
302 
303  ValueT &operator[](KeyT &&Key) {
304  return FindAndConstruct(std::move(Key)).second;
305  }
306 
310  bool isPointerIntoBucketsArray(const void *Ptr) const {
311  return Ptr >= getBuckets() && Ptr < getBucketsEnd();
312  }
313 
317  const void *getPointerIntoBucketsArray() const { return getBuckets(); }
318 
319 protected:
320  DenseMapBase() = default;
321 
322  void destroyAll() {
323  if (getNumBuckets() == 0) // Nothing to do.
324  return;
325 
326  const KeyT EmptyKey = getEmptyKey(), TombstoneKey = getTombstoneKey();
327  for (BucketT *P = getBuckets(), *E = getBucketsEnd(); P != E; ++P) {
328  if (!KeyInfoT::isEqual(P->getFirst(), EmptyKey) &&
329  !KeyInfoT::isEqual(P->getFirst(), TombstoneKey))
330  P->getSecond().~ValueT();
331  P->getFirst().~KeyT();
332  }
333  }
334 
335  void initEmpty() {
336  setNumEntries(0);
337  setNumTombstones(0);
338 
339  assert((getNumBuckets() & (getNumBuckets()-1)) == 0 &&
340  "# initial buckets must be a power of two!");
341  const KeyT EmptyKey = getEmptyKey();
342  for (BucketT *B = getBuckets(), *E = getBucketsEnd(); B != E; ++B)
343  ::new (&B->getFirst()) KeyT(EmptyKey);
344  }
345 
348  unsigned getMinBucketToReserveForEntries(unsigned NumEntries) {
349  // Ensure that "NumEntries * 4 < NumBuckets * 3"
350  if (NumEntries == 0)
351  return 0;
352  // +1 is required because of the strict equality.
353  // For example if NumEntries is 48, we need to return 401.
354  return NextPowerOf2(NumEntries * 4 / 3 + 1);
355  }
356 
357  void moveFromOldBuckets(BucketT *OldBucketsBegin, BucketT *OldBucketsEnd) {
358  initEmpty();
359 
360  // Insert all the old elements.
361  const KeyT EmptyKey = getEmptyKey();
362  const KeyT TombstoneKey = getTombstoneKey();
363  for (BucketT *B = OldBucketsBegin, *E = OldBucketsEnd; B != E; ++B) {
364  if (!KeyInfoT::isEqual(B->getFirst(), EmptyKey) &&
365  !KeyInfoT::isEqual(B->getFirst(), TombstoneKey)) {
366  // Insert the key/value into the new table.
367  BucketT *DestBucket;
368  bool FoundVal = LookupBucketFor(B->getFirst(), DestBucket);
369  (void)FoundVal; // silence warning.
370  assert(!FoundVal && "Key already in new map?");
371  DestBucket->getFirst() = std::move(B->getFirst());
372  ::new (&DestBucket->getSecond()) ValueT(std::move(B->getSecond()));
373  incrementNumEntries();
374 
375  // Free the value.
376  B->getSecond().~ValueT();
377  }
378  B->getFirst().~KeyT();
379  }
380  }
381 
382  template <typename OtherBaseT>
383  void copyFrom(
384  const DenseMapBase<OtherBaseT, KeyT, ValueT, KeyInfoT, BucketT> &other) {
385  assert(&other != this);
386  assert(getNumBuckets() == other.getNumBuckets());
387 
388  setNumEntries(other.getNumEntries());
389  setNumTombstones(other.getNumTombstones());
390 
391  if (isPodLike<KeyT>::value && isPodLike<ValueT>::value)
392  memcpy(getBuckets(), other.getBuckets(),
393  getNumBuckets() * sizeof(BucketT));
394  else
395  for (size_t i = 0; i < getNumBuckets(); ++i) {
396  ::new (&getBuckets()[i].getFirst())
397  KeyT(other.getBuckets()[i].getFirst());
398  if (!KeyInfoT::isEqual(getBuckets()[i].getFirst(), getEmptyKey()) &&
399  !KeyInfoT::isEqual(getBuckets()[i].getFirst(), getTombstoneKey()))
400  ::new (&getBuckets()[i].getSecond())
401  ValueT(other.getBuckets()[i].getSecond());
402  }
403  }
404 
405  static unsigned getHashValue(const KeyT &Val) {
406  return KeyInfoT::getHashValue(Val);
407  }
408 
409  template<typename LookupKeyT>
410  static unsigned getHashValue(const LookupKeyT &Val) {
411  return KeyInfoT::getHashValue(Val);
412  }
413 
414  static const KeyT getEmptyKey() {
415  static_assert(std::is_base_of<DenseMapBase, DerivedT>::value,
416  "Must pass the derived type to this template!");
417  return KeyInfoT::getEmptyKey();
418  }
419 
420  static const KeyT getTombstoneKey() {
421  return KeyInfoT::getTombstoneKey();
422  }
423 
424 private:
425  iterator makeIterator(BucketT *P, BucketT *E,
426  DebugEpochBase &Epoch,
427  bool NoAdvance=false) {
428  return iterator(P, E, Epoch, NoAdvance);
429  }
430 
431  const_iterator makeConstIterator(const BucketT *P, const BucketT *E,
432  const DebugEpochBase &Epoch,
433  const bool NoAdvance=false) const {
434  return const_iterator(P, E, Epoch, NoAdvance);
435  }
436 
437  unsigned getNumEntries() const {
438  return static_cast<const DerivedT *>(this)->getNumEntries();
439  }
440 
441  void setNumEntries(unsigned Num) {
442  static_cast<DerivedT *>(this)->setNumEntries(Num);
443  }
444 
445  void incrementNumEntries() {
446  setNumEntries(getNumEntries() + 1);
447  }
448 
449  void decrementNumEntries() {
450  setNumEntries(getNumEntries() - 1);
451  }
452 
453  unsigned getNumTombstones() const {
454  return static_cast<const DerivedT *>(this)->getNumTombstones();
455  }
456 
457  void setNumTombstones(unsigned Num) {
458  static_cast<DerivedT *>(this)->setNumTombstones(Num);
459  }
460 
461  void incrementNumTombstones() {
462  setNumTombstones(getNumTombstones() + 1);
463  }
464 
465  void decrementNumTombstones() {
466  setNumTombstones(getNumTombstones() - 1);
467  }
468 
469  const BucketT *getBuckets() const {
470  return static_cast<const DerivedT *>(this)->getBuckets();
471  }
472 
473  BucketT *getBuckets() {
474  return static_cast<DerivedT *>(this)->getBuckets();
475  }
476 
477  unsigned getNumBuckets() const {
478  return static_cast<const DerivedT *>(this)->getNumBuckets();
479  }
480 
481  BucketT *getBucketsEnd() {
482  return getBuckets() + getNumBuckets();
483  }
484 
485  const BucketT *getBucketsEnd() const {
486  return getBuckets() + getNumBuckets();
487  }
488 
489  void grow(unsigned AtLeast) {
490  static_cast<DerivedT *>(this)->grow(AtLeast);
491  }
492 
493  void shrink_and_clear() {
494  static_cast<DerivedT *>(this)->shrink_and_clear();
495  }
496 
497  template <typename KeyArg, typename... ValueArgs>
498  BucketT *InsertIntoBucket(BucketT *TheBucket, KeyArg &&Key,
499  ValueArgs &&... Values) {
500  TheBucket = InsertIntoBucketImpl(Key, Key, TheBucket);
501 
502  TheBucket->getFirst() = std::forward<KeyArg>(Key);
503  ::new (&TheBucket->getSecond()) ValueT(std::forward<ValueArgs>(Values)...);
504  return TheBucket;
505  }
506 
507  template <typename LookupKeyT>
508  BucketT *InsertIntoBucketWithLookup(BucketT *TheBucket, KeyT &&Key,
509  ValueT &&Value, LookupKeyT &Lookup) {
510  TheBucket = InsertIntoBucketImpl(Key, Lookup, TheBucket);
511 
512  TheBucket->getFirst() = std::move(Key);
513  ::new (&TheBucket->getSecond()) ValueT(std::move(Value));
514  return TheBucket;
515  }
516 
517  template <typename LookupKeyT>
518  BucketT *InsertIntoBucketImpl(const KeyT &Key, const LookupKeyT &Lookup,
519  BucketT *TheBucket) {
520  incrementEpoch();
521 
522  // If the load of the hash table is more than 3/4, or if fewer than 1/8 of
523  // the buckets are empty (meaning that many are filled with tombstones),
524  // grow the table.
525  //
526  // The later case is tricky. For example, if we had one empty bucket with
527  // tons of tombstones, failing lookups (e.g. for insertion) would have to
528  // probe almost the entire table until it found the empty bucket. If the
529  // table completely filled with tombstones, no lookup would ever succeed,
530  // causing infinite loops in lookup.
531  unsigned NewNumEntries = getNumEntries() + 1;
532  unsigned NumBuckets = getNumBuckets();
533  if (LLVM_UNLIKELY(NewNumEntries * 4 >= NumBuckets * 3)) {
534  this->grow(NumBuckets * 2);
535  LookupBucketFor(Lookup, TheBucket);
536  NumBuckets = getNumBuckets();
537  } else if (LLVM_UNLIKELY(NumBuckets-(NewNumEntries+getNumTombstones()) <=
538  NumBuckets/8)) {
539  this->grow(NumBuckets);
540  LookupBucketFor(Lookup, TheBucket);
541  }
542  assert(TheBucket);
543 
544  // Only update the state after we've grown our bucket space appropriately
545  // so that when growing buckets we have self-consistent entry count.
546  incrementNumEntries();
547 
548  // If we are writing over a tombstone, remember this.
549  const KeyT EmptyKey = getEmptyKey();
550  if (!KeyInfoT::isEqual(TheBucket->getFirst(), EmptyKey))
551  decrementNumTombstones();
552 
553  return TheBucket;
554  }
555 
560  template<typename LookupKeyT>
561  bool LookupBucketFor(const LookupKeyT &Val,
562  const BucketT *&FoundBucket) const {
563  const BucketT *BucketsPtr = getBuckets();
564  const unsigned NumBuckets = getNumBuckets();
565 
566  if (NumBuckets == 0) {
567  FoundBucket = nullptr;
568  return false;
569  }
570 
571  // FoundTombstone - Keep track of whether we find a tombstone while probing.
572  const BucketT *FoundTombstone = nullptr;
573  const KeyT EmptyKey = getEmptyKey();
574  const KeyT TombstoneKey = getTombstoneKey();
575  assert(!KeyInfoT::isEqual(Val, EmptyKey) &&
576  !KeyInfoT::isEqual(Val, TombstoneKey) &&
577  "Empty/Tombstone value shouldn't be inserted into map!");
578 
579  unsigned BucketNo = getHashValue(Val) & (NumBuckets-1);
580  unsigned ProbeAmt = 1;
581  while (true) {
582  const BucketT *ThisBucket = BucketsPtr + BucketNo;
583  // Found Val's bucket? If so, return it.
584  if (LLVM_LIKELY(KeyInfoT::isEqual(Val, ThisBucket->getFirst()))) {
585  FoundBucket = ThisBucket;
586  return true;
587  }
588 
589  // If we found an empty bucket, the key doesn't exist in the set.
590  // Insert it and return the default value.
591  if (LLVM_LIKELY(KeyInfoT::isEqual(ThisBucket->getFirst(), EmptyKey))) {
592  // If we've already seen a tombstone while probing, fill it in instead
593  // of the empty bucket we eventually probed to.
594  FoundBucket = FoundTombstone ? FoundTombstone : ThisBucket;
595  return false;
596  }
597 
598  // If this is a tombstone, remember it. If Val ends up not in the map, we
599  // prefer to return it than something that would require more probing.
600  if (KeyInfoT::isEqual(ThisBucket->getFirst(), TombstoneKey) &&
601  !FoundTombstone)
602  FoundTombstone = ThisBucket; // Remember the first tombstone found.
603 
604  // Otherwise, it's a hash collision or a tombstone, continue quadratic
605  // probing.
606  BucketNo += ProbeAmt++;
607  BucketNo &= (NumBuckets-1);
608  }
609  }
610 
611  template <typename LookupKeyT>
612  bool LookupBucketFor(const LookupKeyT &Val, BucketT *&FoundBucket) {
613  const BucketT *ConstFoundBucket;
614  bool Result = const_cast<const DenseMapBase *>(this)
615  ->LookupBucketFor(Val, ConstFoundBucket);
616  FoundBucket = const_cast<BucketT *>(ConstFoundBucket);
617  return Result;
618  }
619 
620 public:
625  size_t getMemorySize() const {
626  return getNumBuckets() * sizeof(BucketT);
627  }
628 };
629 
630 template <typename KeyT, typename ValueT,
631  typename KeyInfoT = DenseMapInfo<KeyT>,
632  typename BucketT = detail::DenseMapPair<KeyT, ValueT>>
633 class DenseMap : public DenseMapBase<DenseMap<KeyT, ValueT, KeyInfoT, BucketT>,
634  KeyT, ValueT, KeyInfoT, BucketT> {
635  friend class DenseMapBase<DenseMap, KeyT, ValueT, KeyInfoT, BucketT>;
636 
637  // Lift some types from the dependent base class into this class for
638  // simplicity of referring to them.
640 
641  BucketT *Buckets;
642  unsigned NumEntries;
643  unsigned NumTombstones;
644  unsigned NumBuckets;
645 
646 public:
649  explicit DenseMap(unsigned InitialReserve = 0) { init(InitialReserve); }
650 
651  DenseMap(const DenseMap &other) : BaseT() {
652  init(0);
653  copyFrom(other);
654  }
655 
656  DenseMap(DenseMap &&other) : BaseT() {
657  init(0);
658  swap(other);
659  }
660 
661  template<typename InputIt>
662  DenseMap(const InputIt &I, const InputIt &E) {
663  init(std::distance(I, E));
664  this->insert(I, E);
665  }
666 
667  ~DenseMap() {
668  this->destroyAll();
669  operator delete(Buckets);
670  }
671 
672  void swap(DenseMap& RHS) {
673  this->incrementEpoch();
674  RHS.incrementEpoch();
675  std::swap(Buckets, RHS.Buckets);
676  std::swap(NumEntries, RHS.NumEntries);
677  std::swap(NumTombstones, RHS.NumTombstones);
678  std::swap(NumBuckets, RHS.NumBuckets);
679  }
680 
681  DenseMap& operator=(const DenseMap& other) {
682  if (&other != this)
683  copyFrom(other);
684  return *this;
685  }
686 
687  DenseMap& operator=(DenseMap &&other) {
688  this->destroyAll();
689  operator delete(Buckets);
690  init(0);
691  swap(other);
692  return *this;
693  }
694 
695  void copyFrom(const DenseMap& other) {
696  this->destroyAll();
697  operator delete(Buckets);
698  if (allocateBuckets(other.NumBuckets)) {
699  this->BaseT::copyFrom(other);
700  } else {
701  NumEntries = 0;
702  NumTombstones = 0;
703  }
704  }
705 
706  void init(unsigned InitNumEntries) {
707  auto InitBuckets = BaseT::getMinBucketToReserveForEntries(InitNumEntries);
708  if (allocateBuckets(InitBuckets)) {
709  this->BaseT::initEmpty();
710  } else {
711  NumEntries = 0;
712  NumTombstones = 0;
713  }
714  }
715 
716  void grow(unsigned AtLeast) {
717  unsigned OldNumBuckets = NumBuckets;
718  BucketT *OldBuckets = Buckets;
719 
720  allocateBuckets(std::max<unsigned>(64, static_cast<unsigned>(NextPowerOf2(AtLeast-1))));
721  assert(Buckets);
722  if (!OldBuckets) {
723  this->BaseT::initEmpty();
724  return;
725  }
726 
727  this->moveFromOldBuckets(OldBuckets, OldBuckets+OldNumBuckets);
728 
729  // Free the old table.
730  operator delete(OldBuckets);
731  }
732 
733  void shrink_and_clear() {
734  unsigned OldNumEntries = NumEntries;
735  this->destroyAll();
736 
737  // Reduce the number of buckets.
738  unsigned NewNumBuckets = 0;
739  if (OldNumEntries)
740  NewNumBuckets = std::max(64, 1 << (Log2_32_Ceil(OldNumEntries) + 1));
741  if (NewNumBuckets == NumBuckets) {
742  this->BaseT::initEmpty();
743  return;
744  }
745 
746  operator delete(Buckets);
747  init(NewNumBuckets);
748  }
749 
750 private:
751  unsigned getNumEntries() const {
752  return NumEntries;
753  }
754 
755  void setNumEntries(unsigned Num) {
756  NumEntries = Num;
757  }
758 
759  unsigned getNumTombstones() const {
760  return NumTombstones;
761  }
762 
763  void setNumTombstones(unsigned Num) {
764  NumTombstones = Num;
765  }
766 
767  BucketT *getBuckets() const {
768  return Buckets;
769  }
770 
771  unsigned getNumBuckets() const {
772  return NumBuckets;
773  }
774 
775  bool allocateBuckets(unsigned Num) {
776  NumBuckets = Num;
777  if (NumBuckets == 0) {
778  Buckets = nullptr;
779  return false;
780  }
781 
782  Buckets = static_cast<BucketT*>(operator new(sizeof(BucketT) * NumBuckets));
783  return true;
784  }
785 };
786 
787 template <typename KeyT, typename ValueT, unsigned InlineBuckets = 4,
788  typename KeyInfoT = DenseMapInfo<KeyT>,
789  typename BucketT = detail::DenseMapPair<KeyT, ValueT>>
791  : public DenseMapBase<
792  SmallDenseMap<KeyT, ValueT, InlineBuckets, KeyInfoT, BucketT>, KeyT,
793  ValueT, KeyInfoT, BucketT> {
794  friend class DenseMapBase<SmallDenseMap, KeyT, ValueT, KeyInfoT, BucketT>;
795 
796  // Lift some types from the dependent base class into this class for
797  // simplicity of referring to them.
799 
800  static_assert(isPowerOf2_64(InlineBuckets),
801  "InlineBuckets must be a power of 2.");
802 
803  unsigned Small : 1;
804  unsigned NumEntries : 31;
805  unsigned NumTombstones;
806 
807  struct LargeRep {
808  BucketT *Buckets;
809  unsigned NumBuckets;
810  };
811 
815 
816 public:
817  explicit SmallDenseMap(unsigned NumInitBuckets = 0) {
818  init(NumInitBuckets);
819  }
820 
821  SmallDenseMap(const SmallDenseMap &other) : BaseT() {
822  init(0);
823  copyFrom(other);
824  }
825 
826  SmallDenseMap(SmallDenseMap &&other) : BaseT() {
827  init(0);
828  swap(other);
829  }
830 
831  template<typename InputIt>
832  SmallDenseMap(const InputIt &I, const InputIt &E) {
833  init(NextPowerOf2(std::distance(I, E)));
834  this->insert(I, E);
835  }
836 
837  ~SmallDenseMap() {
838  this->destroyAll();
839  deallocateBuckets();
840  }
841 
842  void swap(SmallDenseMap& RHS) {
843  unsigned TmpNumEntries = RHS.NumEntries;
844  RHS.NumEntries = NumEntries;
845  NumEntries = TmpNumEntries;
846  std::swap(NumTombstones, RHS.NumTombstones);
847 
848  const KeyT EmptyKey = this->getEmptyKey();
849  const KeyT TombstoneKey = this->getTombstoneKey();
850  if (Small && RHS.Small) {
851  // If we're swapping inline bucket arrays, we have to cope with some of
852  // the tricky bits of DenseMap's storage system: the buckets are not
853  // fully initialized. Thus we swap every key, but we may have
854  // a one-directional move of the value.
855  for (unsigned i = 0, e = InlineBuckets; i != e; ++i) {
856  BucketT *LHSB = &getInlineBuckets()[i],
857  *RHSB = &RHS.getInlineBuckets()[i];
858  bool hasLHSValue = (!KeyInfoT::isEqual(LHSB->getFirst(), EmptyKey) &&
859  !KeyInfoT::isEqual(LHSB->getFirst(), TombstoneKey));
860  bool hasRHSValue = (!KeyInfoT::isEqual(RHSB->getFirst(), EmptyKey) &&
861  !KeyInfoT::isEqual(RHSB->getFirst(), TombstoneKey));
862  if (hasLHSValue && hasRHSValue) {
863  // Swap together if we can...
864  std::swap(*LHSB, *RHSB);
865  continue;
866  }
867  // Swap separately and handle any assymetry.
868  std::swap(LHSB->getFirst(), RHSB->getFirst());
869  if (hasLHSValue) {
870  ::new (&RHSB->getSecond()) ValueT(std::move(LHSB->getSecond()));
871  LHSB->getSecond().~ValueT();
872  } else if (hasRHSValue) {
873  ::new (&LHSB->getSecond()) ValueT(std::move(RHSB->getSecond()));
874  RHSB->getSecond().~ValueT();
875  }
876  }
877  return;
878  }
879  if (!Small && !RHS.Small) {
880  std::swap(getLargeRep()->Buckets, RHS.getLargeRep()->Buckets);
881  std::swap(getLargeRep()->NumBuckets, RHS.getLargeRep()->NumBuckets);
882  return;
883  }
884 
885  SmallDenseMap &SmallSide = Small ? *this : RHS;
886  SmallDenseMap &LargeSide = Small ? RHS : *this;
887 
888  // First stash the large side's rep and move the small side across.
889  LargeRep TmpRep = std::move(*LargeSide.getLargeRep());
890  LargeSide.getLargeRep()->~LargeRep();
891  LargeSide.Small = true;
892  // This is similar to the standard move-from-old-buckets, but the bucket
893  // count hasn't actually rotated in this case. So we have to carefully
894  // move construct the keys and values into their new locations, but there
895  // is no need to re-hash things.
896  for (unsigned i = 0, e = InlineBuckets; i != e; ++i) {
897  BucketT *NewB = &LargeSide.getInlineBuckets()[i],
898  *OldB = &SmallSide.getInlineBuckets()[i];
899  ::new (&NewB->getFirst()) KeyT(std::move(OldB->getFirst()));
900  OldB->getFirst().~KeyT();
901  if (!KeyInfoT::isEqual(NewB->getFirst(), EmptyKey) &&
902  !KeyInfoT::isEqual(NewB->getFirst(), TombstoneKey)) {
903  ::new (&NewB->getSecond()) ValueT(std::move(OldB->getSecond()));
904  OldB->getSecond().~ValueT();
905  }
906  }
907 
908  // The hard part of moving the small buckets across is done, just move
909  // the TmpRep into its new home.
910  SmallSide.Small = false;
911  new (SmallSide.getLargeRep()) LargeRep(std::move(TmpRep));
912  }
913 
914  SmallDenseMap& operator=(const SmallDenseMap& other) {
915  if (&other != this)
916  copyFrom(other);
917  return *this;
918  }
919 
920  SmallDenseMap& operator=(SmallDenseMap &&other) {
921  this->destroyAll();
922  deallocateBuckets();
923  init(0);
924  swap(other);
925  return *this;
926  }
927 
928  void copyFrom(const SmallDenseMap& other) {
929  this->destroyAll();
930  deallocateBuckets();
931  Small = true;
932  if (other.getNumBuckets() > InlineBuckets) {
933  Small = false;
934  new (getLargeRep()) LargeRep(allocateBuckets(other.getNumBuckets()));
935  }
936  this->BaseT::copyFrom(other);
937  }
938 
939  void init(unsigned InitBuckets) {
940  Small = true;
941  if (InitBuckets > InlineBuckets) {
942  Small = false;
943  new (getLargeRep()) LargeRep(allocateBuckets(InitBuckets));
944  }
945  this->BaseT::initEmpty();
946  }
947 
948  void grow(unsigned AtLeast) {
949  if (AtLeast >= InlineBuckets)
950  AtLeast = std::max<unsigned>(64, NextPowerOf2(AtLeast-1));
951 
952  if (Small) {
953  if (AtLeast < InlineBuckets)
954  return; // Nothing to do.
955 
956  // First move the inline buckets into a temporary storage.
958  BucketT *TmpBegin = reinterpret_cast<BucketT *>(TmpStorage.buffer);
959  BucketT *TmpEnd = TmpBegin;
960 
961  // Loop over the buckets, moving non-empty, non-tombstones into the
962  // temporary storage. Have the loop move the TmpEnd forward as it goes.
963  const KeyT EmptyKey = this->getEmptyKey();
964  const KeyT TombstoneKey = this->getTombstoneKey();
965  for (BucketT *P = getBuckets(), *E = P + InlineBuckets; P != E; ++P) {
966  if (!KeyInfoT::isEqual(P->getFirst(), EmptyKey) &&
967  !KeyInfoT::isEqual(P->getFirst(), TombstoneKey)) {
968  assert(size_t(TmpEnd - TmpBegin) < InlineBuckets &&
969  "Too many inline buckets!");
970  ::new (&TmpEnd->getFirst()) KeyT(std::move(P->getFirst()));
971  ::new (&TmpEnd->getSecond()) ValueT(std::move(P->getSecond()));
972  ++TmpEnd;
973  P->getSecond().~ValueT();
974  }
975  P->getFirst().~KeyT();
976  }
977 
978  // Now make this map use the large rep, and move all the entries back
979  // into it.
980  Small = false;
981  new (getLargeRep()) LargeRep(allocateBuckets(AtLeast));
982  this->moveFromOldBuckets(TmpBegin, TmpEnd);
983  return;
984  }
985 
986  LargeRep OldRep = std::move(*getLargeRep());
987  getLargeRep()->~LargeRep();
988  if (AtLeast <= InlineBuckets) {
989  Small = true;
990  } else {
991  new (getLargeRep()) LargeRep(allocateBuckets(AtLeast));
992  }
993 
994  this->moveFromOldBuckets(OldRep.Buckets, OldRep.Buckets+OldRep.NumBuckets);
995 
996  // Free the old table.
997  operator delete(OldRep.Buckets);
998  }
999 
1000  void shrink_and_clear() {
1001  unsigned OldSize = this->size();
1002  this->destroyAll();
1003 
1004  // Reduce the number of buckets.
1005  unsigned NewNumBuckets = 0;
1006  if (OldSize) {
1007  NewNumBuckets = 1 << (Log2_32_Ceil(OldSize) + 1);
1008  if (NewNumBuckets > InlineBuckets && NewNumBuckets < 64u)
1009  NewNumBuckets = 64;
1010  }
1011  if ((Small && NewNumBuckets <= InlineBuckets) ||
1012  (!Small && NewNumBuckets == getLargeRep()->NumBuckets)) {
1013  this->BaseT::initEmpty();
1014  return;
1015  }
1016 
1017  deallocateBuckets();
1018  init(NewNumBuckets);
1019  }
1020 
1021 private:
1022  unsigned getNumEntries() const {
1023  return NumEntries;
1024  }
1025 
1026  void setNumEntries(unsigned Num) {
1027  // NumEntries is hardcoded to be 31 bits wide.
1028  assert(Num < (1U << 31) && "Cannot support more than 1<<31 entries");
1029  NumEntries = Num;
1030  }
1031 
1032  unsigned getNumTombstones() const {
1033  return NumTombstones;
1034  }
1035 
1036  void setNumTombstones(unsigned Num) {
1037  NumTombstones = Num;
1038  }
1039 
1040  const BucketT *getInlineBuckets() const {
1041  assert(Small);
1042  // Note that this cast does not violate aliasing rules as we assert that
1043  // the memory's dynamic type is the small, inline bucket buffer, and the
1044  // 'storage.buffer' static type is 'char *'.
1045  return reinterpret_cast<const BucketT *>(storage.buffer);
1046  }
1047 
1048  BucketT *getInlineBuckets() {
1049  return const_cast<BucketT *>(
1050  const_cast<const SmallDenseMap *>(this)->getInlineBuckets());
1051  }
1052 
1053  const LargeRep *getLargeRep() const {
1054  assert(!Small);
1055  // Note, same rule about aliasing as with getInlineBuckets.
1056  return reinterpret_cast<const LargeRep *>(storage.buffer);
1057  }
1058 
1059  LargeRep *getLargeRep() {
1060  return const_cast<LargeRep *>(
1061  const_cast<const SmallDenseMap *>(this)->getLargeRep());
1062  }
1063 
1064  const BucketT *getBuckets() const {
1065  return Small ? getInlineBuckets() : getLargeRep()->Buckets;
1066  }
1067 
1068  BucketT *getBuckets() {
1069  return const_cast<BucketT *>(
1070  const_cast<const SmallDenseMap *>(this)->getBuckets());
1071  }
1072 
1073  unsigned getNumBuckets() const {
1074  return Small ? InlineBuckets : getLargeRep()->NumBuckets;
1075  }
1076 
1077  void deallocateBuckets() {
1078  if (Small)
1079  return;
1080 
1081  operator delete(getLargeRep()->Buckets);
1082  getLargeRep()->~LargeRep();
1083  }
1084 
1085  LargeRep allocateBuckets(unsigned Num) {
1086  assert(Num > InlineBuckets && "Must allocate more buckets than are inline");
1087  LargeRep Rep = {
1088  static_cast<BucketT*>(operator new(sizeof(BucketT) * Num)), Num
1089  };
1090  return Rep;
1091  }
1092 };
1093 
1094 template <typename KeyT, typename ValueT, typename KeyInfoT, typename Bucket,
1095  bool IsConst>
1097  friend class DenseMapIterator<KeyT, ValueT, KeyInfoT, Bucket, true>;
1098  friend class DenseMapIterator<KeyT, ValueT, KeyInfoT, Bucket, false>;
1099 
1101 
1102 public:
1103  using difference_type = ptrdiff_t;
1104  using value_type =
1105  typename std::conditional<IsConst, const Bucket, Bucket>::type;
1106  using pointer = value_type *;
1107  using reference = value_type &;
1108  using iterator_category = std::forward_iterator_tag;
1109 
1110 private:
1111  pointer Ptr = nullptr;
1112  pointer End = nullptr;
1113 
1114 public:
1115  DenseMapIterator() = default;
1116 
1117  DenseMapIterator(pointer Pos, pointer E, const DebugEpochBase &Epoch,
1118  bool NoAdvance = false)
1119  : DebugEpochBase::HandleBase(&Epoch), Ptr(Pos), End(E) {
1120  assert(isHandleInSync() && "invalid construction!");
1121 
1122  if (NoAdvance) return;
1123  AdvancePastEmptyBuckets();
1124  }
1125 
1126  // Converting ctor from non-const iterators to const iterators. SFINAE'd out
1127  // for const iterator destinations so it doesn't end up as a user defined copy
1128  // constructor.
1129  template <bool IsConstSrc,
1130  typename = typename std::enable_if<!IsConstSrc && IsConst>::type>
1133  : DebugEpochBase::HandleBase(I), Ptr(I.Ptr), End(I.End) {}
1134 
1135  reference operator*() const {
1136  assert(isHandleInSync() && "invalid iterator access!");
1137  return *Ptr;
1138  }
1139  pointer operator->() const {
1140  assert(isHandleInSync() && "invalid iterator access!");
1141  return Ptr;
1142  }
1143 
1144  bool operator==(const ConstIterator &RHS) const {
1145  assert((!Ptr || isHandleInSync()) && "handle not in sync!");
1146  assert((!RHS.Ptr || RHS.isHandleInSync()) && "handle not in sync!");
1147  assert(getEpochAddress() == RHS.getEpochAddress() &&
1148  "comparing incomparable iterators!");
1149  return Ptr == RHS.Ptr;
1150  }
1151  bool operator!=(const ConstIterator &RHS) const {
1152  assert((!Ptr || isHandleInSync()) && "handle not in sync!");
1153  assert((!RHS.Ptr || RHS.isHandleInSync()) && "handle not in sync!");
1154  assert(getEpochAddress() == RHS.getEpochAddress() &&
1155  "comparing incomparable iterators!");
1156  return Ptr != RHS.Ptr;
1157  }
1158 
1159  inline DenseMapIterator& operator++() { // Preincrement
1160  assert(isHandleInSync() && "invalid iterator access!");
1161  ++Ptr;
1162  AdvancePastEmptyBuckets();
1163  return *this;
1164  }
1165  DenseMapIterator operator++(int) { // Postincrement
1166  assert(isHandleInSync() && "invalid iterator access!");
1167  DenseMapIterator tmp = *this; ++*this; return tmp;
1168  }
1169 
1170 private:
1171  void AdvancePastEmptyBuckets() {
1172  assert(Ptr <= End);
1173  const KeyT Empty = KeyInfoT::getEmptyKey();
1174  const KeyT Tombstone = KeyInfoT::getTombstoneKey();
1175 
1176  while (Ptr != End && (KeyInfoT::isEqual(Ptr->getFirst(), Empty) ||
1177  KeyInfoT::isEqual(Ptr->getFirst(), Tombstone)))
1178  ++Ptr;
1179  }
1180 
1181  void RetreatPastEmptyBuckets() {
1182  assert(Ptr >= End);
1183  const KeyT Empty = KeyInfoT::getEmptyKey();
1184  const KeyT Tombstone = KeyInfoT::getTombstoneKey();
1185 
1186  while (Ptr != End && (KeyInfoT::isEqual(Ptr[-1].getFirst(), Empty) ||
1187  KeyInfoT::isEqual(Ptr[-1].getFirst(), Tombstone)))
1188  --Ptr;
1189  }
1190 };
1191 
1192 template <typename KeyT, typename ValueT, typename KeyInfoT>
1193 inline size_t capacity_in_bytes(const DenseMap<KeyT, ValueT, KeyInfoT> &X) {
1194  return X.getMemorySize();
1195 }
1196 
1197 } // end namespace wpi
1198 
1199 #endif // LLVM_ADT_DENSEMAP_H
unsigned Log2_32_Ceil(uint32_t Value)
Return the ceil log base 2 of the specified value, 32 if the value is zero.
Definition: MathExtras.h:526
A base class for iterator classes ("handles") that wish to poll for iterator invalidating modificatio...
Definition: EpochTracker.h:71
size_t getMemorySize() const
Return the approximate size (in bytes) of the actual map.
Definition: DenseMap.h:625
Definition: DenseMapInfo.h:29
Definition: DenseMap.h:633
Definition: DenseMap.h:56
WPILib C++ utilities (wpiutil) namespace.
Definition: SmallString.h:21
void reserve(size_type NumEntries)
Grow the densemap so that it can contain at least NumEntries items before resizing again...
Definition: DenseMap.h:96
DenseMap(unsigned InitialReserve=0)
Create a DenseMap wth an optional InitialReserve that guarantee that this number of elements can be i...
Definition: DenseMap.h:649
size_type count(const_arg_type_t< KeyT > Val) const
Return 1 if the specified key is in the map, 0 otherwise.
Definition: DenseMap.h:137
Definition: DenseMap.h:52
iterator find_as(const LookupKeyT &Val)
Alternate version of find() which allows a different, and possibly less expensive, key type.
Definition: DenseMap.h:161
Definition: DenseMap.h:790
uint64_t NextPowerOf2(uint64_t A)
Returns the next power of two (in 64-bits) that is strictly greater than A.
Definition: MathExtras.h:614
void incrementEpoch()
Calling incrementEpoch invalidates all handles pointing into the calling instance.
Definition: EpochTracker.h:57
unsigned getMinBucketToReserveForEntries(unsigned NumEntries)
Returns the number of buckets to allocate to ensure that the DenseMap can accommodate NumEntries with...
Definition: DenseMap.h:348
A base class for data structure classes wishing to make iterators ("handles") pointing into themselve...
Definition: EpochTracker.h:49
void insert(InputIt I, InputIt E)
insert - Range insertion of pairs.
Definition: DenseMap.h:259
This union template exposes a suitably aligned and sized character array member which can hold elemen...
Definition: AlignOf.h:138
Definition: DenseMap.h:40
ValueT lookup(const_arg_type_t< KeyT > Val) const
lookup - Return the entry for the specified key, or a default constructed value if no such entry exis...
Definition: DenseMap.h:177
auto size(R &&Range, typename std::enable_if< std::is_same< typename std::iterator_traits< decltype(Range.begin())>::iterator_category, std::random_access_iterator_tag >::value, void >::type *=nullptr) -> decltype(std::distance(Range.begin(), Range.end()))
Get the size of a range.
Definition: STLExtras.h:999
constexpr bool isPowerOf2_64(uint64_t Value)
Return true if the argument is a power of two > 0 (64 bit edition.)
Definition: MathExtras.h:423
bool isPointerIntoBucketsArray(const void *Ptr) const
isPointerIntoBucketsArray - Return true if the specified pointer points somewhere into the DenseMap's...
Definition: DenseMap.h:310
std::pair< iterator, bool > insert_as(std::pair< KeyT, ValueT > &&KV, const LookupKeyT &Val)
Alternate version of insert() which allows a different, and possibly less expensive, key type.
Definition: DenseMap.h:241
const void * getPointerIntoBucketsArray() const
getPointerIntoBucketsArray() - Return an opaque pointer into the buckets array.
Definition: DenseMap.h:317