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