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
21namespace 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.
32template<typename ValueTy>
33class StringMapEntryInitializer {
34public:
35  template <typename InitTy>
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.
43class StringMapEntryBase {
44  unsigned StrLen;
45public:
46  explicit StringMapEntryBase(unsigned Len) : StrLen(Len) {}
47
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.
53class StringMapImpl {
54protected:
55  // Array of NumBuckets pointers to entries, null pointers are holes.
56  // TheTable[NumBuckets] contains a sentinel value for easy iteration. Follwed
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;
63protected:
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);
93private:
94  void init(unsigned Size);
95public:
96  static StringMapEntryBase *getTombstoneVal() {
97    return (StringMapEntryBase*)-1;
98  }
99
100  unsigned getNumBuckets() const { return NumBuckets; }
101  unsigned getNumItems() const { return NumItems; }
102
103  bool empty() const { return NumItems == 0; }
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.
110template<typename ValueTy>
111class StringMapEntry : public StringMapEntryBase {
112public:
113  ValueTy second;
114
115  explicit StringMapEntry(unsigned strLen)
116    : StringMapEntryBase(strLen), second() {}
117  StringMapEntry(unsigned strLen, const ValueTy &V)
118    : StringMapEntryBase(strLen), second(V) {}
119
120  StringRef getKey() const {
121    return StringRef(getKeyData(), getKeyLength());
122  }
123
124  const ValueTy &getValue() const { return second; }
125  ValueTy &getValue() { return second; }
126
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.
132  const char *getKeyData() const {return reinterpret_cast<const char*>(this+1);}
133
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>
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>
169  static StringMapEntry *Create(const char *KeyStart, const char *KeyEnd,
170                                AllocatorTy &Allocator) {
171    return Create(KeyStart, KeyEnd, Allocator, 0);
172  }
173
174
175  /// Create - Create a StringMapEntry with normal malloc/free.
176  template<typename InitType>
177  static StringMapEntry *Create(const char *KeyStart, const char *KeyEnd,
178                                InitType InitVal) {
179    MallocAllocator A;
180    return Create(KeyStart, KeyEnd, A, InitVal);
181  }
182
183  static StringMapEntry *Create(const char *KeyStart, const char *KeyEnd) {
184    return Create(KeyStart, KeyEnd, ValueTy());
185  }
186
187  /// GetStringMapEntryFromValue - Given a value that is known to be embedded
188  /// into a StringMapEntry, return the StringMapEntry itself.
189  static StringMapEntry &GetStringMapEntryFromValue(ValueTy &V) {
190    StringMapEntry *EPtr = 0;
191    char *Ptr = reinterpret_cast<char*>(&V) -
192                  (reinterpret_cast<char*>(&EPtr->second) -
193                   reinterpret_cast<char*>(EPtr));
194    return *reinterpret_cast<StringMapEntry*>(Ptr);
195  }
196  static const StringMapEntry &GetStringMapEntryFromValue(const ValueTy &V) {
197    return GetStringMapEntryFromValue(const_cast<ValueTy&>(V));
198  }
199
200  /// GetStringMapEntryFromKeyData - Given key data that is known to be embedded
201  /// into a StringMapEntry, return the StringMapEntry itself.
202  static StringMapEntry &GetStringMapEntryFromKeyData(const char *KeyData) {
203    char *Ptr = const_cast<char*>(KeyData) - sizeof(StringMapEntry<ValueTy>);
204    return *reinterpret_cast<StringMapEntry*>(Ptr);
205  }
206
207
208  /// Destroy - Destroy this StringMapEntry, releasing memory back to the
209  /// specified allocator.
210  template<typename AllocatorTy>
211  void Destroy(AllocatorTy &Allocator) {
212    // Free memory referenced by the item.
213    this->~StringMapEntry();
214    Allocator.Deallocate(this);
215  }
216
217  /// Destroy this object, releasing memory back to the malloc allocator.
218  void Destroy() {
219    MallocAllocator A;
220    Destroy(A);
221  }
222};
223
224
225/// StringMap - This is an unconventional map that is specialized for handling
226/// keys that are "strings", which are basically ranges of bytes. This does some
227/// funky memory allocation and hashing things to make it extremely efficient,
228/// storing the string data *after* the value in the map.
229template<typename ValueTy, typename AllocatorTy = MallocAllocator>
230class StringMap : public StringMapImpl {
231  AllocatorTy Allocator;
232public:
233  typedef StringMapEntry<ValueTy> MapEntryTy;
234
235  StringMap() : StringMapImpl(static_cast<unsigned>(sizeof(MapEntryTy))) {}
236  explicit StringMap(unsigned InitialSize)
237    : StringMapImpl(InitialSize, static_cast<unsigned>(sizeof(MapEntryTy))) {}
238
239  explicit StringMap(AllocatorTy A)
240    : StringMapImpl(static_cast<unsigned>(sizeof(MapEntryTy))), Allocator(A) {}
241
242  StringMap(const StringMap &RHS)
243    : StringMapImpl(static_cast<unsigned>(sizeof(MapEntryTy))) {
244    assert(RHS.empty() &&
245           "Copy ctor from non-empty stringmap not implemented yet!");
246    (void)RHS;
247  }
248  void operator=(const StringMap &RHS) {
249    assert(RHS.empty() &&
250           "assignment from non-empty stringmap not implemented yet!");
251    (void)RHS;
252    clear();
253  }
254
255  typedef typename ReferenceAdder<AllocatorTy>::result AllocatorRefTy;
256  typedef typename ReferenceAdder<const AllocatorTy>::result AllocatorCRefTy;
257  AllocatorRefTy getAllocator() { return Allocator; }
258  AllocatorCRefTy getAllocator() const { return Allocator; }
259
260  typedef const char* key_type;
261  typedef ValueTy mapped_type;
262  typedef StringMapEntry<ValueTy> value_type;
263  typedef size_t size_type;
264
265  typedef StringMapConstIterator<ValueTy> const_iterator;
266  typedef StringMapIterator<ValueTy> iterator;
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
293   /// lookup - Return the entry for the specified key, or a default
294  /// constructed value if no such entry exists.
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
302  ValueTy &operator[](StringRef Key) {
303    return GetOrCreateValue(Key).getValue();
304  }
305
306  size_type count(StringRef Key) const {
307    return find(Key) == end() ? 0 : 1;
308  }
309
310  /// insert - Insert the specified key/value pair into the map.  If the key
311  /// already exists in the map, return false and ignore the request, otherwise
312  /// insert it and return true.
313  bool insert(MapEntryTy *KeyValue) {
314    unsigned BucketNo = LookupBucketFor(KeyValue->getKey());
315    StringMapEntryBase *&Bucket = TheTable[BucketNo];
316    if (Bucket && Bucket != getTombstoneVal())
317      return false;  // Already exists in map.
318
319    if (Bucket == getTombstoneVal())
320      --NumTombstones;
321    Bucket = KeyValue;
322    ++NumItems;
323    assert(NumItems + NumTombstones <= NumBuckets);
324
325    RehashTable();
326    return true;
327  }
328
329  // clear - Empties out the StringMap
330  void clear() {
331    if (empty()) return;
332
333    // Zap all values, resetting the keys back to non-present (not tombstone),
334    // which is safe because we're removing all elements.
335    for (unsigned I = 0, E = NumBuckets; I != E; ++I) {
336      StringMapEntryBase *&Bucket = TheTable[I];
337      if (Bucket && Bucket != getTombstoneVal()) {
338        static_cast<MapEntryTy*>(Bucket)->Destroy(Allocator);
339        Bucket = 0;
340      }
341    }
342
343    NumItems = 0;
344    NumTombstones = 0;
345  }
346
347  /// GetOrCreateValue - Look up the specified key in the table.  If a value
348  /// exists, return it.  Otherwise, default construct a value, insert it, and
349  /// return.
350  template <typename InitTy>
351  MapEntryTy &GetOrCreateValue(StringRef Key, InitTy Val) {
352    unsigned BucketNo = LookupBucketFor(Key);
353    StringMapEntryBase *&Bucket = TheTable[BucketNo];
354    if (Bucket && Bucket != getTombstoneVal())
355      return *static_cast<MapEntryTy*>(Bucket);
356
357    MapEntryTy *NewItem =
358      MapEntryTy::Create(Key.begin(), Key.end(), Allocator, Val);
359
360    if (Bucket == getTombstoneVal())
361      --NumTombstones;
362    ++NumItems;
363    assert(NumItems + NumTombstones <= NumBuckets);
364
365    // Fill in the bucket for the hash table.  The FullHashValue was already
366    // filled in by LookupBucketFor.
367    Bucket = NewItem;
368
369    RehashTable();
370    return *NewItem;
371  }
372
373  MapEntryTy &GetOrCreateValue(StringRef Key) {
374    return GetOrCreateValue(Key, ValueTy());
375  }
376
377  /// remove - Remove the specified key/value pair from the map, but do not
378  /// erase it.  This aborts if the key is not in the map.
379  void remove(MapEntryTy *KeyValue) {
380    RemoveKey(KeyValue);
381  }
382
383  void erase(iterator I) {
384    MapEntryTy &V = *I;
385    remove(&V);
386    V.Destroy(Allocator);
387  }
388
389  bool erase(StringRef Key) {
390    iterator I = find(Key);
391    if (I == end()) return false;
392    erase(I);
393    return true;
394  }
395
396  ~StringMap() {
397    clear();
398    free(TheTable);
399  }
400};
401
402
403template<typename ValueTy>
404class StringMapConstIterator {
405protected:
406  StringMapEntryBase **Ptr;
407public:
408  typedef StringMapEntry<ValueTy> value_type;
409
410  explicit StringMapConstIterator(StringMapEntryBase **Bucket,
411                                  bool NoAdvance = false)
412  : Ptr(Bucket) {
413    if (!NoAdvance) AdvancePastEmptyBuckets();
414  }
415
416  const value_type &operator*() const {
417    return *static_cast<StringMapEntry<ValueTy>*>(*Ptr);
418  }
419  const value_type *operator->() const {
420    return static_cast<StringMapEntry<ValueTy>*>(*Ptr);
421  }
422
423  bool operator==(const StringMapConstIterator &RHS) const {
424    return Ptr == RHS.Ptr;
425  }
426  bool operator!=(const StringMapConstIterator &RHS) const {
427    return Ptr != RHS.Ptr;
428  }
429
430  inline StringMapConstIterator& operator++() {          // Preincrement
431    ++Ptr;
432    AdvancePastEmptyBuckets();
433    return *this;
434  }
435  StringMapConstIterator operator++(int) {        // Postincrement
436    StringMapConstIterator tmp = *this; ++*this; return tmp;
437  }
438
439private:
440  void AdvancePastEmptyBuckets() {
441    while (*Ptr == 0 || *Ptr == StringMapImpl::getTombstoneVal())
442      ++Ptr;
443  }
444};
445
446template<typename ValueTy>
447class StringMapIterator : public StringMapConstIterator<ValueTy> {
448public:
449  explicit StringMapIterator(StringMapEntryBase **Bucket,
450                             bool NoAdvance = false)
451    : StringMapConstIterator<ValueTy>(Bucket, NoAdvance) {
452  }
453  StringMapEntry<ValueTy> &operator*() const {
454    return *static_cast<StringMapEntry<ValueTy>*>(*this->Ptr);
455  }
456  StringMapEntry<ValueTy> *operator->() const {
457    return static_cast<StringMapEntry<ValueTy>*>(*this->Ptr);
458  }
459};
460
461}
462
463#endif
464