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. 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;
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  void swap(StringMapImpl &Other) {
107    std::swap(TheTable, Other.TheTable);
108    std::swap(NumBuckets, Other.NumBuckets);
109    std::swap(NumItems, Other.NumItems);
110    std::swap(NumTombstones, Other.NumTombstones);
111  }
112};
113
114/// StringMapEntry - This is used to represent one value that is inserted into
115/// a StringMap.  It contains the Value itself and the key: the string length
116/// and data.
117template<typename ValueTy>
118class StringMapEntry : public StringMapEntryBase {
119  StringMapEntry(StringMapEntry &E) LLVM_DELETED_FUNCTION;
120public:
121  ValueTy second;
122
123  explicit StringMapEntry(unsigned strLen)
124    : StringMapEntryBase(strLen), second() {}
125  StringMapEntry(unsigned strLen, const ValueTy &V)
126    : StringMapEntryBase(strLen), second(V) {}
127
128  StringRef getKey() const {
129    return StringRef(getKeyData(), getKeyLength());
130  }
131
132  const ValueTy &getValue() const { return second; }
133  ValueTy &getValue() { return second; }
134
135  void setValue(const ValueTy &V) { second = V; }
136
137  /// getKeyData - Return the start of the string data that is the key for this
138  /// value.  The string data is always stored immediately after the
139  /// StringMapEntry object.
140  const char *getKeyData() const {return reinterpret_cast<const char*>(this+1);}
141
142  StringRef first() const { return StringRef(getKeyData(), getKeyLength()); }
143
144  /// Create - Create a StringMapEntry for the specified key and default
145  /// construct the value.
146  template<typename AllocatorTy, typename InitType>
147  static StringMapEntry *Create(const char *KeyStart, const char *KeyEnd,
148                                AllocatorTy &Allocator,
149                                InitType InitVal) {
150    unsigned KeyLength = static_cast<unsigned>(KeyEnd-KeyStart);
151
152    // Okay, the item doesn't already exist, and 'Bucket' is the bucket to fill
153    // in.  Allocate a new item with space for the string at the end and a null
154    // terminator.
155
156    unsigned AllocSize = static_cast<unsigned>(sizeof(StringMapEntry))+
157      KeyLength+1;
158    unsigned Alignment = alignOf<StringMapEntry>();
159
160    StringMapEntry *NewItem =
161      static_cast<StringMapEntry*>(Allocator.Allocate(AllocSize,Alignment));
162
163    // Default construct the value.
164    new (NewItem) StringMapEntry(KeyLength);
165
166    // Copy the string information.
167    char *StrBuffer = const_cast<char*>(NewItem->getKeyData());
168    memcpy(StrBuffer, KeyStart, KeyLength);
169    StrBuffer[KeyLength] = 0;  // Null terminate for convenience of clients.
170
171    // Initialize the value if the client wants to.
172    StringMapEntryInitializer<ValueTy>::Initialize(*NewItem, InitVal);
173    return NewItem;
174  }
175
176  template<typename AllocatorTy>
177  static StringMapEntry *Create(const char *KeyStart, const char *KeyEnd,
178                                AllocatorTy &Allocator) {
179    return Create(KeyStart, KeyEnd, Allocator, 0);
180  }
181
182  /// Create - Create a StringMapEntry with normal malloc/free.
183  template<typename InitType>
184  static StringMapEntry *Create(const char *KeyStart, const char *KeyEnd,
185                                InitType InitVal) {
186    MallocAllocator A;
187    return Create(KeyStart, KeyEnd, A, InitVal);
188  }
189
190  static StringMapEntry *Create(const char *KeyStart, const char *KeyEnd) {
191    return Create(KeyStart, KeyEnd, ValueTy());
192  }
193
194  /// GetStringMapEntryFromValue - Given a value that is known to be embedded
195  /// into a StringMapEntry, return the StringMapEntry itself.
196  static StringMapEntry &GetStringMapEntryFromValue(ValueTy &V) {
197    StringMapEntry *EPtr = 0;
198    char *Ptr = reinterpret_cast<char*>(&V) -
199                  (reinterpret_cast<char*>(&EPtr->second) -
200                   reinterpret_cast<char*>(EPtr));
201    return *reinterpret_cast<StringMapEntry*>(Ptr);
202  }
203  static const StringMapEntry &GetStringMapEntryFromValue(const ValueTy &V) {
204    return GetStringMapEntryFromValue(const_cast<ValueTy&>(V));
205  }
206
207  /// GetStringMapEntryFromKeyData - Given key data that is known to be embedded
208  /// into a StringMapEntry, return the StringMapEntry itself.
209  static StringMapEntry &GetStringMapEntryFromKeyData(const char *KeyData) {
210    char *Ptr = const_cast<char*>(KeyData) - sizeof(StringMapEntry<ValueTy>);
211    return *reinterpret_cast<StringMapEntry*>(Ptr);
212  }
213
214  /// Destroy - Destroy this StringMapEntry, releasing memory back to the
215  /// specified allocator.
216  template<typename AllocatorTy>
217  void Destroy(AllocatorTy &Allocator) {
218    // Free memory referenced by the item.
219    this->~StringMapEntry();
220    Allocator.Deallocate(this);
221  }
222
223  /// Destroy this object, releasing memory back to the malloc allocator.
224  void Destroy() {
225    MallocAllocator A;
226    Destroy(A);
227  }
228};
229
230
231/// StringMap - This is an unconventional map that is specialized for handling
232/// keys that are "strings", which are basically ranges of bytes. This does some
233/// funky memory allocation and hashing things to make it extremely efficient,
234/// storing the string data *after* the value in the map.
235template<typename ValueTy, typename AllocatorTy = MallocAllocator>
236class StringMap : public StringMapImpl {
237  AllocatorTy Allocator;
238public:
239  typedef StringMapEntry<ValueTy> MapEntryTy;
240
241  StringMap() : StringMapImpl(static_cast<unsigned>(sizeof(MapEntryTy))) {}
242  explicit StringMap(unsigned InitialSize)
243    : StringMapImpl(InitialSize, static_cast<unsigned>(sizeof(MapEntryTy))) {}
244
245  explicit StringMap(AllocatorTy A)
246    : StringMapImpl(static_cast<unsigned>(sizeof(MapEntryTy))), Allocator(A) {}
247
248  StringMap(unsigned InitialSize, AllocatorTy A)
249    : StringMapImpl(InitialSize, static_cast<unsigned>(sizeof(MapEntryTy))),
250      Allocator(A) {}
251
252  StringMap(const StringMap &RHS)
253    : StringMapImpl(static_cast<unsigned>(sizeof(MapEntryTy))) {
254    assert(RHS.empty() &&
255           "Copy ctor from non-empty stringmap not implemented yet!");
256    (void)RHS;
257  }
258  void operator=(const StringMap &RHS) {
259    assert(RHS.empty() &&
260           "assignment from non-empty stringmap not implemented yet!");
261    (void)RHS;
262    clear();
263  }
264
265  typedef typename ReferenceAdder<AllocatorTy>::result AllocatorRefTy;
266  typedef typename ReferenceAdder<const AllocatorTy>::result AllocatorCRefTy;
267  AllocatorRefTy getAllocator() { return Allocator; }
268  AllocatorCRefTy getAllocator() const { return Allocator; }
269
270  typedef const char* key_type;
271  typedef ValueTy mapped_type;
272  typedef StringMapEntry<ValueTy> value_type;
273  typedef size_t size_type;
274
275  typedef StringMapConstIterator<ValueTy> const_iterator;
276  typedef StringMapIterator<ValueTy> iterator;
277
278  iterator begin() {
279    return iterator(TheTable, NumBuckets == 0);
280  }
281  iterator end() {
282    return iterator(TheTable+NumBuckets, true);
283  }
284  const_iterator begin() const {
285    return const_iterator(TheTable, NumBuckets == 0);
286  }
287  const_iterator end() const {
288    return const_iterator(TheTable+NumBuckets, true);
289  }
290
291  iterator find(StringRef Key) {
292    int Bucket = FindKey(Key);
293    if (Bucket == -1) return end();
294    return iterator(TheTable+Bucket, true);
295  }
296
297  const_iterator find(StringRef Key) const {
298    int Bucket = FindKey(Key);
299    if (Bucket == -1) return end();
300    return const_iterator(TheTable+Bucket, true);
301  }
302
303  /// lookup - Return the entry for the specified key, or a default
304  /// constructed value if no such entry exists.
305  ValueTy lookup(StringRef Key) const {
306    const_iterator it = find(Key);
307    if (it != end())
308      return it->second;
309    return ValueTy();
310  }
311
312  ValueTy &operator[](StringRef Key) {
313    return GetOrCreateValue(Key).getValue();
314  }
315
316  size_type count(StringRef Key) const {
317    return find(Key) == end() ? 0 : 1;
318  }
319
320  /// insert - Insert the specified key/value pair into the map.  If the key
321  /// already exists in the map, return false and ignore the request, otherwise
322  /// insert it and return true.
323  bool insert(MapEntryTy *KeyValue) {
324    unsigned BucketNo = LookupBucketFor(KeyValue->getKey());
325    StringMapEntryBase *&Bucket = TheTable[BucketNo];
326    if (Bucket && Bucket != getTombstoneVal())
327      return false;  // Already exists in map.
328
329    if (Bucket == getTombstoneVal())
330      --NumTombstones;
331    Bucket = KeyValue;
332    ++NumItems;
333    assert(NumItems + NumTombstones <= NumBuckets);
334
335    RehashTable();
336    return true;
337  }
338
339  // clear - Empties out the StringMap
340  void clear() {
341    if (empty()) return;
342
343    // Zap all values, resetting the keys back to non-present (not tombstone),
344    // which is safe because we're removing all elements.
345    for (unsigned I = 0, E = NumBuckets; I != E; ++I) {
346      StringMapEntryBase *&Bucket = TheTable[I];
347      if (Bucket && Bucket != getTombstoneVal()) {
348        static_cast<MapEntryTy*>(Bucket)->Destroy(Allocator);
349      }
350      Bucket = 0;
351    }
352
353    NumItems = 0;
354    NumTombstones = 0;
355  }
356
357  /// GetOrCreateValue - Look up the specified key in the table.  If a value
358  /// exists, return it.  Otherwise, default construct a value, insert it, and
359  /// return.
360  template <typename InitTy>
361  MapEntryTy &GetOrCreateValue(StringRef Key, InitTy Val) {
362    unsigned BucketNo = LookupBucketFor(Key);
363    StringMapEntryBase *&Bucket = TheTable[BucketNo];
364    if (Bucket && Bucket != getTombstoneVal())
365      return *static_cast<MapEntryTy*>(Bucket);
366
367    MapEntryTy *NewItem =
368      MapEntryTy::Create(Key.begin(), Key.end(), Allocator, Val);
369
370    if (Bucket == getTombstoneVal())
371      --NumTombstones;
372    ++NumItems;
373    assert(NumItems + NumTombstones <= NumBuckets);
374
375    // Fill in the bucket for the hash table.  The FullHashValue was already
376    // filled in by LookupBucketFor.
377    Bucket = NewItem;
378
379    RehashTable();
380    return *NewItem;
381  }
382
383  MapEntryTy &GetOrCreateValue(StringRef Key) {
384    return GetOrCreateValue(Key, ValueTy());
385  }
386
387  /// remove - Remove the specified key/value pair from the map, but do not
388  /// erase it.  This aborts if the key is not in the map.
389  void remove(MapEntryTy *KeyValue) {
390    RemoveKey(KeyValue);
391  }
392
393  void erase(iterator I) {
394    MapEntryTy &V = *I;
395    remove(&V);
396    V.Destroy(Allocator);
397  }
398
399  bool erase(StringRef Key) {
400    iterator I = find(Key);
401    if (I == end()) return false;
402    erase(I);
403    return true;
404  }
405
406  ~StringMap() {
407    clear();
408    free(TheTable);
409  }
410};
411
412
413template<typename ValueTy>
414class StringMapConstIterator {
415protected:
416  StringMapEntryBase **Ptr;
417public:
418  typedef StringMapEntry<ValueTy> value_type;
419
420  StringMapConstIterator() : Ptr(0) { }
421
422  explicit StringMapConstIterator(StringMapEntryBase **Bucket,
423                                  bool NoAdvance = false)
424  : Ptr(Bucket) {
425    if (!NoAdvance) AdvancePastEmptyBuckets();
426  }
427
428  const value_type &operator*() const {
429    return *static_cast<StringMapEntry<ValueTy>*>(*Ptr);
430  }
431  const value_type *operator->() const {
432    return static_cast<StringMapEntry<ValueTy>*>(*Ptr);
433  }
434
435  bool operator==(const StringMapConstIterator &RHS) const {
436    return Ptr == RHS.Ptr;
437  }
438  bool operator!=(const StringMapConstIterator &RHS) const {
439    return Ptr != RHS.Ptr;
440  }
441
442  inline StringMapConstIterator& operator++() {   // Preincrement
443    ++Ptr;
444    AdvancePastEmptyBuckets();
445    return *this;
446  }
447  StringMapConstIterator operator++(int) {        // Postincrement
448    StringMapConstIterator tmp = *this; ++*this; return tmp;
449  }
450
451private:
452  void AdvancePastEmptyBuckets() {
453    while (*Ptr == 0 || *Ptr == StringMapImpl::getTombstoneVal())
454      ++Ptr;
455  }
456};
457
458template<typename ValueTy>
459class StringMapIterator : public StringMapConstIterator<ValueTy> {
460public:
461  StringMapIterator() {}
462  explicit StringMapIterator(StringMapEntryBase **Bucket,
463                             bool NoAdvance = false)
464    : StringMapConstIterator<ValueTy>(Bucket, NoAdvance) {
465  }
466  StringMapEntry<ValueTy> &operator*() const {
467    return *static_cast<StringMapEntry<ValueTy>*>(*this->Ptr);
468  }
469  StringMapEntry<ValueTy> *operator->() const {
470    return static_cast<StringMapEntry<ValueTy>*>(*this->Ptr);
471  }
472};
473
474}
475
476#endif
477