LLVM API Documentation

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