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