StringMap.h revision 23d7b3611759c7fb3a853dfce3ee3d43ef5ca67d 
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
20namespace llvm {
21
22/// CStringMapVisitor - Subclasses of this class may be implemented to walk all
23/// of the items in a CStringMap.
24class CStringMapVisitor {
25public:
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.
32class CStringMapImpl {
33protected:
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;
49protected:
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
60public:
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.
72template<typename ValueTy, typename AllocatorTy = MallocAllocator>
73class CStringMap : public CStringMapImpl {
74  AllocatorTy Allocator;
75public:
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