42 unsigned NumBuckets) {
43 return reinterpret_cast<unsigned *
>(TheTable + NumBuckets + 1);
66 assert((InitSize & (InitSize - 1)) == 0 &&
67 "Init Size must be a power of 2 or zero!");
69 unsigned NewNumBuckets = InitSize ? InitSize : 16;
90 FullHashValue = ~FullHashValue;
91 unsigned BucketNo = FullHashValue & (
NumBuckets - 1);
94 unsigned ProbeAmt = 1;
95 int FirstTombstone = -1;
102 if (FirstTombstone != -1) {
103 HashTable[FirstTombstone] = FullHashValue;
104 return FirstTombstone;
107 HashTable[BucketNo] = FullHashValue;
113 if (FirstTombstone == -1)
114 FirstTombstone = BucketNo;
115 }
else if (
LLVM_LIKELY(HashTable[BucketNo] == FullHashValue)) {
123 char *ItemStr = (
char *)BucketItem +
ItemSize;
131 BucketNo = (BucketNo + ProbeAmt) & (
NumBuckets - 1);
147 FullHashValue = ~FullHashValue;
148 unsigned BucketNo = FullHashValue & (
NumBuckets - 1);
151 unsigned ProbeAmt = 1;
160 }
else if (
LLVM_LIKELY(HashTable[BucketNo] == FullHashValue)) {
168 char *ItemStr = (
char *)BucketItem +
ItemSize;
176 BucketNo = (BucketNo + ProbeAmt) & (
NumBuckets - 1);
187 const char *VStr = (
char *)V +
ItemSize;
190 assert(V == V2 &&
"Didn't find key?");
225 unsigned NewBucketNo = BucketNo;
227 unsigned *NewHashArray =
getHashTable(NewTableArray, NewSize);
236 unsigned FullHash = HashTable[
I];
237 unsigned NewBucket = FullHash & (NewSize - 1);
238 if (NewTableArray[NewBucket]) {
239 unsigned ProbeSize = 1;
241 NewBucket = (NewBucket + ProbeSize++) & (NewSize - 1);
242 }
while (NewTableArray[NewBucket]);
246 NewTableArray[NewBucket] = Bucket;
247 NewHashArray[NewBucket] = FullHash;
249 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.
uint64_t xxh3_64bits(ArrayRef< uint8_t > data)
LLVM_ATTRIBUTE_RETURNS_NONNULL void * safe_calloc(size_t Count, size_t Sz)
bool shouldReverseIterate()
constexpr uint64_t NextPowerOf2(uint64_t A)
Returns the next power of two (in 64-bits) that is strictly greater than A.