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   /// GetOrCreateValue - Look up the specified key in the table.  If a value
  90   /// exists, return it.  Otherwise, default construct a value, insert it, and
  91   /// return.
  92   ValueTy &GetOrCreateValue(const char *KeyStart, const char *KeyEnd) {
  93     unsigned BucketNo = LookupBucketFor(KeyStart, KeyEnd);
  94     ItemBucket &Bucket = TheTable[BucketNo];
  95     if (Bucket.Item)
  96       return *static_cast<ValueTy*>(Bucket.Item);
  97
  98     unsigned KeyLength = KeyEnd-KeyStart;
  99
 100     // Okay, the item doesn't already exist, and Bucket is the bucket to fill
 101     // in.  Allocate a new item with space for the null-terminated string at the
 102     // end.
 103     unsigned AllocSize = sizeof(ValueTy)+KeyLength+1;
 104
 105 #ifdef __GNUC__
 106     unsigned Alignment = __alignof__(ValueTy);
 107 #else
 108     // FIXME: ugly.
 109     unsigned Alignment = 8;
 110 #endif
 111     ValueTy *NewItem = (ValueTy*)Allocator.Allocate(AllocSize, Alignment);
 112     new (NewItem) ValueTy();
 113     ++NumItems;
 114
 115     // Copy the string information.
 116     char *StrBuffer = (char*)(NewItem+1);
 117     memcpy(StrBuffer, KeyStart, KeyLength);
 118     StrBuffer[KeyLength] = 0;  // Null terminate string.
 119
 120     // Fill in the bucket for the hash table.  The FullHashValue was already
 121     // filled in by LookupBucketFor.
 122     Bucket.Item = NewItem;
 123
 124     // If the hash table is now more than 3/4 full, rehash into a larger table.
 125     if (NumItems > NumBuckets*3/4)
 126       RehashTable();
 127     return *NewItem;
 128   }
 129
 130   ~CStringMap() {
 131     for (ItemBucket *I = TheTable, *E = TheTable+NumBuckets; I != E; ++I) {
 132       if (ValueTy *Id = static_cast<ValueTy*>(I->Item)) {
 133         // Free memory referenced by the item.
 134         Id->~ValueTy();
 135         Allocator.Deallocate(Id);
 136       }
 137     }
 138     delete [] TheTable;
 139   }
 140 };
 141
 142 }
 143
 144 #endif
 145