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
|
//===--- CStringMap.h - CString 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 CStringMap class.
//
//===----------------------------------------------------------------------===//
#ifndef LLVM_ADT_CSTRINGMAP_H
#define LLVM_ADT_CSTRINGMAP_H
#include "llvm/Support/Allocator.h"
#include <cstring>
namespace llvm {
/// CStringMapVisitor - Subclasses of this class may be implemented to walk all
/// of the items in a CStringMap.
class CStringMapVisitor {
public:
virtual ~CStringMapVisitor();
virtual void Visit(const char *Key, void *Value) const = 0;
};
/// CStringMapImpl - This is the base class of CStringMap that is shared among
/// all of its instantiations.
class CStringMapImpl {
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.
void *Item;
};
ItemBucket *TheTable;
unsigned NumBuckets;
unsigned NumItems;
unsigned ItemSize;
protected:
CStringMapImpl(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 CStringMapVisitor &Visitor) const;
};
/// CStringMap - This is an unconventional map that is specialized for handling
/// keys that are "C strings", that is, null-terminated strings. 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 CStringMap : public CStringMapImpl {
AllocatorTy Allocator;
public:
CStringMap(unsigned InitialSize = 0)
: CStringMapImpl(InitialSize, sizeof(ValueTy)) {}
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.
ValueTy *FindValue(const char *KeyStart, const char *KeyEnd) {
unsigned BucketNo = LookupBucketFor(KeyStart, KeyEnd);
return static_cast<ValueTy*>(TheTable[BucketNo].Item);
}
/// GetKeyForValueInMap - Given a value that is inserted into this map, return
/// the string that corresponds to it. This is an efficient operation that
/// is provided by CStringMap. The string is live as long as the value is in
/// the map.
static const char *GetKeyForValueInMap(const ValueTy &Val) {
return reinterpret_cast<const char*>(&Val+1);
}
/// GetOrCreateValue - Look up the specified key in the table. If a value
/// exists, return it. Otherwise, default construct a value, insert it, and
/// return.
ValueTy &GetOrCreateValue(const char *KeyStart, const char *KeyEnd) {
unsigned BucketNo = LookupBucketFor(KeyStart, KeyEnd);
ItemBucket &Bucket = TheTable[BucketNo];
if (Bucket.Item)
return *static_cast<ValueTy*>(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 null-terminated string at the
// end.
unsigned AllocSize = sizeof(ValueTy)+KeyLength+1;
#ifdef __GNUC__
unsigned Alignment = __alignof__(ValueTy);
#else
// FIXME: ugly.
unsigned Alignment = 8;
#endif
ValueTy *NewItem = (ValueTy*)Allocator.Allocate(AllocSize, Alignment);
new (NewItem) ValueTy();
++NumItems;
// Copy the string information.
char *StrBuffer = (char*)(NewItem+1);
memcpy(StrBuffer, KeyStart, KeyLength);
StrBuffer[KeyLength] = 0; // Null terminate string.
// 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;
}
~CStringMap() {
for (ItemBucket *I = TheTable, *E = TheTable+NumBuckets; I != E; ++I) {
if (ValueTy *Id = static_cast<ValueTy*>(I->Item)) {
// Free memory referenced by the item.
Id->~ValueTy();
Allocator.Deallocate(Id);
}
}
delete [] TheTable;
}
};
}
#endif
|
