14 #ifndef LLVM_ADT_STRINGMAP_H 15 #define LLVM_ADT_STRINGMAP_H 17 #include "llvm/SmallVector.h" 18 #include "llvm/StringRef.h" 19 #include "llvm/PointerLikeTypeTraits.h" 26 template<
typename ValueT>
28 template<
typename ValueT>
30 template<
typename ValueTy>
40 unsigned getKeyLength()
const {
return StrLen; }
53 unsigned NumTombstones;
60 NumBuckets(0), NumItems(0), NumTombstones(0), ItemSize(itemSize) {}
62 : TheTable(RHS.TheTable), NumBuckets(RHS.NumBuckets),
63 NumItems(RHS.NumItems), NumTombstones(RHS.NumTombstones),
64 ItemSize(RHS.ItemSize) {
65 RHS.TheTable =
nullptr;
68 RHS.NumTombstones = 0;
72 unsigned RehashTable(
unsigned BucketNo = 0);
96 void init(
unsigned Size);
100 uintptr_t Val =
static_cast<uintptr_t
>(-1);
101 Val <<= PointerLikeTypeTraits<StringMapEntryBase *>::NumLowBitsAvailable;
105 unsigned getNumBuckets()
const {
return NumBuckets; }
106 unsigned getNumItems()
const {
return NumItems; }
108 bool empty()
const {
return NumItems == 0; }
109 unsigned size()
const {
return NumItems; }
112 std::swap(TheTable, Other.TheTable);
113 std::swap(NumBuckets, Other.NumBuckets);
114 std::swap(NumItems, Other.NumItems);
115 std::swap(NumTombstones, Other.NumTombstones);
122 template<
typename ValueTy>
131 template <
typename... InitTy>
136 return StringRef(getKeyData(), getKeyLength());
139 const ValueTy &getValue()
const {
return second; }
140 ValueTy &getValue() {
return second; }
142 void setValue(
const ValueTy &V) { second = V; }
147 const char *
getKeyData()
const {
return reinterpret_cast<const char*
>(
this+1);}
153 template <
typename... InitTy>
155 unsigned KeyLength = Key.
size();
159 unsigned AllocSize =
static_cast<unsigned>(
sizeof(StringMapEntry))+
162 StringMapEntry *NewItem =
163 static_cast<StringMapEntry*
>(std::malloc(AllocSize));
166 new (NewItem) StringMapEntry(KeyLength, std::forward<InitTy>(InitVals)...);
169 char *StrBuffer =
const_cast<char*
>(NewItem->
getKeyData());
171 memcpy(StrBuffer, Key.
data(), KeyLength);
172 StrBuffer[KeyLength] = 0;
176 static StringMapEntry *Create(
StringRef Key) {
177 return Create(Key, ValueTy());
184 return *
reinterpret_cast<StringMapEntry*
>(Ptr);
191 this->~StringMapEntry();
192 std::free(static_cast<void *>(
this));
201 template<
typename ValueTy>
208 :
StringMapImpl(InitialSize, static_cast<unsigned>(
sizeof(MapEntryTy))) {}
210 StringMap(std::initializer_list<std::pair<StringRef, ValueTy>> List)
211 :
StringMapImpl(List.size(),
static_cast<unsigned>(
sizeof(MapEntryTy))) {
212 for (
const auto &P : List) {
221 StringMapImpl::swap(RHS);
232 init(RHS.NumBuckets);
233 unsigned *HashTable = (
unsigned *)(TheTable + NumBuckets + 1),
234 *RHSHashTable = (
unsigned *)(RHS.TheTable + NumBuckets + 1);
236 NumItems = RHS.NumItems;
237 NumTombstones = RHS.NumTombstones;
238 for (
unsigned I = 0, E = NumBuckets; I != E; ++I) {
240 if (!Bucket || Bucket == getTombstoneVal()) {
241 TheTable[I] = Bucket;
245 TheTable[I] = MapEntryTy::Create(
246 static_cast<MapEntryTy *>(Bucket)->getKey(),
247 static_cast<MapEntryTy *>(Bucket)->getValue());
248 HashTable[I] = RHSHashTable[I];
260 typedef const char* key_type;
261 typedef ValueTy mapped_type;
263 typedef size_t size_type;
269 return iterator(TheTable, NumBuckets == 0);
272 return iterator(TheTable+NumBuckets,
true);
274 const_iterator begin()
const {
275 return const_iterator(TheTable, NumBuckets == 0);
277 const_iterator end()
const {
278 return const_iterator(TheTable+NumBuckets,
true);
282 int Bucket = FindKey(Key);
283 if (Bucket == -1)
return end();
284 return iterator(TheTable+Bucket,
true);
287 const_iterator find(
StringRef Key)
const {
288 int Bucket = FindKey(Key);
289 if (Bucket == -1)
return end();
290 return const_iterator(TheTable+Bucket,
true);
296 const_iterator it = find(Key);
305 return emplace_second(Key).first->second;
310 return find(Key) == end() ? 0 : 1;
317 unsigned BucketNo = LookupBucketFor(KeyValue->getKey());
319 if (Bucket && Bucket != getTombstoneVal())
322 if (Bucket == getTombstoneVal())
326 assert(NumItems + NumTombstones <= NumBuckets);
336 std::pair<iterator, bool>
insert(std::pair<StringRef, ValueTy> KV) {
337 return emplace_second(KV.first, std::move(KV.second));
344 template <
typename... ArgsTy>
346 unsigned BucketNo = LookupBucketFor(Key);
348 if (Bucket && Bucket != getTombstoneVal())
349 return std::make_pair(iterator(TheTable + BucketNo,
false),
352 if (Bucket == getTombstoneVal())
354 Bucket = MapEntryTy::Create(Key, std::forward<ArgsTy>(Args)...);
356 assert(NumItems + NumTombstones <= NumBuckets);
358 BucketNo = RehashTable(BucketNo);
359 return std::make_pair(iterator(TheTable + BucketNo,
false),
true);
368 for (
unsigned I = 0, E = NumBuckets; I != E; ++I) {
370 if (Bucket && Bucket != getTombstoneVal()) {
371 static_cast<MapEntryTy*
>(Bucket)->Destroy();
382 void remove(MapEntryTy *KeyValue) {
386 void erase(iterator I) {
393 iterator I = find(Key);
394 if (I == end())
return false;
404 for (
unsigned I = 0, E = NumBuckets; I != E; ++I) {
406 if (Bucket && Bucket != getTombstoneVal()) {
407 static_cast<MapEntryTy*
>(Bucket)->Destroy();
425 bool NoAdvance =
false)
427 if (!NoAdvance) AdvancePastEmptyBuckets();
430 const value_type &operator*()
const {
433 const value_type *operator->()
const {
438 return Ptr == RHS.Ptr;
441 return Ptr != RHS.Ptr;
446 AdvancePastEmptyBuckets();
454 void AdvancePastEmptyBuckets() {
455 while (*Ptr ==
nullptr || *Ptr == StringMapImpl::getTombstoneVal())
460 template<
typename ValueTy>
465 bool NoAdvance =
false)
476 template <
typename ValueTy>
479 if (&lhs == &rhs)
return true;
482 if (lhs.size() != rhs.size())
return false;
486 lhs_items.reserve(lhs.size());
487 for (
auto i = lhs.begin(), end = lhs.end(); i != end; ++i)
488 lhs_items.push_back(i);
489 std::sort(lhs_items.begin(), lhs_items.end(),
492 return a->getKey() < b->getKey();
496 rhs_items.reserve(rhs.size());
497 for (
auto i = rhs.begin(), end = rhs.end(); i != end; ++i)
498 rhs_items.push_back(i);
499 std::sort(rhs_items.begin(), rhs_items.end(),
502 return a->getKey() < b->getKey();
506 for (
auto a = lhs_items.begin(), b = rhs_items.begin(),
507 aend = lhs_items.end(), bend = rhs_items.end();
508 a != aend && b != bend; ++a, ++b) {
509 if ((*a)->first() != (*b)->first() || (*a)->second != (*b)->second)
515 template <
typename ValueTy>
518 return !(lhs == rhs);
521 template <
typename ValueTy>
524 if (&lhs == &rhs)
return false;
528 lhs_keys.reserve(lhs.size());
529 for (
auto i = lhs.begin(), end = lhs.
end(); i != end; ++i)
530 lhs_keys.push_back(i->getKey());
531 std::sort(lhs_keys.begin(), lhs_keys.end());
534 rhs_keys.reserve(rhs.size());
535 for (
auto i = rhs.begin(), end = rhs.end(); i != end; ++i)
536 rhs_keys.push_back(i->getKey());
537 std::sort(rhs_keys.begin(), rhs_keys.end());
540 return lhs_keys < rhs_keys;
543 template <
typename ValueTy>
544 inline bool operator<=(const StringMap<ValueTy>& lhs,
549 template <
typename ValueTy>
552 return !(lhs <= rhs);
555 template <
typename ValueTy>
bool insert(MapEntryTy *KeyValue)
insert - Insert the specified key/value pair into the map.
Definition: StringMap.h:316
size_t size() const
size - Get the string size.
Definition: StringRef.h:149
StringMapEntry - This is used to represent one value that is inserted into a StringMap.
Definition: StringMap.h:31
size_type count(StringRef Key) const
count - Return 1 if the element is in the map, 0 otherwise.
Definition: StringMap.h:309
static StringMapEntry * Create(StringRef Key, InitTy &&...InitVals)
Create a StringMapEntry for the specified key construct the value using InitiVals.
Definition: StringMap.h:154
static StringMapEntry & GetStringMapEntryFromKeyData(const char *KeyData)
GetStringMapEntryFromKeyData - Given key data that is known to be embedded into a StringMapEntry...
Definition: StringMap.h:182
StringMapImpl - This is the base class of StringMap that is shared among all of its instantiations...
Definition: StringMap.h:45
const char * data() const
data - Get a pointer to the start of the string (which may not be null terminated).
Definition: StringRef.h:139
ValueTy & operator[](StringRef Key)
Lookup the ValueTy for the Key, or create a default constructed value if the key is not in the map...
Definition: StringMap.h:304
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:336
friend const_iterator end(StringRef path)
Get end iterator over path.
Definition: Path.cpp:163
void Destroy()
Destroy - Destroy this StringMapEntry, releasing memory back to the specified allocator.
Definition: StringMap.h:189
Definition: StringMap.h:27
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:295
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small...
Definition: SmallVector.h:834
const char * getKeyData() const
getKeyData - Return the start of the string data that is the key for this value.
Definition: StringMap.h:147
StringMap - This is an unconventional map that is specialized for handling keys that are "strings"...
Definition: StringMap.h:202
Definition: StringMap.h:29
StringMapEntryBase - Shared base class of StringMapEntry instances.
Definition: StringMap.h:34
StringRef - Represent a constant reference to a string, i.e.
Definition: StringRef.h:42
std::pair< iterator, bool > emplace_second(StringRef Key, ArgsTy &&...Args)
Emplace a new element for the specified key into the map if the key isn't already in the map...
Definition: StringMap.h:345