DenseMap.h revision 137d4b253384adce88bfa2a1c37695d90f0a9d6c 
1//===- llvm/ADT/DenseMap.h - Dense probed hash table ------------*- C++ -*-===//
2//
3//                     The LLVM Compiler Infrastructure
4//
5// This file was developed by Chris Lattner and is distributed under
6// the University of Illinois Open Source 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 <cassert>
19#include <utility>
20
21namespace llvm {
22
23template<typename T>
24struct DenseMapKeyInfo {
25  //static inline T getEmptyKey();
26  //static inline T getTombstoneKey();
27  //static unsigned getHashValue(const T &Val);
28  //static bool isPod()
29};
30
31template<typename T>
32struct DenseMapKeyInfo<T*> {
33  static inline T* getEmptyKey() { return (T*)-1; }
34  static inline T* getTombstoneKey() { return (T*)-2; }
35  static unsigned getHashValue(const T *PtrVal) {
36    return (unsigned)((uintptr_t)PtrVal >> 4) ^
37           (unsigned)((uintptr_t)PtrVal >> 9);
38  }
39  static bool isPod() { return true; }
40};
41
42template<typename KeyT, typename ValueT>
43class DenseMapIterator;
44template<typename KeyT, typename ValueT>
45class DenseMapConstIterator;
46
47template<typename KeyT, typename ValueT>
48class DenseMap {
49  typedef std::pair<KeyT, ValueT> BucketT;
50  unsigned NumBuckets;
51  BucketT *Buckets;
52
53  unsigned NumEntries;
54  DenseMap(const DenseMap &); // not implemented.
55public:
56  explicit DenseMap(unsigned NumInitBuckets = 8) {
57    init(NumInitBuckets);
58  }
59  ~DenseMap() {
60    const KeyT EmptyKey = getEmptyKey(), TombstoneKey = getTombstoneKey();
61    for (BucketT *P = Buckets, *E = Buckets+NumBuckets; P != E; ++P) {
62      if (P->first != EmptyKey && P->first != TombstoneKey)
63        P->second.~ValueT();
64      P->first.~KeyT();
65    }
66    delete[] (char*)Buckets;
67  }
68
69  typedef DenseMapIterator<KeyT, ValueT> iterator;
70  typedef DenseMapConstIterator<KeyT, ValueT> const_iterator;
71  inline iterator begin() {
72     return DenseMapIterator<KeyT, ValueT>(Buckets, Buckets+NumBuckets);
73  }
74  inline iterator end() {
75    return DenseMapIterator<KeyT, ValueT>(Buckets+NumBuckets,
76                                          Buckets+NumBuckets);
77  }
78  inline const_iterator begin() const {
79    return DenseMapConstIterator<KeyT, ValueT>(Buckets, Buckets+NumBuckets);
80  }
81  inline const_iterator end() const {
82    return DenseMapConstIterator<KeyT, ValueT>(Buckets+NumBuckets,
83                                               Buckets+NumBuckets);
84  }
85
86  bool empty() const { return NumEntries == 0; }
87  unsigned size() const { return NumEntries; }
88
89  void clear() {
90    const KeyT EmptyKey = getEmptyKey(), TombstoneKey = getTombstoneKey();
91    for (BucketT *P = Buckets, *E = Buckets+NumBuckets; P != E; ++P) {
92      if (P->first != EmptyKey && P->first != TombstoneKey) {
93        P->first = EmptyKey;
94        P->second.~ValueT();
95        --NumEntries;
96      }
97    }
98    assert(NumEntries == 0 && "Node count imbalance!");
99  }
100
101  /// count - Return true if the specified key is in the map.
102  bool count(const KeyT &Val) const {
103    BucketT *TheBucket;
104    return LookupBucketFor(Val, TheBucket);
105  }
106
107  iterator find(const KeyT &Val) const {
108    BucketT *TheBucket;
109    if (LookupBucketFor(Val, TheBucket))
110      return iterator(TheBucket, Buckets+NumBuckets);
111    return end();
112  }
113
114  bool erase(const KeyT &Val) {
115    BucketT *TheBucket;
116    if (!LookupBucketFor(Val, TheBucket))
117      return false; // not in map.
118
119    TheBucket->second.~ValueT();
120    TheBucket->first = getTombstoneKey();
121    --NumEntries;
122    return true;
123  }
124  bool erase(iterator I) {
125    BucketT *TheBucket = &*I;
126    TheBucket->second.~ValueT();
127    TheBucket->first = getTombstoneKey();
128    --NumEntries;
129    return true;
130  }
131
132  ValueT &operator[](const KeyT &Val) {
133    BucketT *TheBucket;
134    if (LookupBucketFor(Val, TheBucket))
135      return TheBucket->second;
136
137    // If the load of the hash table is more than 3/4, grow it.
138    if (NumEntries*4 >= NumBuckets*3) {
139      this->grow();
140      LookupBucketFor(Val, TheBucket);
141    }
142    ++NumEntries;
143    TheBucket->first = Val;
144    new (&TheBucket->second) ValueT();
145    return TheBucket->second;
146  }
147
148private:
149  static unsigned getHashValue(const KeyT &Val) {
150    return DenseMapKeyInfo<KeyT>::getHashValue(Val);
151  }
152  static const KeyT getEmptyKey() {
153    return DenseMapKeyInfo<KeyT>::getEmptyKey();
154  }
155  static const KeyT getTombstoneKey() {
156    return DenseMapKeyInfo<KeyT>::getTombstoneKey();
157  }
158
159  /// LookupBucketFor - Lookup the appropriate bucket for Val, returning it in
160  /// FoundBucket.  If the bucket contains the key and a value, this returns
161  /// true, otherwise it returns a bucket with an empty marker or tombstone and
162  /// returns false.
163  bool LookupBucketFor(const KeyT &Val, BucketT *&FoundBucket) const {
164    unsigned BucketNo = getHashValue(Val);
165    unsigned ProbeAmt = 1;
166    BucketT *BucketsPtr = Buckets;
167
168    // FoundTombstone - Keep track of whether we find a tombstone while probing.
169    BucketT *FoundTombstone = 0;
170    const KeyT EmptyKey = getEmptyKey();
171    const KeyT TombstoneKey = getTombstoneKey();
172    assert(Val != EmptyKey && Val != TombstoneKey &&
173           "Empty/Tombstone value shouldn't be inserted into map!");
174
175    while (1) {
176      BucketT *ThisBucket = BucketsPtr + (BucketNo & (NumBuckets-1));
177      // Found Val's bucket?  If so, return it.
178      if (ThisBucket->first == Val) {
179        FoundBucket = ThisBucket;
180        return true;
181      }
182
183      // If we found an empty bucket, the key doesn't exist in the set.
184      // Insert it and return the default value.
185      if (ThisBucket->first == EmptyKey) {
186        // If we've already seen a tombstone while probing, fill it in instead
187        // of the empty bucket we eventually probed to.
188        if (FoundTombstone) ThisBucket = FoundTombstone;
189        FoundBucket = FoundTombstone ? FoundTombstone : ThisBucket;
190        return false;
191      }
192
193      // If this is a tombstone, remember it.  If Val ends up not in the map, we
194      // prefer to return it than something that would require more probing.
195      if (ThisBucket->first == TombstoneKey && !FoundTombstone)
196        FoundTombstone = ThisBucket;  // Remember the first tombstone found.
197
198      // Otherwise, it's a hash collision or a tombstone, continue quadratic
199      // probing.
200      BucketNo += ProbeAmt++;
201    }
202  }
203
204  void init(unsigned InitBuckets) {
205    NumEntries = 0;
206    NumBuckets = InitBuckets;
207    assert(InitBuckets && (InitBuckets & InitBuckets-1) == 0 &&
208           "# initial buckets must be a power of two!");
209    Buckets = (BucketT*)new char[sizeof(BucketT)*InitBuckets];
210    // Initialize all the keys to EmptyKey.
211    const KeyT EmptyKey = getEmptyKey();
212    for (unsigned i = 0; i != InitBuckets; ++i)
213      new (&Buckets[i].first) KeyT(EmptyKey);
214  }
215
216  void grow() {
217    unsigned OldNumBuckets = NumBuckets;
218    BucketT *OldBuckets = Buckets;
219
220    // Double the number of buckets.
221    NumBuckets <<= 1;
222    Buckets = (BucketT*)new char[sizeof(BucketT)*NumBuckets];
223
224    // Initialize all the keys to EmptyKey.
225    const KeyT EmptyKey = getEmptyKey();
226    for (unsigned i = 0, e = NumBuckets; i != e; ++i)
227      new (&Buckets[i].first) KeyT(EmptyKey);
228
229    // Insert all the old elements.
230    const KeyT TombstoneKey = getTombstoneKey();
231    for (BucketT *B = OldBuckets, *E = OldBuckets+OldNumBuckets; B != E; ++B) {
232      if (B->first != EmptyKey && B->first != TombstoneKey) {
233        // Insert the key/value into the new table.
234        BucketT *DestBucket;
235        bool FoundVal = LookupBucketFor(B->first, DestBucket);
236        FoundVal = FoundVal; // silence warning.
237        assert(!FoundVal && "Key already in new map?");
238        DestBucket->first = B->first;
239        new (&DestBucket->second) ValueT(B->second);
240
241        // Free the value.
242        B->second.~ValueT();
243      }
244      B->first.~KeyT();
245    }
246
247    // Free the old table.
248    delete[] (char*)OldBuckets;
249  }
250};
251
252template<typename KeyT, typename ValueT>
253class DenseMapIterator {
254  typedef std::pair<KeyT, ValueT> BucketT;
255protected:
256  const BucketT *Ptr, *End;
257public:
258  DenseMapIterator(const BucketT *Pos, const BucketT *E) : Ptr(Pos), End(E) {
259    AdvancePastEmptyBuckets();
260  }
261
262  std::pair<KeyT, ValueT> &operator*() const {
263    return *const_cast<BucketT*>(Ptr);
264  }
265  std::pair<KeyT, ValueT> *operator->() const {
266    return const_cast<BucketT*>(Ptr);
267  }
268
269  bool operator==(const DenseMapIterator &RHS) const {
270    return Ptr == RHS.Ptr;
271  }
272  bool operator!=(const DenseMapIterator &RHS) const {
273    return Ptr != RHS.Ptr;
274  }
275
276  inline DenseMapIterator& operator++() {          // Preincrement
277    ++Ptr;
278    AdvancePastEmptyBuckets();
279    return *this;
280  }
281  DenseMapIterator operator++(int) {        // Postincrement
282    DenseMapIterator tmp = *this; ++*this; return tmp;
283  }
284
285private:
286  void AdvancePastEmptyBuckets() {
287    const KeyT Empty = DenseMapKeyInfo<KeyT>::getEmptyKey();
288    const KeyT Tombstone = DenseMapKeyInfo<KeyT>::getTombstoneKey();
289
290    while (Ptr != End && (Ptr->first == Empty || Ptr->first == Tombstone))
291      ++Ptr;
292  }
293};
294
295template<typename KeyT, typename ValueT>
296class DenseMapConstIterator : public DenseMapIterator<KeyT, ValueT> {
297public:
298  DenseMapConstIterator(const std::pair<KeyT, ValueT> *Pos,
299                        const std::pair<KeyT, ValueT> *E)
300    : DenseMapIterator<KeyT, ValueT>(Pos, E) {
301  }
302  const std::pair<KeyT, ValueT> &operator*() const {
303    return *this->Ptr;
304  }
305  const std::pair<KeyT, ValueT> *operator->() const {
306    return this->Ptr;
307  }
308};
309
310} // end namespace llvm
311
312#endif
313