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