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   /// GetStringMapEntryFromValue - Given a value that is known to be embedded
00183   /// into a StringMapEntry, return the StringMapEntry itself.
00184   static StringMapEntry &GetStringMapEntryFromValue(ValueTy &V) {
00185     StringMapEntry *EPtr = 0;
00186     char *Ptr = reinterpret_cast<char*>(&V) -
00187                   (reinterpret_cast<char*>(&EPtr->second) -
00188                    reinterpret_cast<char*>(EPtr));
00189     return *reinterpret_cast<StringMapEntry*>(Ptr);
00190   }
00191   static const StringMapEntry &GetStringMapEntryFromValue(const ValueTy &V) {
00192     return GetStringMapEntryFromValue(const_cast<ValueTy&>(V));
00193   }
00194 
00195   /// GetStringMapEntryFromKeyData - Given key data that is known to be embedded
00196   /// into a StringMapEntry, return the StringMapEntry itself.
00197   static StringMapEntry &GetStringMapEntryFromKeyData(const char *KeyData) {
00198     char *Ptr = const_cast<char*>(KeyData) - sizeof(StringMapEntry<ValueTy>);
00199     return *reinterpret_cast<StringMapEntry*>(Ptr);
00200   }
00201 
00202   /// Destroy - Destroy this StringMapEntry, releasing memory back to the
00203   /// specified allocator.
00204   template<typename AllocatorTy>
00205   void Destroy(AllocatorTy &Allocator) {
00206     // Free memory referenced by the item.
00207     unsigned AllocSize =
00208         static_cast<unsigned>(sizeof(StringMapEntry)) + getKeyLength() + 1;
00209     this->~StringMapEntry();
00210     Allocator.Deallocate(static_cast<void *>(this), AllocSize);
00211   }
00212 
00213   /// Destroy this object, releasing memory back to the malloc allocator.
00214   void Destroy() {
00215     MallocAllocator A;
00216     Destroy(A);
00217   }
00218 };
00219 
00220 
00221 /// StringMap - This is an unconventional map that is specialized for handling
00222 /// keys that are "strings", which are basically ranges of bytes. This does some
00223 /// funky memory allocation and hashing things to make it extremely efficient,
00224 /// storing the string data *after* the value in the map.
00225 template<typename ValueTy, typename AllocatorTy = MallocAllocator>
00226 class StringMap : public StringMapImpl {
00227   AllocatorTy Allocator;
00228 public:
00229   typedef StringMapEntry<ValueTy> MapEntryTy;
00230   
00231   StringMap() : StringMapImpl(static_cast<unsigned>(sizeof(MapEntryTy))) {}
00232   explicit StringMap(unsigned InitialSize)
00233     : StringMapImpl(InitialSize, static_cast<unsigned>(sizeof(MapEntryTy))) {}
00234 
00235   explicit StringMap(AllocatorTy A)
00236     : StringMapImpl(static_cast<unsigned>(sizeof(MapEntryTy))), Allocator(A) {}
00237 
00238   StringMap(unsigned InitialSize, AllocatorTy A)
00239     : StringMapImpl(InitialSize, static_cast<unsigned>(sizeof(MapEntryTy))),
00240       Allocator(A) {}
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 
00402 template<typename ValueTy>
00403 class StringMapConstIterator {
00404 protected:
00405   StringMapEntryBase **Ptr;
00406 public:
00407   typedef StringMapEntry<ValueTy> value_type;
00408 
00409   StringMapConstIterator() : Ptr(nullptr) { }
00410 
00411   explicit StringMapConstIterator(StringMapEntryBase **Bucket,
00412                                   bool NoAdvance = false)
00413   : Ptr(Bucket) {
00414     if (!NoAdvance) AdvancePastEmptyBuckets();
00415   }
00416 
00417   const value_type &operator*() const {
00418     return *static_cast<StringMapEntry<ValueTy>*>(*Ptr);
00419   }
00420   const value_type *operator->() const {
00421     return static_cast<StringMapEntry<ValueTy>*>(*Ptr);
00422   }
00423 
00424   bool operator==(const StringMapConstIterator &RHS) const {
00425     return Ptr == RHS.Ptr;
00426   }
00427   bool operator!=(const StringMapConstIterator &RHS) const {
00428     return Ptr != RHS.Ptr;
00429   }
00430 
00431   inline StringMapConstIterator& operator++() {   // Preincrement
00432     ++Ptr;
00433     AdvancePastEmptyBuckets();
00434     return *this;
00435   }
00436   StringMapConstIterator operator++(int) {        // Postincrement
00437     StringMapConstIterator tmp = *this; ++*this; return tmp;
00438   }
00439 
00440 private:
00441   void AdvancePastEmptyBuckets() {
00442     while (*Ptr == nullptr || *Ptr == StringMapImpl::getTombstoneVal())
00443       ++Ptr;
00444   }
00445 };
00446 
00447 template<typename ValueTy>
00448 class StringMapIterator : public StringMapConstIterator<ValueTy> {
00449 public:
00450   StringMapIterator() {}
00451   explicit StringMapIterator(StringMapEntryBase **Bucket,
00452                              bool NoAdvance = false)
00453     : StringMapConstIterator<ValueTy>(Bucket, NoAdvance) {
00454   }
00455   StringMapEntry<ValueTy> &operator*() const {
00456     return *static_cast<StringMapEntry<ValueTy>*>(*this->Ptr);
00457   }
00458   StringMapEntry<ValueTy> *operator->() const {
00459     return static_cast<StringMapEntry<ValueTy>*>(*this->Ptr);
00460   }
00461 };
00462 
00463 }
00464 
00465 #endif