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