DenseMap.h revision 198090
1193323Sed//===- llvm/ADT/DenseMap.h - Dense probed hash table ------------*- C++ -*-===// 2193323Sed// 3193323Sed// The LLVM Compiler Infrastructure 4193323Sed// 5193323Sed// This file is distributed under the University of Illinois Open Source 6193323Sed// License. See LICENSE.TXT for details. 7193323Sed// 8193323Sed//===----------------------------------------------------------------------===// 9193323Sed// 10193323Sed// This file defines the DenseMap class. 11193323Sed// 12193323Sed//===----------------------------------------------------------------------===// 13193323Sed 14193323Sed#ifndef LLVM_ADT_DENSEMAP_H 15193323Sed#define LLVM_ADT_DENSEMAP_H 16193323Sed 17193323Sed#include "llvm/Support/PointerLikeTypeTraits.h" 18193323Sed#include "llvm/Support/MathExtras.h" 19198090Srdivacky#include "llvm/ADT/DenseMapInfo.h" 20198090Srdivacky#include <iterator> 21198090Srdivacky#include <new> 22198090Srdivacky#include <utility> 23193323Sed#include <cassert> 24198090Srdivacky#include <cstring> 25193323Sed 26193323Sednamespace llvm { 27193323Sed 28193323Sedtemplate<typename KeyT, typename ValueT, 29193323Sed typename KeyInfoT = DenseMapInfo<KeyT>, 30193323Sed typename ValueInfoT = DenseMapInfo<ValueT> > 31193323Sedclass DenseMapIterator; 32193323Sedtemplate<typename KeyT, typename ValueT, 33193323Sed typename KeyInfoT = DenseMapInfo<KeyT>, 34193323Sed typename ValueInfoT = DenseMapInfo<ValueT> > 35193323Sedclass DenseMapConstIterator; 36193323Sed 37193323Sedtemplate<typename KeyT, typename ValueT, 38193323Sed typename KeyInfoT = DenseMapInfo<KeyT>, 39193323Sed typename ValueInfoT = DenseMapInfo<ValueT> > 40193323Sedclass DenseMap { 41193323Sed typedef std::pair<KeyT, ValueT> BucketT; 42193323Sed unsigned NumBuckets; 43193323Sed BucketT *Buckets; 44193323Sed 45193323Sed unsigned NumEntries; 46193323Sed unsigned NumTombstones; 47193323Sedpublic: 48193323Sed typedef KeyT key_type; 49193323Sed typedef ValueT mapped_type; 50193323Sed typedef BucketT value_type; 51193323Sed 52193323Sed DenseMap(const DenseMap& other) { 53193323Sed NumBuckets = 0; 54193323Sed CopyFrom(other); 55193323Sed } 56193323Sed 57193323Sed explicit DenseMap(unsigned NumInitBuckets = 64) { 58193323Sed init(NumInitBuckets); 59193323Sed } 60193323Sed 61193323Sed ~DenseMap() { 62193323Sed const KeyT EmptyKey = getEmptyKey(), TombstoneKey = getTombstoneKey(); 63193323Sed for (BucketT *P = Buckets, *E = Buckets+NumBuckets; P != E; ++P) { 64193323Sed if (!KeyInfoT::isEqual(P->first, EmptyKey) && 65193323Sed !KeyInfoT::isEqual(P->first, TombstoneKey)) 66193323Sed P->second.~ValueT(); 67193323Sed P->first.~KeyT(); 68193323Sed } 69198090Srdivacky#ifndef NDEBUG 70198090Srdivacky memset(Buckets, 0x5a, sizeof(BucketT)*NumBuckets); 71198090Srdivacky#endif 72193323Sed operator delete(Buckets); 73193323Sed } 74193323Sed 75193323Sed typedef DenseMapIterator<KeyT, ValueT, KeyInfoT> iterator; 76193323Sed typedef DenseMapConstIterator<KeyT, ValueT, KeyInfoT> const_iterator; 77193323Sed inline iterator begin() { 78193323Sed return iterator(Buckets, Buckets+NumBuckets); 79193323Sed } 80193323Sed inline iterator end() { 81193323Sed return iterator(Buckets+NumBuckets, Buckets+NumBuckets); 82193323Sed } 83193323Sed inline const_iterator begin() const { 84193323Sed return const_iterator(Buckets, Buckets+NumBuckets); 85193323Sed } 86193323Sed inline const_iterator end() const { 87193323Sed return const_iterator(Buckets+NumBuckets, Buckets+NumBuckets); 88193323Sed } 89193323Sed 90193323Sed bool empty() const { return NumEntries == 0; } 91193323Sed unsigned size() const { return NumEntries; } 92193323Sed 93193323Sed /// Grow the densemap so that it has at least Size buckets. Does not shrink 94193323Sed void resize(size_t Size) { grow(Size); } 95193323Sed 96193323Sed void clear() { 97198090Srdivacky if (NumEntries == 0 && NumTombstones == 0) return; 98198090Srdivacky 99193323Sed // If the capacity of the array is huge, and the # elements used is small, 100193323Sed // shrink the array. 101193323Sed if (NumEntries * 4 < NumBuckets && NumBuckets > 64) { 102193323Sed shrink_and_clear(); 103193323Sed return; 104193323Sed } 105193323Sed 106193323Sed const KeyT EmptyKey = getEmptyKey(), TombstoneKey = getTombstoneKey(); 107193323Sed for (BucketT *P = Buckets, *E = Buckets+NumBuckets; P != E; ++P) { 108193323Sed if (!KeyInfoT::isEqual(P->first, EmptyKey)) { 109193323Sed if (!KeyInfoT::isEqual(P->first, TombstoneKey)) { 110193323Sed P->second.~ValueT(); 111193323Sed --NumEntries; 112193323Sed } 113193323Sed P->first = EmptyKey; 114193323Sed } 115193323Sed } 116193323Sed assert(NumEntries == 0 && "Node count imbalance!"); 117193323Sed NumTombstones = 0; 118193323Sed } 119193323Sed 120193323Sed /// count - Return true if the specified key is in the map. 121193323Sed bool count(const KeyT &Val) const { 122193323Sed BucketT *TheBucket; 123193323Sed return LookupBucketFor(Val, TheBucket); 124193323Sed } 125193323Sed 126193323Sed iterator find(const KeyT &Val) { 127193323Sed BucketT *TheBucket; 128193323Sed if (LookupBucketFor(Val, TheBucket)) 129193323Sed return iterator(TheBucket, Buckets+NumBuckets); 130193323Sed return end(); 131193323Sed } 132193323Sed const_iterator find(const KeyT &Val) const { 133193323Sed BucketT *TheBucket; 134193323Sed if (LookupBucketFor(Val, TheBucket)) 135193323Sed return const_iterator(TheBucket, Buckets+NumBuckets); 136193323Sed return end(); 137193323Sed } 138193323Sed 139193323Sed /// lookup - Return the entry for the specified key, or a default 140193323Sed /// constructed value if no such entry exists. 141193323Sed ValueT lookup(const KeyT &Val) const { 142193323Sed BucketT *TheBucket; 143193323Sed if (LookupBucketFor(Val, TheBucket)) 144193323Sed return TheBucket->second; 145193323Sed return ValueT(); 146193323Sed } 147193323Sed 148198090Srdivacky // Inserts key,value pair into the map if the key isn't already in the map. 149198090Srdivacky // If the key is already in the map, it returns false and doesn't update the 150198090Srdivacky // value. 151193323Sed std::pair<iterator, bool> insert(const std::pair<KeyT, ValueT> &KV) { 152193323Sed BucketT *TheBucket; 153193323Sed if (LookupBucketFor(KV.first, TheBucket)) 154193323Sed return std::make_pair(iterator(TheBucket, Buckets+NumBuckets), 155193323Sed false); // Already in map. 156193323Sed 157193323Sed // Otherwise, insert the new element. 158193323Sed TheBucket = InsertIntoBucket(KV.first, KV.second, TheBucket); 159193323Sed return std::make_pair(iterator(TheBucket, Buckets+NumBuckets), 160193323Sed true); 161193323Sed } 162193323Sed 163193323Sed /// insert - Range insertion of pairs. 164193323Sed template<typename InputIt> 165193323Sed void insert(InputIt I, InputIt E) { 166193323Sed for (; I != E; ++I) 167193323Sed insert(*I); 168193323Sed } 169193323Sed 170193323Sed 171193323Sed bool erase(const KeyT &Val) { 172193323Sed BucketT *TheBucket; 173193323Sed if (!LookupBucketFor(Val, TheBucket)) 174193323Sed return false; // not in map. 175193323Sed 176193323Sed TheBucket->second.~ValueT(); 177193323Sed TheBucket->first = getTombstoneKey(); 178193323Sed --NumEntries; 179193323Sed ++NumTombstones; 180193323Sed return true; 181193323Sed } 182193323Sed bool erase(iterator I) { 183193323Sed BucketT *TheBucket = &*I; 184193323Sed TheBucket->second.~ValueT(); 185193323Sed TheBucket->first = getTombstoneKey(); 186193323Sed --NumEntries; 187193323Sed ++NumTombstones; 188193323Sed return true; 189193323Sed } 190193323Sed 191193323Sed value_type& FindAndConstruct(const KeyT &Key) { 192193323Sed BucketT *TheBucket; 193193323Sed if (LookupBucketFor(Key, TheBucket)) 194193323Sed return *TheBucket; 195193323Sed 196193323Sed return *InsertIntoBucket(Key, ValueT(), TheBucket); 197193323Sed } 198193323Sed 199193323Sed ValueT &operator[](const KeyT &Key) { 200193323Sed return FindAndConstruct(Key).second; 201193323Sed } 202193323Sed 203193323Sed DenseMap& operator=(const DenseMap& other) { 204193323Sed CopyFrom(other); 205193323Sed return *this; 206193323Sed } 207193323Sed 208193323Sed /// isPointerIntoBucketsArray - Return true if the specified pointer points 209193323Sed /// somewhere into the DenseMap's array of buckets (i.e. either to a key or 210193323Sed /// value in the DenseMap). 211193323Sed bool isPointerIntoBucketsArray(const void *Ptr) const { 212193323Sed return Ptr >= Buckets && Ptr < Buckets+NumBuckets; 213193323Sed } 214193323Sed 215193323Sed /// getPointerIntoBucketsArray() - Return an opaque pointer into the buckets 216193323Sed /// array. In conjunction with the previous method, this can be used to 217193323Sed /// determine whether an insertion caused the DenseMap to reallocate. 218193323Sed const void *getPointerIntoBucketsArray() const { return Buckets; } 219193323Sed 220193323Sedprivate: 221193323Sed void CopyFrom(const DenseMap& other) { 222193323Sed if (NumBuckets != 0 && (!KeyInfoT::isPod() || !ValueInfoT::isPod())) { 223193323Sed const KeyT EmptyKey = getEmptyKey(), TombstoneKey = getTombstoneKey(); 224193323Sed for (BucketT *P = Buckets, *E = Buckets+NumBuckets; P != E; ++P) { 225193323Sed if (!KeyInfoT::isEqual(P->first, EmptyKey) && 226193323Sed !KeyInfoT::isEqual(P->first, TombstoneKey)) 227193323Sed P->second.~ValueT(); 228193323Sed P->first.~KeyT(); 229193323Sed } 230193323Sed } 231193323Sed 232193323Sed NumEntries = other.NumEntries; 233193323Sed NumTombstones = other.NumTombstones; 234193323Sed 235198090Srdivacky if (NumBuckets) { 236198090Srdivacky#ifndef NDEBUG 237198090Srdivacky memset(Buckets, 0x5a, sizeof(BucketT)*NumBuckets); 238198090Srdivacky#endif 239193323Sed operator delete(Buckets); 240198090Srdivacky } 241193323Sed Buckets = static_cast<BucketT*>(operator new(sizeof(BucketT) * 242193323Sed other.NumBuckets)); 243193323Sed 244193323Sed if (KeyInfoT::isPod() && ValueInfoT::isPod()) 245193323Sed memcpy(Buckets, other.Buckets, other.NumBuckets * sizeof(BucketT)); 246193323Sed else 247193323Sed for (size_t i = 0; i < other.NumBuckets; ++i) { 248193323Sed new (&Buckets[i].first) KeyT(other.Buckets[i].first); 249193323Sed if (!KeyInfoT::isEqual(Buckets[i].first, getEmptyKey()) && 250193323Sed !KeyInfoT::isEqual(Buckets[i].first, getTombstoneKey())) 251193323Sed new (&Buckets[i].second) ValueT(other.Buckets[i].second); 252193323Sed } 253193323Sed NumBuckets = other.NumBuckets; 254193323Sed } 255193323Sed 256193323Sed BucketT *InsertIntoBucket(const KeyT &Key, const ValueT &Value, 257193323Sed BucketT *TheBucket) { 258193323Sed // If the load of the hash table is more than 3/4, or if fewer than 1/8 of 259193323Sed // the buckets are empty (meaning that many are filled with tombstones), 260193323Sed // grow the table. 261193323Sed // 262193323Sed // The later case is tricky. For example, if we had one empty bucket with 263193323Sed // tons of tombstones, failing lookups (e.g. for insertion) would have to 264193323Sed // probe almost the entire table until it found the empty bucket. If the 265193323Sed // table completely filled with tombstones, no lookup would ever succeed, 266193323Sed // causing infinite loops in lookup. 267193323Sed ++NumEntries; 268193323Sed if (NumEntries*4 >= NumBuckets*3 || 269193323Sed NumBuckets-(NumEntries+NumTombstones) < NumBuckets/8) { 270193323Sed this->grow(NumBuckets * 2); 271193323Sed LookupBucketFor(Key, TheBucket); 272193323Sed } 273193323Sed 274193323Sed // If we are writing over a tombstone, remember this. 275193323Sed if (!KeyInfoT::isEqual(TheBucket->first, getEmptyKey())) 276193323Sed --NumTombstones; 277193323Sed 278193323Sed TheBucket->first = Key; 279193323Sed new (&TheBucket->second) ValueT(Value); 280193323Sed return TheBucket; 281193323Sed } 282193323Sed 283193323Sed static unsigned getHashValue(const KeyT &Val) { 284193323Sed return KeyInfoT::getHashValue(Val); 285193323Sed } 286193323Sed static const KeyT getEmptyKey() { 287193323Sed return KeyInfoT::getEmptyKey(); 288193323Sed } 289193323Sed static const KeyT getTombstoneKey() { 290193323Sed return KeyInfoT::getTombstoneKey(); 291193323Sed } 292193323Sed 293193323Sed /// LookupBucketFor - Lookup the appropriate bucket for Val, returning it in 294193323Sed /// FoundBucket. If the bucket contains the key and a value, this returns 295193323Sed /// true, otherwise it returns a bucket with an empty marker or tombstone and 296193323Sed /// returns false. 297193323Sed bool LookupBucketFor(const KeyT &Val, BucketT *&FoundBucket) const { 298193323Sed unsigned BucketNo = getHashValue(Val); 299193323Sed unsigned ProbeAmt = 1; 300193323Sed BucketT *BucketsPtr = Buckets; 301193323Sed 302193323Sed // FoundTombstone - Keep track of whether we find a tombstone while probing. 303193323Sed BucketT *FoundTombstone = 0; 304193323Sed const KeyT EmptyKey = getEmptyKey(); 305193323Sed const KeyT TombstoneKey = getTombstoneKey(); 306193323Sed assert(!KeyInfoT::isEqual(Val, EmptyKey) && 307193323Sed !KeyInfoT::isEqual(Val, TombstoneKey) && 308193323Sed "Empty/Tombstone value shouldn't be inserted into map!"); 309193323Sed 310193323Sed while (1) { 311193323Sed BucketT *ThisBucket = BucketsPtr + (BucketNo & (NumBuckets-1)); 312193323Sed // Found Val's bucket? If so, return it. 313193323Sed if (KeyInfoT::isEqual(ThisBucket->first, Val)) { 314193323Sed FoundBucket = ThisBucket; 315193323Sed return true; 316193323Sed } 317193323Sed 318193323Sed // If we found an empty bucket, the key doesn't exist in the set. 319193323Sed // Insert it and return the default value. 320193323Sed if (KeyInfoT::isEqual(ThisBucket->first, EmptyKey)) { 321193323Sed // If we've already seen a tombstone while probing, fill it in instead 322193323Sed // of the empty bucket we eventually probed to. 323193323Sed if (FoundTombstone) ThisBucket = FoundTombstone; 324193323Sed FoundBucket = FoundTombstone ? FoundTombstone : ThisBucket; 325193323Sed return false; 326193323Sed } 327193323Sed 328193323Sed // If this is a tombstone, remember it. If Val ends up not in the map, we 329193323Sed // prefer to return it than something that would require more probing. 330193323Sed if (KeyInfoT::isEqual(ThisBucket->first, TombstoneKey) && !FoundTombstone) 331193323Sed FoundTombstone = ThisBucket; // Remember the first tombstone found. 332193323Sed 333193323Sed // Otherwise, it's a hash collision or a tombstone, continue quadratic 334193323Sed // probing. 335193323Sed BucketNo += ProbeAmt++; 336193323Sed } 337193323Sed } 338193323Sed 339193323Sed void init(unsigned InitBuckets) { 340193323Sed NumEntries = 0; 341193323Sed NumTombstones = 0; 342193323Sed NumBuckets = InitBuckets; 343193323Sed assert(InitBuckets && (InitBuckets & (InitBuckets-1)) == 0 && 344193323Sed "# initial buckets must be a power of two!"); 345193323Sed Buckets = static_cast<BucketT*>(operator new(sizeof(BucketT)*InitBuckets)); 346193323Sed // Initialize all the keys to EmptyKey. 347193323Sed const KeyT EmptyKey = getEmptyKey(); 348193323Sed for (unsigned i = 0; i != InitBuckets; ++i) 349193323Sed new (&Buckets[i].first) KeyT(EmptyKey); 350193323Sed } 351193323Sed 352193323Sed void grow(unsigned AtLeast) { 353193323Sed unsigned OldNumBuckets = NumBuckets; 354193323Sed BucketT *OldBuckets = Buckets; 355193323Sed 356193323Sed // Double the number of buckets. 357193323Sed while (NumBuckets <= AtLeast) 358193323Sed NumBuckets <<= 1; 359193323Sed NumTombstones = 0; 360193323Sed Buckets = static_cast<BucketT*>(operator new(sizeof(BucketT)*NumBuckets)); 361193323Sed 362193323Sed // Initialize all the keys to EmptyKey. 363193323Sed const KeyT EmptyKey = getEmptyKey(); 364193323Sed for (unsigned i = 0, e = NumBuckets; i != e; ++i) 365193323Sed new (&Buckets[i].first) KeyT(EmptyKey); 366193323Sed 367193323Sed // Insert all the old elements. 368193323Sed const KeyT TombstoneKey = getTombstoneKey(); 369193323Sed for (BucketT *B = OldBuckets, *E = OldBuckets+OldNumBuckets; B != E; ++B) { 370193323Sed if (!KeyInfoT::isEqual(B->first, EmptyKey) && 371193323Sed !KeyInfoT::isEqual(B->first, TombstoneKey)) { 372193323Sed // Insert the key/value into the new table. 373193323Sed BucketT *DestBucket; 374193323Sed bool FoundVal = LookupBucketFor(B->first, DestBucket); 375193323Sed FoundVal = FoundVal; // silence warning. 376193323Sed assert(!FoundVal && "Key already in new map?"); 377193323Sed DestBucket->first = B->first; 378193323Sed new (&DestBucket->second) ValueT(B->second); 379193323Sed 380193323Sed // Free the value. 381193323Sed B->second.~ValueT(); 382193323Sed } 383193323Sed B->first.~KeyT(); 384193323Sed } 385193323Sed 386198090Srdivacky#ifndef NDEBUG 387198090Srdivacky memset(OldBuckets, 0x5a, sizeof(BucketT)*OldNumBuckets); 388198090Srdivacky#endif 389193323Sed // Free the old table. 390193323Sed operator delete(OldBuckets); 391193323Sed } 392193323Sed 393193323Sed void shrink_and_clear() { 394193323Sed unsigned OldNumBuckets = NumBuckets; 395193323Sed BucketT *OldBuckets = Buckets; 396193323Sed 397193323Sed // Reduce the number of buckets. 398193323Sed NumBuckets = NumEntries > 32 ? 1 << (Log2_32_Ceil(NumEntries) + 1) 399193323Sed : 64; 400193323Sed NumTombstones = 0; 401193323Sed Buckets = static_cast<BucketT*>(operator new(sizeof(BucketT)*NumBuckets)); 402193323Sed 403193323Sed // Initialize all the keys to EmptyKey. 404193323Sed const KeyT EmptyKey = getEmptyKey(); 405193323Sed for (unsigned i = 0, e = NumBuckets; i != e; ++i) 406193323Sed new (&Buckets[i].first) KeyT(EmptyKey); 407193323Sed 408193323Sed // Free the old buckets. 409193323Sed const KeyT TombstoneKey = getTombstoneKey(); 410193323Sed for (BucketT *B = OldBuckets, *E = OldBuckets+OldNumBuckets; B != E; ++B) { 411193323Sed if (!KeyInfoT::isEqual(B->first, EmptyKey) && 412193323Sed !KeyInfoT::isEqual(B->first, TombstoneKey)) { 413193323Sed // Free the value. 414193323Sed B->second.~ValueT(); 415193323Sed } 416193323Sed B->first.~KeyT(); 417193323Sed } 418193323Sed 419198090Srdivacky#ifndef NDEBUG 420198090Srdivacky memset(OldBuckets, 0x5a, sizeof(BucketT)*OldNumBuckets); 421198090Srdivacky#endif 422193323Sed // Free the old table. 423193323Sed operator delete(OldBuckets); 424193323Sed 425193323Sed NumEntries = 0; 426193323Sed } 427193323Sed}; 428193323Sed 429193323Sedtemplate<typename KeyT, typename ValueT, typename KeyInfoT, typename ValueInfoT> 430198090Srdivackyclass DenseMapIterator : 431198090Srdivacky public std::iterator<std::forward_iterator_tag, std::pair<KeyT, ValueT>, 432198090Srdivacky ptrdiff_t> { 433193323Sed typedef std::pair<KeyT, ValueT> BucketT; 434193323Sedprotected: 435193323Sed const BucketT *Ptr, *End; 436193323Sedpublic: 437198090Srdivacky DenseMapIterator() : Ptr(0), End(0) {} 438193323Sed 439193323Sed DenseMapIterator(const BucketT *Pos, const BucketT *E) : Ptr(Pos), End(E) { 440193323Sed AdvancePastEmptyBuckets(); 441193323Sed } 442193323Sed 443193323Sed std::pair<KeyT, ValueT> &operator*() const { 444193323Sed return *const_cast<BucketT*>(Ptr); 445193323Sed } 446193323Sed std::pair<KeyT, ValueT> *operator->() const { 447193323Sed return const_cast<BucketT*>(Ptr); 448193323Sed } 449193323Sed 450193323Sed bool operator==(const DenseMapIterator &RHS) const { 451193323Sed return Ptr == RHS.Ptr; 452193323Sed } 453193323Sed bool operator!=(const DenseMapIterator &RHS) const { 454193323Sed return Ptr != RHS.Ptr; 455193323Sed } 456193323Sed 457193323Sed inline DenseMapIterator& operator++() { // Preincrement 458193323Sed ++Ptr; 459193323Sed AdvancePastEmptyBuckets(); 460193323Sed return *this; 461193323Sed } 462193323Sed DenseMapIterator operator++(int) { // Postincrement 463193323Sed DenseMapIterator tmp = *this; ++*this; return tmp; 464193323Sed } 465193323Sed 466193323Sedprivate: 467193323Sed void AdvancePastEmptyBuckets() { 468193323Sed const KeyT Empty = KeyInfoT::getEmptyKey(); 469193323Sed const KeyT Tombstone = KeyInfoT::getTombstoneKey(); 470193323Sed 471193323Sed while (Ptr != End && 472193323Sed (KeyInfoT::isEqual(Ptr->first, Empty) || 473193323Sed KeyInfoT::isEqual(Ptr->first, Tombstone))) 474193323Sed ++Ptr; 475193323Sed } 476193323Sed}; 477193323Sed 478193323Sedtemplate<typename KeyT, typename ValueT, typename KeyInfoT, typename ValueInfoT> 479193323Sedclass DenseMapConstIterator : public DenseMapIterator<KeyT, ValueT, KeyInfoT> { 480193323Sedpublic: 481198090Srdivacky DenseMapConstIterator() : DenseMapIterator<KeyT, ValueT, KeyInfoT>() {} 482193323Sed DenseMapConstIterator(const std::pair<KeyT, ValueT> *Pos, 483193323Sed const std::pair<KeyT, ValueT> *E) 484193323Sed : DenseMapIterator<KeyT, ValueT, KeyInfoT>(Pos, E) { 485193323Sed } 486193323Sed const std::pair<KeyT, ValueT> &operator*() const { 487193323Sed return *this->Ptr; 488193323Sed } 489193323Sed const std::pair<KeyT, ValueT> *operator->() const { 490193323Sed return this->Ptr; 491193323Sed } 492193323Sed}; 493193323Sed 494193323Sed} // end namespace llvm 495193323Sed 496193323Sed#endif 497