Go to the documentation of this file.
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);
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;
unsigned RehashTable(unsigned BucketNo=0)
RehashTable - Grow the table, redistributing values into the buckets with the appropriate mod-of-hash...
This is an optimization pass for GlobalISel generic memory operations.
size_t getKeyLength() const
LLVM_ATTRIBUTE_RETURNS_NONNULL void * safe_calloc(size_t Count, size_t Sz)
static unsigned getMinBucketToReserveForEntries(unsigned NumEntries)
Returns the number of buckets to allocate to ensure that the DenseMap can accommodate NumEntries with...
static unsigned * getHashTable(StringMapEntryBase **TheTable, unsigned NumBuckets)
StringMapEntryBase - Shared base class of StringMapEntry instances.
static StringMapEntryBase ** createTable(unsigned NewNumBuckets)
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
StringMapEntryBase ** TheTable
constexpr uint64_t NextPowerOf2(uint64_t A)
Returns the next power of two (in 64-bits) that is strictly greater than A.
int FindKey(StringRef Key) const
FindKey - Look up the bucket that contains the specified key.
static StringMapEntryBase * getTombstoneVal()
void init(unsigned Size)
Allocate the table with the specified number of buckets and otherwise setup the map as empty.
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
unsigned LookupBucketFor(StringRef Key)
LookupBucketFor - Look up the bucket that the specified string should end up in.
StringRef - Represent a constant reference to a string, i.e.
StringMapImpl(unsigned itemSize)
void RemoveKey(StringMapEntryBase *V)
RemoveKey - Remove the specified StringMapEntry from the table, but do not delete it.
#define LLVM_LIKELY(EXPR)
uint32_t djbHash(StringRef Buffer, uint32_t H=5381)
The Bernstein hash function used by the DWARF accelerator tables.
#define LLVM_UNLIKELY(EXPR)