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" 16e160c53fbef056a3f121eeebcb7074f780bfae52Benjamin Kramer#include "llvm/Support/Compiler.h" 1723d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner#include <cassert> 1823d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattnerusing namespace llvm; 1923d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner 20bb28a81ba3c112853f0eb3d8df0190accc0379c9Chris LattnerStringMapImpl::StringMapImpl(unsigned InitSize, unsigned itemSize) { 21794a014809d810b7ee9a96be76774185561f0dccChris Lattner ItemSize = itemSize; 22794a014809d810b7ee9a96be76774185561f0dccChris Lattner 23794a014809d810b7ee9a96be76774185561f0dccChris Lattner // If a size is specified, initialize the table with that many buckets. 24794a014809d810b7ee9a96be76774185561f0dccChris Lattner if (InitSize) { 25794a014809d810b7ee9a96be76774185561f0dccChris Lattner init(InitSize); 26794a014809d810b7ee9a96be76774185561f0dccChris Lattner return; 27794a014809d810b7ee9a96be76774185561f0dccChris Lattner } 28794a014809d810b7ee9a96be76774185561f0dccChris Lattner 29794a014809d810b7ee9a96be76774185561f0dccChris Lattner // Otherwise, initialize it with zero buckets to avoid the allocation. 30dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines TheTable = nullptr; 31794a014809d810b7ee9a96be76774185561f0dccChris Lattner NumBuckets = 0; 32794a014809d810b7ee9a96be76774185561f0dccChris Lattner NumItems = 0; 33794a014809d810b7ee9a96be76774185561f0dccChris Lattner NumTombstones = 0; 34794a014809d810b7ee9a96be76774185561f0dccChris Lattner} 35794a014809d810b7ee9a96be76774185561f0dccChris Lattner 36794a014809d810b7ee9a96be76774185561f0dccChris Lattnervoid StringMapImpl::init(unsigned InitSize) { 3723d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner assert((InitSize & (InitSize-1)) == 0 && 3823d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner "Init Size must be a power of 2 or zero!"); 39ef4c916193e49e20c492f73147b3872b01c23862Chris Lattner NumBuckets = InitSize ? InitSize : 16; 4023d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner NumItems = 0; 4144dcd01cb3424420d79d5811fa8c1c052411f975Chris Lattner NumTombstones = 0; 4223d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner 43c894b02ae037b5fdb38e42535539d5a0e49d6c41Benjamin Kramer TheTable = (StringMapEntryBase **)calloc(NumBuckets+1, 44c894b02ae037b5fdb38e42535539d5a0e49d6c41Benjamin Kramer sizeof(StringMapEntryBase **) + 45c894b02ae037b5fdb38e42535539d5a0e49d6c41Benjamin Kramer sizeof(unsigned)); 46c894b02ae037b5fdb38e42535539d5a0e49d6c41Benjamin Kramer 47a86559ec426c643a151aeba1e051e4f878050f95Chris Lattner // Allocate one extra bucket, set it to look filled so the iterators stop at 48a86559ec426c643a151aeba1e051e4f878050f95Chris Lattner // end. 49c894b02ae037b5fdb38e42535539d5a0e49d6c41Benjamin Kramer TheTable[NumBuckets] = (StringMapEntryBase*)2; 5023d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner} 5123d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner 5223d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner 5323d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner/// LookupBucketFor - Look up the bucket that the specified string should end 5423d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner/// up in. If it already exists as a key in the map, the Item pointer for the 5523d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner/// specified bucket will be non-null. Otherwise, it will be null. In either 5623d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner/// case, the FullHashValue field of the bucket will be set to the hash value 5723d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner/// of the string. 582928c83b010f7cfdb0f819199d806f6942a7d995Daniel Dunbarunsigned StringMapImpl::LookupBucketFor(StringRef Name) { 5923d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner unsigned HTSize = NumBuckets; 60794a014809d810b7ee9a96be76774185561f0dccChris Lattner if (HTSize == 0) { // Hash table unallocated so far? 61794a014809d810b7ee9a96be76774185561f0dccChris Lattner init(16); 62794a014809d810b7ee9a96be76774185561f0dccChris Lattner HTSize = NumBuckets; 63794a014809d810b7ee9a96be76774185561f0dccChris Lattner } 644dee7fd2c2cb3fabddf99a184abe41dbc0bd4085Daniel Dunbar unsigned FullHashValue = HashString(Name); 6523d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner unsigned BucketNo = FullHashValue & (HTSize-1); 66c894b02ae037b5fdb38e42535539d5a0e49d6c41Benjamin Kramer unsigned *HashTable = (unsigned *)(TheTable + NumBuckets + 1); 67c894b02ae037b5fdb38e42535539d5a0e49d6c41Benjamin Kramer 6823d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner unsigned ProbeAmt = 1; 6944dcd01cb3424420d79d5811fa8c1c052411f975Chris Lattner int FirstTombstone = -1; 7023d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner while (1) { 71c894b02ae037b5fdb38e42535539d5a0e49d6c41Benjamin Kramer StringMapEntryBase *BucketItem = TheTable[BucketNo]; 7223d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner // If we found an empty bucket, this key isn't in the table yet, return it. 73dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines if (LLVM_LIKELY(!BucketItem)) { 7444dcd01cb3424420d79d5811fa8c1c052411f975Chris Lattner // If we found a tombstone, we want to reuse the tombstone instead of an 7544dcd01cb3424420d79d5811fa8c1c052411f975Chris Lattner // empty bucket. This reduces probing. 7644dcd01cb3424420d79d5811fa8c1c052411f975Chris Lattner if (FirstTombstone != -1) { 77c894b02ae037b5fdb38e42535539d5a0e49d6c41Benjamin Kramer HashTable[FirstTombstone] = FullHashValue; 7844dcd01cb3424420d79d5811fa8c1c052411f975Chris Lattner return FirstTombstone; 7944dcd01cb3424420d79d5811fa8c1c052411f975Chris Lattner } 8044dcd01cb3424420d79d5811fa8c1c052411f975Chris Lattner 81c894b02ae037b5fdb38e42535539d5a0e49d6c41Benjamin Kramer HashTable[BucketNo] = FullHashValue; 8223d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner return BucketNo; 8323d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner } 8423d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner 8544dcd01cb3424420d79d5811fa8c1c052411f975Chris Lattner if (BucketItem == getTombstoneVal()) { 8644dcd01cb3424420d79d5811fa8c1c052411f975Chris Lattner // Skip over tombstones. However, remember the first one we see. 8744dcd01cb3424420d79d5811fa8c1c052411f975Chris Lattner if (FirstTombstone == -1) FirstTombstone = BucketNo; 88e160c53fbef056a3f121eeebcb7074f780bfae52Benjamin Kramer } else if (LLVM_LIKELY(HashTable[BucketNo] == FullHashValue)) { 8944dcd01cb3424420d79d5811fa8c1c052411f975Chris Lattner // If the full hash value matches, check deeply for a match. The common 9044dcd01cb3424420d79d5811fa8c1c052411f975Chris Lattner // case here is that we are only looking at the buckets (for item info 9144dcd01cb3424420d79d5811fa8c1c052411f975Chris Lattner // being non-null and for the full hash value) not at the items. This 9244dcd01cb3424420d79d5811fa8c1c052411f975Chris Lattner // is important for cache locality. 9344dcd01cb3424420d79d5811fa8c1c052411f975Chris Lattner 946316fbcb04af00fe76b6526fab09f51484014b3eDaniel Dunbar // Do the comparison like this because Name isn't necessarily 9523d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner // null-terminated! 9623d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner char *ItemStr = (char*)BucketItem+ItemSize; 976316fbcb04af00fe76b6526fab09f51484014b3eDaniel Dunbar if (Name == StringRef(ItemStr, BucketItem->getKeyLength())) { 9823d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner // We found a match! 9923d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner return BucketNo; 10023d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner } 10123d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner } 10223d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner 10323d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner // Okay, we didn't find the item. Probe to the next bucket. 10423d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner BucketNo = (BucketNo+ProbeAmt) & (HTSize-1); 10523d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner 10623d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner // Use quadratic probing, it has fewer clumping artifacts than linear 10723d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner // probing and has good cache behavior in the common case. 10823d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner ++ProbeAmt; 10923d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner } 11023d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner} 11123d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner 112b5bb9f5b5cfe89f4b7626671f4923d50f8d4cd6aChris Lattner 113b5bb9f5b5cfe89f4b7626671f4923d50f8d4cd6aChris Lattner/// FindKey - Look up the bucket that contains the specified key. If it exists 114b5bb9f5b5cfe89f4b7626671f4923d50f8d4cd6aChris Lattner/// in the map, return the bucket number of the key. Otherwise return -1. 115b5bb9f5b5cfe89f4b7626671f4923d50f8d4cd6aChris Lattner/// This does not modify the map. 1162928c83b010f7cfdb0f819199d806f6942a7d995Daniel Dunbarint StringMapImpl::FindKey(StringRef Key) const { 117b5bb9f5b5cfe89f4b7626671f4923d50f8d4cd6aChris Lattner unsigned HTSize = NumBuckets; 118794a014809d810b7ee9a96be76774185561f0dccChris Lattner if (HTSize == 0) return -1; // Really empty table? 1194dee7fd2c2cb3fabddf99a184abe41dbc0bd4085Daniel Dunbar unsigned FullHashValue = HashString(Key); 120b5bb9f5b5cfe89f4b7626671f4923d50f8d4cd6aChris Lattner unsigned BucketNo = FullHashValue & (HTSize-1); 121c894b02ae037b5fdb38e42535539d5a0e49d6c41Benjamin Kramer unsigned *HashTable = (unsigned *)(TheTable + NumBuckets + 1); 122c894b02ae037b5fdb38e42535539d5a0e49d6c41Benjamin Kramer 123b5bb9f5b5cfe89f4b7626671f4923d50f8d4cd6aChris Lattner unsigned ProbeAmt = 1; 124b5bb9f5b5cfe89f4b7626671f4923d50f8d4cd6aChris Lattner while (1) { 125c894b02ae037b5fdb38e42535539d5a0e49d6c41Benjamin Kramer StringMapEntryBase *BucketItem = TheTable[BucketNo]; 126b5bb9f5b5cfe89f4b7626671f4923d50f8d4cd6aChris Lattner // If we found an empty bucket, this key isn't in the table yet, return. 127dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines if (LLVM_LIKELY(!BucketItem)) 128b5bb9f5b5cfe89f4b7626671f4923d50f8d4cd6aChris Lattner return -1; 129b5bb9f5b5cfe89f4b7626671f4923d50f8d4cd6aChris Lattner 13044dcd01cb3424420d79d5811fa8c1c052411f975Chris Lattner if (BucketItem == getTombstoneVal()) { 13144dcd01cb3424420d79d5811fa8c1c052411f975Chris Lattner // Ignore tombstones. 132e160c53fbef056a3f121eeebcb7074f780bfae52Benjamin Kramer } else if (LLVM_LIKELY(HashTable[BucketNo] == FullHashValue)) { 13344dcd01cb3424420d79d5811fa8c1c052411f975Chris Lattner // If the full hash value matches, check deeply for a match. The common 13444dcd01cb3424420d79d5811fa8c1c052411f975Chris Lattner // case here is that we are only looking at the buckets (for item info 13544dcd01cb3424420d79d5811fa8c1c052411f975Chris Lattner // being non-null and for the full hash value) not at the items. This 13644dcd01cb3424420d79d5811fa8c1c052411f975Chris Lattner // is important for cache locality. 13744dcd01cb3424420d79d5811fa8c1c052411f975Chris Lattner 138b5bb9f5b5cfe89f4b7626671f4923d50f8d4cd6aChris Lattner // Do the comparison like this because NameStart isn't necessarily 139b5bb9f5b5cfe89f4b7626671f4923d50f8d4cd6aChris Lattner // null-terminated! 140b5bb9f5b5cfe89f4b7626671f4923d50f8d4cd6aChris Lattner char *ItemStr = (char*)BucketItem+ItemSize; 1416316fbcb04af00fe76b6526fab09f51484014b3eDaniel Dunbar if (Key == StringRef(ItemStr, BucketItem->getKeyLength())) { 142b5bb9f5b5cfe89f4b7626671f4923d50f8d4cd6aChris Lattner // We found a match! 143b5bb9f5b5cfe89f4b7626671f4923d50f8d4cd6aChris Lattner return BucketNo; 144b5bb9f5b5cfe89f4b7626671f4923d50f8d4cd6aChris Lattner } 145b5bb9f5b5cfe89f4b7626671f4923d50f8d4cd6aChris Lattner } 146b5bb9f5b5cfe89f4b7626671f4923d50f8d4cd6aChris Lattner 147b5bb9f5b5cfe89f4b7626671f4923d50f8d4cd6aChris Lattner // Okay, we didn't find the item. Probe to the next bucket. 148b5bb9f5b5cfe89f4b7626671f4923d50f8d4cd6aChris Lattner BucketNo = (BucketNo+ProbeAmt) & (HTSize-1); 149b5bb9f5b5cfe89f4b7626671f4923d50f8d4cd6aChris Lattner 150b5bb9f5b5cfe89f4b7626671f4923d50f8d4cd6aChris Lattner // Use quadratic probing, it has fewer clumping artifacts than linear 151b5bb9f5b5cfe89f4b7626671f4923d50f8d4cd6aChris Lattner // probing and has good cache behavior in the common case. 152b5bb9f5b5cfe89f4b7626671f4923d50f8d4cd6aChris Lattner ++ProbeAmt; 153b5bb9f5b5cfe89f4b7626671f4923d50f8d4cd6aChris Lattner } 154b5bb9f5b5cfe89f4b7626671f4923d50f8d4cd6aChris Lattner} 155b5bb9f5b5cfe89f4b7626671f4923d50f8d4cd6aChris Lattner 15644dcd01cb3424420d79d5811fa8c1c052411f975Chris Lattner/// RemoveKey - Remove the specified StringMapEntry from the table, but do not 15744dcd01cb3424420d79d5811fa8c1c052411f975Chris Lattner/// delete it. This aborts if the value isn't in the table. 15844dcd01cb3424420d79d5811fa8c1c052411f975Chris Lattnervoid StringMapImpl::RemoveKey(StringMapEntryBase *V) { 15944dcd01cb3424420d79d5811fa8c1c052411f975Chris Lattner const char *VStr = (char*)V + ItemSize; 1606316fbcb04af00fe76b6526fab09f51484014b3eDaniel Dunbar StringMapEntryBase *V2 = RemoveKey(StringRef(VStr, V->getKeyLength())); 1618e68c3873549ca31533e2e3e40dda3a43cb79566Jeffrey Yasskin (void)V2; 16244dcd01cb3424420d79d5811fa8c1c052411f975Chris Lattner assert(V == V2 && "Didn't find key?"); 16344dcd01cb3424420d79d5811fa8c1c052411f975Chris Lattner} 16444dcd01cb3424420d79d5811fa8c1c052411f975Chris Lattner 16544dcd01cb3424420d79d5811fa8c1c052411f975Chris Lattner/// RemoveKey - Remove the StringMapEntry for the specified key from the 16644dcd01cb3424420d79d5811fa8c1c052411f975Chris Lattner/// table, returning it. If the key is not in the table, this returns null. 1672928c83b010f7cfdb0f819199d806f6942a7d995Daniel DunbarStringMapEntryBase *StringMapImpl::RemoveKey(StringRef Key) { 1686316fbcb04af00fe76b6526fab09f51484014b3eDaniel Dunbar int Bucket = FindKey(Key); 169dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines if (Bucket == -1) return nullptr; 17044dcd01cb3424420d79d5811fa8c1c052411f975Chris Lattner 171c894b02ae037b5fdb38e42535539d5a0e49d6c41Benjamin Kramer StringMapEntryBase *Result = TheTable[Bucket]; 172c894b02ae037b5fdb38e42535539d5a0e49d6c41Benjamin Kramer TheTable[Bucket] = getTombstoneVal(); 17344dcd01cb3424420d79d5811fa8c1c052411f975Chris Lattner --NumItems; 17444dcd01cb3424420d79d5811fa8c1c052411f975Chris Lattner ++NumTombstones; 17503ef44991768b803ed5b210877ce0d83bf16fd93Jakob Stoklund Olesen assert(NumItems + NumTombstones <= NumBuckets); 17603ef44991768b803ed5b210877ce0d83bf16fd93Jakob Stoklund Olesen 17744dcd01cb3424420d79d5811fa8c1c052411f975Chris Lattner return Result; 17844dcd01cb3424420d79d5811fa8c1c052411f975Chris Lattner} 17944dcd01cb3424420d79d5811fa8c1c052411f975Chris Lattner 18044dcd01cb3424420d79d5811fa8c1c052411f975Chris Lattner 181b5bb9f5b5cfe89f4b7626671f4923d50f8d4cd6aChris Lattner 18223d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner/// RehashTable - Grow the table, redistributing values into the buckets with 18323d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner/// the appropriate mod-of-hashtable-size. 184cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hinesunsigned StringMapImpl::RehashTable(unsigned BucketNo) { 185aea4fe2862ce17acc6ce943df589ee8d5eb05adfJakob Stoklund Olesen unsigned NewSize; 186c894b02ae037b5fdb38e42535539d5a0e49d6c41Benjamin Kramer unsigned *HashTable = (unsigned *)(TheTable + NumBuckets + 1); 187aea4fe2862ce17acc6ce943df589ee8d5eb05adfJakob Stoklund Olesen 188aea4fe2862ce17acc6ce943df589ee8d5eb05adfJakob Stoklund Olesen // If the hash table is now more than 3/4 full, or if fewer than 1/8 of 189aea4fe2862ce17acc6ce943df589ee8d5eb05adfJakob Stoklund Olesen // the buckets are empty (meaning that many are filled with tombstones), 190aea4fe2862ce17acc6ce943df589ee8d5eb05adfJakob Stoklund Olesen // grow/rehash the table. 191aea4fe2862ce17acc6ce943df589ee8d5eb05adfJakob Stoklund Olesen if (NumItems*4 > NumBuckets*3) { 192aea4fe2862ce17acc6ce943df589ee8d5eb05adfJakob Stoklund Olesen NewSize = NumBuckets*2; 1932a79116940012acaad9cc70efef79d7359f27513Chandler Carruth } else if (NumBuckets-(NumItems+NumTombstones) <= NumBuckets/8) { 194aea4fe2862ce17acc6ce943df589ee8d5eb05adfJakob Stoklund Olesen NewSize = NumBuckets; 195aea4fe2862ce17acc6ce943df589ee8d5eb05adfJakob Stoklund Olesen } else { 196cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines return BucketNo; 197aea4fe2862ce17acc6ce943df589ee8d5eb05adfJakob Stoklund Olesen } 198aea4fe2862ce17acc6ce943df589ee8d5eb05adfJakob Stoklund Olesen 199cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines unsigned NewBucketNo = BucketNo; 200a86559ec426c643a151aeba1e051e4f878050f95Chris Lattner // Allocate one extra bucket which will always be non-empty. This allows the 201a86559ec426c643a151aeba1e051e4f878050f95Chris Lattner // iterators to stop at end. 202c894b02ae037b5fdb38e42535539d5a0e49d6c41Benjamin Kramer StringMapEntryBase **NewTableArray = 203c894b02ae037b5fdb38e42535539d5a0e49d6c41Benjamin Kramer (StringMapEntryBase **)calloc(NewSize+1, sizeof(StringMapEntryBase *) + 204c894b02ae037b5fdb38e42535539d5a0e49d6c41Benjamin Kramer sizeof(unsigned)); 205c894b02ae037b5fdb38e42535539d5a0e49d6c41Benjamin Kramer unsigned *NewHashArray = (unsigned *)(NewTableArray + NewSize + 1); 206c894b02ae037b5fdb38e42535539d5a0e49d6c41Benjamin Kramer NewTableArray[NewSize] = (StringMapEntryBase*)2; 207c894b02ae037b5fdb38e42535539d5a0e49d6c41Benjamin Kramer 20823d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner // Rehash all the items into their new buckets. Luckily :) we already have 20923d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner // the hash values available, so we don't have to rehash any strings. 210c894b02ae037b5fdb38e42535539d5a0e49d6c41Benjamin Kramer for (unsigned I = 0, E = NumBuckets; I != E; ++I) { 211c894b02ae037b5fdb38e42535539d5a0e49d6c41Benjamin Kramer StringMapEntryBase *Bucket = TheTable[I]; 212c894b02ae037b5fdb38e42535539d5a0e49d6c41Benjamin Kramer if (Bucket && Bucket != getTombstoneVal()) { 21323d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner // Fast case, bucket available. 214c894b02ae037b5fdb38e42535539d5a0e49d6c41Benjamin Kramer unsigned FullHash = HashTable[I]; 21523d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner unsigned NewBucket = FullHash & (NewSize-1); 216dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines if (!NewTableArray[NewBucket]) { 217c894b02ae037b5fdb38e42535539d5a0e49d6c41Benjamin Kramer NewTableArray[FullHash & (NewSize-1)] = Bucket; 218c894b02ae037b5fdb38e42535539d5a0e49d6c41Benjamin Kramer NewHashArray[FullHash & (NewSize-1)] = FullHash; 219cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines if (I == BucketNo) 220cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines NewBucketNo = NewBucket; 22123d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner continue; 22223d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner } 22323d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner 22444dcd01cb3424420d79d5811fa8c1c052411f975Chris Lattner // Otherwise probe for a spot. 22523d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner unsigned ProbeSize = 1; 22623d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner do { 22723d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner NewBucket = (NewBucket + ProbeSize++) & (NewSize-1); 228c894b02ae037b5fdb38e42535539d5a0e49d6c41Benjamin Kramer } while (NewTableArray[NewBucket]); 22923d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner 23023d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner // Finally found a slot. Fill it in. 231c894b02ae037b5fdb38e42535539d5a0e49d6c41Benjamin Kramer NewTableArray[NewBucket] = Bucket; 232c894b02ae037b5fdb38e42535539d5a0e49d6c41Benjamin Kramer NewHashArray[NewBucket] = FullHash; 233cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines if (I == BucketNo) 234cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines NewBucketNo = NewBucket; 23523d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner } 23623d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner } 23723d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner 23812ba806c5d9ab0b45e41d7dc3d7af235f87d5e7eChris Lattner free(TheTable); 23923d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner 24023d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner TheTable = NewTableArray; 24123d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner NumBuckets = NewSize; 24203ef44991768b803ed5b210877ce0d83bf16fd93Jakob Stoklund Olesen NumTombstones = 0; 243cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines return NewBucketNo; 24423d7b3611759c7fb3a853dfce3ee3d43ef5ca67dChris Lattner} 245