WPILibC++  2019.3.1
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Modules Pages
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 WPIUTIL_WPI_STRINGMAP_H
15 #define WPIUTIL_WPI_STRINGMAP_H
16 
17 #include "wpi/SmallVector.h"
18 #include "wpi/StringRef.h"
19 #include "wpi/iterator.h"
20 #include "wpi/iterator_range.h"
21 #include "wpi/PointerLikeTypeTraits.h"
22 #include "wpi/deprecated.h"
23 #include "wpi/memory.h"
24 #include <algorithm>
25 #include <cassert>
26 #include <cstdint>
27 #include <cstdlib>
28 #include <cstring>
29 #include <initializer_list>
30 #include <iterator>
31 #include <utility>
32 
33 namespace wpi {
34 
35 template<typename ValueTy> class StringMapConstIterator;
36 template<typename ValueTy> class StringMapIterator;
37 template<typename ValueTy> class StringMapKeyIterator;
38 template<typename ValueTy> class StringMapEntry;
39 
42  size_t StrLen;
43 
44 public:
45  explicit StringMapEntryBase(size_t Len) : StrLen(Len) {}
46 
47  size_t getKeyLength() const { return StrLen; }
48 };
49 
53 protected:
54  // Array of NumBuckets pointers to entries, null pointers are holes.
55  // TheTable[NumBuckets] contains a sentinel value for easy iteration. Followed
56  // by an array of the actual hash values as unsigned integers.
57  StringMapEntryBase **TheTable = nullptr;
58  unsigned NumBuckets = 0;
59  unsigned NumItems = 0;
60  unsigned NumTombstones = 0;
61  unsigned ItemSize;
62 
63 protected:
64  explicit StringMapImpl(unsigned itemSize)
65  : ItemSize(itemSize) {}
67  : TheTable(RHS.TheTable), NumBuckets(RHS.NumBuckets),
68  NumItems(RHS.NumItems), NumTombstones(RHS.NumTombstones),
69  ItemSize(RHS.ItemSize) {
70  RHS.TheTable = nullptr;
71  RHS.NumBuckets = 0;
72  RHS.NumItems = 0;
73  RHS.NumTombstones = 0;
74  }
75 
76  StringMapImpl(unsigned InitSize, unsigned ItemSize);
77  unsigned RehashTable(unsigned BucketNo = 0);
78 
84  unsigned LookupBucketFor(StringRef Key);
85 
89  int FindKey(StringRef Key) const;
90 
94 
98 
101  void init(unsigned Size);
102 
103 public:
104  static StringMapEntryBase *getTombstoneVal() {
105  uintptr_t Val = static_cast<uintptr_t>(-1);
106  Val <<= PointerLikeTypeTraits<StringMapEntryBase *>::NumLowBitsAvailable;
107  return reinterpret_cast<StringMapEntryBase *>(Val);
108  }
109 
110  unsigned getNumBuckets() const { return NumBuckets; }
111  unsigned getNumItems() const { return NumItems; }
112 
113  bool empty() const { return NumItems == 0; }
114  unsigned size() const { return NumItems; }
115 
116  void swap(StringMapImpl &Other) {
117  std::swap(TheTable, Other.TheTable);
118  std::swap(NumBuckets, Other.NumBuckets);
119  std::swap(NumItems, Other.NumItems);
120  std::swap(NumTombstones, Other.NumTombstones);
121  }
122 };
123 
127 template<typename ValueTy>
128 class StringMapEntry : public StringMapEntryBase {
129 public:
130  ValueTy second;
131 
132  explicit StringMapEntry(size_t strLen)
133  : StringMapEntryBase(strLen), second() {}
134  template <typename... InitTy>
135  StringMapEntry(size_t strLen, InitTy &&... InitVals)
136  : StringMapEntryBase(strLen), second(std::forward<InitTy>(InitVals)...) {}
137  StringMapEntry(StringMapEntry &E) = delete;
138 
139  StringRef getKey() const {
140  return StringRef(getKeyData(), getKeyLength());
141  }
142 
143  const ValueTy &getValue() const { return second; }
144  ValueTy &getValue() { return second; }
145 
146  void setValue(const ValueTy &V) { second = V; }
147 
151  const char *getKeyData() const {return reinterpret_cast<const char*>(this+1);}
152 
153  StringRef first() const { return StringRef(getKeyData(), getKeyLength()); }
154 
157  template <typename... InitTy>
158  static StringMapEntry *Create(StringRef Key, InitTy &&... InitVals) {
159  size_t KeyLength = Key.size();
160 
161  // Allocate a new item with space for the string at the end and a null
162  // terminator.
163  size_t AllocSize = sizeof(StringMapEntry) + KeyLength + 1;
164 
165  StringMapEntry *NewItem =
166  static_cast<StringMapEntry*>(CheckedMalloc(AllocSize));
167 
168  // Construct the value.
169  new (NewItem) StringMapEntry(KeyLength, std::forward<InitTy>(InitVals)...);
170 
171  // Copy the string information.
172  char *StrBuffer = const_cast<char*>(NewItem->getKeyData());
173  if (KeyLength > 0)
174  memcpy(StrBuffer, Key.data(), KeyLength);
175  StrBuffer[KeyLength] = 0; // Null terminate for convenience of clients.
176  return NewItem;
177  }
178 
179  static StringMapEntry *Create(StringRef Key) {
180  return Create(Key, ValueTy());
181  }
182 
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 
192  void Destroy() {
193  // Free memory referenced by the item.
194  this->~StringMapEntry();
195  std::free(static_cast<void *>(this));
196  }
197 };
198 
199 
204 template<typename ValueTy>
205 class StringMap : public StringMapImpl {
206 public:
208 
209  StringMap() : StringMapImpl(static_cast<unsigned>(sizeof(MapEntryTy))) {}
210 
211  explicit StringMap(unsigned InitialSize)
212  : StringMapImpl(InitialSize, static_cast<unsigned>(sizeof(MapEntryTy))) {}
213 
214  StringMap(std::initializer_list<std::pair<StringRef, ValueTy>> List)
215  : StringMapImpl(List.size(), static_cast<unsigned>(sizeof(MapEntryTy))) {
216  for (const auto &P : List) {
217  insert(P);
218  }
219  }
220 
221  StringMap(StringMap &&RHS)
222  : StringMapImpl(std::move(RHS)) {}
223 
224  StringMap(const StringMap &RHS) :
225  StringMapImpl(static_cast<unsigned>(sizeof(MapEntryTy))) {
226  if (RHS.empty())
227  return;
228 
229  // Allocate TheTable of the same size as RHS's TheTable, and set the
230  // sentinel appropriately (and NumBuckets).
231  init(RHS.NumBuckets);
232  unsigned *HashTable = (unsigned *)(TheTable + NumBuckets + 1),
233  *RHSHashTable = (unsigned *)(RHS.TheTable + NumBuckets + 1);
234 
235  NumItems = RHS.NumItems;
236  NumTombstones = RHS.NumTombstones;
237  for (unsigned I = 0, E = NumBuckets; I != E; ++I) {
238  StringMapEntryBase *Bucket = RHS.TheTable[I];
239  if (!Bucket || Bucket == getTombstoneVal()) {
240  TheTable[I] = Bucket;
241  continue;
242  }
243 
244  TheTable[I] = MapEntryTy::Create(
245  static_cast<MapEntryTy *>(Bucket)->getKey(),
246  static_cast<MapEntryTy *>(Bucket)->getValue());
247  HashTable[I] = RHSHashTable[I];
248  }
249 
250  // Note that here we've copied everything from the RHS into this object,
251  // tombstones included. We could, instead, have re-probed for each key to
252  // instantiate this new object without any tombstone buckets. The
253  // assumption here is that items are rarely deleted from most StringMaps,
254  // and so tombstones are rare, so the cost of re-probing for all inputs is
255  // not worthwhile.
256  }
257 
258  StringMap &operator=(StringMap RHS) {
259  StringMapImpl::swap(RHS);
260  return *this;
261  }
262 
263  ~StringMap() {
264  // Delete all the elements in the map, but don't reset the elements
265  // to default values. This is a copy of clear(), but avoids unnecessary
266  // work not required in the destructor.
267  if (!empty()) {
268  for (unsigned I = 0, E = NumBuckets; I != E; ++I) {
269  StringMapEntryBase *Bucket = TheTable[I];
270  if (Bucket && Bucket != getTombstoneVal()) {
271  static_cast<MapEntryTy*>(Bucket)->Destroy();
272  }
273  }
274  }
275  free(TheTable);
276  }
277 
278  using key_type = const char*;
279  using mapped_type = ValueTy;
281  using size_type = size_t;
282 
285 
286  iterator begin() {
287  return iterator(TheTable, NumBuckets == 0);
288  }
289  iterator end() {
290  return iterator(TheTable+NumBuckets, true);
291  }
292  const_iterator begin() const {
293  return const_iterator(TheTable, NumBuckets == 0);
294  }
295  const_iterator end() const {
296  return const_iterator(TheTable+NumBuckets, true);
297  }
298 
302  }
303 
304  iterator find(StringRef Key) {
305  int Bucket = FindKey(Key);
306  if (Bucket == -1) return end();
307  return iterator(TheTable+Bucket, true);
308  }
309 
310  const_iterator find(StringRef Key) const {
311  int Bucket = FindKey(Key);
312  if (Bucket == -1) return end();
313  return const_iterator(TheTable+Bucket, true);
314  }
315 
318  ValueTy lookup(StringRef Key) const {
319  const_iterator it = find(Key);
320  if (it != end())
321  return it->second;
322  return ValueTy();
323  }
324 
327  ValueTy &operator[](StringRef Key) { return try_emplace(Key).first->second; }
328 
330  size_type count(StringRef Key) const {
331  return find(Key) == end() ? 0 : 1;
332  }
333 
337  bool insert(MapEntryTy *KeyValue) {
338  unsigned BucketNo = LookupBucketFor(KeyValue->getKey());
339  StringMapEntryBase *&Bucket = TheTable[BucketNo];
340  if (Bucket && Bucket != getTombstoneVal())
341  return false; // Already exists in map.
342 
343  if (Bucket == getTombstoneVal())
344  --NumTombstones;
345  Bucket = KeyValue;
346  ++NumItems;
347  assert(NumItems + NumTombstones <= NumBuckets);
348 
349  RehashTable();
350  return true;
351  }
352 
357  std::pair<iterator, bool> insert(std::pair<StringRef, ValueTy> KV) {
358  return try_emplace(KV.first, std::move(KV.second));
359  }
360 
361  template <typename... ArgsTy>
362  WPI_DEPRECATED("use try_emplace instead")
363  std::pair<iterator, bool> emplace_second(StringRef Key, ArgsTy &&... Args) {
364  return try_emplace(Key, std::forward<ArgsTy>(Args)...);
365  }
366 
371  template <typename... ArgsTy>
372  std::pair<iterator, bool> try_emplace(StringRef Key, ArgsTy &&... Args) {
373  unsigned BucketNo = LookupBucketFor(Key);
374  StringMapEntryBase *&Bucket = TheTable[BucketNo];
375  if (Bucket && Bucket != getTombstoneVal())
376  return std::make_pair(iterator(TheTable + BucketNo, false),
377  false); // Already exists in map.
378 
379  if (Bucket == getTombstoneVal())
380  --NumTombstones;
381  Bucket = MapEntryTy::Create(Key, std::forward<ArgsTy>(Args)...);
382  ++NumItems;
383  assert(NumItems + NumTombstones <= NumBuckets);
384 
385  BucketNo = RehashTable(BucketNo);
386  return std::make_pair(iterator(TheTable + BucketNo, false), true);
387  }
388 
389  // clear - Empties out the StringMap
390  void clear() {
391  if (empty()) return;
392 
393  // Zap all values, resetting the keys back to non-present (not tombstone),
394  // which is safe because we're removing all elements.
395  for (unsigned I = 0, E = NumBuckets; I != E; ++I) {
396  StringMapEntryBase *&Bucket = TheTable[I];
397  if (Bucket && Bucket != getTombstoneVal()) {
398  static_cast<MapEntryTy*>(Bucket)->Destroy();
399  }
400  Bucket = nullptr;
401  }
402 
403  NumItems = 0;
404  NumTombstones = 0;
405  }
406 
409  void remove(MapEntryTy *KeyValue) {
410  RemoveKey(KeyValue);
411  }
412 
413  void erase(iterator I) {
414  MapEntryTy &V = *I;
415  remove(&V);
416  V.Destroy();
417  }
418 
419  bool erase(StringRef Key) {
420  iterator I = find(Key);
421  if (I == end()) return false;
422  erase(I);
423  return true;
424  }
425 };
426 
427 template <typename DerivedTy, typename ValueTy>
429  : public iterator_facade_base<DerivedTy, std::forward_iterator_tag,
430  ValueTy> {
431 protected:
432  StringMapEntryBase **Ptr = nullptr;
433 
434 public:
435  StringMapIterBase() = default;
436 
437  explicit StringMapIterBase(StringMapEntryBase **Bucket,
438  bool NoAdvance = false)
439  : Ptr(Bucket) {
440  if (!NoAdvance) AdvancePastEmptyBuckets();
441  }
442 
443  DerivedTy &operator=(const DerivedTy &Other) {
444  Ptr = Other.Ptr;
445  return static_cast<DerivedTy &>(*this);
446  }
447 
448  bool operator==(const DerivedTy &RHS) const { return Ptr == RHS.Ptr; }
449 
450  DerivedTy &operator++() { // Preincrement
451  ++Ptr;
452  AdvancePastEmptyBuckets();
453  return static_cast<DerivedTy &>(*this);
454  }
455 
456  DerivedTy operator++(int) { // Post-increment
457  DerivedTy Tmp(Ptr);
458  ++*this;
459  return Tmp;
460  }
461 
462  DerivedTy &operator--() { // Predecrement
463  --Ptr;
464  ReversePastEmptyBuckets();
465  return static_cast<DerivedTy &>(*this);
466  }
467 
468  DerivedTy operator--(int) { // Post-decrement
469  DerivedTy Tmp(Ptr);
470  --*this;
471  return Tmp;
472  }
473 
474 private:
475  void AdvancePastEmptyBuckets() {
476  while (*Ptr == nullptr || *Ptr == StringMapImpl::getTombstoneVal())
477  ++Ptr;
478  }
479  void ReversePastEmptyBuckets() {
480  while (*Ptr == nullptr || *Ptr == StringMapImpl::getTombstoneVal())
481  --Ptr;
482  }
483 };
484 
485 template <typename ValueTy>
487  : public StringMapIterBase<StringMapConstIterator<ValueTy>,
488  const StringMapEntry<ValueTy>> {
491 
492 public:
493  using value_type = const StringMapEntry<ValueTy>;
494 
495  StringMapConstIterator() = default;
496  explicit StringMapConstIterator(StringMapEntryBase **Bucket,
497  bool NoAdvance = false)
498  : base(Bucket, NoAdvance) {}
499 
500  value_type &operator*() const {
501  return *static_cast<value_type *>(*this->Ptr);
502  }
503 };
504 
505 template <typename ValueTy>
506 class StringMapIterator : public StringMapIterBase<StringMapIterator<ValueTy>,
507  StringMapEntry<ValueTy>> {
508  using base =
509  StringMapIterBase<StringMapIterator<ValueTy>, StringMapEntry<ValueTy>>;
510 
511 public:
512  using value_type = StringMapEntry<ValueTy>;
513 
514  StringMapIterator() = default;
515  explicit StringMapIterator(StringMapEntryBase **Bucket,
516  bool NoAdvance = false)
517  : base(Bucket, NoAdvance) {}
518 
519  value_type &operator*() const {
520  return *static_cast<value_type *>(*this->Ptr);
521  }
522 
523  operator StringMapConstIterator<ValueTy>() const {
524  return StringMapConstIterator<ValueTy>(this->Ptr, true);
525  }
526 };
527 
528 template <typename ValueTy>
529 class StringMapKeyIterator
530  : public iterator_adaptor_base<StringMapKeyIterator<ValueTy>,
531  StringMapConstIterator<ValueTy>,
532  std::forward_iterator_tag, StringRef> {
533  using base = iterator_adaptor_base<StringMapKeyIterator<ValueTy>,
534  StringMapConstIterator<ValueTy>,
535  std::forward_iterator_tag, StringRef>;
536 
537 public:
538  StringMapKeyIterator() = default;
539  explicit StringMapKeyIterator(StringMapConstIterator<ValueTy> Iter)
540  : base(std::move(Iter)) {}
541 
542  StringRef &operator*() {
543  Key = this->wrapped()->getKey();
544  return Key;
545  }
546 
547 private:
548  StringRef Key;
549 };
550 
551 template <typename ValueTy>
552 bool operator==(const StringMap<ValueTy>& lhs, const StringMap<ValueTy>& rhs) {
553  // same instance?
554  if (&lhs == &rhs) return true;
555 
556  // first check that sizes are identical
557  if (lhs.size() != rhs.size()) return false;
558 
559  // copy into vectors and sort by key
560  SmallVector<StringMapConstIterator<ValueTy>, 16> lhs_items;
561  lhs_items.reserve(lhs.size());
562  for (auto i = lhs.begin(), end = lhs.end(); i != end; ++i)
563  lhs_items.push_back(i);
564  std::sort(lhs_items.begin(), lhs_items.end(),
565  [](const StringMapConstIterator<ValueTy>& a,
566  const StringMapConstIterator<ValueTy>& b) {
567  return a->getKey() < b->getKey();
568  });
569 
570  SmallVector<StringMapConstIterator<ValueTy>, 16> rhs_items;
571  rhs_items.reserve(rhs.size());
572  for (auto i = rhs.begin(), end = rhs.end(); i != end; ++i)
573  rhs_items.push_back(i);
574  std::sort(rhs_items.begin(), rhs_items.end(),
575  [](const StringMapConstIterator<ValueTy>& a,
576  const StringMapConstIterator<ValueTy>& b) {
577  return a->getKey() < b->getKey();
578  });
579 
580  // compare vector keys and values
581  for (auto a = lhs_items.begin(), b = rhs_items.begin(),
582  aend = lhs_items.end(), bend = rhs_items.end();
583  a != aend && b != bend; ++a, ++b) {
584  if ((*a)->first() != (*b)->first() || (*a)->second != (*b)->second)
585  return false;
586  }
587  return true;
588 }
589 
590 template <typename ValueTy>
591 inline bool operator!=(const StringMap<ValueTy>& lhs,
592  const StringMap<ValueTy>& rhs) {
593  return !(lhs == rhs);
594 }
595 
596 template <typename ValueTy>
597 bool operator<(const StringMap<ValueTy>& lhs, const StringMap<ValueTy>& rhs) {
598  // same instance?
599  if (&lhs == &rhs) return false;
600 
601  // copy into vectors and sort by key
602  SmallVector<StringRef, 16> lhs_keys;
603  lhs_keys.reserve(lhs.size());
604  for (auto i = lhs.begin(), end = lhs.end(); i != end; ++i)
605  lhs_keys.push_back(i->getKey());
606  std::sort(lhs_keys.begin(), lhs_keys.end());
607 
608  SmallVector<StringRef, 16> rhs_keys;
609  rhs_keys.reserve(rhs.size());
610  for (auto i = rhs.begin(), end = rhs.end(); i != end; ++i)
611  rhs_keys.push_back(i->getKey());
612  std::sort(rhs_keys.begin(), rhs_keys.end());
613 
614  // use std::vector comparison
615  return lhs_keys < rhs_keys;
616 }
617 
618 template <typename ValueTy>
619 inline bool operator<=(const StringMap<ValueTy>& lhs,
620  const StringMap<ValueTy>& rhs) {
621  return !(rhs < lhs);
622 }
623 
624 template <typename ValueTy>
625 inline bool operator>(const StringMap<ValueTy>& lhs,
626  const StringMap<ValueTy>& rhs) {
627  return !(lhs <= rhs);
628 }
629 
630 template <typename ValueTy>
631 inline bool operator>=(const StringMap<ValueTy>& lhs,
632  const StringMap<ValueTy>& rhs) {
633  return !(lhs < rhs);
634 }
635 
636 } // end namespace wpi
637 
638 #endif // LLVM_ADT_STRINGMAP_H
static StringMapEntry * Create(StringRef Key, InitTy &&...InitVals)
Create a StringMapEntry for the specified key construct the value using InitiVals.
Definition: StringMap.h:158
void init(unsigned Size)
Allocate the table with the specified number of buckets and otherwise setup the map as empty...
Definition: StringMap.h:35
void Destroy()
Destroy - Destroy this StringMapEntry, releasing memory back to the specified allocator.
Definition: StringMap.h:192
Definition: StringMap.h:428
This provides a very simple, boring adaptor for a begin and end iterator into a range type...
Definition: optional.h:885
StringMapEntryBase - Shared base class of StringMapEntry instances.
Definition: StringMap.h:41
LLVM_NODISCARD LLVM_ATTRIBUTE_ALWAYS_INLINE const char * data() const noexcept
data - Get a pointer to the start of the string (which may not be null terminated).
Definition: StringRef.h:128
WPILib C++ utilities (wpiutil) namespace.
Definition: SmallString.h:21
friend const_iterator end(StringRef path)
Get end iterator over path.
CRTP base class which implements the entire standard iterator facade in terms of a minimal subset of ...
Definition: iterator.h:68
unsigned LookupBucketFor(StringRef Key)
LookupBucketFor - Look up the bucket that the specified string should end up in.
Definition: StringMap.h:37
static StringMapEntry & GetStringMapEntryFromKeyData(const char *KeyData)
GetStringMapEntryFromKeyData - Given key data that is known to be embedded into a StringMapEntry...
Definition: StringMap.h:185
A range adaptor for a pair of iterators.
Definition: iterator_range.h:32
size_type count(StringRef Key) const
count - Return 1 if the element is in the map, 0 otherwise.
Definition: StringMap.h:330
void RemoveKey(StringMapEntryBase *V)
RemoveKey - Remove the specified StringMapEntry from the table, but do not delete it...
StringMapImpl - This is the base class of StringMap that is shared among all of its instantiations...
Definition: StringMap.h:52
StringMapEntry - This is used to represent one value that is inserted into a StringMap.
Definition: StringMap.h:38
void * CheckedMalloc(size_t size)
Wrapper around std::malloc that calls std::terminate on out of memory.
Definition: StringMap.h:36
iterator_range< T > make_range(T x, T y)
Convenience function for iterating over sub-ranges.
Definition: iterator_range.h:54
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:327
const char * getKeyData() const
getKeyData - Return the start of the string data that is the key for this value.
Definition: StringMap.h:151
StringRef - Represent a constant reference to a string, i.e.
Definition: StringRef.h:49
int FindKey(StringRef Key) const
FindKey - Look up the bucket that contains the specified key.
LLVM_NODISCARD LLVM_ATTRIBUTE_ALWAYS_INLINE size_t size() const noexcept
size - Get the string size.
Definition: StringRef.h:138
StringMap - This is an unconventional map that is specialized for handling keys that are "strings"...
Definition: StringMap.h:205
bool insert(MapEntryTy *KeyValue)
insert - Insert the specified key/value pair into the map.
Definition: StringMap.h:337
std::pair< iterator, bool > try_emplace(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:372
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:357
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:318