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