include/llvm/ADT/StringMap.h

   1 //===--- CStringMap.h - CString Hash table map interface --------*- C++ -*-===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file was developed by Chris Lattner and is distributed under
   6 // the University of Illinois Open Source License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 // This file defines the CStringMap class.
  11 //
  12 //===----------------------------------------------------------------------===//
  13
  14 #ifndef LLVM_ADT_CSTRINGMAP_H
  15 #define LLVM_ADT_CSTRINGMAP_H
  16
  17 #include "llvm/Support/Allocator.h"
  18 #include <cstring>
  19
  20 namespace llvm {
  21
  22 /// CStringMapVisitor - Subclasses of this class may be implemented to walk all
  23 /// of the items in a CStringMap.
  24 class CStringMapVisitor {
  25 public:
  26   virtual ~CStringMapVisitor();
  27   virtual void Visit(const char *Key, void *Value) const = 0;
  28 };
  29
  30 /// CStringMapImpl - This is the base class of CStringMap that is shared among
  31 /// all of its instantiations.
  32 class CStringMapImpl {
  33 protected:
  34   /// ItemBucket - The hash table consists of an array of these.  If Item is
  35   /// non-null, this is an extant entry, otherwise, it is a hole.
  36   struct ItemBucket {
  37     /// FullHashValue - This remembers the full hash value of the key for
  38     /// easy scanning.
  39     unsigned FullHashValue;
  40
  41     /// Item - This is a pointer to the actual item object.
  42     void *Item;
  43   };
  44
  45   ItemBucket *TheTable;
  46   unsigned NumBuckets;
  47   unsigned NumItems;
  48   unsigned ItemSize;
  49 protected:
  50   CStringMapImpl(unsigned InitSize, unsigned ItemSize);
  51   void RehashTable();
  52
  53   /// LookupBucketFor - Look up the bucket that the specified string should end
  54   /// up in.  If it already exists as a key in the map, the Item pointer for the
  55   /// specified bucket will be non-null.  Otherwise, it will be null.  In either
  56   /// case, the FullHashValue field of the bucket will be set to the hash value
  57   /// of the string.
  58   unsigned LookupBucketFor(const char *KeyStart, const char *KeyEnd);
  59
  60 public:
  61   unsigned getNumBuckets() const { return NumBuckets; }
  62   unsigned getNumItems() const { return NumItems; }
  63
  64   void VisitEntries(const CStringMapVisitor &Visitor) const;
  65 };
  66
  67
  68 /// CStringMap - This is an unconventional map that is specialized for handling
  69 /// keys that are "C strings", that is, null-terminated strings.  This does some
  70 /// funky memory allocation and hashing things to make it extremely efficient,
  71 /// storing the string data *after* the value in the map.
  72 template<typename ValueTy, typename AllocatorTy = MallocAllocator>
  73 class CStringMap : public CStringMapImpl {
  74   AllocatorTy Allocator;
  75 public:
  76   CStringMap(unsigned InitialSize = 0)
  77     : CStringMapImpl(InitialSize, sizeof(ValueTy)) {}
  78
  79   AllocatorTy &getAllocator() { return Allocator; }
  80   const AllocatorTy &getAllocator() const { return Allocator; }
  81
  82   /// FindValue - Look up the specified key in the map.  If it exists, return a
  83   /// pointer to the element, otherwise return null.
  84   ValueTy *FindValue(const char *KeyStart, const char *KeyEnd) {
  85     unsigned BucketNo = LookupBucketFor(KeyStart, KeyEnd);
  86     return static_cast<ValueTy*>(TheTable[BucketNo].Item);
  87   }
  88
  89   /// GetKeyForValueInMap - Given a value that is inserted into this map, return
  90   /// the string that corresponds to it.  This is an efficient operation that
  91   /// is provided by CStringMap.  The string is live as long as the value is in
  92   /// the map.
  93   static const char *GetKeyForValueInMap(const ValueTy &Val) {
  94     return reinterpret_cast<const char*>(&Val+1);
  95   }
  96
  97   /// GetOrCreateValue - Look up the specified key in the table.  If a value
  98   /// exists, return it.  Otherwise, default construct a value, insert it, and
  99   /// return.
 100   ValueTy &GetOrCreateValue(const char *KeyStart, const char *KeyEnd) {
 101     unsigned BucketNo = LookupBucketFor(KeyStart, KeyEnd);
 102     ItemBucket &Bucket = TheTable[BucketNo];
 103     if (Bucket.Item)
 104       return *static_cast<ValueTy*>(Bucket.Item);
 105
 106     unsigned KeyLength = KeyEnd-KeyStart;
 107
 108     // Okay, the item doesn't already exist, and Bucket is the bucket to fill
 109     // in.  Allocate a new item with space for the null-terminated string at the
 110     // end.
 111     unsigned AllocSize = sizeof(ValueTy)+KeyLength+1;
 112
 113 #ifdef __GNUC__
 114     unsigned Alignment = __alignof__(ValueTy);
 115 #else
 116     // FIXME: ugly.
 117     unsigned Alignment = 8;
 118 #endif
 119     ValueTy *NewItem = (ValueTy*)Allocator.Allocate(AllocSize, Alignment);
 120     new (NewItem) ValueTy();
 121     ++NumItems;
 122
 123     // Copy the string information.
 124     char *StrBuffer = (char*)(NewItem+1);
 125     memcpy(StrBuffer, KeyStart, KeyLength);
 126     StrBuffer[KeyLength] = 0;  // Null terminate string.
 127
 128     // Fill in the bucket for the hash table.  The FullHashValue was already
 129     // filled in by LookupBucketFor.
 130     Bucket.Item = NewItem;
 131
 132     // If the hash table is now more than 3/4 full, rehash into a larger table.
 133     if (NumItems > NumBuckets*3/4)
 134       RehashTable();
 135     return *NewItem;
 136   }
 137
 138   ~CStringMap() {
 139     for (ItemBucket *I = TheTable, *E = TheTable+NumBuckets; I != E; ++I) {
 140       if (ValueTy *Id = static_cast<ValueTy*>(I->Item)) {
 141         // Free memory referenced by the item.
 142         Id->~ValueTy();
 143         Allocator.Deallocate(Id);
 144       }
 145     }
 146     delete [] TheTable;
 147   }
 148 };
 149
 150 }
 151
 152 #endif
 153