//
//===----------------------------------------------------------------------===//
-#ifndef LLVM_ADT_IMSET_H
-#define LLVM_ADT_IMSET_H
+#ifndef LLVM_ADT_IMMUTABLESET_H
+#define LLVM_ADT_IMMUTABLESET_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 <cassert>
#include <functional>
#include <vector>
-#include <stdio.h>
namespace llvm {
}
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;
}
/// 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; }
assert(isMutable() && "Mutable flag already removed.");
IsMutable = false;
}
-
+
/// markedCachedDigest - Clears the NoCachedDigest flag for a tree.
void markedCachedDigest() {
assert(!hasCachedDigest() && "NoCachedDigest flag already removed.");
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;
TreeTy* getEmptyTree() const { return NULL; }
protected:
-
+
//===--------------------------------------------------===//
// A bunch of quick helper functions used for reasoning
// about the properties of trees and their children.
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);
// 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()) {
freeNodes.pop_back();
assert(T != L);
assert(T != R);
- }
- else {
+ } else {
T = (TreeTy*) A.Allocate<TreeTy>();
}
new (T) TreeTy(this, L, R, V, incrementHeight(L,R));
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);
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
markImmutable(getLeft(T));
markImmutable(getRight(T));
}
-
+
public:
TreeTy *getCanonicalTree(TreeTy *TNew) {
if (!TNew)
// 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;
return reinterpret_cast<TreeTy*>(stack.back() & ~Flags);
}
- uintptr_t getVisitState() {
+ uintptr_t getVisitState() const {
assert(!stack.empty());
return stack.back() & Flags;
}
stack.back() |= VisitedRight;
break;
default:
- assert(false && "Unreachable.");
+ llvm_unreachable("Unreachable.");
}
}
skipToParent();
break;
default:
- assert(false && "Unreachable.");
+ llvm_unreachable("Unreachable.");
}
return *this;
}
stack.push_back(reinterpret_cast<uintptr_t>(R) | VisitedRight);
break;
default:
- assert(false && "Unreachable.");
+ llvm_unreachable("Unreachable.");
}
return *this;
}
#undef PROFILE_INTEGER_INFO
+/// Profile traits for booleans.
+template <>
+struct ImutProfileInfo<bool> {
+ typedef const bool value_type;
+ typedef const bool& value_type_ref;
+
+ static inline void Profile(FoldingSetNodeID& ID, value_type_ref X) {
+ ID.AddBoolean(X);
+ }
+};
+
+
/// Generic profile trait for pointer types. We treat pointers as
/// references to unique objects.
template <typename T>
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
typename TreeTy::Factory *getTreeFactory() const {
return const_cast<typename TreeTy::Factory *>(&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;
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;
}
class iterator {
typename TreeTy::iterator itr;
+
+ iterator() {}
iterator(TreeTy* t) : itr(t) {}
friend class ImmutableSet<ValT,ValInfo>;
+
public:
- iterator() {}
- inline value_type_ref operator*() const { return itr->getValue(); }
- inline iterator& operator++() { ++itr; return *this; }
- inline iterator operator++(int) { iterator tmp(*this); ++itr; return tmp; }
- inline iterator& operator--() { --itr; return *this; }
- inline iterator operator--(int) { iterator tmp(*this); --itr; return tmp; }
- inline bool operator==(const iterator& RHS) const { return RHS.itr == itr; }
- inline bool operator!=(const iterator& RHS) const { return RHS.itr != itr; }
- inline value_type *operator->() const { return &(operator*()); }
+ typedef ptrdiff_t difference_type;
+ typedef typename ImmutableSet<ValT,ValInfo>::value_type value_type;
+ typedef typename ImmutableSet<ValT,ValInfo>::value_type_ref reference;
+ typedef typename iterator::value_type *pointer;
+ typedef std::bidirectional_iterator_tag iterator_category;
+
+ typename iterator::reference operator*() const { return itr->getValue(); }
+ typename iterator::pointer operator->() const { return &(operator*()); }
+
+ iterator& operator++() { ++itr; return *this; }
+ iterator operator++(int) { iterator tmp(*this); ++itr; return tmp; }
+ iterator& operator--() { --itr; return *this; }
+ iterator operator--(int) { iterator tmp(*this); --itr; return tmp; }
+
+ bool operator==(const iterator& RHS) const { return RHS.itr == itr; }
+ bool operator!=(const iterator& RHS) const { return RHS.itr != itr; }
};
iterator begin() const { return iterator(Root); }
void validateTree() const { if (Root) Root->validateTree(); }
};
-
+
// NOTE: This may some day replace the current ImmutableSet.
template <typename ValT, typename ValInfo = ImutContainerInfo<ValT> >
class ImmutableSetRef {
typedef typename ValInfo::value_type_ref value_type_ref;
typedef ImutAVLTree<ValInfo> 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
~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<ValT> asImmutableSet(bool canonicalize = true) const {
return ImmutableSet<ValT>(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; }
//===--------------------------------------------------===//
// Iterators.
//===--------------------------------------------------===//
-
+
class iterator {
typename TreeTy::iterator itr;
iterator(TreeTy* t) : itr(t) {}
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(); }
};
projects / oota-llvm.git / blobdiff