On Oct 9, 2007, at 2:38 PM, Ted Kremenek wrote: > Author: kremenek > Date: Tue Oct 9 16:38:09 2007 > New Revision: 42813 > > URL: http://llvm.org/viewvc/llvm-project?rev=42813&view=rev > Log: > Added implementation of immutable (functional) maps and sets, as > implemented on top of a functional AVL tree. The AVL balancing code > is inspired by the OCaml implementation of Map, which also uses a > functional > AVL tree. > > Documentation is currently limited and cleanups are planned, but > this code > compiles and has been tested. >
You mention that documentation is limited, so this may be a stupid question. Do you plan to add doxygen style comments to each function providing a brief description of it? Thanks, Tanya > Added: > llvm/trunk/include/llvm/ADT/ImmutableMap.h > llvm/trunk/include/llvm/ADT/ImmutableSet.h > > Added: llvm/trunk/include/llvm/ADT/ImmutableMap.h > URL: http://llvm.org/viewvc/llvm-project/llvm/trunk/include/llvm/ > ADT/ImmutableMap.h?rev=42813&view=auto > > ====================================================================== > ======== > --- llvm/trunk/include/llvm/ADT/ImmutableMap.h (added) > +++ llvm/trunk/include/llvm/ADT/ImmutableMap.h Tue Oct 9 16:38:09 > 2007 > @@ -0,0 +1,163 @@ > +//===--- ImmutableMap.h - Immutable (functional) map interface -- > *- C++ -*-===// > +// > +// The LLVM Compiler Infrastructure > +// > +// This file was developed by Ted Kremenek and is distributed under > +// the University of Illinois Open Source License. See LICENSE.TXT > for details. > +// > +// > ===------------------------------------------------------------------- > ---===// > +// > +// This file defines the ImmutableMap class. > +// > +// > ===------------------------------------------------------------------- > ---===// > + > +#ifndef LLVM_ADT_IMMAP_H > +#define LLVM_ADT_IMMAP_H > + > +#include "llvm/ADT/ImmutableSet.h" > + > +namespace llvm { > + > +/// ImutKeyValueInfo -Traits class used by ImmutableMap. While > both the first and > +/// second elements in a pair are used to generate profile > information, > +/// only the first element (the key) is used by isEqual and isLess. > +template <typename T, typename S> > +struct ImutKeyValueInfo { > + typedef const std::pair<T,S> value_type; > + typedef const value_type& value_type_ref; > + typedef const T key_type; > + typedef const T& key_type_ref; > + typedef const S data_type; > + typedef const S& data_type_ref; > + > + static inline key_type_ref KeyOfValue(value_type_ref V) { > + return V.first; > + } > + > + static inline bool isEqual(key_type_ref L, key_type_ref R) { > + return ImutContainerInfo<T>::isEqual(L,R); > + } > + > + static inline bool isLess(key_type_ref L, key_type_ref R) { > + return ImutContainerInfo<T>::isLess(L,R); > + } > + > + static inline void Profile(FoldingSetNodeID& ID, value_type_ref > V) { > + ImutContainerInfo<T>::Profile(ID, V.first); > + ImutContainerInfo<S>::Profile(ID, V.second); > + } > +}; > + > + > +template <typename KeyT, typename ValT, > + typename ValInfo = ImutKeyValueInfo<KeyT,ValT> > > +class ImmutableMap { > + typedef typename ValInfo::value_type value_type; > + typedef typename ValInfo::value_type_ref value_type_ref; > + typedef typename ValInfo::key_type key_type; > + typedef typename ValInfo::key_type_ref key_type_ref; > + typedef typename ValInfo::data_type data_type; > + typedef typename ValInfo::data_type_ref data_type_ref; > + > +private: > + typedef ImutAVLTree<ValInfo> TreeTy; > + TreeTy* Root; > + > + ImmutableMap(TreeTy* R) : Root(R) {} > + > +public: > + > + class Factory { > + typename TreeTy::Factory F; > + > + public: > + Factory() {} > + > + ImmutableMap GetEmptyMap() { return ImmutableMap(F.GetEmptyTree > ()); } > + > + ImmutableMap Add(ImmutableMap Old, key_type_ref K, > data_type_ref D) { > + return ImmutableMap(F.Add > (Old.Root,std::make_pair<key_type,data_type>(K,D))); > + } > + > + ImmutableMap Remove(ImmutableMap Old, key_type_ref K) { > + return ImmutableMap(F.Remove(Old.Root,K)); > + } > + > + private: > + Factory(const Factory& RHS) {}; > + void operator=(const Factory& RHS) {}; > + }; > + > + friend class Factory; > + > + bool contains(key_type_ref K) const { > + return Root ? Root->contains(K) : false; > + } > + > + data_type* find(key_type_ref K) const { > + if (Root) { > + TreeTy* T = Root->find(K); > + if (T) return &T->getValue().second; > + } > + > + return NULL; > + } > + > + bool operator==(ImmutableMap RHS) const { > + return Root && RHS.Root ? Root->isEqual(*RHS.Root) : Root == > RHS.Root; > + } > + > + bool operator!=(ImmutableMap RHS) const { > + return Root && RHS.Root ? Root->isNotEqual(*RHS.Root) : Root ! > = RHS.Root; > + } > + > + bool isEmpty() const { return !Root; } > + > + //===--------------------------------------------------===// > + // Foreach - A limited form of map iteration. > + //===--------------------------------------------------===// > + > +private: > + template <typename Callback> > + struct CBWrapper { > + Callback C; > + void operator()(value_type_ref V) { C(V.first,V.second); } > + }; > + > + template <typename Callback> > + struct CBWrapperRef { > + Callback &C; > + CBWrapperRef(Callback& c) : C(c) {} > + > + void operator()(value_type_ref V) { C(V.first,V.second); } > + }; > + > +public: > + template <typename Callback> > + void foreach(Callback& C) { > + if (Root) { > + CBWrapperRef<Callback> CB(C); > + Root->foreach(CB); > + } > + } > + > + template <typename Callback> > + void foreach() { > + if (Root) { > + CBWrapper<Callback> CB; > + Root->foreach(CB); > + } > + } > + > + //===--------------------------------------------------===// > + // For testing. > + //===--------------------------------------------------===// > + > + void verify() const { if (Root) Root->verify(); } > + unsigned getHeight() const { return Root ? Root->getHeight() : 0; } > + > +}; > + > +} // end namespace llvm > + > +#endif > > Added: llvm/trunk/include/llvm/ADT/ImmutableSet.h > URL: http://llvm.org/viewvc/llvm-project/llvm/trunk/include/llvm/ > ADT/ImmutableSet.h?rev=42813&view=auto > > ====================================================================== > ======== > --- llvm/trunk/include/llvm/ADT/ImmutableSet.h (added) > +++ llvm/trunk/include/llvm/ADT/ImmutableSet.h Tue Oct 9 16:38:09 > 2007 > @@ -0,0 +1,608 @@ > +//===--- ImmutableSet.h - Immutable (functional) set interface -- > *- C++ -*-===// > +// > +// The LLVM Compiler Infrastructure > +// > +// This file was developed by Ted Kremenek and is distributed under > +// the University of Illinois Open Source License. See LICENSE.TXT > for details. > +// > +// > ===------------------------------------------------------------------- > ---===// > +// > +// This file defines the ImutAVLTree and ImmutableSet classes. > +// > +// > ===------------------------------------------------------------------- > ---===// > + > +#ifndef LLVM_ADT_IMSET_H > +#define LLVM_ADT_IMSET_H > + > +#include "llvm/Support/Allocator.h" > +#include "llvm/ADT/FoldingSet.h" > +#include <cassert> > + > +namespace llvm { > + > +// > ===------------------------------------------------------------------- > ---===// > +// Immutable AVL-Tree Definition. > +// > ===------------------------------------------------------------------- > ---===// > + > +template <typename ImutInfo> class ImutAVLFactory; > + > +template <typename ImutInfo > > +class ImutAVLTree : public FoldingSetNode { > + struct ComputeIsEqual; > +public: > + typedef typename ImutInfo::key_type_ref key_type_ref; > + typedef typename ImutInfo::value_type value_type; > + typedef typename ImutInfo::value_type_ref value_type_ref; > + typedef ImutAVLFactory<ImutInfo> Factory; > + friend class ImutAVLFactory<ImutInfo>; > + > + //===----------------------------------------------------===// > + // Public Interface. > + //===----------------------------------------------------===// > + > + ImutAVLTree* getLeft() const { return > reinterpret_cast<ImutAVLTree*>(Left); } > + > + ImutAVLTree* getRight() const { return Right; } > + > + unsigned getHeight() const { return Height; } > + > + const value_type& getValue() const { return Value; } > + > + ImutAVLTree* find(key_type_ref K) { > + ImutAVLTree *T = this; > + > + while (T) { > + key_type_ref CurrentKey = ImutInfo::KeyOfValue(Value(T)); > + > + if (ImutInfo::isEqual(K,CurrentKey)) > + return T; > + else if (ImutInfo::isLess(K,CurrentKey)) > + T = T->getLeft(); > + else > + T = T->getRight(); > + } > + > + return NULL; > + } > + > + unsigned size() const { > + unsigned n = 1; > + > + if (const ImutAVLTree* L = getLeft()) n += L->size(); > + if (const ImutAVLTree* R = getRight()) n += R->size(); > + > + return n; > + } > + > + > + > + bool isEqual(const ImutAVLTree& RHS) const { > + // FIXME: Todo. > + return true; > + } > + > + bool isNotEqual(const ImutAVLTree& RHS) const { return !isEqual > (RHS); } > + > + bool contains(const key_type_ref K) { return (bool) find(K); } > + > + template <typename Callback> > + void foreach(Callback& C) { > + if (ImutAVLTree* L = getLeft()) L->foreach(C); > + > + C(Value); > + > + if (ImutAVLTree* R = getRight()) R->foreach(C); > + } > + > + unsigned verify() const { > + unsigned HL = getLeft() ? getLeft()->verify() : 0; > + unsigned HR = getRight() ? getRight()->verify() : 0; > + > + assert (getHeight() == ( HL > HR ? HL : HR ) + 1 > + && "Height calculation wrong."); > + > + assert ((HL > HR ? HL-HR : HR-HL) <= 2 > + && "Balancing invariant violated."); > + > + > + assert (!getLeft() > + || ImutInfo::isLess(ImutInfo::KeyOfValue(getLeft()- > >getValue()), > + ImutInfo::KeyOfValue(getValue())) > + && "Value in left child is not less that current > value."); > + > + > + assert (!getRight() > + || ImutInfo::isLess(ImutInfo::KeyOfValue(getValue()), > + ImutInfo::KeyOfValue(getRight()- > >getValue())) > + && "Current value is not less that value of right > child."); > + > + return getHeight(); > + } > + > + //===----------------------------------------------------===// > + // Internal Values. > + //===----------------------------------------------------===// > + > +private: > + uintptr_t Left; > + ImutAVLTree* Right; > + unsigned Height; > + value_type Value; > + > + //===----------------------------------------------------===// > + // Profiling or FoldingSet. > + //===----------------------------------------------------===// > + > + static inline > + void Profile(FoldingSetNodeID& ID, ImutAVLTree* L, ImutAVLTree* R, > + unsigned H, value_type_ref V) { > + ID.AddPointer(L); > + ID.AddPointer(R); > + ID.AddInteger(H); > + ImutInfo::Profile(ID,V); > + } > + > +public: > + > + void Profile(FoldingSetNodeID& ID) { > + Profile(ID,getSafeLeft(),getRight(),getHeight(),getValue()); > + } > + > + //===----------------------------------------------------===// > + // Internal methods (node manipulation; used by Factory). > + //===----------------------------------------------------===// > + > +private: > + > + ImutAVLTree(ImutAVLTree* l, ImutAVLTree* r, value_type_ref v, > unsigned height) > + : Left(reinterpret_cast<uintptr_t>(l) | 0x1), > + Right(r), Height(height), Value(v) {} > + > + bool isMutable() const { return Left & 0x1; } > + > + ImutAVLTree* getSafeLeft() const { > + return reinterpret_cast<ImutAVLTree*>(Left & ~0x1); > + } > + > + // Mutating operations. A tree root can be manipulated as long as > + // its reference has not "escaped" from internal methods of a > + // factory object (see below). When a tree pointer is externally > + // viewable by client code, the internal "mutable bit" is cleared > + // to mark the tree immutable. Note that a tree that still has > + // its mutable bit set may have children (subtrees) that are > themselves > + // immutable. > + > + void RemoveMutableFlag() { > + assert (Left & 0x1 && "Mutable flag already removed."); > + Left &= ~0x1; > + } > + > + void setLeft(ImutAVLTree* NewLeft) { > + assert (isMutable()); > + Left = reinterpret_cast<uintptr_t>(NewLeft) | 0x1; > + } > + > + void setRight(ImutAVLTree* NewRight) { > + assert (isMutable()); > + Right = NewRight; > + } > + > + void setHeight(unsigned h) { > + assert (isMutable()); > + Height = h; > + } > +}; > + > +// > ===------------------------------------------------------------------- > ---===// > +// Immutable AVL-Tree Factory class. > +// > ===------------------------------------------------------------------- > ---===// > + > +template <typename ImutInfo > > +class ImutAVLFactory { > + typedef ImutAVLTree<ImutInfo> TreeTy; > + typedef typename TreeTy::value_type_ref value_type_ref; > + typedef typename TreeTy::key_type_ref key_type_ref; > + > + typedef FoldingSet<TreeTy> CacheTy; > + > + CacheTy Cache; > + BumpPtrAllocator Allocator; > + > + //===--------------------------------------------------===// > + // Public interface. > + //===--------------------------------------------------===// > + > +public: > + ImutAVLFactory() {} > + > + TreeTy* Add(TreeTy* T, value_type_ref V) { > + T = Add_internal(V,T); > + MarkImmutable(T); > + return T; > + } > + > + TreeTy* Remove(TreeTy* T, key_type_ref V) { > + T = Remove_internal(V,T); > + MarkImmutable(T); > + return T; > + } > + > + TreeTy* GetEmptyTree() const { return NULL; } > + > + //===--------------------------------------------------===// > + // A bunch of quick helper functions used for reasoning > + // about the properties of trees and their children. > + // These have succinct names so that the balancing code > + // is as terse (and readable) as possible. > + //===--------------------------------------------------===// > +private: > + > + bool isEmpty(TreeTy* T) const { > + return !T; > + } > + > + unsigned Height(TreeTy* T) const { > + return T ? T->getHeight() : 0; > + } > + > + TreeTy* Left(TreeTy* T) const { > + assert (T); > + return T->getSafeLeft(); > + } > + > + TreeTy* Right(TreeTy* T) const { > + assert (T); > + return T->getRight(); > + } > + > + value_type_ref Value(TreeTy* T) const { > + assert (T); > + return T->Value; > + } > + > + unsigned IncrementHeight(TreeTy* L, TreeTy* R) const { > + unsigned hl = Height(L); > + unsigned hr = Height(R); > + return ( hl > hr ? hl : hr ) + 1; > + } > + > + //===--------------------------------------------------===// > + // "Create" is used to generate new tree roots that link > + // to other trees. The functon may also simply move links > + // in an existing root if that root is still marked mutable. > + // This is necessary because otherwise our balancing code > + // would leak memory as it would create nodes that are > + // then discarded later before the finished tree is > + // returned to the caller. > + //===--------------------------------------------------===// > + > + TreeTy* Create(TreeTy* L, value_type_ref V, TreeTy* R) { > + FoldingSetNodeID ID; > + unsigned height = IncrementHeight(L,R); > + > + TreeTy::Profile(ID,L,R,height,V); > + void* InsertPos; > + > + if (TreeTy* T = Cache.FindNodeOrInsertPos(ID,InsertPos)) > + return T; > + > + assert (InsertPos != NULL); > + > + // FIXME: more intelligent calculation of alignment. > + TreeTy* T = (TreeTy*) Allocator.Allocate(sizeof(*T),16); > + new (T) TreeTy(L,R,V,height); > + > + Cache.InsertNode(T,InsertPos); > + return T; > + } > + > + TreeTy* Create(TreeTy* L, TreeTy* OldTree, TreeTy* R) { > + assert (!isEmpty(OldTree)); > + > + if (OldTree->isMutable()) { > + OldTree->setLeft(L); > + OldTree->setRight(R); > + OldTree->setHeight(IncrementHeight(L,R)); > + return OldTree; > + } > + else return Create(L, Value(OldTree), R); > + } > + > + /// Balance - Used by Add_internal and Remove_internal to > + /// balance a newly created tree. > + TreeTy* Balance(TreeTy* L, value_type_ref V, TreeTy* R) { > + > + unsigned hl = Height(L); > + unsigned hr = Height(R); > + > + if (hl > hr + 2) { > + assert (!isEmpty(L) && > + "Left tree cannot be empty to have a height >= 2."); > + > + TreeTy* LL = Left(L); > + TreeTy* LR = Right(L); > + > + if (Height(LL) >= Height(LR)) > + return Create(LL, L, Create(LR,V,R)); > + > + assert (!isEmpty(LR) && > + "LR cannot be empty because it has a height >= 1."); > + > + TreeTy* LRL = Left(LR); > + TreeTy* LRR = Right(LR); > + > + return Create(Create(LL,L,LRL), LR, Create(LRR,V,R)); > + } > + else if (hr > hl + 2) { > + assert (!isEmpty(R) && > + "Right tree cannot be empty to have a height >= 2."); > + > + TreeTy* RL = Left(R); > + TreeTy* RR = Right(R); > + > + if (Height(RR) >= Height(RL)) > + return Create(Create(L,V,RL), R, RR); > + > + assert (!isEmpty(RL) && > + "RL cannot be empty because it has a height >= 1."); > + > + TreeTy* RLL = Left(RL); > + TreeTy* RLR = Right(RL); > + > + return Create(Create(L,V,RLL), RL, Create(RLR,R,RR)); > + } > + else > + return Create(L,V,R); > + } > + > + /// Add_internal - Creates a new tree that includes the specified > + /// data and the data from the original tree. If the original > tree > + /// already contained the data item, the original tree is > returned. > + TreeTy* Add_internal(value_type_ref V, TreeTy* T) { > + if (isEmpty(T)) > + return Create(T, V, T); > + > + assert (!T->isMutable()); > + > + key_type_ref K = ImutInfo::KeyOfValue(V); > + key_type_ref KCurrent = ImutInfo::KeyOfValue(Value(T)); > + > + if (ImutInfo::isEqual(K,KCurrent)) > + return Create(Left(T), V, Right(T)); > + else if (ImutInfo::isLess(K,KCurrent)) > + return Balance(Add_internal(V,Left(T)), Value(T), Right(T)); > + else > + return Balance(Left(T), Value(T), Add_internal(V,Right(T))); > + } > + > + /// Remove_interal - Creates a new tree that includes all the data > + /// from the original tree except the specified data. If the > + /// specified data did not exist in the original tree, the > original > + /// tree is returned. > + TreeTy* Remove_internal(key_type_ref K, TreeTy* T) { > + if (isEmpty(T)) > + return T; > + > + assert (!T->isMutable()); > + > + key_type_ref KCurrent = ImutInfo::KeyOfValue(Value(T)); > + > + if (ImutInfo::isEqual(K,KCurrent)) > + return CombineLeftRightTrees(Left(T),Right(T)); > + else if (ImutInfo::isLess(K,KCurrent)) > + return Balance(Remove_internal(K,Left(T)), Value(T), Right(T)); > + else > + return Balance(Left(T), Value(T), Remove_internal(K,Right(T))); > + } > + > + TreeTy* CombineLeftRightTrees(TreeTy* L, TreeTy* R) { > + if (isEmpty(L)) return R; > + if (isEmpty(R)) return L; > + > + TreeTy* OldNode; > + TreeTy* NewRight = RemoveMinBinding(R,OldNode); > + return Balance(L,Value(OldNode),NewRight); > + } > + > + TreeTy* RemoveMinBinding(TreeTy* T, TreeTy*& NodeRemoved) { > + assert (!isEmpty(T)); > + > + if (isEmpty(Left(T))) { > + NodeRemoved = T; > + return Right(T); > + } > + > + return Balance(RemoveMinBinding(Left(T),NodeRemoved),Value > (T),Right(T)); > + } > + > + /// MarkImmutable - Clears the mutable bits of a root and all of > its > + /// descendants. > + void MarkImmutable(TreeTy* T) { > + if (!T || !T->isMutable()) > + return; > + > + T->RemoveMutableFlag(); > + MarkImmutable(Left(T)); > + MarkImmutable(Right(T)); > + } > +}; > + > + > +// > ===------------------------------------------------------------------- > ---===// > +// Trait classes for Profile information. > +// > ===------------------------------------------------------------------- > ---===// > + > +/// Generic profile template. The default behavior is to invoke the > +/// profile method of an object. Specializations for primitive > integers > +/// and generic handling of pointers is done below. > +template <typename T> > +struct ImutProfileInfo { > + typedef const T value_type; > + typedef const T& value_type_ref; > + > + static inline void Profile(FoldingSetNodeID& ID, value_type_ref > X) { > + X.Profile(ID); > + } > +}; > + > +/// Profile traits for integers. > +template <typename T> > +struct ImutProfileInteger { > + typedef const T value_type; > + typedef const T& value_type_ref; > + > + static inline void Profile(FoldingSetNodeID& ID, value_type_ref > X) { > + ID.AddInteger(X); > + } > +}; > + > +#define PROFILE_INTEGER_INFO(X)\ > +template<> struct ImutProfileInfo<X> : ImutProfileInteger<X> {}; > + > +PROFILE_INTEGER_INFO(char) > +PROFILE_INTEGER_INFO(unsigned char) > +PROFILE_INTEGER_INFO(short) > +PROFILE_INTEGER_INFO(unsigned short) > +PROFILE_INTEGER_INFO(unsigned) > +PROFILE_INTEGER_INFO(signed) > +PROFILE_INTEGER_INFO(long) > +PROFILE_INTEGER_INFO(unsigned long) > +PROFILE_INTEGER_INFO(long long) > +PROFILE_INTEGER_INFO(unsigned long long) > + > +#undef PROFILE_INTEGER_INFO > + > +/// Generic profile trait for pointer types. We treat pointers as > +/// references to unique objects. > +template <typename T> > +struct ImutProfileInfo<T*> { > + typedef const T* value_type; > + typedef value_type value_type_ref; > + > + static inline void Profile(FoldingSetNodeID &ID, value_type_ref > X) { > + ID.AddPointer(X); > + } > +}; > + > +// > ===------------------------------------------------------------------- > ---===// > +// Trait classes that contain element comparison operators and type > +// definitions used by ImutAVLTree, ImmutableSet, and > ImmutableMap. These > +// inherit from the profile traits (ImutProfileInfo) to include > operations > +// for element profiling. > +// > ===------------------------------------------------------------------- > ---===// > + > + > +/// ImutContainerInfo - Generic definition of comparison > operations for > +/// elements of immutable containers that defaults to using > +/// std::equal_to<> and std::less<> to perform comparison of > elements. > +template <typename T> > +struct ImutContainerInfo : public ImutProfileInfo<T> { > + typedef typename ImutProfileInfo<T>::value_type value_type; > + typedef typename ImutProfileInfo<T>::value_type_ref > value_type_ref; > + typedef value_type key_type; > + typedef value_type_ref key_type_ref; > + > + static inline key_type_ref KeyOfValue(value_type_ref D) { return > D; } > + > + static inline bool isEqual(key_type_ref LHS, key_type_ref RHS) { > + return std::equal_to<key_type>()(LHS,RHS); > + } > + > + static inline bool isLess(key_type_ref LHS, key_type_ref RHS) { > + return std::less<key_type>()(LHS,RHS); > + } > +}; > + > +/// ImutContainerInfo - Specialization for pointer values to treat > pointers > +/// as references to unique objects. Pointers are thus compared by > +/// their addresses. > +template <typename T> > +struct ImutContainerInfo<T*> : public ImutProfileInfo<T*> { > + typedef typename ImutProfileInfo<T*>::value_type value_type; > + typedef typename ImutProfileInfo<T*>::value_type_ref > value_type_ref; > + typedef value_type key_type; > + typedef value_type_ref key_type_ref; > + > + static inline key_type_ref KeyOfValue(value_type_ref D) { return > D; } > + > + static inline bool isEqual(key_type_ref LHS, key_type_ref RHS) { > + return LHS == RHS; > + } > + > + static inline bool isLess(key_type_ref LHS, key_type_ref RHS) { > + return LHS < RHS; > + } > +}; > + > +// > ===------------------------------------------------------------------- > ---===// > +// Immutable Set > +// > ===------------------------------------------------------------------- > ---===// > + > +template <typename ValT, typename ValInfo = ImutContainerInfo<ValT> > > +class ImmutableSet { > +public: > + typedef typename ValInfo::value_type value_type; > + typedef typename ValInfo::value_type_ref value_type_ref; > + > +private: > + typedef ImutAVLTree<ValInfo> TreeTy; > + TreeTy* Root; > + > + ImmutableSet(TreeTy* R) : Root(R) {} > + > +public: > + > + class Factory { > + typename TreeTy::Factory F; > + > + public: > + Factory() {} > + > + ImmutableSet GetEmptySet() { return ImmutableSet(F.GetEmptyTree > ()); } > + > + ImmutableSet Add(ImmutableSet Old, value_type_ref V) { > + return ImmutableSet(F.Add(Old.Root,V)); > + } > + > + ImmutableSet Remove(ImmutableSet Old, value_type_ref V) { > + return ImmutableSet(F.Remove(Old.Root,V)); > + } > + > + private: > + Factory(const Factory& RHS) {}; > + void operator=(const Factory& RHS) {}; > + }; > + > + friend class Factory; > + > + bool contains(const value_type_ref V) const { > + return Root ? Root->contains(V) : false; > + } > + > + bool operator==(ImmutableSet RHS) const { > + return Root && RHS.Root ? Root->isEqual(*RHS.Root) : Root == > RHS.Root; > + } > + > + bool operator!=(ImmutableSet RHS) const { > + return Root && RHS.Root ? Root->isNotEqual(*RHS.Root) : Root ! > = RHS.Root; > + } > + > + bool isEmpty() const { return !Root; } > + > + template <typename Callback> > + void foreach(Callback& C) { if (Root) Root->foreach(C); } > + > + template <typename Callback> > + void foreach() { if (Root) { Callback C; Root->foreach(C); } } > + > + //===--------------------------------------------------===// > + // For testing. > + //===--------------------------------------------------===// > + > + void verify() const { if (Root) Root->verify(); } > + unsigned getHeight() const { return Root ? Root->getHeight() : 0; } > +}; > + > +} // end namespace llvm > + > +#endif > > > _______________________________________________ > llvm-commits mailing list > [email protected] > http://lists.cs.uiuc.edu/mailman/listinfo/llvm-commits _______________________________________________ llvm-commits mailing list [email protected] http://lists.cs.uiuc.edu/mailman/listinfo/llvm-commits
