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