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