LLVM: lib/Support/StringMap.cpp Source File (original) (raw)
1
2
3
4
5
6
7
8
9
10
11
12
17
18using namespace llvm;
19
20
21
23
24 if (NumEntries == 0)
25 return 0;
26
27
29}
30
33 NewNumBuckets + 1, sizeof(StringMapEntryBase **) + sizeof(unsigned)));
34
35
36
38 return Table;
39}
40
42 unsigned NumBuckets) {
43 return reinterpret_cast<unsigned *>(TheTable + NumBuckets + 1);
44}
45
47
50
51 if (InitSize) {
52
53
54
56 }
57}
58
60 assert((InitSize & (InitSize - 1)) == 0 &&
61 "Init Size must be a power of 2 or zero!");
62
63 unsigned NewNumBuckets = InitSize ? InitSize : 16;
66
68
69
71}
72
73
74
75
76
77
80#ifdef EXPENSIVE_CHECKS
82#endif
83
87 FullHashValue = ~FullHashValue;
88 unsigned BucketNo = FullHashValue & (NumBuckets - 1);
90
91 unsigned ProbeAmt = 1;
92 int FirstTombstone = -1;
93 while (true) {
95
97
98
99 if (FirstTombstone != -1) {
100 HashTable[FirstTombstone] = FullHashValue;
101 return FirstTombstone;
102 }
103
104 HashTable[BucketNo] = FullHashValue;
105 return BucketNo;
106 }
107
109
110 if (FirstTombstone == -1)
111 FirstTombstone = BucketNo;
112 } else if (LLVM_LIKELY(HashTable[BucketNo] == FullHashValue)) {
113
114
115
116
117
118
119
120 char *ItemStr = (char *)BucketItem + ItemSize;
122
123 return BucketNo;
124 }
125 }
126
127
128 BucketNo = (BucketNo + ProbeAmt) & (NumBuckets - 1);
129
130
131
132 ++ProbeAmt;
133 }
134}
135
136
137
138
141 return -1;
142#ifdef EXPENSIVE_CHECKS
144#endif
146 FullHashValue = ~FullHashValue;
147 unsigned BucketNo = FullHashValue & (NumBuckets - 1);
149
150 unsigned ProbeAmt = 1;
151 while (true) {
153
155 return -1;
156
158
159 } else if (LLVM_LIKELY(HashTable[BucketNo] == FullHashValue)) {
160
161
162
163
164
165
166
167 char *ItemStr = (char *)BucketItem + ItemSize;
169
170 return BucketNo;
171 }
172 }
173
174
175 BucketNo = (BucketNo + ProbeAmt) & (NumBuckets - 1);
176
177
178
179 ++ProbeAmt;
180 }
181}
182
183
184
186 const char *VStr = (char *)V + ItemSize;
188 (void)V2;
189 assert(V == V2 && "Didn't find key?");
190}
191
192
193
196 if (Bucket == -1)
197 return nullptr;
198
204
205 return Result;
206}
207
208
209
211 unsigned NewSize;
212
213
214
220 } else {
221 return BucketNo;
222 }
223
224 unsigned NewBucketNo = BucketNo;
225 auto **NewTableArray = createTable(NewSize);
226 unsigned *NewHashArray = getHashTable(NewTableArray, NewSize);
228
229
230
231 for (unsigned I = 0, E = NumBuckets; I != E; ++I) {
234
235 unsigned FullHash = HashTable[I];
236 unsigned NewBucket = FullHash & (NewSize - 1);
237 if (NewTableArray[NewBucket]) {
238 unsigned ProbeSize = 1;
239 do {
240 NewBucket = (NewBucket + ProbeSize++) & (NewSize - 1);
241 } while (NewTableArray[NewBucket]);
242 }
243
244
245 NewTableArray[NewBucket] = Bucket;
246 NewHashArray[NewBucket] = FullHash;
247 if (I == BucketNo)
248 NewBucketNo = NewBucket;
249 }
250 }
251
253
257 return NewBucketNo;
258}
assert(UImm &&(UImm !=~static_cast< T >(0)) &&"Invalid immediate!")
This file defines the StringMap class.
#define LLVM_UNLIKELY(EXPR)
#define LLVM_LIKELY(EXPR)
static StringMapEntryBase ** createTable(unsigned NewNumBuckets)
Definition StringMap.cpp:31
static unsigned * getHashTable(StringMapEntryBase **TheTable, unsigned NumBuckets)
Definition StringMap.cpp:41
static unsigned getMinBucketToReserveForEntries(unsigned NumEntries)
Returns the number of buckets to allocate to ensure that the DenseMap can accommodate NumEntries with...
Definition StringMap.cpp:22
StringMapEntryBase - Shared base class of StringMapEntry instances.
size_t getKeyLength() const
static StringMapEntryBase * getTombstoneVal()
unsigned LookupBucketFor(StringRef Key)
LookupBucketFor - Look up the bucket that the specified string should end up in.
LLVM_ABI unsigned RehashTable(unsigned BucketNo=0)
RehashTable - Grow the table, redistributing values into the buckets with the appropriate mod-of-hash...
Definition StringMap.cpp:210
LLVM_ABI void RemoveKey(StringMapEntryBase *V)
RemoveKey - Remove the specified StringMapEntry from the table, but do not delete it.
Definition StringMap.cpp:185
StringMapEntryBase ** TheTable
StringMapImpl(unsigned itemSize)
LLVM_ABI void init(unsigned Size)
Allocate the table with the specified number of buckets and otherwise setup the map as empty.
Definition StringMap.cpp:59
static LLVM_ABI uint32_t hash(StringRef Key)
Returns the hash value that will be used for the given string.
Definition StringMap.cpp:46
int FindKey(StringRef Key) const
FindKey - Look up the bucket that contains the specified key.
StringRef - Represent a constant reference to a string, i.e.
This is an optimization pass for GlobalISel generic memory operations.
LLVM_ABI uint64_t xxh3_64bits(ArrayRef< uint8_t > data)
LLVM_ATTRIBUTE_RETURNS_NONNULL void * safe_calloc(size_t Count, size_t Sz)
constexpr bool shouldReverseIterate()
LLVM_ATTRIBUTE_VISIBILITY_DEFAULT AnalysisKey InnerAnalysisManagerProxy< AnalysisManagerT, IRUnitT, ExtraArgTs... >::Key
constexpr uint64_t NextPowerOf2(uint64_t A)
Returns the next power of two (in 64-bits) that is strictly greater than A.