//===--- StringMap.cpp - String Hash table map implementation -------------===// // // The LLVM Compiler Infrastructure // // This file is distributed under the University of Illinois Open Source // License. See LICENSE.TXT for details. // //===----------------------------------------------------------------------===// // // This file implements the StringMap class. // //===----------------------------------------------------------------------===// #include "llvm/ADT/StringMap.h" #include "llvm/ADT/StringExtras.h" #include "llvm/Support/Compiler.h" #include "llvm/Support/MathExtras.h" #include <cassert> using namespace llvm; /// Returns the number of buckets to allocate to ensure that the DenseMap can /// accommodate \p NumEntries without need to grow(). static unsigned getMinBucketToReserveForEntries(unsigned NumEntries) { // Ensure that "NumEntries * 4 < NumBuckets * 3" if (NumEntries == 0) return 0; // +1 is required because of the strict equality. // For example if NumEntries is 48, we need to return 401. return NextPowerOf2(NumEntries * 4 / 3 + 1); } StringMapImpl::StringMapImpl(unsigned InitSize, unsigned itemSize) { ItemSize = itemSize; // If a size is specified, initialize the table with that many buckets. if (InitSize) { // The table will grow when the number of entries reach 3/4 of the number of // buckets. To guarantee that "InitSize" number of entries can be inserted // in the table without growing, we allocate just what is needed here. init(getMinBucketToReserveForEntries(InitSize)); return; } // Otherwise, initialize it with zero buckets to avoid the allocation. TheTable = nullptr; NumBuckets = 0; NumItems = 0; NumTombstones = 0; } void StringMapImpl::init(unsigned InitSize) { assert((InitSize & (InitSize-1)) == 0 && "Init Size must be a power of 2 or zero!"); NumBuckets = InitSize ? InitSize : 16; NumItems = 0; NumTombstones = 0; TheTable = (StringMapEntryBase **)calloc(NumBuckets+1, sizeof(StringMapEntryBase **) + sizeof(unsigned)); // Allocate one extra bucket, set it to look filled so the iterators stop at // end. TheTable[NumBuckets] = (StringMapEntryBase*)2; } /// LookupBucketFor - Look up the bucket that the specified string should end /// up in. If it already exists as a key in the map, the Item pointer for the /// specified bucket will be non-null. Otherwise, it will be null. In either /// case, the FullHashValue field of the bucket will be set to the hash value /// of the string. unsigned StringMapImpl::LookupBucketFor(StringRef Name) { unsigned HTSize = NumBuckets; if (HTSize == 0) { // Hash table unallocated so far? init(16); HTSize = NumBuckets; } unsigned FullHashValue = HashString(Name); unsigned BucketNo = FullHashValue & (HTSize-1); unsigned *HashTable = (unsigned *)(TheTable + NumBuckets + 1); unsigned ProbeAmt = 1; int FirstTombstone = -1; while (true) { StringMapEntryBase *BucketItem = TheTable[BucketNo]; // If we found an empty bucket, this key isn't in the table yet, return it. if (LLVM_LIKELY(!BucketItem)) { // If we found a tombstone, we want to reuse the tombstone instead of an // empty bucket. This reduces probing. if (FirstTombstone != -1) { HashTable[FirstTombstone] = FullHashValue; return FirstTombstone; } HashTable[BucketNo] = FullHashValue; return BucketNo; } if (BucketItem == getTombstoneVal()) { // Skip over tombstones. However, remember the first one we see. if (FirstTombstone == -1) FirstTombstone = BucketNo; } else if (LLVM_LIKELY(HashTable[BucketNo] == FullHashValue)) { // If the full hash value matches, check deeply for a match. The common // case here is that we are only looking at the buckets (for item info // being non-null and for the full hash value) not at the items. This // is important for cache locality. // Do the comparison like this because Name isn't necessarily // null-terminated! char *ItemStr = (char*)BucketItem+ItemSize; if (Name == StringRef(ItemStr, BucketItem->getKeyLength())) { // We found a match! return BucketNo; } } // Okay, we didn't find the item. Probe to the next bucket. BucketNo = (BucketNo+ProbeAmt) & (HTSize-1); // Use quadratic probing, it has fewer clumping artifacts than linear // probing and has good cache behavior in the common case. ++ProbeAmt; } } /// FindKey - Look up the bucket that contains the specified key. If it exists /// in the map, return the bucket number of the key. Otherwise return -1. /// This does not modify the map. int StringMapImpl::FindKey(StringRef Key) const { unsigned HTSize = NumBuckets; if (HTSize == 0) return -1; // Really empty table? unsigned FullHashValue = HashString(Key); unsigned BucketNo = FullHashValue & (HTSize-1); unsigned *HashTable = (unsigned *)(TheTable + NumBuckets + 1); unsigned ProbeAmt = 1; while (true) { StringMapEntryBase *BucketItem = TheTable[BucketNo]; // If we found an empty bucket, this key isn't in the table yet, return. if (LLVM_LIKELY(!BucketItem)) return -1; if (BucketItem == getTombstoneVal()) { // Ignore tombstones. } else if (LLVM_LIKELY(HashTable[BucketNo] == FullHashValue)) { // If the full hash value matches, check deeply for a match. The common // case here is that we are only looking at the buckets (for item info // being non-null and for the full hash value) not at the items. This // is important for cache locality. // Do the comparison like this because NameStart isn't necessarily // null-terminated! char *ItemStr = (char*)BucketItem+ItemSize; if (Key == StringRef(ItemStr, BucketItem->getKeyLength())) { // We found a match! return BucketNo; } } // Okay, we didn't find the item. Probe to the next bucket. BucketNo = (BucketNo+ProbeAmt) & (HTSize-1); // Use quadratic probing, it has fewer clumping artifacts than linear // probing and has good cache behavior in the common case. ++ProbeAmt; } } /// RemoveKey - Remove the specified StringMapEntry from the table, but do not /// delete it. This aborts if the value isn't in the table. void StringMapImpl::RemoveKey(StringMapEntryBase *V) { const char *VStr = (char*)V + ItemSize; StringMapEntryBase *V2 = RemoveKey(StringRef(VStr, V->getKeyLength())); (void)V2; assert(V == V2 && "Didn't find key?"); } /// RemoveKey - Remove the StringMapEntry for the specified key from the /// table, returning it. If the key is not in the table, this returns null. StringMapEntryBase *StringMapImpl::RemoveKey(StringRef Key) { int Bucket = FindKey(Key); if (Bucket == -1) return nullptr; StringMapEntryBase *Result = TheTable[Bucket]; TheTable[Bucket] = getTombstoneVal(); --NumItems; ++NumTombstones; assert(NumItems + NumTombstones <= NumBuckets); return Result; } /// RehashTable - Grow the table, redistributing values into the buckets with /// the appropriate mod-of-hashtable-size. unsigned StringMapImpl::RehashTable(unsigned BucketNo) { unsigned NewSize; unsigned *HashTable = (unsigned *)(TheTable + NumBuckets + 1); // If the hash table is now more than 3/4 full, or if fewer than 1/8 of // the buckets are empty (meaning that many are filled with tombstones), // grow/rehash the table. if (LLVM_UNLIKELY(NumItems * 4 > NumBuckets * 3)) { NewSize = NumBuckets*2; } else if (LLVM_UNLIKELY(NumBuckets - (NumItems + NumTombstones) <= NumBuckets / 8)) { NewSize = NumBuckets; } else { return BucketNo; } unsigned NewBucketNo = BucketNo; // Allocate one extra bucket which will always be non-empty. This allows the // iterators to stop at end. StringMapEntryBase **NewTableArray = (StringMapEntryBase **)calloc(NewSize+1, sizeof(StringMapEntryBase *) + sizeof(unsigned)); unsigned *NewHashArray = (unsigned *)(NewTableArray + NewSize + 1); NewTableArray[NewSize] = (StringMapEntryBase*)2; // Rehash all the items into their new buckets. Luckily :) we already have // the hash values available, so we don't have to rehash any strings. for (unsigned I = 0, E = NumBuckets; I != E; ++I) { StringMapEntryBase *Bucket = TheTable[I]; if (Bucket && Bucket != getTombstoneVal()) { // Fast case, bucket available. unsigned FullHash = HashTable[I]; unsigned NewBucket = FullHash & (NewSize-1); if (!NewTableArray[NewBucket]) { NewTableArray[FullHash & (NewSize-1)] = Bucket; NewHashArray[FullHash & (NewSize-1)] = FullHash; if (I == BucketNo) NewBucketNo = NewBucket; continue; } // Otherwise probe for a spot. unsigned ProbeSize = 1; do { NewBucket = (NewBucket + ProbeSize++) & (NewSize-1); } while (NewTableArray[NewBucket]); // Finally found a slot. Fill it in. NewTableArray[NewBucket] = Bucket; NewHashArray[NewBucket] = FullHash; if (I == BucketNo) NewBucketNo = NewBucket; } } free(TheTable); TheTable = NewTableArray; NumBuckets = NewSize; NumTombstones = 0; return NewBucketNo; }