ScopedHashTable.h revision 4f20c6d354d4c6eba00148c2dfc9ad2dae8fd140
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 99d10e467ad961f7c3b548ee2f2de8a576a245e25aChris Lattnerprivate: 1004f20c6d354d4c6eba00148c2dfc9ad2dae8fd140Chris Lattner friend class ScopedHashTable<K, V, KInfo, AllocatorTy>; 1014f20c6d354d4c6eba00148c2dfc9ad2dae8fd140Chris Lattner ScopedHashTableVal<K, V> *getLastValInScope() { 102d5e9e5f22176fbd0d18a558901e2786106fd03f5Evan Cheng return LastValInScope; 103d5e9e5f22176fbd0d18a558901e2786106fd03f5Evan Cheng } 1044f20c6d354d4c6eba00148c2dfc9ad2dae8fd140Chris Lattner void setLastValInScope(ScopedHashTableVal<K, V> *Val) { 105d5e9e5f22176fbd0d18a558901e2786106fd03f5Evan Cheng LastValInScope = Val; 106d5e9e5f22176fbd0d18a558901e2786106fd03f5Evan Cheng } 107d10e467ad961f7c3b548ee2f2de8a576a245e25aChris Lattner}; 108d10e467ad961f7c3b548ee2f2de8a576a245e25aChris Lattner 109d10e467ad961f7c3b548ee2f2de8a576a245e25aChris Lattner 110d5e9e5f22176fbd0d18a558901e2786106fd03f5Evan Chengtemplate <typename K, typename V, typename KInfo = DenseMapInfo<K> > 111d10e467ad961f7c3b548ee2f2de8a576a245e25aChris Lattnerclass ScopedHashTableIterator { 1124f20c6d354d4c6eba00148c2dfc9ad2dae8fd140Chris Lattner ScopedHashTableVal<K, V> *Node; 113d10e467ad961f7c3b548ee2f2de8a576a245e25aChris Lattnerpublic: 1144f20c6d354d4c6eba00148c2dfc9ad2dae8fd140Chris Lattner ScopedHashTableIterator(ScopedHashTableVal<K, V> *node) : Node(node) {} 1153a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 116d10e467ad961f7c3b548ee2f2de8a576a245e25aChris Lattner V &operator*() const { 117d10e467ad961f7c3b548ee2f2de8a576a245e25aChris Lattner assert(Node && "Dereference end()"); 118d10e467ad961f7c3b548ee2f2de8a576a245e25aChris Lattner return Node->getValue(); 119d10e467ad961f7c3b548ee2f2de8a576a245e25aChris Lattner } 120d10e467ad961f7c3b548ee2f2de8a576a245e25aChris Lattner V *operator->() const { 121d10e467ad961f7c3b548ee2f2de8a576a245e25aChris Lattner return &Node->getValue(); 122d10e467ad961f7c3b548ee2f2de8a576a245e25aChris Lattner } 1233a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 124d10e467ad961f7c3b548ee2f2de8a576a245e25aChris Lattner bool operator==(const ScopedHashTableIterator &RHS) const { 125d10e467ad961f7c3b548ee2f2de8a576a245e25aChris Lattner return Node == RHS.Node; 126d10e467ad961f7c3b548ee2f2de8a576a245e25aChris Lattner } 127d10e467ad961f7c3b548ee2f2de8a576a245e25aChris Lattner bool operator!=(const ScopedHashTableIterator &RHS) const { 128d10e467ad961f7c3b548ee2f2de8a576a245e25aChris Lattner return Node != RHS.Node; 129d10e467ad961f7c3b548ee2f2de8a576a245e25aChris Lattner } 1303a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 131d10e467ad961f7c3b548ee2f2de8a576a245e25aChris Lattner inline ScopedHashTableIterator& operator++() { // Preincrement 132d10e467ad961f7c3b548ee2f2de8a576a245e25aChris Lattner assert(Node && "incrementing past end()"); 133d10e467ad961f7c3b548ee2f2de8a576a245e25aChris Lattner Node = Node->getNextForKey(); 134d10e467ad961f7c3b548ee2f2de8a576a245e25aChris Lattner return *this; 135d10e467ad961f7c3b548ee2f2de8a576a245e25aChris Lattner } 136d10e467ad961f7c3b548ee2f2de8a576a245e25aChris Lattner ScopedHashTableIterator operator++(int) { // Postincrement 137d10e467ad961f7c3b548ee2f2de8a576a245e25aChris Lattner ScopedHashTableIterator tmp = *this; ++*this; return tmp; 138d10e467ad961f7c3b548ee2f2de8a576a245e25aChris Lattner } 139d10e467ad961f7c3b548ee2f2de8a576a245e25aChris Lattner}; 140d10e467ad961f7c3b548ee2f2de8a576a245e25aChris Lattner 141d10e467ad961f7c3b548ee2f2de8a576a245e25aChris Lattner 14261a10a0dc91863b70002cc412a1277357d6a4b45Chris Lattnertemplate <typename K, typename V, typename KInfo, typename AllocatorTy> 143d10e467ad961f7c3b548ee2f2de8a576a245e25aChris Lattnerclass ScopedHashTable { 1444f20c6d354d4c6eba00148c2dfc9ad2dae8fd140Chris Lattner typedef ScopedHashTableVal<K, V> ValTy; 14561a10a0dc91863b70002cc412a1277357d6a4b45Chris Lattner DenseMap<K, ValTy*, KInfo> TopLevelMap; 1464f20c6d354d4c6eba00148c2dfc9ad2dae8fd140Chris Lattner ScopedHashTableScope<K, V, KInfo, AllocatorTy> *CurScope; 14761a10a0dc91863b70002cc412a1277357d6a4b45Chris Lattner 14861a10a0dc91863b70002cc412a1277357d6a4b45Chris Lattner AllocatorTy Allocator; 14961a10a0dc91863b70002cc412a1277357d6a4b45Chris Lattner 150d10e467ad961f7c3b548ee2f2de8a576a245e25aChris Lattner ScopedHashTable(const ScopedHashTable&); // NOT YET IMPLEMENTED 151d10e467ad961f7c3b548ee2f2de8a576a245e25aChris Lattner void operator=(const ScopedHashTable&); // NOT YET IMPLEMENTED 1524f20c6d354d4c6eba00148c2dfc9ad2dae8fd140Chris Lattner friend class ScopedHashTableScope<K, V, KInfo, AllocatorTy>; 153d10e467ad961f7c3b548ee2f2de8a576a245e25aChris Lattnerpublic: 154d10e467ad961f7c3b548ee2f2de8a576a245e25aChris Lattner ScopedHashTable() : CurScope(0) {} 15561a10a0dc91863b70002cc412a1277357d6a4b45Chris Lattner ScopedHashTable(AllocatorTy A) : CurScope(0), Allocator(A) {} 156d10e467ad961f7c3b548ee2f2de8a576a245e25aChris Lattner ~ScopedHashTable() { 157d10e467ad961f7c3b548ee2f2de8a576a245e25aChris Lattner assert(CurScope == 0 && TopLevelMap.empty() && "Scope imbalance!"); 158d10e467ad961f7c3b548ee2f2de8a576a245e25aChris Lattner } 15961a10a0dc91863b70002cc412a1277357d6a4b45Chris Lattner 16061a10a0dc91863b70002cc412a1277357d6a4b45Chris Lattner typedef typename ReferenceAdder<AllocatorTy>::result AllocatorRefTy; 16161a10a0dc91863b70002cc412a1277357d6a4b45Chris Lattner typedef typename ReferenceAdder<const AllocatorTy>::result AllocatorCRefTy; 16261a10a0dc91863b70002cc412a1277357d6a4b45Chris Lattner AllocatorRefTy getAllocator() { return Allocator; } 16361a10a0dc91863b70002cc412a1277357d6a4b45Chris Lattner AllocatorCRefTy getAllocator() const { return Allocator; } 1643a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 1657f05aa72f970bdb92c831a83b02197b8699f7635Evan Cheng bool count(const K &Key) const { 1667f05aa72f970bdb92c831a83b02197b8699f7635Evan Cheng return TopLevelMap.count(Key); 1677f05aa72f970bdb92c831a83b02197b8699f7635Evan Cheng } 1687f05aa72f970bdb92c831a83b02197b8699f7635Evan Cheng 1697f05aa72f970bdb92c831a83b02197b8699f7635Evan Cheng V lookup(const K &Key) { 17061a10a0dc91863b70002cc412a1277357d6a4b45Chris Lattner typename DenseMap<K, ValTy*, KInfo>::iterator I = TopLevelMap.find(Key); 17190f8795e1c0d43e5b3d6254ff2a3cad533069218Chris Lattner if (I != TopLevelMap.end()) 17290f8795e1c0d43e5b3d6254ff2a3cad533069218Chris Lattner return I->second->getValue(); 17390f8795e1c0d43e5b3d6254ff2a3cad533069218Chris Lattner 17490f8795e1c0d43e5b3d6254ff2a3cad533069218Chris Lattner return V(); 1757f05aa72f970bdb92c831a83b02197b8699f7635Evan Cheng } 1767f05aa72f970bdb92c831a83b02197b8699f7635Evan Cheng 177d10e467ad961f7c3b548ee2f2de8a576a245e25aChris Lattner void insert(const K &Key, const V &Val) { 178d10e467ad961f7c3b548ee2f2de8a576a245e25aChris Lattner assert(CurScope && "No scope active!"); 1793a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 1804f20c6d354d4c6eba00148c2dfc9ad2dae8fd140Chris Lattner ScopedHashTableVal<K, V> *&KeyEntry = TopLevelMap[Key]; 1813a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 18261a10a0dc91863b70002cc412a1277357d6a4b45Chris Lattner KeyEntry = ValTy::Create(CurScope->getLastValInScope(), KeyEntry, Key, Val, 18361a10a0dc91863b70002cc412a1277357d6a4b45Chris Lattner Allocator); 184d10e467ad961f7c3b548ee2f2de8a576a245e25aChris Lattner CurScope->setLastValInScope(KeyEntry); 185d10e467ad961f7c3b548ee2f2de8a576a245e25aChris Lattner } 1863a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 187d5e9e5f22176fbd0d18a558901e2786106fd03f5Evan Cheng typedef ScopedHashTableIterator<K, V, KInfo> iterator; 188d10e467ad961f7c3b548ee2f2de8a576a245e25aChris Lattner 189d10e467ad961f7c3b548ee2f2de8a576a245e25aChris Lattner iterator end() { return iterator(0); } 190d10e467ad961f7c3b548ee2f2de8a576a245e25aChris Lattner 191d10e467ad961f7c3b548ee2f2de8a576a245e25aChris Lattner iterator begin(const K &Key) { 19261a10a0dc91863b70002cc412a1277357d6a4b45Chris Lattner typename DenseMap<K, ValTy*, KInfo>::iterator I = 193d10e467ad961f7c3b548ee2f2de8a576a245e25aChris Lattner TopLevelMap.find(Key); 194d10e467ad961f7c3b548ee2f2de8a576a245e25aChris Lattner if (I == TopLevelMap.end()) return end(); 195d10e467ad961f7c3b548ee2f2de8a576a245e25aChris Lattner return iterator(I->second); 196d10e467ad961f7c3b548ee2f2de8a576a245e25aChris Lattner } 197d10e467ad961f7c3b548ee2f2de8a576a245e25aChris Lattner}; 198d10e467ad961f7c3b548ee2f2de8a576a245e25aChris Lattner 199d10e467ad961f7c3b548ee2f2de8a576a245e25aChris Lattner/// ScopedHashTableScope ctor - Install this as the current scope for the hash 200d10e467ad961f7c3b548ee2f2de8a576a245e25aChris Lattner/// table. 2014f20c6d354d4c6eba00148c2dfc9ad2dae8fd140Chris Lattnertemplate <typename K, typename V, typename KInfo, typename Allocator> 2024f20c6d354d4c6eba00148c2dfc9ad2dae8fd140Chris LattnerScopedHashTableScope<K, V, KInfo, Allocator>:: 2034f20c6d354d4c6eba00148c2dfc9ad2dae8fd140Chris Lattner ScopedHashTableScope(ScopedHashTable<K, V, KInfo, Allocator> &ht) : HT(ht) { 204d10e467ad961f7c3b548ee2f2de8a576a245e25aChris Lattner PrevScope = HT.CurScope; 205d10e467ad961f7c3b548ee2f2de8a576a245e25aChris Lattner HT.CurScope = this; 206d10e467ad961f7c3b548ee2f2de8a576a245e25aChris Lattner LastValInScope = 0; 207d10e467ad961f7c3b548ee2f2de8a576a245e25aChris Lattner} 208d10e467ad961f7c3b548ee2f2de8a576a245e25aChris Lattner 2094f20c6d354d4c6eba00148c2dfc9ad2dae8fd140Chris Lattnertemplate <typename K, typename V, typename KInfo, typename Allocator> 2104f20c6d354d4c6eba00148c2dfc9ad2dae8fd140Chris LattnerScopedHashTableScope<K, V, KInfo, Allocator>::~ScopedHashTableScope() { 211d10e467ad961f7c3b548ee2f2de8a576a245e25aChris Lattner assert(HT.CurScope == this && "Scope imbalance!"); 212d10e467ad961f7c3b548ee2f2de8a576a245e25aChris Lattner HT.CurScope = PrevScope; 2133a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 214d10e467ad961f7c3b548ee2f2de8a576a245e25aChris Lattner // Pop and delete all values corresponding to this scope. 2154f20c6d354d4c6eba00148c2dfc9ad2dae8fd140Chris Lattner while (ScopedHashTableVal<K, V> *ThisEntry = LastValInScope) { 216d10e467ad961f7c3b548ee2f2de8a576a245e25aChris Lattner // Pop this value out of the TopLevelMap. 217d10e467ad961f7c3b548ee2f2de8a576a245e25aChris Lattner if (ThisEntry->getNextForKey() == 0) { 218d10e467ad961f7c3b548ee2f2de8a576a245e25aChris Lattner assert(HT.TopLevelMap[ThisEntry->getKey()] == ThisEntry && 219d10e467ad961f7c3b548ee2f2de8a576a245e25aChris Lattner "Scope imbalance!"); 220d10e467ad961f7c3b548ee2f2de8a576a245e25aChris Lattner HT.TopLevelMap.erase(ThisEntry->getKey()); 2213a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman } else { 2224f20c6d354d4c6eba00148c2dfc9ad2dae8fd140Chris Lattner ScopedHashTableVal<K, V> *&KeyEntry = HT.TopLevelMap[ThisEntry->getKey()]; 223d10e467ad961f7c3b548ee2f2de8a576a245e25aChris Lattner assert(KeyEntry == ThisEntry && "Scope imbalance!"); 224d10e467ad961f7c3b548ee2f2de8a576a245e25aChris Lattner KeyEntry = ThisEntry->getNextForKey(); 225d10e467ad961f7c3b548ee2f2de8a576a245e25aChris Lattner } 2263a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 227d10e467ad961f7c3b548ee2f2de8a576a245e25aChris Lattner // Pop this value out of the scope. 228d10e467ad961f7c3b548ee2f2de8a576a245e25aChris Lattner LastValInScope = ThisEntry->getNextInScope(); 2293a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 230d10e467ad961f7c3b548ee2f2de8a576a245e25aChris Lattner // Delete this entry. 23161a10a0dc91863b70002cc412a1277357d6a4b45Chris Lattner ThisEntry->Destroy(HT.getAllocator()); 232d10e467ad961f7c3b548ee2f2de8a576a245e25aChris Lattner } 233d10e467ad961f7c3b548ee2f2de8a576a245e25aChris Lattner} 234d10e467ad961f7c3b548ee2f2de8a576a245e25aChris Lattner 235d10e467ad961f7c3b548ee2f2de8a576a245e25aChris Lattner} // end namespace llvm 236d10e467ad961f7c3b548ee2f2de8a576a245e25aChris Lattner 237d10e467ad961f7c3b548ee2f2de8a576a245e25aChris Lattner#endif 238