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