include/llvm/ADT/StringMap.h

   1 //===--- StringMap.h - String Hash table map interface ----------*- C++ -*-===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file was developed by Chris Lattner and is distributed under
   6 // the University of Illinois Open Source 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/Support/Allocator.h"
  18 #include <cstring>
  19
  20 namespace llvm {
  21   template<typename ValueT>
  22   class StringMapConstIterator;
  23   template<typename ValueT>
  24   class StringMapIterator;
  25
  26
  27 /// StringMapEntryBase - Shared base class of StringMapEntry instances.
  28 class StringMapEntryBase {
  29   unsigned StrLen;
  30 public:
  31   StringMapEntryBase(unsigned Len) : StrLen(Len) {}
  32
  33   unsigned getKeyLength() const { return StrLen; }
  34 };
  35
  36 /// StringMapImpl - This is the base class of StringMap that is shared among
  37 /// all of its instantiations.
  38 class StringMapImpl {
  39 public:
  40   /// ItemBucket - The hash table consists of an array of these.  If Item is
  41   /// non-null, this is an extant entry, otherwise, it is a hole.
  42   struct ItemBucket {
  43     /// FullHashValue - This remembers the full hash value of the key for
  44     /// easy scanning.
  45     unsigned FullHashValue;
  46
  47     /// Item - This is a pointer to the actual item object.
  48     StringMapEntryBase *Item;
  49   };
  50
  51 protected:
  52   ItemBucket *TheTable;
  53   unsigned NumBuckets;
  54   unsigned NumItems;
  55   unsigned ItemSize;
  56 protected:
  57   StringMapImpl(unsigned InitSize, unsigned ItemSize);
  58   void RehashTable();
  59
  60   /// LookupBucketFor - Look up the bucket that the specified string should end
  61   /// up in.  If it already exists as a key in the map, the Item pointer for the
  62   /// specified bucket will be non-null.  Otherwise, it will be null.  In either
  63   /// case, the FullHashValue field of the bucket will be set to the hash value
  64   /// of the string.
  65   unsigned LookupBucketFor(const char *KeyStart, const char *KeyEnd);
  66
  67 public:
  68   static StringMapEntryBase *getTombstoneVal() {
  69     return (StringMapEntryBase*)-1;
  70   }
  71
  72   unsigned getNumBuckets() const { return NumBuckets; }
  73   unsigned getNumItems() const { return NumItems; }
  74
  75   bool empty() const { return NumItems == 0; }
  76   unsigned size() const { return NumItems; }
  77 };
  78
  79 /// StringMapEntry - This is used to represent one value that is inserted into
  80 /// a StringMap.  It contains the Value itself and the key: the string length
  81 /// and data.
  82 template<typename ValueTy>
  83 class StringMapEntry : public StringMapEntryBase {
  84   ValueTy Val;
  85 public:
  86   StringMapEntry(unsigned StrLen)
  87     : StringMapEntryBase(StrLen), Val() {}
  88   StringMapEntry(unsigned StrLen, const ValueTy &V)
  89     : StringMapEntryBase(StrLen), Val(V) {}
  90
  91   const ValueTy &getValue() const { return Val; }
  92   ValueTy &getValue() { return Val; }
  93
  94   void setValue(const ValueTy &V) { Val = V; }
  95
  96   /// getKeyData - Return the start of the string data that is the key for this
  97   /// value.  The string data is always stored immediately after the
  98   /// StringMapEntry object.
  99   const char *getKeyData() const {return reinterpret_cast<const char*>(this+1);}
 100
 101   /// Create - Create a StringMapEntry for the specified key and default
 102   /// construct the value.
 103   template<typename AllocatorTy>
 104   static StringMapEntry *Create(const char *KeyStart, const char *KeyEnd,
 105                                 AllocatorTy &Allocator) {
 106     unsigned KeyLength = KeyEnd-KeyStart;
 107
 108     // Okay, the item doesn't already exist, and 'Bucket' is the bucket to fill
 109     // in.  Allocate a new item with space for the string at the end and a null
 110     // terminator.
 111     unsigned AllocSize = sizeof(StringMapEntry)+KeyLength+1;
 112
 113 #ifdef __GNUC__
 114     unsigned Alignment = __alignof__(StringMapEntry);
 115 #else
 116     // FIXME: ugly.
 117     unsigned Alignment = 8;
 118 #endif
 119     StringMapEntry *NewItem =
 120       static_cast<StringMapEntry*>(Allocator.Allocate(AllocSize, Alignment));
 121
 122     // Default construct the value.
 123     new (NewItem) StringMapEntry(KeyLength);
 124
 125     // Copy the string information.
 126     char *StrBuffer = const_cast<char*>(NewItem->getKeyData());
 127     memcpy(StrBuffer, KeyStart, KeyLength);
 128     StrBuffer[KeyLength] = 0;  // Null terminate for convenience of clients.
 129     return NewItem;
 130   }
 131
 132   /// Create - Create a StringMapEntry with normal malloc/free.
 133   static StringMapEntry *Create(const char *KeyStart, const char *KeyEnd) {
 134     MallocAllocator A;
 135     return Create(KeyStart, KeyEnd, A);
 136   }
 137
 138   /// Destroy - Destroy this StringMapEntry, releasing memory back to the
 139   /// specified allocator.
 140   template<typename AllocatorTy>
 141   void Destroy(AllocatorTy &Allocator) {
 142     // Free memory referenced by the item.
 143     this->~StringMapEntry();
 144     Allocator.Deallocate(this);
 145   }
 146
 147   /// Destroy this object, releasing memory back to the malloc allocator.
 148   void Destroy() {
 149     MallocAllocator A;
 150     Destroy(A);
 151   }
 152 };
 153
 154
 155 /// StringMap - This is an unconventional map that is specialized for handling
 156 /// keys that are "strings", which are basically ranges of bytes. This does some
 157 /// funky memory allocation and hashing things to make it extremely efficient,
 158 /// storing the string data *after* the value in the map.
 159 template<typename ValueTy, typename AllocatorTy = MallocAllocator>
 160 class StringMap : public StringMapImpl {
 161   AllocatorTy Allocator;
 162   typedef StringMapEntry<ValueTy> MapEntryTy;
 163 public:
 164   StringMap(unsigned InitialSize = 0)
 165     : StringMapImpl(InitialSize, sizeof(MapEntryTy)) {}
 166
 167   AllocatorTy &getAllocator() { return Allocator; }
 168   const AllocatorTy &getAllocator() const { return Allocator; }
 169
 170   typedef StringMapConstIterator<ValueTy> const_iterator;
 171   typedef StringMapIterator<ValueTy> iterator;
 172
 173   iterator begin() { return iterator(TheTable); }
 174   iterator end() { return iterator(TheTable+NumBuckets); }
 175   const_iterator begin() const { return const_iterator(TheTable); }
 176   const_iterator end() const { return const_iterator(TheTable+NumBuckets); }
 177
 178   /// FindValue - Look up the specified key in the map.  If it exists, return a
 179   /// pointer to the element, otherwise return null.
 180   MapEntryTy *FindValue(const char *KeyStart, const char *KeyEnd) {
 181     unsigned BucketNo = LookupBucketFor(KeyStart, KeyEnd);
 182     return static_cast<MapEntryTy*>(TheTable[BucketNo].Item);
 183   }
 184
 185   /// GetOrCreateValue - Look up the specified key in the table.  If a value
 186   /// exists, return it.  Otherwise, default construct a value, insert it, and
 187   /// return.
 188   StringMapEntry<ValueTy> &GetOrCreateValue(const char *KeyStart,
 189                                             const char *KeyEnd) {
 190     unsigned BucketNo = LookupBucketFor(KeyStart, KeyEnd);
 191     ItemBucket &Bucket = TheTable[BucketNo];
 192     if (Bucket.Item)
 193       return *static_cast<MapEntryTy*>(Bucket.Item);
 194
 195     MapEntryTy *NewItem = MapEntryTy::Create(KeyStart, KeyEnd, Allocator);
 196     ++NumItems;
 197
 198     // Fill in the bucket for the hash table.  The FullHashValue was already
 199     // filled in by LookupBucketFor.
 200     Bucket.Item = NewItem;
 201
 202     // If the hash table is now more than 3/4 full, rehash into a larger table.
 203     if (NumItems > NumBuckets*3/4)
 204       RehashTable();
 205     return *NewItem;
 206   }
 207
 208   ~StringMap() {
 209     for (ItemBucket *I = TheTable, *E = TheTable+NumBuckets; I != E; ++I) {
 210       if (MapEntryTy *Id = static_cast<MapEntryTy*>(I->Item))
 211         Id->Destroy(Allocator);
 212     }
 213     delete [] TheTable;
 214   }
 215 };
 216
 217
 218 template<typename ValueTy>
 219 class StringMapConstIterator {
 220   StringMapImpl::ItemBucket *Ptr;
 221 public:
 222   StringMapConstIterator(StringMapImpl::ItemBucket *Bucket) : Ptr(Bucket) {
 223     AdvancePastEmptyBuckets();
 224   }
 225
 226   const StringMapEntry<ValueTy> &operator*() const {
 227     return *static_cast<StringMapEntry<ValueTy>*>(Ptr->Item);
 228   }
 229   const StringMapEntry<ValueTy> *operator->() const {
 230     return static_cast<StringMapEntry<ValueTy>*>(Ptr->Item);
 231   }
 232
 233   bool operator==(const StringMapConstIterator &RHS) const {
 234     return Ptr == RHS.Ptr;
 235   }
 236   bool operator!=(const StringMapConstIterator &RHS) const {
 237     return Ptr != RHS.Ptr;
 238   }
 239
 240   inline StringMapConstIterator& operator++() {          // Preincrement
 241     ++Ptr;
 242     AdvancePastEmptyBuckets();
 243     return *this;
 244   }
 245   StringMapConstIterator operator++(int) {        // Postincrement
 246     StringMapConstIterator tmp = *this; ++*this; return tmp;
 247   }
 248
 249 private:
 250   void AdvancePastEmptyBuckets() {
 251     while (Ptr->Item == 0 || Ptr->Item == StringMapImpl::getTombstoneVal())
 252       ++Ptr;
 253   }
 254 };
 255
 256 template<typename ValueTy>
 257 class StringMapIterator : public StringMapConstIterator<ValueTy> {
 258 public:
 259   StringMapIterator(StringMapImpl::ItemBucket *Bucket)
 260     : StringMapConstIterator<ValueTy>(Bucket) {
 261   }
 262   StringMapEntry<ValueTy> &operator*() const {
 263     return *static_cast<StringMapEntry<ValueTy>*>(this->Ptr->Item);
 264   }
 265   StringMapEntry<ValueTy> *operator->() const {
 266     return static_cast<StringMapEntry<ValueTy>*>(this->Ptr->Item);
 267   }
 268 };
 269
 270 }
 271
 272 #endif
 273