X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=include%2Fllvm%2FADT%2FScopedHashTable.h;h=a6803ee0eddf0f1ff9bcc564475822018107a76c;hb=cbeb8d9869aafec3c2c1ee0922f0a4d5bb4a916a;hp=b5ca374a7ddd46acfb5ecd9a3baa72baf53eed2a;hpb=a84f3d9a978d0cfdf0e4b5fbd1095a965a30110b;p=oota-llvm.git diff --git a/include/llvm/ADT/ScopedHashTable.h b/include/llvm/ADT/ScopedHashTable.h index b5ca374a7dd..a6803ee0edd 100644 --- a/include/llvm/ADT/ScopedHashTable.h +++ b/include/llvm/ADT/ScopedHashTable.h @@ -31,25 +31,23 @@ #ifndef LLVM_ADT_SCOPEDHASHTABLE_H #define LLVM_ADT_SCOPEDHASHTABLE_H -#include #include "llvm/ADT/DenseMap.h" +#include "llvm/Support/Allocator.h" namespace llvm { -template > +template , + typename AllocatorTy = MallocAllocator> class ScopedHashTable; -template > +template class ScopedHashTableVal { ScopedHashTableVal *NextInScope; ScopedHashTableVal *NextForKey; K Key; V Val; + ScopedHashTableVal(const K &key, const V &val) : Key(key), Val(val) {} public: - ScopedHashTableVal(ScopedHashTableVal *nextInScope, - ScopedHashTableVal *nextForKey, const K &key, const V &val) - : NextInScope(nextInScope), NextForKey(nextForKey), Key(key), Val(val) { - } const K &getKey() const { return Key; } const V &getValue() const { return Val; } @@ -57,33 +55,56 @@ public: ScopedHashTableVal *getNextForKey() { return NextForKey; } const ScopedHashTableVal *getNextForKey() const { return NextForKey; } -public: ScopedHashTableVal *getNextInScope() { return NextInScope; } + + template + static ScopedHashTableVal *Create(ScopedHashTableVal *nextInScope, + ScopedHashTableVal *nextForKey, + const K &key, const V &val, + AllocatorTy &Allocator) { + ScopedHashTableVal *New = Allocator.template Allocate(); + // Set up the value. + new (New) ScopedHashTableVal(key, val); + New->NextInScope = nextInScope; + New->NextForKey = nextForKey; + return New; + } + + template + void Destroy(AllocatorTy &Allocator) { + // Free memory referenced by the item. + this->~ScopedHashTableVal(); + Allocator.Deallocate(this); + } }; -template > +template , + typename AllocatorTy = MallocAllocator> class ScopedHashTableScope { /// HT - The hashtable that we are active for. - ScopedHashTable &HT; + ScopedHashTable &HT; /// PrevScope - This is the scope that we are shadowing in HT. ScopedHashTableScope *PrevScope; /// LastValInScope - This is the last value that was inserted for this scope /// or null if none have been inserted yet. - ScopedHashTableVal *LastValInScope; + ScopedHashTableVal *LastValInScope; void operator=(ScopedHashTableScope&); // DO NOT IMPLEMENT ScopedHashTableScope(ScopedHashTableScope&); // DO NOT IMPLEMENT public: - ScopedHashTableScope(ScopedHashTable &HT); + ScopedHashTableScope(ScopedHashTable &HT); ~ScopedHashTableScope(); + ScopedHashTableScope *getParentScope() { return PrevScope; } + const ScopedHashTableScope *getParentScope() const { return PrevScope; } + private: - friend class ScopedHashTable; - ScopedHashTableVal *getLastValInScope() { + friend class ScopedHashTable; + ScopedHashTableVal *getLastValInScope() { return LastValInScope; } - void setLastValInScope(ScopedHashTableVal *Val) { + void setLastValInScope(ScopedHashTableVal *Val) { LastValInScope = Val; } }; @@ -91,9 +112,9 @@ private: template > class ScopedHashTableIterator { - ScopedHashTableVal *Node; + ScopedHashTableVal *Node; public: - ScopedHashTableIterator(ScopedHashTableVal *node) : Node(node) {} + ScopedHashTableIterator(ScopedHashTableVal *node) : Node(node) {} V &operator*() const { assert(Node && "Dereference end()"); @@ -121,35 +142,50 @@ public: }; -template +template class ScopedHashTable { - DenseMap*, KInfo> TopLevelMap; - ScopedHashTableScope *CurScope; +public: + /// ScopeTy - This is a helpful typedef that allows clients to get easy access + /// to the name of the scope for this hash table. + typedef ScopedHashTableScope ScopeTy; +private: + typedef ScopedHashTableVal ValTy; + DenseMap TopLevelMap; + ScopeTy *CurScope; + + AllocatorTy Allocator; + ScopedHashTable(const ScopedHashTable&); // NOT YET IMPLEMENTED void operator=(const ScopedHashTable&); // NOT YET IMPLEMENTED - friend class ScopedHashTableScope; + friend class ScopedHashTableScope; public: ScopedHashTable() : CurScope(0) {} + ScopedHashTable(AllocatorTy A) : CurScope(0), Allocator(A) {} ~ScopedHashTable() { assert(CurScope == 0 && TopLevelMap.empty() && "Scope imbalance!"); } + + + /// Access to the allocator. + typedef typename ReferenceAdder::result AllocatorRefTy; + typedef typename ReferenceAdder::result AllocatorCRefTy; + AllocatorRefTy getAllocator() { return Allocator; } + AllocatorCRefTy getAllocator() const { return Allocator; } bool count(const K &Key) const { return TopLevelMap.count(Key); } V lookup(const K &Key) { - return TopLevelMap[Key]->getValue(); + typename DenseMap::iterator I = TopLevelMap.find(Key); + if (I != TopLevelMap.end()) + return I->second->getValue(); + + return V(); } void insert(const K &Key, const V &Val) { - assert(CurScope && "No scope active!"); - - ScopedHashTableVal *&KeyEntry = TopLevelMap[Key]; - - KeyEntry= new ScopedHashTableVal(CurScope->getLastValInScope(), - KeyEntry, Key, Val); - CurScope->setLastValInScope(KeyEntry); + insertIntoScope(CurScope, Key, Val); } typedef ScopedHashTableIterator iterator; @@ -157,38 +193,52 @@ public: iterator end() { return iterator(0); } iterator begin(const K &Key) { - typename DenseMap*, KInfo>::iterator I = + typename DenseMap::iterator I = TopLevelMap.find(Key); if (I == TopLevelMap.end()) return end(); return iterator(I->second); } + + ScopeTy *getCurScope() { return CurScope; } + const ScopeTy *getCurScope() const { return CurScope; } + + /// insertIntoScope - This inserts the specified key/value at the specified + /// (possibly not the current) scope. While it is ok to insert into a scope + /// that isn't the current one, it isn't ok to insert *underneath* an existing + /// value of the specified key. + void insertIntoScope(ScopeTy *S, const K &Key, const V &Val) { + assert(S && "No scope active!"); + ScopedHashTableVal *&KeyEntry = TopLevelMap[Key]; + KeyEntry = ValTy::Create(S->getLastValInScope(), KeyEntry, Key, Val, + Allocator); + S->setLastValInScope(KeyEntry); + } }; /// ScopedHashTableScope ctor - Install this as the current scope for the hash /// table. -template -ScopedHashTableScope:: - ScopedHashTableScope(ScopedHashTable &ht) : HT(ht) { +template +ScopedHashTableScope:: + ScopedHashTableScope(ScopedHashTable &ht) : HT(ht) { PrevScope = HT.CurScope; HT.CurScope = this; LastValInScope = 0; } -template -ScopedHashTableScope::~ScopedHashTableScope() { +template +ScopedHashTableScope::~ScopedHashTableScope() { assert(HT.CurScope == this && "Scope imbalance!"); HT.CurScope = PrevScope; // Pop and delete all values corresponding to this scope. - while (ScopedHashTableVal *ThisEntry = LastValInScope) { + while (ScopedHashTableVal *ThisEntry = LastValInScope) { // Pop this value out of the TopLevelMap. if (ThisEntry->getNextForKey() == 0) { assert(HT.TopLevelMap[ThisEntry->getKey()] == ThisEntry && "Scope imbalance!"); HT.TopLevelMap.erase(ThisEntry->getKey()); } else { - ScopedHashTableVal *&KeyEntry = - HT.TopLevelMap[ThisEntry->getKey()]; + ScopedHashTableVal *&KeyEntry = HT.TopLevelMap[ThisEntry->getKey()]; assert(KeyEntry == ThisEntry && "Scope imbalance!"); KeyEntry = ThisEntry->getNextForKey(); } @@ -197,7 +247,7 @@ ScopedHashTableScope::~ScopedHashTableScope() { LastValInScope = ThisEntry->getNextInScope(); // Delete this entry. - delete ThisEntry; + ThisEntry->Destroy(HT.getAllocator()); } }