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