41 unsigned NumBuckets) {
42 return reinterpret_cast<unsigned *
>(TheTable + NumBuckets + 1);
65 assert((InitSize & (InitSize - 1)) == 0 &&
66 "Init Size must be a power of 2 or zero!");
68 unsigned NewNumBuckets = InitSize ? InitSize : 16;
88 unsigned BucketNo = FullHashValue & (
NumBuckets - 1);
91 unsigned ProbeAmt = 1;
92 int FirstTombstone = -1;
99 if (FirstTombstone != -1) {
100 HashTable[FirstTombstone] = FullHashValue;
101 return FirstTombstone;
104 HashTable[BucketNo] = FullHashValue;
110 if (FirstTombstone == -1)
111 FirstTombstone = BucketNo;
112 }
else if (
LLVM_LIKELY(HashTable[BucketNo] == FullHashValue)) {
120 char *ItemStr = (
char *)BucketItem +
ItemSize;
128 BucketNo = (BucketNo + ProbeAmt) & (
NumBuckets - 1);
142 unsigned FullHashValue =
xxHash64(Key);
143 unsigned BucketNo = FullHashValue & (
NumBuckets - 1);
146 unsigned ProbeAmt = 1;
155 }
else if (
LLVM_LIKELY(HashTable[BucketNo] == FullHashValue)) {
163 char *ItemStr = (
char *)BucketItem +
ItemSize;
171 BucketNo = (BucketNo + ProbeAmt) & (
NumBuckets - 1);
182 const char *VStr = (
char *)V +
ItemSize;
185 assert(V == V2 &&
"Didn't find key?");
220 unsigned NewBucketNo = BucketNo;
222 unsigned *NewHashArray =
getHashTable(NewTableArray, NewSize);
231 unsigned FullHash = HashTable[
I];
232 unsigned NewBucket = FullHash & (NewSize - 1);
233 if (NewTableArray[NewBucket]) {
234 unsigned ProbeSize = 1;
236 NewBucket = (NewBucket + ProbeSize++) & (NewSize - 1);
237 }
while (NewTableArray[NewBucket]);
241 NewTableArray[NewBucket] = Bucket;
242 NewHashArray[NewBucket] = FullHash;
244 NewBucketNo = NewBucket;
This file defines the StringMap class.
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
#define LLVM_UNLIKELY(EXPR)
#define LLVM_LIKELY(EXPR)
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
static StringMapEntryBase ** createTable(unsigned NewNumBuckets)
static unsigned * getHashTable(StringMapEntryBase **TheTable, unsigned NumBuckets)
static unsigned getMinBucketToReserveForEntries(unsigned NumEntries)
Returns the number of buckets to allocate to ensure that the DenseMap can accommodate NumEntries with...
StringMapEntryBase - Shared base class of StringMapEntry instances.
size_t getKeyLength() const
static StringMapEntryBase * getTombstoneVal()
int FindKey(StringRef Key) const
FindKey - Look up the bucket that contains the specified key.
unsigned RehashTable(unsigned BucketNo=0)
RehashTable - Grow the table, redistributing values into the buckets with the appropriate mod-of-hash...
unsigned LookupBucketFor(StringRef Key)
LookupBucketFor - Look up the bucket that the specified string should end up in.
void RemoveKey(StringMapEntryBase *V)
RemoveKey - Remove the specified StringMapEntry from the table, but do not delete it.
StringMapEntryBase ** TheTable
StringMapImpl(unsigned itemSize)
void init(unsigned Size)
Allocate the table with the specified number of buckets and otherwise setup the map as empty.
StringRef - Represent a constant reference to a string, i.e.
This is an optimization pass for GlobalISel generic memory operations.
LLVM_ATTRIBUTE_RETURNS_NONNULL void * safe_calloc(size_t Count, size_t Sz)
constexpr uint64_t NextPowerOf2(uint64_t A)
Returns the next power of two (in 64-bits) that is strictly greater than A.
uint64_t xxHash64(llvm::StringRef Data)