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