StringMap.cpp revision d2f197da59a3c937c1809997907918c029f9f884
1bb28a81ba3c112853f0eb3d8df0190accc0379c9Chris Lattner//===--- StringMap.cpp - String Hash table map implementation -------------===// 223d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner// 323d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner// The LLVM Compiler Infrastructure 423d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner// 523d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner// This file was developed by Chris Lattner and is distributed under 623d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner// the University of Illinois Open Source 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" 1523d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner#include <cassert> 1623d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattnerusing namespace llvm; 1723d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner 18bb28a81ba3c112853f0eb3d8df0190accc0379c9Chris LattnerStringMapImpl::StringMapImpl(unsigned InitSize, unsigned itemSize) { 19794a014809d810b7ee9a96be76774185561f0dccChris Lattner ItemSize = itemSize; 20794a014809d810b7ee9a96be76774185561f0dccChris Lattner 21794a014809d810b7ee9a96be76774185561f0dccChris Lattner // If a size is specified, initialize the table with that many buckets. 22794a014809d810b7ee9a96be76774185561f0dccChris Lattner if (InitSize) { 23794a014809d810b7ee9a96be76774185561f0dccChris Lattner init(InitSize); 24794a014809d810b7ee9a96be76774185561f0dccChris Lattner return; 25794a014809d810b7ee9a96be76774185561f0dccChris Lattner } 26794a014809d810b7ee9a96be76774185561f0dccChris Lattner 27794a014809d810b7ee9a96be76774185561f0dccChris Lattner // Otherwise, initialize it with zero buckets to avoid the allocation. 28794a014809d810b7ee9a96be76774185561f0dccChris Lattner TheTable = 0; 29794a014809d810b7ee9a96be76774185561f0dccChris Lattner NumBuckets = 0; 30794a014809d810b7ee9a96be76774185561f0dccChris Lattner NumItems = 0; 31794a014809d810b7ee9a96be76774185561f0dccChris Lattner NumTombstones = 0; 32794a014809d810b7ee9a96be76774185561f0dccChris Lattner} 33794a014809d810b7ee9a96be76774185561f0dccChris Lattner 34794a014809d810b7ee9a96be76774185561f0dccChris Lattnervoid StringMapImpl::init(unsigned InitSize) { 3523d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner assert((InitSize & (InitSize-1)) == 0 && 3623d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner "Init Size must be a power of 2 or zero!"); 37ef4c916193e49e20c492f73147b3872b01c23862Chris Lattner NumBuckets = InitSize ? InitSize : 16; 3823d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner NumItems = 0; 3944dcd01cb3424420d79d5811fa8c1c052411f975Chris Lattner NumTombstones = 0; 4023d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner 41d2f197da59a3c937c1809997907918c029f9f884Chris Lattner TheTable = (ItemBucket*)calloc(NumBuckets+1, sizeof(ItemBucket)); 42a86559ec426c643a151aeba1e051e4f878050f95Chris Lattner 43a86559ec426c643a151aeba1e051e4f878050f95Chris Lattner // Allocate one extra bucket, set it to look filled so the iterators stop at 44a86559ec426c643a151aeba1e051e4f878050f95Chris Lattner // end. 45a86559ec426c643a151aeba1e051e4f878050f95Chris Lattner TheTable[NumBuckets].Item = (StringMapEntryBase*)2; 4623d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner} 4723d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner 4823d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner 4923d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner/// HashString - Compute a hash code for the specified string. 5023d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner/// 5123d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattnerstatic unsigned HashString(const char *Start, const char *End) { 5238742b9603858db660cbb6b67853ca9266eaa196Chris Lattner // Bernstein hash function. 5323d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner unsigned int Result = 0; 5438742b9603858db660cbb6b67853ca9266eaa196Chris Lattner // TODO: investigate whether a modified bernstein hash function performs 5541a4429f6586ce648ba29fbd33bfed433005c3daChris Lattner // better: http://eternallyconfuzzled.com/tuts/algorithms/jsw_tut_hashing.aspx 5638742b9603858db660cbb6b67853ca9266eaa196Chris Lattner // X*33+c -> X*33^c 5723d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner while (Start != End) 5823d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner Result = Result * 33 + *Start++; 5923d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner Result = Result + (Result >> 5); 6023d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner return Result; 6123d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner} 6223d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner 6323d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner/// LookupBucketFor - Look up the bucket that the specified string should end 6423d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner/// up in. If it already exists as a key in the map, the Item pointer for the 6523d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner/// specified bucket will be non-null. Otherwise, it will be null. In either 6623d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner/// case, the FullHashValue field of the bucket will be set to the hash value 6723d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner/// of the string. 68bb28a81ba3c112853f0eb3d8df0190accc0379c9Chris Lattnerunsigned StringMapImpl::LookupBucketFor(const char *NameStart, 69794a014809d810b7ee9a96be76774185561f0dccChris Lattner const char *NameEnd) { 7023d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner unsigned HTSize = NumBuckets; 71794a014809d810b7ee9a96be76774185561f0dccChris Lattner if (HTSize == 0) { // Hash table unallocated so far? 72794a014809d810b7ee9a96be76774185561f0dccChris Lattner init(16); 73794a014809d810b7ee9a96be76774185561f0dccChris Lattner HTSize = NumBuckets; 74794a014809d810b7ee9a96be76774185561f0dccChris Lattner } 7523d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner unsigned FullHashValue = HashString(NameStart, NameEnd); 7623d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner unsigned BucketNo = FullHashValue & (HTSize-1); 7723d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner 7823d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner unsigned ProbeAmt = 1; 7944dcd01cb3424420d79d5811fa8c1c052411f975Chris Lattner int FirstTombstone = -1; 8023d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner while (1) { 8123d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner ItemBucket &Bucket = TheTable[BucketNo]; 82ee182422ff0b638b17c5ee802c19b8680107c2bbChris Lattner StringMapEntryBase *BucketItem = Bucket.Item; 8323d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner // If we found an empty bucket, this key isn't in the table yet, return it. 8423d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner if (BucketItem == 0) { 8544dcd01cb3424420d79d5811fa8c1c052411f975Chris Lattner // If we found a tombstone, we want to reuse the tombstone instead of an 8644dcd01cb3424420d79d5811fa8c1c052411f975Chris Lattner // empty bucket. This reduces probing. 8744dcd01cb3424420d79d5811fa8c1c052411f975Chris Lattner if (FirstTombstone != -1) { 8844dcd01cb3424420d79d5811fa8c1c052411f975Chris Lattner TheTable[FirstTombstone].FullHashValue = FullHashValue; 8944dcd01cb3424420d79d5811fa8c1c052411f975Chris Lattner return FirstTombstone; 9044dcd01cb3424420d79d5811fa8c1c052411f975Chris Lattner } 9144dcd01cb3424420d79d5811fa8c1c052411f975Chris Lattner 9223d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner Bucket.FullHashValue = FullHashValue; 9323d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner return BucketNo; 9423d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner } 9523d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner 9644dcd01cb3424420d79d5811fa8c1c052411f975Chris Lattner if (BucketItem == getTombstoneVal()) { 9744dcd01cb3424420d79d5811fa8c1c052411f975Chris Lattner // Skip over tombstones. However, remember the first one we see. 9844dcd01cb3424420d79d5811fa8c1c052411f975Chris Lattner if (FirstTombstone == -1) FirstTombstone = BucketNo; 9944dcd01cb3424420d79d5811fa8c1c052411f975Chris Lattner } else if (Bucket.FullHashValue == FullHashValue) { 10044dcd01cb3424420d79d5811fa8c1c052411f975Chris Lattner // If the full hash value matches, check deeply for a match. The common 10144dcd01cb3424420d79d5811fa8c1c052411f975Chris Lattner // case here is that we are only looking at the buckets (for item info 10244dcd01cb3424420d79d5811fa8c1c052411f975Chris Lattner // being non-null and for the full hash value) not at the items. This 10344dcd01cb3424420d79d5811fa8c1c052411f975Chris Lattner // is important for cache locality. 10444dcd01cb3424420d79d5811fa8c1c052411f975Chris Lattner 10523d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner // Do the comparison like this because NameStart isn't necessarily 10623d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner // null-terminated! 10723d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner char *ItemStr = (char*)BucketItem+ItemSize; 108ee182422ff0b638b17c5ee802c19b8680107c2bbChris Lattner unsigned ItemStrLen = BucketItem->getKeyLength(); 109ee182422ff0b638b17c5ee802c19b8680107c2bbChris Lattner if (unsigned(NameEnd-NameStart) == ItemStrLen && 110ee182422ff0b638b17c5ee802c19b8680107c2bbChris Lattner memcmp(ItemStr, NameStart, ItemStrLen) == 0) { 11123d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner // We found a match! 11223d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner return BucketNo; 11323d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner } 11423d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner } 11523d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner 11623d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner // Okay, we didn't find the item. Probe to the next bucket. 11723d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner BucketNo = (BucketNo+ProbeAmt) & (HTSize-1); 11823d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner 11923d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner // Use quadratic probing, it has fewer clumping artifacts than linear 12023d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner // probing and has good cache behavior in the common case. 12123d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner ++ProbeAmt; 12223d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner } 12323d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner} 12423d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner 125b5bb9f5b5cfe89f4b7626671f4923d50f8d4cd6aChris Lattner 126b5bb9f5b5cfe89f4b7626671f4923d50f8d4cd6aChris Lattner/// FindKey - Look up the bucket that contains the specified key. If it exists 127b5bb9f5b5cfe89f4b7626671f4923d50f8d4cd6aChris Lattner/// in the map, return the bucket number of the key. Otherwise return -1. 128b5bb9f5b5cfe89f4b7626671f4923d50f8d4cd6aChris Lattner/// This does not modify the map. 129b5bb9f5b5cfe89f4b7626671f4923d50f8d4cd6aChris Lattnerint StringMapImpl::FindKey(const char *KeyStart, const char *KeyEnd) const { 130b5bb9f5b5cfe89f4b7626671f4923d50f8d4cd6aChris Lattner unsigned HTSize = NumBuckets; 131794a014809d810b7ee9a96be76774185561f0dccChris Lattner if (HTSize == 0) return -1; // Really empty table? 132b5bb9f5b5cfe89f4b7626671f4923d50f8d4cd6aChris Lattner unsigned FullHashValue = HashString(KeyStart, KeyEnd); 133b5bb9f5b5cfe89f4b7626671f4923d50f8d4cd6aChris Lattner unsigned BucketNo = FullHashValue & (HTSize-1); 134b5bb9f5b5cfe89f4b7626671f4923d50f8d4cd6aChris Lattner 135b5bb9f5b5cfe89f4b7626671f4923d50f8d4cd6aChris Lattner unsigned ProbeAmt = 1; 136b5bb9f5b5cfe89f4b7626671f4923d50f8d4cd6aChris Lattner while (1) { 137b5bb9f5b5cfe89f4b7626671f4923d50f8d4cd6aChris Lattner ItemBucket &Bucket = TheTable[BucketNo]; 138b5bb9f5b5cfe89f4b7626671f4923d50f8d4cd6aChris Lattner StringMapEntryBase *BucketItem = Bucket.Item; 139b5bb9f5b5cfe89f4b7626671f4923d50f8d4cd6aChris Lattner // If we found an empty bucket, this key isn't in the table yet, return. 140b5bb9f5b5cfe89f4b7626671f4923d50f8d4cd6aChris Lattner if (BucketItem == 0) 141b5bb9f5b5cfe89f4b7626671f4923d50f8d4cd6aChris Lattner return -1; 142b5bb9f5b5cfe89f4b7626671f4923d50f8d4cd6aChris Lattner 14344dcd01cb3424420d79d5811fa8c1c052411f975Chris Lattner if (BucketItem == getTombstoneVal()) { 14444dcd01cb3424420d79d5811fa8c1c052411f975Chris Lattner // Ignore tombstones. 14544dcd01cb3424420d79d5811fa8c1c052411f975Chris Lattner } else if (Bucket.FullHashValue == FullHashValue) { 14644dcd01cb3424420d79d5811fa8c1c052411f975Chris Lattner // If the full hash value matches, check deeply for a match. The common 14744dcd01cb3424420d79d5811fa8c1c052411f975Chris Lattner // case here is that we are only looking at the buckets (for item info 14844dcd01cb3424420d79d5811fa8c1c052411f975Chris Lattner // being non-null and for the full hash value) not at the items. This 14944dcd01cb3424420d79d5811fa8c1c052411f975Chris Lattner // is important for cache locality. 15044dcd01cb3424420d79d5811fa8c1c052411f975Chris Lattner 151b5bb9f5b5cfe89f4b7626671f4923d50f8d4cd6aChris Lattner // Do the comparison like this because NameStart isn't necessarily 152b5bb9f5b5cfe89f4b7626671f4923d50f8d4cd6aChris Lattner // null-terminated! 153b5bb9f5b5cfe89f4b7626671f4923d50f8d4cd6aChris Lattner char *ItemStr = (char*)BucketItem+ItemSize; 154b5bb9f5b5cfe89f4b7626671f4923d50f8d4cd6aChris Lattner unsigned ItemStrLen = BucketItem->getKeyLength(); 155b5bb9f5b5cfe89f4b7626671f4923d50f8d4cd6aChris Lattner if (unsigned(KeyEnd-KeyStart) == ItemStrLen && 156b5bb9f5b5cfe89f4b7626671f4923d50f8d4cd6aChris Lattner memcmp(ItemStr, KeyStart, ItemStrLen) == 0) { 157b5bb9f5b5cfe89f4b7626671f4923d50f8d4cd6aChris Lattner // We found a match! 158b5bb9f5b5cfe89f4b7626671f4923d50f8d4cd6aChris Lattner return BucketNo; 159b5bb9f5b5cfe89f4b7626671f4923d50f8d4cd6aChris Lattner } 160b5bb9f5b5cfe89f4b7626671f4923d50f8d4cd6aChris Lattner } 161b5bb9f5b5cfe89f4b7626671f4923d50f8d4cd6aChris Lattner 162b5bb9f5b5cfe89f4b7626671f4923d50f8d4cd6aChris Lattner // Okay, we didn't find the item. Probe to the next bucket. 163b5bb9f5b5cfe89f4b7626671f4923d50f8d4cd6aChris Lattner BucketNo = (BucketNo+ProbeAmt) & (HTSize-1); 164b5bb9f5b5cfe89f4b7626671f4923d50f8d4cd6aChris Lattner 165b5bb9f5b5cfe89f4b7626671f4923d50f8d4cd6aChris Lattner // Use quadratic probing, it has fewer clumping artifacts than linear 166b5bb9f5b5cfe89f4b7626671f4923d50f8d4cd6aChris Lattner // probing and has good cache behavior in the common case. 167b5bb9f5b5cfe89f4b7626671f4923d50f8d4cd6aChris Lattner ++ProbeAmt; 168b5bb9f5b5cfe89f4b7626671f4923d50f8d4cd6aChris Lattner } 169b5bb9f5b5cfe89f4b7626671f4923d50f8d4cd6aChris Lattner} 170b5bb9f5b5cfe89f4b7626671f4923d50f8d4cd6aChris Lattner 17144dcd01cb3424420d79d5811fa8c1c052411f975Chris Lattner/// RemoveKey - Remove the specified StringMapEntry from the table, but do not 17244dcd01cb3424420d79d5811fa8c1c052411f975Chris Lattner/// delete it. This aborts if the value isn't in the table. 17344dcd01cb3424420d79d5811fa8c1c052411f975Chris Lattnervoid StringMapImpl::RemoveKey(StringMapEntryBase *V) { 17444dcd01cb3424420d79d5811fa8c1c052411f975Chris Lattner const char *VStr = (char*)V + ItemSize; 17544dcd01cb3424420d79d5811fa8c1c052411f975Chris Lattner StringMapEntryBase *V2 = RemoveKey(VStr, VStr+V->getKeyLength()); 17644dcd01cb3424420d79d5811fa8c1c052411f975Chris Lattner V2 = V2; 17744dcd01cb3424420d79d5811fa8c1c052411f975Chris Lattner assert(V == V2 && "Didn't find key?"); 17844dcd01cb3424420d79d5811fa8c1c052411f975Chris Lattner} 17944dcd01cb3424420d79d5811fa8c1c052411f975Chris Lattner 18044dcd01cb3424420d79d5811fa8c1c052411f975Chris Lattner/// RemoveKey - Remove the StringMapEntry for the specified key from the 18144dcd01cb3424420d79d5811fa8c1c052411f975Chris Lattner/// table, returning it. If the key is not in the table, this returns null. 18244dcd01cb3424420d79d5811fa8c1c052411f975Chris LattnerStringMapEntryBase *StringMapImpl::RemoveKey(const char *KeyStart, 18344dcd01cb3424420d79d5811fa8c1c052411f975Chris Lattner const char *KeyEnd) { 18444dcd01cb3424420d79d5811fa8c1c052411f975Chris Lattner int Bucket = FindKey(KeyStart, KeyEnd); 18544dcd01cb3424420d79d5811fa8c1c052411f975Chris Lattner if (Bucket == -1) return 0; 18644dcd01cb3424420d79d5811fa8c1c052411f975Chris Lattner 18744dcd01cb3424420d79d5811fa8c1c052411f975Chris Lattner StringMapEntryBase *Result = TheTable[Bucket].Item; 18844dcd01cb3424420d79d5811fa8c1c052411f975Chris Lattner TheTable[Bucket].Item = getTombstoneVal(); 18944dcd01cb3424420d79d5811fa8c1c052411f975Chris Lattner --NumItems; 19044dcd01cb3424420d79d5811fa8c1c052411f975Chris Lattner ++NumTombstones; 19144dcd01cb3424420d79d5811fa8c1c052411f975Chris Lattner return Result; 19244dcd01cb3424420d79d5811fa8c1c052411f975Chris Lattner} 19344dcd01cb3424420d79d5811fa8c1c052411f975Chris Lattner 19444dcd01cb3424420d79d5811fa8c1c052411f975Chris Lattner 195b5bb9f5b5cfe89f4b7626671f4923d50f8d4cd6aChris Lattner 19623d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner/// RehashTable - Grow the table, redistributing values into the buckets with 19723d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner/// the appropriate mod-of-hashtable-size. 198bb28a81ba3c112853f0eb3d8df0190accc0379c9Chris Lattnervoid StringMapImpl::RehashTable() { 19923d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner unsigned NewSize = NumBuckets*2; 200a86559ec426c643a151aeba1e051e4f878050f95Chris Lattner // Allocate one extra bucket which will always be non-empty. This allows the 201a86559ec426c643a151aeba1e051e4f878050f95Chris Lattner // iterators to stop at end. 202d2f197da59a3c937c1809997907918c029f9f884Chris Lattner ItemBucket *NewTableArray =(ItemBucket*)calloc(NewSize+1, sizeof(ItemBucket)); 203a86559ec426c643a151aeba1e051e4f878050f95Chris Lattner NewTableArray[NewSize].Item = (StringMapEntryBase*)2; 20423d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner 20523d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner // Rehash all the items into their new buckets. Luckily :) we already have 20623d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner // the hash values available, so we don't have to rehash any strings. 20723d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner for (ItemBucket *IB = TheTable, *E = TheTable+NumBuckets; IB != E; ++IB) { 20844dcd01cb3424420d79d5811fa8c1c052411f975Chris Lattner if (IB->Item && IB->Item != getTombstoneVal()) { 20923d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner // Fast case, bucket available. 21023d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner unsigned FullHash = IB->FullHashValue; 21123d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner unsigned NewBucket = FullHash & (NewSize-1); 21223d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner if (NewTableArray[NewBucket].Item == 0) { 21323d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner NewTableArray[FullHash & (NewSize-1)].Item = IB->Item; 21423d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner NewTableArray[FullHash & (NewSize-1)].FullHashValue = FullHash; 21523d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner continue; 21623d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner } 21723d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner 21844dcd01cb3424420d79d5811fa8c1c052411f975Chris Lattner // Otherwise probe for a spot. 21923d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner unsigned ProbeSize = 1; 22023d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner do { 22123d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner NewBucket = (NewBucket + ProbeSize++) & (NewSize-1); 22223d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner } while (NewTableArray[NewBucket].Item); 22323d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner 22423d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner // Finally found a slot. Fill it in. 22523d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner NewTableArray[NewBucket].Item = IB->Item; 22623d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner NewTableArray[NewBucket].FullHashValue = FullHash; 22723d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner } 22823d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner } 22923d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner 23023d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner delete[] TheTable; 23123d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner 23223d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner TheTable = NewTableArray; 23323d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner NumBuckets = NewSize; 23423d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner} 235