1d10e467ad961f7c3b548ee2f2de8a576a245e25aChris Lattner//===- ScopedHashTable.h - A simple scoped hash table ---------------------===// 2d10e467ad961f7c3b548ee2f2de8a576a245e25aChris Lattner// 3d10e467ad961f7c3b548ee2f2de8a576a245e25aChris Lattner// The LLVM Compiler Infrastructure 4d10e467ad961f7c3b548ee2f2de8a576a245e25aChris Lattner// 5d10e467ad961f7c3b548ee2f2de8a576a245e25aChris Lattner// This file is distributed under the University of Illinois Open Source 6d10e467ad961f7c3b548ee2f2de8a576a245e25aChris Lattner// License. See LICENSE.TXT for details. 7d10e467ad961f7c3b548ee2f2de8a576a245e25aChris Lattner// 8d10e467ad961f7c3b548ee2f2de8a576a245e25aChris Lattner//===----------------------------------------------------------------------===// 9d10e467ad961f7c3b548ee2f2de8a576a245e25aChris Lattner// 10d10e467ad961f7c3b548ee2f2de8a576a245e25aChris Lattner// This file implements an efficient scoped hash table, which is useful for 11d10e467ad961f7c3b548ee2f2de8a576a245e25aChris Lattner// things like dominator-based optimizations. This allows clients to do things 12d10e467ad961f7c3b548ee2f2de8a576a245e25aChris Lattner// like this: 13d10e467ad961f7c3b548ee2f2de8a576a245e25aChris Lattner// 14d10e467ad961f7c3b548ee2f2de8a576a245e25aChris Lattner// ScopedHashTable<int, int> HT; 15d10e467ad961f7c3b548ee2f2de8a576a245e25aChris Lattner// { 16d10e467ad961f7c3b548ee2f2de8a576a245e25aChris Lattner// ScopedHashTableScope<int, int> Scope1(HT); 17d10e467ad961f7c3b548ee2f2de8a576a245e25aChris Lattner// HT.insert(0, 0); 18d10e467ad961f7c3b548ee2f2de8a576a245e25aChris Lattner// HT.insert(1, 1); 19d10e467ad961f7c3b548ee2f2de8a576a245e25aChris Lattner// { 20d10e467ad961f7c3b548ee2f2de8a576a245e25aChris Lattner// ScopedHashTableScope<int, int> Scope2(HT); 21d10e467ad961f7c3b548ee2f2de8a576a245e25aChris Lattner// HT.insert(0, 42); 22d10e467ad961f7c3b548ee2f2de8a576a245e25aChris Lattner// } 23d10e467ad961f7c3b548ee2f2de8a576a245e25aChris Lattner// } 24d10e467ad961f7c3b548ee2f2de8a576a245e25aChris Lattner// 25d10e467ad961f7c3b548ee2f2de8a576a245e25aChris Lattner// Looking up the value for "0" in the Scope2 block will return 42. Looking 26d10e467ad961f7c3b548ee2f2de8a576a245e25aChris Lattner// up the value for 0 before 42 is inserted or after Scope2 is popped will 27d10e467ad961f7c3b548ee2f2de8a576a245e25aChris Lattner// return 0. 28d10e467ad961f7c3b548ee2f2de8a576a245e25aChris Lattner// 29d10e467ad961f7c3b548ee2f2de8a576a245e25aChris Lattner//===----------------------------------------------------------------------===// 30d10e467ad961f7c3b548ee2f2de8a576a245e25aChris Lattner 31d10e467ad961f7c3b548ee2f2de8a576a245e25aChris Lattner#ifndef LLVM_ADT_SCOPEDHASHTABLE_H 32d10e467ad961f7c3b548ee2f2de8a576a245e25aChris Lattner#define LLVM_ADT_SCOPEDHASHTABLE_H 33d10e467ad961f7c3b548ee2f2de8a576a245e25aChris Lattner 34d10e467ad961f7c3b548ee2f2de8a576a245e25aChris Lattner#include "llvm/ADT/DenseMap.h" 3561a10a0dc91863b70002cc412a1277357d6a4b45Chris Lattner#include "llvm/Support/Allocator.h" 36d10e467ad961f7c3b548ee2f2de8a576a245e25aChris Lattner 37d10e467ad961f7c3b548ee2f2de8a576a245e25aChris Lattnernamespace llvm { 38d10e467ad961f7c3b548ee2f2de8a576a245e25aChris Lattner 3961a10a0dc91863b70002cc412a1277357d6a4b45Chris Lattnertemplate <typename K, typename V, typename KInfo = DenseMapInfo<K>, 4061a10a0dc91863b70002cc412a1277357d6a4b45Chris Lattner typename AllocatorTy = MallocAllocator> 41d10e467ad961f7c3b548ee2f2de8a576a245e25aChris Lattnerclass ScopedHashTable; 42d10e467ad961f7c3b548ee2f2de8a576a245e25aChris Lattner 434f20c6d354d4c6eba00148c2dfc9ad2dae8fd140Chris Lattnertemplate <typename K, typename V> 44d10e467ad961f7c3b548ee2f2de8a576a245e25aChris Lattnerclass ScopedHashTableVal { 45d10e467ad961f7c3b548ee2f2de8a576a245e25aChris Lattner ScopedHashTableVal *NextInScope; 46d10e467ad961f7c3b548ee2f2de8a576a245e25aChris Lattner ScopedHashTableVal *NextForKey; 47d10e467ad961f7c3b548ee2f2de8a576a245e25aChris Lattner K Key; 48d10e467ad961f7c3b548ee2f2de8a576a245e25aChris Lattner V Val; 4961a10a0dc91863b70002cc412a1277357d6a4b45Chris Lattner ScopedHashTableVal(const K &key, const V &val) : Key(key), Val(val) {} 50d10e467ad961f7c3b548ee2f2de8a576a245e25aChris Lattnerpublic: 513a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 52d10e467ad961f7c3b548ee2f2de8a576a245e25aChris Lattner const K &getKey() const { return Key; } 53d10e467ad961f7c3b548ee2f2de8a576a245e25aChris Lattner const V &getValue() const { return Val; } 54d10e467ad961f7c3b548ee2f2de8a576a245e25aChris Lattner V &getValue() { return Val; } 553a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 56d10e467ad961f7c3b548ee2f2de8a576a245e25aChris Lattner ScopedHashTableVal *getNextForKey() { return NextForKey; } 57d10e467ad961f7c3b548ee2f2de8a576a245e25aChris Lattner const ScopedHashTableVal *getNextForKey() const { return NextForKey; } 58d10e467ad961f7c3b548ee2f2de8a576a245e25aChris Lattner ScopedHashTableVal *getNextInScope() { return NextInScope; } 5961a10a0dc91863b70002cc412a1277357d6a4b45Chris Lattner 6061a10a0dc91863b70002cc412a1277357d6a4b45Chris Lattner template <typename AllocatorTy> 6161a10a0dc91863b70002cc412a1277357d6a4b45Chris Lattner static ScopedHashTableVal *Create(ScopedHashTableVal *nextInScope, 6261a10a0dc91863b70002cc412a1277357d6a4b45Chris Lattner ScopedHashTableVal *nextForKey, 6361a10a0dc91863b70002cc412a1277357d6a4b45Chris Lattner const K &key, const V &val, 6461a10a0dc91863b70002cc412a1277357d6a4b45Chris Lattner AllocatorTy &Allocator) { 6561a10a0dc91863b70002cc412a1277357d6a4b45Chris Lattner ScopedHashTableVal *New = Allocator.template Allocate<ScopedHashTableVal>(); 6661a10a0dc91863b70002cc412a1277357d6a4b45Chris Lattner // Set up the value. 6761a10a0dc91863b70002cc412a1277357d6a4b45Chris Lattner new (New) ScopedHashTableVal(key, val); 6861a10a0dc91863b70002cc412a1277357d6a4b45Chris Lattner New->NextInScope = nextInScope; 6961a10a0dc91863b70002cc412a1277357d6a4b45Chris Lattner New->NextForKey = nextForKey; 7061a10a0dc91863b70002cc412a1277357d6a4b45Chris Lattner return New; 7161a10a0dc91863b70002cc412a1277357d6a4b45Chris Lattner } 7261a10a0dc91863b70002cc412a1277357d6a4b45Chris Lattner 7361a10a0dc91863b70002cc412a1277357d6a4b45Chris Lattner template <typename AllocatorTy> 7461a10a0dc91863b70002cc412a1277357d6a4b45Chris Lattner void Destroy(AllocatorTy &Allocator) { 7561a10a0dc91863b70002cc412a1277357d6a4b45Chris Lattner // Free memory referenced by the item. 7661a10a0dc91863b70002cc412a1277357d6a4b45Chris Lattner this->~ScopedHashTableVal(); 7761a10a0dc91863b70002cc412a1277357d6a4b45Chris Lattner Allocator.Deallocate(this); 7861a10a0dc91863b70002cc412a1277357d6a4b45Chris Lattner } 79d10e467ad961f7c3b548ee2f2de8a576a245e25aChris Lattner}; 80d10e467ad961f7c3b548ee2f2de8a576a245e25aChris Lattner 814f20c6d354d4c6eba00148c2dfc9ad2dae8fd140Chris Lattnertemplate <typename K, typename V, typename KInfo = DenseMapInfo<K>, 824f20c6d354d4c6eba00148c2dfc9ad2dae8fd140Chris Lattner typename AllocatorTy = MallocAllocator> 83d10e467ad961f7c3b548ee2f2de8a576a245e25aChris Lattnerclass ScopedHashTableScope { 84d10e467ad961f7c3b548ee2f2de8a576a245e25aChris Lattner /// HT - The hashtable that we are active for. 854f20c6d354d4c6eba00148c2dfc9ad2dae8fd140Chris Lattner ScopedHashTable<K, V, KInfo, AllocatorTy> &HT; 863a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 87d10e467ad961f7c3b548ee2f2de8a576a245e25aChris Lattner /// PrevScope - This is the scope that we are shadowing in HT. 88d10e467ad961f7c3b548ee2f2de8a576a245e25aChris Lattner ScopedHashTableScope *PrevScope; 89d10e467ad961f7c3b548ee2f2de8a576a245e25aChris Lattner 90d10e467ad961f7c3b548ee2f2de8a576a245e25aChris Lattner /// LastValInScope - This is the last value that was inserted for this scope 91d10e467ad961f7c3b548ee2f2de8a576a245e25aChris Lattner /// or null if none have been inserted yet. 924f20c6d354d4c6eba00148c2dfc9ad2dae8fd140Chris Lattner ScopedHashTableVal<K, V> *LastValInScope; 93d10e467ad961f7c3b548ee2f2de8a576a245e25aChris Lattner void operator=(ScopedHashTableScope&); // DO NOT IMPLEMENT 94d10e467ad961f7c3b548ee2f2de8a576a245e25aChris Lattner ScopedHashTableScope(ScopedHashTableScope&); // DO NOT IMPLEMENT 95d10e467ad961f7c3b548ee2f2de8a576a245e25aChris Lattnerpublic: 964f20c6d354d4c6eba00148c2dfc9ad2dae8fd140Chris Lattner ScopedHashTableScope(ScopedHashTable<K, V, KInfo, AllocatorTy> &HT); 97d10e467ad961f7c3b548ee2f2de8a576a245e25aChris Lattner ~ScopedHashTableScope(); 983a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 99cdac46d18e8bf1850b435960ccc29fb8743d9b05Chris Lattner ScopedHashTableScope *getParentScope() { return PrevScope; } 100cdac46d18e8bf1850b435960ccc29fb8743d9b05Chris Lattner const ScopedHashTableScope *getParentScope() const { return PrevScope; } 101cdac46d18e8bf1850b435960ccc29fb8743d9b05Chris Lattner 102d10e467ad961f7c3b548ee2f2de8a576a245e25aChris Lattnerprivate: 1034f20c6d354d4c6eba00148c2dfc9ad2dae8fd140Chris Lattner friend class ScopedHashTable<K, V, KInfo, AllocatorTy>; 1044f20c6d354d4c6eba00148c2dfc9ad2dae8fd140Chris Lattner ScopedHashTableVal<K, V> *getLastValInScope() { 105d5e9e5f22176fbd0d18a558901e2786106fd03f5Evan Cheng return LastValInScope; 106d5e9e5f22176fbd0d18a558901e2786106fd03f5Evan Cheng } 1074f20c6d354d4c6eba00148c2dfc9ad2dae8fd140Chris Lattner void setLastValInScope(ScopedHashTableVal<K, V> *Val) { 108d5e9e5f22176fbd0d18a558901e2786106fd03f5Evan Cheng LastValInScope = Val; 109d5e9e5f22176fbd0d18a558901e2786106fd03f5Evan Cheng } 110d10e467ad961f7c3b548ee2f2de8a576a245e25aChris Lattner}; 111d10e467ad961f7c3b548ee2f2de8a576a245e25aChris Lattner 112d10e467ad961f7c3b548ee2f2de8a576a245e25aChris Lattner 113d5e9e5f22176fbd0d18a558901e2786106fd03f5Evan Chengtemplate <typename K, typename V, typename KInfo = DenseMapInfo<K> > 114d10e467ad961f7c3b548ee2f2de8a576a245e25aChris Lattnerclass ScopedHashTableIterator { 1154f20c6d354d4c6eba00148c2dfc9ad2dae8fd140Chris Lattner ScopedHashTableVal<K, V> *Node; 116d10e467ad961f7c3b548ee2f2de8a576a245e25aChris Lattnerpublic: 1174f20c6d354d4c6eba00148c2dfc9ad2dae8fd140Chris Lattner ScopedHashTableIterator(ScopedHashTableVal<K, V> *node) : Node(node) {} 1183a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 119d10e467ad961f7c3b548ee2f2de8a576a245e25aChris Lattner V &operator*() const { 120d10e467ad961f7c3b548ee2f2de8a576a245e25aChris Lattner assert(Node && "Dereference end()"); 121d10e467ad961f7c3b548ee2f2de8a576a245e25aChris Lattner return Node->getValue(); 122d10e467ad961f7c3b548ee2f2de8a576a245e25aChris Lattner } 123d10e467ad961f7c3b548ee2f2de8a576a245e25aChris Lattner V *operator->() const { 124d10e467ad961f7c3b548ee2f2de8a576a245e25aChris Lattner return &Node->getValue(); 125d10e467ad961f7c3b548ee2f2de8a576a245e25aChris Lattner } 1263a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 127d10e467ad961f7c3b548ee2f2de8a576a245e25aChris Lattner bool operator==(const ScopedHashTableIterator &RHS) const { 128d10e467ad961f7c3b548ee2f2de8a576a245e25aChris Lattner return Node == RHS.Node; 129d10e467ad961f7c3b548ee2f2de8a576a245e25aChris Lattner } 130d10e467ad961f7c3b548ee2f2de8a576a245e25aChris Lattner bool operator!=(const ScopedHashTableIterator &RHS) const { 131d10e467ad961f7c3b548ee2f2de8a576a245e25aChris Lattner return Node != RHS.Node; 132d10e467ad961f7c3b548ee2f2de8a576a245e25aChris Lattner } 1333a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 134d10e467ad961f7c3b548ee2f2de8a576a245e25aChris Lattner inline ScopedHashTableIterator& operator++() { // Preincrement 135d10e467ad961f7c3b548ee2f2de8a576a245e25aChris Lattner assert(Node && "incrementing past end()"); 136d10e467ad961f7c3b548ee2f2de8a576a245e25aChris Lattner Node = Node->getNextForKey(); 137d10e467ad961f7c3b548ee2f2de8a576a245e25aChris Lattner return *this; 138d10e467ad961f7c3b548ee2f2de8a576a245e25aChris Lattner } 139d10e467ad961f7c3b548ee2f2de8a576a245e25aChris Lattner ScopedHashTableIterator operator++(int) { // Postincrement 140d10e467ad961f7c3b548ee2f2de8a576a245e25aChris Lattner ScopedHashTableIterator tmp = *this; ++*this; return tmp; 141d10e467ad961f7c3b548ee2f2de8a576a245e25aChris Lattner } 142d10e467ad961f7c3b548ee2f2de8a576a245e25aChris Lattner}; 143d10e467ad961f7c3b548ee2f2de8a576a245e25aChris Lattner 144d10e467ad961f7c3b548ee2f2de8a576a245e25aChris Lattner 14561a10a0dc91863b70002cc412a1277357d6a4b45Chris Lattnertemplate <typename K, typename V, typename KInfo, typename AllocatorTy> 146d10e467ad961f7c3b548ee2f2de8a576a245e25aChris Lattnerclass ScopedHashTable { 147cdac46d18e8bf1850b435960ccc29fb8743d9b05Chris Lattnerpublic: 148cdac46d18e8bf1850b435960ccc29fb8743d9b05Chris Lattner /// ScopeTy - This is a helpful typedef that allows clients to get easy access 149cdac46d18e8bf1850b435960ccc29fb8743d9b05Chris Lattner /// to the name of the scope for this hash table. 150cdac46d18e8bf1850b435960ccc29fb8743d9b05Chris Lattner typedef ScopedHashTableScope<K, V, KInfo, AllocatorTy> ScopeTy; 151cdac46d18e8bf1850b435960ccc29fb8743d9b05Chris Lattnerprivate: 1524f20c6d354d4c6eba00148c2dfc9ad2dae8fd140Chris Lattner typedef ScopedHashTableVal<K, V> ValTy; 15361a10a0dc91863b70002cc412a1277357d6a4b45Chris Lattner DenseMap<K, ValTy*, KInfo> TopLevelMap; 154cdac46d18e8bf1850b435960ccc29fb8743d9b05Chris Lattner ScopeTy *CurScope; 15561a10a0dc91863b70002cc412a1277357d6a4b45Chris Lattner 15661a10a0dc91863b70002cc412a1277357d6a4b45Chris Lattner AllocatorTy Allocator; 15761a10a0dc91863b70002cc412a1277357d6a4b45Chris Lattner 158d10e467ad961f7c3b548ee2f2de8a576a245e25aChris Lattner ScopedHashTable(const ScopedHashTable&); // NOT YET IMPLEMENTED 159d10e467ad961f7c3b548ee2f2de8a576a245e25aChris Lattner void operator=(const ScopedHashTable&); // NOT YET IMPLEMENTED 1604f20c6d354d4c6eba00148c2dfc9ad2dae8fd140Chris Lattner friend class ScopedHashTableScope<K, V, KInfo, AllocatorTy>; 161d10e467ad961f7c3b548ee2f2de8a576a245e25aChris Lattnerpublic: 162d10e467ad961f7c3b548ee2f2de8a576a245e25aChris Lattner ScopedHashTable() : CurScope(0) {} 16361a10a0dc91863b70002cc412a1277357d6a4b45Chris Lattner ScopedHashTable(AllocatorTy A) : CurScope(0), Allocator(A) {} 164d10e467ad961f7c3b548ee2f2de8a576a245e25aChris Lattner ~ScopedHashTable() { 165d10e467ad961f7c3b548ee2f2de8a576a245e25aChris Lattner assert(CurScope == 0 && TopLevelMap.empty() && "Scope imbalance!"); 166d10e467ad961f7c3b548ee2f2de8a576a245e25aChris Lattner } 16761a10a0dc91863b70002cc412a1277357d6a4b45Chris Lattner 168152096275ad45bb13d5652f7019f48be5ccd67f8Chris Lattner 169152096275ad45bb13d5652f7019f48be5ccd67f8Chris Lattner /// Access to the allocator. 17061a10a0dc91863b70002cc412a1277357d6a4b45Chris Lattner typedef typename ReferenceAdder<AllocatorTy>::result AllocatorRefTy; 17161a10a0dc91863b70002cc412a1277357d6a4b45Chris Lattner typedef typename ReferenceAdder<const AllocatorTy>::result AllocatorCRefTy; 17261a10a0dc91863b70002cc412a1277357d6a4b45Chris Lattner AllocatorRefTy getAllocator() { return Allocator; } 17361a10a0dc91863b70002cc412a1277357d6a4b45Chris Lattner AllocatorCRefTy getAllocator() const { return Allocator; } 1743a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 1757f05aa72f970bdb92c831a83b02197b8699f7635Evan Cheng bool count(const K &Key) const { 1767f05aa72f970bdb92c831a83b02197b8699f7635Evan Cheng return TopLevelMap.count(Key); 1777f05aa72f970bdb92c831a83b02197b8699f7635Evan Cheng } 1787f05aa72f970bdb92c831a83b02197b8699f7635Evan Cheng 1797f05aa72f970bdb92c831a83b02197b8699f7635Evan Cheng V lookup(const K &Key) { 18061a10a0dc91863b70002cc412a1277357d6a4b45Chris Lattner typename DenseMap<K, ValTy*, KInfo>::iterator I = TopLevelMap.find(Key); 18190f8795e1c0d43e5b3d6254ff2a3cad533069218Chris Lattner if (I != TopLevelMap.end()) 18290f8795e1c0d43e5b3d6254ff2a3cad533069218Chris Lattner return I->second->getValue(); 18390f8795e1c0d43e5b3d6254ff2a3cad533069218Chris Lattner 18490f8795e1c0d43e5b3d6254ff2a3cad533069218Chris Lattner return V(); 1857f05aa72f970bdb92c831a83b02197b8699f7635Evan Cheng } 1867f05aa72f970bdb92c831a83b02197b8699f7635Evan Cheng 187d10e467ad961f7c3b548ee2f2de8a576a245e25aChris Lattner void insert(const K &Key, const V &Val) { 188cdac46d18e8bf1850b435960ccc29fb8743d9b05Chris Lattner insertIntoScope(CurScope, Key, Val); 189d10e467ad961f7c3b548ee2f2de8a576a245e25aChris Lattner } 1903a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 191d5e9e5f22176fbd0d18a558901e2786106fd03f5Evan Cheng typedef ScopedHashTableIterator<K, V, KInfo> iterator; 192d10e467ad961f7c3b548ee2f2de8a576a245e25aChris Lattner 193d10e467ad961f7c3b548ee2f2de8a576a245e25aChris Lattner iterator end() { return iterator(0); } 194d10e467ad961f7c3b548ee2f2de8a576a245e25aChris Lattner 195d10e467ad961f7c3b548ee2f2de8a576a245e25aChris Lattner iterator begin(const K &Key) { 19661a10a0dc91863b70002cc412a1277357d6a4b45Chris Lattner typename DenseMap<K, ValTy*, KInfo>::iterator I = 197d10e467ad961f7c3b548ee2f2de8a576a245e25aChris Lattner TopLevelMap.find(Key); 198d10e467ad961f7c3b548ee2f2de8a576a245e25aChris Lattner if (I == TopLevelMap.end()) return end(); 199d10e467ad961f7c3b548ee2f2de8a576a245e25aChris Lattner return iterator(I->second); 200d10e467ad961f7c3b548ee2f2de8a576a245e25aChris Lattner } 201cdac46d18e8bf1850b435960ccc29fb8743d9b05Chris Lattner 202cdac46d18e8bf1850b435960ccc29fb8743d9b05Chris Lattner ScopeTy *getCurScope() { return CurScope; } 203cdac46d18e8bf1850b435960ccc29fb8743d9b05Chris Lattner const ScopeTy *getCurScope() const { return CurScope; } 204cdac46d18e8bf1850b435960ccc29fb8743d9b05Chris Lattner 205cdac46d18e8bf1850b435960ccc29fb8743d9b05Chris Lattner /// insertIntoScope - This inserts the specified key/value at the specified 206cdac46d18e8bf1850b435960ccc29fb8743d9b05Chris Lattner /// (possibly not the current) scope. While it is ok to insert into a scope 207cdac46d18e8bf1850b435960ccc29fb8743d9b05Chris Lattner /// that isn't the current one, it isn't ok to insert *underneath* an existing 208cdac46d18e8bf1850b435960ccc29fb8743d9b05Chris Lattner /// value of the specified key. 209cdac46d18e8bf1850b435960ccc29fb8743d9b05Chris Lattner void insertIntoScope(ScopeTy *S, const K &Key, const V &Val) { 210cdac46d18e8bf1850b435960ccc29fb8743d9b05Chris Lattner assert(S && "No scope active!"); 211cdac46d18e8bf1850b435960ccc29fb8743d9b05Chris Lattner ScopedHashTableVal<K, V> *&KeyEntry = TopLevelMap[Key]; 212cdac46d18e8bf1850b435960ccc29fb8743d9b05Chris Lattner KeyEntry = ValTy::Create(S->getLastValInScope(), KeyEntry, Key, Val, 213cdac46d18e8bf1850b435960ccc29fb8743d9b05Chris Lattner Allocator); 214cdac46d18e8bf1850b435960ccc29fb8743d9b05Chris Lattner S->setLastValInScope(KeyEntry); 215cdac46d18e8bf1850b435960ccc29fb8743d9b05Chris Lattner } 216d10e467ad961f7c3b548ee2f2de8a576a245e25aChris Lattner}; 217d10e467ad961f7c3b548ee2f2de8a576a245e25aChris Lattner 218d10e467ad961f7c3b548ee2f2de8a576a245e25aChris Lattner/// ScopedHashTableScope ctor - Install this as the current scope for the hash 219d10e467ad961f7c3b548ee2f2de8a576a245e25aChris Lattner/// table. 2204f20c6d354d4c6eba00148c2dfc9ad2dae8fd140Chris Lattnertemplate <typename K, typename V, typename KInfo, typename Allocator> 2214f20c6d354d4c6eba00148c2dfc9ad2dae8fd140Chris LattnerScopedHashTableScope<K, V, KInfo, Allocator>:: 2224f20c6d354d4c6eba00148c2dfc9ad2dae8fd140Chris Lattner ScopedHashTableScope(ScopedHashTable<K, V, KInfo, Allocator> &ht) : HT(ht) { 223d10e467ad961f7c3b548ee2f2de8a576a245e25aChris Lattner PrevScope = HT.CurScope; 224d10e467ad961f7c3b548ee2f2de8a576a245e25aChris Lattner HT.CurScope = this; 225d10e467ad961f7c3b548ee2f2de8a576a245e25aChris Lattner LastValInScope = 0; 226d10e467ad961f7c3b548ee2f2de8a576a245e25aChris Lattner} 227d10e467ad961f7c3b548ee2f2de8a576a245e25aChris Lattner 2284f20c6d354d4c6eba00148c2dfc9ad2dae8fd140Chris Lattnertemplate <typename K, typename V, typename KInfo, typename Allocator> 2294f20c6d354d4c6eba00148c2dfc9ad2dae8fd140Chris LattnerScopedHashTableScope<K, V, KInfo, Allocator>::~ScopedHashTableScope() { 230d10e467ad961f7c3b548ee2f2de8a576a245e25aChris Lattner assert(HT.CurScope == this && "Scope imbalance!"); 231d10e467ad961f7c3b548ee2f2de8a576a245e25aChris Lattner HT.CurScope = PrevScope; 2323a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 233d10e467ad961f7c3b548ee2f2de8a576a245e25aChris Lattner // Pop and delete all values corresponding to this scope. 2344f20c6d354d4c6eba00148c2dfc9ad2dae8fd140Chris Lattner while (ScopedHashTableVal<K, V> *ThisEntry = LastValInScope) { 235d10e467ad961f7c3b548ee2f2de8a576a245e25aChris Lattner // Pop this value out of the TopLevelMap. 236d10e467ad961f7c3b548ee2f2de8a576a245e25aChris Lattner if (ThisEntry->getNextForKey() == 0) { 237d10e467ad961f7c3b548ee2f2de8a576a245e25aChris Lattner assert(HT.TopLevelMap[ThisEntry->getKey()] == ThisEntry && 238d10e467ad961f7c3b548ee2f2de8a576a245e25aChris Lattner "Scope imbalance!"); 239d10e467ad961f7c3b548ee2f2de8a576a245e25aChris Lattner HT.TopLevelMap.erase(ThisEntry->getKey()); 2403a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman } else { 2414f20c6d354d4c6eba00148c2dfc9ad2dae8fd140Chris Lattner ScopedHashTableVal<K, V> *&KeyEntry = HT.TopLevelMap[ThisEntry->getKey()]; 242d10e467ad961f7c3b548ee2f2de8a576a245e25aChris Lattner assert(KeyEntry == ThisEntry && "Scope imbalance!"); 243d10e467ad961f7c3b548ee2f2de8a576a245e25aChris Lattner KeyEntry = ThisEntry->getNextForKey(); 244d10e467ad961f7c3b548ee2f2de8a576a245e25aChris Lattner } 2453a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 246d10e467ad961f7c3b548ee2f2de8a576a245e25aChris Lattner // Pop this value out of the scope. 247d10e467ad961f7c3b548ee2f2de8a576a245e25aChris Lattner LastValInScope = ThisEntry->getNextInScope(); 2483a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 249d10e467ad961f7c3b548ee2f2de8a576a245e25aChris Lattner // Delete this entry. 25061a10a0dc91863b70002cc412a1277357d6a4b45Chris Lattner ThisEntry->Destroy(HT.getAllocator()); 251d10e467ad961f7c3b548ee2f2de8a576a245e25aChris Lattner } 252d10e467ad961f7c3b548ee2f2de8a576a245e25aChris Lattner} 253d10e467ad961f7c3b548ee2f2de8a576a245e25aChris Lattner 254d10e467ad961f7c3b548ee2f2de8a576a245e25aChris Lattner} // end namespace llvm 255d10e467ad961f7c3b548ee2f2de8a576a245e25aChris Lattner 256d10e467ad961f7c3b548ee2f2de8a576a245e25aChris Lattner#endif 257