Line data Source code
1 : //===- ScopedHashTable.h - A simple scoped hash table -----------*- C++ -*-===//
2 : //
3 : // The LLVM Compiler Infrastructure
4 : //
5 : // This file is distributed under the University of Illinois Open Source
6 : // License. See LICENSE.TXT for details.
7 : //
8 : //===----------------------------------------------------------------------===//
9 : //
10 : // This file implements an efficient scoped hash table, which is useful for
11 : // things like dominator-based optimizations. This allows clients to do things
12 : // like this:
13 : //
14 : // ScopedHashTable<int, int> HT;
15 : // {
16 : // ScopedHashTableScope<int, int> Scope1(HT);
17 : // HT.insert(0, 0);
18 : // HT.insert(1, 1);
19 : // {
20 : // ScopedHashTableScope<int, int> Scope2(HT);
21 : // HT.insert(0, 42);
22 : // }
23 : // }
24 : //
25 : // Looking up the value for "0" in the Scope2 block will return 42. Looking
26 : // up the value for 0 before 42 is inserted or after Scope2 is popped will
27 : // return 0.
28 : //
29 : //===----------------------------------------------------------------------===//
30 :
31 : #ifndef LLVM_ADT_SCOPEDHASHTABLE_H
32 : #define LLVM_ADT_SCOPEDHASHTABLE_H
33 :
34 : #include "llvm/ADT/DenseMap.h"
35 : #include "llvm/ADT/DenseMapInfo.h"
36 : #include "llvm/Support/Allocator.h"
37 : #include <cassert>
38 : #include <new>
39 :
40 : namespace llvm {
41 :
42 : template <typename K, typename V, typename KInfo = DenseMapInfo<K>,
43 : typename AllocatorTy = MallocAllocator>
44 : class ScopedHashTable;
45 :
46 : template <typename K, typename V>
47 : class ScopedHashTableVal {
48 : ScopedHashTableVal *NextInScope;
49 : ScopedHashTableVal *NextForKey;
50 : K Key;
51 : V Val;
52 :
53 3343851 : ScopedHashTableVal(const K &key, const V &val) : Key(key), Val(val) {}
54 :
55 : public:
56 4890301 : const K &getKey() const { return Key; }
57 : const V &getValue() const { return Val; }
58 : V &getValue() { return Val; }
59 :
60 0 : ScopedHashTableVal *getNextForKey() { return NextForKey; }
61 : const ScopedHashTableVal *getNextForKey() const { return NextForKey; }
62 0 : ScopedHashTableVal *getNextInScope() { return NextInScope; }
63 :
64 : template <typename AllocatorTy>
65 1664096 : static ScopedHashTableVal *Create(ScopedHashTableVal *nextInScope,
66 : ScopedHashTableVal *nextForKey,
67 : const K &key, const V &val,
68 : AllocatorTy &Allocator) {
69 : ScopedHashTableVal *New = Allocator.template Allocate<ScopedHashTableVal>();
70 : // Set up the value.
71 : new (New) ScopedHashTableVal(key, val);
72 3343851 : New->NextInScope = nextInScope;
73 3343851 : New->NextForKey = nextForKey;
74 1664096 : return New;
75 : }
76 0 :
77 : template <typename AllocatorTy> void Destroy(AllocatorTy &Allocator) {
78 : // Free memory referenced by the item.
79 : this->~ScopedHashTableVal();
80 : Allocator.Deallocate(this);
81 : }
82 : };
83 0 :
84 0 : template <typename K, typename V, typename KInfo = DenseMapInfo<K>,
85 0 : typename AllocatorTy = MallocAllocator>
86 : class ScopedHashTableScope {
87 1662681 : /// HT - The hashtable that we are active for.
88 : ScopedHashTable<K, V, KInfo, AllocatorTy> &HT;
89 :
90 : /// PrevScope - This is the scope that we are shadowing in HT.
91 : ScopedHashTableScope *PrevScope;
92 :
93 : /// LastValInScope - This is the last value that was inserted for this scope
94 1662681 : /// or null if none have been inserted yet.
95 1662681 : ScopedHashTableVal<K, V> *LastValInScope;
96 1662681 :
97 : public:
98 1415 : ScopedHashTableScope(ScopedHashTable<K, V, KInfo, AllocatorTy> &HT);
99 : ScopedHashTableScope(ScopedHashTableScope &) = delete;
100 : ScopedHashTableScope &operator=(ScopedHashTableScope &) = delete;
101 : ~ScopedHashTableScope();
102 :
103 : ScopedHashTableScope *getParentScope() { return PrevScope; }
104 : const ScopedHashTableScope *getParentScope() const { return PrevScope; }
105 1415 :
106 1415 : private:
107 1415 : friend class ScopedHashTable<K, V, KInfo, AllocatorTy>;
108 :
109 0 : ScopedHashTableVal<K, V> *getLastValInScope() {
110 0 : return LastValInScope;
111 : }
112 :
113 0 : void setLastValInScope(ScopedHashTableVal<K, V> *Val) {
114 1680833 : LastValInScope = Val;
115 0 : }
116 0 : };
117 0 :
118 0 : template <typename K, typename V, typename KInfo = DenseMapInfo<K>>
119 : class ScopedHashTableIterator {
120 : ScopedHashTableVal<K, V> *Node;
121 0 :
122 : public:
123 : ScopedHashTableIterator(ScopedHashTableVal<K, V> *node) : Node(node) {}
124 :
125 0 : V &operator*() const {
126 : assert(Node && "Dereference end()");
127 : return Node->getValue();
128 : }
129 : V *operator->() const {
130 : return &Node->getValue();
131 : }
132 :
133 : bool operator==(const ScopedHashTableIterator &RHS) const {
134 : return Node == RHS.Node;
135 : }
136 : bool operator!=(const ScopedHashTableIterator &RHS) const {
137 : return Node != RHS.Node;
138 : }
139 :
140 : inline ScopedHashTableIterator& operator++() { // Preincrement
141 : assert(Node && "incrementing past end()");
142 : Node = Node->getNextForKey();
143 : return *this;
144 : }
145 : ScopedHashTableIterator operator++(int) { // Postincrement
146 : ScopedHashTableIterator tmp = *this; ++*this; return tmp;
147 : }
148 : };
149 :
150 : template <typename K, typename V, typename KInfo, typename AllocatorTy>
151 : class ScopedHashTable {
152 : public:
153 0 : /// ScopeTy - This is a helpful typedef that allows clients to get easy access
154 0 : /// to the name of the scope for this hash table.
155 : using ScopeTy = ScopedHashTableScope<K, V, KInfo, AllocatorTy>;
156 0 : using size_type = unsigned;
157 0 :
158 : private:
159 0 : friend class ScopedHashTableScope<K, V, KInfo, AllocatorTy>;
160 0 :
161 : using ValTy = ScopedHashTableVal<K, V>;
162 0 :
163 0 : DenseMap<K, ValTy*, KInfo> TopLevelMap;
164 : ScopeTy *CurScope = nullptr;
165 0 :
166 0 : AllocatorTy Allocator;
167 :
168 : public:
169 24084 : ScopedHashTable() = default;
170 3202792 : ScopedHashTable(AllocatorTy A) : Allocator(A) {}
171 0 : ScopedHashTable(const ScopedHashTable &) = delete;
172 0 : ScopedHashTable &operator=(const ScopedHashTable &) = delete;
173 0 :
174 21973 : ~ScopedHashTable() {
175 0 : assert(!CurScope && TopLevelMap.empty() && "Scope imbalance!");
176 21972 : }
177 0 :
178 0 : /// Access to the allocator.
179 0 : AllocatorTy &getAllocator() { return Allocator; }
180 0 : const AllocatorTy &getAllocator() const { return Allocator; }
181 0 :
182 0 : /// Return 1 if the specified key is in the table, 0 otherwise.
183 0 : size_type count(const K &Key) const {
184 3736435 : return TopLevelMap.count(Key);
185 : }
186 :
187 2418 : V lookup(const K &Key) const {
188 2418 : auto I = TopLevelMap.find(Key);
189 2418 : if (I != TopLevelMap.end())
190 90 : return I->second->getValue();
191 :
192 2328 : return V();
193 : }
194 :
195 : void insert(const K &Key, const V &Val) {
196 1680833 : insertIntoScope(CurScope, Key, Val);
197 : }
198 :
199 : using iterator = ScopedHashTableIterator<K, V, KInfo>;
200 :
201 : iterator end() { return iterator(0); }
202 :
203 : iterator begin(const K &Key) {
204 : typename DenseMap<K, ValTy*, KInfo>::iterator I =
205 : TopLevelMap.find(Key);
206 : if (I == TopLevelMap.end()) return end();
207 : return iterator(I->second);
208 : }
209 :
210 : ScopeTy *getCurScope() { return CurScope; }
211 : const ScopeTy *getCurScope() const { return CurScope; }
212 :
213 : /// insertIntoScope - This inserts the specified key/value at the specified
214 : /// (possibly not the current) scope. While it is ok to insert into a scope
215 : /// that isn't the current one, it isn't ok to insert *underneath* an existing
216 : /// value of the specified key.
217 1680833 : void insertIntoScope(ScopeTy *S, const K &Key, const V &Val) {
218 : assert(S && "No scope active!");
219 1680833 : ScopedHashTableVal<K, V> *&KeyEntry = TopLevelMap[Key];
220 1681911 : KeyEntry = ValTy::Create(S->getLastValInScope(), KeyEntry, Key, Val,
221 1078 : Allocator);
222 : S->setLastValInScope(KeyEntry);
223 1680833 : }
224 : };
225 :
226 : /// ScopedHashTableScope ctor - Install this as the current scope for the hash
227 : /// table.
228 : template <typename K, typename V, typename KInfo, typename Allocator>
229 464336 : ScopedHashTableScope<K, V, KInfo, Allocator>::
230 464336 : ScopedHashTableScope(ScopedHashTable<K, V, KInfo, Allocator> &ht) : HT(ht) {
231 464336 : PrevScope = HT.CurScope;
232 464336 : HT.CurScope = this;
233 464336 : LastValInScope = nullptr;
234 : }
235 :
236 : template <typename K, typename V, typename KInfo, typename Allocator>
237 627853 : ScopedHashTableScope<K, V, KInfo, Allocator>::~ScopedHashTableScope() {
238 : assert(HT.CurScope == this && "Scope imbalance!");
239 464336 : HT.CurScope = PrevScope;
240 :
241 : // Pop and delete all values corresponding to this scope.
242 2308685 : while (ScopedHashTableVal<K, V> *ThisEntry = LastValInScope) {
243 : // Pop this value out of the TopLevelMap.
244 1844349 : if (!ThisEntry->getNextForKey()) {
245 : assert(HT.TopLevelMap[ThisEntry->getKey()] == ThisEntry &&
246 : "Scope imbalance!");
247 1429184 : HT.TopLevelMap.erase(ThisEntry->getKey());
248 : } else {
249 251648 : ScopedHashTableVal<K, V> *&KeyEntry = HT.TopLevelMap[ThisEntry->getKey()];
250 : assert(KeyEntry == ThisEntry && "Scope imbalance!");
251 251648 : KeyEntry = ThisEntry->getNextForKey();
252 141830 : }
253 :
254 : // Pop this value out of the scope.
255 3218126 : LastValInScope = ThisEntry->getNextInScope();
256 1537294 :
257 1537294 : // Delete this entry.
258 1776430 : ThisEntry->Destroy(HT.getAllocator());
259 : }
260 470943 : }
261 :
262 6684 : } // end namespace llvm
263 6684 :
264 6684 : #endif // LLVM_ADT_SCOPEDHASHTABLE_H
|
