Line data Source code
1 : //===--- StringMap.h - String Hash table map interface ----------*- C++ -*-===//
2 : //
3 : // The LLVM Compiler Infrastructure
4 : //
5 : // This file is distributed under the University of Illinois Open Source
6 : // License. See LICENSE.TXT for details.
7 : //
8 : //===----------------------------------------------------------------------===//
9 : //
10 : // This file defines the StringMap class.
11 : //
12 : //===----------------------------------------------------------------------===//
13 :
14 : #ifndef LLVM_ADT_STRINGMAP_H
15 : #define LLVM_ADT_STRINGMAP_H
16 :
17 : #include "llvm/ADT/StringRef.h"
18 : #include "llvm/Support/Allocator.h"
19 : #include <cstring>
20 : #include <utility>
21 :
22 : namespace llvm {
23 : template<typename ValueT>
24 : class StringMapConstIterator;
25 : template<typename ValueT>
26 : class StringMapIterator;
27 : template<typename ValueTy>
28 : class StringMapEntry;
29 :
30 : /// StringMapEntryBase - Shared base class of StringMapEntry instances.
31 : class StringMapEntryBase {
32 : unsigned StrLen;
33 : public:
34 : explicit StringMapEntryBase(unsigned Len) : StrLen(Len) {}
35 :
36 24 : unsigned getKeyLength() const { return StrLen; }
37 : };
38 :
39 : /// StringMapImpl - This is the base class of StringMap that is shared among
40 : /// all of its instantiations.
41 : class StringMapImpl {
42 : protected:
43 : // Array of NumBuckets pointers to entries, null pointers are holes.
44 : // TheTable[NumBuckets] contains a sentinel value for easy iteration. Followed
45 : // by an array of the actual hash values as unsigned integers.
46 : StringMapEntryBase **TheTable;
47 : unsigned NumBuckets;
48 : unsigned NumItems;
49 : unsigned NumTombstones;
50 : unsigned ItemSize;
51 : protected:
52 : explicit StringMapImpl(unsigned itemSize)
53 : : TheTable(nullptr),
54 : // Initialize the map with zero buckets to allocation.
55 : NumBuckets(0), NumItems(0), NumTombstones(0), ItemSize(itemSize) {}
56 : StringMapImpl(StringMapImpl &&RHS)
57 : : TheTable(RHS.TheTable), NumBuckets(RHS.NumBuckets),
58 : NumItems(RHS.NumItems), NumTombstones(RHS.NumTombstones),
59 : ItemSize(RHS.ItemSize) {
60 : RHS.TheTable = nullptr;
61 : RHS.NumBuckets = 0;
62 : RHS.NumItems = 0;
63 : RHS.NumTombstones = 0;
64 : }
65 :
66 : StringMapImpl(unsigned InitSize, unsigned ItemSize);
67 : unsigned RehashTable(unsigned BucketNo = 0);
68 :
69 : /// LookupBucketFor - Look up the bucket that the specified string should end
70 : /// up in. If it already exists as a key in the map, the Item pointer for the
71 : /// specified bucket will be non-null. Otherwise, it will be null. In either
72 : /// case, the FullHashValue field of the bucket will be set to the hash value
73 : /// of the string.
74 : unsigned LookupBucketFor(StringRef Key);
75 :
76 : /// FindKey - Look up the bucket that contains the specified key. If it exists
77 : /// in the map, return the bucket number of the key. Otherwise return -1.
78 : /// This does not modify the map.
79 : int FindKey(StringRef Key) const;
80 :
81 : /// RemoveKey - Remove the specified StringMapEntry from the table, but do not
82 : /// delete it. This aborts if the value isn't in the table.
83 : void RemoveKey(StringMapEntryBase *V);
84 :
85 : /// RemoveKey - Remove the StringMapEntry for the specified key from the
86 : /// table, returning it. If the key is not in the table, this returns null.
87 : StringMapEntryBase *RemoveKey(StringRef Key);
88 : private:
89 : void init(unsigned Size);
90 : public:
91 : static StringMapEntryBase *getTombstoneVal() {
92 48 : return (StringMapEntryBase*)-1;
93 : }
94 :
95 : unsigned getNumBuckets() const { return NumBuckets; }
96 : unsigned getNumItems() const { return NumItems; }
97 :
98 24 : bool empty() const { return NumItems == 0; }
99 : unsigned size() const { return NumItems; }
100 :
101 : void swap(StringMapImpl &Other) {
102 : std::swap(TheTable, Other.TheTable);
103 : std::swap(NumBuckets, Other.NumBuckets);
104 : std::swap(NumItems, Other.NumItems);
105 : std::swap(NumTombstones, Other.NumTombstones);
106 : }
107 : };
108 :
109 : /// StringMapEntry - This is used to represent one value that is inserted into
110 : /// a StringMap. It contains the Value itself and the key: the string length
111 : /// and data.
112 : template<typename ValueTy>
113 24 : class StringMapEntry : public StringMapEntryBase {
114 : StringMapEntry(StringMapEntry &E) = delete;
115 : public:
116 : ValueTy second;
117 :
118 : explicit StringMapEntry(unsigned strLen)
119 : : StringMapEntryBase(strLen), second() {}
120 : template <class InitTy>
121 : StringMapEntry(unsigned strLen, InitTy &&V)
122 : : StringMapEntryBase(strLen), second(std::forward<InitTy>(V)) {}
123 :
124 : StringRef getKey() const {
125 : return StringRef(getKeyData(), getKeyLength());
126 : }
127 :
128 : const ValueTy &getValue() const { return second; }
129 : ValueTy &getValue() { return second; }
130 :
131 : void setValue(const ValueTy &V) { second = V; }
132 :
133 : /// getKeyData - Return the start of the string data that is the key for this
134 : /// value. The string data is always stored immediately after the
135 : /// StringMapEntry object.
136 : const char *getKeyData() const {return reinterpret_cast<const char*>(this+1);}
137 :
138 : StringRef first() const { return StringRef(getKeyData(), getKeyLength()); }
139 :
140 : /// Create - Create a StringMapEntry for the specified key and default
141 : /// construct the value.
142 : template <typename AllocatorTy, typename InitType>
143 : static StringMapEntry *Create(StringRef Key, AllocatorTy &Allocator,
144 : InitType &&InitVal) {
145 : unsigned KeyLength = Key.size();
146 :
147 : // Allocate a new item with space for the string at the end and a null
148 : // terminator.
149 : unsigned AllocSize = static_cast<unsigned>(sizeof(StringMapEntry))+
150 : KeyLength+1;
151 : unsigned Alignment = alignOf<StringMapEntry>();
152 :
153 : StringMapEntry *NewItem =
154 : static_cast<StringMapEntry*>(Allocator.Allocate(AllocSize,Alignment));
155 :
156 : // Default construct the value.
157 : new (NewItem) StringMapEntry(KeyLength, std::forward<InitType>(InitVal));
158 :
159 : // Copy the string information.
160 : char *StrBuffer = const_cast<char*>(NewItem->getKeyData());
161 : if (KeyLength > 0)
162 : memcpy(StrBuffer, Key.data(), KeyLength);
163 : StrBuffer[KeyLength] = 0; // Null terminate for convenience of clients.
164 : return NewItem;
165 : }
166 :
167 : template<typename AllocatorTy>
168 : static StringMapEntry *Create(StringRef Key, AllocatorTy &Allocator) {
169 : return Create(Key, Allocator, ValueTy());
170 : }
171 :
172 : /// Create - Create a StringMapEntry with normal malloc/free.
173 : template<typename InitType>
174 : static StringMapEntry *Create(StringRef Key, InitType &&InitVal) {
175 : MallocAllocator A;
176 : return Create(Key, A, std::forward<InitType>(InitVal));
177 : }
178 :
179 : static StringMapEntry *Create(StringRef Key) {
180 : return Create(Key, ValueTy());
181 : }
182 :
183 : /// GetStringMapEntryFromKeyData - Given key data that is known to be embedded
184 : /// into a StringMapEntry, return the StringMapEntry itself.
185 : static StringMapEntry &GetStringMapEntryFromKeyData(const char *KeyData) {
186 : char *Ptr = const_cast<char*>(KeyData) - sizeof(StringMapEntry<ValueTy>);
187 : return *reinterpret_cast<StringMapEntry*>(Ptr);
188 : }
189 :
190 : /// Destroy - Destroy this StringMapEntry, releasing memory back to the
191 : /// specified allocator.
192 : template<typename AllocatorTy>
193 : void Destroy(AllocatorTy &Allocator) {
194 : // Free memory referenced by the item.
195 24 : unsigned AllocSize =
196 24 : static_cast<unsigned>(sizeof(StringMapEntry)) + getKeyLength() + 1;
197 24 : this->~StringMapEntry();
198 24 : Allocator.Deallocate(static_cast<void *>(this), AllocSize);
199 24 : }
200 :
201 : /// Destroy this object, releasing memory back to the malloc allocator.
202 : void Destroy() {
203 : MallocAllocator A;
204 : Destroy(A);
205 : }
206 : };
207 :
208 :
209 : /// StringMap - This is an unconventional map that is specialized for handling
210 : /// keys that are "strings", which are basically ranges of bytes. This does some
211 : /// funky memory allocation and hashing things to make it extremely efficient,
212 : /// storing the string data *after* the value in the map.
213 : template<typename ValueTy, typename AllocatorTy = MallocAllocator>
214 : class StringMap : public StringMapImpl {
215 : AllocatorTy Allocator;
216 : public:
217 : typedef StringMapEntry<ValueTy> MapEntryTy;
218 :
219 : StringMap() : StringMapImpl(static_cast<unsigned>(sizeof(MapEntryTy))) {}
220 : explicit StringMap(unsigned InitialSize)
221 : : StringMapImpl(InitialSize, static_cast<unsigned>(sizeof(MapEntryTy))) {}
222 :
223 : explicit StringMap(AllocatorTy A)
224 : : StringMapImpl(static_cast<unsigned>(sizeof(MapEntryTy))), Allocator(A) {}
225 :
226 : StringMap(unsigned InitialSize, AllocatorTy A)
227 : : StringMapImpl(InitialSize, static_cast<unsigned>(sizeof(MapEntryTy))),
228 : Allocator(A) {}
229 :
230 : StringMap(StringMap &&RHS)
231 : : StringMapImpl(std::move(RHS)), Allocator(std::move(RHS.Allocator)) {}
232 :
233 : StringMap &operator=(StringMap RHS) {
234 : StringMapImpl::swap(RHS);
235 : std::swap(Allocator, RHS.Allocator);
236 : return *this;
237 : }
238 :
239 : // FIXME: Implement copy operations if/when they're needed.
240 :
241 : AllocatorTy &getAllocator() { return Allocator; }
242 : const AllocatorTy &getAllocator() const { return Allocator; }
243 :
244 : typedef const char* key_type;
245 : typedef ValueTy mapped_type;
246 : typedef StringMapEntry<ValueTy> value_type;
247 : typedef size_t size_type;
248 :
249 : typedef StringMapConstIterator<ValueTy> const_iterator;
250 : typedef StringMapIterator<ValueTy> iterator;
251 :
252 : iterator begin() {
253 : return iterator(TheTable, NumBuckets == 0);
254 : }
255 : iterator end() {
256 : return iterator(TheTable+NumBuckets, true);
257 : }
258 : const_iterator begin() const {
259 : return const_iterator(TheTable, NumBuckets == 0);
260 : }
261 : const_iterator end() const {
262 : return const_iterator(TheTable+NumBuckets, true);
263 : }
264 :
265 : iterator find(StringRef Key) {
266 : int Bucket = FindKey(Key);
267 : if (Bucket == -1) return end();
268 : return iterator(TheTable+Bucket, true);
269 : }
270 :
271 : const_iterator find(StringRef Key) const {
272 : int Bucket = FindKey(Key);
273 : if (Bucket == -1) return end();
274 : return const_iterator(TheTable+Bucket, true);
275 : }
276 :
277 : /// lookup - Return the entry for the specified key, or a default
278 : /// constructed value if no such entry exists.
279 : ValueTy lookup(StringRef Key) const {
280 : const_iterator it = find(Key);
281 : if (it != end())
282 : return it->second;
283 : return ValueTy();
284 : }
285 :
286 : ValueTy &operator[](StringRef Key) {
287 : return insert(std::make_pair(Key, ValueTy())).first->second;
288 : }
289 :
290 : /// count - Return 1 if the element is in the map, 0 otherwise.
291 : size_type count(StringRef Key) const {
292 : return find(Key) == end() ? 0 : 1;
293 : }
294 :
295 : /// insert - Insert the specified key/value pair into the map. If the key
296 : /// already exists in the map, return false and ignore the request, otherwise
297 : /// insert it and return true.
298 : bool insert(MapEntryTy *KeyValue) {
299 : unsigned BucketNo = LookupBucketFor(KeyValue->getKey());
300 : StringMapEntryBase *&Bucket = TheTable[BucketNo];
301 : if (Bucket && Bucket != getTombstoneVal())
302 : return false; // Already exists in map.
303 :
304 : if (Bucket == getTombstoneVal())
305 : --NumTombstones;
306 : Bucket = KeyValue;
307 : ++NumItems;
308 : assert(NumItems + NumTombstones <= NumBuckets);
309 :
310 : RehashTable();
311 : return true;
312 : }
313 :
314 : /// insert - Inserts the specified key/value pair into the map if the key
315 : /// isn't already in the map. The bool component of the returned pair is true
316 : /// if and only if the insertion takes place, and the iterator component of
317 : /// the pair points to the element with key equivalent to the key of the pair.
318 : std::pair<iterator, bool> insert(std::pair<StringRef, ValueTy> KV) {
319 : unsigned BucketNo = LookupBucketFor(KV.first);
320 : StringMapEntryBase *&Bucket = TheTable[BucketNo];
321 : if (Bucket && Bucket != getTombstoneVal())
322 : return std::make_pair(iterator(TheTable + BucketNo, false),
323 : false); // Already exists in map.
324 :
325 : if (Bucket == getTombstoneVal())
326 : --NumTombstones;
327 : Bucket =
328 : MapEntryTy::Create(KV.first, Allocator, std::move(KV.second));
329 : ++NumItems;
330 : assert(NumItems + NumTombstones <= NumBuckets);
331 :
332 : BucketNo = RehashTable(BucketNo);
333 : return std::make_pair(iterator(TheTable + BucketNo, false), true);
334 : }
335 :
336 : // clear - Empties out the StringMap
337 : void clear() {
338 : if (empty()) return;
339 :
340 : // Zap all values, resetting the keys back to non-present (not tombstone),
341 : // which is safe because we're removing all elements.
342 : for (unsigned I = 0, E = NumBuckets; I != E; ++I) {
343 : StringMapEntryBase *&Bucket = TheTable[I];
344 : if (Bucket && Bucket != getTombstoneVal()) {
345 : static_cast<MapEntryTy*>(Bucket)->Destroy(Allocator);
346 : }
347 : Bucket = nullptr;
348 : }
349 :
350 : NumItems = 0;
351 : NumTombstones = 0;
352 : }
353 :
354 : /// remove - Remove the specified key/value pair from the map, but do not
355 : /// erase it. This aborts if the key is not in the map.
356 : void remove(MapEntryTy *KeyValue) {
357 : RemoveKey(KeyValue);
358 : }
359 :
360 : void erase(iterator I) {
361 : MapEntryTy &V = *I;
362 : remove(&V);
363 : V.Destroy(Allocator);
364 : }
365 :
366 : bool erase(StringRef Key) {
367 : iterator I = find(Key);
368 : if (I == end()) return false;
369 : erase(I);
370 : return true;
371 : }
372 :
373 : ~StringMap() {
374 : // Delete all the elements in the map, but don't reset the elements
375 : // to default values. This is a copy of clear(), but avoids unnecessary
376 : // work not required in the destructor.
377 48 : if (!empty()) {
378 816 : for (unsigned I = 0, E = NumBuckets; I != E; ++I) {
379 384 : StringMapEntryBase *Bucket = TheTable[I];
380 432 : if (Bucket && Bucket != getTombstoneVal()) {
381 24 : static_cast<MapEntryTy*>(Bucket)->Destroy(Allocator);
382 24 : }
383 384 : }
384 24 : }
385 24 : free(TheTable);
386 24 : }
387 : };
388 :
389 :
390 : template<typename ValueTy>
391 : class StringMapConstIterator {
392 : protected:
393 : StringMapEntryBase **Ptr;
394 : public:
395 : typedef StringMapEntry<ValueTy> value_type;
396 :
397 : StringMapConstIterator() : Ptr(nullptr) { }
398 :
399 : explicit StringMapConstIterator(StringMapEntryBase **Bucket,
400 : bool NoAdvance = false)
401 : : Ptr(Bucket) {
402 : if (!NoAdvance) AdvancePastEmptyBuckets();
403 : }
404 :
405 : const value_type &operator*() const {
406 : return *static_cast<StringMapEntry<ValueTy>*>(*Ptr);
407 : }
408 : const value_type *operator->() const {
409 : return static_cast<StringMapEntry<ValueTy>*>(*Ptr);
410 : }
411 :
412 : bool operator==(const StringMapConstIterator &RHS) const {
413 : return Ptr == RHS.Ptr;
414 : }
415 : bool operator!=(const StringMapConstIterator &RHS) const {
416 : return Ptr != RHS.Ptr;
417 : }
418 :
419 : inline StringMapConstIterator& operator++() { // Preincrement
420 : ++Ptr;
421 : AdvancePastEmptyBuckets();
422 : return *this;
423 : }
424 : StringMapConstIterator operator++(int) { // Postincrement
425 : StringMapConstIterator tmp = *this; ++*this; return tmp;
426 : }
427 :
428 : private:
429 : void AdvancePastEmptyBuckets() {
430 : while (*Ptr == nullptr || *Ptr == StringMapImpl::getTombstoneVal())
431 : ++Ptr;
432 : }
433 : };
434 :
435 : template<typename ValueTy>
436 : class StringMapIterator : public StringMapConstIterator<ValueTy> {
437 : public:
438 : StringMapIterator() {}
439 : explicit StringMapIterator(StringMapEntryBase **Bucket,
440 : bool NoAdvance = false)
441 : : StringMapConstIterator<ValueTy>(Bucket, NoAdvance) {
442 : }
443 : StringMapEntry<ValueTy> &operator*() const {
444 : return *static_cast<StringMapEntry<ValueTy>*>(*this->Ptr);
445 : }
446 : StringMapEntry<ValueTy> *operator->() const {
447 : return static_cast<StringMapEntry<ValueTy>*>(*this->Ptr);
448 : }
449 : };
450 :
451 : }
452 :
453 : #endif
|
