1 //===--- StringMap.h - String Hash table map interface ----------*- C++ -*-===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // This file defines the StringMap class.
12 //===----------------------------------------------------------------------===//
14 #ifndef LLVM_ADT_STRINGMAP_H
15 #define LLVM_ADT_STRINGMAP_H
17 #include "llvm/ADT/StringRef.h"
18 #include "llvm/Support/Allocator.h"
23 template<typename ValueT>
24 class StringMapConstIterator;
25 template<typename ValueT>
26 class StringMapIterator;
27 template<typename ValueTy>
30 /// StringMapEntryBase - Shared base class of StringMapEntry instances.
31 class StringMapEntryBase {
34 explicit StringMapEntryBase(unsigned Len) : StrLen(Len) {}
36 unsigned getKeyLength() const { return StrLen; }
39 /// StringMapImpl - This is the base class of StringMap that is shared among
40 /// all of its instantiations.
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;
49 unsigned NumTombstones;
52 explicit StringMapImpl(unsigned itemSize)
54 // Initialize the map with zero buckets to allocation.
55 NumBuckets(0), NumItems(0), NumTombstones(0), ItemSize(itemSize) {}
56 StringMapImpl(StringMapImpl &&RHS) : TheTable(RHS.TheTable), NumBuckets(RHS.NumBuckets), NumItems(RHS.NumItems), NumTombstones(RHS.NumTombstones), ItemSize(RHS.ItemSize) {
57 RHS.TheTable = nullptr;
60 RHS.NumTombstones = 0;
63 StringMapImpl(unsigned InitSize, unsigned ItemSize);
66 /// LookupBucketFor - Look up the bucket that the specified string should end
67 /// up in. If it already exists as a key in the map, the Item pointer for the
68 /// specified bucket will be non-null. Otherwise, it will be null. In either
69 /// case, the FullHashValue field of the bucket will be set to the hash value
71 unsigned LookupBucketFor(StringRef Key);
73 /// FindKey - Look up the bucket that contains the specified key. If it exists
74 /// in the map, return the bucket number of the key. Otherwise return -1.
75 /// This does not modify the map.
76 int FindKey(StringRef Key) const;
78 /// RemoveKey - Remove the specified StringMapEntry from the table, but do not
79 /// delete it. This aborts if the value isn't in the table.
80 void RemoveKey(StringMapEntryBase *V);
82 /// RemoveKey - Remove the StringMapEntry for the specified key from the
83 /// table, returning it. If the key is not in the table, this returns null.
84 StringMapEntryBase *RemoveKey(StringRef Key);
86 void init(unsigned Size);
88 static StringMapEntryBase *getTombstoneVal() {
89 return (StringMapEntryBase*)-1;
92 unsigned getNumBuckets() const { return NumBuckets; }
93 unsigned getNumItems() const { return NumItems; }
95 bool empty() const { return NumItems == 0; }
96 unsigned size() const { return NumItems; }
98 void swap(StringMapImpl &Other) {
99 std::swap(TheTable, Other.TheTable);
100 std::swap(NumBuckets, Other.NumBuckets);
101 std::swap(NumItems, Other.NumItems);
102 std::swap(NumTombstones, Other.NumTombstones);
106 /// StringMapEntry - This is used to represent one value that is inserted into
107 /// a StringMap. It contains the Value itself and the key: the string length
109 template<typename ValueTy>
110 class StringMapEntry : public StringMapEntryBase {
111 StringMapEntry(StringMapEntry &E) LLVM_DELETED_FUNCTION;
115 explicit StringMapEntry(unsigned strLen)
116 : StringMapEntryBase(strLen), second() {}
117 StringMapEntry(unsigned strLen, ValueTy V)
118 : StringMapEntryBase(strLen), second(std::move(V)) {}
120 StringRef getKey() const {
121 return StringRef(getKeyData(), getKeyLength());
124 const ValueTy &getValue() const { return second; }
125 ValueTy &getValue() { return second; }
127 void setValue(const ValueTy &V) { second = V; }
129 /// getKeyData - Return the start of the string data that is the key for this
130 /// value. The string data is always stored immediately after the
131 /// StringMapEntry object.
132 const char *getKeyData() const {return reinterpret_cast<const char*>(this+1);}
134 StringRef first() const { return StringRef(getKeyData(), getKeyLength()); }
136 /// Create - Create a StringMapEntry for the specified key and default
137 /// construct the value.
138 template<typename AllocatorTy, typename InitType>
139 static StringMapEntry *Create(const char *KeyStart, const char *KeyEnd,
140 AllocatorTy &Allocator,
142 unsigned KeyLength = static_cast<unsigned>(KeyEnd-KeyStart);
144 // Allocate a new item with space for the string at the end and a null
146 unsigned AllocSize = static_cast<unsigned>(sizeof(StringMapEntry))+
148 unsigned Alignment = alignOf<StringMapEntry>();
150 StringMapEntry *NewItem =
151 static_cast<StringMapEntry*>(Allocator.Allocate(AllocSize,Alignment));
153 // Default construct the value.
154 new (NewItem) StringMapEntry(KeyLength, std::move(InitVal));
156 // Copy the string information.
157 char *StrBuffer = const_cast<char*>(NewItem->getKeyData());
158 memcpy(StrBuffer, KeyStart, KeyLength);
159 StrBuffer[KeyLength] = 0; // Null terminate for convenience of clients.
163 template<typename AllocatorTy>
164 static StringMapEntry *Create(const char *KeyStart, const char *KeyEnd,
165 AllocatorTy &Allocator) {
166 return Create(KeyStart, KeyEnd, Allocator, 0);
169 /// Create - Create a StringMapEntry with normal malloc/free.
170 template<typename InitType>
171 static StringMapEntry *Create(const char *KeyStart, const char *KeyEnd,
174 return Create(KeyStart, KeyEnd, A, std::move(InitVal));
177 static StringMapEntry *Create(const char *KeyStart, const char *KeyEnd) {
178 return Create(KeyStart, KeyEnd, ValueTy());
181 /// GetStringMapEntryFromValue - Given a value that is known to be embedded
182 /// into a StringMapEntry, return the StringMapEntry itself.
183 static StringMapEntry &GetStringMapEntryFromValue(ValueTy &V) {
184 StringMapEntry *EPtr = 0;
185 char *Ptr = reinterpret_cast<char*>(&V) -
186 (reinterpret_cast<char*>(&EPtr->second) -
187 reinterpret_cast<char*>(EPtr));
188 return *reinterpret_cast<StringMapEntry*>(Ptr);
190 static const StringMapEntry &GetStringMapEntryFromValue(const ValueTy &V) {
191 return GetStringMapEntryFromValue(const_cast<ValueTy&>(V));
194 /// GetStringMapEntryFromKeyData - Given key data that is known to be embedded
195 /// into a StringMapEntry, return the StringMapEntry itself.
196 static StringMapEntry &GetStringMapEntryFromKeyData(const char *KeyData) {
197 char *Ptr = const_cast<char*>(KeyData) - sizeof(StringMapEntry<ValueTy>);
198 return *reinterpret_cast<StringMapEntry*>(Ptr);
201 /// Destroy - Destroy this StringMapEntry, releasing memory back to the
202 /// specified allocator.
203 template<typename AllocatorTy>
204 void Destroy(AllocatorTy &Allocator) {
205 // Free memory referenced by the item.
207 static_cast<unsigned>(sizeof(StringMapEntry)) + getKeyLength() + 1;
208 this->~StringMapEntry();
209 Allocator.Deallocate(static_cast<void *>(this), AllocSize);
212 /// Destroy this object, releasing memory back to the malloc allocator.
220 /// StringMap - This is an unconventional map that is specialized for handling
221 /// keys that are "strings", which are basically ranges of bytes. This does some
222 /// funky memory allocation and hashing things to make it extremely efficient,
223 /// storing the string data *after* the value in the map.
224 template<typename ValueTy, typename AllocatorTy = MallocAllocator>
225 class StringMap : public StringMapImpl {
226 AllocatorTy Allocator;
228 typedef StringMapEntry<ValueTy> MapEntryTy;
230 StringMap() : StringMapImpl(static_cast<unsigned>(sizeof(MapEntryTy))) {}
231 explicit StringMap(unsigned InitialSize)
232 : StringMapImpl(InitialSize, static_cast<unsigned>(sizeof(MapEntryTy))) {}
234 explicit StringMap(AllocatorTy A)
235 : StringMapImpl(static_cast<unsigned>(sizeof(MapEntryTy))), Allocator(A) {}
237 StringMap(unsigned InitialSize, AllocatorTy A)
238 : StringMapImpl(InitialSize, static_cast<unsigned>(sizeof(MapEntryTy))),
241 StringMap(StringMap &&RHS)
242 : StringMapImpl(std::move(RHS)), Allocator(std::move(RHS.Allocator)) {}
244 StringMap &operator=(StringMap RHS) {
245 StringMapImpl::swap(RHS);
246 std::swap(Allocator, RHS.Allocator);
250 // FIXME: Implement copy operations if/when they're needed.
252 AllocatorTy &getAllocator() { return Allocator; }
253 const AllocatorTy &getAllocator() const { return Allocator; }
255 typedef const char* key_type;
256 typedef ValueTy mapped_type;
257 typedef StringMapEntry<ValueTy> value_type;
258 typedef size_t size_type;
260 typedef StringMapConstIterator<ValueTy> const_iterator;
261 typedef StringMapIterator<ValueTy> iterator;
264 return iterator(TheTable, NumBuckets == 0);
267 return iterator(TheTable+NumBuckets, true);
269 const_iterator begin() const {
270 return const_iterator(TheTable, NumBuckets == 0);
272 const_iterator end() const {
273 return const_iterator(TheTable+NumBuckets, true);
276 iterator find(StringRef Key) {
277 int Bucket = FindKey(Key);
278 if (Bucket == -1) return end();
279 return iterator(TheTable+Bucket, true);
282 const_iterator find(StringRef Key) const {
283 int Bucket = FindKey(Key);
284 if (Bucket == -1) return end();
285 return const_iterator(TheTable+Bucket, true);
288 /// lookup - Return the entry for the specified key, or a default
289 /// constructed value if no such entry exists.
290 ValueTy lookup(StringRef Key) const {
291 const_iterator it = find(Key);
297 ValueTy &operator[](StringRef Key) {
298 return GetOrCreateValue(Key).getValue();
301 /// count - Return 1 if the element is in the map, 0 otherwise.
302 size_type count(StringRef Key) const {
303 return find(Key) == end() ? 0 : 1;
306 /// insert - Insert the specified key/value pair into the map. If the key
307 /// already exists in the map, return false and ignore the request, otherwise
308 /// insert it and return true.
309 bool insert(MapEntryTy *KeyValue) {
310 unsigned BucketNo = LookupBucketFor(KeyValue->getKey());
311 StringMapEntryBase *&Bucket = TheTable[BucketNo];
312 if (Bucket && Bucket != getTombstoneVal())
313 return false; // Already exists in map.
315 if (Bucket == getTombstoneVal())
319 assert(NumItems + NumTombstones <= NumBuckets);
325 // clear - Empties out the StringMap
329 // Zap all values, resetting the keys back to non-present (not tombstone),
330 // which is safe because we're removing all elements.
331 for (unsigned I = 0, E = NumBuckets; I != E; ++I) {
332 StringMapEntryBase *&Bucket = TheTable[I];
333 if (Bucket && Bucket != getTombstoneVal()) {
334 static_cast<MapEntryTy*>(Bucket)->Destroy(Allocator);
343 /// GetOrCreateValue - Look up the specified key in the table. If a value
344 /// exists, return it. Otherwise, default construct a value, insert it, and
346 template <typename InitTy>
347 MapEntryTy &GetOrCreateValue(StringRef Key, InitTy Val) {
348 unsigned BucketNo = LookupBucketFor(Key);
349 StringMapEntryBase *&Bucket = TheTable[BucketNo];
350 if (Bucket && Bucket != getTombstoneVal())
351 return *static_cast<MapEntryTy*>(Bucket);
353 MapEntryTy *NewItem =
354 MapEntryTy::Create(Key.begin(), Key.end(), Allocator, std::move(Val));
356 if (Bucket == getTombstoneVal())
359 assert(NumItems + NumTombstones <= NumBuckets);
361 // Fill in the bucket for the hash table. The FullHashValue was already
362 // filled in by LookupBucketFor.
369 MapEntryTy &GetOrCreateValue(StringRef Key) {
370 return GetOrCreateValue(Key, ValueTy());
373 /// remove - Remove the specified key/value pair from the map, but do not
374 /// erase it. This aborts if the key is not in the map.
375 void remove(MapEntryTy *KeyValue) {
379 void erase(iterator I) {
382 V.Destroy(Allocator);
385 bool erase(StringRef Key) {
386 iterator I = find(Key);
387 if (I == end()) return false;
393 // Delete all the elements in the map, but don't reset the elements
394 // to default values. This is a copy of clear(), but avoids unnecessary
395 // work not required in the destructor.
397 for (unsigned I = 0, E = NumBuckets; I != E; ++I) {
398 StringMapEntryBase *Bucket = TheTable[I];
399 if (Bucket && Bucket != getTombstoneVal()) {
400 static_cast<MapEntryTy*>(Bucket)->Destroy(Allocator);
409 template<typename ValueTy>
410 class StringMapConstIterator {
412 StringMapEntryBase **Ptr;
414 typedef StringMapEntry<ValueTy> value_type;
416 StringMapConstIterator() : Ptr(nullptr) { }
418 explicit StringMapConstIterator(StringMapEntryBase **Bucket,
419 bool NoAdvance = false)
421 if (!NoAdvance) AdvancePastEmptyBuckets();
424 const value_type &operator*() const {
425 return *static_cast<StringMapEntry<ValueTy>*>(*Ptr);
427 const value_type *operator->() const {
428 return static_cast<StringMapEntry<ValueTy>*>(*Ptr);
431 bool operator==(const StringMapConstIterator &RHS) const {
432 return Ptr == RHS.Ptr;
434 bool operator!=(const StringMapConstIterator &RHS) const {
435 return Ptr != RHS.Ptr;
438 inline StringMapConstIterator& operator++() { // Preincrement
440 AdvancePastEmptyBuckets();
443 StringMapConstIterator operator++(int) { // Postincrement
444 StringMapConstIterator tmp = *this; ++*this; return tmp;
448 void AdvancePastEmptyBuckets() {
449 while (*Ptr == nullptr || *Ptr == StringMapImpl::getTombstoneVal())
454 template<typename ValueTy>
455 class StringMapIterator : public StringMapConstIterator<ValueTy> {
457 StringMapIterator() {}
458 explicit StringMapIterator(StringMapEntryBase **Bucket,
459 bool NoAdvance = false)
460 : StringMapConstIterator<ValueTy>(Bucket, NoAdvance) {
462 StringMapEntry<ValueTy> &operator*() const {
463 return *static_cast<StringMapEntry<ValueTy>*>(*this->Ptr);
465 StringMapEntry<ValueTy> *operator->() const {
466 return static_cast<StringMapEntry<ValueTy>*>(*this->Ptr);