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