LLVM  mainline
StringMap.h
Go to the documentation of this file.
00001 //===--- StringMap.h - String Hash table map interface ----------*- C++ -*-===//
00002 //
00003 //                     The LLVM Compiler Infrastructure
00004 //
00005 // This file is distributed under the University of Illinois Open Source
00006 // License. See LICENSE.TXT for details.
00007 //
00008 //===----------------------------------------------------------------------===//
00009 //
00010 // This file defines the StringMap class.
00011 //
00012 //===----------------------------------------------------------------------===//
00013 
00014 #ifndef LLVM_ADT_STRINGMAP_H
00015 #define LLVM_ADT_STRINGMAP_H
00016 
00017 #include "llvm/ADT/StringRef.h"
00018 #include "llvm/Support/Allocator.h"
00019 #include <cstring>
00020 #include <utility>
00021 
00022 namespace llvm {
00023   template<typename ValueT>
00024   class StringMapConstIterator;
00025   template<typename ValueT>
00026   class StringMapIterator;
00027   template<typename ValueTy>
00028   class StringMapEntry;
00029 
00030 /// StringMapEntryBase - Shared base class of StringMapEntry instances.
00031 class StringMapEntryBase {
00032   unsigned StrLen;
00033 
00034 public:
00035   explicit StringMapEntryBase(unsigned Len) : StrLen(Len) {}
00036 
00037   unsigned getKeyLength() const { return StrLen; }
00038 };
00039 
00040 /// StringMapImpl - This is the base class of StringMap that is shared among
00041 /// all of its instantiations.
00042 class StringMapImpl {
00043 protected:
00044   // Array of NumBuckets pointers to entries, null pointers are holes.
00045   // TheTable[NumBuckets] contains a sentinel value for easy iteration. Followed
00046   // by an array of the actual hash values as unsigned integers.
00047   StringMapEntryBase **TheTable;
00048   unsigned NumBuckets;
00049   unsigned NumItems;
00050   unsigned NumTombstones;
00051   unsigned ItemSize;
00052 
00053 protected:
00054   explicit StringMapImpl(unsigned itemSize)
00055       : TheTable(nullptr),
00056         // Initialize the map with zero buckets to allocation.
00057         NumBuckets(0), NumItems(0), NumTombstones(0), ItemSize(itemSize) {}
00058   StringMapImpl(StringMapImpl &&RHS)
00059       : TheTable(RHS.TheTable), NumBuckets(RHS.NumBuckets),
00060         NumItems(RHS.NumItems), NumTombstones(RHS.NumTombstones),
00061         ItemSize(RHS.ItemSize) {
00062     RHS.TheTable = nullptr;
00063     RHS.NumBuckets = 0;
00064     RHS.NumItems = 0;
00065     RHS.NumTombstones = 0;
00066   }
00067 
00068   StringMapImpl(unsigned InitSize, unsigned ItemSize);
00069   unsigned RehashTable(unsigned BucketNo = 0);
00070 
00071   /// LookupBucketFor - Look up the bucket that the specified string should end
00072   /// up in.  If it already exists as a key in the map, the Item pointer for the
00073   /// specified bucket will be non-null.  Otherwise, it will be null.  In either
00074   /// case, the FullHashValue field of the bucket will be set to the hash value
00075   /// of the string.
00076   unsigned LookupBucketFor(StringRef Key);
00077 
00078   /// FindKey - Look up the bucket that contains the specified key. If it exists
00079   /// in the map, return the bucket number of the key.  Otherwise return -1.
00080   /// This does not modify the map.
00081   int FindKey(StringRef Key) const;
00082 
00083   /// RemoveKey - Remove the specified StringMapEntry from the table, but do not
00084   /// delete it.  This aborts if the value isn't in the table.
00085   void RemoveKey(StringMapEntryBase *V);
00086 
00087   /// RemoveKey - Remove the StringMapEntry for the specified key from the
00088   /// table, returning it.  If the key is not in the table, this returns null.
00089   StringMapEntryBase *RemoveKey(StringRef Key);
00090 
00091 private:
00092   void init(unsigned Size);
00093 
00094 public:
00095   static StringMapEntryBase *getTombstoneVal() {
00096     return (StringMapEntryBase*)-1;
00097   }
00098 
00099   unsigned getNumBuckets() const { return NumBuckets; }
00100   unsigned getNumItems() const { return NumItems; }
00101 
00102   bool empty() const { return NumItems == 0; }
00103   unsigned size() const { return NumItems; }
00104 
00105   void swap(StringMapImpl &Other) {
00106     std::swap(TheTable, Other.TheTable);
00107     std::swap(NumBuckets, Other.NumBuckets);
00108     std::swap(NumItems, Other.NumItems);
00109     std::swap(NumTombstones, Other.NumTombstones);
00110   }
00111 };
00112 
00113 /// StringMapEntry - This is used to represent one value that is inserted into
00114 /// a StringMap.  It contains the Value itself and the key: the string length
00115 /// and data.
00116 template<typename ValueTy>
00117 class StringMapEntry : public StringMapEntryBase {
00118   StringMapEntry(StringMapEntry &E) = delete;
00119 
00120 public:
00121   ValueTy second;
00122 
00123   explicit StringMapEntry(unsigned strLen)
00124     : StringMapEntryBase(strLen), second() {}
00125   template <class InitTy>
00126   StringMapEntry(unsigned strLen, InitTy &&V)
00127       : StringMapEntryBase(strLen), second(std::forward<InitTy>(V)) {}
00128 
00129   StringRef getKey() const {
00130     return StringRef(getKeyData(), getKeyLength());
00131   }
00132 
00133   const ValueTy &getValue() const { return second; }
00134   ValueTy &getValue() { return second; }
00135 
00136   void setValue(const ValueTy &V) { second = V; }
00137 
00138   /// getKeyData - Return the start of the string data that is the key for this
00139   /// value.  The string data is always stored immediately after the
00140   /// StringMapEntry object.
00141   const char *getKeyData() const {return reinterpret_cast<const char*>(this+1);}
00142 
00143   StringRef first() const { return StringRef(getKeyData(), getKeyLength()); }
00144 
00145   /// Create - Create a StringMapEntry for the specified key and default
00146   /// construct the value.
00147   template <typename AllocatorTy, typename InitType>
00148   static StringMapEntry *Create(StringRef Key, AllocatorTy &Allocator,
00149                                 InitType &&InitVal) {
00150     unsigned KeyLength = Key.size();
00151 
00152     // Allocate a new item with space for the string at the end and a null
00153     // terminator.
00154     unsigned AllocSize = static_cast<unsigned>(sizeof(StringMapEntry))+
00155       KeyLength+1;
00156     unsigned Alignment = alignOf<StringMapEntry>();
00157 
00158     StringMapEntry *NewItem =
00159       static_cast<StringMapEntry*>(Allocator.Allocate(AllocSize,Alignment));
00160 
00161     // Default construct the value.
00162     new (NewItem) StringMapEntry(KeyLength, std::forward<InitType>(InitVal));
00163 
00164     // Copy the string information.
00165     char *StrBuffer = const_cast<char*>(NewItem->getKeyData());
00166     if (KeyLength > 0)
00167       memcpy(StrBuffer, Key.data(), KeyLength);
00168     StrBuffer[KeyLength] = 0;  // Null terminate for convenience of clients.
00169     return NewItem;
00170   }
00171 
00172   template<typename AllocatorTy>
00173   static StringMapEntry *Create(StringRef Key, AllocatorTy &Allocator) {
00174     return Create(Key, Allocator, ValueTy());
00175   }
00176 
00177   /// Create - Create a StringMapEntry with normal malloc/free.
00178   template<typename InitType>
00179   static StringMapEntry *Create(StringRef Key, InitType &&InitVal) {
00180     MallocAllocator A;
00181     return Create(Key, A, std::forward<InitType>(InitVal));
00182   }
00183 
00184   static StringMapEntry *Create(StringRef Key) {
00185     return Create(Key, ValueTy());
00186   }
00187 
00188   /// GetStringMapEntryFromKeyData - Given key data that is known to be embedded
00189   /// into a StringMapEntry, return the StringMapEntry itself.
00190   static StringMapEntry &GetStringMapEntryFromKeyData(const char *KeyData) {
00191     char *Ptr = const_cast<char*>(KeyData) - sizeof(StringMapEntry<ValueTy>);
00192     return *reinterpret_cast<StringMapEntry*>(Ptr);
00193   }
00194 
00195   /// Destroy - Destroy this StringMapEntry, releasing memory back to the
00196   /// specified allocator.
00197   template<typename AllocatorTy>
00198   void Destroy(AllocatorTy &Allocator) {
00199     // Free memory referenced by the item.
00200     unsigned AllocSize =
00201         static_cast<unsigned>(sizeof(StringMapEntry)) + getKeyLength() + 1;
00202     this->~StringMapEntry();
00203     Allocator.Deallocate(static_cast<void *>(this), AllocSize);
00204   }
00205 
00206   /// Destroy this object, releasing memory back to the malloc allocator.
00207   void Destroy() {
00208     MallocAllocator A;
00209     Destroy(A);
00210   }
00211 };
00212 
00213 /// StringMap - This is an unconventional map that is specialized for handling
00214 /// keys that are "strings", which are basically ranges of bytes. This does some
00215 /// funky memory allocation and hashing things to make it extremely efficient,
00216 /// storing the string data *after* the value in the map.
00217 template<typename ValueTy, typename AllocatorTy = MallocAllocator>
00218 class StringMap : public StringMapImpl {
00219   AllocatorTy Allocator;
00220 
00221 public:
00222   typedef StringMapEntry<ValueTy> MapEntryTy;
00223 
00224   StringMap() : StringMapImpl(static_cast<unsigned>(sizeof(MapEntryTy))) {}
00225   explicit StringMap(unsigned InitialSize)
00226     : StringMapImpl(InitialSize, static_cast<unsigned>(sizeof(MapEntryTy))) {}
00227 
00228   explicit StringMap(AllocatorTy A)
00229     : StringMapImpl(static_cast<unsigned>(sizeof(MapEntryTy))), Allocator(A) {}
00230 
00231   StringMap(unsigned InitialSize, AllocatorTy A)
00232     : StringMapImpl(InitialSize, static_cast<unsigned>(sizeof(MapEntryTy))),
00233       Allocator(A) {}
00234 
00235   StringMap(std::initializer_list<std::pair<StringRef, ValueTy>> List)
00236       : StringMapImpl(static_cast<unsigned>(sizeof(MapEntryTy))) {
00237     for (const auto &P : List) {
00238       insert(P);
00239     }
00240   }
00241 
00242   StringMap(StringMap &&RHS)
00243       : StringMapImpl(std::move(RHS)), Allocator(std::move(RHS.Allocator)) {}
00244 
00245   StringMap &operator=(StringMap RHS) {
00246     StringMapImpl::swap(RHS);
00247     std::swap(Allocator, RHS.Allocator);
00248     return *this;
00249   }
00250 
00251   // FIXME: Implement copy operations if/when they're needed.
00252 
00253   AllocatorTy &getAllocator() { return Allocator; }
00254   const AllocatorTy &getAllocator() const { return Allocator; }
00255 
00256   typedef const char* key_type;
00257   typedef ValueTy mapped_type;
00258   typedef StringMapEntry<ValueTy> value_type;
00259   typedef size_t size_type;
00260 
00261   typedef StringMapConstIterator<ValueTy> const_iterator;
00262   typedef StringMapIterator<ValueTy> iterator;
00263 
00264   iterator begin() {
00265     return iterator(TheTable, NumBuckets == 0);
00266   }
00267   iterator end() {
00268     return iterator(TheTable+NumBuckets, true);
00269   }
00270   const_iterator begin() const {
00271     return const_iterator(TheTable, NumBuckets == 0);
00272   }
00273   const_iterator end() const {
00274     return const_iterator(TheTable+NumBuckets, true);
00275   }
00276 
00277   iterator find(StringRef Key) {
00278     int Bucket = FindKey(Key);
00279     if (Bucket == -1) return end();
00280     return iterator(TheTable+Bucket, true);
00281   }
00282 
00283   const_iterator find(StringRef Key) const {
00284     int Bucket = FindKey(Key);
00285     if (Bucket == -1) return end();
00286     return const_iterator(TheTable+Bucket, true);
00287   }
00288 
00289   /// lookup - Return the entry for the specified key, or a default
00290   /// constructed value if no such entry exists.
00291   ValueTy lookup(StringRef Key) const {
00292     const_iterator it = find(Key);
00293     if (it != end())
00294       return it->second;
00295     return ValueTy();
00296   }
00297 
00298   ValueTy &operator[](StringRef Key) {
00299     return insert(std::make_pair(Key, ValueTy())).first->second;
00300   }
00301 
00302   /// count - Return 1 if the element is in the map, 0 otherwise.
00303   size_type count(StringRef Key) const {
00304     return find(Key) == end() ? 0 : 1;
00305   }
00306 
00307   /// insert - Insert the specified key/value pair into the map.  If the key
00308   /// already exists in the map, return false and ignore the request, otherwise
00309   /// insert it and return true.
00310   bool insert(MapEntryTy *KeyValue) {
00311     unsigned BucketNo = LookupBucketFor(KeyValue->getKey());
00312     StringMapEntryBase *&Bucket = TheTable[BucketNo];
00313     if (Bucket && Bucket != getTombstoneVal())
00314       return false;  // Already exists in map.
00315 
00316     if (Bucket == getTombstoneVal())
00317       --NumTombstones;
00318     Bucket = KeyValue;
00319     ++NumItems;
00320     assert(NumItems + NumTombstones <= NumBuckets);
00321 
00322     RehashTable();
00323     return true;
00324   }
00325 
00326   /// insert - Inserts the specified key/value pair into the map if the key
00327   /// isn't already in the map. The bool component of the returned pair is true
00328   /// if and only if the insertion takes place, and the iterator component of
00329   /// the pair points to the element with key equivalent to the key of the pair.
00330   std::pair<iterator, bool> insert(std::pair<StringRef, ValueTy> KV) {
00331     unsigned BucketNo = LookupBucketFor(KV.first);
00332     StringMapEntryBase *&Bucket = TheTable[BucketNo];
00333     if (Bucket && Bucket != getTombstoneVal())
00334       return std::make_pair(iterator(TheTable + BucketNo, false),
00335                             false); // Already exists in map.
00336 
00337     if (Bucket == getTombstoneVal())
00338       --NumTombstones;
00339     Bucket =
00340         MapEntryTy::Create(KV.first, Allocator, std::move(KV.second));
00341     ++NumItems;
00342     assert(NumItems + NumTombstones <= NumBuckets);
00343 
00344     BucketNo = RehashTable(BucketNo);
00345     return std::make_pair(iterator(TheTable + BucketNo, false), true);
00346   }
00347 
00348   // clear - Empties out the StringMap
00349   void clear() {
00350     if (empty()) return;
00351 
00352     // Zap all values, resetting the keys back to non-present (not tombstone),
00353     // which is safe because we're removing all elements.
00354     for (unsigned I = 0, E = NumBuckets; I != E; ++I) {
00355       StringMapEntryBase *&Bucket = TheTable[I];
00356       if (Bucket && Bucket != getTombstoneVal()) {
00357         static_cast<MapEntryTy*>(Bucket)->Destroy(Allocator);
00358       }
00359       Bucket = nullptr;
00360     }
00361 
00362     NumItems = 0;
00363     NumTombstones = 0;
00364   }
00365 
00366   /// remove - Remove the specified key/value pair from the map, but do not
00367   /// erase it.  This aborts if the key is not in the map.
00368   void remove(MapEntryTy *KeyValue) {
00369     RemoveKey(KeyValue);
00370   }
00371 
00372   void erase(iterator I) {
00373     MapEntryTy &V = *I;
00374     remove(&V);
00375     V.Destroy(Allocator);
00376   }
00377 
00378   bool erase(StringRef Key) {
00379     iterator I = find(Key);
00380     if (I == end()) return false;
00381     erase(I);
00382     return true;
00383   }
00384 
00385   ~StringMap() {
00386     // Delete all the elements in the map, but don't reset the elements
00387     // to default values.  This is a copy of clear(), but avoids unnecessary
00388     // work not required in the destructor.
00389     if (!empty()) {
00390       for (unsigned I = 0, E = NumBuckets; I != E; ++I) {
00391         StringMapEntryBase *Bucket = TheTable[I];
00392         if (Bucket && Bucket != getTombstoneVal()) {
00393           static_cast<MapEntryTy*>(Bucket)->Destroy(Allocator);
00394         }
00395       }
00396     }
00397     free(TheTable);
00398   }
00399 };
00400 
00401 template <typename ValueTy> class StringMapConstIterator {
00402 protected:
00403   StringMapEntryBase **Ptr;
00404 
00405 public:
00406   typedef StringMapEntry<ValueTy> value_type;
00407 
00408   StringMapConstIterator() : Ptr(nullptr) { }
00409 
00410   explicit StringMapConstIterator(StringMapEntryBase **Bucket,
00411                                   bool NoAdvance = false)
00412   : Ptr(Bucket) {
00413     if (!NoAdvance) AdvancePastEmptyBuckets();
00414   }
00415 
00416   const value_type &operator*() const {
00417     return *static_cast<StringMapEntry<ValueTy>*>(*Ptr);
00418   }
00419   const value_type *operator->() const {
00420     return static_cast<StringMapEntry<ValueTy>*>(*Ptr);
00421   }
00422 
00423   bool operator==(const StringMapConstIterator &RHS) const {
00424     return Ptr == RHS.Ptr;
00425   }
00426   bool operator!=(const StringMapConstIterator &RHS) const {
00427     return Ptr != RHS.Ptr;
00428   }
00429 
00430   inline StringMapConstIterator& operator++() {   // Preincrement
00431     ++Ptr;
00432     AdvancePastEmptyBuckets();
00433     return *this;
00434   }
00435   StringMapConstIterator operator++(int) {        // Postincrement
00436     StringMapConstIterator tmp = *this; ++*this; return tmp;
00437   }
00438 
00439 private:
00440   void AdvancePastEmptyBuckets() {
00441     while (*Ptr == nullptr || *Ptr == StringMapImpl::getTombstoneVal())
00442       ++Ptr;
00443   }
00444 };
00445 
00446 template<typename ValueTy>
00447 class StringMapIterator : public StringMapConstIterator<ValueTy> {
00448 public:
00449   StringMapIterator() {}
00450   explicit StringMapIterator(StringMapEntryBase **Bucket,
00451                              bool NoAdvance = false)
00452     : StringMapConstIterator<ValueTy>(Bucket, NoAdvance) {
00453   }
00454   StringMapEntry<ValueTy> &operator*() const {
00455     return *static_cast<StringMapEntry<ValueTy>*>(*this->Ptr);
00456   }
00457   StringMapEntry<ValueTy> *operator->() const {
00458     return static_cast<StringMapEntry<ValueTy>*>(*this->Ptr);
00459   }
00460 };
00461 }
00462 
00463 #endif