LLVM API Documentation

ImmutableSet.h

Go to the documentation of this file.
00001 //===--- ImmutableSet.h - Immutable (functional) set interface --*- C++ -*-===//
00002 //
00003 //                     The LLVM Compiler Infrastructure
00004 //
00005 // This file is distributed under the University of Illinois Open Source
00006 // License. See LICENSE.TXT for details.
00007 //
00008 //===----------------------------------------------------------------------===//
00009 //
00010 // This file defines the ImutAVLTree and ImmutableSet classes.
00011 //
00012 //===----------------------------------------------------------------------===//
00013 
00014 #ifndef LLVM_ADT_IMSET_H
00015 #define LLVM_ADT_IMSET_H
00016 
00017 #include "llvm/Support/Allocator.h"
00018 #include "llvm/ADT/FoldingSet.h"
00019 #include "llvm/Support/DataTypes.h"
00020 #include <cassert>
00021 #include <functional>
00022 
00023 namespace llvm {
00024 
00025 //===----------------------------------------------------------------------===//
00026 // Immutable AVL-Tree Definition.
00027 //===----------------------------------------------------------------------===//
00028 
00029 template <typename ImutInfo> class ImutAVLFactory;
00030 template <typename ImutInfo> class ImutAVLTreeInOrderIterator;
00031 template <typename ImutInfo> class ImutAVLTreeGenericIterator;
00032 
00033 template <typename ImutInfo >
00034 class ImutAVLTree : public FoldingSetNode {
00035 public:
00036   typedef typename ImutInfo::key_type_ref   key_type_ref;
00037   typedef typename ImutInfo::value_type     value_type;
00038   typedef typename ImutInfo::value_type_ref value_type_ref;
00039 
00040   typedef ImutAVLFactory<ImutInfo>          Factory;
00041   friend class ImutAVLFactory<ImutInfo>;
00042 
00043   friend class ImutAVLTreeGenericIterator<ImutInfo>;
00044   friend class FoldingSet<ImutAVLTree>;
00045 
00046   typedef ImutAVLTreeInOrderIterator<ImutInfo>  iterator;
00047 
00048   //===----------------------------------------------------===//
00049   // Public Interface.
00050   //===----------------------------------------------------===//
00051 
00052   /// getLeft - Returns a pointer to the left subtree.  This value
00053   ///  is NULL if there is no left subtree.
00054   ImutAVLTree *getLeft() const {
00055     return reinterpret_cast<ImutAVLTree*>(Left & ~LeftFlags);
00056   }
00057 
00058   /// getRight - Returns a pointer to the right subtree.  This value is
00059   ///  NULL if there is no right subtree.
00060   ImutAVLTree* getRight() const { return Right; }
00061 
00062   /// getHeight - Returns the height of the tree.  A tree with no subtrees
00063   ///  has a height of 1.
00064   unsigned getHeight() const { return Height; }
00065 
00066   /// getValue - Returns the data value associated with the tree node.
00067   const value_type& getValue() const { return Value; }
00068 
00069   /// find - Finds the subtree associated with the specified key value.
00070   ///  This method returns NULL if no matching subtree is found.
00071   ImutAVLTree* find(key_type_ref K) {
00072     ImutAVLTree *T = this;
00073 
00074     while (T) {
00075       key_type_ref CurrentKey = ImutInfo::KeyOfValue(T->getValue());
00076 
00077       if (ImutInfo::isEqual(K,CurrentKey))
00078         return T;
00079       else if (ImutInfo::isLess(K,CurrentKey))
00080         T = T->getLeft();
00081       else
00082         T = T->getRight();
00083     }
00084 
00085     return NULL;
00086   }
00087   
00088   /// getMaxElement - Find the subtree associated with the highest ranged
00089   ///  key value.
00090   ImutAVLTree* getMaxElement() {
00091     ImutAVLTree *T = this;
00092     ImutAVLTree *Right = T->getRight();    
00093     while (Right) { T = Right; Right = T->getRight(); }
00094     return T;
00095   }
00096 
00097   /// size - Returns the number of nodes in the tree, which includes
00098   ///  both leaves and non-leaf nodes.
00099   unsigned size() const {
00100     unsigned n = 1;
00101 
00102     if (const ImutAVLTree* L = getLeft())  n += L->size();
00103     if (const ImutAVLTree* R = getRight()) n += R->size();
00104 
00105     return n;
00106   }
00107 
00108   /// begin - Returns an iterator that iterates over the nodes of the tree
00109   ///  in an inorder traversal.  The returned iterator thus refers to the
00110   ///  the tree node with the minimum data element.
00111   iterator begin() const { return iterator(this); }
00112 
00113   /// end - Returns an iterator for the tree that denotes the end of an
00114   ///  inorder traversal.
00115   iterator end() const { return iterator(); }
00116 
00117   bool ElementEqual(value_type_ref V) const {
00118     // Compare the keys.
00119     if (!ImutInfo::isEqual(ImutInfo::KeyOfValue(getValue()),
00120                            ImutInfo::KeyOfValue(V)))
00121       return false;
00122 
00123     // Also compare the data values.
00124     if (!ImutInfo::isDataEqual(ImutInfo::DataOfValue(getValue()),
00125                                ImutInfo::DataOfValue(V)))
00126       return false;
00127 
00128     return true;
00129   }
00130 
00131   bool ElementEqual(const ImutAVLTree* RHS) const {
00132     return ElementEqual(RHS->getValue());
00133   }
00134 
00135   /// isEqual - Compares two trees for structural equality and returns true
00136   ///   if they are equal.  This worst case performance of this operation is
00137   //    linear in the sizes of the trees.
00138   bool isEqual(const ImutAVLTree& RHS) const {
00139     if (&RHS == this)
00140       return true;
00141 
00142     iterator LItr = begin(), LEnd = end();
00143     iterator RItr = RHS.begin(), REnd = RHS.end();
00144 
00145     while (LItr != LEnd && RItr != REnd) {
00146       if (*LItr == *RItr) {
00147         LItr.SkipSubTree();
00148         RItr.SkipSubTree();
00149         continue;
00150       }
00151 
00152       if (!LItr->ElementEqual(*RItr))
00153         return false;
00154 
00155       ++LItr;
00156       ++RItr;
00157     }
00158 
00159     return LItr == LEnd && RItr == REnd;
00160   }
00161 
00162   /// isNotEqual - Compares two trees for structural inequality.  Performance
00163   ///  is the same is isEqual.
00164   bool isNotEqual(const ImutAVLTree& RHS) const { return !isEqual(RHS); }
00165 
00166   /// contains - Returns true if this tree contains a subtree (node) that
00167   ///  has an data element that matches the specified key.  Complexity
00168   ///  is logarithmic in the size of the tree.
00169   bool contains(key_type_ref K) { return (bool) find(K); }
00170 
00171   /// foreach - A member template the accepts invokes operator() on a functor
00172   ///  object (specifed by Callback) for every node/subtree in the tree.
00173   ///  Nodes are visited using an inorder traversal.
00174   template <typename Callback>
00175   void foreach(Callback& C) {
00176     if (ImutAVLTree* L = getLeft()) L->foreach(C);
00177 
00178     C(Value);
00179 
00180     if (ImutAVLTree* R = getRight()) R->foreach(C);
00181   }
00182 
00183   /// verify - A utility method that checks that the balancing and
00184   ///  ordering invariants of the tree are satisifed.  It is a recursive
00185   ///  method that returns the height of the tree, which is then consumed
00186   ///  by the enclosing verify call.  External callers should ignore the
00187   ///  return value.  An invalid tree will cause an assertion to fire in
00188   ///  a debug build.
00189   unsigned verify() const {
00190     unsigned HL = getLeft() ? getLeft()->verify() : 0;
00191     unsigned HR = getRight() ? getRight()->verify() : 0;
00192 
00193     assert (getHeight() == ( HL > HR ? HL : HR ) + 1
00194             && "Height calculation wrong.");
00195 
00196     assert ((HL > HR ? HL-HR : HR-HL) <= 2
00197             && "Balancing invariant violated.");
00198 
00199 
00200     assert (!getLeft()
00201             || ImutInfo::isLess(ImutInfo::KeyOfValue(getLeft()->getValue()),
00202                                 ImutInfo::KeyOfValue(getValue()))
00203             && "Value in left child is not less that current value.");
00204 
00205 
00206     assert (!getRight()
00207             || ImutInfo::isLess(ImutInfo::KeyOfValue(getValue()),
00208                                 ImutInfo::KeyOfValue(getRight()->getValue()))
00209             && "Current value is not less that value of right child.");
00210 
00211     return getHeight();
00212   }
00213 
00214   /// Profile - Profiling for ImutAVLTree.
00215   void Profile(llvm::FoldingSetNodeID& ID) {
00216     ID.AddInteger(ComputeDigest());
00217   }
00218 
00219   //===----------------------------------------------------===//
00220   // Internal Values.
00221   //===----------------------------------------------------===//
00222 
00223 private:
00224   uintptr_t        Left;
00225   ImutAVLTree*     Right;
00226   unsigned         Height;
00227   value_type       Value;
00228   uint32_t         Digest;
00229 
00230   //===----------------------------------------------------===//
00231   // Internal methods (node manipulation; used by Factory).
00232   //===----------------------------------------------------===//
00233 
00234 private:
00235 
00236   enum { Mutable = 0x1, NoCachedDigest = 0x2, LeftFlags = 0x3 };
00237 
00238   /// ImutAVLTree - Internal constructor that is only called by
00239   ///   ImutAVLFactory.
00240   ImutAVLTree(ImutAVLTree* l, ImutAVLTree* r, value_type_ref v, unsigned height)
00241   : Left(reinterpret_cast<uintptr_t>(l) | (Mutable | NoCachedDigest)),
00242     Right(r), Height(height), Value(v), Digest(0) {}
00243 
00244 
00245   /// isMutable - Returns true if the left and right subtree references
00246   ///  (as well as height) can be changed.  If this method returns false,
00247   ///  the tree is truly immutable.  Trees returned from an ImutAVLFactory
00248   ///  object should always have this method return true.  Further, if this
00249   ///  method returns false for an instance of ImutAVLTree, all subtrees
00250   ///  will also have this method return false.  The converse is not true.
00251   bool isMutable() const { return Left & Mutable; }
00252   
00253   /// hasCachedDigest - Returns true if the digest for this tree is cached.
00254   ///  This can only be true if the tree is immutable.
00255   bool hasCachedDigest() const { return !(Left & NoCachedDigest); }
00256 
00257   //===----------------------------------------------------===//
00258   // Mutating operations.  A tree root can be manipulated as
00259   // long as its reference has not "escaped" from internal
00260   // methods of a factory object (see below).  When a tree
00261   // pointer is externally viewable by client code, the
00262   // internal "mutable bit" is cleared to mark the tree
00263   // immutable.  Note that a tree that still has its mutable
00264   // bit set may have children (subtrees) that are themselves
00265   // immutable.
00266   //===----------------------------------------------------===//
00267 
00268   /// MarkImmutable - Clears the mutable flag for a tree.  After this happens,
00269   ///   it is an error to call setLeft(), setRight(), and setHeight().
00270   void MarkImmutable() {
00271     assert(isMutable() && "Mutable flag already removed.");
00272     Left &= ~Mutable;
00273   }
00274   
00275   /// MarkedCachedDigest - Clears the NoCachedDigest flag for a tree.
00276   void MarkedCachedDigest() {
00277     assert(!hasCachedDigest() && "NoCachedDigest flag already removed.");
00278     Left &= ~NoCachedDigest;
00279   }
00280 
00281   /// setLeft - Changes the reference of the left subtree.  Used internally
00282   ///   by ImutAVLFactory.
00283   void setLeft(ImutAVLTree* NewLeft) {
00284     assert(isMutable() &&
00285            "Only a mutable tree can have its left subtree changed.");
00286     Left = reinterpret_cast<uintptr_t>(NewLeft) | LeftFlags;
00287   }
00288 
00289   /// setRight - Changes the reference of the right subtree.  Used internally
00290   ///  by ImutAVLFactory.
00291   void setRight(ImutAVLTree* NewRight) {
00292     assert(isMutable() &&
00293            "Only a mutable tree can have its right subtree changed.");
00294 
00295     Right = NewRight;
00296     // Set the NoCachedDigest flag.
00297     Left = Left | NoCachedDigest;
00298 
00299   }
00300 
00301   /// setHeight - Changes the height of the tree.  Used internally by
00302   ///  ImutAVLFactory.
00303   void setHeight(unsigned h) {
00304     assert(isMutable() && "Only a mutable tree can have its height changed.");
00305     Height = h;
00306   }
00307 
00308   static inline
00309   uint32_t ComputeDigest(ImutAVLTree* L, ImutAVLTree* R, value_type_ref V) {
00310     uint32_t digest = 0;
00311 
00312     if (L)
00313       digest += L->ComputeDigest();
00314 
00315     // Compute digest of stored data.
00316     FoldingSetNodeID ID;
00317     ImutInfo::Profile(ID,V);
00318     digest += ID.ComputeHash();
00319 
00320     if (R)
00321       digest += R->ComputeDigest();
00322 
00323     return digest;
00324   }
00325 
00326   inline uint32_t ComputeDigest() {
00327     // Check the lowest bit to determine if digest has actually been
00328     // pre-computed.
00329     if (hasCachedDigest())
00330       return Digest;
00331 
00332     uint32_t X = ComputeDigest(getLeft(), getRight(), getValue());
00333     Digest = X;
00334     return X;
00335   }
00336 };
00337 
00338 //===----------------------------------------------------------------------===//
00339 // Immutable AVL-Tree Factory class.
00340 //===----------------------------------------------------------------------===//
00341 
00342 template <typename ImutInfo >
00343 class ImutAVLFactory {
00344   typedef ImutAVLTree<ImutInfo> TreeTy;
00345   typedef typename TreeTy::value_type_ref value_type_ref;
00346   typedef typename TreeTy::key_type_ref   key_type_ref;
00347 
00348   typedef FoldingSet<TreeTy> CacheTy;
00349 
00350   CacheTy Cache;
00351   uintptr_t Allocator;
00352 
00353   bool ownsAllocator() const {
00354     return Allocator & 0x1 ? false : true;
00355   }
00356 
00357   BumpPtrAllocator& getAllocator() const {
00358     return *reinterpret_cast<BumpPtrAllocator*>(Allocator & ~0x1);
00359   }
00360 
00361   //===--------------------------------------------------===//
00362   // Public interface.
00363   //===--------------------------------------------------===//
00364 
00365 public:
00366   ImutAVLFactory()
00367     : Allocator(reinterpret_cast<uintptr_t>(new BumpPtrAllocator())) {}
00368 
00369   ImutAVLFactory(BumpPtrAllocator& Alloc)
00370     : Allocator(reinterpret_cast<uintptr_t>(&Alloc) | 0x1) {}
00371 
00372   ~ImutAVLFactory() {
00373     if (ownsAllocator()) delete &getAllocator();
00374   }
00375 
00376   TreeTy* Add(TreeTy* T, value_type_ref V) {
00377     T = Add_internal(V,T);
00378     MarkImmutable(T);
00379     return T;
00380   }
00381 
00382   TreeTy* Remove(TreeTy* T, key_type_ref V) {
00383     T = Remove_internal(V,T);
00384     MarkImmutable(T);
00385     return T;
00386   }
00387 
00388   TreeTy* GetEmptyTree() const { return NULL; }
00389 
00390   //===--------------------------------------------------===//
00391   // A bunch of quick helper functions used for reasoning
00392   // about the properties of trees and their children.
00393   // These have succinct names so that the balancing code
00394   // is as terse (and readable) as possible.
00395   //===--------------------------------------------------===//
00396 private:
00397 
00398   bool           isEmpty(TreeTy* T) const { return !T; }
00399   unsigned        Height(TreeTy* T) const { return T ? T->getHeight() : 0; }
00400   TreeTy*           Left(TreeTy* T) const { return T->getLeft(); }
00401   TreeTy*          Right(TreeTy* T) const { return T->getRight(); }
00402   value_type_ref   Value(TreeTy* T) const { return T->Value; }
00403 
00404   unsigned IncrementHeight(TreeTy* L, TreeTy* R) const {
00405     unsigned hl = Height(L);
00406     unsigned hr = Height(R);
00407     return ( hl > hr ? hl : hr ) + 1;
00408   }
00409 
00410   static bool CompareTreeWithSection(TreeTy* T,
00411                                      typename TreeTy::iterator& TI,
00412                                      typename TreeTy::iterator& TE) {
00413 
00414     typename TreeTy::iterator I = T->begin(), E = T->end();
00415 
00416     for ( ; I!=E ; ++I, ++TI)
00417       if (TI == TE || !I->ElementEqual(*TI))
00418         return false;
00419 
00420     return true;
00421   }
00422 
00423   //===--------------------------------------------------===//
00424   // "CreateNode" is used to generate new tree roots that link
00425   // to other trees.  The functon may also simply move links
00426   // in an existing root if that root is still marked mutable.
00427   // This is necessary because otherwise our balancing code
00428   // would leak memory as it would create nodes that are
00429   // then discarded later before the finished tree is
00430   // returned to the caller.
00431   //===--------------------------------------------------===//
00432 
00433   TreeTy* CreateNode(TreeTy* L, value_type_ref V, TreeTy* R) {
00434     // Search the FoldingSet bucket for a Tree with the same digest.
00435     FoldingSetNodeID ID;
00436     unsigned digest = TreeTy::ComputeDigest(L, R, V);
00437     ID.AddInteger(digest);
00438     unsigned hash = ID.ComputeHash();
00439 
00440     typename CacheTy::bucket_iterator I = Cache.bucket_begin(hash);
00441     typename CacheTy::bucket_iterator E = Cache.bucket_end(hash);
00442 
00443     for (; I != E; ++I) {
00444       TreeTy* T = &*I;
00445 
00446       if (T->ComputeDigest() != digest)
00447         continue;
00448 
00449       // We found a collision.  Perform a comparison of Contents('T')
00450       // with Contents('L')+'V'+Contents('R').
00451       typename TreeTy::iterator TI = T->begin(), TE = T->end();
00452 
00453       // First compare Contents('L') with the (initial) contents of T.
00454       if (!CompareTreeWithSection(L, TI, TE))
00455         continue;
00456 
00457       // Now compare the new data element.
00458       if (TI == TE || !TI->ElementEqual(V))
00459         continue;
00460 
00461       ++TI;
00462 
00463       // Now compare the remainder of 'T' with 'R'.
00464       if (!CompareTreeWithSection(R, TI, TE))
00465         continue;
00466 
00467       if (TI != TE)
00468         continue; // Contents('R') did not match suffix of 'T'.
00469 
00470       // Trees did match!  Return 'T'.
00471       return T;
00472     }
00473 
00474     // No tree with the contents: Contents('L')+'V'+Contents('R').
00475     // Create it.  Allocate the new tree node and insert it into the cache.
00476     BumpPtrAllocator& A = getAllocator();
00477     TreeTy* T = (TreeTy*) A.Allocate<TreeTy>();
00478     new (T) TreeTy(L,R,V,IncrementHeight(L,R));
00479 
00480     // We do not insert 'T' into the FoldingSet here.  This is because
00481     // this tree is still mutable and things may get rebalanced.
00482     // Because our digest is associative and based on the contents of
00483     // the set, this should hopefully not cause any strange bugs.
00484     // 'T' is inserted by 'MarkImmutable'.
00485     return T;
00486   }
00487 
00488   TreeTy* CreateNode(TreeTy* L, TreeTy* OldTree, TreeTy* R) {
00489     assert (!isEmpty(OldTree));
00490 
00491     if (OldTree->isMutable()) {
00492       OldTree->setLeft(L);
00493       OldTree->setRight(R);
00494       OldTree->setHeight(IncrementHeight(L,R));
00495       return OldTree;
00496     }
00497     else
00498       return CreateNode(L, Value(OldTree), R);
00499   }
00500 
00501   /// Balance - Used by Add_internal and Remove_internal to
00502   ///  balance a newly created tree.
00503   TreeTy* Balance(TreeTy* L, value_type_ref V, TreeTy* R) {
00504 
00505     unsigned hl = Height(L);
00506     unsigned hr = Height(R);
00507 
00508     if (hl > hr + 2) {
00509       assert (!isEmpty(L) &&
00510               "Left tree cannot be empty to have a height >= 2.");
00511 
00512       TreeTy* LL = Left(L);
00513       TreeTy* LR = Right(L);
00514 
00515       if (Height(LL) >= Height(LR))
00516         return CreateNode(LL, L, CreateNode(LR,V,R));
00517 
00518       assert (!isEmpty(LR) &&
00519               "LR cannot be empty because it has a height >= 1.");
00520 
00521       TreeTy* LRL = Left(LR);
00522       TreeTy* LRR = Right(LR);
00523 
00524       return CreateNode(CreateNode(LL,L,LRL), LR, CreateNode(LRR,V,R));
00525     }
00526     else if (hr > hl + 2) {
00527       assert (!isEmpty(R) &&
00528               "Right tree cannot be empty to have a height >= 2.");
00529 
00530       TreeTy* RL = Left(R);
00531       TreeTy* RR = Right(R);
00532 
00533       if (Height(RR) >= Height(RL))
00534         return CreateNode(CreateNode(L,V,RL), R, RR);
00535 
00536       assert (!isEmpty(RL) &&
00537               "RL cannot be empty because it has a height >= 1.");
00538 
00539       TreeTy* RLL = Left(RL);
00540       TreeTy* RLR = Right(RL);
00541 
00542       return CreateNode(CreateNode(L,V,RLL), RL, CreateNode(RLR,R,RR));
00543     }
00544     else
00545       return CreateNode(L,V,R);
00546   }
00547 
00548   /// Add_internal - Creates a new tree that includes the specified
00549   ///  data and the data from the original tree.  If the original tree
00550   ///  already contained the data item, the original tree is returned.
00551   TreeTy* Add_internal(value_type_ref V, TreeTy* T) {
00552     if (isEmpty(T))
00553       return CreateNode(T, V, T);
00554 
00555     assert (!T->isMutable());
00556 
00557     key_type_ref K = ImutInfo::KeyOfValue(V);
00558     key_type_ref KCurrent = ImutInfo::KeyOfValue(Value(T));
00559 
00560     if (ImutInfo::isEqual(K,KCurrent))
00561       return CreateNode(Left(T), V, Right(T));
00562     else if (ImutInfo::isLess(K,KCurrent))
00563       return Balance(Add_internal(V,Left(T)), Value(T), Right(T));
00564     else
00565       return Balance(Left(T), Value(T), Add_internal(V,Right(T)));
00566   }
00567 
00568   /// Remove_internal - Creates a new tree that includes all the data
00569   ///  from the original tree except the specified data.  If the
00570   ///  specified data did not exist in the original tree, the original
00571   ///  tree is returned.
00572   TreeTy* Remove_internal(key_type_ref K, TreeTy* T) {
00573     if (isEmpty(T))
00574       return T;
00575 
00576     assert (!T->isMutable());
00577 
00578     key_type_ref KCurrent = ImutInfo::KeyOfValue(Value(T));
00579 
00580     if (ImutInfo::isEqual(K,KCurrent))
00581       return CombineLeftRightTrees(Left(T),Right(T));
00582     else if (ImutInfo::isLess(K,KCurrent))
00583       return Balance(Remove_internal(K,Left(T)), Value(T), Right(T));
00584     else
00585       return Balance(Left(T), Value(T), Remove_internal(K,Right(T)));
00586   }
00587 
00588   TreeTy* CombineLeftRightTrees(TreeTy* L, TreeTy* R) {
00589     if (isEmpty(L)) return R;
00590     if (isEmpty(R)) return L;
00591 
00592     TreeTy* OldNode;
00593     TreeTy* NewRight = RemoveMinBinding(R,OldNode);
00594     return Balance(L,Value(OldNode),NewRight);
00595   }
00596 
00597   TreeTy* RemoveMinBinding(TreeTy* T, TreeTy*& NodeRemoved) {
00598     assert (!isEmpty(T));
00599 
00600     if (isEmpty(Left(T))) {
00601       NodeRemoved = T;
00602       return Right(T);
00603     }
00604 
00605     return Balance(RemoveMinBinding(Left(T),NodeRemoved),Value(T),Right(T));
00606   }
00607 
00608   /// MarkImmutable - Clears the mutable bits of a root and all of its
00609   ///  descendants.
00610   void MarkImmutable(TreeTy* T) {
00611     if (!T || !T->isMutable())
00612       return;
00613 
00614     T->MarkImmutable();
00615     MarkImmutable(Left(T));
00616     MarkImmutable(Right(T));
00617 
00618     // Now that the node is immutable it can safely be inserted
00619     // into the node cache.
00620     llvm::FoldingSetNodeID ID;
00621     ID.AddInteger(T->ComputeDigest());
00622     Cache.InsertNode(T, (void*) &*Cache.bucket_end(ID.ComputeHash()));
00623   }
00624 };
00625 
00626 
00627 //===----------------------------------------------------------------------===//
00628 // Immutable AVL-Tree Iterators.
00629 //===----------------------------------------------------------------------===//
00630 
00631 template <typename ImutInfo>
00632 class ImutAVLTreeGenericIterator {
00633   SmallVector<uintptr_t,20> stack;
00634 public:
00635   enum VisitFlag { VisitedNone=0x0, VisitedLeft=0x1, VisitedRight=0x3,
00636                    Flags=0x3 };
00637 
00638   typedef ImutAVLTree<ImutInfo> TreeTy;
00639   typedef ImutAVLTreeGenericIterator<ImutInfo> _Self;
00640 
00641   inline ImutAVLTreeGenericIterator() {}
00642   inline ImutAVLTreeGenericIterator(const TreeTy* Root) {
00643     if (Root) stack.push_back(reinterpret_cast<uintptr_t>(Root));
00644   }
00645 
00646   TreeTy* operator*() const {
00647     assert (!stack.empty());
00648     return reinterpret_cast<TreeTy*>(stack.back() & ~Flags);
00649   }
00650 
00651   uintptr_t getVisitState() {
00652     assert (!stack.empty());
00653     return stack.back() & Flags;
00654   }
00655 
00656 
00657   bool AtEnd() const { return stack.empty(); }
00658 
00659   bool AtBeginning() const {
00660     return stack.size() == 1 && getVisitState() == VisitedNone;
00661   }
00662 
00663   void SkipToParent() {
00664     assert (!stack.empty());
00665     stack.pop_back();
00666 
00667     if (stack.empty())
00668       return;
00669 
00670     switch (getVisitState()) {
00671       case VisitedNone:
00672         stack.back() |= VisitedLeft;
00673         break;
00674       case VisitedLeft:
00675         stack.back() |= VisitedRight;
00676         break;
00677       default:
00678         assert (false && "Unreachable.");
00679     }
00680   }
00681 
00682   inline bool operator==(const _Self& x) const {
00683     if (stack.size() != x.stack.size())
00684       return false;
00685 
00686     for (unsigned i = 0 ; i < stack.size(); i++)
00687       if (stack[i] != x.stack[i])
00688         return false;
00689 
00690     return true;
00691   }
00692 
00693   inline bool operator!=(const _Self& x) const { return !operator==(x); }
00694 
00695   _Self& operator++() {
00696     assert (!stack.empty());
00697 
00698     TreeTy* Current = reinterpret_cast<TreeTy*>(stack.back() & ~Flags);
00699     assert (Current);
00700 
00701     switch (getVisitState()) {
00702       case VisitedNone:
00703         if (TreeTy* L = Current->getLeft())
00704           stack.push_back(reinterpret_cast<uintptr_t>(L));
00705         else
00706           stack.back() |= VisitedLeft;
00707 
00708         break;
00709 
00710       case VisitedLeft:
00711         if (TreeTy* R = Current->getRight())
00712           stack.push_back(reinterpret_cast<uintptr_t>(R));
00713         else
00714           stack.back() |= VisitedRight;
00715 
00716         break;
00717 
00718       case VisitedRight:
00719         SkipToParent();
00720         break;
00721 
00722       default:
00723         assert (false && "Unreachable.");
00724     }
00725 
00726     return *this;
00727   }
00728 
00729   _Self& operator--() {
00730     assert (!stack.empty());
00731 
00732     TreeTy* Current = reinterpret_cast<TreeTy*>(stack.back() & ~Flags);
00733     assert (Current);
00734 
00735     switch (getVisitState()) {
00736       case VisitedNone:
00737         stack.pop_back();
00738         break;
00739 
00740       case VisitedLeft:
00741         stack.back() &= ~Flags; // Set state to "VisitedNone."
00742 
00743         if (TreeTy* L = Current->getLeft())
00744           stack.push_back(reinterpret_cast<uintptr_t>(L) | VisitedRight);
00745 
00746         break;
00747 
00748       case VisitedRight:
00749         stack.back() &= ~Flags;
00750         stack.back() |= VisitedLeft;
00751 
00752         if (TreeTy* R = Current->getRight())
00753           stack.push_back(reinterpret_cast<uintptr_t>(R) | VisitedRight);
00754 
00755         break;
00756 
00757       default:
00758         assert (false && "Unreachable.");
00759     }
00760 
00761     return *this;
00762   }
00763 };
00764 
00765 template <typename ImutInfo>
00766 class ImutAVLTreeInOrderIterator {
00767   typedef ImutAVLTreeGenericIterator<ImutInfo> InternalIteratorTy;
00768   InternalIteratorTy InternalItr;
00769 
00770 public:
00771   typedef ImutAVLTree<ImutInfo> TreeTy;
00772   typedef ImutAVLTreeInOrderIterator<ImutInfo> _Self;
00773 
00774   ImutAVLTreeInOrderIterator(const TreeTy* Root) : InternalItr(Root) {
00775     if (Root) operator++(); // Advance to first element.
00776   }
00777 
00778   ImutAVLTreeInOrderIterator() : InternalItr() {}
00779 
00780   inline bool operator==(const _Self& x) const {
00781     return InternalItr == x.InternalItr;
00782   }
00783 
00784   inline bool operator!=(const _Self& x) const { return !operator==(x); }
00785 
00786   inline TreeTy* operator*() const { return *InternalItr; }
00787   inline TreeTy* operator->() const { return *InternalItr; }
00788 
00789   inline _Self& operator++() {
00790     do ++InternalItr;
00791     while (!InternalItr.AtEnd() &&
00792            InternalItr.getVisitState() != InternalIteratorTy::VisitedLeft);
00793 
00794     return *this;
00795   }
00796 
00797   inline _Self& operator--() {
00798     do --InternalItr;
00799     while (!InternalItr.AtBeginning() &&
00800            InternalItr.getVisitState() != InternalIteratorTy::VisitedLeft);
00801 
00802     return *this;
00803   }
00804 
00805   inline void SkipSubTree() {
00806     InternalItr.SkipToParent();
00807 
00808     while (!InternalItr.AtEnd() &&
00809            InternalItr.getVisitState() != InternalIteratorTy::VisitedLeft)
00810       ++InternalItr;
00811   }
00812 };
00813 
00814 //===----------------------------------------------------------------------===//
00815 // Trait classes for Profile information.
00816 //===----------------------------------------------------------------------===//
00817 
00818 /// Generic profile template.  The default behavior is to invoke the
00819 /// profile method of an object.  Specializations for primitive integers
00820 /// and generic handling of pointers is done below.
00821 template <typename T>
00822 struct ImutProfileInfo {
00823   typedef const T  value_type;
00824   typedef const T& value_type_ref;
00825 
00826   static inline void Profile(FoldingSetNodeID& ID, value_type_ref X) {
00827     FoldingSetTrait<T>::Profile(X,ID);
00828   }
00829 };
00830 
00831 /// Profile traits for integers.
00832 template <typename T>
00833 struct ImutProfileInteger {
00834   typedef const T  value_type;
00835   typedef const T& value_type_ref;
00836 
00837   static inline void Profile(FoldingSetNodeID& ID, value_type_ref X) {
00838     ID.AddInteger(X);
00839   }
00840 };
00841 
00842 #define PROFILE_INTEGER_INFO(X)\
00843 template<> struct ImutProfileInfo<X> : ImutProfileInteger<X> {};
00844 
00845 PROFILE_INTEGER_INFO(char)
00846 PROFILE_INTEGER_INFO(unsigned char)
00847 PROFILE_INTEGER_INFO(short)
00848 PROFILE_INTEGER_INFO(unsigned short)
00849 PROFILE_INTEGER_INFO(unsigned)
00850 PROFILE_INTEGER_INFO(signed)
00851 PROFILE_INTEGER_INFO(long)
00852 PROFILE_INTEGER_INFO(unsigned long)
00853 PROFILE_INTEGER_INFO(long long)
00854 PROFILE_INTEGER_INFO(unsigned long long)
00855 
00856 #undef PROFILE_INTEGER_INFO
00857 
00858 /// Generic profile trait for pointer types.  We treat pointers as
00859 /// references to unique objects.
00860 template <typename T>
00861 struct ImutProfileInfo<T*> {
00862   typedef const T*   value_type;
00863   typedef value_type value_type_ref;
00864 
00865   static inline void Profile(FoldingSetNodeID &ID, value_type_ref X) {
00866     ID.AddPointer(X);
00867   }
00868 };
00869 
00870 //===----------------------------------------------------------------------===//
00871 // Trait classes that contain element comparison operators and type
00872 //  definitions used by ImutAVLTree, ImmutableSet, and ImmutableMap.  These
00873 //  inherit from the profile traits (ImutProfileInfo) to include operations
00874 //  for element profiling.
00875 //===----------------------------------------------------------------------===//
00876 
00877 
00878 /// ImutContainerInfo - Generic definition of comparison operations for
00879 ///   elements of immutable containers that defaults to using
00880 ///   std::equal_to<> and std::less<> to perform comparison of elements.
00881 template <typename T>
00882 struct ImutContainerInfo : public ImutProfileInfo<T> {
00883   typedef typename ImutProfileInfo<T>::value_type      value_type;
00884   typedef typename ImutProfileInfo<T>::value_type_ref  value_type_ref;
00885   typedef value_type      key_type;
00886   typedef value_type_ref  key_type_ref;
00887   typedef bool            data_type;
00888   typedef bool            data_type_ref;
00889 
00890   static inline key_type_ref KeyOfValue(value_type_ref D) { return D; }
00891   static inline data_type_ref DataOfValue(value_type_ref) { return true; }
00892 
00893   static inline bool isEqual(key_type_ref LHS, key_type_ref RHS) {
00894     return std::equal_to<key_type>()(LHS,RHS);
00895   }
00896 
00897   static inline bool isLess(key_type_ref LHS, key_type_ref RHS) {
00898     return std::less<key_type>()(LHS,RHS);
00899   }
00900 
00901   static inline bool isDataEqual(data_type_ref,data_type_ref) { return true; }
00902 };
00903 
00904 /// ImutContainerInfo - Specialization for pointer values to treat pointers
00905 ///  as references to unique objects.  Pointers are thus compared by
00906 ///  their addresses.
00907 template <typename T>
00908 struct ImutContainerInfo<T*> : public ImutProfileInfo<T*> {
00909   typedef typename ImutProfileInfo<T*>::value_type      value_type;
00910   typedef typename ImutProfileInfo<T*>::value_type_ref  value_type_ref;
00911   typedef value_type      key_type;
00912   typedef value_type_ref  key_type_ref;
00913   typedef bool            data_type;
00914   typedef bool            data_type_ref;
00915 
00916   static inline key_type_ref KeyOfValue(value_type_ref D) { return D; }
00917   static inline data_type_ref DataOfValue(value_type_ref) { return true; }
00918 
00919   static inline bool isEqual(key_type_ref LHS, key_type_ref RHS) {
00920     return LHS == RHS;
00921   }
00922 
00923   static inline bool isLess(key_type_ref LHS, key_type_ref RHS) {
00924     return LHS < RHS;
00925   }
00926 
00927   static inline bool isDataEqual(data_type_ref,data_type_ref) { return true; }
00928 };
00929 
00930 //===----------------------------------------------------------------------===//
00931 // Immutable Set
00932 //===----------------------------------------------------------------------===//
00933 
00934 template <typename ValT, typename ValInfo = ImutContainerInfo<ValT> >
00935 class ImmutableSet {
00936 public:
00937   typedef typename ValInfo::value_type      value_type;
00938   typedef typename ValInfo::value_type_ref  value_type_ref;
00939   typedef ImutAVLTree<ValInfo> TreeTy;
00940 
00941 private:
00942   TreeTy* Root;
00943 
00944 public:
00945   /// Constructs a set from a pointer to a tree root.  In general one
00946   /// should use a Factory object to create sets instead of directly
00947   /// invoking the constructor, but there are cases where make this
00948   /// constructor public is useful.
00949   explicit ImmutableSet(TreeTy* R) : Root(R) {}
00950 
00951   class Factory {
00952     typename TreeTy::Factory F;
00953 
00954   public:
00955     Factory() {}
00956 
00957     Factory(BumpPtrAllocator& Alloc)
00958       : F(Alloc) {}
00959 
00960     /// GetEmptySet - Returns an immutable set that contains no elements.
00961     ImmutableSet GetEmptySet() { return ImmutableSet(F.GetEmptyTree()); }
00962 
00963     /// Add - Creates a new immutable set that contains all of the values
00964     ///  of the original set with the addition of the specified value.  If
00965     ///  the original set already included the value, then the original set is
00966     ///  returned and no memory is allocated.  The time and space complexity
00967     ///  of this operation is logarithmic in the size of the original set.
00968     ///  The memory allocated to represent the set is released when the
00969     ///  factory object that created the set is destroyed.
00970     ImmutableSet Add(ImmutableSet Old, value_type_ref V) {
00971       return ImmutableSet(F.Add(Old.Root,V));
00972     }
00973 
00974     /// Remove - Creates a new immutable set that contains all of the values
00975     ///  of the original set with the exception of the specified value.  If
00976     ///  the original set did not contain the value, the original set is
00977     ///  returned and no memory is allocated.  The time and space complexity
00978     ///  of this operation is logarithmic in the size of the original set.
00979     ///  The memory allocated to represent the set is released when the
00980     ///  factory object that created the set is destroyed.
00981     ImmutableSet Remove(ImmutableSet Old, value_type_ref V) {
00982       return ImmutableSet(F.Remove(Old.Root,V));
00983     }
00984 
00985     BumpPtrAllocator& getAllocator() { return F.getAllocator(); }
00986 
00987   private:
00988     Factory(const Factory& RHS) {};
00989     void operator=(const Factory& RHS) {};
00990   };
00991 
00992   friend class Factory;
00993 
00994   /// contains - Returns true if the set contains the specified value.
00995   bool contains(value_type_ref V) const {
00996     return Root ? Root->contains(V) : false;
00997   }
00998 
00999   bool operator==(ImmutableSet RHS) const {
01000     return Root && RHS.Root ? Root->isEqual(*RHS.Root) : Root == RHS.Root;
01001   }
01002 
01003   bool operator!=(ImmutableSet RHS) const {
01004     return Root && RHS.Root ? Root->isNotEqual(*RHS.Root) : Root != RHS.Root;
01005   }
01006 
01007   TreeTy* getRoot() const { return Root; }
01008 
01009   /// isEmpty - Return true if the set contains no elements.
01010   bool isEmpty() const { return !Root; }
01011 
01012   /// isSingleton - Return true if the set contains exactly one element.
01013   ///   This method runs in constant time.
01014   bool isSingleton() const { return getHeight() == 1; }
01015 
01016   template <typename Callback>
01017   void foreach(Callback& C) { if (Root) Root->foreach(C); }
01018 
01019   template <typename Callback>
01020   void foreach() { if (Root) { Callback C; Root->foreach(C); } }
01021 
01022   //===--------------------------------------------------===//
01023   // Iterators.
01024   //===--------------------------------------------------===//
01025 
01026   class iterator {
01027     typename TreeTy::iterator itr;
01028     iterator(TreeTy* t) : itr(t) {}
01029     friend class ImmutableSet<ValT,ValInfo>;
01030   public:
01031     iterator() {}
01032     inline value_type_ref operator*() const { return itr->getValue(); }
01033     inline iterator& operator++() { ++itr; return *this; }
01034     inline iterator  operator++(int) { iterator tmp(*this); ++itr; return tmp; }
01035     inline iterator& operator--() { --itr; return *this; }
01036     inline iterator  operator--(int) { iterator tmp(*this); --itr; return tmp; }
01037     inline bool operator==(const iterator& RHS) const { return RHS.itr == itr; }
01038     inline bool operator!=(const iterator& RHS) const { return RHS.itr != itr; }
01039     inline value_type *operator->() const { return &(operator*()); }
01040   };
01041 
01042   iterator begin() const { return iterator(Root); }
01043   iterator end() const { return iterator(); }
01044 
01045   //===--------------------------------------------------===//
01046   // Utility methods.
01047   //===--------------------------------------------------===//
01048 
01049   inline unsigned getHeight() const { return Root ? Root->getHeight() : 0; }
01050 
01051   static inline void Profile(FoldingSetNodeID& ID, const ImmutableSet& S) {
01052     ID.AddPointer(S.Root);
01053   }
01054 
01055   inline void Profile(FoldingSetNodeID& ID) const {
01056     return Profile(ID,*this);
01057   }
01058 
01059   //===--------------------------------------------------===//
01060   // For testing.
01061   //===--------------------------------------------------===//
01062 
01063   void verify() const { if (Root) Root->verify(); }
01064 };
01065 
01066 } // end namespace llvm
01067 
01068 #endif