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