17ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens//===--- StringMap.cpp - String Hash table map implementation -------------===// 27ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens// 37ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens// The LLVM Compiler Infrastructure 47ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens// 57ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens// This file is distributed under the University of Illinois Open Source 67ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens// License. See LICENSE.TXT for details. 77ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens// 87ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens//===----------------------------------------------------------------------===// 97ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens// 107ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens// This file implements the StringMap class. 117ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens// 127ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens//===----------------------------------------------------------------------===// 137ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens 147ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens#include "llvm/ADT/StringMap.h" 157ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens#include "llvm/ADT/StringExtras.h" 167ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens#include "llvm/Support/Compiler.h" 177ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens#include "llvm/Support/MathExtras.h" 187ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens#include <cassert> 197ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens 207ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capensusing namespace llvm; 217ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens 227ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens/// Returns the number of buckets to allocate to ensure that the DenseMap can 237ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens/// accommodate \p NumEntries without need to grow(). 247ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capensstatic unsigned getMinBucketToReserveForEntries(unsigned NumEntries) { 257ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens // Ensure that "NumEntries * 4 < NumBuckets * 3" 267ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens if (NumEntries == 0) 277ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens return 0; 287ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens // +1 is required because of the strict equality. 297ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens // For example if NumEntries is 48, we need to return 401. 307ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens return NextPowerOf2(NumEntries * 4 / 3 + 1); 317ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens} 327ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens 337ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas CapensStringMapImpl::StringMapImpl(unsigned InitSize, unsigned itemSize) { 347ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens ItemSize = itemSize; 357ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens 367ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens // If a size is specified, initialize the table with that many buckets. 377ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens if (InitSize) { 387ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens // The table will grow when the number of entries reach 3/4 of the number of 397ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens // buckets. To guarantee that "InitSize" number of entries can be inserted 407ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens // in the table without growing, we allocate just what is needed here. 417ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens init(getMinBucketToReserveForEntries(InitSize)); 427ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens return; 437ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens } 447ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens 457ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens // Otherwise, initialize it with zero buckets to avoid the allocation. 467ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens TheTable = nullptr; 477ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens NumBuckets = 0; 487ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens NumItems = 0; 497ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens NumTombstones = 0; 507ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens} 517ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens 527ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capensvoid StringMapImpl::init(unsigned InitSize) { 537ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens assert((InitSize & (InitSize-1)) == 0 && 547ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens "Init Size must be a power of 2 or zero!"); 557ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens NumBuckets = InitSize ? InitSize : 16; 567ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens NumItems = 0; 577ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens NumTombstones = 0; 587ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens 597ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens TheTable = (StringMapEntryBase **)calloc(NumBuckets+1, 607ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens sizeof(StringMapEntryBase **) + 617ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens sizeof(unsigned)); 627ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens 637ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens // Allocate one extra bucket, set it to look filled so the iterators stop at 647ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens // end. 657ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens TheTable[NumBuckets] = (StringMapEntryBase*)2; 667ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens} 677ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens 687ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens/// LookupBucketFor - Look up the bucket that the specified string should end 697ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens/// up in. If it already exists as a key in the map, the Item pointer for the 707ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens/// specified bucket will be non-null. Otherwise, it will be null. In either 717ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens/// case, the FullHashValue field of the bucket will be set to the hash value 727ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens/// of the string. 737ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capensunsigned StringMapImpl::LookupBucketFor(StringRef Name) { 747ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens unsigned HTSize = NumBuckets; 757ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens if (HTSize == 0) { // Hash table unallocated so far? 767ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens init(16); 777ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens HTSize = NumBuckets; 787ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens } 797ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens unsigned FullHashValue = HashString(Name); 807ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens unsigned BucketNo = FullHashValue & (HTSize-1); 817ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens unsigned *HashTable = (unsigned *)(TheTable + NumBuckets + 1); 827ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens 837ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens unsigned ProbeAmt = 1; 847ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens int FirstTombstone = -1; 857ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens while (true) { 867ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens StringMapEntryBase *BucketItem = TheTable[BucketNo]; 877ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens // If we found an empty bucket, this key isn't in the table yet, return it. 887ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens if (LLVM_LIKELY(!BucketItem)) { 897ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens // If we found a tombstone, we want to reuse the tombstone instead of an 907ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens // empty bucket. This reduces probing. 917ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens if (FirstTombstone != -1) { 927ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens HashTable[FirstTombstone] = FullHashValue; 937ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens return FirstTombstone; 947ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens } 957ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens 967ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens HashTable[BucketNo] = FullHashValue; 977ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens return BucketNo; 987ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens } 997ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens 1007ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens if (BucketItem == getTombstoneVal()) { 1017ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens // Skip over tombstones. However, remember the first one we see. 1027ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens if (FirstTombstone == -1) FirstTombstone = BucketNo; 1037ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens } else if (LLVM_LIKELY(HashTable[BucketNo] == FullHashValue)) { 1047ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens // If the full hash value matches, check deeply for a match. The common 1057ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens // case here is that we are only looking at the buckets (for item info 1067ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens // being non-null and for the full hash value) not at the items. This 1077ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens // is important for cache locality. 1087ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens 1097ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens // Do the comparison like this because Name isn't necessarily 1107ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens // null-terminated! 1117ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens char *ItemStr = (char*)BucketItem+ItemSize; 1127ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens if (Name == StringRef(ItemStr, BucketItem->getKeyLength())) { 1137ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens // We found a match! 1147ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens return BucketNo; 1157ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens } 1167ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens } 1177ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens 1187ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens // Okay, we didn't find the item. Probe to the next bucket. 1197ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens BucketNo = (BucketNo+ProbeAmt) & (HTSize-1); 1207ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens 1217ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens // Use quadratic probing, it has fewer clumping artifacts than linear 1227ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens // probing and has good cache behavior in the common case. 1237ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens ++ProbeAmt; 1247ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens } 1257ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens} 1267ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens 1277ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens/// FindKey - Look up the bucket that contains the specified key. If it exists 1287ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens/// in the map, return the bucket number of the key. Otherwise return -1. 1297ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens/// This does not modify the map. 1307ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capensint StringMapImpl::FindKey(StringRef Key) const { 1317ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens unsigned HTSize = NumBuckets; 1327ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens if (HTSize == 0) return -1; // Really empty table? 1337ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens unsigned FullHashValue = HashString(Key); 1347ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens unsigned BucketNo = FullHashValue & (HTSize-1); 1357ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens unsigned *HashTable = (unsigned *)(TheTable + NumBuckets + 1); 1367ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens 1377ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens unsigned ProbeAmt = 1; 1387ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens while (true) { 1397ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens StringMapEntryBase *BucketItem = TheTable[BucketNo]; 1407ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens // If we found an empty bucket, this key isn't in the table yet, return. 1417ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens if (LLVM_LIKELY(!BucketItem)) 1427ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens return -1; 1437ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens 1447ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens if (BucketItem == getTombstoneVal()) { 1457ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens // Ignore tombstones. 1467ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens } else if (LLVM_LIKELY(HashTable[BucketNo] == FullHashValue)) { 1477ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens // If the full hash value matches, check deeply for a match. The common 1487ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens // case here is that we are only looking at the buckets (for item info 1497ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens // being non-null and for the full hash value) not at the items. This 1507ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens // is important for cache locality. 1517ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens 1527ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens // Do the comparison like this because NameStart isn't necessarily 1537ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens // null-terminated! 1547ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens char *ItemStr = (char*)BucketItem+ItemSize; 1557ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens if (Key == StringRef(ItemStr, BucketItem->getKeyLength())) { 1567ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens // We found a match! 1577ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens return BucketNo; 1587ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens } 1597ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens } 1607ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens 1617ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens // Okay, we didn't find the item. Probe to the next bucket. 1627ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens BucketNo = (BucketNo+ProbeAmt) & (HTSize-1); 1637ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens 1647ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens // Use quadratic probing, it has fewer clumping artifacts than linear 1657ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens // probing and has good cache behavior in the common case. 1667ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens ++ProbeAmt; 1677ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens } 1687ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens} 1697ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens 1707ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens/// RemoveKey - Remove the specified StringMapEntry from the table, but do not 1717ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens/// delete it. This aborts if the value isn't in the table. 1727ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capensvoid StringMapImpl::RemoveKey(StringMapEntryBase *V) { 1737ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens const char *VStr = (char*)V + ItemSize; 1747ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens StringMapEntryBase *V2 = RemoveKey(StringRef(VStr, V->getKeyLength())); 1757ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens (void)V2; 1767ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens assert(V == V2 && "Didn't find key?"); 1777ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens} 1787ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens 1797ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens/// RemoveKey - Remove the StringMapEntry for the specified key from the 1807ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens/// table, returning it. If the key is not in the table, this returns null. 1817ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas CapensStringMapEntryBase *StringMapImpl::RemoveKey(StringRef Key) { 1827ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens int Bucket = FindKey(Key); 1837ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens if (Bucket == -1) return nullptr; 1847ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens 1857ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens StringMapEntryBase *Result = TheTable[Bucket]; 1867ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens TheTable[Bucket] = getTombstoneVal(); 1877ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens --NumItems; 1887ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens ++NumTombstones; 1897ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens assert(NumItems + NumTombstones <= NumBuckets); 1907ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens 1917ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens return Result; 1927ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens} 1937ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens 1947ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens/// RehashTable - Grow the table, redistributing values into the buckets with 1957ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens/// the appropriate mod-of-hashtable-size. 1967ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capensunsigned StringMapImpl::RehashTable(unsigned BucketNo) { 1977ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens unsigned NewSize; 1987ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens unsigned *HashTable = (unsigned *)(TheTable + NumBuckets + 1); 1997ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens 2007ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens // If the hash table is now more than 3/4 full, or if fewer than 1/8 of 2017ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens // the buckets are empty (meaning that many are filled with tombstones), 2027ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens // grow/rehash the table. 2037ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens if (LLVM_UNLIKELY(NumItems * 4 > NumBuckets * 3)) { 2047ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens NewSize = NumBuckets*2; 2057ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens } else if (LLVM_UNLIKELY(NumBuckets - (NumItems + NumTombstones) <= 2067ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens NumBuckets / 8)) { 2077ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens NewSize = NumBuckets; 2087ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens } else { 2097ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens return BucketNo; 2107ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens } 2117ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens 2127ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens unsigned NewBucketNo = BucketNo; 2137ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens // Allocate one extra bucket which will always be non-empty. This allows the 2147ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens // iterators to stop at end. 2157ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens StringMapEntryBase **NewTableArray = 2167ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens (StringMapEntryBase **)calloc(NewSize+1, sizeof(StringMapEntryBase *) + 2177ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens sizeof(unsigned)); 2187ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens unsigned *NewHashArray = (unsigned *)(NewTableArray + NewSize + 1); 2197ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens NewTableArray[NewSize] = (StringMapEntryBase*)2; 2207ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens 2217ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens // Rehash all the items into their new buckets. Luckily :) we already have 2227ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens // the hash values available, so we don't have to rehash any strings. 2237ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens for (unsigned I = 0, E = NumBuckets; I != E; ++I) { 2247ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens StringMapEntryBase *Bucket = TheTable[I]; 2257ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens if (Bucket && Bucket != getTombstoneVal()) { 2267ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens // Fast case, bucket available. 2277ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens unsigned FullHash = HashTable[I]; 2287ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens unsigned NewBucket = FullHash & (NewSize-1); 2297ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens if (!NewTableArray[NewBucket]) { 2307ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens NewTableArray[FullHash & (NewSize-1)] = Bucket; 2317ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens NewHashArray[FullHash & (NewSize-1)] = FullHash; 2327ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens if (I == BucketNo) 2337ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens NewBucketNo = NewBucket; 2347ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens continue; 2357ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens } 2367ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens 2377ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens // Otherwise probe for a spot. 2387ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens unsigned ProbeSize = 1; 2397ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens do { 2407ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens NewBucket = (NewBucket + ProbeSize++) & (NewSize-1); 2417ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens } while (NewTableArray[NewBucket]); 2427ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens 2437ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens // Finally found a slot. Fill it in. 2447ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens NewTableArray[NewBucket] = Bucket; 2457ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens NewHashArray[NewBucket] = FullHash; 2467ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens if (I == BucketNo) 2477ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens NewBucketNo = NewBucket; 2487ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens } 2497ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens } 2507ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens 2517ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens free(TheTable); 2527ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens 2537ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens TheTable = NewTableArray; 2547ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens NumBuckets = NewSize; 2557ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens NumTombstones = 0; 2567ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens return NewBucketNo; 2577ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens} 258