1894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman//===--- StringMap.cpp - String Hash table map implementation -------------===// 2894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// 3894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// The LLVM Compiler Infrastructure 4894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// 5894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// This file is distributed under the University of Illinois Open Source 6894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// License. See LICENSE.TXT for details. 7894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// 8894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman//===----------------------------------------------------------------------===// 9894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// 10894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// This file implements the StringMap class. 11894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// 12894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman//===----------------------------------------------------------------------===// 13894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 14894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman#include "llvm/ADT/StringMap.h" 15894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman#include "llvm/ADT/StringExtras.h" 16894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman#include <cassert> 17894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Baumanusing namespace llvm; 18894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 19894018228b0e0bdbd7aa7e8f47d4a9458789ca82John BaumanStringMapImpl::StringMapImpl(unsigned InitSize, unsigned itemSize) { 20894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman ItemSize = itemSize; 21894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 22894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // If a size is specified, initialize the table with that many buckets. 23894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (InitSize) { 24894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman init(InitSize); 25894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return; 26894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 27894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 28894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Otherwise, initialize it with zero buckets to avoid the allocation. 29894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman TheTable = 0; 30894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman NumBuckets = 0; 31894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman NumItems = 0; 32894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman NumTombstones = 0; 33894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman} 34894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 35894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Baumanvoid StringMapImpl::init(unsigned InitSize) { 36894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman assert((InitSize & (InitSize-1)) == 0 && 37894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman "Init Size must be a power of 2 or zero!"); 38894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman NumBuckets = InitSize ? InitSize : 16; 39894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman NumItems = 0; 40894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman NumTombstones = 0; 41894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 42894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman TheTable = (ItemBucket*)calloc(NumBuckets+1, sizeof(ItemBucket)); 43894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 44894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Allocate one extra bucket, set it to look filled so the iterators stop at 45894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // end. 46894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman TheTable[NumBuckets].Item = (StringMapEntryBase*)2; 47894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman} 48894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 49894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 50894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// LookupBucketFor - Look up the bucket that the specified string should end 51894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// up in. If it already exists as a key in the map, the Item pointer for the 52894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// specified bucket will be non-null. Otherwise, it will be null. In either 53894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// case, the FullHashValue field of the bucket will be set to the hash value 54894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// of the string. 55894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Baumanunsigned StringMapImpl::LookupBucketFor(StringRef Name) { 56894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman unsigned HTSize = NumBuckets; 57894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (HTSize == 0) { // Hash table unallocated so far? 58894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman init(16); 59894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman HTSize = NumBuckets; 60894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 61894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman unsigned FullHashValue = HashString(Name); 62894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman unsigned BucketNo = FullHashValue & (HTSize-1); 63894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 64894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman unsigned ProbeAmt = 1; 65894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman int FirstTombstone = -1; 66894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman while (1) { 67894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman ItemBucket &Bucket = TheTable[BucketNo]; 68894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman StringMapEntryBase *BucketItem = Bucket.Item; 69894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // If we found an empty bucket, this key isn't in the table yet, return it. 70894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (BucketItem == 0) { 71894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // If we found a tombstone, we want to reuse the tombstone instead of an 72894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // empty bucket. This reduces probing. 73894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (FirstTombstone != -1) { 74894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman TheTable[FirstTombstone].FullHashValue = FullHashValue; 75894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return FirstTombstone; 76894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 77894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 78894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Bucket.FullHashValue = FullHashValue; 79894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return BucketNo; 80894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 81894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 82894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (BucketItem == getTombstoneVal()) { 83894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Skip over tombstones. However, remember the first one we see. 84894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (FirstTombstone == -1) FirstTombstone = BucketNo; 85894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } else if (Bucket.FullHashValue == FullHashValue) { 86894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // If the full hash value matches, check deeply for a match. The common 87894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // case here is that we are only looking at the buckets (for item info 88894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // being non-null and for the full hash value) not at the items. This 89894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // is important for cache locality. 90894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 91894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Do the comparison like this because Name isn't necessarily 92894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // null-terminated! 93894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman char *ItemStr = (char*)BucketItem+ItemSize; 94894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (Name == StringRef(ItemStr, BucketItem->getKeyLength())) { 95894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // We found a match! 96894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return BucketNo; 97894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 98894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 99894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 100894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Okay, we didn't find the item. Probe to the next bucket. 101894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman BucketNo = (BucketNo+ProbeAmt) & (HTSize-1); 102894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 103894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Use quadratic probing, it has fewer clumping artifacts than linear 104894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // probing and has good cache behavior in the common case. 105894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman ++ProbeAmt; 106894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 107894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman} 108894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 109894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 110894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// FindKey - Look up the bucket that contains the specified key. If it exists 111894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// in the map, return the bucket number of the key. Otherwise return -1. 112894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// This does not modify the map. 113894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Baumanint StringMapImpl::FindKey(StringRef Key) const { 114894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman unsigned HTSize = NumBuckets; 115894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (HTSize == 0) return -1; // Really empty table? 116894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman unsigned FullHashValue = HashString(Key); 117894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman unsigned BucketNo = FullHashValue & (HTSize-1); 118894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 119894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman unsigned ProbeAmt = 1; 120894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman while (1) { 121894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman ItemBucket &Bucket = TheTable[BucketNo]; 122894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman StringMapEntryBase *BucketItem = Bucket.Item; 123894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // If we found an empty bucket, this key isn't in the table yet, return. 124894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (BucketItem == 0) 125894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return -1; 126894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 127894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (BucketItem == getTombstoneVal()) { 128894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Ignore tombstones. 129894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } else if (Bucket.FullHashValue == FullHashValue) { 130894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // If the full hash value matches, check deeply for a match. The common 131894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // case here is that we are only looking at the buckets (for item info 132894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // being non-null and for the full hash value) not at the items. This 133894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // is important for cache locality. 134894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 135894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Do the comparison like this because NameStart isn't necessarily 136894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // null-terminated! 137894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman char *ItemStr = (char*)BucketItem+ItemSize; 138894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (Key == StringRef(ItemStr, BucketItem->getKeyLength())) { 139894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // We found a match! 140894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return BucketNo; 141894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 142894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 143894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 144894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Okay, we didn't find the item. Probe to the next bucket. 145894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman BucketNo = (BucketNo+ProbeAmt) & (HTSize-1); 146894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 147894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Use quadratic probing, it has fewer clumping artifacts than linear 148894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // probing and has good cache behavior in the common case. 149894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman ++ProbeAmt; 150894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 151894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman} 152894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 153894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// RemoveKey - Remove the specified StringMapEntry from the table, but do not 154894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// delete it. This aborts if the value isn't in the table. 155894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Baumanvoid StringMapImpl::RemoveKey(StringMapEntryBase *V) { 156894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman const char *VStr = (char*)V + ItemSize; 157894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman StringMapEntryBase *V2 = RemoveKey(StringRef(VStr, V->getKeyLength())); 15819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman (void)V2; 159894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman assert(V == V2 && "Didn't find key?"); 160894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman} 161894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 162894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// RemoveKey - Remove the StringMapEntry for the specified key from the 163894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// table, returning it. If the key is not in the table, this returns null. 164894018228b0e0bdbd7aa7e8f47d4a9458789ca82John BaumanStringMapEntryBase *StringMapImpl::RemoveKey(StringRef Key) { 165894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman int Bucket = FindKey(Key); 166894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (Bucket == -1) return 0; 167894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 168894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman StringMapEntryBase *Result = TheTable[Bucket].Item; 169894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman TheTable[Bucket].Item = getTombstoneVal(); 170894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman --NumItems; 171894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman ++NumTombstones; 17219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman assert(NumItems + NumTombstones <= NumBuckets); 17319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 174894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return Result; 175894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman} 176894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 177894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 178894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 179894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// RehashTable - Grow the table, redistributing values into the buckets with 180894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// the appropriate mod-of-hashtable-size. 181894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Baumanvoid StringMapImpl::RehashTable() { 18219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman unsigned NewSize; 18319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 18419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // If the hash table is now more than 3/4 full, or if fewer than 1/8 of 18519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // the buckets are empty (meaning that many are filled with tombstones), 18619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // grow/rehash the table. 18719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (NumItems*4 > NumBuckets*3) { 18819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman NewSize = NumBuckets*2; 18919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } else if (NumBuckets-(NumItems+NumTombstones) < NumBuckets/8) { 19019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman NewSize = NumBuckets; 19119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } else { 19219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return; 19319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 19419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 195894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Allocate one extra bucket which will always be non-empty. This allows the 196894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // iterators to stop at end. 197894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman ItemBucket *NewTableArray =(ItemBucket*)calloc(NewSize+1, sizeof(ItemBucket)); 198894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman NewTableArray[NewSize].Item = (StringMapEntryBase*)2; 199894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 200894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Rehash all the items into their new buckets. Luckily :) we already have 201894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // the hash values available, so we don't have to rehash any strings. 202894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman for (ItemBucket *IB = TheTable, *E = TheTable+NumBuckets; IB != E; ++IB) { 203894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (IB->Item && IB->Item != getTombstoneVal()) { 204894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Fast case, bucket available. 205894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman unsigned FullHash = IB->FullHashValue; 206894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman unsigned NewBucket = FullHash & (NewSize-1); 207894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (NewTableArray[NewBucket].Item == 0) { 208894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman NewTableArray[FullHash & (NewSize-1)].Item = IB->Item; 209894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman NewTableArray[FullHash & (NewSize-1)].FullHashValue = FullHash; 210894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman continue; 211894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 212894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 213894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Otherwise probe for a spot. 214894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman unsigned ProbeSize = 1; 215894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman do { 216894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman NewBucket = (NewBucket + ProbeSize++) & (NewSize-1); 217894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } while (NewTableArray[NewBucket].Item); 218894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 219894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Finally found a slot. Fill it in. 220894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman NewTableArray[NewBucket].Item = IB->Item; 221894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman NewTableArray[NewBucket].FullHashValue = FullHash; 222894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 223894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 224894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 225894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman free(TheTable); 226894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 227894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman TheTable = NewTableArray; 228894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman NumBuckets = NewSize; 22919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman NumTombstones = 0; 230894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman} 231