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 ScopedHashTableVal(const K &key, const V &val) : Key(key), Val(val) {} 53 54 public: 55 const K &getKey() const { return Key; } 56 const V &getValue() const { return Val; } 57 V &getValue() { return Val; } 58 59 ScopedHashTableVal *getNextForKey() { return NextForKey; } 60 const ScopedHashTableVal *getNextForKey() const { return NextForKey; } 61 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 AllocatorTy &Allocator) { 68 ScopedHashTableVal *New = Allocator.template Allocate<ScopedHashTableVal>(); 69 // Set up the value. 70 new (New) ScopedHashTableVal(key, val); 71 New->NextInScope = nextInScope; 72 New->NextForKey = nextForKey; 73 return New; 74 } 75 76 template <typename AllocatorTy> void Destroy(AllocatorTy &Allocator) { 77 // Free memory referenced by the item. 78 this->~ScopedHashTableVal(); 79 Allocator.Deallocate(this); 80 } 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 ScopedHashTableVal<K, V> *getLastValInScope() { 109 return LastValInScope; 110 } 111 112 void setLastValInScope(ScopedHashTableVal<K, V> *Val) { 113 LastValInScope = Val; 114 } 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 ScopedHashTable() = default; 169 ScopedHashTable(AllocatorTy A) : Allocator(A) {} 170 ScopedHashTable(const ScopedHashTable &) = delete; 171 ScopedHashTable &operator=(const ScopedHashTable &) = delete; 172 173 ~ScopedHashTable() { 174 assert(!CurScope && TopLevelMap.empty() && "Scope imbalance!"); 175 } 176 177 /// Access to the allocator. 178 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 size_type count(const K &Key) const { 183 return TopLevelMap.count(Key); 184 } 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 void insert(const K &Key, const V &Val) { 195 insertIntoScope(CurScope, Key, Val); 196 } 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 void insertIntoScope(ScopeTy *S, const K &Key, const V &Val) { 217 assert(S && "No scope active!"); 218 ScopedHashTableVal<K, V> *&KeyEntry = TopLevelMap[Key]; 219 KeyEntry = ValTy::Create(S->getLastValInScope(), KeyEntry, Key, Val, 220 Allocator); 221 S->setLastValInScope(KeyEntry); 222 } 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 ScopedHashTableScope(ScopedHashTable<K, V, KInfo, Allocator> &ht) : HT(ht) { 230 PrevScope = HT.CurScope; 231 HT.CurScope = this; 232 LastValInScope = nullptr; 233 } 234 235 template <typename K, typename V, typename KInfo, typename Allocator> 236 ScopedHashTableScope<K, V, KInfo, Allocator>::~ScopedHashTableScope() { 237 assert(HT.CurScope == this && "Scope imbalance!"); 238 HT.CurScope = PrevScope; 239 240 // Pop and delete all values corresponding to this scope. 241 while (ScopedHashTableVal<K, V> *ThisEntry = LastValInScope) { 242 // Pop this value out of the TopLevelMap. 243 if (!ThisEntry->getNextForKey()) { 244 assert(HT.TopLevelMap[ThisEntry->getKey()] == ThisEntry && 245 "Scope imbalance!"); 246 HT.TopLevelMap.erase(ThisEntry->getKey()); 247 } else { 248 ScopedHashTableVal<K, V> *&KeyEntry = HT.TopLevelMap[ThisEntry->getKey()]; 249 assert(KeyEntry == ThisEntry && "Scope imbalance!"); 250 KeyEntry = ThisEntry->getNextForKey(); 251 } 252 253 // Pop this value out of the scope. 254 LastValInScope = ThisEntry->getNextInScope(); 255 256 // Delete this entry. 257 ThisEntry->Destroy(HT.getAllocator()); 258 } 259 } 260 261 } // end namespace llvm 262 263 #endif // LLVM_ADT_SCOPEDHASHTABLE_H 264