LCOV - code coverage report
Current view: top level - include/llvm/ADT - ImmutableSet.h (source / functions) Hit Total Coverage
Test: llvm-toolchain.info Lines: 330 337 97.9 %
Date: 2017-09-14 15:23:50 Functions: 959 1054 91.0 %
Legend: Lines: hit not hit

          Line data    Source code
       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    11582116 :   unsigned getHeight() const { return height; }
      69             : 
      70             :   /// getValue - Returns the data value associated with the tree node.
      71     5825361 :   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     1365375 :   ImutAVLTree* find(key_type_ref K) {
      76     1365375 :     ImutAVLTree *T = this;
      77    17928343 :     while (T) {
      78    18333283 :       key_type_ref CurrentKey = ImutInfo::KeyOfValue(T->getValue());
      79    23324626 :       if (ImutInfo::isEqual(K,CurrentKey))
      80             :         return T;
      81    16524601 :       else if (ImutInfo::isLess(K,CurrentKey))
      82     4644885 :         T = T->getLeft();
      83             :       else
      84     5821255 :         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           1 :     ImutAVLTree *T = this;
      93           1 :     ImutAVLTree *Right = T->getRight();
      94           3 :     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     3017728 :   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     3017728 :   iterator end() const { return iterator(); }
     117             : 
     118     1041730 :   bool isElementEqual(value_type_ref V) const {
     119             :     // Compare the keys.
     120     8851529 :     if (!ImutInfo::isEqual(ImutInfo::KeyOfValue(getValue()),
     121             :                            ImutInfo::KeyOfValue(V)))
     122             :       return false;
     123             : 
     124             :     // Also compare the data values.
     125     6143861 :     if (!ImutInfo::isDataEqual(ImutInfo::DataOfValue(getValue()),
     126             :                                ImutInfo::DataOfValue(V)))
     127             :       return false;
     128             : 
     129     1041730 :     return true;
     130             :   }
     131             : 
     132             :   bool isElementEqual(const ImutAVLTree* RHS) const {
     133     4688888 :     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     2255257 :   bool isEqual(const ImutAVLTree& RHS) const {
     140     2255257 :     if (&RHS == this)
     141             :       return true;
     142             : 
     143     1946463 :     iterator LItr = begin(), LEnd = end();
     144     1946463 :     iterator RItr = RHS.begin(), REnd = RHS.end();
     145             : 
     146     4383137 :     while (LItr != LEnd && RItr != REnd) {
     147     4634635 :       if (&*LItr == &*RItr) {
     148      412497 :         LItr.skipSubTree();
     149      412497 :         RItr.skipSubTree();
     150      412497 :         continue;
     151             :       }
     152             : 
     153     3397144 :       if (!LItr->isElementEqual(&*RItr))
     154             :         return false;
     155             : 
     156             :       ++LItr;
     157             :       ++RItr;
     158             :     }
     159             : 
     160       83696 :     return LItr == LEnd && RItr == REnd;
     161             :   }
     162             : 
     163             :   /// isNotEqual - Compares two trees for structural inequality.  Performance
     164             :   ///  is the same is isEqual.
     165      505468 :   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     1074166 :   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           6 :   void foreach(Callback& C) {
     177          14 :     if (ImutAVLTree* L = getLeft())
     178           3 :       L->foreach(C);
     179             : 
     180          28 :     C(value);
     181             : 
     182          14 :     if (ImutAVLTree* R = getRight())
     183             :       R->foreach(C);
     184           6 :   }
     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     6489705 :   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     7872279 :       IsDigestCached(false), IsCanonicalized(false), value(v)
     249             :   {
     250     6489705 :     if (left) left->retain();
     251     6489705 :     if (right) right->retain();
     252     1382574 :   }
     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    14482901 :   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     6568679 :   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     6116050 :     IsMutable = false;
     282             :   }
     283             : 
     284             :   /// markedCachedDigest - Clears the NoCachedDigest flag for a tree.
     285             :   void markedCachedDigest() {
     286             :     assert(!hasCachedDigest() && "NoCachedDigest flag already removed.");
     287     4695861 :     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     4695861 :   static uint32_t computeDigest(ImutAVLTree *L, ImutAVLTree *R,
     298             :                                 value_type_ref V) {
     299     4695861 :     uint32_t digest = 0;
     300             : 
     301     4695861 :     if (L)
     302     1841592 :       digest += L->computeDigest();
     303             : 
     304             :     // Compute digest of stored data.
     305     9391722 :     FoldingSetNodeID ID;
     306     4696019 :     ImutInfo::Profile(ID,V);
     307     4695861 :     digest += ID.ComputeHash();
     308             : 
     309     4695861 :     if (R)
     310     2581589 :       digest += R->computeDigest();
     311             : 
     312     9391722 :     return digest;
     313             :   }
     314             : 
     315     4467080 :   uint32_t computeDigest() {
     316             :     // Check the lowest bit to determine if digest has actually been
     317             :     // pre-computed.
     318     6568679 :     if (hasCachedDigest())
     319     1872818 :       return digest;
     320             : 
     321     4695861 :     uint32_t X = computeDigest(getLeft(), getRight(), getValue());
     322     4695861 :     digest = X;
     323     4695861 :     markedCachedDigest();
     324     2939914 :     return X;
     325             :   }
     326             : 
     327             :   //===----------------------------------------------------===//
     328             :   // Reference count operations.
     329             :   //===----------------------------------------------------===//
     330             : 
     331             : public:
     332    33435753 :   void retain() { ++refCount; }
     333             : 
     334     4195072 :   void release() {
     335             :     assert(refCount > 0);
     336    27712003 :     if (--refCount == 0)
     337     3751236 :       destroy();
     338     4195072 :   }
     339             : 
     340     4694305 :   void destroy() {
     341     4694305 :     if (left)
     342     1687524 :       left->release();
     343     4694305 :     if (right)
     344     2507548 :       right->release();
     345     4694305 :     if (IsCanonicalized) {
     346      354975 :       if (next)
     347           0 :         next->prev = prev;
     348             : 
     349      354975 :       if (prev)
     350           0 :         prev->next = next;
     351             :       else
     352     1064925 :         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     4694305 :     IsMutable = false;
     358     9388610 :     factory->freeNodes.push_back(this);
     359     4694305 :   }
     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      102986 :     return (Allocator & 0x1) == 0;
     382             :   }
     383             : 
     384             :   BumpPtrAllocator& getAllocator() const {
     385     6546988 :     return *reinterpret_cast<BumpPtrAllocator*>(Allocator & ~0x1);
     386             :   }
     387             : 
     388             :   //===--------------------------------------------------===//
     389             :   // Public interface.
     390             :   //===--------------------------------------------------===//
     391             : 
     392             : public:
     393       57283 :   ImutAVLFactory()
     394      286415 :     : Allocator(reinterpret_cast<uintptr_t>(new BumpPtrAllocator())) {}
     395             : 
     396       45703 :   ImutAVLFactory(BumpPtrAllocator& Alloc)
     397      182812 :     : Allocator(reinterpret_cast<uintptr_t>(&Alloc) | 0x1) {}
     398             : 
     399      102986 :   ~ImutAVLFactory() {
     400      263255 :     if (ownsAllocator()) delete &getAllocator();
     401      411944 :   }
     402             : 
     403     2161991 :   TreeTy* add(TreeTy* T, value_type_ref V) {
     404     2161991 :     T = add_internal(V,T);
     405     2161991 :     markImmutable(T);
     406     2161991 :     recoverNodes();
     407     2161991 :     return T;
     408             :   }
     409             : 
     410      514997 :   TreeTy* remove(TreeTy* T, key_type_ref V) {
     411      514997 :     T = remove_internal(V,T);
     412      514997 :     markImmutable(T);
     413      514997 :     recoverNodes();
     414      514997 :     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    33018739 :   unsigned        getHeight(TreeTy* T) const { return T ? T->getHeight() : 0; }
     429    11261601 :   TreeTy*         getLeft(TreeTy* T) const { return T->getLeft(); }
     430    11251800 :   TreeTy*         getRight(TreeTy* T) const { return T->getRight(); }
     431     3981385 :   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     2145498 :   static unsigned maskCacheIndex(unsigned I) { return (I & ~0x02); }
     435             : 
     436             :   unsigned incrementHeight(TreeTy* L, TreeTy* R) const {
     437    12979410 :     unsigned hl = getHeight(L);
     438    12979410 :     unsigned hr = getHeight(R);
     439     6489705 :     return (hl > hr ? hl : hr) + 1;
     440             :   }
     441             : 
     442      860043 :   static bool compareTreeWithSection(TreeTy* T,
     443             :                                      typename TreeTy::iterator& TI,
     444             :                                      typename TreeTy::iterator& TE) {
     445     2580129 :     typename TreeTy::iterator I = T->begin(), E = T->end();
     446     3850358 :     for ( ; I!=E ; ++I, ++TI) {
     447    10012678 :       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     6489705 :   TreeTy* createNode(TreeTy* L, value_type_ref V, TreeTy* R) {
     464    12979410 :     BumpPtrAllocator& A = getAllocator();
     465             :     TreeTy* T;
     466    12979410 :     if (!freeNodes.empty()) {
     467     8636398 :       T = freeNodes.back();
     468     4318199 :       freeNodes.pop_back();
     469             :       assert(T != L);
     470             :       assert(T != R);
     471             :     } else {
     472     2171506 :       T = (TreeTy*) A.Allocate<TreeTy>();
     473             :     }
     474    12979410 :     new (T) TreeTy(this, L, R, V, incrementHeight(L,R));
     475     6489705 :     createdNodes.push_back(T);
     476     6489705 :     return T;
     477             :   }
     478             : 
     479             :   TreeTy* createNode(TreeTy* newLeft, TreeTy* oldTree, TreeTy* newRight) {
     480      758119 :     return createNode(newLeft, getValue(oldTree), newRight);
     481             :   }
     482             : 
     483     2676988 :   void recoverNodes() {
     484    11843681 :     for (unsigned i = 0, n = createdNodes.size(); i < n; ++i) {
     485    12979410 :       TreeTy *N = createdNodes[i];
     486     6489705 :       if (N->isMutable() && N->refCount == 0)
     487      297797 :         N->destroy();
     488             :     }
     489     5353976 :     createdNodes.clear();
     490     2676988 :   }
     491             : 
     492             :   /// balanceTree - Used by add_internal and remove_internal to
     493             :   ///  balance a newly created tree.
     494     3944975 :   TreeTy* balanceTree(TreeTy* L, value_type_ref V, TreeTy* R) {
     495     7889950 :     unsigned hl = getHeight(L);
     496     7889950 :     unsigned hr = getHeight(R);
     497             : 
     498     3944975 :     if (hl > hr + 2) {
     499             :       assert(!isEmpty(L) && "Left tree cannot be empty to have a height >= 2");
     500             : 
     501      114596 :       TreeTy *LL = getLeft(L);
     502      114596 :       TreeTy *LR = getRight(L);
     503             : 
     504      171894 :       if (getHeight(LL) >= getHeight(LR))
     505       40444 :         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       74152 :       TreeTy *LRL = getLeft(LR);
     510       74152 :       TreeTy *LRR = getRight(LR);
     511             : 
     512      111228 :       return createNode(createNode(LL,L,LRL), LR, createNode(LRR,V,R));
     513             :     }
     514             : 
     515     3887677 :     if (hr > hl + 2) {
     516             :       assert(!isEmpty(R) && "Right tree cannot be empty to have a height >= 2");
     517             : 
     518      497794 :       TreeTy *RL = getLeft(R);
     519      497794 :       TreeTy *RR = getRight(R);
     520             : 
     521      746691 :       if (getHeight(RR) >= getHeight(RL))
     522      418858 :         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       78936 :       TreeTy *RLL = getLeft(RL);
     527       78936 :       TreeTy *RLR = getRight(RL);
     528             : 
     529       78936 :       return createNode(createNode(L,V,RLL), RL, createNode(RLR,R,RR));
     530             :     }
     531             : 
     532     3638780 :     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     5456935 :   TreeTy* add_internal(value_type_ref V, TreeTy* T) {
     539     5456935 :     if (isEmpty(T))
     540     1798795 :       return createNode(T, V, T);
     541             :     assert(!T->isMutable());
     542             : 
     543     3658140 :     key_type_ref K = ImutInfo::KeyOfValue(V);
     544     6085009 :     key_type_ref KCurrent = ImutInfo::KeyOfValue(getValue(T));
     545             : 
     546     3658140 :     if (ImutInfo::isEqual(K,KCurrent))
     547     1089588 :       return createNode(getLeft(T), V, getRight(T));
     548     2638548 :     else if (ImutInfo::isLess(K,KCurrent))
     549     3344757 :       return balanceTree(add_internal(V, getLeft(T)), getValue(T), getRight(T));
     550             :     else
     551     9624169 :       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     1065343 :   TreeTy* remove_internal(key_type_ref K, TreeTy* T) {
     559     1065343 :     if (isEmpty(T))
     560             :       return T;
     561             : 
     562             :     assert(!T->isMutable());
     563             : 
     564     1010795 :     key_type_ref KCurrent = ImutInfo::KeyOfValue(getValue(T));
     565             : 
     566     1671237 :     if (ImutInfo::isEqual(K,KCurrent)) {
     567     1334520 :       return combineTrees(getLeft(T), getRight(T));
     568      935542 :     } else if (ImutInfo::isLess(K,KCurrent)) {
     569      659698 :       return balanceTree(remove_internal(K, getLeft(T)),
     570      191466 :                                             getValue(T), getRight(T));
     571             :     } else {
     572     1393841 :       return balanceTree(getLeft(T), getValue(T),
     573      358880 :                          remove_internal(K, getRight(T)));
     574             :     }
     575             :   }
     576             : 
     577      444840 :   TreeTy* combineTrees(TreeTy* L, TreeTy* R) {
     578      444840 :     if (isEmpty(L))
     579             :       return R;
     580      126105 :     if (isEmpty(R))
     581             :       return L;
     582             :     TreeTy* OldNode;
     583       89884 :     TreeTy* newRight = removeMinBinding(R,OldNode);
     584      177178 :     return balanceTree(L, getValue(OldNode), newRight);
     585             :   }
     586             : 
     587       99685 :   TreeTy* removeMinBinding(TreeTy* T, TreeTy*& Noderemoved) {
     588             :     assert(!isEmpty(T));
     589      199370 :     if (isEmpty(getLeft(T))) {
     590       89884 :       Noderemoved = T;
     591      179768 :       return getRight(T);
     592             :     }
     593       38789 :     return balanceTree(removeMinBinding(getLeft(T), Noderemoved),
     594        9801 :                        getValue(T), getRight(T));
     595             :   }
     596             : 
     597             :   /// markImmutable - Clears the mutable bits of a root and all of its
     598             :   ///  descendants.
     599     8793038 :   void markImmutable(TreeTy* T) {
     600    22902284 :     if (!T || !T->isMutable())
     601             :       return;
     602     6116050 :     T->markImmutable();
     603    12232100 :     markImmutable(getLeft(T));
     604    12232100 :     markImmutable(getRight(T));
     605             :   }
     606             : 
     607             : public:
     608     2081656 :   TreeTy *getCanonicalTree(TreeTy *TNew) {
     609     2081656 :     if (!TNew)
     610             :       return nullptr;
     611             : 
     612     1962789 :     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     1790523 :     unsigned digest = TNew->computeDigest();
     618     3581046 :     TreeTy *&entry = Cache[maskCacheIndex(digest)];
     619             :     do {
     620     1790523 :       if (!entry)
     621             :         break;
     622      860045 :       for (TreeTy *T = entry ; T != nullptr; T = T->next) {
     623             :         // Compare the Contents('T') with Contents('TNew')
     624      860043 :         typename TreeTy::iterator TI = T->begin(), TE = T->end();
     625      860043 :         if (!compareTreeWithSection(TNew, TI, TE))
     626           2 :           continue;
     627      860042 :         if (TI != TE)
     628           0 :           continue; // T has more contents than TNew.
     629             :         // Trees did match!  Return 'T'.
     630      860042 :         if (TNew->refCount == 0)
     631      645272 :           TNew->destroy();
     632     1720084 :         return T;
     633             :       }
     634           1 :       entry->prev = TNew;
     635           1 :       TNew->next = entry;
     636             :     }
     637             :     while (false);
     638             : 
     639      930481 :     entry = TNew;
     640      930481 :     TNew->IsCanonicalized = true;
     641      930481 :     return TNew;
     642             :   }
     643             : };
     644             : 
     645             : //===----------------------------------------------------------------------===//
     646             : // Immutable AVL-Tree Iterators.
     647             : //===----------------------------------------------------------------------===//
     648             : 
     649             : template <typename ImutInfo>
     650    31514158 : 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    10535558 :   ImutAVLTreeGenericIterator() = default;
     662    10886322 :   ImutAVLTreeGenericIterator(const TreeTy *Root) {
     663     5443161 :     if (Root) stack.push_back(reinterpret_cast<uintptr_t>(Root));
     664             :   }
     665             : 
     666             :   TreeTy &operator*() const {
     667             :     assert(!stack.empty());
     668    37030390 :     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   172974074 :     return stack.back() & Flags;
     675             :   }
     676             : 
     677    40886000 :   bool atEnd() const { return stack.empty(); }
     678             : 
     679             :   bool atBeginning() const {
     680             :     return stack.size() == 1 && getVisitState() == VisitedNone;
     681             :   }
     682             : 
     683    12281835 :   void skipToParent() {
     684             :     assert(!stack.empty());
     685    24563670 :     stack.pop_back();
     686    12281835 :     if (stack.empty())
     687             :       return;
     688     8910933 :     switch (getVisitState()) {
     689     4159328 :       case VisitedNone:
     690     8318656 :         stack.back() |= VisitedLeft;
     691     4159328 :         break;
     692     4751605 :       case VisitedLeft:
     693     9503210 :         stack.back() |= VisitedRight;
     694     4751605 :         break;
     695           0 :       default:
     696           0 :         llvm_unreachable("Unreachable.");
     697             :     }
     698             :   }
     699             : 
     700             :   bool operator==(const ImutAVLTreeGenericIterator &x) const {
     701    18960731 :     return stack == x.stack;
     702             :   }
     703             : 
     704             :   bool operator!=(const ImutAVLTreeGenericIterator &x) const {
     705             :     return !(*this == x);
     706             :   }
     707             : 
     708    40061006 :   ImutAVLTreeGenericIterator &operator++() {
     709             :     assert(!stack.empty());
     710    80122012 :     TreeTy* Current = reinterpret_cast<TreeTy*>(stack.back() & ~Flags);
     711             :     assert(Current);
     712    40061006 :     switch (getVisitState()) {
     713    15759300 :       case VisitedNone:
     714    15759300 :         if (TreeTy* L = Current->getLeft())
     715     4727717 :           stack.push_back(reinterpret_cast<uintptr_t>(L));
     716             :         else
     717    22063166 :           stack.back() |= VisitedLeft;
     718             :         break;
     719    12844865 :       case VisitedLeft:
     720    12844865 :         if (TreeTy* R = Current->getRight())
     721     6139629 :           stack.push_back(reinterpret_cast<uintptr_t>(R));
     722             :         else
     723    13410472 :           stack.back() |= VisitedRight;
     724             :         break;
     725    11456841 :       case VisitedRight:
     726    11456841 :         skipToParent();
     727    11456841 :         break;
     728           0 :       default:
     729           0 :         llvm_unreachable("Unreachable.");
     730             :     }
     731    40061006 :     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    31514157 : 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    10886322 :   ImutAVLTreeInOrderIterator(const TreeTy* Root) : InternalItr(Root) {
     772     5443161 :     if (Root)
     773             :       ++*this; // Advance to first element.
     774     5443161 :   }
     775             : 
     776    10535558 :   ImutAVLTreeInOrderIterator() : InternalItr() {}
     777             : 
     778             :   bool operator==(const ImutAVLTreeInOrderIterator &x) const {
     779    38003027 :     return InternalItr == x.InternalItr;
     780             :   }
     781             : 
     782             :   bool operator!=(const ImutAVLTreeInOrderIterator &x) const {
     783     9093537 :     return !(*this == x);
     784             :   }
     785             : 
     786    17822052 :   TreeTy &operator*() const { return *InternalItr; }
     787    24795700 :   TreeTy *operator->() const { return &*InternalItr; }
     788             : 
     789             :   ImutAVLTreeInOrderIterator &operator++() {
     790    40031753 :     do ++InternalItr;
     791   116724357 :     while (!InternalItr.atEnd() &&
     792    73321702 :            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      824994 :   void skipSubTree() {
     806      824994 :     InternalItr.skipToParent();
     807             : 
     808     2591994 :     while (!InternalItr.atEnd() &&
     809     1708494 :            InternalItr.getVisitState() != InternalIteratorTy::VisitedLeft)
     810       29253 :       ++InternalItr;
     811      824994 :   }
     812             : };
     813             : 
     814             : /// Generic iterator that wraps a T::TreeTy::iterator and exposes
     815             : /// iterator::getValue() on dereference.
     816             : template <typename T>
     817     9741504 : 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     4500102 :   ImutAVLValueIterator() = default;
     824     2425433 :   explicit ImutAVLValueIterator(typename T::TreeTy *Tree)
     825     7276299 :       : ImutAVLValueIterator::iterator_adaptor_base(Tree) {}
     826             : 
     827             :   typename ImutAVLValueIterator::reference operator*() const {
     828    15547794 :     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     6818744 :     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      264325 :     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         776 :     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     2038851 :     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    20357319 :     return std::equal_to<key_type>()(LHS,RHS);
     923             :   }
     924             : 
     925             :   static bool isLess(key_type_ref LHS, key_type_ref RHS) {
     926     7337257 :     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     1455121 :   explicit ImmutableSet(TreeTy* R) : Root(R) {
     974      643813 :     if (Root) { Root->retain(); }
     975             :   }
     976             : 
     977     2557143 :   ImmutableSet(const ImmutableSet &X) : Root(X.Root) {
     978     2556528 :     if (Root) { Root->retain(); }
     979             :   }
     980             : 
     981     3322447 :   ~ImmutableSet() {
     982     3322447 :     if (Root) { Root->release(); }
     983     3322447 :   }
     984             : 
     985     1073482 :   ImmutableSet &operator=(const ImmutableSet &X) {
     986     1073482 :     if (Root != X.Root) {
     987      805479 :       if (X.Root) { X.Root->retain(); }
     988      805479 :       if (Root) { Root->release(); }
     989      805479 :       Root = X.Root;
     990             :     }
     991     1073482 :     return *this;
     992             :   }
     993             : 
     994       49880 :   class Factory {
     995             :     typename TreeTy::Factory F;
     996             :     const bool Canonicalize;
     997             : 
     998             :   public:
     999       49431 :     Factory(bool canonicalize = true)
    1000       49431 :       : Canonicalize(canonicalize) {}
    1001             : 
    1002         449 :     Factory(BumpPtrAllocator& Alloc, bool canonicalize = true)
    1003         898 :       : 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      483904 :       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      398409 :     ImmutableSet add(ImmutableSet Old, value_type_ref V) {
    1021      398409 :       TreeTy *NewT = F.add(Old.Root, V);
    1022      796818 :       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      174080 :     ImmutableSet remove(ImmutableSet Old, value_type_ref V) {
    1033      174080 :       TreeTy *NewT = F.remove(Old.Root, V);
    1034      348160 :       return ImmutableSet(Canonicalize ? F.getCanonicalTree(NewT) : NewT);
    1035             :     }
    1036             : 
    1037             :     BumpPtrAllocator& getAllocator() { return F.getAllocator(); }
    1038             : 
    1039             :     typename TreeTy::Factory *getTreeFactory() const {
    1040       68262 :       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     2209807 :     return Root ? Root->contains(V) : false;
    1049             :   }
    1050             : 
    1051             :   bool operator==(const ImmutableSet &RHS) const {
    1052      679910 :     return Root && RHS.Root ? Root->isEqual(*RHS.Root) : Root == RHS.Root;
    1053             :   }
    1054             : 
    1055           6 :   bool operator!=(const ImmutableSet &RHS) const {
    1056           9 :     return Root && RHS.Root ? Root->isNotEqual(*RHS.Root) : Root != RHS.Root;
    1057             :   }
    1058             : 
    1059             :   TreeTy *getRoot() {
    1060         702 :     if (Root) { Root->retain(); }
    1061             :     return Root;
    1062             :   }
    1063             : 
    1064             :   TreeTy *getRootWithoutRetain() const {
    1065      136524 :     return Root;
    1066             :   }
    1067             : 
    1068             :   /// isEmpty - Return true if the set contains no elements.
    1069      171734 :   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       45126 :   bool isSingleton() const { return getHeight() == 1; }
    1074             : 
    1075             :   template <typename Callback>
    1076           3 :   void foreach(Callback& C) { if (Root) Root->foreach(C); }
    1077             : 
    1078             :   template <typename Callback>
    1079           2 :   void foreach() { if (Root) { Callback C; Root->foreach(C); } }
    1080             : 
    1081             :   //===--------------------------------------------------===//
    1082             :   // Iterators.
    1083             :   //===--------------------------------------------------===//
    1084             : 
    1085             :   using iterator = ImutAVLValueIterator<ImmutableSet>;
    1086             : 
    1087      319554 :   iterator begin() const { return iterator(Root); }
    1088      288344 :   iterator end() const { return iterator(); }
    1089             : 
    1090             :   //===--------------------------------------------------===//
    1091             :   // Utility methods.
    1092             :   //===--------------------------------------------------===//
    1093             : 
    1094       90252 :   unsigned getHeight() const { return Root ? Root->getHeight() : 0; }
    1095             : 
    1096             :   static void Profile(FoldingSetNodeID &ID, const ImmutableSet &S) {
    1097      673197 :     ID.AddPointer(S.Root);
    1098             :   }
    1099             : 
    1100      673197 :   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      136524 :   explicit ImmutableSetRef(TreeTy* R, FactoryTy *F)
    1128             :     : Root(R),
    1129      142839 :       Factory(F) {
    1130      142839 :     if (Root) { Root->retain(); }
    1131             :   }
    1132             : 
    1133      136524 :   ImmutableSetRef(const ImmutableSetRef &X)
    1134      136524 :     : Root(X.Root),
    1135      204786 :       Factory(X.Factory) {
    1136      204786 :     if (Root) { Root->retain(); }
    1137             :   }
    1138             : 
    1139      347625 :   ~ImmutableSetRef() {
    1140      347625 :     if (Root) { Root->release(); }
    1141      347625 :   }
    1142             : 
    1143       74577 :   ImmutableSetRef &operator=(const ImmutableSetRef &X) {
    1144       74577 :     if (Root != X.Root) {
    1145       28437 :       if (X.Root) { X.Root->retain(); }
    1146       28437 :       if (Root) { Root->release(); }
    1147       28437 :       Root = X.Root;
    1148       28437 :       Factory = X.Factory;
    1149             :     }
    1150       74577 :     return *this;
    1151             :   }
    1152             : 
    1153             :   static ImmutableSetRef getEmptySet(FactoryTy *F) {
    1154             :     return ImmutableSetRef(0, F);
    1155             :   }
    1156             : 
    1157        6315 :   ImmutableSetRef add(value_type_ref V) {
    1158       12630 :     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      136524 :                               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        4649 :   iterator begin() const { return iterator(Root); }
    1201        9298 :   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

Generated by: LCOV version 1.13