include/llvm/ADT/StringMap.h

   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>
  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:
  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.
  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:
  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:
  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.
 117 template<typename ValueTy>
 118 class StringMapEntry : public StringMapEntryBase {
 119   StringMapEntry(StringMapEntry &E) LLVM_DELETED_FUNCTION;
 120 public:
 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.
 235 template<typename ValueTy, typename AllocatorTy = MallocAllocator>
 236 class StringMap : public StringMapImpl {
 237   AllocatorTy Allocator;
 238 public:
 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   /// count - Return 1 if the element is in the map, 0 otherwise.
 317   size_type count(StringRef Key) const {
 318     return find(Key) == end() ? 0 : 1;
 319   }
 320
 321   /// insert - Insert the specified key/value pair into the map.  If the key
 322   /// already exists in the map, return false and ignore the request, otherwise
 323   /// insert it and return true.
 324   bool insert(MapEntryTy *KeyValue) {
 325     unsigned BucketNo = LookupBucketFor(KeyValue->getKey());
 326     StringMapEntryBase *&Bucket = TheTable[BucketNo];
 327     if (Bucket && Bucket != getTombstoneVal())
 328       return false;  // Already exists in map.
 329
 330     if (Bucket == getTombstoneVal())
 331       --NumTombstones;
 332     Bucket = KeyValue;
 333     ++NumItems;
 334     assert(NumItems + NumTombstones <= NumBuckets);
 335
 336     RehashTable();
 337     return true;
 338   }
 339
 340   // clear - Empties out the StringMap
 341   void clear() {
 342     if (empty()) return;
 343
 344     // Zap all values, resetting the keys back to non-present (not tombstone),
 345     // which is safe because we're removing all elements.
 346     for (unsigned I = 0, E = NumBuckets; I != E; ++I) {
 347       StringMapEntryBase *&Bucket = TheTable[I];
 348       if (Bucket && Bucket != getTombstoneVal()) {
 349         static_cast<MapEntryTy*>(Bucket)->Destroy(Allocator);
 350       }
 351       Bucket = 0;
 352     }
 353
 354     NumItems = 0;
 355     NumTombstones = 0;
 356   }
 357
 358   /// GetOrCreateValue - Look up the specified key in the table.  If a value
 359   /// exists, return it.  Otherwise, default construct a value, insert it, and
 360   /// return.
 361   template <typename InitTy>
 362   MapEntryTy &GetOrCreateValue(StringRef Key, InitTy Val) {
 363     unsigned BucketNo = LookupBucketFor(Key);
 364     StringMapEntryBase *&Bucket = TheTable[BucketNo];
 365     if (Bucket && Bucket != getTombstoneVal())
 366       return *static_cast<MapEntryTy*>(Bucket);
 367
 368     MapEntryTy *NewItem =
 369       MapEntryTy::Create(Key.begin(), Key.end(), Allocator, Val);
 370
 371     if (Bucket == getTombstoneVal())
 372       --NumTombstones;
 373     ++NumItems;
 374     assert(NumItems + NumTombstones <= NumBuckets);
 375
 376     // Fill in the bucket for the hash table.  The FullHashValue was already
 377     // filled in by LookupBucketFor.
 378     Bucket = NewItem;
 379
 380     RehashTable();
 381     return *NewItem;
 382   }
 383
 384   MapEntryTy &GetOrCreateValue(StringRef Key) {
 385     return GetOrCreateValue(Key, ValueTy());
 386   }
 387
 388   /// remove - Remove the specified key/value pair from the map, but do not
 389   /// erase it.  This aborts if the key is not in the map.
 390   void remove(MapEntryTy *KeyValue) {
 391     RemoveKey(KeyValue);
 392   }
 393
 394   void erase(iterator I) {
 395     MapEntryTy &V = *I;
 396     remove(&V);
 397     V.Destroy(Allocator);
 398   }
 399
 400   bool erase(StringRef Key) {
 401     iterator I = find(Key);
 402     if (I == end()) return false;
 403     erase(I);
 404     return true;
 405   }
 406
 407   ~StringMap() {
 408     clear();
 409     free(TheTable);
 410   }
 411 };
 412
 413
 414 template<typename ValueTy>
 415 class StringMapConstIterator {
 416 protected:
 417   StringMapEntryBase **Ptr;
 418 public:
 419   typedef StringMapEntry<ValueTy> value_type;
 420
 421   StringMapConstIterator() : Ptr(0) { }
 422
 423   explicit StringMapConstIterator(StringMapEntryBase **Bucket,
 424                                   bool NoAdvance = false)
 425   : Ptr(Bucket) {
 426     if (!NoAdvance) AdvancePastEmptyBuckets();
 427   }
 428
 429   const value_type &operator*() const {
 430     return *static_cast<StringMapEntry<ValueTy>*>(*Ptr);
 431   }
 432   const value_type *operator->() const {
 433     return static_cast<StringMapEntry<ValueTy>*>(*Ptr);
 434   }
 435
 436   bool operator==(const StringMapConstIterator &RHS) const {
 437     return Ptr == RHS.Ptr;
 438   }
 439   bool operator!=(const StringMapConstIterator &RHS) const {
 440     return Ptr != RHS.Ptr;
 441   }
 442
 443   inline StringMapConstIterator& operator++() {   // Preincrement
 444     ++Ptr;
 445     AdvancePastEmptyBuckets();
 446     return *this;
 447   }
 448   StringMapConstIterator operator++(int) {        // Postincrement
 449     StringMapConstIterator tmp = *this; ++*this; return tmp;
 450   }
 451
 452 private:
 453   void AdvancePastEmptyBuckets() {
 454     while (*Ptr == 0 || *Ptr == StringMapImpl::getTombstoneVal())
 455       ++Ptr;
 456   }
 457 };
 458
 459 template<typename ValueTy>
 460 class StringMapIterator : public StringMapConstIterator<ValueTy> {
 461 public:
 462   StringMapIterator() {}
 463   explicit StringMapIterator(StringMapEntryBase **Bucket,
 464                              bool NoAdvance = false)
 465     : StringMapConstIterator<ValueTy>(Bucket, NoAdvance) {
 466   }
 467   StringMapEntry<ValueTy> &operator*() const {
 468     return *static_cast<StringMapEntry<ValueTy>*>(*this->Ptr);
 469   }
 470   StringMapEntry<ValueTy> *operator->() const {
 471     return static_cast<StringMapEntry<ValueTy>*>(*this->Ptr);
 472   }
 473 };
 474
 475 }
 476
 477 #endif