• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
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/ADT/StringRef.h"
18 #include "llvm/Support/Allocator.h"
19 #include <cstring>
20 
21 namespace llvm {
22   template<typename ValueT>
23   class StringMapConstIterator;
24   template<typename ValueT>
25   class StringMapIterator;
26   template<typename ValueTy>
27   class StringMapEntry;
28 
29 /// StringMapEntryInitializer - This datatype can be partially specialized for
30 /// various datatypes in a stringmap to allow them to be initialized when an
31 /// entry is default constructed for the map.
32 template<typename ValueTy>
33 class StringMapEntryInitializer {
34 public:
35   template <typename InitTy>
Initialize(StringMapEntry<ValueTy> & T,InitTy InitVal)36   static void Initialize(StringMapEntry<ValueTy> &T, InitTy InitVal) {
37     T.second = InitVal;
38   }
39 };
40 
41 
42 /// StringMapEntryBase - Shared base class of StringMapEntry instances.
43 class StringMapEntryBase {
44   unsigned StrLen;
45 public:
StringMapEntryBase(unsigned Len)46   explicit StringMapEntryBase(unsigned Len) : StrLen(Len) {}
47 
getKeyLength()48   unsigned getKeyLength() const { return StrLen; }
49 };
50 
51 /// StringMapImpl - This is the base class of StringMap that is shared among
52 /// all of its instantiations.
53 class StringMapImpl {
54 protected:
55   // Array of NumBuckets pointers to entries, null pointers are holes.
56   // TheTable[NumBuckets] contains a sentinel value for easy iteration. Followed
57   // by an array of the actual hash values as unsigned integers.
58   StringMapEntryBase **TheTable;
59   unsigned NumBuckets;
60   unsigned NumItems;
61   unsigned NumTombstones;
62   unsigned ItemSize;
63 protected:
StringMapImpl(unsigned itemSize)64   explicit StringMapImpl(unsigned itemSize) : ItemSize(itemSize) {
65     // Initialize the map with zero buckets to allocation.
66     TheTable = 0;
67     NumBuckets = 0;
68     NumItems = 0;
69     NumTombstones = 0;
70   }
71   StringMapImpl(unsigned InitSize, unsigned ItemSize);
72   void RehashTable();
73 
74   /// LookupBucketFor - Look up the bucket that the specified string should end
75   /// up in.  If it already exists as a key in the map, the Item pointer for the
76   /// specified bucket will be non-null.  Otherwise, it will be null.  In either
77   /// case, the FullHashValue field of the bucket will be set to the hash value
78   /// of the string.
79   unsigned LookupBucketFor(StringRef Key);
80 
81   /// FindKey - Look up the bucket that contains the specified key. If it exists
82   /// in the map, return the bucket number of the key.  Otherwise return -1.
83   /// This does not modify the map.
84   int FindKey(StringRef Key) const;
85 
86   /// RemoveKey - Remove the specified StringMapEntry from the table, but do not
87   /// delete it.  This aborts if the value isn't in the table.
88   void RemoveKey(StringMapEntryBase *V);
89 
90   /// RemoveKey - Remove the StringMapEntry for the specified key from the
91   /// table, returning it.  If the key is not in the table, this returns null.
92   StringMapEntryBase *RemoveKey(StringRef Key);
93 private:
94   void init(unsigned Size);
95 public:
getTombstoneVal()96   static StringMapEntryBase *getTombstoneVal() {
97     return (StringMapEntryBase*)-1;
98   }
99 
getNumBuckets()100   unsigned getNumBuckets() const { return NumBuckets; }
getNumItems()101   unsigned getNumItems() const { return NumItems; }
102 
empty()103   bool empty() const { return NumItems == 0; }
size()104   unsigned size() const { return NumItems; }
105 };
106 
107 /// StringMapEntry - This is used to represent one value that is inserted into
108 /// a StringMap.  It contains the Value itself and the key: the string length
109 /// and data.
110 template<typename ValueTy>
111 class StringMapEntry : public StringMapEntryBase {
112 public:
113   ValueTy second;
114 
StringMapEntry(unsigned strLen)115   explicit StringMapEntry(unsigned strLen)
116     : StringMapEntryBase(strLen), second() {}
StringMapEntry(unsigned strLen,const ValueTy & V)117   StringMapEntry(unsigned strLen, const ValueTy &V)
118     : StringMapEntryBase(strLen), second(V) {}
119 
getKey()120   StringRef getKey() const {
121     return StringRef(getKeyData(), getKeyLength());
122   }
123 
getValue()124   const ValueTy &getValue() const { return second; }
getValue()125   ValueTy &getValue() { return second; }
126 
setValue(const ValueTy & V)127   void setValue(const ValueTy &V) { second = V; }
128 
129   /// getKeyData - Return the start of the string data that is the key for this
130   /// value.  The string data is always stored immediately after the
131   /// StringMapEntry object.
getKeyData()132   const char *getKeyData() const {return reinterpret_cast<const char*>(this+1);}
133 
first()134   StringRef first() const { return StringRef(getKeyData(), getKeyLength()); }
135 
136   /// Create - Create a StringMapEntry for the specified key and default
137   /// construct the value.
138   template<typename AllocatorTy, typename InitType>
Create(const char * KeyStart,const char * KeyEnd,AllocatorTy & Allocator,InitType InitVal)139   static StringMapEntry *Create(const char *KeyStart, const char *KeyEnd,
140                                 AllocatorTy &Allocator,
141                                 InitType InitVal) {
142     unsigned KeyLength = static_cast<unsigned>(KeyEnd-KeyStart);
143 
144     // Okay, the item doesn't already exist, and 'Bucket' is the bucket to fill
145     // in.  Allocate a new item with space for the string at the end and a null
146     // terminator.
147 
148     unsigned AllocSize = static_cast<unsigned>(sizeof(StringMapEntry))+
149       KeyLength+1;
150     unsigned Alignment = alignOf<StringMapEntry>();
151 
152     StringMapEntry *NewItem =
153       static_cast<StringMapEntry*>(Allocator.Allocate(AllocSize,Alignment));
154 
155     // Default construct the value.
156     new (NewItem) StringMapEntry(KeyLength);
157 
158     // Copy the string information.
159     char *StrBuffer = const_cast<char*>(NewItem->getKeyData());
160     memcpy(StrBuffer, KeyStart, KeyLength);
161     StrBuffer[KeyLength] = 0;  // Null terminate for convenience of clients.
162 
163     // Initialize the value if the client wants to.
164     StringMapEntryInitializer<ValueTy>::Initialize(*NewItem, InitVal);
165     return NewItem;
166   }
167 
168   template<typename AllocatorTy>
Create(const char * KeyStart,const char * KeyEnd,AllocatorTy & Allocator)169   static StringMapEntry *Create(const char *KeyStart, const char *KeyEnd,
170                                 AllocatorTy &Allocator) {
171     return Create(KeyStart, KeyEnd, Allocator, 0);
172   }
173 
174   /// Create - Create a StringMapEntry with normal malloc/free.
175   template<typename InitType>
Create(const char * KeyStart,const char * KeyEnd,InitType InitVal)176   static StringMapEntry *Create(const char *KeyStart, const char *KeyEnd,
177                                 InitType InitVal) {
178     MallocAllocator A;
179     return Create(KeyStart, KeyEnd, A, InitVal);
180   }
181 
Create(const char * KeyStart,const char * KeyEnd)182   static StringMapEntry *Create(const char *KeyStart, const char *KeyEnd) {
183     return Create(KeyStart, KeyEnd, ValueTy());
184   }
185 
186   /// GetStringMapEntryFromValue - Given a value that is known to be embedded
187   /// into a StringMapEntry, return the StringMapEntry itself.
GetStringMapEntryFromValue(ValueTy & V)188   static StringMapEntry &GetStringMapEntryFromValue(ValueTy &V) {
189     StringMapEntry *EPtr = 0;
190     char *Ptr = reinterpret_cast<char*>(&V) -
191                   (reinterpret_cast<char*>(&EPtr->second) -
192                    reinterpret_cast<char*>(EPtr));
193     return *reinterpret_cast<StringMapEntry*>(Ptr);
194   }
GetStringMapEntryFromValue(const ValueTy & V)195   static const StringMapEntry &GetStringMapEntryFromValue(const ValueTy &V) {
196     return GetStringMapEntryFromValue(const_cast<ValueTy&>(V));
197   }
198 
199   /// GetStringMapEntryFromKeyData - Given key data that is known to be embedded
200   /// into a StringMapEntry, return the StringMapEntry itself.
GetStringMapEntryFromKeyData(const char * KeyData)201   static StringMapEntry &GetStringMapEntryFromKeyData(const char *KeyData) {
202     char *Ptr = const_cast<char*>(KeyData) - sizeof(StringMapEntry<ValueTy>);
203     return *reinterpret_cast<StringMapEntry*>(Ptr);
204   }
205 
206   /// Destroy - Destroy this StringMapEntry, releasing memory back to the
207   /// specified allocator.
208   template<typename AllocatorTy>
Destroy(AllocatorTy & Allocator)209   void Destroy(AllocatorTy &Allocator) {
210     // Free memory referenced by the item.
211     this->~StringMapEntry();
212     Allocator.Deallocate(this);
213   }
214 
215   /// Destroy this object, releasing memory back to the malloc allocator.
Destroy()216   void Destroy() {
217     MallocAllocator A;
218     Destroy(A);
219   }
220 };
221 
222 
223 /// StringMap - This is an unconventional map that is specialized for handling
224 /// keys that are "strings", which are basically ranges of bytes. This does some
225 /// funky memory allocation and hashing things to make it extremely efficient,
226 /// storing the string data *after* the value in the map.
227 template<typename ValueTy, typename AllocatorTy = MallocAllocator>
228 class StringMap : public StringMapImpl {
229   AllocatorTy Allocator;
230 public:
231   typedef StringMapEntry<ValueTy> MapEntryTy;
232 
StringMap()233   StringMap() : StringMapImpl(static_cast<unsigned>(sizeof(MapEntryTy))) {}
StringMap(unsigned InitialSize)234   explicit StringMap(unsigned InitialSize)
235     : StringMapImpl(InitialSize, static_cast<unsigned>(sizeof(MapEntryTy))) {}
236 
StringMap(AllocatorTy A)237   explicit StringMap(AllocatorTy A)
238     : StringMapImpl(static_cast<unsigned>(sizeof(MapEntryTy))), Allocator(A) {}
239 
StringMap(unsigned InitialSize,AllocatorTy A)240   StringMap(unsigned InitialSize, AllocatorTy A)
241     : StringMapImpl(InitialSize, static_cast<unsigned>(sizeof(MapEntryTy))),
242       Allocator(A) {}
243 
StringMap(const StringMap & RHS)244   StringMap(const StringMap &RHS)
245     : StringMapImpl(static_cast<unsigned>(sizeof(MapEntryTy))) {
246     assert(RHS.empty() &&
247            "Copy ctor from non-empty stringmap not implemented yet!");
248     (void)RHS;
249   }
250   void operator=(const StringMap &RHS) {
251     assert(RHS.empty() &&
252            "assignment from non-empty stringmap not implemented yet!");
253     (void)RHS;
254     clear();
255   }
256 
257   typedef typename ReferenceAdder<AllocatorTy>::result AllocatorRefTy;
258   typedef typename ReferenceAdder<const AllocatorTy>::result AllocatorCRefTy;
getAllocator()259   AllocatorRefTy getAllocator() { return Allocator; }
getAllocator()260   AllocatorCRefTy getAllocator() const { return Allocator; }
261 
262   typedef const char* key_type;
263   typedef ValueTy mapped_type;
264   typedef StringMapEntry<ValueTy> value_type;
265   typedef size_t size_type;
266 
267   typedef StringMapConstIterator<ValueTy> const_iterator;
268   typedef StringMapIterator<ValueTy> iterator;
269 
begin()270   iterator begin() {
271     return iterator(TheTable, NumBuckets == 0);
272   }
end()273   iterator end() {
274     return iterator(TheTable+NumBuckets, true);
275   }
begin()276   const_iterator begin() const {
277     return const_iterator(TheTable, NumBuckets == 0);
278   }
end()279   const_iterator end() const {
280     return const_iterator(TheTable+NumBuckets, true);
281   }
282 
find(StringRef Key)283   iterator find(StringRef Key) {
284     int Bucket = FindKey(Key);
285     if (Bucket == -1) return end();
286     return iterator(TheTable+Bucket, true);
287   }
288 
find(StringRef Key)289   const_iterator find(StringRef Key) const {
290     int Bucket = FindKey(Key);
291     if (Bucket == -1) return end();
292     return const_iterator(TheTable+Bucket, true);
293   }
294 
295   /// lookup - Return the entry for the specified key, or a default
296   /// constructed value if no such entry exists.
lookup(StringRef Key)297   ValueTy lookup(StringRef Key) const {
298     const_iterator it = find(Key);
299     if (it != end())
300       return it->second;
301     return ValueTy();
302   }
303 
304   ValueTy &operator[](StringRef Key) {
305     return GetOrCreateValue(Key).getValue();
306   }
307 
count(StringRef Key)308   size_type count(StringRef Key) const {
309     return find(Key) == end() ? 0 : 1;
310   }
311 
312   /// insert - Insert the specified key/value pair into the map.  If the key
313   /// already exists in the map, return false and ignore the request, otherwise
314   /// insert it and return true.
insert(MapEntryTy * KeyValue)315   bool insert(MapEntryTy *KeyValue) {
316     unsigned BucketNo = LookupBucketFor(KeyValue->getKey());
317     StringMapEntryBase *&Bucket = TheTable[BucketNo];
318     if (Bucket && Bucket != getTombstoneVal())
319       return false;  // Already exists in map.
320 
321     if (Bucket == getTombstoneVal())
322       --NumTombstones;
323     Bucket = KeyValue;
324     ++NumItems;
325     assert(NumItems + NumTombstones <= NumBuckets);
326 
327     RehashTable();
328     return true;
329   }
330 
331   // clear - Empties out the StringMap
clear()332   void clear() {
333     if (empty()) return;
334 
335     // Zap all values, resetting the keys back to non-present (not tombstone),
336     // which is safe because we're removing all elements.
337     for (unsigned I = 0, E = NumBuckets; I != E; ++I) {
338       StringMapEntryBase *&Bucket = TheTable[I];
339       if (Bucket && Bucket != getTombstoneVal()) {
340         static_cast<MapEntryTy*>(Bucket)->Destroy(Allocator);
341       }
342       Bucket = 0;
343     }
344 
345     NumItems = 0;
346     NumTombstones = 0;
347   }
348 
349   /// GetOrCreateValue - Look up the specified key in the table.  If a value
350   /// exists, return it.  Otherwise, default construct a value, insert it, and
351   /// return.
352   template <typename InitTy>
GetOrCreateValue(StringRef Key,InitTy Val)353   MapEntryTy &GetOrCreateValue(StringRef Key, InitTy Val) {
354     unsigned BucketNo = LookupBucketFor(Key);
355     StringMapEntryBase *&Bucket = TheTable[BucketNo];
356     if (Bucket && Bucket != getTombstoneVal())
357       return *static_cast<MapEntryTy*>(Bucket);
358 
359     MapEntryTy *NewItem =
360       MapEntryTy::Create(Key.begin(), Key.end(), Allocator, Val);
361 
362     if (Bucket == getTombstoneVal())
363       --NumTombstones;
364     ++NumItems;
365     assert(NumItems + NumTombstones <= NumBuckets);
366 
367     // Fill in the bucket for the hash table.  The FullHashValue was already
368     // filled in by LookupBucketFor.
369     Bucket = NewItem;
370 
371     RehashTable();
372     return *NewItem;
373   }
374 
GetOrCreateValue(StringRef Key)375   MapEntryTy &GetOrCreateValue(StringRef Key) {
376     return GetOrCreateValue(Key, ValueTy());
377   }
378 
379   /// remove - Remove the specified key/value pair from the map, but do not
380   /// erase it.  This aborts if the key is not in the map.
remove(MapEntryTy * KeyValue)381   void remove(MapEntryTy *KeyValue) {
382     RemoveKey(KeyValue);
383   }
384 
erase(iterator I)385   void erase(iterator I) {
386     MapEntryTy &V = *I;
387     remove(&V);
388     V.Destroy(Allocator);
389   }
390 
erase(StringRef Key)391   bool erase(StringRef Key) {
392     iterator I = find(Key);
393     if (I == end()) return false;
394     erase(I);
395     return true;
396   }
397 
~StringMap()398   ~StringMap() {
399     clear();
400     free(TheTable);
401   }
402 };
403 
404 
405 template<typename ValueTy>
406 class StringMapConstIterator {
407 protected:
408   StringMapEntryBase **Ptr;
409 public:
410   typedef StringMapEntry<ValueTy> value_type;
411 
412   explicit StringMapConstIterator(StringMapEntryBase **Bucket,
413                                   bool NoAdvance = false)
Ptr(Bucket)414   : Ptr(Bucket) {
415     if (!NoAdvance) AdvancePastEmptyBuckets();
416   }
417 
418   const value_type &operator*() const {
419     return *static_cast<StringMapEntry<ValueTy>*>(*Ptr);
420   }
421   const value_type *operator->() const {
422     return static_cast<StringMapEntry<ValueTy>*>(*Ptr);
423   }
424 
425   bool operator==(const StringMapConstIterator &RHS) const {
426     return Ptr == RHS.Ptr;
427   }
428   bool operator!=(const StringMapConstIterator &RHS) const {
429     return Ptr != RHS.Ptr;
430   }
431 
432   inline StringMapConstIterator& operator++() {   // Preincrement
433     ++Ptr;
434     AdvancePastEmptyBuckets();
435     return *this;
436   }
437   StringMapConstIterator operator++(int) {        // Postincrement
438     StringMapConstIterator tmp = *this; ++*this; return tmp;
439   }
440 
441 private:
AdvancePastEmptyBuckets()442   void AdvancePastEmptyBuckets() {
443     while (*Ptr == 0 || *Ptr == StringMapImpl::getTombstoneVal())
444       ++Ptr;
445   }
446 };
447 
448 template<typename ValueTy>
449 class StringMapIterator : public StringMapConstIterator<ValueTy> {
450 public:
451   explicit StringMapIterator(StringMapEntryBase **Bucket,
452                              bool NoAdvance = false)
453     : StringMapConstIterator<ValueTy>(Bucket, NoAdvance) {
454   }
455   StringMapEntry<ValueTy> &operator*() const {
456     return *static_cast<StringMapEntry<ValueTy>*>(*this->Ptr);
457   }
458   StringMapEntry<ValueTy> *operator->() const {
459     return static_cast<StringMapEntry<ValueTy>*>(*this->Ptr);
460   }
461 };
462 
463 }
464 
465 #endif
466