DenseMap.h revision 6e94c00ab29e654125e845f3bce692a3764c1c11
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 20namespace llvm { 21 22template<typename T> 23struct DenseMapKeyInfo { 24 //static inline T getEmptyKey(); 25 //static inline T getTombstoneKey(); 26 //static unsigned getHashValue(const T &Val); 27 //static bool isPod() 28}; 29 30template<typename T> 31struct DenseMapKeyInfo<T*> { 32 static inline T* getEmptyKey() { return (T*)-1; } 33 static inline T* getTombstoneKey() { return (T*)-2; } 34 static unsigned getHashValue(const T *PtrVal) { 35 return (unsigned)((uintptr_t)PtrVal >> 4) ^ 36 (unsigned)((uintptr_t)PtrVal >> 9); 37 } 38 static bool isPod() { return true; } 39}; 40 41 42template<typename KeyT, typename ValueT> 43class DenseMap { 44 struct BucketT { KeyT Key; ValueT Value; }; 45 unsigned NumBuckets; 46 BucketT *Buckets; 47 48 unsigned NumEntries; 49 DenseMap(const DenseMap &); // not implemented. 50public: 51 explicit DenseMap(unsigned NumInitBuckets = 8) { 52 init(NumInitBuckets); 53 } 54 ~DenseMap() { 55 const KeyT EmptyKey = getEmptyKey(), TombstoneKey = getTombstoneKey(); 56 for (BucketT *P = Buckets, *E = Buckets+NumBuckets; P != E; ++P) { 57 if (P->Key != EmptyKey && P->Key != TombstoneKey) 58 P->Value.~ValueT(); 59 P->Key.~KeyT(); 60 } 61 delete[] (char*)Buckets; 62 } 63 64 unsigned size() const { return NumEntries; } 65 66 void clear() { 67 const KeyT EmptyKey = getEmptyKey(), TombstoneKey = getTombstoneKey(); 68 for (BucketT *P = Buckets, *E = Buckets+NumBuckets; P != E; ++P) { 69 if (P->Key != EmptyKey && P->Key != TombstoneKey) { 70 P->Key = EmptyKey; 71 P->Value.~ValueT(); 72 --NumEntries; 73 } 74 } 75 assert(NumEntries == 0 && "Node count imbalance!"); 76 } 77 78 /// count - Return true if the specified key is in the map. 79 bool count(const KeyT &Val) const { 80 BucketT *TheBucket; 81 return LookupBucketFor(Val, TheBucket); 82 } 83 84 ValueT &operator[](const KeyT &Val) { 85 BucketT *TheBucket; 86 if (LookupBucketFor(Val, TheBucket)) 87 return TheBucket->Value; 88 89 // If the load of the hash table is more than 3/4, grow it. 90 if (NumEntries*4 >= NumBuckets*3) { 91 this->grow(); 92 LookupBucketFor(Val, TheBucket); 93 } 94 ++NumEntries; 95 TheBucket->Key = Val; 96 new (&TheBucket->Value) ValueT(); 97 return TheBucket->Value; 98 } 99 100private: 101 unsigned getHashValue(const KeyT &Val) const { 102 return DenseMapKeyInfo<KeyT>::getHashValue(Val); 103 } 104 const KeyT getEmptyKey() const { return DenseMapKeyInfo<KeyT>::getEmptyKey();} 105 const KeyT getTombstoneKey() const { 106 return DenseMapKeyInfo<KeyT>::getTombstoneKey(); 107 } 108 109 /// LookupBucketFor - Lookup the appropriate bucket for Val, returning it in 110 /// FoundBucket. If the bucket contains the key and a value, this returns 111 /// true, otherwise it returns a bucket with an empty marker or tombstone and 112 /// returns false. 113 bool LookupBucketFor(const KeyT &Val, BucketT *&FoundBucket) const { 114 unsigned BucketNo = getHashValue(Val); 115 unsigned ProbeAmt = 1; 116 BucketT *BucketsPtr = Buckets; 117 118 // FoundTombstone - Keep track of whether we find a tombstone while probing. 119 BucketT *FoundTombstone = 0; 120 const KeyT EmptyKey = getEmptyKey(); 121 const KeyT TombstoneKey = getTombstoneKey(); 122 assert(Val != EmptyKey && Val != TombstoneKey && 123 "Empty/Tombstone value shouldn't be inserted into map!"); 124 125 while (1) { 126 BucketT *ThisBucket = BucketsPtr + (BucketNo & (NumBuckets-1)); 127 // Found Val's bucket? If so, return it. 128 if (ThisBucket->Key == Val) { 129 FoundBucket = ThisBucket; 130 return true; 131 } 132 133 // If we found an empty bucket, the key doesn't exist in the set. 134 // Insert it and return the default value. 135 if (ThisBucket->Key == EmptyKey) { 136 // If we've already seen a tombstone while probing, fill it in instead 137 // of the empty bucket we eventually probed to. 138 if (FoundTombstone) ThisBucket = FoundTombstone; 139 FoundBucket = FoundTombstone ? FoundTombstone : ThisBucket; 140 return false; 141 } 142 143 // If this is a tombstone, remember it. If Val ends up not in the map, we 144 // prefer to return it than something that would require more probing. 145 if (ThisBucket->Key == TombstoneKey && !FoundTombstone) 146 FoundTombstone = ThisBucket; // Remember the first tombstone found. 147 148 // Otherwise, it's a hash collision or a tombstone, continue quadratic 149 // probing. 150 BucketNo += ProbeAmt++; 151 } 152 } 153 154 void init(unsigned InitBuckets) { 155 NumEntries = 0; 156 NumBuckets = InitBuckets; 157 assert(InitBuckets && (InitBuckets & InitBuckets-1) == 0 && 158 "# initial buckets must be a power of two!"); 159 Buckets = (BucketT*)new char[sizeof(BucketT)*InitBuckets]; 160 // Initialize all the keys to EmptyKey. 161 const KeyT EmptyKey = getEmptyKey(); 162 for (unsigned i = 0; i != InitBuckets; ++i) 163 new (&Buckets[i].Key) KeyT(EmptyKey); 164 } 165 166 void grow() { 167 unsigned OldNumBuckets = NumBuckets; 168 BucketT *OldBuckets = Buckets; 169 170 // Double the number of buckets. 171 NumBuckets <<= 1; 172 Buckets = (BucketT*)new char[sizeof(BucketT)*NumBuckets]; 173 174 // Initialize all the keys to EmptyKey. 175 const KeyT EmptyKey = getEmptyKey(); 176 for (unsigned i = 0, e = NumBuckets; i != e; ++i) 177 new (&Buckets[i].Key) KeyT(EmptyKey); 178 179 // Insert all the old elements. 180 const KeyT TombstoneKey = getTombstoneKey(); 181 for (BucketT *B = OldBuckets, *E = OldBuckets+OldNumBuckets; B != E; ++B) { 182 if (B->Key != EmptyKey && B->Key != TombstoneKey) { 183 // Insert the key/value into the new table. 184 BucketT *DestBucket; 185 bool FoundVal = LookupBucketFor(B->Key, DestBucket); 186 assert(!FoundVal && "Key already in new map?"); 187 DestBucket->Key = B->Key; 188 new (&DestBucket->Value) ValueT(B->Value); 189 190 // Free the value. 191 B->Value.~ValueT(); 192 } 193 B->Key.~KeyT(); 194 } 195 196 // Free the old table. 197 delete[] (char*)OldBuckets; 198 } 199}; 200 201} // end namespace llvm 202 203#endif 204