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_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 inline
00297   uint32_t computeDigest(ImutAVLTree* L, ImutAVLTree* R, 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   inline 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 inline unsigned maskCacheIndex(unsigned I) {
00433     return (I & ~0x02);
00434   }
00435 
00436   unsigned incrementHeight(TreeTy* L, TreeTy* R) const {
00437     unsigned hl = getHeight(L);
00438     unsigned hr = getHeight(R);
00439     return (hl > hr ? hl : hr) + 1;
00440   }
00441 
00442   static bool compareTreeWithSection(TreeTy* T,
00443                                      typename TreeTy::iterator& TI,
00444                                      typename TreeTy::iterator& TE) {
00445     typename TreeTy::iterator I = T->begin(), E = T->end();
00446     for ( ; I!=E ; ++I, ++TI) {
00447       if (TI == TE || !I->isElementEqual(*TI))
00448         return false;
00449     }
00450     return true;
00451   }
00452 
00453   //===--------------------------------------------------===//
00454   // "createNode" is used to generate new tree roots that link
00455   // to other trees.  The functon may also simply move links
00456   // in an existing root if that root is still marked mutable.
00457   // This is necessary because otherwise our balancing code
00458   // would leak memory as it would create nodes that are
00459   // then discarded later before the finished tree is
00460   // returned to the caller.
00461   //===--------------------------------------------------===//
00462 
00463   TreeTy* createNode(TreeTy* L, value_type_ref V, TreeTy* R) {
00464     BumpPtrAllocator& A = getAllocator();
00465     TreeTy* T;
00466     if (!freeNodes.empty()) {
00467       T = freeNodes.back();
00468       freeNodes.pop_back();
00469       assert(T != L);
00470       assert(T != R);
00471     } else {
00472       T = (TreeTy*) A.Allocate<TreeTy>();
00473     }
00474     new (T) TreeTy(this, L, R, V, incrementHeight(L,R));
00475     createdNodes.push_back(T);
00476     return T;
00477   }
00478 
00479   TreeTy* createNode(TreeTy* newLeft, TreeTy* oldTree, TreeTy* newRight) {
00480     return createNode(newLeft, getValue(oldTree), newRight);
00481   }
00482 
00483   void recoverNodes() {
00484     for (unsigned i = 0, n = createdNodes.size(); i < n; ++i) {
00485       TreeTy *N = createdNodes[i];
00486       if (N->isMutable() && N->refCount == 0)
00487         N->destroy();
00488     }
00489     createdNodes.clear();
00490   }
00491 
00492   /// balanceTree - Used by add_internal and remove_internal to
00493   ///  balance a newly created tree.
00494   TreeTy* balanceTree(TreeTy* L, value_type_ref V, TreeTy* R) {
00495     unsigned hl = getHeight(L);
00496     unsigned hr = getHeight(R);
00497 
00498     if (hl > hr + 2) {
00499       assert(!isEmpty(L) && "Left tree cannot be empty to have a height >= 2");
00500 
00501       TreeTy *LL = getLeft(L);
00502       TreeTy *LR = getRight(L);
00503 
00504       if (getHeight(LL) >= getHeight(LR))
00505         return createNode(LL, L, createNode(LR,V,R));
00506 
00507       assert(!isEmpty(LR) && "LR cannot be empty because it has a height >= 1");
00508 
00509       TreeTy *LRL = getLeft(LR);
00510       TreeTy *LRR = getRight(LR);
00511 
00512       return createNode(createNode(LL,L,LRL), LR, createNode(LRR,V,R));
00513     }
00514 
00515     if (hr > hl + 2) {
00516       assert(!isEmpty(R) && "Right tree cannot be empty to have a height >= 2");
00517 
00518       TreeTy *RL = getLeft(R);
00519       TreeTy *RR = getRight(R);
00520 
00521       if (getHeight(RR) >= getHeight(RL))
00522         return createNode(createNode(L,V,RL), R, RR);
00523 
00524       assert(!isEmpty(RL) && "RL cannot be empty because it has a height >= 1");
00525 
00526       TreeTy *RLL = getLeft(RL);
00527       TreeTy *RLR = getRight(RL);
00528 
00529       return createNode(createNode(L,V,RLL), RL, createNode(RLR,R,RR));
00530     }
00531 
00532     return createNode(L,V,R);
00533   }
00534 
00535   /// add_internal - Creates a new tree that includes the specified
00536   ///  data and the data from the original tree.  If the original tree
00537   ///  already contained the data item, the original tree is returned.
00538   TreeTy* add_internal(value_type_ref V, TreeTy* T) {
00539     if (isEmpty(T))
00540       return createNode(T, V, T);
00541     assert(!T->isMutable());
00542 
00543     key_type_ref K = ImutInfo::KeyOfValue(V);
00544     key_type_ref KCurrent = ImutInfo::KeyOfValue(getValue(T));
00545 
00546     if (ImutInfo::isEqual(K,KCurrent))
00547       return createNode(getLeft(T), V, getRight(T));
00548     else if (ImutInfo::isLess(K,KCurrent))
00549       return balanceTree(add_internal(V, getLeft(T)), getValue(T), getRight(T));
00550     else
00551       return balanceTree(getLeft(T), getValue(T), add_internal(V, getRight(T)));
00552   }
00553 
00554   /// remove_internal - Creates a new tree that includes all the data
00555   ///  from the original tree except the specified data.  If the
00556   ///  specified data did not exist in the original tree, the original
00557   ///  tree is returned.
00558   TreeTy* remove_internal(key_type_ref K, TreeTy* T) {
00559     if (isEmpty(T))
00560       return T;
00561 
00562     assert(!T->isMutable());
00563 
00564     key_type_ref KCurrent = ImutInfo::KeyOfValue(getValue(T));
00565 
00566     if (ImutInfo::isEqual(K,KCurrent)) {
00567       return combineTrees(getLeft(T), getRight(T));
00568     } else if (ImutInfo::isLess(K,KCurrent)) {
00569       return balanceTree(remove_internal(K, getLeft(T)),
00570                                             getValue(T), getRight(T));
00571     } else {
00572       return balanceTree(getLeft(T), getValue(T),
00573                          remove_internal(K, getRight(T)));
00574     }
00575   }
00576 
00577   TreeTy* combineTrees(TreeTy* L, TreeTy* R) {
00578     if (isEmpty(L))
00579       return R;
00580     if (isEmpty(R))
00581       return L;
00582     TreeTy* OldNode;
00583     TreeTy* newRight = removeMinBinding(R,OldNode);
00584     return balanceTree(L, getValue(OldNode), newRight);
00585   }
00586 
00587   TreeTy* removeMinBinding(TreeTy* T, TreeTy*& Noderemoved) {
00588     assert(!isEmpty(T));
00589     if (isEmpty(getLeft(T))) {
00590       Noderemoved = T;
00591       return getRight(T);
00592     }
00593     return balanceTree(removeMinBinding(getLeft(T), Noderemoved),
00594                        getValue(T), getRight(T));
00595   }
00596 
00597   /// markImmutable - Clears the mutable bits of a root and all of its
00598   ///  descendants.
00599   void markImmutable(TreeTy* T) {
00600     if (!T || !T->isMutable())
00601       return;
00602     T->markImmutable();
00603     markImmutable(getLeft(T));
00604     markImmutable(getRight(T));
00605   }
00606 
00607 public:
00608   TreeTy *getCanonicalTree(TreeTy *TNew) {
00609     if (!TNew)
00610       return nullptr;
00611 
00612     if (TNew->IsCanonicalized)
00613       return TNew;
00614 
00615     // Search the hashtable for another tree with the same digest, and
00616     // if find a collision compare those trees by their contents.
00617     unsigned digest = TNew->computeDigest();
00618     TreeTy *&entry = Cache[maskCacheIndex(digest)];
00619     do {
00620       if (!entry)
00621         break;
00622       for (TreeTy *T = entry ; T != nullptr; T = T->next) {
00623         // Compare the Contents('T') with Contents('TNew')
00624         typename TreeTy::iterator TI = T->begin(), TE = T->end();
00625         if (!compareTreeWithSection(TNew, TI, TE))
00626           continue;
00627         if (TI != TE)
00628           continue; // T has more contents than TNew.
00629         // Trees did match!  Return 'T'.
00630         if (TNew->refCount == 0)
00631           TNew->destroy();
00632         return T;
00633       }
00634       entry->prev = TNew;
00635       TNew->next = entry;
00636     }
00637     while (false);
00638 
00639     entry = TNew;
00640     TNew->IsCanonicalized = true;
00641     return TNew;
00642   }
00643 };
00644 
00645 //===----------------------------------------------------------------------===//
00646 // Immutable AVL-Tree Iterators.
00647 //===----------------------------------------------------------------------===//
00648 
00649 template <typename ImutInfo>
00650 class ImutAVLTreeGenericIterator {
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   typedef ImutAVLTreeGenericIterator<ImutInfo> _Self;
00658 
00659   inline ImutAVLTreeGenericIterator() {}
00660   inline ImutAVLTreeGenericIterator(const TreeTy* Root) {
00661     if (Root) stack.push_back(reinterpret_cast<uintptr_t>(Root));
00662   }
00663 
00664   TreeTy* operator*() const {
00665     assert(!stack.empty());
00666     return reinterpret_cast<TreeTy*>(stack.back() & ~Flags);
00667   }
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   inline bool operator==(const _Self& x) const {
00699     return stack == x.stack;
00700   }
00701 
00702   inline bool operator!=(const _Self& x) const { return !operator==(x); }
00703 
00704   _Self& operator++() {
00705     assert(!stack.empty());
00706     TreeTy* Current = reinterpret_cast<TreeTy*>(stack.back() & ~Flags);
00707     assert(Current);
00708     switch (getVisitState()) {
00709       case VisitedNone:
00710         if (TreeTy* L = Current->getLeft())
00711           stack.push_back(reinterpret_cast<uintptr_t>(L));
00712         else
00713           stack.back() |= VisitedLeft;
00714         break;
00715       case VisitedLeft:
00716         if (TreeTy* R = Current->getRight())
00717           stack.push_back(reinterpret_cast<uintptr_t>(R));
00718         else
00719           stack.back() |= VisitedRight;
00720         break;
00721       case VisitedRight:
00722         skipToParent();
00723         break;
00724       default:
00725         llvm_unreachable("Unreachable.");
00726     }
00727     return *this;
00728   }
00729 
00730   _Self& operator--() {
00731     assert(!stack.empty());
00732     TreeTy* Current = reinterpret_cast<TreeTy*>(stack.back() & ~Flags);
00733     assert(Current);
00734     switch (getVisitState()) {
00735       case VisitedNone:
00736         stack.pop_back();
00737         break;
00738       case VisitedLeft:
00739         stack.back() &= ~Flags; // Set state to "VisitedNone."
00740         if (TreeTy* L = Current->getLeft())
00741           stack.push_back(reinterpret_cast<uintptr_t>(L) | VisitedRight);
00742         break;
00743       case VisitedRight:
00744         stack.back() &= ~Flags;
00745         stack.back() |= VisitedLeft;
00746         if (TreeTy* R = Current->getRight())
00747           stack.push_back(reinterpret_cast<uintptr_t>(R) | VisitedRight);
00748         break;
00749       default:
00750         llvm_unreachable("Unreachable.");
00751     }
00752     return *this;
00753   }
00754 };
00755 
00756 template <typename ImutInfo>
00757 class ImutAVLTreeInOrderIterator {
00758   typedef ImutAVLTreeGenericIterator<ImutInfo> InternalIteratorTy;
00759   InternalIteratorTy InternalItr;
00760 
00761 public:
00762   typedef ImutAVLTree<ImutInfo> TreeTy;
00763   typedef ImutAVLTreeInOrderIterator<ImutInfo> _Self;
00764 
00765   ImutAVLTreeInOrderIterator(const TreeTy* Root) : InternalItr(Root) {
00766     if (Root) operator++(); // Advance to first element.
00767   }
00768 
00769   ImutAVLTreeInOrderIterator() : InternalItr() {}
00770 
00771   inline bool operator==(const _Self& x) const {
00772     return InternalItr == x.InternalItr;
00773   }
00774 
00775   inline bool operator!=(const _Self& x) const { return !operator==(x); }
00776 
00777   inline TreeTy* operator*() const { return *InternalItr; }
00778   inline TreeTy* operator->() const { return *InternalItr; }
00779 
00780   inline _Self& operator++() {
00781     do ++InternalItr;
00782     while (!InternalItr.atEnd() &&
00783            InternalItr.getVisitState() != InternalIteratorTy::VisitedLeft);
00784 
00785     return *this;
00786   }
00787 
00788   inline _Self& operator--() {
00789     do --InternalItr;
00790     while (!InternalItr.atBeginning() &&
00791            InternalItr.getVisitState() != InternalIteratorTy::VisitedLeft);
00792 
00793     return *this;
00794   }
00795 
00796   inline void skipSubTree() {
00797     InternalItr.skipToParent();
00798 
00799     while (!InternalItr.atEnd() &&
00800            InternalItr.getVisitState() != InternalIteratorTy::VisitedLeft)
00801       ++InternalItr;
00802   }
00803 };
00804 
00805 //===----------------------------------------------------------------------===//
00806 // Trait classes for Profile information.
00807 //===----------------------------------------------------------------------===//
00808 
00809 /// Generic profile template.  The default behavior is to invoke the
00810 /// profile method of an object.  Specializations for primitive integers
00811 /// and generic handling of pointers is done below.
00812 template <typename T>
00813 struct ImutProfileInfo {
00814   typedef const T  value_type;
00815   typedef const T& value_type_ref;
00816 
00817   static inline void Profile(FoldingSetNodeID& ID, value_type_ref X) {
00818     FoldingSetTrait<T>::Profile(X,ID);
00819   }
00820 };
00821 
00822 /// Profile traits for integers.
00823 template <typename T>
00824 struct ImutProfileInteger {
00825   typedef const T  value_type;
00826   typedef const T& value_type_ref;
00827 
00828   static inline void Profile(FoldingSetNodeID& ID, value_type_ref X) {
00829     ID.AddInteger(X);
00830   }
00831 };
00832 
00833 #define PROFILE_INTEGER_INFO(X)\
00834 template<> struct ImutProfileInfo<X> : ImutProfileInteger<X> {};
00835 
00836 PROFILE_INTEGER_INFO(char)
00837 PROFILE_INTEGER_INFO(unsigned char)
00838 PROFILE_INTEGER_INFO(short)
00839 PROFILE_INTEGER_INFO(unsigned short)
00840 PROFILE_INTEGER_INFO(unsigned)
00841 PROFILE_INTEGER_INFO(signed)
00842 PROFILE_INTEGER_INFO(long)
00843 PROFILE_INTEGER_INFO(unsigned long)
00844 PROFILE_INTEGER_INFO(long long)
00845 PROFILE_INTEGER_INFO(unsigned long long)
00846 
00847 #undef PROFILE_INTEGER_INFO
00848 
00849 /// Profile traits for booleans.
00850 template <>
00851 struct ImutProfileInfo<bool> {
00852   typedef const bool  value_type;
00853   typedef const bool& value_type_ref;
00854 
00855   static inline void Profile(FoldingSetNodeID& ID, value_type_ref X) {
00856     ID.AddBoolean(X);
00857   }
00858 };
00859 
00860 
00861 /// Generic profile trait for pointer types.  We treat pointers as
00862 /// references to unique objects.
00863 template <typename T>
00864 struct ImutProfileInfo<T*> {
00865   typedef const T*   value_type;
00866   typedef value_type value_type_ref;
00867 
00868   static inline void Profile(FoldingSetNodeID &ID, value_type_ref X) {
00869     ID.AddPointer(X);
00870   }
00871 };
00872 
00873 //===----------------------------------------------------------------------===//
00874 // Trait classes that contain element comparison operators and type
00875 //  definitions used by ImutAVLTree, ImmutableSet, and ImmutableMap.  These
00876 //  inherit from the profile traits (ImutProfileInfo) to include operations
00877 //  for element profiling.
00878 //===----------------------------------------------------------------------===//
00879 
00880 
00881 /// ImutContainerInfo - Generic definition of comparison operations for
00882 ///   elements of immutable containers that defaults to using
00883 ///   std::equal_to<> and std::less<> to perform comparison of elements.
00884 template <typename T>
00885 struct ImutContainerInfo : public ImutProfileInfo<T> {
00886   typedef typename ImutProfileInfo<T>::value_type      value_type;
00887   typedef typename ImutProfileInfo<T>::value_type_ref  value_type_ref;
00888   typedef value_type      key_type;
00889   typedef value_type_ref  key_type_ref;
00890   typedef bool            data_type;
00891   typedef bool            data_type_ref;
00892 
00893   static inline key_type_ref KeyOfValue(value_type_ref D) { return D; }
00894   static inline data_type_ref DataOfValue(value_type_ref) { return true; }
00895 
00896   static inline bool isEqual(key_type_ref LHS, key_type_ref RHS) {
00897     return std::equal_to<key_type>()(LHS,RHS);
00898   }
00899 
00900   static inline bool isLess(key_type_ref LHS, key_type_ref RHS) {
00901     return std::less<key_type>()(LHS,RHS);
00902   }
00903 
00904   static inline bool isDataEqual(data_type_ref,data_type_ref) { return true; }
00905 };
00906 
00907 /// ImutContainerInfo - Specialization for pointer values to treat pointers
00908 ///  as references to unique objects.  Pointers are thus compared by
00909 ///  their addresses.
00910 template <typename T>
00911 struct ImutContainerInfo<T*> : public ImutProfileInfo<T*> {
00912   typedef typename ImutProfileInfo<T*>::value_type      value_type;
00913   typedef typename ImutProfileInfo<T*>::value_type_ref  value_type_ref;
00914   typedef value_type      key_type;
00915   typedef value_type_ref  key_type_ref;
00916   typedef bool            data_type;
00917   typedef bool            data_type_ref;
00918 
00919   static inline key_type_ref KeyOfValue(value_type_ref D) { return D; }
00920   static inline data_type_ref DataOfValue(value_type_ref) { return true; }
00921 
00922   static inline bool isEqual(key_type_ref LHS, key_type_ref RHS) {
00923     return LHS == RHS;
00924   }
00925 
00926   static inline bool isLess(key_type_ref LHS, key_type_ref RHS) {
00927     return LHS < RHS;
00928   }
00929 
00930   static inline bool isDataEqual(data_type_ref,data_type_ref) { return true; }
00931 };
00932 
00933 //===----------------------------------------------------------------------===//
00934 // Immutable Set
00935 //===----------------------------------------------------------------------===//
00936 
00937 template <typename ValT, typename ValInfo = ImutContainerInfo<ValT> >
00938 class ImmutableSet {
00939 public:
00940   typedef typename ValInfo::value_type      value_type;
00941   typedef typename ValInfo::value_type_ref  value_type_ref;
00942   typedef ImutAVLTree<ValInfo> TreeTy;
00943 
00944 private:
00945   TreeTy *Root;
00946 
00947 public:
00948   /// Constructs a set from a pointer to a tree root.  In general one
00949   /// should use a Factory object to create sets instead of directly
00950   /// invoking the constructor, but there are cases where make this
00951   /// constructor public is useful.
00952   explicit ImmutableSet(TreeTy* R) : Root(R) {
00953     if (Root) { Root->retain(); }
00954   }
00955   ImmutableSet(const ImmutableSet &X) : Root(X.Root) {
00956     if (Root) { Root->retain(); }
00957   }
00958   ImmutableSet &operator=(const ImmutableSet &X) {
00959     if (Root != X.Root) {
00960       if (X.Root) { X.Root->retain(); }
00961       if (Root) { Root->release(); }
00962       Root = X.Root;
00963     }
00964     return *this;
00965   }
00966   ~ImmutableSet() {
00967     if (Root) { Root->release(); }
00968   }
00969 
00970   class Factory {
00971     typename TreeTy::Factory F;
00972     const bool Canonicalize;
00973 
00974   public:
00975     Factory(bool canonicalize = true)
00976       : Canonicalize(canonicalize) {}
00977 
00978     Factory(BumpPtrAllocator& Alloc, bool canonicalize = true)
00979       : F(Alloc), Canonicalize(canonicalize) {}
00980 
00981     /// getEmptySet - Returns an immutable set that contains no elements.
00982     ImmutableSet getEmptySet() {
00983       return ImmutableSet(F.getEmptyTree());
00984     }
00985 
00986     /// add - Creates a new immutable set that contains all of the values
00987     ///  of the original set with the addition of the specified value.  If
00988     ///  the original set already included the value, then the original set is
00989     ///  returned and no memory is allocated.  The time and space complexity
00990     ///  of this operation is logarithmic in the size of the original set.
00991     ///  The memory allocated to represent the set is released when the
00992     ///  factory object that created the set is destroyed.
00993     ImmutableSet add(ImmutableSet Old, value_type_ref V) {
00994       TreeTy *NewT = F.add(Old.Root, V);
00995       return ImmutableSet(Canonicalize ? F.getCanonicalTree(NewT) : NewT);
00996     }
00997 
00998     /// remove - Creates a new immutable set that contains all of the values
00999     ///  of the original set with the exception of the specified value.  If
01000     ///  the original set did not contain the value, the original set is
01001     ///  returned and no memory is allocated.  The time and space complexity
01002     ///  of this operation is logarithmic in the size of the original set.
01003     ///  The memory allocated to represent the set is released when the
01004     ///  factory object that created the set is destroyed.
01005     ImmutableSet remove(ImmutableSet Old, value_type_ref V) {
01006       TreeTy *NewT = F.remove(Old.Root, V);
01007       return ImmutableSet(Canonicalize ? F.getCanonicalTree(NewT) : NewT);
01008     }
01009 
01010     BumpPtrAllocator& getAllocator() { return F.getAllocator(); }
01011 
01012     typename TreeTy::Factory *getTreeFactory() const {
01013       return const_cast<typename TreeTy::Factory *>(&F);
01014     }
01015 
01016   private:
01017     Factory(const Factory& RHS) LLVM_DELETED_FUNCTION;
01018     void operator=(const Factory& RHS) LLVM_DELETED_FUNCTION;
01019   };
01020 
01021   friend class Factory;
01022 
01023   /// Returns true if the set contains the specified value.
01024   bool contains(value_type_ref V) const {
01025     return Root ? Root->contains(V) : false;
01026   }
01027 
01028   bool operator==(const ImmutableSet &RHS) const {
01029     return Root && RHS.Root ? Root->isEqual(*RHS.Root) : Root == RHS.Root;
01030   }
01031 
01032   bool operator!=(const ImmutableSet &RHS) const {
01033     return Root && RHS.Root ? Root->isNotEqual(*RHS.Root) : Root != RHS.Root;
01034   }
01035 
01036   TreeTy *getRoot() {
01037     if (Root) { Root->retain(); }
01038     return Root;
01039   }
01040 
01041   TreeTy *getRootWithoutRetain() const {
01042     return Root;
01043   }
01044 
01045   /// isEmpty - Return true if the set contains no elements.
01046   bool isEmpty() const { return !Root; }
01047 
01048   /// isSingleton - Return true if the set contains exactly one element.
01049   ///   This method runs in constant time.
01050   bool isSingleton() const { return getHeight() == 1; }
01051 
01052   template <typename Callback>
01053   void foreach(Callback& C) { if (Root) Root->foreach(C); }
01054 
01055   template <typename Callback>
01056   void foreach() { if (Root) { Callback C; Root->foreach(C); } }
01057 
01058   //===--------------------------------------------------===//
01059   // Iterators.
01060   //===--------------------------------------------------===//
01061 
01062   class iterator {
01063     typename TreeTy::iterator itr;
01064 
01065     iterator() {}
01066     iterator(TreeTy* t) : itr(t) {}
01067     friend class ImmutableSet<ValT,ValInfo>;
01068 
01069   public:
01070     typedef ptrdiff_t difference_type;
01071     typedef typename ImmutableSet<ValT,ValInfo>::value_type value_type;
01072     typedef typename ImmutableSet<ValT,ValInfo>::value_type_ref reference;
01073     typedef typename iterator::value_type *pointer;
01074     typedef std::bidirectional_iterator_tag iterator_category;
01075 
01076     typename iterator::reference operator*() const { return itr->getValue(); }
01077     typename iterator::pointer   operator->() const { return &(operator*()); }
01078 
01079     iterator& operator++() { ++itr; return *this; }
01080     iterator  operator++(int) { iterator tmp(*this); ++itr; return tmp; }
01081     iterator& operator--() { --itr; return *this; }
01082     iterator  operator--(int) { iterator tmp(*this); --itr; return tmp; }
01083 
01084     bool operator==(const iterator& RHS) const { return RHS.itr == itr; }
01085     bool operator!=(const iterator& RHS) const { return RHS.itr != itr; }
01086   };
01087 
01088   iterator begin() const { return iterator(Root); }
01089   iterator end() const { return iterator(); }
01090 
01091   //===--------------------------------------------------===//
01092   // Utility methods.
01093   //===--------------------------------------------------===//
01094 
01095   unsigned getHeight() const { return Root ? Root->getHeight() : 0; }
01096 
01097   static inline void Profile(FoldingSetNodeID& ID, const ImmutableSet& S) {
01098     ID.AddPointer(S.Root);
01099   }
01100 
01101   inline void Profile(FoldingSetNodeID& ID) const {
01102     return Profile(ID,*this);
01103   }
01104 
01105   //===--------------------------------------------------===//
01106   // For testing.
01107   //===--------------------------------------------------===//
01108 
01109   void validateTree() const { if (Root) Root->validateTree(); }
01110 };
01111 
01112 // NOTE: This may some day replace the current ImmutableSet.
01113 template <typename ValT, typename ValInfo = ImutContainerInfo<ValT> >
01114 class ImmutableSetRef {
01115 public:
01116   typedef typename ValInfo::value_type      value_type;
01117   typedef typename ValInfo::value_type_ref  value_type_ref;
01118   typedef ImutAVLTree<ValInfo> TreeTy;
01119   typedef typename TreeTy::Factory          FactoryTy;
01120 
01121 private:
01122   TreeTy *Root;
01123   FactoryTy *Factory;
01124 
01125 public:
01126   /// Constructs a set from a pointer to a tree root.  In general one
01127   /// should use a Factory object to create sets instead of directly
01128   /// invoking the constructor, but there are cases where make this
01129   /// constructor public is useful.
01130   explicit ImmutableSetRef(TreeTy* R, FactoryTy *F)
01131     : Root(R),
01132       Factory(F) {
01133     if (Root) { Root->retain(); }
01134   }
01135   ImmutableSetRef(const ImmutableSetRef &X)
01136     : Root(X.Root),
01137       Factory(X.Factory) {
01138     if (Root) { Root->retain(); }
01139   }
01140   ImmutableSetRef &operator=(const ImmutableSetRef &X) {
01141     if (Root != X.Root) {
01142       if (X.Root) { X.Root->retain(); }
01143       if (Root) { Root->release(); }
01144       Root = X.Root;
01145       Factory = X.Factory;
01146     }
01147     return *this;
01148   }
01149   ~ImmutableSetRef() {
01150     if (Root) { Root->release(); }
01151   }
01152 
01153   static inline ImmutableSetRef getEmptySet(FactoryTy *F) {
01154     return ImmutableSetRef(0, F);
01155   }
01156 
01157   ImmutableSetRef add(value_type_ref V) {
01158     return ImmutableSetRef(Factory->add(Root, V), Factory);
01159   }
01160 
01161   ImmutableSetRef remove(value_type_ref V) {
01162     return ImmutableSetRef(Factory->remove(Root, V), Factory);
01163   }
01164 
01165   /// Returns true if the set contains the specified value.
01166   bool contains(value_type_ref V) const {
01167     return Root ? Root->contains(V) : false;
01168   }
01169 
01170   ImmutableSet<ValT> asImmutableSet(bool canonicalize = true) const {
01171     return ImmutableSet<ValT>(canonicalize ?
01172                               Factory->getCanonicalTree(Root) : Root);
01173   }
01174 
01175   TreeTy *getRootWithoutRetain() const {
01176     return Root;
01177   }
01178 
01179   bool operator==(const ImmutableSetRef &RHS) const {
01180     return Root && RHS.Root ? Root->isEqual(*RHS.Root) : Root == RHS.Root;
01181   }
01182 
01183   bool operator!=(const ImmutableSetRef &RHS) const {
01184     return Root && RHS.Root ? Root->isNotEqual(*RHS.Root) : Root != RHS.Root;
01185   }
01186 
01187   /// isEmpty - Return true if the set contains no elements.
01188   bool isEmpty() const { return !Root; }
01189 
01190   /// isSingleton - Return true if the set contains exactly one element.
01191   ///   This method runs in constant time.
01192   bool isSingleton() const { return getHeight() == 1; }
01193 
01194   //===--------------------------------------------------===//
01195   // Iterators.
01196   //===--------------------------------------------------===//
01197 
01198   class iterator {
01199     typename</