X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=include%2Fllvm%2FADT%2FImmutableSet.h;h=0982657ccf1cdb91988f9559e2b1a08029753bd7;hb=b02ed5b8eafd11500bbefb7206ecbf5bc3fc324a;hp=d597a7c9be72c5734b79b2219af4faf567c43c80;hpb=4f101db8852ba60d8d9545f7e0b5ad8a7b18c8b1;p=oota-llvm.git diff --git a/include/llvm/ADT/ImmutableSet.h b/include/llvm/ADT/ImmutableSet.h index d597a7c9be7..0982657ccf1 100644 --- a/include/llvm/ADT/ImmutableSet.h +++ b/include/llvm/ADT/ImmutableSet.h @@ -14,14 +14,14 @@ #ifndef LLVM_ADT_IMSET_H #define LLVM_ADT_IMSET_H -#include "llvm/Support/Allocator.h" #include "llvm/ADT/DenseMap.h" #include "llvm/ADT/FoldingSet.h" +#include "llvm/Support/Allocator.h" #include "llvm/Support/DataTypes.h" +#include "llvm/Support/ErrorHandling.h" #include #include #include -#include namespace llvm { @@ -83,13 +83,13 @@ public: } return NULL; } - + /// getMaxElement - Find the subtree associated with the highest ranged /// key value. ImutAVLTree* getMaxElement() { ImutAVLTree *T = this; - ImutAVLTree *Right = T->getRight(); - while (Right) { T = right; right = T->getRight(); } + ImutAVLTree *Right = T->getRight(); + while (Right) { T = Right; Right = T->getRight(); } return T; } @@ -257,7 +257,7 @@ private: /// method returns false for an instance of ImutAVLTree, all subtrees /// will also have this method return false. The converse is not true. bool isMutable() const { return IsMutable; } - + /// hasCachedDigest - Returns true if the digest for this tree is cached. /// This can only be true if the tree is immutable. bool hasCachedDigest() const { return IsDigestCached; } @@ -279,7 +279,7 @@ private: assert(isMutable() && "Mutable flag already removed."); IsMutable = false; } - + /// markedCachedDigest - Clears the NoCachedDigest flag for a tree. void markedCachedDigest() { assert(!hasCachedDigest() && "NoCachedDigest flag already removed."); @@ -346,9 +346,9 @@ public: if (prev) prev->next = next; else - factory->Cache[computeDigest()] = next; + factory->Cache[factory->maskCacheIndex(computeDigest())] = next; } - + // We need to clear the mutability bit in case we are // destroying the node as part of a sweep in ImutAVLFactory::recoverNodes(). IsMutable = false; @@ -414,7 +414,7 @@ public: TreeTy* getEmptyTree() const { return NULL; } protected: - + //===--------------------------------------------------===// // A bunch of quick helper functions used for reasoning // about the properties of trees and their children. @@ -428,6 +428,11 @@ protected: TreeTy* getRight(TreeTy* T) const { return T->getRight(); } value_type_ref getValue(TreeTy* T) const { return T->value; } + // Make sure the index is not the Tombstone or Entry key of the DenseMap. + static inline unsigned maskCacheIndex(unsigned I) { + return (I & ~0x02); + } + unsigned incrementHeight(TreeTy* L, TreeTy* R) const { unsigned hl = getHeight(L); unsigned hr = getHeight(R); @@ -455,7 +460,7 @@ protected: // returned to the caller. //===--------------------------------------------------===// - TreeTy* createNode(TreeTy* L, value_type_ref V, TreeTy* R) { + TreeTy* createNode(TreeTy* L, value_type_ref V, TreeTy* R) { BumpPtrAllocator& A = getAllocator(); TreeTy* T; if (!freeNodes.empty()) { @@ -463,8 +468,7 @@ protected: freeNodes.pop_back(); assert(T != L); assert(T != R); - } - else { + } else { T = (TreeTy*) A.Allocate(); } new (T) TreeTy(this, L, R, V, incrementHeight(L,R)); @@ -507,7 +511,8 @@ protected: return createNode(createNode(LL,L,LRL), LR, createNode(LRR,V,R)); } - else if (hr > hl + 2) { + + if (hr > hl + 2) { assert(!isEmpty(R) && "Right tree cannot be empty to have a height >= 2"); TreeTy *RL = getLeft(R); @@ -523,8 +528,8 @@ protected: return createNode(createNode(L,V,RLL), RL, createNode(RLR,R,RR)); } - else - return createNode(L,V,R); + + return createNode(L,V,R); } /// add_internal - Creates a new tree that includes the specified @@ -598,7 +603,7 @@ protected: markImmutable(getLeft(T)); markImmutable(getRight(T)); } - + public: TreeTy *getCanonicalTree(TreeTy *TNew) { if (!TNew) @@ -610,7 +615,7 @@ public: // Search the hashtable for another tree with the same digest, and // if find a collision compare those trees by their contents. unsigned digest = TNew->computeDigest(); - TreeTy *&entry = Cache[digest]; + TreeTy *&entry = Cache[maskCacheIndex(digest)]; do { if (!entry) break; @@ -661,7 +666,7 @@ public: return reinterpret_cast(stack.back() & ~Flags); } - uintptr_t getVisitState() { + uintptr_t getVisitState() const { assert(!stack.empty()); return stack.back() & Flags; } @@ -686,7 +691,7 @@ public: stack.back() |= VisitedRight; break; default: - assert(false && "Unreachable."); + llvm_unreachable("Unreachable."); } } @@ -722,7 +727,7 @@ public: skipToParent(); break; default: - assert(false && "Unreachable."); + llvm_unreachable("Unreachable."); } return *this; } @@ -747,7 +752,7 @@ public: stack.push_back(reinterpret_cast(R) | VisitedRight); break; default: - assert(false && "Unreachable."); + llvm_unreachable("Unreachable."); } return *this; } @@ -931,7 +936,7 @@ public: private: TreeTy *Root; - + public: /// Constructs a set from a pointer to a tree root. In general one /// should use a Factory object to create sets instead of directly @@ -1000,10 +1005,10 @@ public: typename TreeTy::Factory *getTreeFactory() const { return const_cast(&F); } - + private: - Factory(const Factory& RHS); // DO NOT IMPLEMENT - void operator=(const Factory& RHS); // DO NOT IMPLEMENT + Factory(const Factory& RHS) LLVM_DELETED_FUNCTION; + void operator=(const Factory& RHS) LLVM_DELETED_FUNCTION; }; friend class Factory; @@ -1021,11 +1026,11 @@ public: return Root && RHS.Root ? Root->isNotEqual(*RHS.Root) : Root != RHS.Root; } - TreeTy *getRoot() { + TreeTy *getRoot() { if (Root) { Root->retain(); } return Root; } - + TreeTy *getRootWithoutRetain() const { return Root; } @@ -1086,7 +1091,7 @@ public: void validateTree() const { if (Root) Root->validateTree(); } }; - + // NOTE: This may some day replace the current ImmutableSet. template > class ImmutableSetRef { @@ -1095,11 +1100,11 @@ public: typedef typename ValInfo::value_type_ref value_type_ref; typedef ImutAVLTree TreeTy; typedef typename TreeTy::Factory FactoryTy; - + private: TreeTy *Root; FactoryTy *Factory; - + public: /// Constructs a set from a pointer to a tree root. In general one /// should use a Factory object to create sets instead of directly @@ -1127,44 +1132,44 @@ public: ~ImmutableSetRef() { if (Root) { Root->release(); } } - + static inline ImmutableSetRef getEmptySet(FactoryTy *F) { return ImmutableSetRef(0, F); } - + ImmutableSetRef add(value_type_ref V) { return ImmutableSetRef(Factory->add(Root, V), Factory); } - + ImmutableSetRef remove(value_type_ref V) { return ImmutableSetRef(Factory->remove(Root, V), Factory); } - + /// Returns true if the set contains the specified value. bool contains(value_type_ref V) const { return Root ? Root->contains(V) : false; } - + ImmutableSet asImmutableSet(bool canonicalize = true) const { return ImmutableSet(canonicalize ? Factory->getCanonicalTree(Root) : Root); } - + TreeTy *getRootWithoutRetain() const { return Root; } - + bool operator==(const ImmutableSetRef &RHS) const { return Root && RHS.Root ? Root->isEqual(*RHS.Root) : Root == RHS.Root; } - + bool operator!=(const ImmutableSetRef &RHS) const { return Root && RHS.Root ? Root->isNotEqual(*RHS.Root) : Root != RHS.Root; } /// isEmpty - Return true if the set contains no elements. bool isEmpty() const { return !Root; } - + /// isSingleton - Return true if the set contains exactly one element. /// This method runs in constant time. bool isSingleton() const { return getHeight() == 1; } @@ -1172,7 +1177,7 @@ public: //===--------------------------------------------------===// // Iterators. //===--------------------------------------------------===// - + class iterator { typename TreeTy::iterator itr; iterator(TreeTy* t) : itr(t) {} @@ -1188,28 +1193,28 @@ public: inline bool operator!=(const iterator& RHS) const { return RHS.itr != itr; } inline value_type *operator->() const { return &(operator*()); } }; - + iterator begin() const { return iterator(Root); } iterator end() const { return iterator(); } - + //===--------------------------------------------------===// // Utility methods. //===--------------------------------------------------===// - + unsigned getHeight() const { return Root ? Root->getHeight() : 0; } - + static inline void Profile(FoldingSetNodeID& ID, const ImmutableSetRef& S) { ID.AddPointer(S.Root); } - + inline void Profile(FoldingSetNodeID& ID) const { return Profile(ID,*this); } - + //===--------------------------------------------------===// // For testing. //===--------------------------------------------------===// - + void validateTree() const { if (Root) Root->validateTree(); } };