WPILibC++  unspecified
 All Classes Files Functions Variables Typedefs Enumerations Enumerator 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 LLVM_ADT_STRINGMAP_H
15 #define LLVM_ADT_STRINGMAP_H
16 
17 #include "llvm/StringRef.h"
18 #include <cstdlib>
19 #include <cstring>
20 #include <utility>
21 
22 namespace llvm {
23  template<typename ValueT>
25  template<typename ValueT>
27  template<typename ValueTy>
29 
32  unsigned StrLen;
33 public:
34  explicit StringMapEntryBase(unsigned Len) : StrLen(Len) {}
35 
36  unsigned getKeyLength() const { return StrLen; }
37 };
38 
42 protected:
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;
47  unsigned NumBuckets;
48  unsigned NumItems;
49  unsigned NumTombstones;
50  unsigned ItemSize;
51 protected:
52  explicit StringMapImpl(unsigned itemSize)
53  : TheTable(nullptr),
54  // Initialize the map with zero buckets to allocation.
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;
61  RHS.NumBuckets = 0;
62  RHS.NumItems = 0;
63  RHS.NumTombstones = 0;
64  }
65 
66  StringMapImpl(unsigned InitSize, unsigned ItemSize);
67  unsigned RehashTable(unsigned BucketNo = 0);
68 
74  unsigned LookupBucketFor(StringRef Key);
75 
79  int FindKey(StringRef Key) const;
80 
84 
88 private:
89  void init(unsigned Size);
90 public:
91  static StringMapEntryBase *getTombstoneVal() {
92  return (StringMapEntryBase*)-1;
93  }
94 
95  unsigned getNumBuckets() const { return NumBuckets; }
96  unsigned getNumItems() const { return NumItems; }
97 
98  bool empty() const { return NumItems == 0; }
99  unsigned size() const { return NumItems; }
100 
101  void swap(StringMapImpl &Other) {
102  std::swap(TheTable, Other.TheTable);
103  std::swap(NumBuckets, Other.NumBuckets);
104  std::swap(NumItems, Other.NumItems);
105  std::swap(NumTombstones, Other.NumTombstones);
106  }
107 };
108 
112 template<typename ValueTy>
113 class StringMapEntry : public StringMapEntryBase {
114  StringMapEntry(StringMapEntry &E) = delete;
115 public:
116  ValueTy second;
117 
118  explicit StringMapEntry(unsigned strLen)
119  : StringMapEntryBase(strLen), second() {}
120  template <class InitTy>
121  StringMapEntry(unsigned strLen, InitTy &&V)
122  : StringMapEntryBase(strLen), second(std::forward<InitTy>(V)) {}
123 
124  StringRef getKey() const {
125  return StringRef(getKeyData(), getKeyLength());
126  }
127 
128  const ValueTy &getValue() const { return second; }
129  ValueTy &getValue() { return second; }
130 
131  void setValue(const ValueTy &V) { second = V; }
132 
136  const char *getKeyData() const {return reinterpret_cast<const char*>(this+1);}
137 
138  StringRef first() const { return StringRef(getKeyData(), getKeyLength()); }
139 
142  template <typename InitType>
143  static StringMapEntry *Create(StringRef Key, InitType &&InitVal) {
144  unsigned KeyLength = Key.size();
145 
146  // Allocate a new item with space for the string at the end and a null
147  // terminator.
148  unsigned AllocSize = static_cast<unsigned>(sizeof(StringMapEntry))+
149  KeyLength+1;
150 
151  StringMapEntry *NewItem =
152  static_cast<StringMapEntry*>(std::malloc(AllocSize));
153 
154  // Default construct the value.
155  new (NewItem) StringMapEntry(KeyLength, std::forward<InitType>(InitVal));
156 
157  // Copy the string information.
158  char *StrBuffer = const_cast<char*>(NewItem->getKeyData());
159  memcpy(StrBuffer, Key.data(), KeyLength);
160  StrBuffer[KeyLength] = 0; // Null terminate for convenience of clients.
161  return NewItem;
162  }
163 
164  static StringMapEntry *Create(StringRef Key) {
165  return Create(Key, ValueTy());
166  }
167 
170  static StringMapEntry &GetStringMapEntryFromKeyData(const char *KeyData) {
171  char *Ptr = const_cast<char*>(KeyData) - sizeof(StringMapEntry<ValueTy>);
172  return *reinterpret_cast<StringMapEntry*>(Ptr);
173  }
174 
177  void Destroy() {
178  // Free memory referenced by the item.
179  this->~StringMapEntry();
180  std::free(static_cast<void *>(this));
181  }
182 };
183 
184 
189 template<typename ValueTy>
190 class StringMap : public StringMapImpl {
191 public:
193 
194  StringMap() : StringMapImpl(static_cast<unsigned>(sizeof(MapEntryTy))) {}
195  explicit StringMap(unsigned InitialSize)
196  : StringMapImpl(InitialSize, static_cast<unsigned>(sizeof(MapEntryTy))) {}
197 
198  StringMap(StringMap &&RHS)
199  : StringMapImpl(std::move(RHS)) {}
200 
201  StringMap &operator=(StringMap RHS) {
202  StringMapImpl::swap(RHS);
203  return *this;
204  }
205 
206  // FIXME: Implement copy operations if/when they're needed.
207 
208  typedef const char* key_type;
209  typedef ValueTy mapped_type;
211  typedef size_t size_type;
212 
215 
216  iterator begin() {
217  return iterator(TheTable, NumBuckets == 0);
218  }
219  iterator end() {
220  return iterator(TheTable+NumBuckets, true);
221  }
222  const_iterator begin() const {
223  return const_iterator(TheTable, NumBuckets == 0);
224  }
225  const_iterator end() const {
226  return const_iterator(TheTable+NumBuckets, true);
227  }
228 
229  iterator find(StringRef Key) {
230  int Bucket = FindKey(Key);
231  if (Bucket == -1) return end();
232  return iterator(TheTable+Bucket, true);
233  }
234 
235  const_iterator find(StringRef Key) const {
236  int Bucket = FindKey(Key);
237  if (Bucket == -1) return end();
238  return const_iterator(TheTable+Bucket, true);
239  }
240 
243  ValueTy lookup(StringRef Key) const {
244  const_iterator it = find(Key);
245  if (it != end())
246  return it->second;
247  return ValueTy();
248  }
249 
250  ValueTy &operator[](StringRef Key) {
251  return insert(std::make_pair(Key, ValueTy())).first->second;
252  }
253 
255  size_type count(StringRef Key) const {
256  return find(Key) == end() ? 0 : 1;
257  }
258 
262  bool insert(MapEntryTy *KeyValue) {
263  unsigned BucketNo = LookupBucketFor(KeyValue->getKey());
264  StringMapEntryBase *&Bucket = TheTable[BucketNo];
265  if (Bucket && Bucket != getTombstoneVal())
266  return false; // Already exists in map.
267 
268  if (Bucket == getTombstoneVal())
269  --NumTombstones;
270  Bucket = KeyValue;
271  ++NumItems;
272  assert(NumItems + NumTombstones <= NumBuckets);
273 
274  RehashTable();
275  return true;
276  }
277 
282  std::pair<iterator, bool> insert(std::pair<StringRef, ValueTy> KV) {
283  unsigned BucketNo = LookupBucketFor(KV.first);
284  StringMapEntryBase *&Bucket = TheTable[BucketNo];
285  if (Bucket && Bucket != getTombstoneVal())
286  return std::make_pair(iterator(TheTable + BucketNo, false),
287  false); // Already exists in map.
288 
289  if (Bucket == getTombstoneVal())
290  --NumTombstones;
291  Bucket =
292  MapEntryTy::Create(KV.first, std::move(KV.second));
293  ++NumItems;
294  assert(NumItems + NumTombstones <= NumBuckets);
295 
296  BucketNo = RehashTable(BucketNo);
297  return std::make_pair(iterator(TheTable + BucketNo, false), true);
298  }
299 
300  // clear - Empties out the StringMap
301  void clear() {
302  if (empty()) return;
303 
304  // Zap all values, resetting the keys back to non-present (not tombstone),
305  // which is safe because we're removing all elements.
306  for (unsigned I = 0, E = NumBuckets; I != E; ++I) {
307  StringMapEntryBase *&Bucket = TheTable[I];
308  if (Bucket && Bucket != getTombstoneVal()) {
309  static_cast<MapEntryTy*>(Bucket)->Destroy();
310  }
311  Bucket = nullptr;
312  }
313 
314  NumItems = 0;
315  NumTombstones = 0;
316  }
317 
320  void remove(MapEntryTy *KeyValue) {
321  RemoveKey(KeyValue);
322  }
323 
324  void erase(iterator I) {
325  MapEntryTy &V = *I;
326  remove(&V);
327  V.Destroy();
328  }
329 
330  bool erase(StringRef Key) {
331  iterator I = find(Key);
332  if (I == end()) return false;
333  erase(I);
334  return true;
335  }
336 
337  ~StringMap() {
338  // Delete all the elements in the map, but don't reset the elements
339  // to default values. This is a copy of clear(), but avoids unnecessary
340  // work not required in the destructor.
341  if (!empty()) {
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();
346  }
347  }
348  }
349  free(TheTable);
350  }
351 };
352 
353 
354 template<typename ValueTy>
355 class StringMapConstIterator {
356 protected:
357  StringMapEntryBase **Ptr;
358 public:
359  typedef StringMapEntry<ValueTy> value_type;
360 
361  StringMapConstIterator() : Ptr(nullptr) { }
362 
363  explicit StringMapConstIterator(StringMapEntryBase **Bucket,
364  bool NoAdvance = false)
365  : Ptr(Bucket) {
366  if (!NoAdvance) AdvancePastEmptyBuckets();
367  }
368 
369  const value_type &operator*() const {
370  return *static_cast<StringMapEntry<ValueTy>*>(*Ptr);
371  }
372  const value_type *operator->() const {
373  return static_cast<StringMapEntry<ValueTy>*>(*Ptr);
374  }
375 
376  bool operator==(const StringMapConstIterator &RHS) const {
377  return Ptr == RHS.Ptr;
378  }
379  bool operator!=(const StringMapConstIterator &RHS) const {
380  return Ptr != RHS.Ptr;
381  }
382 
383  inline StringMapConstIterator& operator++() { // Preincrement
384  ++Ptr;
385  AdvancePastEmptyBuckets();
386  return *this;
387  }
388  StringMapConstIterator operator++(int) { // Postincrement
389  StringMapConstIterator tmp = *this; ++*this; return tmp;
390  }
391 
392 private:
393  void AdvancePastEmptyBuckets() {
394  while (*Ptr == nullptr || *Ptr == StringMapImpl::getTombstoneVal())
395  ++Ptr;
396  }
397 };
398 
399 template<typename ValueTy>
400 class StringMapIterator : public StringMapConstIterator<ValueTy> {
401 public:
402  StringMapIterator() {}
403  explicit StringMapIterator(StringMapEntryBase **Bucket,
404  bool NoAdvance = false)
405  : StringMapConstIterator<ValueTy>(Bucket, NoAdvance) {
406  }
407  StringMapEntry<ValueTy> &operator*() const {
408  return *static_cast<StringMapEntry<ValueTy>*>(*this->Ptr);
409  }
410  StringMapEntry<ValueTy> *operator->() const {
411  return static_cast<StringMapEntry<ValueTy>*>(*this->Ptr);
412  }
413 };
414 
415 } // namespace llvm
416 
417 #endif
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