DenseMap.h revision f6390f48e6324b0221d10a9c75ab625357d8a43a 
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;
44
45template<typename KeyT, typename ValueT>
46class DenseMap {
47  typedef std::pair<KeyT, ValueT> BucketT;
48  unsigned NumBuckets;
49  BucketT *Buckets;
50
51  unsigned NumEntries;
52  DenseMap(const DenseMap &); // not implemented.
53public:
54  explicit DenseMap(unsigned NumInitBuckets = 8) {
55    init(NumInitBuckets);
56  }
57  ~DenseMap() {
58    const KeyT EmptyKey = getEmptyKey(), TombstoneKey = getTombstoneKey();
59    for (BucketT *P = Buckets, *E = Buckets+NumBuckets; P != E; ++P) {
60      if (P->first != EmptyKey && P->first != TombstoneKey)
61        P->second.~ValueT();
62      P->first.~KeyT();
63    }
64    delete[] (char*)Buckets;
65  }
66
67  typedef DenseMapIterator<KeyT, ValueT> iterator;
68  typedef DenseMapIterator<KeyT, ValueT> const_iterator;
69  inline iterator begin() const;
70  inline iterator end() const;
71
72  unsigned size() const { return NumEntries; }
73
74  void clear() {
75    const KeyT EmptyKey = getEmptyKey(), TombstoneKey = getTombstoneKey();
76    for (BucketT *P = Buckets, *E = Buckets+NumBuckets; P != E; ++P) {
77      if (P->first != EmptyKey && P->first != TombstoneKey) {
78        P->first = EmptyKey;
79        P->second.~ValueT();
80        --NumEntries;
81      }
82    }
83    assert(NumEntries == 0 && "Node count imbalance!");
84  }
85
86  /// count - Return true if the specified key is in the map.
87  bool count(const KeyT &Val) const {
88    BucketT *TheBucket;
89    return LookupBucketFor(Val, TheBucket);
90  }
91
92  ValueT &operator[](const KeyT &Val) {
93    BucketT *TheBucket;
94    if (LookupBucketFor(Val, TheBucket))
95      return TheBucket->second;
96
97    // If the load of the hash table is more than 3/4, grow it.
98    if (NumEntries*4 >= NumBuckets*3) {
99      this->grow();
100      LookupBucketFor(Val, TheBucket);
101    }
102    ++NumEntries;
103    TheBucket->first = Val;
104    new (&TheBucket->second) ValueT();
105    return TheBucket->second;
106  }
107
108private:
109  unsigned getHashValue(const KeyT &Val) const {
110    return DenseMapKeyInfo<KeyT>::getHashValue(Val);
111  }
112  const KeyT getEmptyKey() const { return DenseMapKeyInfo<KeyT>::getEmptyKey();}
113  const KeyT getTombstoneKey() const {
114    return DenseMapKeyInfo<KeyT>::getTombstoneKey();
115  }
116
117  /// LookupBucketFor - Lookup the appropriate bucket for Val, returning it in
118  /// FoundBucket.  If the bucket contains the key and a value, this returns
119  /// true, otherwise it returns a bucket with an empty marker or tombstone and
120  /// returns false.
121  bool LookupBucketFor(const KeyT &Val, BucketT *&FoundBucket) const {
122    unsigned BucketNo = getHashValue(Val);
123    unsigned ProbeAmt = 1;
124    BucketT *BucketsPtr = Buckets;
125
126    // FoundTombstone - Keep track of whether we find a tombstone while probing.
127    BucketT *FoundTombstone = 0;
128    const KeyT EmptyKey = getEmptyKey();
129    const KeyT TombstoneKey = getTombstoneKey();
130    assert(Val != EmptyKey && Val != TombstoneKey &&
131           "Empty/Tombstone value shouldn't be inserted into map!");
132
133    while (1) {
134      BucketT *ThisBucket = BucketsPtr + (BucketNo & (NumBuckets-1));
135      // Found Val's bucket?  If so, return it.
136      if (ThisBucket->first == Val) {
137        FoundBucket = ThisBucket;
138        return true;
139      }
140
141      // If we found an empty bucket, the key doesn't exist in the set.
142      // Insert it and return the default value.
143      if (ThisBucket->first == EmptyKey) {
144        // If we've already seen a tombstone while probing, fill it in instead
145        // of the empty bucket we eventually probed to.
146        if (FoundTombstone) ThisBucket = FoundTombstone;
147        FoundBucket = FoundTombstone ? FoundTombstone : ThisBucket;
148        return false;
149      }
150
151      // If this is a tombstone, remember it.  If Val ends up not in the map, we
152      // prefer to return it than something that would require more probing.
153      if (ThisBucket->first == TombstoneKey && !FoundTombstone)
154        FoundTombstone = ThisBucket;  // Remember the first tombstone found.
155
156      // Otherwise, it's a hash collision or a tombstone, continue quadratic
157      // probing.
158      BucketNo += ProbeAmt++;
159    }
160  }
161
162  void init(unsigned InitBuckets) {
163    NumEntries = 0;
164    NumBuckets = InitBuckets;
165    assert(InitBuckets && (InitBuckets & InitBuckets-1) == 0 &&
166           "# initial buckets must be a power of two!");
167    Buckets = (BucketT*)new char[sizeof(BucketT)*InitBuckets];
168    // Initialize all the keys to EmptyKey.
169    const KeyT EmptyKey = getEmptyKey();
170    for (unsigned i = 0; i != InitBuckets; ++i)
171      new (&Buckets[i].first) KeyT(EmptyKey);
172  }
173
174  void grow() {
175    unsigned OldNumBuckets = NumBuckets;
176    BucketT *OldBuckets = Buckets;
177
178    // Double the number of buckets.
179    NumBuckets <<= 1;
180    Buckets = (BucketT*)new char[sizeof(BucketT)*NumBuckets];
181
182    // Initialize all the keys to EmptyKey.
183    const KeyT EmptyKey = getEmptyKey();
184    for (unsigned i = 0, e = NumBuckets; i != e; ++i)
185      new (&Buckets[i].first) KeyT(EmptyKey);
186
187    // Insert all the old elements.
188    const KeyT TombstoneKey = getTombstoneKey();
189    for (BucketT *B = OldBuckets, *E = OldBuckets+OldNumBuckets; B != E; ++B) {
190      if (B->first != EmptyKey && B->first != TombstoneKey) {
191        // Insert the key/value into the new table.
192        BucketT *DestBucket;
193        bool FoundVal = LookupBucketFor(B->first, DestBucket);
194        assert(!FoundVal && "Key already in new map?");
195        DestBucket->first = B->first;
196        new (&DestBucket->second) ValueT(B->second);
197
198        // Free the value.
199        B->second.~ValueT();
200      }
201      B->first.~KeyT();
202    }
203
204    // Free the old table.
205    delete[] (char*)OldBuckets;
206  }
207};
208
209template<typename KeyT, typename ValueT>
210class DenseMapIterator {
211  typedef std::pair<KeyT, ValueT> BucketT;
212  const BucketT *Ptr, *End;
213public:
214  DenseMapIterator(const BucketT *Pos, const BucketT *E) : Ptr(Pos), End(E) {
215    AdvancePastEmptyBuckets();
216  }
217
218  const std::pair<KeyT, ValueT> &operator*() const {
219    return *Ptr;
220  }
221  const std::pair<KeyT, ValueT> *operator->() const {
222    return Ptr;
223  }
224
225  bool operator==(const DenseMapIterator &RHS) const {
226    return Ptr == RHS.Ptr;
227  }
228  bool operator!=(const DenseMapIterator &RHS) const {
229    return Ptr != RHS.Ptr;
230  }
231
232  inline DenseMapIterator& operator++() {          // Preincrement
233    ++Ptr;
234    AdvancePastEmptyBuckets();
235    return *this;
236  }
237  DenseMapIterator operator++(int) {        // Postincrement
238    DenseMapIterator tmp = *this; ++*this; return tmp;
239  }
240
241private:
242  void AdvancePastEmptyBuckets() {
243    const KeyT Empty = DenseMapKeyInfo<KeyT>::getEmptyKey();
244    const KeyT Tombstone = DenseMapKeyInfo<KeyT>::getTombstoneKey();
245
246    while (Ptr != End && Ptr->first != Empty && Ptr->first != Tombstone)
247      ++Ptr;
248  }
249};
250
251
252template<typename KeyT, typename ValueT>
253inline DenseMapIterator<KeyT, ValueT> DenseMap<KeyT, ValueT>::begin() const {
254  return DenseMapIterator<KeyT, ValueT>(Buckets, Buckets+NumBuckets);
255}
256template<typename KeyT, typename ValueT>
257inline DenseMapIterator<KeyT, ValueT> DenseMap<KeyT, ValueT>::end() const {
258  return DenseMapIterator<KeyT, ValueT>(Buckets+NumBuckets, Buckets+NumBuckets);
259}
260
261} // end namespace llvm
262
263#endif
264