src/vm/hash.h

   1 // Licensed to the .NET Foundation under one or more agreements.
   2 // The .NET Foundation licenses this file to you under the MIT license.
   3 // See the LICENSE file in the project root for more information.
   4
   5
   6 /*++---------------------------------------------------------------------------------------
   7
   8 Module Name:
   9
  10     hash.h
  11
  12 Abstract:
  13
  14     Fast hash table classes,
  15 --*/
  16
  17 #ifndef _HASH_H_
  18 #define _HASH_H_
  19
  20 #ifndef ASSERT
  21 #define ASSERT _ASSERTE
  22 #endif
  23
  24
  25 #include "crst.h"
  26
  27 // #define HASHTABLE_PROFILE
  28
  29 // Track collision chains of up to length X
  30 const unsigned int HASHTABLE_LOOKUP_PROBES_DATA = 20;
  31
  32 //-------------------------------------------------------
  33 //  enums for special Key values used in hash table
  34 //
  35 enum
  36 {
  37     EMPTY  = 0,
  38     DELETED = 1,
  39     INVALIDENTRY = ~0
  40 };
  41
  42 typedef ULONG_PTR UPTR;
  43
  44 //------------------------------------------------------------------------------
  45 // classes in use
  46 //------------------------------------------------------------------------------
  47 class Bucket;
  48 class HashMap;
  49
  50 //-------------------------------------------------------
  51 //  class Bucket
  52 //  used by hash table implementation
  53 //
  54 typedef DPTR(class Bucket) PTR_Bucket;
  55 class Bucket
  56 {
  57 public:
  58     UPTR m_rgKeys[4];
  59     UPTR m_rgValues[4];
  60
  61 #define VALUE_MASK (sizeof(LPVOID) == 4 ? 0x7FFFFFFF : I64(0x7FFFFFFFFFFFFFFF))
  62
  63     void SetValue (UPTR value, UPTR i)
  64     {
  65         LIMITED_METHOD_CONTRACT;
  66
  67         ASSERT(value <= VALUE_MASK);
  68         m_rgValues[i] = (UPTR) ((m_rgValues[i] & ~VALUE_MASK) | value);
  69     }
  70
  71     UPTR GetValue (UPTR i)
  72     {
  73         LIMITED_METHOD_DAC_CONTRACT;
  74
  75         return (UPTR)(m_rgValues[i] & VALUE_MASK);
  76     }
  77
  78     UPTR IsCollision() // useful sentinel for fast fail of lookups
  79     {
  80         LIMITED_METHOD_CONTRACT;
  81
  82         return (UPTR) (m_rgValues[0] & ~VALUE_MASK);
  83     }
  84
  85     void SetCollision()
  86     {
  87         LIMITED_METHOD_CONTRACT;
  88
  89         m_rgValues[0] |= ~VALUE_MASK; // set collision bit
  90         m_rgValues[1] &= VALUE_MASK;   // reset has free slots bit
  91     }
  92
  93     BOOL HasFreeSlots()
  94     {
  95         WRAPPER_NO_CONTRACT;
  96
  97         // check for free slots available in the bucket
  98         // either there is no collision or a free slot has been during
  99         // compaction
 100         return (!IsCollision() || (m_rgValues[1] & ~VALUE_MASK));
 101     }
 102
 103     void SetFreeSlots()
 104     {
 105         LIMITED_METHOD_CONTRACT;
 106
 107         m_rgValues[1] |= ~VALUE_MASK; // set has free slots bit
 108     }
 109
 110     BOOL InsertValue(const UPTR key, const UPTR value);
 111 };
 112
 113
 114 //------------------------------------------------------------------------------
 115 // bool (*CompareFnPtr)(UPTR,UPTR); pointer to a function that takes 2 UPTRs
 116 // and returns a boolean, provide a function with this signature to the HashTable
 117 // to use for comparing Values during lookup
 118 //------------------------------------------------------------------------------
 119 typedef  BOOL (*CompareFnPtr)(UPTR,UPTR);
 120
 121 class Compare
 122 {
 123 protected:
 124     Compare()
 125     {
 126         LIMITED_METHOD_CONTRACT;
 127
 128         m_ptr = NULL;
 129     }
 130 public:
 131     CompareFnPtr m_ptr;
 132
 133     Compare(CompareFnPtr ptr)
 134     {
 135         LIMITED_METHOD_CONTRACT;
 136
 137         _ASSERTE(ptr != NULL);
 138         m_ptr = ptr;
 139     }
 140
 141     virtual ~Compare()
 142     {
 143         LIMITED_METHOD_CONTRACT;
 144     }
 145
 146     virtual UPTR CompareHelper(UPTR val1, UPTR storedval)
 147     {
 148         WRAPPER_NO_CONTRACT;
 149
 150 #ifndef _DEBUG
 151         CONTRACTL
 152         {
 153             DISABLED(THROWS);       // This is not a bug, we cannot decide, since the function ptr called may be either.
 154             DISABLED(GC_NOTRIGGER); // This is not a bug, we cannot decide, since the function ptr called may be either.
 155         }
 156         CONTRACTL_END;
 157 #endif // !_DEBUG
 158
 159         return (*m_ptr)(val1,storedval);
 160     }
 161 };
 162
 163 class ComparePtr : public Compare
 164 {
 165 public:
 166     ComparePtr (CompareFnPtr ptr)
 167     {
 168         LIMITED_METHOD_CONTRACT;
 169
 170         _ASSERTE(ptr != NULL);
 171         m_ptr = ptr;
 172     }
 173
 174     virtual UPTR CompareHelper(UPTR val1, UPTR storedval)
 175     {
 176         WRAPPER_NO_CONTRACT;
 177
 178 #ifndef _DEBUG
 179         CONTRACTL
 180         {
 181             DISABLED(THROWS);       // This is not a bug, we cannot decide, since the function ptr called may be either.
 182             DISABLED(GC_NOTRIGGER); // This is not a bug, we cannot decide, since the function ptr called may be either.
 183         }
 184         CONTRACTL_END;
 185 #endif // !_DEBUG
 186
 187         storedval <<=1;
 188         return (*m_ptr)(val1,storedval);
 189     }
 190 };
 191
 192 //------------------------------------------------------------------------------
 193 // Class HashMap
 194 // Fast Hash table, for concurrent use,
 195 // stores a 4 byte Key and a 4 byte Value for each slot.
 196 // Duplicate keys are allowed, (keys are compared as 4 byte UPTRs)
 197 // Duplicate values are allowed,(values are compared using comparison fn. provided)
 198 // but if no comparison function is provided then the values should be unique
 199 //
 200 // Lookup's don't require to take locks, unless you specify fAsyncMode.
 201 // Insert and Delete operations require locks
 202 // Inserting a duplicate value will assert in DEBUG mode, the PROPER way to perform inserts
 203 // is to take a lock, do a lookup and if the lookup fails then Insert
 204 //
 205 // In async mode, deleted slots are not immediately reclaimed (until a rehash), and
 206 // accesses to the hash table cause a transition to cooperative GC mode, and reclamation of old
 207 // hash maps (after a rehash) are deferred until GC time.
 208 // In sync mode, none of this is necessary; however calls to LookupValue must be synchronized as well.
 209 //
 210 // Algorithm:
 211 //   The Hash table is an array of buckets, each bucket can contain 4 key/value pairs
 212 //   Special key values are used to identify EMPTY and DELETED slots
 213 //   Hash function uses the current size of the hash table and a SEED based on the key
 214 //   to choose the bucket, seed starts of being the key and gets refined every time
 215 //   the hash function is re-applied.
 216 //
 217 //   Inserts choose an empty slot in the current bucket for new entries, if the current bucket
 218 //   is full, then the seed is refined and a new bucket is choosen, if an empty slot is not found
 219 //   after 8 retries, the hash table is expanded, this causes the current array of buckets to
 220 //   be put in a free list and a new array of buckets is allocated and all non-deleted entries
 221 //   from the old hash table are rehashed to the new array
 222 //   The old arrays are reclaimed during Compact phase, which should only be called during GC or
 223 //   any other time it is guaranteed that no Lookups are taking place.
 224 //   Concurrent Insert and Delete operations need to be serialized
 225 //
 226 //   Delete operations, mark the Key in the slot as DELETED, the value is not removed and inserts
 227 //   don't reuse these slots, they get reclaimed during expansion and compact phases.
 228 //
 229 //------------------------------------------------------------------------------
 230
 231 class HashMap
 232 {
 233 public:
 234
 235     //@constructor
 236     HashMap() DAC_EMPTY();
 237     //destructor
 238     ~HashMap() DAC_EMPTY();
 239
 240     // Init
 241     void Init(BOOL fAsyncMode, LockOwner *pLock)
 242     {
 243         WRAPPER_NO_CONTRACT;
 244
 245         Init(0, (Compare *)NULL,fAsyncMode, pLock);
 246     }
 247     // Init
 248     void Init(DWORD cbInitialSize, BOOL fAsyncMode, LockOwner *pLock)
 249     {
 250         WRAPPER_NO_CONTRACT;
 251
 252         Init(cbInitialSize, (Compare*)NULL, fAsyncMode, pLock);
 253     }
 254     // Init
 255     void Init(CompareFnPtr ptr, BOOL fAsyncMode, LockOwner *pLock)
 256     {
 257         WRAPPER_NO_CONTRACT;
 258
 259         Init(0, ptr, fAsyncMode, pLock);
 260     }
 261
 262     // Init method
 263     void Init(DWORD cbInitialSize, CompareFnPtr ptr, BOOL fAsyncMode, LockOwner *pLock);
 264
 265
 266     //Init method
 267     void Init(DWORD cbInitialSize, Compare* pCompare, BOOL fAsyncMode, LockOwner *pLock);
 268
 269     // check to see if the value is already in the Hash Table
 270     // key should be > DELETED
 271     // if provided, uses the comparison function ptr to compare values
 272     // returns INVALIDENTRY if not found
 273     UPTR LookupValue(UPTR key, UPTR value);
 274
 275     // Insert if the value is not already present
 276     // it is illegal to insert duplicate values in the hash map
 277     // do a lookup to verify the value is not already present
 278
 279     void InsertValue(UPTR key, UPTR value);
 280
 281     // Replace the value if present
 282     // returns the previous value, or INVALIDENTRY if not present
 283     // does not insert a new value under any circumstances
 284
 285     UPTR ReplaceValue(UPTR key, UPTR value);
 286
 287     // mark the entry as deleted and return the stored value
 288     // returns INVALIDENTRY, if not found
 289     UPTR DeleteValue (UPTR key, UPTR value);
 290
 291     // for unique keys, use this function to get the value that is
 292     // stored in the hash table, returns INVALIDENTRY if key not found
 293     UPTR Gethash(UPTR key);
 294
 295     // Called only when all threads are frozed, like during GC
 296     // for a SINGLE user mode, call compact after every delete
 297     // operation on the hash table
 298     void Compact();
 299
 300     // Remove all entries from the hash tablex
 301     void Clear();
 302
 303 #ifdef DACCESS_COMPILE
 304     void EnumMemoryRegions(CLRDataEnumMemoryFlags flags);
 305 #endif
 306
 307     // inline helper, in non HASHTABLE_PROFILE mode becomes a NO-OP
 308     void        ProfileLookup(UPTR ntry, UPTR retValue);
 309     // data members used for profiling
 310 #ifdef HASHTABLE_PROFILE
 311     unsigned    m_cbRehash;    // number of times rehashed
 312     unsigned    m_cbRehashSlots; // number of slots that were rehashed
 313     unsigned    m_cbObsoleteTables;
 314     unsigned    m_cbTotalBuckets;
 315     unsigned    m_cbInsertProbesGt8; // inserts that needed more than 8 probes
 316     LONG        m_rgLookupProbes[HASHTABLE_LOOKUP_PROBES_DATA]; // lookup probes
 317     UPTR        maxFailureProbe; // cost of failed lookup
 318
 319     void DumpStatistics();
 320 #endif // HASHTABLE_PROFILE
 321
 322 #if 0 // Test-only code for debugging this class.
 323 #ifndef DACCESS_COMPILE
 324     static void LookupPerfTest(HashMap * table, const unsigned int MinThreshold);
 325     static void HashMapTest();
 326 #endif // !DACCESS_COMPILE
 327 #endif // 0 // Test-only code for debugging this class.
 328
 329 protected:
 330     // static helper function
 331     static UPTR PutEntry (Bucket* rgBuckets, UPTR key, UPTR value);
 332 private:
 333
 334     DWORD       GetNearestIndex(DWORD cbInitialSize);
 335
 336 #ifdef _DEBUG
 337     static void            Enter(HashMap *);        // check valid to enter
 338     static void            Leave(HashMap *);        // check valid to leave
 339
 340     typedef Holder<HashMap *, HashMap::Enter, HashMap::Leave> SyncAccessHolder;
 341     BOOL            m_fInSyncCode; // test for non-synchronus access
 342 #else // !_DEBUG
 343     // in non DEBUG mode use a no-op helper
 344     typedef NoOpBaseHolder<HashMap *> SyncAccessHolder;
 345 #endif // !_DEBUG
 346
 347     // compute the new size, based on the number of free slots
 348     // available, compact or expand
 349     UPTR            NewSize();
 350     // create a new bucket array and rehash the non-deleted entries
 351     void            Rehash();
 352     static DWORD    GetSize(PTR_Bucket rgBuckets);
 353     static void     SetSize(Bucket* rgBuckets, size_t size);
 354     PTR_Bucket      Buckets();
 355     UPTR            CompareValues(const UPTR value1, const UPTR value2);
 356
 357     // For double hashing, compute the second hash function once, then add.
 358     // H(key, i) = H1(key) + i * H2(key), where 0 <= i < numBuckets
 359     static void     HashFunction(const UPTR key, const UINT numBuckets, UINT &seed, UINT &incr);
 360
 361     Compare*        m_pCompare;         // compare object to be used in lookup
 362     SIZE_T          m_iPrimeIndex;      // current size (index into prime array)
 363     PTR_Bucket      m_rgBuckets;        // array of buckets
 364
 365     // track the number of inserts and deletes
 366     SIZE_T          m_cbPrevSlotsInUse;
 367     SIZE_T          m_cbInserts;
 368     SIZE_T          m_cbDeletes;
 369     // mode of operation, synchronus or single user
 370     bool            m_fAsyncMode;
 371
 372 #ifdef _DEBUG
 373     LPVOID          m_lockData;
 374     FnLockOwner     m_pfnLockOwner;
 375     EEThreadId      m_writerThreadId;
 376 #endif // _DEBUG
 377
 378 #ifdef _DEBUG
 379     // A thread must own a lock for a hash if it is a writer.
 380     BOOL OwnLock();
 381 #endif // _DEBUG
 382
 383 public:
 384     ///---------Iterator----------------
 385
 386     // Iterator,
 387     class Iterator
 388     {
 389         PTR_Bucket m_pBucket;
 390         PTR_Bucket m_pSentinel;
 391         int        m_id;
 392         BOOL       m_fEnd;
 393
 394     public:
 395
 396         // Constructor
 397         Iterator(Bucket* pBucket) :
 398             m_pBucket(dac_cast<PTR_Bucket>(pBucket)),
 399             m_id(-1), m_fEnd(false)
 400         {
 401             SUPPORTS_DAC;
 402             WRAPPER_NO_CONTRACT;
 403
 404             if (!m_pBucket) {
 405                 m_pSentinel = NULL;
 406                 m_fEnd = true;
 407                 return;
 408             }
 409             size_t cbSize = (PTR_size_t(m_pBucket))[0];
 410             m_pBucket++;
 411             m_pSentinel = m_pBucket+cbSize;
 412             MoveNext(); // start
 413         }
 414
 415         Iterator(const Iterator& iter)
 416         {
 417             LIMITED_METHOD_CONTRACT;
 418
 419             m_pBucket = iter.m_pBucket;
 420             m_pSentinel = iter.m_pSentinel;
 421             m_id    = iter.m_id;
 422             m_fEnd = iter.m_fEnd;
 423
 424         }
 425
 426         //destructor
 427         ~Iterator(){ LIMITED_METHOD_DAC_CONTRACT; };
 428
 429         // friend operator==
 430         friend bool operator == (const Iterator& lhs, const Iterator& rhs)
 431         {
 432             LIMITED_METHOD_CONTRACT;
 433
 434             return (lhs.m_pBucket == rhs.m_pBucket && lhs.m_id == rhs.m_id);
 435         }
 436         // operator =
 437         inline Iterator& operator= (const Iterator& iter)
 438         {
 439             LIMITED_METHOD_CONTRACT;
 440
 441             m_pBucket = iter.m_pBucket;
 442             m_pSentinel = iter.m_pSentinel;
 443             m_id    = iter.m_id;
 444             m_fEnd = iter.m_fEnd;
 445             return *this;
 446         }
 447
 448         // operator ++
 449         inline void operator++ ()
 450         {
 451             WRAPPER_NO_CONTRACT;
 452             SUPPORTS_DAC;
 453
 454             _ASSERTE(!m_fEnd); // check we are not alredy at end
 455             MoveNext();
 456         }
 457         // operator --
 458
 459
 460
 461         //accessors : GetDisc() , returns the discriminator
 462         inline UPTR GetKey()
 463         {
 464             LIMITED_METHOD_CONTRACT;
 465
 466             _ASSERTE(!m_fEnd); // check we are not alredy at end
 467             return m_pBucket->m_rgKeys[m_id];
 468         }
 469         //accessors : SetDisc() , sets the discriminator
 470
 471
 472         //accessors : GetValue(),
 473         // returns the pointer that corresponds to the discriminator
 474         inline UPTR GetValue()
 475         {
 476             WRAPPER_NO_CONTRACT;
 477             SUPPORTS_DAC;
 478
 479             _ASSERTE(!m_fEnd); // check we are not alredy at end
 480             return m_pBucket->GetValue(m_id);
 481         }
 482
 483
 484         // end(), check if the iterator is at the end of the bucket
 485         inline BOOL end() const
 486         {
 487             LIMITED_METHOD_DAC_CONTRACT;
 488
 489             return m_fEnd;
 490         }
 491
 492     protected:
 493
 494         void MoveNext()
 495         {
 496             LIMITED_METHOD_DAC_CONTRACT;
 497
 498             for (;m_pBucket < m_pSentinel; m_pBucket++)
 499             {   //loop thru all buckets
 500                 for (m_id = m_id+1; m_id < 4; m_id++)
 501                 {   //loop through all slots
 502                     if (m_pBucket->m_rgKeys[m_id] > DELETED)
 503                     {
 504                         return;
 505                     }
 506                 }
 507                 m_id  = -1;
 508             }
 509             m_fEnd = true;
 510         }
 511
 512     };
 513
 514     inline Bucket* firstBucket()
 515     {
 516         WRAPPER_NO_CONTRACT;
 517         SUPPORTS_DAC;
 518
 519         return m_rgBuckets;
 520     }
 521
 522     // return an iterator, positioned at the beginning of the bucket
 523     inline Iterator begin()
 524     {
 525         WRAPPER_NO_CONTRACT;
 526
 527         return Iterator(m_rgBuckets);
 528     }
 529
 530     inline SIZE_T GetCount()
 531     {
 532         LIMITED_METHOD_CONTRACT;
 533
 534         return m_cbInserts-m_cbDeletes;
 535     }
 536 };
 537
 538 //---------------------------------------------------------------------------------------
 539 // class PtrHashMap
 540 //  Wrapper class for using Hash table to store pointer values
 541 //  HashMap class requires that high bit is always reset
 542 //  The allocator used within the runtime, always allocates objects 8 byte aligned
 543 //  so we can shift right one bit, and store the result in the hash table
 544 class PtrHashMap
 545 {
 546     HashMap         m_HashMap;
 547
 548     // key really acts as a hash code. Sanitize it from special values used by the underlying HashMap.
 549     inline static UPTR SanitizeKey(UPTR key)
 550     {
 551         return (key > DELETED) ? key : (key + 100);
 552     }
 553
 554 public:
 555 #ifndef DACCESS_COMPILE
 556     void *operator new(size_t size, LoaderHeap *pHeap);
 557     void operator delete(void *p);
 558 #endif // !DACCESS_COMPILE
 559
 560     // Init
 561     void Init(BOOL fAsyncMode, LockOwner *pLock)
 562     {
 563         WRAPPER_NO_CONTRACT;
 564
 565         Init(0,NULL,fAsyncMode,pLock);
 566     }
 567     // Init
 568     void Init(DWORD cbInitialSize, BOOL fAsyncMode, LockOwner *pLock)
 569     {
 570         WRAPPER_NO_CONTRACT;
 571
 572         Init(cbInitialSize, NULL, fAsyncMode,pLock);
 573     }
 574     // Init
 575     void Init(CompareFnPtr ptr, BOOL fAsyncMode, LockOwner *pLock)
 576     {
 577         WRAPPER_NO_CONTRACT;
 578
 579         Init(0, ptr, fAsyncMode,pLock);
 580     }
 581
 582     // Init method
 583     void Init(DWORD cbInitialSize, CompareFnPtr ptr, BOOL fAsyncMode, LockOwner *pLock);
 584
 585     // check to see if the value is already in the Hash Table
 586     LPVOID LookupValue(UPTR key, LPVOID pv)
 587     {
 588         WRAPPER_NO_CONTRACT;
 589
 590         key = SanitizeKey(key);
 591
 592         // gmalloc allocator, always allocates 8 byte aligned
 593         // so we can shift out the lowest bit
 594         // ptr right shift by 1
 595         UPTR value = (UPTR)pv;
 596         _ASSERTE((value & 0x1) == 0);
 597         value>>=1;
 598         UPTR val =  m_HashMap.LookupValue (key, value);
 599         if (val != (UPTR) INVALIDENTRY)
 600         {
 601             val<<=1;
 602         }
 603         return (LPVOID)val;
 604     }
 605
 606     // Insert if the value is not already present
 607     // it is illegal to insert duplicate values in the hash map
 608     // users should do a lookup to verify the value is not already present
 609
 610     void InsertValue(UPTR key, LPVOID pv)
 611     {
 612         WRAPPER_NO_CONTRACT;
 613
 614         key = SanitizeKey(key);
 615
 616         // gmalloc allocator, always allocates 8 byte aligned
 617         // so we can shift out the lowest bit
 618         // ptr right shift by 1
 619         UPTR value = (UPTR)pv;
 620         _ASSERTE((value & 0x1) == 0);
 621         value>>=1;
 622         m_HashMap.InsertValue (key, value);
 623     }
 624
 625     // Replace the value if present
 626     // returns the previous value, or INVALIDENTRY if not present
 627     // does not insert a new value under any circumstances
 628
 629     LPVOID ReplaceValue(UPTR key, LPVOID pv)
 630     {
 631         WRAPPER_NO_CONTRACT;
 632
 633         key = SanitizeKey(key);
 634
 635         // gmalloc allocator, always allocates 8 byte aligned
 636         // so we can shift out the lowest bit
 637         // ptr right shift by 1
 638         UPTR value = (UPTR)pv;
 639         _ASSERTE((value & 0x1) == 0);
 640         value>>=1;
 641         UPTR val = m_HashMap.ReplaceValue (key, value);
 642         if (val != (UPTR) INVALIDENTRY)
 643         {
 644             val<<=1;
 645         }
 646         return (LPVOID)val;
 647     }
 648
 649     // mark the entry as deleted and return the stored value
 650     // returns INVALIDENTRY if not found
 651     LPVOID DeleteValue (UPTR key,LPVOID pv)
 652     {
 653         WRAPPER_NO_CONTRACT;
 654
 655         key = SanitizeKey(key);
 656
 657         UPTR value = (UPTR)pv;
 658         _ASSERTE((value & 0x1) == 0);
 659         value >>=1 ;
 660         UPTR val = m_HashMap.DeleteValue(key, value);
 661         if (val != (UPTR) INVALIDENTRY)
 662         {
 663             val <<= 1;
 664         }
 665         return (LPVOID)val;
 666     }
 667
 668     // for unique keys, use this function to get the value that is
 669     // stored in the hash table, returns INVALIDENTRY if key not found
 670     LPVOID Gethash(UPTR key)
 671     {
 672         WRAPPER_NO_CONTRACT;
 673
 674         key = SanitizeKey(key);
 675
 676         UPTR val = m_HashMap.Gethash(key);
 677         if (val != (UPTR) INVALIDENTRY)
 678         {
 679             val <<= 1;
 680         }
 681         return (LPVOID)val;
 682     }
 683
 684     void Compact()
 685     {
 686         WRAPPER_NO_CONTRACT;
 687
 688         m_HashMap.Compact();
 689     }
 690
 691     void Clear()
 692     {
 693         WRAPPER_NO_CONTRACT;
 694
 695         m_HashMap.Clear();
 696     }
 697
 698     class PtrIterator
 699     {
 700         HashMap::Iterator iter;
 701
 702     public:
 703         PtrIterator(HashMap& hashMap) : iter(hashMap.begin())
 704         {
 705             LIMITED_METHOD_DAC_CONTRACT;
 706         }
 707         PtrIterator(Bucket* bucket) : iter(bucket)
 708         {
 709             LIMITED_METHOD_DAC_CONTRACT;
 710         }
 711
 712         ~PtrIterator()
 713         {
 714             LIMITED_METHOD_DAC_CONTRACT;
 715         }
 716
 717         BOOL end()
 718         {
 719             WRAPPER_NO_CONTRACT;
 720             SUPPORTS_DAC;
 721
 722             return iter.end();
 723         }
 724
 725         UPTR GetKey()
 726         {
 727             WRAPPER_NO_CONTRACT;
 728             SUPPORTS_DAC;
 729
 730             return iter.GetKey();
 731         }
 732
 733         PTR_VOID GetValue()
 734         {
 735             WRAPPER_NO_CONTRACT;
 736             SUPPORTS_DAC;
 737
 738             UPTR val = iter.GetValue();
 739             if (val != (UPTR) INVALIDENTRY)
 740             {
 741                 val <<= 1;
 742             }
 743             return PTR_VOID(val);
 744         }
 745
 746         void operator++()
 747         {
 748             WRAPPER_NO_CONTRACT;
 749             SUPPORTS_DAC;
 750
 751             iter.operator++();
 752         }
 753     };
 754
 755     inline Bucket* firstBucket()
 756     {
 757         WRAPPER_NO_CONTRACT;
 758         SUPPORTS_DAC;
 759
 760         return m_HashMap.firstBucket();
 761     }
 762
 763     // return an iterator, positioned at the beginning of the bucket
 764     inline PtrIterator begin()
 765     {
 766         WRAPPER_NO_CONTRACT;
 767
 768         return PtrIterator(m_HashMap);
 769     }
 770
 771     inline SIZE_T GetCount()
 772     {
 773         LIMITED_METHOD_CONTRACT;
 774
 775         return m_HashMap.GetCount();
 776     }
 777
 778 #ifdef DACCESS_COMPILE
 779     void EnumMemoryRegions(CLRDataEnumMemoryFlags flags)
 780     {
 781         SUPPORTS_DAC;
 782         m_HashMap.EnumMemoryRegions(flags);
 783     }
 784 #endif // DACCESS_COMPILE
 785 };
 786
 787 //---------------------------------------------------------------------
 788 //  inline Bucket*& NextObsolete (Bucket* rgBuckets)
 789 //  get the next obsolete bucket in the chain
 790 inline
 791 Bucket*& NextObsolete (Bucket* rgBuckets)
 792 {
 793     LIMITED_METHOD_CONTRACT;
 794
 795     return *(Bucket**)&((size_t*)rgBuckets)[1];
 796 }
 797
 798 #endif // !_HASH_H_