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