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