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