include/llvm/ADT/ImmutableSet.h

   1 //===--- ImmutableSet.h - Immutable (functional) set interface --*- C++ -*-===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file is distributed under the University of Illinois Open Source
   6 // License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 // This file defines the ImutAVLTree and ImmutableSet classes.
  11 //
  12 //===----------------------------------------------------------------------===//
  13
  14 #ifndef LLVM_ADT_IMSET_H
  15 #define LLVM_ADT_IMSET_H
  16
  17 #include "llvm/Support/Allocator.h"
  18 #include "llvm/ADT/FoldingSet.h"
  19 #include "llvm/System/DataTypes.h"
  20 #include <cassert>
  21 #include <functional>
  22
  23 namespace llvm {
  24
  25 //===----------------------------------------------------------------------===//
  26 // Immutable AVL-Tree Definition.
  27 //===----------------------------------------------------------------------===//
  28
  29 template <typename ImutInfo> class ImutAVLFactory;
  30 template <typename ImutInfo> class ImutIntervalAVLFactory;
  31 template <typename ImutInfo> class ImutAVLTreeInOrderIterator;
  32 template <typename ImutInfo> class ImutAVLTreeGenericIterator;
  33
  34 template <typename ImutInfo >
  35 class ImutAVLTree : public FoldingSetNode {
  36 public:
  37   typedef typename ImutInfo::key_type_ref   key_type_ref;
  38   typedef typename ImutInfo::value_type     value_type;
  39   typedef typename ImutInfo::value_type_ref value_type_ref;
  40
  41   typedef ImutAVLFactory<ImutInfo>          Factory;
  42   friend class ImutAVLFactory<ImutInfo>;
  43   friend class ImutIntervalAVLFactory<ImutInfo>;
  44
  45   friend class ImutAVLTreeGenericIterator<ImutInfo>;
  46   friend class FoldingSet<ImutAVLTree>;
  47
  48   typedef ImutAVLTreeInOrderIterator<ImutInfo>  iterator;
  49
  50   //===----------------------------------------------------===//
  51   // Public Interface.
  52   //===----------------------------------------------------===//
  53
  54   /// getLeft - Returns a pointer to the left subtree.  This value
  55   ///  is NULL if there is no left subtree.
  56   ImutAVLTree *getLeft() const { return left; }
  57
  58   /// getRight - Returns a pointer to the right subtree.  This value is
  59   ///  NULL if there is no right subtree.
  60   ImutAVLTree *getRight() const { return right; }
  61
  62   /// getHeight - Returns the height of the tree.  A tree with no subtrees
  63   ///  has a height of 1.
  64   unsigned getHeight() const { return height; }
  65
  66   /// getValue - Returns the data value associated with the tree node.
  67   const value_type& getValue() const { return value; }
  68
  69   /// find - Finds the subtree associated with the specified key value.
  70   ///  This method returns NULL if no matching subtree is found.
  71   ImutAVLTree* find(key_type_ref K) {
  72     ImutAVLTree *T = this;
  73     while (T) {
  74       key_type_ref CurrentKey = ImutInfo::KeyOfValue(T->getValue());
  75       if (ImutInfo::isEqual(K,CurrentKey))
  76         return T;
  77       else if (ImutInfo::isLess(K,CurrentKey))
  78         T = T->getLeft();
  79       else
  80         T = T->getRight();
  81     }
  82     return NULL;
  83   }
  84
  85   /// getMaxElement - Find the subtree associated with the highest ranged
  86   ///  key value.
  87   ImutAVLTree* getMaxElement() {
  88     ImutAVLTree *T = this;
  89     ImutAVLTree *Right = T->getRight();
  90     while (Right) { T = right; right = T->getRight(); }
  91     return T;
  92   }
  93
  94   /// size - Returns the number of nodes in the tree, which includes
  95   ///  both leaves and non-leaf nodes.
  96   unsigned size() const {
  97     unsigned n = 1;
  98     if (const ImutAVLTree* L = getLeft())
  99       n += L->size();
 100     if (const ImutAVLTree* R = getRight())
 101       n += R->size();
 102     return n;
 103   }
 104
 105   /// begin - Returns an iterator that iterates over the nodes of the tree
 106   ///  in an inorder traversal.  The returned iterator thus refers to the
 107   ///  the tree node with the minimum data element.
 108   iterator begin() const { return iterator(this); }
 109
 110   /// end - Returns an iterator for the tree that denotes the end of an
 111   ///  inorder traversal.
 112   iterator end() const { return iterator(); }
 113
 114   bool isElementEqual(value_type_ref V) const {
 115     // Compare the keys.
 116     if (!ImutInfo::isEqual(ImutInfo::KeyOfValue(getValue()),
 117                            ImutInfo::KeyOfValue(V)))
 118       return false;
 119
 120     // Also compare the data values.
 121     if (!ImutInfo::isDataEqual(ImutInfo::DataOfValue(getValue()),
 122                                ImutInfo::DataOfValue(V)))
 123       return false;
 124
 125     return true;
 126   }
 127
 128   bool isElementEqual(const ImutAVLTree* RHS) const {
 129     return isElementEqual(RHS->getValue());
 130   }
 131
 132   /// isEqual - Compares two trees for structural equality and returns true
 133   ///   if they are equal.  This worst case performance of this operation is
 134   //    linear in the sizes of the trees.
 135   bool isEqual(const ImutAVLTree& RHS) const {
 136     if (&RHS == this)
 137       return true;
 138
 139     iterator LItr = begin(), LEnd = end();
 140     iterator RItr = RHS.begin(), REnd = RHS.end();
 141
 142     while (LItr != LEnd && RItr != REnd) {
 143       if (*LItr == *RItr) {
 144         LItr.skipSubTree();
 145         RItr.skipSubTree();
 146         continue;
 147       }
 148
 149       if (!LItr->isElementEqual(*RItr))
 150         return false;
 151
 152       ++LItr;
 153       ++RItr;
 154     }
 155
 156     return LItr == LEnd && RItr == REnd;
 157   }
 158
 159   /// isNotEqual - Compares two trees for structural inequality.  Performance
 160   ///  is the same is isEqual.
 161   bool isNotEqual(const ImutAVLTree& RHS) const { return !isEqual(RHS); }
 162
 163   /// contains - Returns true if this tree contains a subtree (node) that
 164   ///  has an data element that matches the specified key.  Complexity
 165   ///  is logarithmic in the size of the tree.
 166   bool contains(key_type_ref K) { return (bool) find(K); }
 167
 168   /// foreach - A member template the accepts invokes operator() on a functor
 169   ///  object (specifed by Callback) for every node/subtree in the tree.
 170   ///  Nodes are visited using an inorder traversal.
 171   template <typename Callback>
 172   void foreach(Callback& C) {
 173     if (ImutAVLTree* L = getLeft())
 174       L->foreach(C);
 175
 176     C(value);
 177
 178     if (ImutAVLTree* R = getRight())
 179       R->foreach(C);
 180   }
 181
 182   /// validateTree - A utility method that checks that the balancing and
 183   ///  ordering invariants of the tree are satisifed.  It is a recursive
 184   ///  method that returns the height of the tree, which is then consumed
 185   ///  by the enclosing validateTree call.  External callers should ignore the
 186   ///  return value.  An invalid tree will cause an assertion to fire in
 187   ///  a debug build.
 188   unsigned validateTree() const {
 189     unsigned HL = getLeft() ? getLeft()->validateTree() : 0;
 190     unsigned HR = getRight() ? getRight()->validateTree() : 0;
 191     (void) HL;
 192     (void) HR;
 193
 194     assert(getHeight() == ( HL > HR ? HL : HR ) + 1
 195             && "Height calculation wrong");
 196
 197     assert((HL > HR ? HL-HR : HR-HL) <= 2
 198            && "Balancing invariant violated");
 199
 200     assert((!getLeft() ||
 201             ImutInfo::isLess(ImutInfo::KeyOfValue(getLeft()->getValue()),
 202                              ImutInfo::KeyOfValue(getValue()))) &&
 203            "Value in left child is not less that current value");
 204
 205
 206     assert(!(getRight() ||
 207              ImutInfo::isLess(ImutInfo::KeyOfValue(getValue()),
 208                               ImutInfo::KeyOfValue(getRight()->getValue()))) &&
 209            "Current value is not less that value of right child");
 210
 211     return getHeight();
 212   }
 213
 214   /// Profile - Profiling for ImutAVLTree.
 215   void Profile(llvm::FoldingSetNodeID& ID) {
 216     ID.AddInteger(computeDigest());
 217   }
 218
 219   //===----------------------------------------------------===//
 220   // Internal values.
 221   //===----------------------------------------------------===//
 222
 223 private:
 224   ImutAVLTree*     left;
 225   ImutAVLTree*     right;
 226   unsigned         height         : 28;
 227   unsigned         IsMutable      : 1;
 228   unsigned         IsDigestCached : 1;
 229   value_type       value;
 230   uint32_t         digest;
 231
 232   //===----------------------------------------------------===//
 233   // Internal methods (node manipulation; used by Factory).
 234   //===----------------------------------------------------===//
 235
 236 private:
 237   /// ImutAVLTree - Internal constructor that is only called by
 238   ///   ImutAVLFactory.
 239   ImutAVLTree(ImutAVLTree* l, ImutAVLTree* r, value_type_ref v,
 240               unsigned height)
 241     : left(l), right(r), height(height), IsMutable(true),
 242       IsDigestCached(false), value(v), digest(0) {}
 243
 244   /// isMutable - Returns true if the left and right subtree references
 245   ///  (as well as height) can be changed.  If this method returns false,
 246   ///  the tree is truly immutable.  Trees returned from an ImutAVLFactory
 247   ///  object should always have this method return true.  Further, if this
 248   ///  method returns false for an instance of ImutAVLTree, all subtrees
 249   ///  will also have this method return false.  The converse is not true.
 250   bool isMutable() const { return IsMutable; }
 251
 252   /// hasCachedDigest - Returns true if the digest for this tree is cached.
 253   ///  This can only be true if the tree is immutable.
 254   bool hasCachedDigest() const { return IsDigestCached; }
 255
 256   //===----------------------------------------------------===//
 257   // Mutating operations.  A tree root can be manipulated as
 258   // long as its reference has not "escaped" from internal
 259   // methods of a factory object (see below).  When a tree
 260   // pointer is externally viewable by client code, the
 261   // internal "mutable bit" is cleared to mark the tree
 262   // immutable.  Note that a tree that still has its mutable
 263   // bit set may have children (subtrees) that are themselves
 264   // immutable.
 265   //===----------------------------------------------------===//
 266
 267   /// markImmutable - Clears the mutable flag for a tree.  After this happens,
 268   ///   it is an error to call setLeft(), setRight(), and setHeight().
 269   void markImmutable() {
 270     assert(isMutable() && "Mutable flag already removed.");
 271     IsMutable = false;
 272   }
 273
 274   /// markedCachedDigest - Clears the NoCachedDigest flag for a tree.
 275   void markedCachedDigest() {
 276     assert(!hasCachedDigest() && "NoCachedDigest flag already removed.");
 277     IsDigestCached = true;
 278   }
 279
 280   /// setLeft - Changes the reference of the left subtree.  Used internally
 281   ///   by ImutAVLFactory.
 282   void setLeft(ImutAVLTree* NewLeft) {
 283     assert(isMutable() &&
 284            "Only a mutable tree can have its left subtree changed.");
 285     left = NewLeft;
 286     IsDigestCached = false;
 287   }
 288
 289   /// setRight - Changes the reference of the right subtree.  Used internally
 290   ///  by ImutAVLFactory.
 291   void setRight(ImutAVLTree* newRight) {
 292     assert(isMutable() &&
 293            "Only a mutable tree can have its right subtree changed.");
 294
 295     right = newRight;
 296     IsDigestCached = false;
 297   }
 298
 299   /// setHeight - Changes the height of the tree.  Used internally by
 300   ///  ImutAVLFactory.
 301   void setHeight(unsigned h) {
 302     assert(isMutable() && "Only a mutable tree can have its height changed.");
 303     height = h;
 304   }
 305
 306   static inline
 307   uint32_t computeDigest(ImutAVLTree* L, ImutAVLTree* R, value_type_ref V) {
 308     uint32_t digest = 0;
 309
 310     if (L)
 311       digest += L->computeDigest();
 312
 313     // Compute digest of stored data.
 314     FoldingSetNodeID ID;
 315     ImutInfo::Profile(ID,V);
 316     digest += ID.ComputeHash();
 317
 318     if (R)
 319       digest += R->computeDigest();
 320
 321     return digest;
 322   }
 323
 324   inline uint32_t computeDigest() {
 325     // Check the lowest bit to determine if digest has actually been
 326     // pre-computed.
 327     if (hasCachedDigest())
 328       return digest;
 329
 330     uint32_t X = computeDigest(getLeft(), getRight(), getValue());
 331     digest = X;
 332     markedCachedDigest();
 333     return X;
 334   }
 335 };
 336
 337 //===----------------------------------------------------------------------===//
 338 // Immutable AVL-Tree Factory class.
 339 //===----------------------------------------------------------------------===//
 340
 341 template <typename ImutInfo >
 342 class ImutAVLFactory {
 343   typedef ImutAVLTree<ImutInfo> TreeTy;
 344   typedef typename TreeTy::value_type_ref value_type_ref;
 345   typedef typename TreeTy::key_type_ref   key_type_ref;
 346
 347   typedef FoldingSet<TreeTy> CacheTy;
 348
 349   CacheTy Cache;
 350   uintptr_t Allocator;
 351
 352   bool ownsAllocator() const {
 353     return Allocator & 0x1 ? false : true;
 354   }
 355
 356   BumpPtrAllocator& getAllocator() const {
 357     return *reinterpret_cast<BumpPtrAllocator*>(Allocator & ~0x1);
 358   }
 359
 360   //===--------------------------------------------------===//
 361   // Public interface.
 362   //===--------------------------------------------------===//
 363
 364 public:
 365   ImutAVLFactory()
 366     : Allocator(reinterpret_cast<uintptr_t>(new BumpPtrAllocator())) {}
 367
 368   ImutAVLFactory(BumpPtrAllocator& Alloc)
 369     : Allocator(reinterpret_cast<uintptr_t>(&Alloc) | 0x1) {}
 370
 371   ~ImutAVLFactory() {
 372     if (ownsAllocator()) delete &getAllocator();
 373   }
 374
 375   TreeTy* add(TreeTy* T, value_type_ref V) {
 376     T = add_internal(V,T);
 377     markImmutable(T);
 378     return T;
 379   }
 380
 381   TreeTy* remove(TreeTy* T, key_type_ref V) {
 382     T = remove_internal(V,T);
 383     markImmutable(T);
 384     return T;
 385   }
 386
 387   TreeTy* getEmptyTree() const { return NULL; }
 388
 389 protected:
 390
 391   //===--------------------------------------------------===//
 392   // A bunch of quick helper functions used for reasoning
 393   // about the properties of trees and their children.
 394   // These have succinct names so that the balancing code
 395   // is as terse (and readable) as possible.
 396   //===--------------------------------------------------===//
 397
 398   bool            isEmpty(TreeTy* T) const { return !T; }
 399   unsigned        getHeight(TreeTy* T) const { return T ? T->getHeight() : 0; }
 400   TreeTy*         getLeft(TreeTy* T) const { return T->getLeft(); }
 401   TreeTy*         getRight(TreeTy* T) const { return T->getRight(); }
 402   value_type_ref  getValue(TreeTy* T) const { return T->value; }
 403
 404   unsigned incrementHeight(TreeTy* L, TreeTy* R) const {
 405     unsigned hl = getHeight(L);
 406     unsigned hr = getHeight(R);
 407     return (hl > hr ? hl : hr) + 1;
 408   }
 409
 410   static bool compareTreeWithSection(TreeTy* T,
 411                                      typename TreeTy::iterator& TI,
 412                                      typename TreeTy::iterator& TE) {
 413     typename TreeTy::iterator I = T->begin(), E = T->end();
 414     for ( ; I!=E ; ++I, ++TI) {
 415       if (TI == TE || !I->isElementEqual(*TI))
 416         return false;
 417     }
 418     return true;
 419   }
 420
 421   //===--------------------------------------------------===//
 422   // "createNode" is used to generate new tree roots that link
 423   // to other trees.  The functon may also simply move links
 424   // in an existing root if that root is still marked mutable.
 425   // This is necessary because otherwise our balancing code
 426   // would leak memory as it would create nodes that are
 427   // then discarded later before the finished tree is
 428   // returned to the caller.
 429   //===--------------------------------------------------===//
 430
 431   TreeTy* createNode(TreeTy* L, value_type_ref V, TreeTy* R) {
 432     BumpPtrAllocator& A = getAllocator();
 433     TreeTy* T = (TreeTy*) A.Allocate<TreeTy>();
 434     new (T) TreeTy(L, R, V, incrementHeight(L,R));
 435     return T;
 436   }
 437
 438   TreeTy* createNode(TreeTy* newLeft, TreeTy* oldTree, TreeTy* newRight) {
 439     assert(!isEmpty(oldTree));
 440     if (oldTree->isMutable()) {
 441       oldTree->setLeft(newLeft);
 442       oldTree->setRight(newRight);
 443       oldTree->setHeight(incrementHeight(newLeft, newRight));
 444       return oldTree;
 445     }
 446     else
 447       return createNode(newLeft, getValue(oldTree), newRight);
 448   }
 449
 450   /// balanceTree - Used by add_internal and remove_internal to
 451   ///  balance a newly created tree.
 452   TreeTy* balanceTree(TreeTy* L, value_type_ref V, TreeTy* R) {
 453     unsigned hl = getHeight(L);
 454     unsigned hr = getHeight(R);
 455
 456     if (hl > hr + 2) {
 457       assert(!isEmpty(L) && "Left tree cannot be empty to have a height >= 2");
 458
 459       TreeTy *LL = getLeft(L);
 460       TreeTy *LR = getRight(L);
 461
 462       if (getHeight(LL) >= getHeight(LR))
 463         return createNode(LL, L, createNode(LR,V,R));
 464
 465       assert(!isEmpty(LR) && "LR cannot be empty because it has a height >= 1");
 466
 467       TreeTy *LRL = getLeft(LR);
 468       TreeTy *LRR = getRight(LR);
 469
 470       return createNode(createNode(LL,L,LRL), LR, createNode(LRR,V,R));
 471     }
 472     else if (hr > hl + 2) {
 473       assert(!isEmpty(R) && "Right tree cannot be empty to have a height >= 2");
 474
 475       TreeTy *RL = getLeft(R);
 476       TreeTy *RR = getRight(R);
 477
 478       if (getHeight(RR) >= getHeight(RL))
 479         return createNode(createNode(L,V,RL), R, RR);
 480
 481       assert(!isEmpty(RL) && "RL cannot be empty because it has a height >= 1");
 482
 483       TreeTy *RLL = getLeft(RL);
 484       TreeTy *RLR = getRight(RL);
 485
 486       return createNode(createNode(L,V,RLL), RL, createNode(RLR,R,RR));
 487     }
 488     else
 489       return createNode(L,V,R);
 490   }
 491
 492   /// add_internal - Creates a new tree that includes the specified
 493   ///  data and the data from the original tree.  If the original tree
 494   ///  already contained the data item, the original tree is returned.
 495   TreeTy* add_internal(value_type_ref V, TreeTy* T) {
 496     if (isEmpty(T))
 497       return createNode(T, V, T);
 498     assert(!T->isMutable());
 499
 500     key_type_ref K = ImutInfo::KeyOfValue(V);
 501     key_type_ref KCurrent = ImutInfo::KeyOfValue(getValue(T));
 502
 503     if (ImutInfo::isEqual(K,KCurrent))
 504       return createNode(getLeft(T), V, getRight(T));
 505     else if (ImutInfo::isLess(K,KCurrent))
 506       return balanceTree(add_internal(V, getLeft(T)), getValue(T), getRight(T));
 507     else
 508       return balanceTree(getLeft(T), getValue(T), add_internal(V, getRight(T)));
 509   }
 510
 511   /// remove_internal - Creates a new tree that includes all the data
 512   ///  from the original tree except the specified data.  If the
 513   ///  specified data did not exist in the original tree, the original
 514   ///  tree is returned.
 515   TreeTy* remove_internal(key_type_ref K, TreeTy* T) {
 516     if (isEmpty(T))
 517       return T;
 518
 519     assert(!T->isMutable());
 520
 521     key_type_ref KCurrent = ImutInfo::KeyOfValue(getValue(T));
 522
 523     if (ImutInfo::isEqual(K,KCurrent)) {
 524       return combineTrees(getLeft(T), getRight(T));
 525     } else if (ImutInfo::isLess(K,KCurrent)) {
 526       return balanceTree(remove_internal(K, getLeft(T)),
 527                                             getValue(T), getRight(T));
 528     } else {
 529       return balanceTree(getLeft(T), getValue(T),
 530                          remove_internal(K, getRight(T)));
 531     }
 532   }
 533
 534   TreeTy* combineTrees(TreeTy* L, TreeTy* R) {
 535     if (isEmpty(L))
 536       return R;
 537     if (isEmpty(R))
 538       return L;
 539     TreeTy* OldNode;
 540     TreeTy* newRight = removeMinBinding(R,OldNode);
 541     return balanceTree(L, getValue(OldNode), newRight);
 542   }
 543
 544   TreeTy* removeMinBinding(TreeTy* T, TreeTy*& Noderemoved) {
 545     assert(!isEmpty(T));
 546     if (isEmpty(getLeft(T))) {
 547       Noderemoved = T;
 548       return getRight(T);
 549     }
 550     return balanceTree(removeMinBinding(getLeft(T), Noderemoved),
 551                        getValue(T), getRight(T));
 552   }
 553
 554   /// markImmutable - Clears the mutable bits of a root and all of its
 555   ///  descendants.
 556   void markImmutable(TreeTy* T) {
 557     if (!T || !T->isMutable())
 558       return;
 559     T->markImmutable();
 560     markImmutable(getLeft(T));
 561     markImmutable(getRight(T));
 562   }
 563
 564 public:
 565   TreeTy *getCanonicalTree(TreeTy *TNew) {
 566     if (!TNew)
 567       return NULL;
 568
 569     // Search the FoldingSet bucket for a Tree with the same digest.
 570     FoldingSetNodeID ID;
 571     unsigned digest = TNew->computeDigest();
 572     ID.AddInteger(digest);
 573     unsigned hash = ID.ComputeHash();
 574
 575     typename CacheTy::bucket_iterator I = Cache.bucket_begin(hash);
 576     typename CacheTy::bucket_iterator E = Cache.bucket_end(hash);
 577
 578     for (; I != E; ++I) {
 579       TreeTy *T = &*I;
 580
 581       if (T->computeDigest() != digest)
 582         continue;
 583
 584       // We found a collision.  Perform a comparison of Contents('T')
 585       // with Contents('TNew')
 586       typename TreeTy::iterator TI = T->begin(), TE = T->end();
 587
 588       if (!compareTreeWithSection(TNew, TI, TE))
 589         continue;
 590
 591       if (TI != TE)
 592         continue; // T has more contents than TNew.
 593
 594       // Trees did match!  Return 'T'.
 595       return T;
 596     }
 597
 598     // 'TNew' is the only tree of its kind.  Return it.
 599     Cache.InsertNode(TNew, (void*) &*Cache.bucket_end(hash));
 600     return TNew;
 601   }
 602 };
 603
 604
 605 //===----------------------------------------------------------------------===//
 606 // Immutable AVL-Tree Iterators.
 607 //===----------------------------------------------------------------------===//
 608
 609 template <typename ImutInfo>
 610 class ImutAVLTreeGenericIterator {
 611   SmallVector<uintptr_t,20> stack;
 612 public:
 613   enum VisitFlag { VisitedNone=0x0, VisitedLeft=0x1, VisitedRight=0x3,
 614                    Flags=0x3 };
 615
 616   typedef ImutAVLTree<ImutInfo> TreeTy;
 617   typedef ImutAVLTreeGenericIterator<ImutInfo> _Self;
 618
 619   inline ImutAVLTreeGenericIterator() {}
 620   inline ImutAVLTreeGenericIterator(const TreeTy* Root) {
 621     if (Root) stack.push_back(reinterpret_cast<uintptr_t>(Root));
 622   }
 623
 624   TreeTy* operator*() const {
 625     assert(!stack.empty());
 626     return reinterpret_cast<TreeTy*>(stack.back() & ~Flags);
 627   }
 628
 629   uintptr_t getVisitState() {
 630     assert(!stack.empty());
 631     return stack.back() & Flags;
 632   }
 633
 634
 635   bool atEnd() const { return stack.empty(); }
 636
 637   bool atBeginning() const {
 638     return stack.size() == 1 && getVisitState() == VisitedNone;
 639   }
 640
 641   void skipToParent() {
 642     assert(!stack.empty());
 643     stack.pop_back();
 644     if (stack.empty())
 645       return;
 646     switch (getVisitState()) {
 647       case VisitedNone:
 648         stack.back() |= VisitedLeft;
 649         break;
 650       case VisitedLeft:
 651         stack.back() |= VisitedRight;
 652         break;
 653       default:
 654         assert(false && "Unreachable.");
 655     }
 656   }
 657
 658   inline bool operator==(const _Self& x) const {
 659     if (stack.size() != x.stack.size())
 660       return false;
 661     for (unsigned i = 0 ; i < stack.size(); i++)
 662       if (stack[i] != x.stack[i])
 663         return false;
 664     return true;
 665   }
 666
 667   inline bool operator!=(const _Self& x) const { return !operator==(x); }
 668
 669   _Self& operator++() {
 670     assert(!stack.empty());
 671     TreeTy* Current = reinterpret_cast<TreeTy*>(stack.back() & ~Flags);
 672     assert(Current);
 673     switch (getVisitState()) {
 674       case VisitedNone:
 675         if (TreeTy* L = Current->getLeft())
 676           stack.push_back(reinterpret_cast<uintptr_t>(L));
 677         else
 678           stack.back() |= VisitedLeft;
 679         break;
 680       case VisitedLeft:
 681         if (TreeTy* R = Current->getRight())
 682           stack.push_back(reinterpret_cast<uintptr_t>(R));
 683         else
 684           stack.back() |= VisitedRight;
 685         break;
 686       case VisitedRight:
 687         skipToParent();
 688         break;
 689       default:
 690         assert(false && "Unreachable.");
 691     }
 692     return *this;
 693   }
 694
 695   _Self& operator--() {
 696     assert(!stack.empty());
 697     TreeTy* Current = reinterpret_cast<TreeTy*>(stack.back() & ~Flags);
 698     assert(Current);
 699     switch (getVisitState()) {
 700       case VisitedNone:
 701         stack.pop_back();
 702         break;
 703       case VisitedLeft:
 704         stack.back() &= ~Flags; // Set state to "VisitedNone."
 705         if (TreeTy* L = Current->getLeft())
 706           stack.push_back(reinterpret_cast<uintptr_t>(L) | VisitedRight);
 707         break;
 708       case VisitedRight:
 709         stack.back() &= ~Flags;
 710         stack.back() |= VisitedLeft;
 711         if (TreeTy* R = Current->getRight())
 712           stack.push_back(reinterpret_cast<uintptr_t>(R) | VisitedRight);
 713         break;
 714       default:
 715         assert(false && "Unreachable.");
 716     }
 717     return *this;
 718   }
 719 };
 720
 721 template <typename ImutInfo>
 722 class ImutAVLTreeInOrderIterator {
 723   typedef ImutAVLTreeGenericIterator<ImutInfo> InternalIteratorTy;
 724   InternalIteratorTy InternalItr;
 725
 726 public:
 727   typedef ImutAVLTree<ImutInfo> TreeTy;
 728   typedef ImutAVLTreeInOrderIterator<ImutInfo> _Self;
 729
 730   ImutAVLTreeInOrderIterator(const TreeTy* Root) : InternalItr(Root) {
 731     if (Root) operator++(); // Advance to first element.
 732   }
 733
 734   ImutAVLTreeInOrderIterator() : InternalItr() {}
 735
 736   inline bool operator==(const _Self& x) const {
 737     return InternalItr == x.InternalItr;
 738   }
 739
 740   inline bool operator!=(const _Self& x) const { return !operator==(x); }
 741
 742   inline TreeTy* operator*() const { return *InternalItr; }
 743   inline TreeTy* operator->() const { return *InternalItr; }
 744
 745   inline _Self& operator++() {
 746     do ++InternalItr;
 747     while (!InternalItr.atEnd() &&
 748            InternalItr.getVisitState() != InternalIteratorTy::VisitedLeft);
 749
 750     return *this;
 751   }
 752
 753   inline _Self& operator--() {
 754     do --InternalItr;
 755     while (!InternalItr.atBeginning() &&
 756            InternalItr.getVisitState() != InternalIteratorTy::VisitedLeft);
 757
 758     return *this;
 759   }
 760
 761   inline void skipSubTree() {
 762     InternalItr.skipToParent();
 763
 764     while (!InternalItr.atEnd() &&
 765            InternalItr.getVisitState() != InternalIteratorTy::VisitedLeft)
 766       ++InternalItr;
 767   }
 768 };
 769
 770 //===----------------------------------------------------------------------===//
 771 // Trait classes for Profile information.
 772 //===----------------------------------------------------------------------===//
 773
 774 /// Generic profile template.  The default behavior is to invoke the
 775 /// profile method of an object.  Specializations for primitive integers
 776 /// and generic handling of pointers is done below.
 777 template <typename T>
 778 struct ImutProfileInfo {
 779   typedef const T  value_type;
 780   typedef const T& value_type_ref;
 781
 782   static inline void Profile(FoldingSetNodeID& ID, value_type_ref X) {
 783     FoldingSetTrait<T>::Profile(X,ID);
 784   }
 785 };
 786
 787 /// Profile traits for integers.
 788 template <typename T>
 789 struct ImutProfileInteger {
 790   typedef const T  value_type;
 791   typedef const T& value_type_ref;
 792
 793   static inline void Profile(FoldingSetNodeID& ID, value_type_ref X) {
 794     ID.AddInteger(X);
 795   }
 796 };
 797
 798 #define PROFILE_INTEGER_INFO(X)\
 799 template<> struct ImutProfileInfo<X> : ImutProfileInteger<X> {};
 800
 801 PROFILE_INTEGER_INFO(char)
 802 PROFILE_INTEGER_INFO(unsigned char)
 803 PROFILE_INTEGER_INFO(short)
 804 PROFILE_INTEGER_INFO(unsigned short)
 805 PROFILE_INTEGER_INFO(unsigned)
 806 PROFILE_INTEGER_INFO(signed)
 807 PROFILE_INTEGER_INFO(long)
 808 PROFILE_INTEGER_INFO(unsigned long)
 809 PROFILE_INTEGER_INFO(long long)
 810 PROFILE_INTEGER_INFO(unsigned long long)
 811
 812 #undef PROFILE_INTEGER_INFO
 813
 814 /// Generic profile trait for pointer types.  We treat pointers as
 815 /// references to unique objects.
 816 template <typename T>
 817 struct ImutProfileInfo<T*> {
 818   typedef const T*   value_type;
 819   typedef value_type value_type_ref;
 820
 821   static inline void Profile(FoldingSetNodeID &ID, value_type_ref X) {
 822     ID.AddPointer(X);
 823   }
 824 };
 825
 826 //===----------------------------------------------------------------------===//
 827 // Trait classes that contain element comparison operators and type
 828 //  definitions used by ImutAVLTree, ImmutableSet, and ImmutableMap.  These
 829 //  inherit from the profile traits (ImutProfileInfo) to include operations
 830 //  for element profiling.
 831 //===----------------------------------------------------------------------===//
 832
 833
 834 /// ImutContainerInfo - Generic definition of comparison operations for
 835 ///   elements of immutable containers that defaults to using
 836 ///   std::equal_to<> and std::less<> to perform comparison of elements.
 837 template <typename T>
 838 struct ImutContainerInfo : public ImutProfileInfo<T> {
 839   typedef typename ImutProfileInfo<T>::value_type      value_type;
 840   typedef typename ImutProfileInfo<T>::value_type_ref  value_type_ref;
 841   typedef value_type      key_type;
 842   typedef value_type_ref  key_type_ref;
 843   typedef bool            data_type;
 844   typedef bool            data_type_ref;
 845
 846   static inline key_type_ref KeyOfValue(value_type_ref D) { return D; }
 847   static inline data_type_ref DataOfValue(value_type_ref) { return true; }
 848
 849   static inline bool isEqual(key_type_ref LHS, key_type_ref RHS) {
 850     return std::equal_to<key_type>()(LHS,RHS);
 851   }
 852
 853   static inline bool isLess(key_type_ref LHS, key_type_ref RHS) {
 854     return std::less<key_type>()(LHS,RHS);
 855   }
 856
 857   static inline bool isDataEqual(data_type_ref,data_type_ref) { return true; }
 858 };
 859
 860 /// ImutContainerInfo - Specialization for pointer values to treat pointers
 861 ///  as references to unique objects.  Pointers are thus compared by
 862 ///  their addresses.
 863 template <typename T>
 864 struct ImutContainerInfo<T*> : public ImutProfileInfo<T*> {
 865   typedef typename ImutProfileInfo<T*>::value_type      value_type;
 866   typedef typename ImutProfileInfo<T*>::value_type_ref  value_type_ref;
 867   typedef value_type      key_type;
 868   typedef value_type_ref  key_type_ref;
 869   typedef bool            data_type;
 870   typedef bool            data_type_ref;
 871
 872   static inline key_type_ref KeyOfValue(value_type_ref D) { return D; }
 873   static inline data_type_ref DataOfValue(value_type_ref) { return true; }
 874
 875   static inline bool isEqual(key_type_ref LHS, key_type_ref RHS) {
 876     return LHS == RHS;
 877   }
 878
 879   static inline bool isLess(key_type_ref LHS, key_type_ref RHS) {
 880     return LHS < RHS;
 881   }
 882
 883   static inline bool isDataEqual(data_type_ref,data_type_ref) { return true; }
 884 };
 885
 886 //===----------------------------------------------------------------------===//
 887 // Immutable Set
 888 //===----------------------------------------------------------------------===//
 889
 890 template <typename ValT, typename ValInfo = ImutContainerInfo<ValT> >
 891 class ImmutableSet {
 892 public:
 893   typedef typename ValInfo::value_type      value_type;
 894   typedef typename ValInfo::value_type_ref  value_type_ref;
 895   typedef ImutAVLTree<ValInfo> TreeTy;
 896
 897 private:
 898   TreeTy *Root;
 899
 900 public:
 901   /// Constructs a set from a pointer to a tree root.  In general one
 902   /// should use a Factory object to create sets instead of directly
 903   /// invoking the constructor, but there are cases where make this
 904   /// constructor public is useful.
 905   explicit ImmutableSet(TreeTy* R) : Root(R) {}
 906
 907   class Factory {
 908     typename TreeTy::Factory F;
 909     const bool Canonicalize;
 910
 911   public:
 912     Factory(bool canonicalize = true)
 913       : Canonicalize(canonicalize) {}
 914
 915     Factory(BumpPtrAllocator& Alloc, bool canonicalize = true)
 916       : F(Alloc), Canonicalize(canonicalize) {}
 917
 918     /// getEmptySet - Returns an immutable set that contains no elements.
 919     ImmutableSet getEmptySet() {
 920       return ImmutableSet(F.getEmptyTree());
 921     }
 922
 923     /// add - Creates a new immutable set that contains all of the values
 924     ///  of the original set with the addition of the specified value.  If
 925     ///  the original set already included the value, then the original set is
 926     ///  returned and no memory is allocated.  The time and space complexity
 927     ///  of this operation is logarithmic in the size of the original set.
 928     ///  The memory allocated to represent the set is released when the
 929     ///  factory object that created the set is destroyed.
 930     ImmutableSet add(ImmutableSet Old, value_type_ref V) {
 931       TreeTy *NewT = F.add(Old.Root, V);
 932       return ImmutableSet(Canonicalize ? F.getCanonicalTree(NewT) : NewT);
 933     }
 934
 935     /// remove - Creates a new immutable set that contains all of the values
 936     ///  of the original set with the exception of the specified value.  If
 937     ///  the original set did not contain the value, the original set is
 938     ///  returned and no memory is allocated.  The time and space complexity
 939     ///  of this operation is logarithmic in the size of the original set.
 940     ///  The memory allocated to represent the set is released when the
 941     ///  factory object that created the set is destroyed.
 942     ImmutableSet remove(ImmutableSet Old, value_type_ref V) {
 943       TreeTy *NewT = F.remove(Old.Root, V);
 944       return ImmutableSet(Canonicalize ? F.getCanonicalTree(NewT) : NewT);
 945     }
 946
 947     BumpPtrAllocator& getAllocator() { return F.getAllocator(); }
 948
 949   private:
 950     Factory(const Factory& RHS); // DO NOT IMPLEMENT
 951     void operator=(const Factory& RHS); // DO NOT IMPLEMENT
 952   };
 953
 954   friend class Factory;
 955
 956   /// contains - Returns true if the set contains the specified value.
 957   bool contains(value_type_ref V) const {
 958     return Root ? Root->contains(V) : false;
 959   }
 960
 961   bool operator==(ImmutableSet RHS) const {
 962     return Root && RHS.Root ? Root->isEqual(*RHS.Root) : Root == RHS.Root;
 963   }
 964
 965   bool operator!=(ImmutableSet RHS) const {
 966     return Root && RHS.Root ? Root->isNotEqual(*RHS.Root) : Root != RHS.Root;
 967   }
 968
 969   TreeTy *getRoot() {
 970     return Root;
 971   }
 972
 973   /// isEmpty - Return true if the set contains no elements.
 974   bool isEmpty() const { return !Root; }
 975
 976   /// isSingleton - Return true if the set contains exactly one element.
 977   ///   This method runs in constant time.
 978   bool isSingleton() const { return getHeight() == 1; }
 979
 980   template <typename Callback>
 981   void foreach(Callback& C) { if (Root) Root->foreach(C); }
 982
 983   template <typename Callback>
 984   void foreach() { if (Root) { Callback C; Root->foreach(C); } }
 985
 986   //===--------------------------------------------------===//
 987   // Iterators.
 988   //===--------------------------------------------------===//
 989
 990   class iterator {
 991     typename TreeTy::iterator itr;
 992     iterator(TreeTy* t) : itr(t) {}
 993     friend class ImmutableSet<ValT,ValInfo>;
 994   public:
 995     iterator() {}
 996     inline value_type_ref operator*() const { return itr->getValue(); }
 997     inline iterator& operator++() { ++itr; return *this; }
 998     inline iterator  operator++(int) { iterator tmp(*this); ++itr; return tmp; }
 999     inline iterator& operator--() { --itr; return *this; }
1000     inline iterator  operator--(int) { iterator tmp(*this); --itr; return tmp; }
1001     inline bool operator==(const iterator& RHS) const { return RHS.itr == itr; }
1002     inline bool operator!=(const iterator& RHS) const { return RHS.itr != itr; }
1003     inline value_type *operator->() const { return &(operator*()); }
1004   };
1005
1006   iterator begin() const { return iterator(Root); }
1007   iterator end() const { return iterator(); }
1008
1009   //===--------------------------------------------------===//
1010   // Utility methods.
1011   //===--------------------------------------------------===//
1012
1013   unsigned getHeight() const { return Root ? Root->getHeight() : 0; }
1014
1015   static inline void Profile(FoldingSetNodeID& ID, const ImmutableSet& S) {
1016     ID.AddPointer(S.Root);
1017   }
1018
1019   inline void Profile(FoldingSetNodeID& ID) const {
1020     return Profile(ID,*this);
1021   }
1022
1023   //===--------------------------------------------------===//
1024   // For testing.
1025   //===--------------------------------------------------===//
1026
1027   void validateTree() const { if (Root) Root->validateTree(); }
1028 };
1029
1030 } // end namespace llvm
1031
1032 #endif