StringMap.cpp revision aea4fe2862ce17acc6ce943df589ee8d5eb05adf
1bb28a81ba3c112853f0eb3d8df0190accc0379c9Chris Lattner//===--- StringMap.cpp - String Hash table map implementation -------------===// 223d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner// 323d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner// The LLVM Compiler Infrastructure 423d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner// 54ee451de366474b9c228b4e5fa573795a715216dChris Lattner// This file is distributed under the University of Illinois Open Source 64ee451de366474b9c228b4e5fa573795a715216dChris Lattner// License. See LICENSE.TXT for details. 723d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner// 823d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner//===----------------------------------------------------------------------===// 923d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner// 10bb28a81ba3c112853f0eb3d8df0190accc0379c9Chris Lattner// This file implements the StringMap class. 1123d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner// 1223d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner//===----------------------------------------------------------------------===// 1323d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner 14bb28a81ba3c112853f0eb3d8df0190accc0379c9Chris Lattner#include "llvm/ADT/StringMap.h" 154dee7fd2c2cb3fabddf99a184abe41dbc0bd4085Daniel Dunbar#include "llvm/ADT/StringExtras.h" 1623d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner#include <cassert> 1723d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattnerusing namespace llvm; 1823d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner 19bb28a81ba3c112853f0eb3d8df0190accc0379c9Chris LattnerStringMapImpl::StringMapImpl(unsigned InitSize, unsigned itemSize) { 20794a014809d810b7ee9a96be76774185561f0dccChris Lattner ItemSize = itemSize; 21794a014809d810b7ee9a96be76774185561f0dccChris Lattner 22794a014809d810b7ee9a96be76774185561f0dccChris Lattner // If a size is specified, initialize the table with that many buckets. 23794a014809d810b7ee9a96be76774185561f0dccChris Lattner if (InitSize) { 24794a014809d810b7ee9a96be76774185561f0dccChris Lattner init(InitSize); 25794a014809d810b7ee9a96be76774185561f0dccChris Lattner return; 26794a014809d810b7ee9a96be76774185561f0dccChris Lattner } 27794a014809d810b7ee9a96be76774185561f0dccChris Lattner 28794a014809d810b7ee9a96be76774185561f0dccChris Lattner // Otherwise, initialize it with zero buckets to avoid the allocation. 29794a014809d810b7ee9a96be76774185561f0dccChris Lattner TheTable = 0; 30794a014809d810b7ee9a96be76774185561f0dccChris Lattner NumBuckets = 0; 31794a014809d810b7ee9a96be76774185561f0dccChris Lattner NumItems = 0; 32794a014809d810b7ee9a96be76774185561f0dccChris Lattner NumTombstones = 0; 33794a014809d810b7ee9a96be76774185561f0dccChris Lattner} 34794a014809d810b7ee9a96be76774185561f0dccChris Lattner 35794a014809d810b7ee9a96be76774185561f0dccChris Lattnervoid StringMapImpl::init(unsigned InitSize) { 3623d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner assert((InitSize & (InitSize-1)) == 0 && 3723d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner "Init Size must be a power of 2 or zero!"); 38ef4c916193e49e20c492f73147b3872b01c23862Chris Lattner NumBuckets = InitSize ? InitSize : 16; 3923d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner NumItems = 0; 4044dcd01cb3424420d79d5811fa8c1c052411f975Chris Lattner NumTombstones = 0; 4123d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner 42d2f197da59a3c937c1809997907918c029f9f884Chris Lattner TheTable = (ItemBucket*)calloc(NumBuckets+1, sizeof(ItemBucket)); 43a86559ec426c643a151aeba1e051e4f878050f95Chris Lattner 44a86559ec426c643a151aeba1e051e4f878050f95Chris Lattner // Allocate one extra bucket, set it to look filled so the iterators stop at 45a86559ec426c643a151aeba1e051e4f878050f95Chris Lattner // end. 46a86559ec426c643a151aeba1e051e4f878050f95Chris Lattner TheTable[NumBuckets].Item = (StringMapEntryBase*)2; 4723d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner} 4823d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner 4923d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner 5023d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner/// LookupBucketFor - Look up the bucket that the specified string should end 5123d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner/// up in. If it already exists as a key in the map, the Item pointer for the 5223d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner/// specified bucket will be non-null. Otherwise, it will be null. In either 5323d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner/// case, the FullHashValue field of the bucket will be set to the hash value 5423d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner/// of the string. 552928c83b010f7cfdb0f819199d806f6942a7d995Daniel Dunbarunsigned StringMapImpl::LookupBucketFor(StringRef Name) { 5623d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner unsigned HTSize = NumBuckets; 57794a014809d810b7ee9a96be76774185561f0dccChris Lattner if (HTSize == 0) { // Hash table unallocated so far? 58794a014809d810b7ee9a96be76774185561f0dccChris Lattner init(16); 59794a014809d810b7ee9a96be76774185561f0dccChris Lattner HTSize = NumBuckets; 60794a014809d810b7ee9a96be76774185561f0dccChris Lattner } 614dee7fd2c2cb3fabddf99a184abe41dbc0bd4085Daniel Dunbar unsigned FullHashValue = HashString(Name); 6223d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner unsigned BucketNo = FullHashValue & (HTSize-1); 6323d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner 6423d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner unsigned ProbeAmt = 1; 6544dcd01cb3424420d79d5811fa8c1c052411f975Chris Lattner int FirstTombstone = -1; 6623d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner while (1) { 6723d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner ItemBucket &Bucket = TheTable[BucketNo]; 68ee182422ff0b638b17c5ee802c19b8680107c2bbChris Lattner StringMapEntryBase *BucketItem = Bucket.Item; 6923d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner // If we found an empty bucket, this key isn't in the table yet, return it. 7023d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner if (BucketItem == 0) { 7144dcd01cb3424420d79d5811fa8c1c052411f975Chris Lattner // If we found a tombstone, we want to reuse the tombstone instead of an 7244dcd01cb3424420d79d5811fa8c1c052411f975Chris Lattner // empty bucket. This reduces probing. 7344dcd01cb3424420d79d5811fa8c1c052411f975Chris Lattner if (FirstTombstone != -1) { 7444dcd01cb3424420d79d5811fa8c1c052411f975Chris Lattner TheTable[FirstTombstone].FullHashValue = FullHashValue; 7544dcd01cb3424420d79d5811fa8c1c052411f975Chris Lattner return FirstTombstone; 7644dcd01cb3424420d79d5811fa8c1c052411f975Chris Lattner } 7744dcd01cb3424420d79d5811fa8c1c052411f975Chris Lattner 7823d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner Bucket.FullHashValue = FullHashValue; 7923d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner return BucketNo; 8023d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner } 8123d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner 8244dcd01cb3424420d79d5811fa8c1c052411f975Chris Lattner if (BucketItem == getTombstoneVal()) { 8344dcd01cb3424420d79d5811fa8c1c052411f975Chris Lattner // Skip over tombstones. However, remember the first one we see. 8444dcd01cb3424420d79d5811fa8c1c052411f975Chris Lattner if (FirstTombstone == -1) FirstTombstone = BucketNo; 8544dcd01cb3424420d79d5811fa8c1c052411f975Chris Lattner } else if (Bucket.FullHashValue == FullHashValue) { 8644dcd01cb3424420d79d5811fa8c1c052411f975Chris Lattner // If the full hash value matches, check deeply for a match. The common 8744dcd01cb3424420d79d5811fa8c1c052411f975Chris Lattner // case here is that we are only looking at the buckets (for item info 8844dcd01cb3424420d79d5811fa8c1c052411f975Chris Lattner // being non-null and for the full hash value) not at the items. This 8944dcd01cb3424420d79d5811fa8c1c052411f975Chris Lattner // is important for cache locality. 9044dcd01cb3424420d79d5811fa8c1c052411f975Chris Lattner 916316fbcb04af00fe76b6526fab09f51484014b3eDaniel Dunbar // Do the comparison like this because Name isn't necessarily 9223d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner // null-terminated! 9323d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner char *ItemStr = (char*)BucketItem+ItemSize; 946316fbcb04af00fe76b6526fab09f51484014b3eDaniel Dunbar if (Name == StringRef(ItemStr, BucketItem->getKeyLength())) { 9523d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner // We found a match! 9623d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner return BucketNo; 9723d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner } 9823d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner } 9923d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner 10023d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner // Okay, we didn't find the item. Probe to the next bucket. 10123d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner BucketNo = (BucketNo+ProbeAmt) & (HTSize-1); 10223d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner 10323d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner // Use quadratic probing, it has fewer clumping artifacts than linear 10423d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner // probing and has good cache behavior in the common case. 10523d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner ++ProbeAmt; 10623d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner } 10723d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner} 10823d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner 109b5bb9f5b5cfe89f4b7626671f4923d50f8d4cd6aChris Lattner 110b5bb9f5b5cfe89f4b7626671f4923d50f8d4cd6aChris Lattner/// FindKey - Look up the bucket that contains the specified key. If it exists 111b5bb9f5b5cfe89f4b7626671f4923d50f8d4cd6aChris Lattner/// in the map, return the bucket number of the key. Otherwise return -1. 112b5bb9f5b5cfe89f4b7626671f4923d50f8d4cd6aChris Lattner/// This does not modify the map. 1132928c83b010f7cfdb0f819199d806f6942a7d995Daniel Dunbarint StringMapImpl::FindKey(StringRef Key) const { 114b5bb9f5b5cfe89f4b7626671f4923d50f8d4cd6aChris Lattner unsigned HTSize = NumBuckets; 115794a014809d810b7ee9a96be76774185561f0dccChris Lattner if (HTSize == 0) return -1; // Really empty table? 1164dee7fd2c2cb3fabddf99a184abe41dbc0bd4085Daniel Dunbar unsigned FullHashValue = HashString(Key); 117b5bb9f5b5cfe89f4b7626671f4923d50f8d4cd6aChris Lattner unsigned BucketNo = FullHashValue & (HTSize-1); 118b5bb9f5b5cfe89f4b7626671f4923d50f8d4cd6aChris Lattner 119b5bb9f5b5cfe89f4b7626671f4923d50f8d4cd6aChris Lattner unsigned ProbeAmt = 1; 120b5bb9f5b5cfe89f4b7626671f4923d50f8d4cd6aChris Lattner while (1) { 121b5bb9f5b5cfe89f4b7626671f4923d50f8d4cd6aChris Lattner ItemBucket &Bucket = TheTable[BucketNo]; 122b5bb9f5b5cfe89f4b7626671f4923d50f8d4cd6aChris Lattner StringMapEntryBase *BucketItem = Bucket.Item; 123b5bb9f5b5cfe89f4b7626671f4923d50f8d4cd6aChris Lattner // If we found an empty bucket, this key isn't in the table yet, return. 124b5bb9f5b5cfe89f4b7626671f4923d50f8d4cd6aChris Lattner if (BucketItem == 0) 125b5bb9f5b5cfe89f4b7626671f4923d50f8d4cd6aChris Lattner return -1; 126b5bb9f5b5cfe89f4b7626671f4923d50f8d4cd6aChris Lattner 12744dcd01cb3424420d79d5811fa8c1c052411f975Chris Lattner if (BucketItem == getTombstoneVal()) { 12844dcd01cb3424420d79d5811fa8c1c052411f975Chris Lattner // Ignore tombstones. 12944dcd01cb3424420d79d5811fa8c1c052411f975Chris Lattner } else if (Bucket.FullHashValue == FullHashValue) { 13044dcd01cb3424420d79d5811fa8c1c052411f975Chris Lattner // If the full hash value matches, check deeply for a match. The common 13144dcd01cb3424420d79d5811fa8c1c052411f975Chris Lattner // case here is that we are only looking at the buckets (for item info 13244dcd01cb3424420d79d5811fa8c1c052411f975Chris Lattner // being non-null and for the full hash value) not at the items. This 13344dcd01cb3424420d79d5811fa8c1c052411f975Chris Lattner // is important for cache locality. 13444dcd01cb3424420d79d5811fa8c1c052411f975Chris Lattner 135b5bb9f5b5cfe89f4b7626671f4923d50f8d4cd6aChris Lattner // Do the comparison like this because NameStart isn't necessarily 136b5bb9f5b5cfe89f4b7626671f4923d50f8d4cd6aChris Lattner // null-terminated! 137b5bb9f5b5cfe89f4b7626671f4923d50f8d4cd6aChris Lattner char *ItemStr = (char*)BucketItem+ItemSize; 1386316fbcb04af00fe76b6526fab09f51484014b3eDaniel Dunbar if (Key == StringRef(ItemStr, BucketItem->getKeyLength())) { 139b5bb9f5b5cfe89f4b7626671f4923d50f8d4cd6aChris Lattner // We found a match! 140b5bb9f5b5cfe89f4b7626671f4923d50f8d4cd6aChris Lattner return BucketNo; 141b5bb9f5b5cfe89f4b7626671f4923d50f8d4cd6aChris Lattner } 142b5bb9f5b5cfe89f4b7626671f4923d50f8d4cd6aChris Lattner } 143b5bb9f5b5cfe89f4b7626671f4923d50f8d4cd6aChris Lattner 144b5bb9f5b5cfe89f4b7626671f4923d50f8d4cd6aChris Lattner // Okay, we didn't find the item. Probe to the next bucket. 145b5bb9f5b5cfe89f4b7626671f4923d50f8d4cd6aChris Lattner BucketNo = (BucketNo+ProbeAmt) & (HTSize-1); 146b5bb9f5b5cfe89f4b7626671f4923d50f8d4cd6aChris Lattner 147b5bb9f5b5cfe89f4b7626671f4923d50f8d4cd6aChris Lattner // Use quadratic probing, it has fewer clumping artifacts than linear 148b5bb9f5b5cfe89f4b7626671f4923d50f8d4cd6aChris Lattner // probing and has good cache behavior in the common case. 149b5bb9f5b5cfe89f4b7626671f4923d50f8d4cd6aChris Lattner ++ProbeAmt; 150b5bb9f5b5cfe89f4b7626671f4923d50f8d4cd6aChris Lattner } 151b5bb9f5b5cfe89f4b7626671f4923d50f8d4cd6aChris Lattner} 152b5bb9f5b5cfe89f4b7626671f4923d50f8d4cd6aChris Lattner 15344dcd01cb3424420d79d5811fa8c1c052411f975Chris Lattner/// RemoveKey - Remove the specified StringMapEntry from the table, but do not 15444dcd01cb3424420d79d5811fa8c1c052411f975Chris Lattner/// delete it. This aborts if the value isn't in the table. 15544dcd01cb3424420d79d5811fa8c1c052411f975Chris Lattnervoid StringMapImpl::RemoveKey(StringMapEntryBase *V) { 15644dcd01cb3424420d79d5811fa8c1c052411f975Chris Lattner const char *VStr = (char*)V + ItemSize; 1576316fbcb04af00fe76b6526fab09f51484014b3eDaniel Dunbar StringMapEntryBase *V2 = RemoveKey(StringRef(VStr, V->getKeyLength())); 1588e68c3873549ca31533e2e3e40dda3a43cb79566Jeffrey Yasskin (void)V2; 15944dcd01cb3424420d79d5811fa8c1c052411f975Chris Lattner assert(V == V2 && "Didn't find key?"); 16044dcd01cb3424420d79d5811fa8c1c052411f975Chris Lattner} 16144dcd01cb3424420d79d5811fa8c1c052411f975Chris Lattner 16244dcd01cb3424420d79d5811fa8c1c052411f975Chris Lattner/// RemoveKey - Remove the StringMapEntry for the specified key from the 16344dcd01cb3424420d79d5811fa8c1c052411f975Chris Lattner/// table, returning it. If the key is not in the table, this returns null. 1642928c83b010f7cfdb0f819199d806f6942a7d995Daniel DunbarStringMapEntryBase *StringMapImpl::RemoveKey(StringRef Key) { 1656316fbcb04af00fe76b6526fab09f51484014b3eDaniel Dunbar int Bucket = FindKey(Key); 16644dcd01cb3424420d79d5811fa8c1c052411f975Chris Lattner if (Bucket == -1) return 0; 16744dcd01cb3424420d79d5811fa8c1c052411f975Chris Lattner 16844dcd01cb3424420d79d5811fa8c1c052411f975Chris Lattner StringMapEntryBase *Result = TheTable[Bucket].Item; 16944dcd01cb3424420d79d5811fa8c1c052411f975Chris Lattner TheTable[Bucket].Item = getTombstoneVal(); 17044dcd01cb3424420d79d5811fa8c1c052411f975Chris Lattner --NumItems; 17144dcd01cb3424420d79d5811fa8c1c052411f975Chris Lattner ++NumTombstones; 17244dcd01cb3424420d79d5811fa8c1c052411f975Chris Lattner return Result; 17344dcd01cb3424420d79d5811fa8c1c052411f975Chris Lattner} 17444dcd01cb3424420d79d5811fa8c1c052411f975Chris Lattner 17544dcd01cb3424420d79d5811fa8c1c052411f975Chris Lattner 176b5bb9f5b5cfe89f4b7626671f4923d50f8d4cd6aChris Lattner 17723d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner/// RehashTable - Grow the table, redistributing values into the buckets with 17823d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner/// the appropriate mod-of-hashtable-size. 179bb28a81ba3c112853f0eb3d8df0190accc0379c9Chris Lattnervoid StringMapImpl::RehashTable() { 180aea4fe2862ce17acc6ce943df589ee8d5eb05adfJakob Stoklund Olesen unsigned NewSize; 181aea4fe2862ce17acc6ce943df589ee8d5eb05adfJakob Stoklund Olesen 182aea4fe2862ce17acc6ce943df589ee8d5eb05adfJakob Stoklund Olesen // If the hash table is now more than 3/4 full, or if fewer than 1/8 of 183aea4fe2862ce17acc6ce943df589ee8d5eb05adfJakob Stoklund Olesen // the buckets are empty (meaning that many are filled with tombstones), 184aea4fe2862ce17acc6ce943df589ee8d5eb05adfJakob Stoklund Olesen // grow/rehash the table. 185aea4fe2862ce17acc6ce943df589ee8d5eb05adfJakob Stoklund Olesen if (NumItems*4 > NumBuckets*3) { 186aea4fe2862ce17acc6ce943df589ee8d5eb05adfJakob Stoklund Olesen NewSize = NumBuckets*2; 187aea4fe2862ce17acc6ce943df589ee8d5eb05adfJakob Stoklund Olesen } else if (NumBuckets-(NumItems+NumTombstones) < NumBuckets/8) { 188aea4fe2862ce17acc6ce943df589ee8d5eb05adfJakob Stoklund Olesen NewSize = NumBuckets; 189aea4fe2862ce17acc6ce943df589ee8d5eb05adfJakob Stoklund Olesen } else { 190aea4fe2862ce17acc6ce943df589ee8d5eb05adfJakob Stoklund Olesen return; 191aea4fe2862ce17acc6ce943df589ee8d5eb05adfJakob Stoklund Olesen } 192aea4fe2862ce17acc6ce943df589ee8d5eb05adfJakob Stoklund Olesen 193a86559ec426c643a151aeba1e051e4f878050f95Chris Lattner // Allocate one extra bucket which will always be non-empty. This allows the 194a86559ec426c643a151aeba1e051e4f878050f95Chris Lattner // iterators to stop at end. 195d2f197da59a3c937c1809997907918c029f9f884Chris Lattner ItemBucket *NewTableArray =(ItemBucket*)calloc(NewSize+1, sizeof(ItemBucket)); 196a86559ec426c643a151aeba1e051e4f878050f95Chris Lattner NewTableArray[NewSize].Item = (StringMapEntryBase*)2; 19723d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner 19823d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner // Rehash all the items into their new buckets. Luckily :) we already have 19923d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner // the hash values available, so we don't have to rehash any strings. 20023d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner for (ItemBucket *IB = TheTable, *E = TheTable+NumBuckets; IB != E; ++IB) { 20144dcd01cb3424420d79d5811fa8c1c052411f975Chris Lattner if (IB->Item && IB->Item != getTombstoneVal()) { 20223d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner // Fast case, bucket available. 20323d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner unsigned FullHash = IB->FullHashValue; 20423d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner unsigned NewBucket = FullHash & (NewSize-1); 20523d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner if (NewTableArray[NewBucket].Item == 0) { 20623d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner NewTableArray[FullHash & (NewSize-1)].Item = IB->Item; 20723d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner NewTableArray[FullHash & (NewSize-1)].FullHashValue = FullHash; 20823d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner continue; 20923d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner } 21023d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner 21144dcd01cb3424420d79d5811fa8c1c052411f975Chris Lattner // Otherwise probe for a spot. 21223d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner unsigned ProbeSize = 1; 21323d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner do { 21423d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner NewBucket = (NewBucket + ProbeSize++) & (NewSize-1); 21523d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner } while (NewTableArray[NewBucket].Item); 21623d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner 21723d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner // Finally found a slot. Fill it in. 21823d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner NewTableArray[NewBucket].Item = IB->Item; 21923d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner NewTableArray[NewBucket].FullHashValue = FullHash; 22023d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner } 22123d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner } 22223d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner 22312ba806c5d9ab0b45e41d7dc3d7af235f87d5e7eChris Lattner free(TheTable); 22423d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner 22523d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner TheTable = NewTableArray; 22623d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner NumBuckets = NewSize; 22723d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner} 228