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 //===----------------------------------------------------------------------===//
14 #ifndef LLVM_ADT_CSTRINGMAP_H
15 #define LLVM_ADT_CSTRINGMAP_H
17 #include "llvm/Support/Allocator.h"
18 #include <cstring>
20 namespace llvm {
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 };
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;
41 /// Item - This is a pointer to the actual item object.
42 void *Item;
43 };
45 ItemBucket *TheTable;
46 unsigned NumBuckets;
47 unsigned NumItems;
48 unsigned ItemSize;
49 protected:
50 CStringMapImpl(unsigned InitSize, unsigned ItemSize);
51 void RehashTable();
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);
60 public:
61 unsigned getNumBuckets() const { return NumBuckets; }
62 unsigned getNumItems() const { return NumItems; }
64 void VisitEntries(const CStringMapVisitor &Visitor) const;
65 };
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)) {}
79 AllocatorTy &getAllocator() { return Allocator; }
80 const AllocatorTy &getAllocator() const { return Allocator; }
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 }
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);
98 unsigned KeyLength = KeyEnd-KeyStart;
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;
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;
115 // Copy the string information.
116 char *StrBuffer = (char*)(NewItem+1);
117 memcpy(StrBuffer, KeyStart, KeyLength);
118 StrBuffer[KeyLength] = 0; // Null terminate string.
120 // Fill in the bucket for the hash table. The FullHashValue was already
121 // filled in by LookupBucketFor.
122 Bucket.Item = NewItem;
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 }
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 };
142 }
144 #endif