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