DenseMap.h revision 2f39b29170e0f69491fc5b73952725266ac32fb8 
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/Support/DataTypes.h"
18#include "llvm/Support/MathExtras.h"
19#include <cassert>
20#include <utility>
21
22namespace llvm {
23
24template<typename T>
25struct DenseMapInfo {
26  //static inline T getEmptyKey();
27  //static inline T getTombstoneKey();
28  //static unsigned getHashValue(const T &Val);
29  //static bool isEqual(const T &LHS, const T &RHS);
30  //static bool isPod()
31};
32
33// Provide DenseMapInfo for all pointers.
34template<typename T>
35struct DenseMapInfo<T*> {
36  static inline T* getEmptyKey() { return reinterpret_cast<T*>(-1); }
37  static inline T* getTombstoneKey() { return reinterpret_cast<T*>(-2); }
38  static unsigned getHashValue(const T *PtrVal) {
39    return (unsigned((uintptr_t)PtrVal) >> 4) ^
40           (unsigned((uintptr_t)PtrVal) >> 9);
41  }
42  static bool isEqual(const T *LHS, const T *RHS) { return LHS == RHS; }
43  static bool isPod() { return true; }
44};
45
46// Provide DenseMapInfo for unsigned ints.
47template<> struct DenseMapInfo<unsigned> {
48  static inline unsigned getEmptyKey() { return ~0; }
49  static inline unsigned getTombstoneKey() { return ~0 - 1; }
50  static unsigned getHashValue(const unsigned& Val) { return Val * 37; }
51  static bool isPod() { return true; }
52  static bool isEqual(const unsigned& LHS, const unsigned& RHS) {
53  return LHS == RHS;
54  }
55};
56
57// Provide DenseMapInfo for unsigned longs.
58template<> struct DenseMapInfo<unsigned long> {
59  static inline unsigned long getEmptyKey() { return ~0L; }
60  static inline unsigned long getTombstoneKey() { return ~0L - 1L; }
61  static unsigned getHashValue(const unsigned long& Val) { return Val * 37L; }
62  static bool isPod() { return true; }
63  static bool isEqual(const unsigned long& LHS, const unsigned long& RHS) {
64  return LHS == RHS;
65  }
66};
67
68// Provide DenseMapInfo for all pairs whose members have info.
69template<typename T, typename U>
70struct DenseMapInfo<std::pair<T, U> > {
71  typedef std::pair<T, U> Pair;
72  typedef DenseMapInfo<T> FirstInfo;
73  typedef DenseMapInfo<U> SecondInfo;
74
75  static inline Pair getEmptyKey() {
76    return std::make_pair(FirstInfo::getEmptyKey(),
77                          SecondInfo::getEmptyKey());
78  }
79  static inline Pair getTombstoneKey() {
80    return std::make_pair(FirstInfo::getTombstoneKey(),
81                            SecondInfo::getEmptyKey());
82  }
83  static unsigned getHashValue(const Pair& PairVal) {
84    uint64_t key = (uint64_t)FirstInfo::getHashValue(PairVal.first) << 32
85          | (uint64_t)SecondInfo::getHashValue(PairVal.second);
86    key += ~(key << 32);
87    key ^= (key >> 22);
88    key += ~(key << 13);
89    key ^= (key >> 8);
90    key += (key << 3);
91    key ^= (key >> 15);
92    key += ~(key << 27);
93    key ^= (key >> 31);
94    return (unsigned)key;
95  }
96  static bool isEqual(const Pair& LHS, const Pair& RHS) { return LHS == RHS; }
97  static bool isPod() { return FirstInfo::isPod() && SecondInfo::isPod(); }
98};
99
100template<typename KeyT, typename ValueT,
101         typename KeyInfoT = DenseMapInfo<KeyT>,
102         typename ValueInfoT = DenseMapInfo<ValueT> >
103class DenseMapIterator;
104template<typename KeyT, typename ValueT,
105         typename KeyInfoT = DenseMapInfo<KeyT>,
106         typename ValueInfoT = DenseMapInfo<ValueT> >
107class DenseMapConstIterator;
108
109template<typename KeyT, typename ValueT,
110         typename KeyInfoT = DenseMapInfo<KeyT>,
111         typename ValueInfoT = DenseMapInfo<ValueT> >
112class DenseMap {
113  typedef std::pair<KeyT, ValueT> BucketT;
114  unsigned NumBuckets;
115  BucketT *Buckets;
116
117  unsigned NumEntries;
118  unsigned NumTombstones;
119public:
120  typedef KeyT key_type;
121  typedef ValueT mapped_type;
122  typedef BucketT value_type;
123
124  DenseMap(const DenseMap& other) {
125    NumBuckets = 0;
126    CopyFrom(other);
127  }
128
129  explicit DenseMap(unsigned NumInitBuckets = 64) {
130    init(NumInitBuckets);
131  }
132
133  ~DenseMap() {
134    const KeyT EmptyKey = getEmptyKey(), TombstoneKey = getTombstoneKey();
135    for (BucketT *P = Buckets, *E = Buckets+NumBuckets; P != E; ++P) {
136      if (!KeyInfoT::isEqual(P->first, EmptyKey) &&
137          !KeyInfoT::isEqual(P->first, TombstoneKey))
138        P->second.~ValueT();
139      P->first.~KeyT();
140    }
141    operator delete(Buckets);
142  }
143
144  typedef DenseMapIterator<KeyT, ValueT, KeyInfoT> iterator;
145  typedef DenseMapConstIterator<KeyT, ValueT, KeyInfoT> const_iterator;
146  inline iterator begin() {
147     return iterator(Buckets, Buckets+NumBuckets);
148  }
149  inline iterator end() {
150    return iterator(Buckets+NumBuckets, Buckets+NumBuckets);
151  }
152  inline const_iterator begin() const {
153    return const_iterator(Buckets, Buckets+NumBuckets);
154  }
155  inline const_iterator end() const {
156    return const_iterator(Buckets+NumBuckets, Buckets+NumBuckets);
157  }
158
159  bool empty() const { return NumEntries == 0; }
160  unsigned size() const { return NumEntries; }
161
162  /// Grow the densemap so that it has at least Size buckets. Does not shrink
163  void resize(size_t Size) { grow(Size); }
164
165  void clear() {
166    // If the capacity of the array is huge, and the # elements used is small,
167    // shrink the array.
168    if (NumEntries * 4 < NumBuckets && NumBuckets > 64) {
169      shrink_and_clear();
170      return;
171    }
172
173    const KeyT EmptyKey = getEmptyKey(), TombstoneKey = getTombstoneKey();
174    for (BucketT *P = Buckets, *E = Buckets+NumBuckets; P != E; ++P) {
175      if (!KeyInfoT::isEqual(P->first, EmptyKey)) {
176        if (!KeyInfoT::isEqual(P->first, TombstoneKey)) {
177          P->second.~ValueT();
178          --NumEntries;
179        }
180        P->first = EmptyKey;
181      }
182    }
183    assert(NumEntries == 0 && "Node count imbalance!");
184    NumTombstones = 0;
185  }
186
187  /// count - Return true if the specified key is in the map.
188  bool count(const KeyT &Val) const {
189    BucketT *TheBucket;
190    return LookupBucketFor(Val, TheBucket);
191  }
192
193  iterator find(const KeyT &Val) {
194    BucketT *TheBucket;
195    if (LookupBucketFor(Val, TheBucket))
196      return iterator(TheBucket, Buckets+NumBuckets);
197    return end();
198  }
199  const_iterator find(const KeyT &Val) const {
200    BucketT *TheBucket;
201    if (LookupBucketFor(Val, TheBucket))
202      return const_iterator(TheBucket, Buckets+NumBuckets);
203    return end();
204  }
205
206  /// lookup - Return the entry for the specified key, or a default
207  /// constructed value if no such entry exists.
208  ValueT lookup(const KeyT &Val) const {
209    BucketT *TheBucket;
210    if (LookupBucketFor(Val, TheBucket))
211      return TheBucket->second;
212    return ValueT();
213  }
214
215  std::pair<iterator, bool> insert(const std::pair<KeyT, ValueT> &KV) {
216    BucketT *TheBucket;
217    if (LookupBucketFor(KV.first, TheBucket))
218      return std::make_pair(iterator(TheBucket, Buckets+NumBuckets),
219                            false); // Already in map.
220
221    // Otherwise, insert the new element.
222    TheBucket = InsertIntoBucket(KV.first, KV.second, TheBucket);
223    return std::make_pair(iterator(TheBucket, Buckets+NumBuckets),
224                          true);
225  }
226
227  /// insert - Range insertion of pairs.
228  template<typename InputIt>
229  void insert(InputIt I, InputIt E) {
230    for (; I != E; ++I)
231      insert(*I);
232  }
233
234
235  bool erase(const KeyT &Val) {
236    BucketT *TheBucket;
237    if (!LookupBucketFor(Val, TheBucket))
238      return false; // not in map.
239
240    TheBucket->second.~ValueT();
241    TheBucket->first = getTombstoneKey();
242    --NumEntries;
243    ++NumTombstones;
244    return true;
245  }
246  bool erase(iterator I) {
247    BucketT *TheBucket = &*I;
248    TheBucket->second.~ValueT();
249    TheBucket->first = getTombstoneKey();
250    --NumEntries;
251    ++NumTombstones;
252    return true;
253  }
254
255  value_type& FindAndConstruct(const KeyT &Key) {
256    BucketT *TheBucket;
257    if (LookupBucketFor(Key, TheBucket))
258      return *TheBucket;
259
260    return *InsertIntoBucket(Key, ValueT(), TheBucket);
261  }
262
263  ValueT &operator[](const KeyT &Key) {
264    return FindAndConstruct(Key).second;
265  }
266
267  DenseMap& operator=(const DenseMap& other) {
268    CopyFrom(other);
269    return *this;
270  }
271
272private:
273  void CopyFrom(const DenseMap& other) {
274    if (NumBuckets != 0 && (!KeyInfoT::isPod() || !ValueInfoT::isPod())) {
275      const KeyT EmptyKey = getEmptyKey(), TombstoneKey = getTombstoneKey();
276      for (BucketT *P = Buckets, *E = Buckets+NumBuckets; P != E; ++P) {
277        if (!KeyInfoT::isEqual(P->first, EmptyKey) &&
278            !KeyInfoT::isEqual(P->first, TombstoneKey))
279          P->second.~ValueT();
280        P->first.~KeyT();
281      }
282    }
283
284    NumEntries = other.NumEntries;
285    NumTombstones = other.NumTombstones;
286
287    if (NumBuckets)
288      operator delete(Buckets);
289    Buckets = static_cast<BucketT*>(operator new(sizeof(BucketT) *
290                                                 other.NumBuckets));
291
292    if (KeyInfoT::isPod() && ValueInfoT::isPod())
293      memcpy(Buckets, other.Buckets, other.NumBuckets * sizeof(BucketT));
294    else
295      for (size_t i = 0; i < other.NumBuckets; ++i) {
296        new (&Buckets[i].first) KeyT(other.Buckets[i].first);
297        if (!KeyInfoT::isEqual(Buckets[i].first, getEmptyKey()) &&
298            !KeyInfoT::isEqual(Buckets[i].first, getTombstoneKey()))
299          new (&Buckets[i].second) ValueT(other.Buckets[i].second);
300      }
301    NumBuckets = other.NumBuckets;
302  }
303
304  BucketT *InsertIntoBucket(const KeyT &Key, const ValueT &Value,
305                            BucketT *TheBucket) {
306    // If the load of the hash table is more than 3/4, or if fewer than 1/8 of
307    // the buckets are empty (meaning that many are filled with tombstones),
308    // grow the table.
309    //
310    // The later case is tricky.  For example, if we had one empty bucket with
311    // tons of tombstones, failing lookups (e.g. for insertion) would have to
312    // probe almost the entire table until it found the empty bucket.  If the
313    // table completely filled with tombstones, no lookup would ever succeed,
314    // causing infinite loops in lookup.
315    if (NumEntries*4 >= NumBuckets*3 ||
316        NumBuckets-(NumEntries+NumTombstones) < NumBuckets/8) {
317      this->grow(NumBuckets * 2);
318      LookupBucketFor(Key, TheBucket);
319    }
320    ++NumEntries;
321
322    // If we are writing over a tombstone, remember this.
323    if (!KeyInfoT::isEqual(TheBucket->first, getEmptyKey()))
324      --NumTombstones;
325
326    TheBucket->first = Key;
327    new (&TheBucket->second) ValueT(Value);
328    return TheBucket;
329  }
330
331  static unsigned getHashValue(const KeyT &Val) {
332    return KeyInfoT::getHashValue(Val);
333  }
334  static const KeyT getEmptyKey() {
335    return KeyInfoT::getEmptyKey();
336  }
337  static const KeyT getTombstoneKey() {
338    return KeyInfoT::getTombstoneKey();
339  }
340
341  /// LookupBucketFor - Lookup the appropriate bucket for Val, returning it in
342  /// FoundBucket.  If the bucket contains the key and a value, this returns
343  /// true, otherwise it returns a bucket with an empty marker or tombstone and
344  /// returns false.
345  bool LookupBucketFor(const KeyT &Val, BucketT *&FoundBucket) const {
346    unsigned BucketNo = getHashValue(Val);
347    unsigned ProbeAmt = 1;
348    BucketT *BucketsPtr = Buckets;
349
350    // FoundTombstone - Keep track of whether we find a tombstone while probing.
351    BucketT *FoundTombstone = 0;
352    const KeyT EmptyKey = getEmptyKey();
353    const KeyT TombstoneKey = getTombstoneKey();
354    assert(!KeyInfoT::isEqual(Val, EmptyKey) &&
355           !KeyInfoT::isEqual(Val, TombstoneKey) &&
356           "Empty/Tombstone value shouldn't be inserted into map!");
357
358    while (1) {
359      BucketT *ThisBucket = BucketsPtr + (BucketNo & (NumBuckets-1));
360      // Found Val's bucket?  If so, return it.
361      if (KeyInfoT::isEqual(ThisBucket->first, Val)) {
362        FoundBucket = ThisBucket;
363        return true;
364      }
365
366      // If we found an empty bucket, the key doesn't exist in the set.
367      // Insert it and return the default value.
368      if (KeyInfoT::isEqual(ThisBucket->first, EmptyKey)) {
369        // If we've already seen a tombstone while probing, fill it in instead
370        // of the empty bucket we eventually probed to.
371        if (FoundTombstone) ThisBucket = FoundTombstone;
372        FoundBucket = FoundTombstone ? FoundTombstone : ThisBucket;
373        return false;
374      }
375
376      // If this is a tombstone, remember it.  If Val ends up not in the map, we
377      // prefer to return it than something that would require more probing.
378      if (KeyInfoT::isEqual(ThisBucket->first, TombstoneKey) && !FoundTombstone)
379        FoundTombstone = ThisBucket;  // Remember the first tombstone found.
380
381      // Otherwise, it's a hash collision or a tombstone, continue quadratic
382      // probing.
383      BucketNo += ProbeAmt++;
384    }
385  }
386
387  void init(unsigned InitBuckets) {
388    NumEntries = 0;
389    NumTombstones = 0;
390    NumBuckets = InitBuckets;
391    assert(InitBuckets && (InitBuckets & (InitBuckets-1)) == 0 &&
392           "# initial buckets must be a power of two!");
393    Buckets = static_cast<BucketT*>(operator new(sizeof(BucketT)*InitBuckets));
394    // Initialize all the keys to EmptyKey.
395    const KeyT EmptyKey = getEmptyKey();
396    for (unsigned i = 0; i != InitBuckets; ++i)
397      new (&Buckets[i].first) KeyT(EmptyKey);
398  }
399
400  void grow(unsigned AtLeast) {
401    unsigned OldNumBuckets = NumBuckets;
402    BucketT *OldBuckets = Buckets;
403
404    // Double the number of buckets.
405    while (NumBuckets <= AtLeast)
406      NumBuckets <<= 1;
407    NumTombstones = 0;
408    Buckets = static_cast<BucketT*>(operator new(sizeof(BucketT)*NumBuckets));
409
410    // Initialize all the keys to EmptyKey.
411    const KeyT EmptyKey = getEmptyKey();
412    for (unsigned i = 0, e = NumBuckets; i != e; ++i)
413      new (&Buckets[i].first) KeyT(EmptyKey);
414
415    // Insert all the old elements.
416    const KeyT TombstoneKey = getTombstoneKey();
417    for (BucketT *B = OldBuckets, *E = OldBuckets+OldNumBuckets; B != E; ++B) {
418      if (!KeyInfoT::isEqual(B->first, EmptyKey) &&
419          !KeyInfoT::isEqual(B->first, TombstoneKey)) {
420        // Insert the key/value into the new table.
421        BucketT *DestBucket;
422        bool FoundVal = LookupBucketFor(B->first, DestBucket);
423        FoundVal = FoundVal; // silence warning.
424        assert(!FoundVal && "Key already in new map?");
425        DestBucket->first = B->first;
426        new (&DestBucket->second) ValueT(B->second);
427
428        // Free the value.
429        B->second.~ValueT();
430      }
431      B->first.~KeyT();
432    }
433
434    // Free the old table.
435    operator delete(OldBuckets);
436  }
437
438  void shrink_and_clear() {
439    unsigned OldNumBuckets = NumBuckets;
440    BucketT *OldBuckets = Buckets;
441
442    // Reduce the number of buckets.
443    NumBuckets = NumEntries > 32 ? 1 << (Log2_32_Ceil(NumEntries) + 1)
444                                 : 64;
445    NumTombstones = 0;
446    Buckets = static_cast<BucketT*>(operator new(sizeof(BucketT)*NumBuckets));
447
448    // Initialize all the keys to EmptyKey.
449    const KeyT EmptyKey = getEmptyKey();
450    for (unsigned i = 0, e = NumBuckets; i != e; ++i)
451      new (&Buckets[i].first) KeyT(EmptyKey);
452
453    // Free the old buckets.
454    const KeyT TombstoneKey = getTombstoneKey();
455    for (BucketT *B = OldBuckets, *E = OldBuckets+OldNumBuckets; B != E; ++B) {
456      if (!KeyInfoT::isEqual(B->first, EmptyKey) &&
457          !KeyInfoT::isEqual(B->first, TombstoneKey)) {
458        // Free the value.
459        B->second.~ValueT();
460      }
461      B->first.~KeyT();
462    }
463
464    // Free the old table.
465    operator delete(OldBuckets);
466
467    NumEntries = 0;
468  }
469};
470
471template<typename KeyT, typename ValueT, typename KeyInfoT, typename ValueInfoT>
472class DenseMapIterator {
473  typedef std::pair<KeyT, ValueT> BucketT;
474protected:
475  const BucketT *Ptr, *End;
476public:
477  DenseMapIterator(void) : Ptr(0), End(0) {}
478
479  DenseMapIterator(const BucketT *Pos, const BucketT *E) : Ptr(Pos), End(E) {
480    AdvancePastEmptyBuckets();
481  }
482
483  std::pair<KeyT, ValueT> &operator*() const {
484    return *const_cast<BucketT*>(Ptr);
485  }
486  std::pair<KeyT, ValueT> *operator->() const {
487    return const_cast<BucketT*>(Ptr);
488  }
489
490  bool operator==(const DenseMapIterator &RHS) const {
491    return Ptr == RHS.Ptr;
492  }
493  bool operator!=(const DenseMapIterator &RHS) const {
494    return Ptr != RHS.Ptr;
495  }
496
497  inline DenseMapIterator& operator++() {          // Preincrement
498    ++Ptr;
499    AdvancePastEmptyBuckets();
500    return *this;
501  }
502  DenseMapIterator operator++(int) {        // Postincrement
503    DenseMapIterator tmp = *this; ++*this; return tmp;
504  }
505
506private:
507  void AdvancePastEmptyBuckets() {
508    const KeyT Empty = KeyInfoT::getEmptyKey();
509    const KeyT Tombstone = KeyInfoT::getTombstoneKey();
510
511    while (Ptr != End &&
512           (KeyInfoT::isEqual(Ptr->first, Empty) ||
513            KeyInfoT::isEqual(Ptr->first, Tombstone)))
514      ++Ptr;
515  }
516};
517
518template<typename KeyT, typename ValueT, typename KeyInfoT, typename ValueInfoT>
519class DenseMapConstIterator : public DenseMapIterator<KeyT, ValueT, KeyInfoT> {
520public:
521  DenseMapConstIterator(void) : DenseMapIterator<KeyT, ValueT, KeyInfoT>() {}
522  DenseMapConstIterator(const std::pair<KeyT, ValueT> *Pos,
523                        const std::pair<KeyT, ValueT> *E)
524    : DenseMapIterator<KeyT, ValueT, KeyInfoT>(Pos, E) {
525  }
526  const std::pair<KeyT, ValueT> &operator*() const {
527    return *this->Ptr;
528  }
529  const std::pair<KeyT, ValueT> *operator->() const {
530    return this->Ptr;
531  }
532};
533
534} // end namespace llvm
535
536#endif
537