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