DenseMap.h revision 48f4dcf0f7fd64df00839018d633944bc2464501
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/Compiler.h" 18#include "llvm/Support/MathExtras.h" 19#include "llvm/Support/PointerLikeTypeTraits.h" 20#include "llvm/Support/type_traits.h" 21#include "llvm/ADT/DenseMapInfo.h" 22#include <algorithm> 23#include <iterator> 24#include <new> 25#include <utility> 26#include <cassert> 27#include <cstddef> 28#include <cstring> 29 30namespace llvm { 31 32template<typename KeyT, typename ValueT, 33 typename KeyInfoT = DenseMapInfo<KeyT>, 34 bool IsConst = false> 35class DenseMapIterator; 36 37template<typename DerivedT, 38 typename KeyT, typename ValueT, typename KeyInfoT> 39class DenseMapBase { 40protected: 41 typedef std::pair<KeyT, ValueT> BucketT; 42 43public: 44 typedef KeyT key_type; 45 typedef ValueT mapped_type; 46 typedef BucketT value_type; 47 48 typedef DenseMapIterator<KeyT, ValueT, KeyInfoT> iterator; 49 typedef DenseMapIterator<KeyT, ValueT, 50 KeyInfoT, true> const_iterator; 51 inline iterator begin() { 52 // When the map is empty, avoid the overhead of AdvancePastEmptyBuckets(). 53 return empty() ? end() : iterator(getBuckets(), getBucketsEnd()); 54 } 55 inline iterator end() { 56 return iterator(getBucketsEnd(), getBucketsEnd(), true); 57 } 58 inline const_iterator begin() const { 59 return empty() ? end() : const_iterator(getBuckets(), getBucketsEnd()); 60 } 61 inline const_iterator end() const { 62 return const_iterator(getBucketsEnd(), getBucketsEnd(), true); 63 } 64 65 bool empty() const { return getNumEntries() == 0; } 66 unsigned size() const { return getNumEntries(); } 67 68 /// Grow the densemap so that it has at least Size buckets. Does not shrink 69 void resize(size_t Size) { 70 if (Size > getNumBuckets()) 71 grow(Size); 72 } 73 74 void clear() { 75 if (getNumEntries() == 0 && getNumTombstones() == 0) return; 76 77 // If the capacity of the array is huge, and the # elements used is small, 78 // shrink the array. 79 if (getNumEntries() * 4 < getNumBuckets() && getNumBuckets() > 64) { 80 shrink_and_clear(); 81 return; 82 } 83 84 const KeyT EmptyKey = getEmptyKey(), TombstoneKey = getTombstoneKey(); 85 for (BucketT *P = getBuckets(), *E = getBucketsEnd(); P != E; ++P) { 86 if (!KeyInfoT::isEqual(P->first, EmptyKey)) { 87 if (!KeyInfoT::isEqual(P->first, TombstoneKey)) { 88 P->second.~ValueT(); 89 decrementNumEntries(); 90 } 91 P->first = EmptyKey; 92 } 93 } 94 assert(getNumEntries() == 0 && "Node count imbalance!"); 95 setNumTombstones(0); 96 } 97 98 /// count - Return true if the specified key is in the map. 99 bool count(const KeyT &Val) const { 100 BucketT *TheBucket; 101 return LookupBucketFor(Val, TheBucket); 102 } 103 104 iterator find(const KeyT &Val) { 105 BucketT *TheBucket; 106 if (LookupBucketFor(Val, TheBucket)) 107 return iterator(TheBucket, getBucketsEnd(), true); 108 return end(); 109 } 110 const_iterator find(const KeyT &Val) const { 111 BucketT *TheBucket; 112 if (LookupBucketFor(Val, TheBucket)) 113 return const_iterator(TheBucket, getBucketsEnd(), true); 114 return end(); 115 } 116 117 /// Alternate version of find() which allows a different, and possibly 118 /// less expensive, key type. 119 /// The DenseMapInfo is responsible for supplying methods 120 /// getHashValue(LookupKeyT) and isEqual(LookupKeyT, KeyT) for each key 121 /// type used. 122 template<class LookupKeyT> 123 iterator find_as(const LookupKeyT &Val) { 124 BucketT *TheBucket; 125 if (LookupBucketFor(Val, TheBucket)) 126 return iterator(TheBucket, getBucketsEnd(), true); 127 return end(); 128 } 129 template<class LookupKeyT> 130 const_iterator find_as(const LookupKeyT &Val) const { 131 BucketT *TheBucket; 132 if (LookupBucketFor(Val, TheBucket)) 133 return const_iterator(TheBucket, getBucketsEnd(), true); 134 return end(); 135 } 136 137 /// lookup - Return the entry for the specified key, or a default 138 /// constructed value if no such entry exists. 139 ValueT lookup(const KeyT &Val) const { 140 BucketT *TheBucket; 141 if (LookupBucketFor(Val, TheBucket)) 142 return TheBucket->second; 143 return ValueT(); 144 } 145 146 // Inserts key,value pair into the map if the key isn't already in the map. 147 // If the key is already in the map, it returns false and doesn't update the 148 // value. 149 std::pair<iterator, bool> insert(const std::pair<KeyT, ValueT> &KV) { 150 BucketT *TheBucket; 151 if (LookupBucketFor(KV.first, TheBucket)) 152 return std::make_pair(iterator(TheBucket, getBucketsEnd(), true), 153 false); // Already in map. 154 155 // Otherwise, insert the new element. 156 TheBucket = InsertIntoBucket(KV.first, KV.second, TheBucket); 157 return std::make_pair(iterator(TheBucket, getBucketsEnd(), true), true); 158 } 159 160 /// insert - Range insertion of pairs. 161 template<typename InputIt> 162 void insert(InputIt I, InputIt E) { 163 for (; I != E; ++I) 164 insert(*I); 165 } 166 167 168 bool erase(const KeyT &Val) { 169 BucketT *TheBucket; 170 if (!LookupBucketFor(Val, TheBucket)) 171 return false; // not in map. 172 173 TheBucket->second.~ValueT(); 174 TheBucket->first = getTombstoneKey(); 175 decrementNumEntries(); 176 incrementNumTombstones(); 177 return true; 178 } 179 void erase(iterator I) { 180 BucketT *TheBucket = &*I; 181 TheBucket->second.~ValueT(); 182 TheBucket->first = getTombstoneKey(); 183 decrementNumEntries(); 184 incrementNumTombstones(); 185 } 186 187 value_type& FindAndConstruct(const KeyT &Key) { 188 BucketT *TheBucket; 189 if (LookupBucketFor(Key, TheBucket)) 190 return *TheBucket; 191 192 return *InsertIntoBucket(Key, ValueT(), TheBucket); 193 } 194 195 ValueT &operator[](const KeyT &Key) { 196 return FindAndConstruct(Key).second; 197 } 198 199#if LLVM_USE_RVALUE_REFERENCES 200 value_type& FindAndConstruct(KeyT &&Key) { 201 BucketT *TheBucket; 202 if (LookupBucketFor(Key, TheBucket)) 203 return *TheBucket; 204 205 return *InsertIntoBucket(Key, ValueT(), TheBucket); 206 } 207 208 ValueT &operator[](KeyT &&Key) { 209 return FindAndConstruct(Key).second; 210 } 211#endif 212 213 /// isPointerIntoBucketsArray - Return true if the specified pointer points 214 /// somewhere into the DenseMap's array of buckets (i.e. either to a key or 215 /// value in the DenseMap). 216 bool isPointerIntoBucketsArray(const void *Ptr) const { 217 return Ptr >= getBuckets() && Ptr < getBucketsEnd(); 218 } 219 220 /// getPointerIntoBucketsArray() - Return an opaque pointer into the buckets 221 /// array. In conjunction with the previous method, this can be used to 222 /// determine whether an insertion caused the DenseMap to reallocate. 223 const void *getPointerIntoBucketsArray() const { return getBuckets(); } 224 225protected: 226 DenseMapBase() {} 227 228 void destroyAll() { 229 if (getNumBuckets() == 0) // Nothing to do. 230 return; 231 232 const KeyT EmptyKey = getEmptyKey(), TombstoneKey = getTombstoneKey(); 233 for (BucketT *P = getBuckets(), *E = getBucketsEnd(); P != E; ++P) { 234 if (!KeyInfoT::isEqual(P->first, EmptyKey) && 235 !KeyInfoT::isEqual(P->first, TombstoneKey)) 236 P->second.~ValueT(); 237 P->first.~KeyT(); 238 } 239 240#ifndef NDEBUG 241 memset((void*)getBuckets(), 0x5a, sizeof(BucketT)*getNumBuckets()); 242#endif 243 } 244 245 void initEmpty() { 246 setNumEntries(0); 247 setNumTombstones(0); 248 249 assert((getNumBuckets() & (getNumBuckets()-1)) == 0 && 250 "# initial buckets must be a power of two!"); 251 const KeyT EmptyKey = getEmptyKey(); 252 for (BucketT *B = getBuckets(), *E = getBucketsEnd(); B != E; ++B) 253 new (&B->first) KeyT(EmptyKey); 254 } 255 256 void moveFromOldBuckets(BucketT *OldBucketsBegin, BucketT *OldBucketsEnd) { 257 initEmpty(); 258 259 // Insert all the old elements. 260 const KeyT EmptyKey = getEmptyKey(); 261 const KeyT TombstoneKey = getTombstoneKey(); 262 for (BucketT *B = OldBucketsBegin, *E = OldBucketsEnd; B != E; ++B) { 263 if (!KeyInfoT::isEqual(B->first, EmptyKey) && 264 !KeyInfoT::isEqual(B->first, TombstoneKey)) { 265 // Insert the key/value into the new table. 266 BucketT *DestBucket; 267 bool FoundVal = LookupBucketFor(B->first, DestBucket); 268 (void)FoundVal; // silence warning. 269 assert(!FoundVal && "Key already in new map?"); 270 DestBucket->first = llvm_move(B->first); 271 new (&DestBucket->second) ValueT(llvm_move(B->second)); 272 incrementNumEntries(); 273 274 // Free the value. 275 B->second.~ValueT(); 276 } 277 B->first.~KeyT(); 278 } 279 280#ifndef NDEBUG 281 if (OldBucketsBegin != OldBucketsEnd) 282 memset((void*)OldBucketsBegin, 0x5a, 283 sizeof(BucketT) * (OldBucketsEnd - OldBucketsBegin)); 284#endif 285 } 286 287 template <typename OtherBaseT> 288 void copyFrom(const DenseMapBase<OtherBaseT, KeyT, ValueT, KeyInfoT>& other) { 289 assert(getNumBuckets() == other.getNumBuckets()); 290 291 setNumEntries(other.getNumEntries()); 292 setNumTombstones(other.getNumTombstones()); 293 294 if (isPodLike<KeyT>::value && isPodLike<ValueT>::value) 295 memcpy(getBuckets(), other.getBuckets(), 296 getNumBuckets() * sizeof(BucketT)); 297 else 298 for (size_t i = 0; i < getNumBuckets(); ++i) { 299 new (&getBuckets()[i].first) KeyT(other.getBuckets()[i].first); 300 if (!KeyInfoT::isEqual(getBuckets()[i].first, getEmptyKey()) && 301 !KeyInfoT::isEqual(getBuckets()[i].first, getTombstoneKey())) 302 new (&getBuckets()[i].second) ValueT(other.getBuckets()[i].second); 303 } 304 } 305 306 void swap(DenseMapBase& RHS) { 307 std::swap(getNumEntries(), RHS.getNumEntries()); 308 std::swap(getNumTombstones(), RHS.getNumTombstones()); 309 } 310 311private: 312 static unsigned getHashValue(const KeyT &Val) { 313 return KeyInfoT::getHashValue(Val); 314 } 315 template<typename LookupKeyT> 316 static unsigned getHashValue(const LookupKeyT &Val) { 317 return KeyInfoT::getHashValue(Val); 318 } 319 static const KeyT getEmptyKey() { 320 return KeyInfoT::getEmptyKey(); 321 } 322 static const KeyT getTombstoneKey() { 323 return KeyInfoT::getTombstoneKey(); 324 } 325 326 unsigned getNumEntries() const { 327 return static_cast<const DerivedT *>(this)->getNumEntries(); 328 } 329 void setNumEntries(unsigned Num) { 330 static_cast<DerivedT *>(this)->setNumEntries(Num); 331 } 332 void incrementNumEntries() { 333 setNumEntries(getNumEntries() + 1); 334 } 335 void decrementNumEntries() { 336 setNumEntries(getNumEntries() - 1); 337 } 338 unsigned getNumTombstones() const { 339 return static_cast<const DerivedT *>(this)->getNumTombstones(); 340 } 341 void setNumTombstones(unsigned Num) { 342 static_cast<DerivedT *>(this)->setNumTombstones(Num); 343 } 344 void incrementNumTombstones() { 345 setNumTombstones(getNumTombstones() + 1); 346 } 347 void decrementNumTombstones() { 348 setNumTombstones(getNumTombstones() - 1); 349 } 350 BucketT *getBuckets() const { 351 return static_cast<const DerivedT *>(this)->getBuckets(); 352 } 353 unsigned getNumBuckets() const { 354 return static_cast<const DerivedT *>(this)->getNumBuckets(); 355 } 356 BucketT *getBucketsEnd() const { 357 return getBuckets() + getNumBuckets(); 358 } 359 360 void grow(unsigned AtLeast) { 361 static_cast<DerivedT *>(this)->grow(AtLeast); 362 } 363 364 void shrink_and_clear() { 365 static_cast<DerivedT *>(this)->shrink_and_clear(); 366 } 367 368 369 BucketT *InsertIntoBucket(const KeyT &Key, const ValueT &Value, 370 BucketT *TheBucket) { 371 TheBucket = InsertIntoBucketImpl(Key, TheBucket); 372 373 TheBucket->first = Key; 374 new (&TheBucket->second) ValueT(Value); 375 return TheBucket; 376 } 377 378#if LLVM_USE_RVALUE_REFERENCES 379 BucketT *InsertIntoBucket(const KeyT &Key, ValueT &&Value, 380 BucketT *TheBucket) { 381 TheBucket = InsertIntoBucketImpl(Key, TheBucket); 382 383 TheBucket->first = Key; 384 new (&TheBucket->second) ValueT(std::move(Value)); 385 return TheBucket; 386 } 387 388 BucketT *InsertIntoBucket(KeyT &&Key, ValueT &&Value, BucketT *TheBucket) { 389 TheBucket = InsertIntoBucketImpl(Key, TheBucket); 390 391 TheBucket->first = std::move(Key); 392 new (&TheBucket->second) ValueT(std::move(Value)); 393 return TheBucket; 394 } 395#endif 396 397 BucketT *InsertIntoBucketImpl(const KeyT &Key, BucketT *TheBucket) { 398 // If the load of the hash table is more than 3/4, or if fewer than 1/8 of 399 // the buckets are empty (meaning that many are filled with tombstones), 400 // grow the table. 401 // 402 // The later case is tricky. For example, if we had one empty bucket with 403 // tons of tombstones, failing lookups (e.g. for insertion) would have to 404 // probe almost the entire table until it found the empty bucket. If the 405 // table completely filled with tombstones, no lookup would ever succeed, 406 // causing infinite loops in lookup. 407 unsigned NewNumEntries = getNumEntries() + 1; 408 if (NewNumEntries*4 >= getNumBuckets()*3) { 409 this->grow(getNumBuckets() * 2); 410 LookupBucketFor(Key, TheBucket); 411 } 412 if (getNumBuckets()-(NewNumEntries+getNumTombstones()) < getNumBuckets()/8) { 413 this->grow(getNumBuckets()); 414 LookupBucketFor(Key, TheBucket); 415 } 416 417 // Only update the state after we've grown our bucket space appropriately 418 // so that when growing buckets we have self-consistent entry count. 419 incrementNumEntries(); 420 421 // If we are writing over a tombstone, remember this. 422 if (!KeyInfoT::isEqual(TheBucket->first, getEmptyKey())) 423 decrementNumTombstones(); 424 425 return TheBucket; 426 } 427 428 /// LookupBucketFor - Lookup the appropriate bucket for Val, returning it in 429 /// FoundBucket. If the bucket contains the key and a value, this returns 430 /// true, otherwise it returns a bucket with an empty marker or tombstone and 431 /// returns false. 432 template<typename LookupKeyT> 433 bool LookupBucketFor(const LookupKeyT &Val, BucketT *&FoundBucket) const { 434 unsigned BucketNo = getHashValue(Val); 435 unsigned ProbeAmt = 1; 436 BucketT *BucketsPtr = getBuckets(); 437 438 if (getNumBuckets() == 0) { 439 FoundBucket = 0; 440 return false; 441 } 442 443 // FoundTombstone - Keep track of whether we find a tombstone while probing. 444 BucketT *FoundTombstone = 0; 445 const KeyT EmptyKey = getEmptyKey(); 446 const KeyT TombstoneKey = getTombstoneKey(); 447 assert(!KeyInfoT::isEqual(Val, EmptyKey) && 448 !KeyInfoT::isEqual(Val, TombstoneKey) && 449 "Empty/Tombstone value shouldn't be inserted into map!"); 450 451 while (1) { 452 BucketT *ThisBucket = BucketsPtr + (BucketNo & (getNumBuckets()-1)); 453 // Found Val's bucket? If so, return it. 454 if (KeyInfoT::isEqual(Val, ThisBucket->first)) { 455 FoundBucket = ThisBucket; 456 return true; 457 } 458 459 // If we found an empty bucket, the key doesn't exist in the set. 460 // Insert it and return the default value. 461 if (KeyInfoT::isEqual(ThisBucket->first, EmptyKey)) { 462 // If we've already seen a tombstone while probing, fill it in instead 463 // of the empty bucket we eventually probed to. 464 if (FoundTombstone) ThisBucket = FoundTombstone; 465 FoundBucket = FoundTombstone ? FoundTombstone : ThisBucket; 466 return false; 467 } 468 469 // If this is a tombstone, remember it. If Val ends up not in the map, we 470 // prefer to return it than something that would require more probing. 471 if (KeyInfoT::isEqual(ThisBucket->first, TombstoneKey) && !FoundTombstone) 472 FoundTombstone = ThisBucket; // Remember the first tombstone found. 473 474 // Otherwise, it's a hash collision or a tombstone, continue quadratic 475 // probing. 476 BucketNo += ProbeAmt++; 477 } 478 } 479 480public: 481 /// Return the approximate size (in bytes) of the actual map. 482 /// This is just the raw memory used by DenseMap. 483 /// If entries are pointers to objects, the size of the referenced objects 484 /// are not included. 485 size_t getMemorySize() const { 486 return getNumBuckets() * sizeof(BucketT); 487 } 488}; 489 490template<typename KeyT, typename ValueT, 491 typename KeyInfoT = DenseMapInfo<KeyT> > 492class DenseMap 493 : public DenseMapBase<DenseMap<KeyT, ValueT, KeyInfoT>, 494 KeyT, ValueT, KeyInfoT> { 495 // Lift some types from the dependent base class into this class for 496 // simplicity of referring to them. 497 typedef DenseMapBase<DenseMap, KeyT, ValueT, KeyInfoT> BaseT; 498 typedef typename BaseT::BucketT BucketT; 499 friend class DenseMapBase<DenseMap, KeyT, ValueT, KeyInfoT>; 500 501 BucketT *Buckets; 502 unsigned NumEntries; 503 unsigned NumTombstones; 504 unsigned NumBuckets; 505 506public: 507 explicit DenseMap(unsigned NumInitBuckets = 0) { 508 init(NumInitBuckets); 509 } 510 511 DenseMap(const DenseMap &other) { 512 init(0); 513 copyFrom(other); 514 } 515 516#if LLVM_USE_RVALUE_REFERENCES 517 DenseMap(DenseMap &&other) { 518 init(0); 519 swap(other); 520 } 521#endif 522 523 template<typename InputIt> 524 DenseMap(const InputIt &I, const InputIt &E) { 525 init(NextPowerOf2(std::distance(I, E))); 526 this->insert(I, E); 527 } 528 529 ~DenseMap() { 530 this->destroyAll(); 531 operator delete(Buckets); 532 } 533 534 void swap(DenseMap& RHS) { 535 std::swap(Buckets, RHS.Buckets); 536 std::swap(NumEntries, RHS.NumEntries); 537 std::swap(NumTombstones, RHS.NumTombstones); 538 std::swap(NumBuckets, RHS.NumBuckets); 539 } 540 541 DenseMap& operator=(const DenseMap& other) { 542 copyFrom(other); 543 return *this; 544 } 545 546#if LLVM_USE_RVALUE_REFERENCES 547 DenseMap& operator=(DenseMap &&other) { 548 this->destroyAll(); 549 operator delete(Buckets); 550 init(0); 551 swap(other); 552 return *this; 553 } 554#endif 555 556 void copyFrom(const DenseMap& other) { 557 this->destroyAll(); 558 operator delete(Buckets); 559 if (allocateBuckets(other.NumBuckets)) { 560 this->BaseT::copyFrom(other); 561 } else { 562 NumEntries = 0; 563 NumTombstones = 0; 564 } 565 } 566 567 void init(unsigned InitBuckets) { 568 if (allocateBuckets(InitBuckets)) { 569 this->BaseT::initEmpty(); 570 } else { 571 NumEntries = 0; 572 NumTombstones = 0; 573 } 574 } 575 576 void grow(unsigned AtLeast) { 577 unsigned OldNumBuckets = NumBuckets; 578 BucketT *OldBuckets = Buckets; 579 580 allocateBuckets(std::max<unsigned>(64, NextPowerOf2(AtLeast))); 581 assert(Buckets); 582 if (!OldBuckets) { 583 this->BaseT::initEmpty(); 584 return; 585 } 586 587 this->moveFromOldBuckets(OldBuckets, OldBuckets+OldNumBuckets); 588 589 // Free the old table. 590 operator delete(OldBuckets); 591 } 592 593 void shrink_and_clear() { 594 unsigned OldNumEntries = NumEntries; 595 this->destroyAll(); 596 597 // Reduce the number of buckets. 598 unsigned NewNumBuckets 599 = std::max(64, 1 << (Log2_32_Ceil(OldNumEntries) + 1)); 600 if (NewNumBuckets == NumBuckets) { 601 this->BaseT::initEmpty(); 602 return; 603 } 604 605 operator delete(Buckets); 606 init(NewNumBuckets); 607 } 608 609private: 610 unsigned getNumEntries() const { 611 return NumEntries; 612 } 613 void setNumEntries(unsigned Num) { 614 NumEntries = Num; 615 } 616 617 unsigned getNumTombstones() const { 618 return NumTombstones; 619 } 620 void setNumTombstones(unsigned Num) { 621 NumTombstones = Num; 622 } 623 624 BucketT *getBuckets() const { 625 return Buckets; 626 } 627 628 unsigned getNumBuckets() const { 629 return NumBuckets; 630 } 631 632 bool allocateBuckets(unsigned Num) { 633 NumBuckets = Num; 634 if (NumBuckets == 0) { 635 Buckets = 0; 636 return false; 637 } 638 639 Buckets = static_cast<BucketT*>(operator new(sizeof(BucketT) * NumBuckets)); 640 return true; 641 } 642}; 643 644template<typename KeyT, typename ValueT, 645 typename KeyInfoT, bool IsConst> 646class DenseMapIterator { 647 typedef std::pair<KeyT, ValueT> Bucket; 648 typedef DenseMapIterator<KeyT, ValueT, 649 KeyInfoT, true> ConstIterator; 650 friend class DenseMapIterator<KeyT, ValueT, KeyInfoT, true>; 651public: 652 typedef ptrdiff_t difference_type; 653 typedef typename conditional<IsConst, const Bucket, Bucket>::type value_type; 654 typedef value_type *pointer; 655 typedef value_type &reference; 656 typedef std::forward_iterator_tag iterator_category; 657private: 658 pointer Ptr, End; 659public: 660 DenseMapIterator() : Ptr(0), End(0) {} 661 662 DenseMapIterator(pointer Pos, pointer E, bool NoAdvance = false) 663 : Ptr(Pos), End(E) { 664 if (!NoAdvance) AdvancePastEmptyBuckets(); 665 } 666 667 // If IsConst is true this is a converting constructor from iterator to 668 // const_iterator and the default copy constructor is used. 669 // Otherwise this is a copy constructor for iterator. 670 DenseMapIterator(const DenseMapIterator<KeyT, ValueT, 671 KeyInfoT, false>& I) 672 : Ptr(I.Ptr), End(I.End) {} 673 674 reference operator*() const { 675 return *Ptr; 676 } 677 pointer operator->() const { 678 return Ptr; 679 } 680 681 bool operator==(const ConstIterator &RHS) const { 682 return Ptr == RHS.operator->(); 683 } 684 bool operator!=(const ConstIterator &RHS) const { 685 return Ptr != RHS.operator->(); 686 } 687 688 inline DenseMapIterator& operator++() { // Preincrement 689 ++Ptr; 690 AdvancePastEmptyBuckets(); 691 return *this; 692 } 693 DenseMapIterator operator++(int) { // Postincrement 694 DenseMapIterator tmp = *this; ++*this; return tmp; 695 } 696 697private: 698 void AdvancePastEmptyBuckets() { 699 const KeyT Empty = KeyInfoT::getEmptyKey(); 700 const KeyT Tombstone = KeyInfoT::getTombstoneKey(); 701 702 while (Ptr != End && 703 (KeyInfoT::isEqual(Ptr->first, Empty) || 704 KeyInfoT::isEqual(Ptr->first, Tombstone))) 705 ++Ptr; 706 } 707}; 708 709template<typename KeyT, typename ValueT, typename KeyInfoT> 710static inline size_t 711capacity_in_bytes(const DenseMap<KeyT, ValueT, KeyInfoT> &X) { 712 return X.getMemorySize(); 713} 714 715} // end namespace llvm 716 717#endif 718