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