WPILibC++  unspecified
StringMap.h
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/SmallVector.h"
18 #include "llvm/StringRef.h"
19 #include "llvm/PointerLikeTypeTraits.h"
20 #include <algorithm>
21 #include <cstdlib>
22 #include <cstring>
23 #include <utility>
24 
25 namespace llvm {
26  template<typename ValueT>
28  template<typename ValueT>
30  template<typename ValueTy>
32 
35  unsigned StrLen;
36 
37 public:
38  explicit StringMapEntryBase(unsigned Len) : StrLen(Len) {}
39 
40  unsigned getKeyLength() const { return StrLen; }
41 };
42 
46 protected:
47  // Array of NumBuckets pointers to entries, null pointers are holes.
48  // TheTable[NumBuckets] contains a sentinel value for easy iteration. Followed
49  // by an array of the actual hash values as unsigned integers.
50  StringMapEntryBase **TheTable;
51  unsigned NumBuckets;
52  unsigned NumItems;
53  unsigned NumTombstones;
54  unsigned ItemSize;
55 
56 protected:
57  explicit StringMapImpl(unsigned itemSize)
58  : TheTable(nullptr),
59  // Initialize the map with zero buckets to allocation.
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;
66  RHS.NumBuckets = 0;
67  RHS.NumItems = 0;
68  RHS.NumTombstones = 0;
69  }
70 
71  StringMapImpl(unsigned InitSize, unsigned ItemSize);
72  unsigned RehashTable(unsigned BucketNo = 0);
73 
79  unsigned LookupBucketFor(StringRef Key);
80 
84  int FindKey(StringRef Key) const;
85 
88  void RemoveKey(StringMapEntryBase *V);
89 
92  StringMapEntryBase *RemoveKey(StringRef Key);
93 
96  void init(unsigned Size);
97 
98 public:
99  static StringMapEntryBase *getTombstoneVal() {
100  uintptr_t Val = static_cast<uintptr_t>(-1);
101  Val <<= PointerLikeTypeTraits<StringMapEntryBase *>::NumLowBitsAvailable;
102  return reinterpret_cast<StringMapEntryBase *>(Val);
103  }
104 
105  unsigned getNumBuckets() const { return NumBuckets; }
106  unsigned getNumItems() const { return NumItems; }
107 
108  bool empty() const { return NumItems == 0; }
109  unsigned size() const { return NumItems; }
110 
111  void swap(StringMapImpl &Other) {
112  std::swap(TheTable, Other.TheTable);
113  std::swap(NumBuckets, Other.NumBuckets);
114  std::swap(NumItems, Other.NumItems);
115  std::swap(NumTombstones, Other.NumTombstones);
116  }
117 };
118 
122 template<typename ValueTy>
123 class StringMapEntry : public StringMapEntryBase {
124  StringMapEntry(StringMapEntry &E) = delete;
125 
126 public:
127  ValueTy second;
128 
129  explicit StringMapEntry(unsigned strLen)
130  : StringMapEntryBase(strLen), second() {}
131  template <typename... InitTy>
132  StringMapEntry(unsigned strLen, InitTy &&... InitVals)
133  : StringMapEntryBase(strLen), second(std::forward<InitTy>(InitVals)...) {}
134 
135  StringRef getKey() const {
136  return StringRef(getKeyData(), getKeyLength());
137  }
138 
139  const ValueTy &getValue() const { return second; }
140  ValueTy &getValue() { return second; }
141 
142  void setValue(const ValueTy &V) { second = V; }
143 
147  const char *getKeyData() const {return reinterpret_cast<const char*>(this+1);}
148 
149  StringRef first() const { return StringRef(getKeyData(), getKeyLength()); }
150 
153  template <typename... InitTy>
154  static StringMapEntry *Create(StringRef Key, InitTy &&... InitVals) {
155  unsigned KeyLength = Key.size();
156 
157  // Allocate a new item with space for the string at the end and a null
158  // terminator.
159  unsigned AllocSize = static_cast<unsigned>(sizeof(StringMapEntry))+
160  KeyLength+1;
161 
162  StringMapEntry *NewItem =
163  static_cast<StringMapEntry*>(std::malloc(AllocSize));
164 
165  // Construct the value.
166  new (NewItem) StringMapEntry(KeyLength, std::forward<InitTy>(InitVals)...);
167 
168  // Copy the string information.
169  char *StrBuffer = const_cast<char*>(NewItem->getKeyData());
170  if (KeyLength > 0)
171  memcpy(StrBuffer, Key.data(), KeyLength);
172  StrBuffer[KeyLength] = 0; // Null terminate for convenience of clients.
173  return NewItem;
174  }
175 
176  static StringMapEntry *Create(StringRef Key) {
177  return Create(Key, ValueTy());
178  }
179 
182  static StringMapEntry &GetStringMapEntryFromKeyData(const char *KeyData) {
183  char *Ptr = const_cast<char*>(KeyData) - sizeof(StringMapEntry<ValueTy>);
184  return *reinterpret_cast<StringMapEntry*>(Ptr);
185  }
186 
189  void Destroy() {
190  // Free memory referenced by the item.
191  this->~StringMapEntry();
192  std::free(static_cast<void *>(this));
193  }
194 };
195 
196 
201 template<typename ValueTy>
202 class StringMap : public StringMapImpl {
203 public:
205 
206  StringMap() : StringMapImpl(static_cast<unsigned>(sizeof(MapEntryTy))) {}
207  explicit StringMap(unsigned InitialSize)
208  : StringMapImpl(InitialSize, static_cast<unsigned>(sizeof(MapEntryTy))) {}
209 
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) {
213  insert(P);
214  }
215  }
216 
217  StringMap(StringMap &&RHS)
218  : StringMapImpl(std::move(RHS)) {}
219 
220  StringMap &operator=(StringMap RHS) {
221  StringMapImpl::swap(RHS);
222  return *this;
223  }
224 
225  StringMap(const StringMap &RHS) :
226  StringMapImpl(static_cast<unsigned>(sizeof(MapEntryTy))) {
227  if (RHS.empty())
228  return;
229 
230  // Allocate TheTable of the same size as RHS's TheTable, and set the
231  // sentinel appropriately (and NumBuckets).
232  init(RHS.NumBuckets);
233  unsigned *HashTable = (unsigned *)(TheTable + NumBuckets + 1),
234  *RHSHashTable = (unsigned *)(RHS.TheTable + NumBuckets + 1);
235 
236  NumItems = RHS.NumItems;
237  NumTombstones = RHS.NumTombstones;
238  for (unsigned I = 0, E = NumBuckets; I != E; ++I) {
239  StringMapEntryBase *Bucket = RHS.TheTable[I];
240  if (!Bucket || Bucket == getTombstoneVal()) {
241  TheTable[I] = Bucket;
242  continue;
243  }
244 
245  TheTable[I] = MapEntryTy::Create(
246  static_cast<MapEntryTy *>(Bucket)->getKey(),
247  static_cast<MapEntryTy *>(Bucket)->getValue());
248  HashTable[I] = RHSHashTable[I];
249  }
250 
251  // Note that here we've copied everything from the RHS into this object,
252  // tombstones included. We could, instead, have re-probed for each key to
253  // instantiate this new object without any tombstone buckets. The
254  // assumption here is that items are rarely deleted from most StringMaps,
255  // and so tombstones are rare, so the cost of re-probing for all inputs is
256  // not worthwhile.
257  }
258 
259 
260  typedef const char* key_type;
261  typedef ValueTy mapped_type;
263  typedef size_t size_type;
264 
267 
268  iterator begin() {
269  return iterator(TheTable, NumBuckets == 0);
270  }
271  iterator end() {
272  return iterator(TheTable+NumBuckets, true);
273  }
274  const_iterator begin() const {
275  return const_iterator(TheTable, NumBuckets == 0);
276  }
277  const_iterator end() const {
278  return const_iterator(TheTable+NumBuckets, true);
279  }
280 
281  iterator find(StringRef Key) {
282  int Bucket = FindKey(Key);
283  if (Bucket == -1) return end();
284  return iterator(TheTable+Bucket, true);
285  }
286 
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);
291  }
292 
295  ValueTy lookup(StringRef Key) const {
296  const_iterator it = find(Key);
297  if (it != end())
298  return it->second;
299  return ValueTy();
300  }
301 
304  ValueTy &operator[](StringRef Key) {
305  return emplace_second(Key).first->second;
306  }
307 
309  size_type count(StringRef Key) const {
310  return find(Key) == end() ? 0 : 1;
311  }
312 
316  bool insert(MapEntryTy *KeyValue) {
317  unsigned BucketNo = LookupBucketFor(KeyValue->getKey());
318  StringMapEntryBase *&Bucket = TheTable[BucketNo];
319  if (Bucket && Bucket != getTombstoneVal())
320  return false; // Already exists in map.
321 
322  if (Bucket == getTombstoneVal())
323  --NumTombstones;
324  Bucket = KeyValue;
325  ++NumItems;
326  assert(NumItems + NumTombstones <= NumBuckets);
327 
328  RehashTable();
329  return true;
330  }
331 
336  std::pair<iterator, bool> insert(std::pair<StringRef, ValueTy> KV) {
337  return emplace_second(KV.first, std::move(KV.second));
338  }
339 
344  template <typename... ArgsTy>
345  std::pair<iterator, bool> emplace_second(StringRef Key, ArgsTy &&... Args) {
346  unsigned BucketNo = LookupBucketFor(Key);
347  StringMapEntryBase *&Bucket = TheTable[BucketNo];
348  if (Bucket && Bucket != getTombstoneVal())
349  return std::make_pair(iterator(TheTable + BucketNo, false),
350  false); // Already exists in map.
351 
352  if (Bucket == getTombstoneVal())
353  --NumTombstones;
354  Bucket = MapEntryTy::Create(Key, std::forward<ArgsTy>(Args)...);
355  ++NumItems;
356  assert(NumItems + NumTombstones <= NumBuckets);
357 
358  BucketNo = RehashTable(BucketNo);
359  return std::make_pair(iterator(TheTable + BucketNo, false), true);
360  }
361 
362  // clear - Empties out the StringMap
363  void clear() {
364  if (empty()) return;
365 
366  // Zap all values, resetting the keys back to non-present (not tombstone),
367  // which is safe because we're removing all elements.
368  for (unsigned I = 0, E = NumBuckets; I != E; ++I) {
369  StringMapEntryBase *&Bucket = TheTable[I];
370  if (Bucket && Bucket != getTombstoneVal()) {
371  static_cast<MapEntryTy*>(Bucket)->Destroy();
372  }
373  Bucket = nullptr;
374  }
375 
376  NumItems = 0;
377  NumTombstones = 0;
378  }
379 
382  void remove(MapEntryTy *KeyValue) {
383  RemoveKey(KeyValue);
384  }
385 
386  void erase(iterator I) {
387  MapEntryTy &V = *I;
388  remove(&V);
389  V.Destroy();
390  }
391 
392  bool erase(StringRef Key) {
393  iterator I = find(Key);
394  if (I == end()) return false;
395  erase(I);
396  return true;
397  }
398 
399  ~StringMap() {
400  // Delete all the elements in the map, but don't reset the elements
401  // to default values. This is a copy of clear(), but avoids unnecessary
402  // work not required in the destructor.
403  if (!empty()) {
404  for (unsigned I = 0, E = NumBuckets; I != E; ++I) {
405  StringMapEntryBase *Bucket = TheTable[I];
406  if (Bucket && Bucket != getTombstoneVal()) {
407  static_cast<MapEntryTy*>(Bucket)->Destroy();
408  }
409  }
410  }
411  free(TheTable);
412  }
413 };
414 
415 template <typename ValueTy> class StringMapConstIterator {
416 protected:
417  StringMapEntryBase **Ptr;
418 
419 public:
421 
422  StringMapConstIterator() : Ptr(nullptr) { }
423 
424  explicit StringMapConstIterator(StringMapEntryBase **Bucket,
425  bool NoAdvance = false)
426  : Ptr(Bucket) {
427  if (!NoAdvance) AdvancePastEmptyBuckets();
428  }
429 
430  const value_type &operator*() const {
431  return *static_cast<StringMapEntry<ValueTy>*>(*Ptr);
432  }
433  const value_type *operator->() const {
434  return static_cast<StringMapEntry<ValueTy>*>(*Ptr);
435  }
436 
437  bool operator==(const StringMapConstIterator &RHS) const {
438  return Ptr == RHS.Ptr;
439  }
440  bool operator!=(const StringMapConstIterator &RHS) const {
441  return Ptr != RHS.Ptr;
442  }
443 
444  inline StringMapConstIterator& operator++() { // Preincrement
445  ++Ptr;
446  AdvancePastEmptyBuckets();
447  return *this;
448  }
449  StringMapConstIterator operator++(int) { // Postincrement
450  StringMapConstIterator tmp = *this; ++*this; return tmp;
451  }
452 
453 private:
454  void AdvancePastEmptyBuckets() {
455  while (*Ptr == nullptr || *Ptr == StringMapImpl::getTombstoneVal())
456  ++Ptr;
457  }
458 };
459 
460 template<typename ValueTy>
461 class StringMapIterator : public StringMapConstIterator<ValueTy> {
462 public:
463  StringMapIterator() {}
464  explicit StringMapIterator(StringMapEntryBase **Bucket,
465  bool NoAdvance = false)
466  : StringMapConstIterator<ValueTy>(Bucket, NoAdvance) {
467  }
468  StringMapEntry<ValueTy> &operator*() const {
469  return *static_cast<StringMapEntry<ValueTy>*>(*this->Ptr);
470  }
471  StringMapEntry<ValueTy> *operator->() const {
472  return static_cast<StringMapEntry<ValueTy>*>(*this->Ptr);
473  }
474 };
475 
476 template <typename ValueTy>
477 bool operator==(const StringMap<ValueTy>& lhs, const StringMap<ValueTy>& rhs) {
478  // same instance?
479  if (&lhs == &rhs) return true;
480 
481  // first check that sizes are identical
482  if (lhs.size() != rhs.size()) return false;
483 
484  // copy into vectors and sort by key
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();
493  });
494 
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();
503  });
504 
505  // compare vector keys and values
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)
510  return false;
511  }
512  return true;
513 }
514 
515 template <typename ValueTy>
516 inline bool operator!=(const StringMap<ValueTy>& lhs,
517  const StringMap<ValueTy>& rhs) {
518  return !(lhs == rhs);
519 }
520 
521 template <typename ValueTy>
522 bool operator<(const StringMap<ValueTy>& lhs, const StringMap<ValueTy>& rhs) {
523  // same instance?
524  if (&lhs == &rhs) return false;
525 
526  // copy into vectors and sort by key
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());
532 
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());
538 
539  // use std::vector comparison
540  return lhs_keys < rhs_keys;
541 }
542 
543 template <typename ValueTy>
544 inline bool operator<=(const StringMap<ValueTy>& lhs,
545  const StringMap<ValueTy>& rhs) {
546  return !(rhs < lhs);
547 }
548 
549 template <typename ValueTy>
550 inline bool operator>(const StringMap<ValueTy>& lhs,
551  const StringMap<ValueTy>& rhs) {
552  return !(lhs <= rhs);
553 }
554 
555 template <typename ValueTy>
556 inline bool operator>=(const StringMap<ValueTy>& lhs,
557  const StringMap<ValueTy>& rhs) {
558  return !(lhs < rhs);
559 }
560 
561 } // namespace llvm
562 
563 #endif
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
Definition: Path.inc:27
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&#39;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 &#39;vector&#39; (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&#39;t already in the map...
Definition: StringMap.h:345