14 #ifndef LLVM_ADT_STRINGMAP_H
15 #define LLVM_ADT_STRINGMAP_H
17 #include "llvm/StringRef.h"
23 template<
typename ValueT>
25 template<
typename ValueT>
27 template<
typename ValueTy>
36 unsigned getKeyLength()
const {
return StrLen; }
49 unsigned NumTombstones;
55 NumBuckets(0), NumItems(0), NumTombstones(0), ItemSize(itemSize) {}
57 : TheTable(RHS.TheTable), NumBuckets(RHS.NumBuckets),
58 NumItems(RHS.NumItems), NumTombstones(RHS.NumTombstones),
59 ItemSize(RHS.ItemSize) {
60 RHS.TheTable =
nullptr;
63 RHS.NumTombstones = 0;
89 void init(
unsigned Size);
95 unsigned getNumBuckets()
const {
return NumBuckets; }
96 unsigned getNumItems()
const {
return NumItems; }
98 bool empty()
const {
return NumItems == 0; }
99 unsigned size()
const {
return NumItems; }
102 std::swap(TheTable, Other.TheTable);
103 std::swap(NumBuckets, Other.NumBuckets);
104 std::swap(NumItems, Other.NumItems);
105 std::swap(NumTombstones, Other.NumTombstones);
112 template<
typename ValueTy>
120 template <
class InitTy>
121 StringMapEntry(
unsigned strLen, InitTy &&V)
122 : StringMapEntryBase(strLen), second(std::forward<InitTy>(V)) {}
124 StringRef getKey()
const {
125 return StringRef(
getKeyData(), getKeyLength());
128 const ValueTy &getValue()
const {
return second; }
129 ValueTy &getValue() {
return second; }
131 void setValue(
const ValueTy &V) { second = V; }
136 const char *
getKeyData()
const {
return reinterpret_cast<const char*
>(
this+1);}
142 template <
typename InitType>
144 unsigned KeyLength = Key.
size();
148 unsigned AllocSize =
static_cast<unsigned>(
sizeof(
StringMapEntry))+
155 new (NewItem)
StringMapEntry(KeyLength, std::forward<InitType>(InitVal));
158 char *StrBuffer =
const_cast<char*
>(NewItem->
getKeyData());
159 memcpy(StrBuffer, Key.
data(), KeyLength);
160 StrBuffer[KeyLength] = 0;
165 return Create(Key, ValueTy());
180 std::free(static_cast<void *>(
this));
189 template<
typename ValueTy>
202 StringMapImpl::swap(RHS);
208 typedef const char* key_type;
209 typedef ValueTy mapped_type;
211 typedef size_t size_type;
217 return iterator(TheTable, NumBuckets == 0);
220 return iterator(TheTable+NumBuckets,
true);
231 if (Bucket == -1)
return end();
232 return iterator(TheTable+Bucket,
true);
237 if (Bucket == -1)
return end();
251 return insert(std::make_pair(Key, ValueTy())).first->second;
256 return find(Key) == end() ? 0 : 1;
265 if (Bucket && Bucket != getTombstoneVal())
268 if (Bucket == getTombstoneVal())
272 assert(NumItems + NumTombstones <= NumBuckets);
282 std::pair<iterator, bool>
insert(std::pair<StringRef, ValueTy> KV) {
285 if (Bucket && Bucket != getTombstoneVal())
286 return std::make_pair(
iterator(TheTable + BucketNo,
false),
289 if (Bucket == getTombstoneVal())
294 assert(NumItems + NumTombstones <= NumBuckets);
297 return std::make_pair(
iterator(TheTable + BucketNo,
false),
true);
306 for (
unsigned I = 0, E = NumBuckets; I != E; ++I) {
308 if (Bucket && Bucket != getTombstoneVal()) {
309 static_cast<MapEntryTy*
>(Bucket)->Destroy();
324 void erase(iterator I) {
330 bool erase(StringRef Key) {
331 iterator I = find(Key);
332 if (I == end())
return false;
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();
354 template<
typename ValueTy>
355 class StringMapConstIterator {
357 StringMapEntryBase **Ptr;
359 typedef StringMapEntry<ValueTy> value_type;
361 StringMapConstIterator() : Ptr(nullptr) { }
363 explicit StringMapConstIterator(StringMapEntryBase **Bucket,
364 bool NoAdvance =
false)
366 if (!NoAdvance) AdvancePastEmptyBuckets();
369 const value_type &operator*()
const {
370 return *
static_cast<StringMapEntry<ValueTy>*
>(*Ptr);
372 const value_type *operator->()
const {
373 return static_cast<StringMapEntry<ValueTy>*
>(*Ptr);
376 bool operator==(
const StringMapConstIterator &RHS)
const {
377 return Ptr == RHS.Ptr;
379 bool operator!=(
const StringMapConstIterator &RHS)
const {
380 return Ptr != RHS.Ptr;
383 inline StringMapConstIterator& operator++() {
385 AdvancePastEmptyBuckets();
388 StringMapConstIterator operator++(
int) {
389 StringMapConstIterator tmp = *
this; ++*
this;
return tmp;
393 void AdvancePastEmptyBuckets() {
394 while (*Ptr ==
nullptr || *Ptr == StringMapImpl::getTombstoneVal())
399 template<
typename ValueTy>
400 class StringMapIterator :
public StringMapConstIterator<ValueTy> {
402 StringMapIterator() {}
403 explicit StringMapIterator(StringMapEntryBase **Bucket,
404 bool NoAdvance =
false)
405 : StringMapConstIterator<ValueTy>(Bucket, NoAdvance) {
407 StringMapEntry<ValueTy> &operator*()
const {
408 return *
static_cast<StringMapEntry<ValueTy>*
>(*this->Ptr);
410 StringMapEntry<ValueTy> *operator->()
const {
411 return static_cast<StringMapEntry<ValueTy>*
>(*this->Ptr);
bool insert(MapEntryTy *KeyValue)
insert - Insert the specified key/value pair into the map.
Definition: StringMap.h:262
size_t size() const
size - Get the string size.
Definition: StringRef.h:112
StringMapEntry - This is used to represent one value that is inserted into a StringMap.
Definition: StringMap.h:28
unsigned RehashTable(unsigned BucketNo=0)
RehashTable - Grow the table, redistributing values into the buckets with the appropriate mod-of-hash...
Definition: StringMap.cpp:184
size_type count(StringRef Key) const
count - Return 1 if the element is in the map, 0 otherwise.
Definition: StringMap.h:255
static StringMapEntry * Create(StringRef Key, InitType &&InitVal)
Create - Create a StringMapEntry for the specified key and default construct the value.
Definition: StringMap.h:143
int FindKey(StringRef Key) const
FindKey - Look up the bucket that contains the specified key.
Definition: StringMap.cpp:116
unsigned LookupBucketFor(StringRef Key)
LookupBucketFor - Look up the bucket that the specified string should end up in.
Definition: StringMap.cpp:58
static StringMapEntry & GetStringMapEntryFromKeyData(const char *KeyData)
GetStringMapEntryFromKeyData - Given key data that is known to be embedded into a StringMapEntry...
Definition: StringMap.h:170
StringMapImpl - This is the base class of StringMap that is shared among all of its instantiations...
Definition: StringMap.h:41
const char * data() const
data - Get a pointer to the start of the string (which may not be null terminated).
Definition: StringRef.h:106
std::pair< iterator, bool > insert(std::pair< StringRef, ValueTy > KV)
insert - Inserts the specified key/value pair into the map if the key isn't already in the map...
Definition: StringMap.h:282
void Destroy()
Destroy - Destroy this StringMapEntry, releasing memory back to the specified allocator.
Definition: StringMap.h:177
Definition: StringMap.h:24
ValueTy lookup(StringRef Key) const
lookup - Return the entry for the specified key, or a default constructed value if no such entry exis...
Definition: StringMap.h:243
void RemoveKey(StringMapEntryBase *V)
RemoveKey - Remove the specified StringMapEntry from the table, but do not delete it...
Definition: StringMap.cpp:158
const char * getKeyData() const
getKeyData - Return the start of the string data that is the key for this value.
Definition: StringMap.h:136
StringMap - This is an unconventional map that is specialized for handling keys that are "strings"...
Definition: StringMap.h:190
Definition: StringMap.h:26
StringMapEntryBase - Shared base class of StringMapEntry instances.
Definition: StringMap.h:31
StringRef - Represent a constant reference to a string, i.e.
Definition: StringRef.h:39