| //===--- StringMap.cpp - String Hash table map implementation -------------===// |
| // |
| // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. |
| // See https://llvm.org/LICENSE.txt for license information. |
| // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception |
| // |
| //===----------------------------------------------------------------------===// |
| // |
| // This file implements the StringMap class. |
| // |
| //===----------------------------------------------------------------------===// |
| |
| #include "llvm/ADT/StringMap.h" |
| #include "llvm/ADT/StringExtras.h" |
| #include "llvm/Support/DJB.h" |
| #include "llvm/Support/MathExtras.h" |
| |
| 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!"); |
| |
| unsigned NewNumBuckets = InitSize ? InitSize : 16; |
| NumItems = 0; |
| NumTombstones = 0; |
| |
| TheTable = static_cast<StringMapEntryBase **>(safe_calloc( |
| NewNumBuckets + 1, sizeof(StringMapEntryBase **) + sizeof(unsigned))); |
| |
| // Set the member only if TheTable was successfully allocated |
| NumBuckets = NewNumBuckets; |
| |
| // 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 = djbHash(Name, 0); |
| 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 = djbHash(Key, 0); |
| 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. |
| auto NewTableArray = static_cast<StringMapEntryBase **>(safe_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; |
| } |