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