1//===- ScopedHashTable.h - A simple scoped hash table ---------------------===// 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 <cassert> 35#include "llvm/ADT/DenseMap.h" 36 37namespace llvm { 38 39template <typename K, typename V, typename KInfo = DenseMapInfo<K> > 40class ScopedHashTable; 41 42template <typename K, typename V, typename KInfo = DenseMapInfo<K> > 43class ScopedHashTableVal { 44 ScopedHashTableVal *NextInScope; 45 ScopedHashTableVal *NextForKey; 46 K Key; 47 V Val; 48public: 49 ScopedHashTableVal(ScopedHashTableVal *nextInScope, 50 ScopedHashTableVal *nextForKey, const K &key, const V &val) 51 : NextInScope(nextInScope), NextForKey(nextForKey), Key(key), Val(val) { 52 } 53 54 const K &getKey() const { return Key; } 55 const V &getValue() const { return Val; } 56 V &getValue() { return Val; } 57 58 ScopedHashTableVal *getNextForKey() { return NextForKey; } 59 const ScopedHashTableVal *getNextForKey() const { return NextForKey; } 60public: 61 ScopedHashTableVal *getNextInScope() { return NextInScope; } 62}; 63 64template <typename K, typename V, typename KInfo = DenseMapInfo<K> > 65class ScopedHashTableScope { 66 /// HT - The hashtable that we are active for. 67 ScopedHashTable<K, V, KInfo> &HT; 68 69 /// PrevScope - This is the scope that we are shadowing in HT. 70 ScopedHashTableScope *PrevScope; 71 72 /// LastValInScope - This is the last value that was inserted for this scope 73 /// or null if none have been inserted yet. 74 ScopedHashTableVal<K, V, KInfo> *LastValInScope; 75 void operator=(ScopedHashTableScope&); // DO NOT IMPLEMENT 76 ScopedHashTableScope(ScopedHashTableScope&); // DO NOT IMPLEMENT 77public: 78 ScopedHashTableScope(ScopedHashTable<K, V, KInfo> &HT); 79 ~ScopedHashTableScope(); 80 81private: 82 friend class ScopedHashTable<K, V, KInfo>; 83 ScopedHashTableVal<K, V, KInfo> *getLastValInScope() { 84 return LastValInScope; 85 } 86 void setLastValInScope(ScopedHashTableVal<K, V, KInfo> *Val) { 87 LastValInScope = Val; 88 } 89}; 90 91 92template <typename K, typename V, typename KInfo = DenseMapInfo<K> > 93class ScopedHashTableIterator { 94 ScopedHashTableVal<K, V, KInfo> *Node; 95public: 96 ScopedHashTableIterator(ScopedHashTableVal<K, V, KInfo> *node) : Node(node) {} 97 98 V &operator*() const { 99 assert(Node && "Dereference end()"); 100 return Node->getValue(); 101 } 102 V *operator->() const { 103 return &Node->getValue(); 104 } 105 106 bool operator==(const ScopedHashTableIterator &RHS) const { 107 return Node == RHS.Node; 108 } 109 bool operator!=(const ScopedHashTableIterator &RHS) const { 110 return Node != RHS.Node; 111 } 112 113 inline ScopedHashTableIterator& operator++() { // Preincrement 114 assert(Node && "incrementing past end()"); 115 Node = Node->getNextForKey(); 116 return *this; 117 } 118 ScopedHashTableIterator operator++(int) { // Postincrement 119 ScopedHashTableIterator tmp = *this; ++*this; return tmp; 120 } 121}; 122 123 124template <typename K, typename V, typename KInfo> 125class ScopedHashTable { 126 DenseMap<K, ScopedHashTableVal<K, V, KInfo>*, KInfo> TopLevelMap; 127 ScopedHashTableScope<K, V, KInfo> *CurScope; 128 ScopedHashTable(const ScopedHashTable&); // NOT YET IMPLEMENTED 129 void operator=(const ScopedHashTable&); // NOT YET IMPLEMENTED 130 friend class ScopedHashTableScope<K, V, KInfo>; 131public: 132 ScopedHashTable() : CurScope(0) {} 133 ~ScopedHashTable() { 134 assert(CurScope == 0 && TopLevelMap.empty() && "Scope imbalance!"); 135 } 136 137 bool count(const K &Key) const { 138 return TopLevelMap.count(Key); 139 } 140 141 V lookup(const K &Key) {
| 1//===- ScopedHashTable.h - A simple scoped hash table ---------------------===// 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 <cassert> 35#include "llvm/ADT/DenseMap.h" 36 37namespace llvm { 38 39template <typename K, typename V, typename KInfo = DenseMapInfo<K> > 40class ScopedHashTable; 41 42template <typename K, typename V, typename KInfo = DenseMapInfo<K> > 43class ScopedHashTableVal { 44 ScopedHashTableVal *NextInScope; 45 ScopedHashTableVal *NextForKey; 46 K Key; 47 V Val; 48public: 49 ScopedHashTableVal(ScopedHashTableVal *nextInScope, 50 ScopedHashTableVal *nextForKey, const K &key, const V &val) 51 : NextInScope(nextInScope), NextForKey(nextForKey), Key(key), Val(val) { 52 } 53 54 const K &getKey() const { return Key; } 55 const V &getValue() const { return Val; } 56 V &getValue() { return Val; } 57 58 ScopedHashTableVal *getNextForKey() { return NextForKey; } 59 const ScopedHashTableVal *getNextForKey() const { return NextForKey; } 60public: 61 ScopedHashTableVal *getNextInScope() { return NextInScope; } 62}; 63 64template <typename K, typename V, typename KInfo = DenseMapInfo<K> > 65class ScopedHashTableScope { 66 /// HT - The hashtable that we are active for. 67 ScopedHashTable<K, V, KInfo> &HT; 68 69 /// PrevScope - This is the scope that we are shadowing in HT. 70 ScopedHashTableScope *PrevScope; 71 72 /// LastValInScope - This is the last value that was inserted for this scope 73 /// or null if none have been inserted yet. 74 ScopedHashTableVal<K, V, KInfo> *LastValInScope; 75 void operator=(ScopedHashTableScope&); // DO NOT IMPLEMENT 76 ScopedHashTableScope(ScopedHashTableScope&); // DO NOT IMPLEMENT 77public: 78 ScopedHashTableScope(ScopedHashTable<K, V, KInfo> &HT); 79 ~ScopedHashTableScope(); 80 81private: 82 friend class ScopedHashTable<K, V, KInfo>; 83 ScopedHashTableVal<K, V, KInfo> *getLastValInScope() { 84 return LastValInScope; 85 } 86 void setLastValInScope(ScopedHashTableVal<K, V, KInfo> *Val) { 87 LastValInScope = Val; 88 } 89}; 90 91 92template <typename K, typename V, typename KInfo = DenseMapInfo<K> > 93class ScopedHashTableIterator { 94 ScopedHashTableVal<K, V, KInfo> *Node; 95public: 96 ScopedHashTableIterator(ScopedHashTableVal<K, V, KInfo> *node) : Node(node) {} 97 98 V &operator*() const { 99 assert(Node && "Dereference end()"); 100 return Node->getValue(); 101 } 102 V *operator->() const { 103 return &Node->getValue(); 104 } 105 106 bool operator==(const ScopedHashTableIterator &RHS) const { 107 return Node == RHS.Node; 108 } 109 bool operator!=(const ScopedHashTableIterator &RHS) const { 110 return Node != RHS.Node; 111 } 112 113 inline ScopedHashTableIterator& operator++() { // Preincrement 114 assert(Node && "incrementing past end()"); 115 Node = Node->getNextForKey(); 116 return *this; 117 } 118 ScopedHashTableIterator operator++(int) { // Postincrement 119 ScopedHashTableIterator tmp = *this; ++*this; return tmp; 120 } 121}; 122 123 124template <typename K, typename V, typename KInfo> 125class ScopedHashTable { 126 DenseMap<K, ScopedHashTableVal<K, V, KInfo>*, KInfo> TopLevelMap; 127 ScopedHashTableScope<K, V, KInfo> *CurScope; 128 ScopedHashTable(const ScopedHashTable&); // NOT YET IMPLEMENTED 129 void operator=(const ScopedHashTable&); // NOT YET IMPLEMENTED 130 friend class ScopedHashTableScope<K, V, KInfo>; 131public: 132 ScopedHashTable() : CurScope(0) {} 133 ~ScopedHashTable() { 134 assert(CurScope == 0 && TopLevelMap.empty() && "Scope imbalance!"); 135 } 136 137 bool count(const K &Key) const { 138 return TopLevelMap.count(Key); 139 } 140 141 V lookup(const K &Key) {
|
143 } 144 145 void insert(const K &Key, const V &Val) { 146 assert(CurScope && "No scope active!"); 147 148 ScopedHashTableVal<K, V, KInfo> *&KeyEntry = TopLevelMap[Key]; 149 150 KeyEntry= new ScopedHashTableVal<K, V, KInfo>(CurScope->getLastValInScope(), 151 KeyEntry, Key, Val); 152 CurScope->setLastValInScope(KeyEntry); 153 } 154 155 typedef ScopedHashTableIterator<K, V, KInfo> iterator; 156 157 iterator end() { return iterator(0); } 158 159 iterator begin(const K &Key) { 160 typename DenseMap<K, ScopedHashTableVal<K, V, KInfo>*, KInfo>::iterator I = 161 TopLevelMap.find(Key); 162 if (I == TopLevelMap.end()) return end(); 163 return iterator(I->second); 164 } 165}; 166 167/// ScopedHashTableScope ctor - Install this as the current scope for the hash 168/// table. 169template <typename K, typename V, typename KInfo> 170ScopedHashTableScope<K, V, KInfo>:: 171 ScopedHashTableScope(ScopedHashTable<K, V, KInfo> &ht) : HT(ht) { 172 PrevScope = HT.CurScope; 173 HT.CurScope = this; 174 LastValInScope = 0; 175} 176 177template <typename K, typename V, typename KInfo> 178ScopedHashTableScope<K, V, KInfo>::~ScopedHashTableScope() { 179 assert(HT.CurScope == this && "Scope imbalance!"); 180 HT.CurScope = PrevScope; 181 182 // Pop and delete all values corresponding to this scope. 183 while (ScopedHashTableVal<K, V, KInfo> *ThisEntry = LastValInScope) { 184 // Pop this value out of the TopLevelMap. 185 if (ThisEntry->getNextForKey() == 0) { 186 assert(HT.TopLevelMap[ThisEntry->getKey()] == ThisEntry && 187 "Scope imbalance!"); 188 HT.TopLevelMap.erase(ThisEntry->getKey()); 189 } else { 190 ScopedHashTableVal<K, V, KInfo> *&KeyEntry = 191 HT.TopLevelMap[ThisEntry->getKey()]; 192 assert(KeyEntry == ThisEntry && "Scope imbalance!"); 193 KeyEntry = ThisEntry->getNextForKey(); 194 } 195 196 // Pop this value out of the scope. 197 LastValInScope = ThisEntry->getNextInScope(); 198 199 // Delete this entry. 200 delete ThisEntry; 201 } 202} 203 204} // end namespace llvm 205 206#endif
| 148 } 149 150 void insert(const K &Key, const V &Val) { 151 assert(CurScope && "No scope active!"); 152 153 ScopedHashTableVal<K, V, KInfo> *&KeyEntry = TopLevelMap[Key]; 154 155 KeyEntry= new ScopedHashTableVal<K, V, KInfo>(CurScope->getLastValInScope(), 156 KeyEntry, Key, Val); 157 CurScope->setLastValInScope(KeyEntry); 158 } 159 160 typedef ScopedHashTableIterator<K, V, KInfo> iterator; 161 162 iterator end() { return iterator(0); } 163 164 iterator begin(const K &Key) { 165 typename DenseMap<K, ScopedHashTableVal<K, V, KInfo>*, KInfo>::iterator I = 166 TopLevelMap.find(Key); 167 if (I == TopLevelMap.end()) return end(); 168 return iterator(I->second); 169 } 170}; 171 172/// ScopedHashTableScope ctor - Install this as the current scope for the hash 173/// table. 174template <typename K, typename V, typename KInfo> 175ScopedHashTableScope<K, V, KInfo>:: 176 ScopedHashTableScope(ScopedHashTable<K, V, KInfo> &ht) : HT(ht) { 177 PrevScope = HT.CurScope; 178 HT.CurScope = this; 179 LastValInScope = 0; 180} 181 182template <typename K, typename V, typename KInfo> 183ScopedHashTableScope<K, V, KInfo>::~ScopedHashTableScope() { 184 assert(HT.CurScope == this && "Scope imbalance!"); 185 HT.CurScope = PrevScope; 186 187 // Pop and delete all values corresponding to this scope. 188 while (ScopedHashTableVal<K, V, KInfo> *ThisEntry = LastValInScope) { 189 // Pop this value out of the TopLevelMap. 190 if (ThisEntry->getNextForKey() == 0) { 191 assert(HT.TopLevelMap[ThisEntry->getKey()] == ThisEntry && 192 "Scope imbalance!"); 193 HT.TopLevelMap.erase(ThisEntry->getKey()); 194 } else { 195 ScopedHashTableVal<K, V, KInfo> *&KeyEntry = 196 HT.TopLevelMap[ThisEntry->getKey()]; 197 assert(KeyEntry == ThisEntry && "Scope imbalance!"); 198 KeyEntry = ThisEntry->getNextForKey(); 199 } 200 201 // Pop this value out of the scope. 202 LastValInScope = ThisEntry->getNextInScope(); 203 204 // Delete this entry. 205 delete ThisEntry; 206 } 207} 208 209} // end namespace llvm 210 211#endif
|