1193323Sed//===- ScopedHashTable.h - A simple scoped hash table ---------------------===// 2193323Sed// 3193323Sed// The LLVM Compiler Infrastructure 4193323Sed// 5193323Sed// This file is distributed under the University of Illinois Open Source 6193323Sed// License. See LICENSE.TXT for details. 7193323Sed// 8193323Sed//===----------------------------------------------------------------------===// 9193323Sed// 10193323Sed// This file implements an efficient scoped hash table, which is useful for 11193323Sed// things like dominator-based optimizations. This allows clients to do things 12193323Sed// like this: 13193323Sed// 14193323Sed// ScopedHashTable<int, int> HT; 15193323Sed// { 16193323Sed// ScopedHashTableScope<int, int> Scope1(HT); 17193323Sed// HT.insert(0, 0); 18193323Sed// HT.insert(1, 1); 19193323Sed// { 20193323Sed// ScopedHashTableScope<int, int> Scope2(HT); 21193323Sed// HT.insert(0, 42); 22193323Sed// } 23193323Sed// } 24193323Sed// 25193323Sed// Looking up the value for "0" in the Scope2 block will return 42. Looking 26193323Sed// up the value for 0 before 42 is inserted or after Scope2 is popped will 27193323Sed// return 0. 28193323Sed// 29193323Sed//===----------------------------------------------------------------------===// 30193323Sed 31193323Sed#ifndef LLVM_ADT_SCOPEDHASHTABLE_H 32193323Sed#define LLVM_ADT_SCOPEDHASHTABLE_H 33193323Sed 34193323Sed#include "llvm/ADT/DenseMap.h" 35218893Sdim#include "llvm/Support/Allocator.h" 36193323Sed 37193323Sednamespace llvm { 38193323Sed 39218893Sdimtemplate <typename K, typename V, typename KInfo = DenseMapInfo<K>, 40218893Sdim typename AllocatorTy = MallocAllocator> 41193323Sedclass ScopedHashTable; 42193323Sed 43218893Sdimtemplate <typename K, typename V> 44193323Sedclass ScopedHashTableVal { 45193323Sed ScopedHashTableVal *NextInScope; 46193323Sed ScopedHashTableVal *NextForKey; 47193323Sed K Key; 48193323Sed V Val; 49218893Sdim ScopedHashTableVal(const K &key, const V &val) : Key(key), Val(val) {} 50193323Sedpublic: 51193323Sed 52193323Sed const K &getKey() const { return Key; } 53193323Sed const V &getValue() const { return Val; } 54193323Sed V &getValue() { return Val; } 55193323Sed 56193323Sed ScopedHashTableVal *getNextForKey() { return NextForKey; } 57193323Sed const ScopedHashTableVal *getNextForKey() const { return NextForKey; } 58193323Sed ScopedHashTableVal *getNextInScope() { return NextInScope; } 59218893Sdim 60218893Sdim template <typename AllocatorTy> 61218893Sdim static ScopedHashTableVal *Create(ScopedHashTableVal *nextInScope, 62218893Sdim ScopedHashTableVal *nextForKey, 63218893Sdim const K &key, const V &val, 64218893Sdim AllocatorTy &Allocator) { 65218893Sdim ScopedHashTableVal *New = Allocator.template Allocate<ScopedHashTableVal>(); 66218893Sdim // Set up the value. 67218893Sdim new (New) ScopedHashTableVal(key, val); 68218893Sdim New->NextInScope = nextInScope; 69218893Sdim New->NextForKey = nextForKey; 70218893Sdim return New; 71218893Sdim } 72218893Sdim 73218893Sdim template <typename AllocatorTy> 74218893Sdim void Destroy(AllocatorTy &Allocator) { 75218893Sdim // Free memory referenced by the item. 76218893Sdim this->~ScopedHashTableVal(); 77218893Sdim Allocator.Deallocate(this); 78218893Sdim } 79193323Sed}; 80193323Sed 81218893Sdimtemplate <typename K, typename V, typename KInfo = DenseMapInfo<K>, 82218893Sdim typename AllocatorTy = MallocAllocator> 83193323Sedclass ScopedHashTableScope { 84193323Sed /// HT - The hashtable that we are active for. 85218893Sdim ScopedHashTable<K, V, KInfo, AllocatorTy> &HT; 86193323Sed 87193323Sed /// PrevScope - This is the scope that we are shadowing in HT. 88193323Sed ScopedHashTableScope *PrevScope; 89193323Sed 90193323Sed /// LastValInScope - This is the last value that was inserted for this scope 91193323Sed /// or null if none have been inserted yet. 92218893Sdim ScopedHashTableVal<K, V> *LastValInScope; 93243830Sdim void operator=(ScopedHashTableScope&) LLVM_DELETED_FUNCTION; 94243830Sdim ScopedHashTableScope(ScopedHashTableScope&) LLVM_DELETED_FUNCTION; 95193323Sedpublic: 96218893Sdim ScopedHashTableScope(ScopedHashTable<K, V, KInfo, AllocatorTy> &HT); 97193323Sed ~ScopedHashTableScope(); 98193323Sed 99221345Sdim ScopedHashTableScope *getParentScope() { return PrevScope; } 100221345Sdim const ScopedHashTableScope *getParentScope() const { return PrevScope; } 101221345Sdim 102193323Sedprivate: 103218893Sdim friend class ScopedHashTable<K, V, KInfo, AllocatorTy>; 104218893Sdim ScopedHashTableVal<K, V> *getLastValInScope() { 105204642Srdivacky return LastValInScope; 106204642Srdivacky } 107218893Sdim void setLastValInScope(ScopedHashTableVal<K, V> *Val) { 108204642Srdivacky LastValInScope = Val; 109204642Srdivacky } 110193323Sed}; 111193323Sed 112193323Sed 113204642Srdivackytemplate <typename K, typename V, typename KInfo = DenseMapInfo<K> > 114193323Sedclass ScopedHashTableIterator { 115218893Sdim ScopedHashTableVal<K, V> *Node; 116193323Sedpublic: 117218893Sdim ScopedHashTableIterator(ScopedHashTableVal<K, V> *node) : Node(node) {} 118193323Sed 119193323Sed V &operator*() const { 120193323Sed assert(Node && "Dereference end()"); 121193323Sed return Node->getValue(); 122193323Sed } 123193323Sed V *operator->() const { 124193323Sed return &Node->getValue(); 125193323Sed } 126193323Sed 127193323Sed bool operator==(const ScopedHashTableIterator &RHS) const { 128193323Sed return Node == RHS.Node; 129193323Sed } 130193323Sed bool operator!=(const ScopedHashTableIterator &RHS) const { 131193323Sed return Node != RHS.Node; 132193323Sed } 133193323Sed 134193323Sed inline ScopedHashTableIterator& operator++() { // Preincrement 135193323Sed assert(Node && "incrementing past end()"); 136193323Sed Node = Node->getNextForKey(); 137193323Sed return *this; 138193323Sed } 139193323Sed ScopedHashTableIterator operator++(int) { // Postincrement 140193323Sed ScopedHashTableIterator tmp = *this; ++*this; return tmp; 141193323Sed } 142193323Sed}; 143193323Sed 144193323Sed 145218893Sdimtemplate <typename K, typename V, typename KInfo, typename AllocatorTy> 146193323Sedclass ScopedHashTable { 147221345Sdimpublic: 148221345Sdim /// ScopeTy - This is a helpful typedef that allows clients to get easy access 149221345Sdim /// to the name of the scope for this hash table. 150221345Sdim typedef ScopedHashTableScope<K, V, KInfo, AllocatorTy> ScopeTy; 151221345Sdimprivate: 152218893Sdim typedef ScopedHashTableVal<K, V> ValTy; 153218893Sdim DenseMap<K, ValTy*, KInfo> TopLevelMap; 154221345Sdim ScopeTy *CurScope; 155218893Sdim 156218893Sdim AllocatorTy Allocator; 157218893Sdim 158193323Sed ScopedHashTable(const ScopedHashTable&); // NOT YET IMPLEMENTED 159193323Sed void operator=(const ScopedHashTable&); // NOT YET IMPLEMENTED 160218893Sdim friend class ScopedHashTableScope<K, V, KInfo, AllocatorTy>; 161193323Sedpublic: 162193323Sed ScopedHashTable() : CurScope(0) {} 163218893Sdim ScopedHashTable(AllocatorTy A) : CurScope(0), Allocator(A) {} 164193323Sed ~ScopedHashTable() { 165193323Sed assert(CurScope == 0 && TopLevelMap.empty() && "Scope imbalance!"); 166193323Sed } 167218893Sdim 168193323Sed 169218893Sdim /// Access to the allocator. 170218893Sdim typedef typename ReferenceAdder<AllocatorTy>::result AllocatorRefTy; 171218893Sdim typedef typename ReferenceAdder<const AllocatorTy>::result AllocatorCRefTy; 172218893Sdim AllocatorRefTy getAllocator() { return Allocator; } 173218893Sdim AllocatorCRefTy getAllocator() const { return Allocator; } 174218893Sdim 175204642Srdivacky bool count(const K &Key) const { 176204642Srdivacky return TopLevelMap.count(Key); 177204642Srdivacky } 178204642Srdivacky 179204642Srdivacky V lookup(const K &Key) { 180218893Sdim typename DenseMap<K, ValTy*, KInfo>::iterator I = TopLevelMap.find(Key); 181212904Sdim if (I != TopLevelMap.end()) 182212904Sdim return I->second->getValue(); 183212904Sdim 184212904Sdim return V(); 185204642Srdivacky } 186204642Srdivacky 187193323Sed void insert(const K &Key, const V &Val) { 188221345Sdim insertIntoScope(CurScope, Key, Val); 189193323Sed } 190193323Sed 191204642Srdivacky typedef ScopedHashTableIterator<K, V, KInfo> iterator; 192193323Sed 193193323Sed iterator end() { return iterator(0); } 194193323Sed 195193323Sed iterator begin(const K &Key) { 196218893Sdim typename DenseMap<K, ValTy*, KInfo>::iterator I = 197193323Sed TopLevelMap.find(Key); 198193323Sed if (I == TopLevelMap.end()) return end(); 199193323Sed return iterator(I->second); 200193323Sed } 201221345Sdim 202221345Sdim ScopeTy *getCurScope() { return CurScope; } 203221345Sdim const ScopeTy *getCurScope() const { return CurScope; } 204221345Sdim 205221345Sdim /// insertIntoScope - This inserts the specified key/value at the specified 206221345Sdim /// (possibly not the current) scope. While it is ok to insert into a scope 207221345Sdim /// that isn't the current one, it isn't ok to insert *underneath* an existing 208221345Sdim /// value of the specified key. 209221345Sdim void insertIntoScope(ScopeTy *S, const K &Key, const V &Val) { 210221345Sdim assert(S && "No scope active!"); 211221345Sdim ScopedHashTableVal<K, V> *&KeyEntry = TopLevelMap[Key]; 212221345Sdim KeyEntry = ValTy::Create(S->getLastValInScope(), KeyEntry, Key, Val, 213221345Sdim Allocator); 214221345Sdim S->setLastValInScope(KeyEntry); 215221345Sdim } 216193323Sed}; 217193323Sed 218193323Sed/// ScopedHashTableScope ctor - Install this as the current scope for the hash 219193323Sed/// table. 220218893Sdimtemplate <typename K, typename V, typename KInfo, typename Allocator> 221218893SdimScopedHashTableScope<K, V, KInfo, Allocator>:: 222218893Sdim ScopedHashTableScope(ScopedHashTable<K, V, KInfo, Allocator> &ht) : HT(ht) { 223193323Sed PrevScope = HT.CurScope; 224193323Sed HT.CurScope = this; 225193323Sed LastValInScope = 0; 226193323Sed} 227193323Sed 228218893Sdimtemplate <typename K, typename V, typename KInfo, typename Allocator> 229218893SdimScopedHashTableScope<K, V, KInfo, Allocator>::~ScopedHashTableScope() { 230193323Sed assert(HT.CurScope == this && "Scope imbalance!"); 231193323Sed HT.CurScope = PrevScope; 232193323Sed 233193323Sed // Pop and delete all values corresponding to this scope. 234218893Sdim while (ScopedHashTableVal<K, V> *ThisEntry = LastValInScope) { 235193323Sed // Pop this value out of the TopLevelMap. 236193323Sed if (ThisEntry->getNextForKey() == 0) { 237193323Sed assert(HT.TopLevelMap[ThisEntry->getKey()] == ThisEntry && 238193323Sed "Scope imbalance!"); 239193323Sed HT.TopLevelMap.erase(ThisEntry->getKey()); 240193323Sed } else { 241218893Sdim ScopedHashTableVal<K, V> *&KeyEntry = HT.TopLevelMap[ThisEntry->getKey()]; 242193323Sed assert(KeyEntry == ThisEntry && "Scope imbalance!"); 243193323Sed KeyEntry = ThisEntry->getNextForKey(); 244193323Sed } 245193323Sed 246193323Sed // Pop this value out of the scope. 247193323Sed LastValInScope = ThisEntry->getNextInScope(); 248193323Sed 249193323Sed // Delete this entry. 250218893Sdim ThisEntry->Destroy(HT.getAllocator()); 251193323Sed } 252193323Sed} 253193323Sed 254193323Sed} // end namespace llvm 255193323Sed 256193323Sed#endif 257