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