LCOV - code coverage report
Current view: top level - include/llvm/ADT - ImmutableSet.h (source / functions) Hit Total Coverage
Test: llvm-toolchain.info Lines: 1704 1908 89.3 %
Date: 2018-10-17 09:37:48 Functions: 1038 1928 53.8 %
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           0 :   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           0 :   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    44079243 :   unsigned getHeight() const { return height; }
      69             : 
      70             :   /// getValue - Returns the data value associated with the tree node.
      71    15760225 :   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     1722190 :   ImutAVLTree* find(key_type_ref K) {
      76             :     ImutAVLTree *T = this;
      77    27833337 :     while (T) {
      78     1756862 :       key_type_ref CurrentKey = ImutInfo::KeyOfValue(T->getValue());
      79    19062638 :       if (ImutInfo::isEqual(K,CurrentKey))
      80     1523672 :         return T;
      81    14080059 :       else if (ImutInfo::isLess(K,CurrentKey))
      82     8264964 :         T = T->getLeft();
      83             :       else
      84     8785676 :         T = T->getRight();
      85             :     }
      86             :     return nullptr;
      87             :   }
      88             : 
      89             :   /// getMaxElement - Find the subtree associated with the highest ranged
      90             :   ///  key value.
      91             :   ImutAVLTree* getMaxElement() {
      92             :     ImutAVLTree *T = this;
      93           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     2551419 :   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           0 :   iterator end() const { return iterator(); }
     117             : 
     118     1408445 :   bool isElementEqual(value_type_ref V) const {
     119             :     // Compare the keys.
     120    41879595 :     if (!ImutInfo::isEqual(ImutInfo::KeyOfValue(getValue()),
     121             :                            ImutInfo::KeyOfValue(V)))
     122           0 :       return false;
     123             : 
     124             :     // Also compare the data values.
     125    42409022 :     if (!ImutInfo::isDataEqual(ImutInfo::DataOfValue(getValue()),
     126             :                                ImutInfo::DataOfValue(V)))
     127           0 :       return false;
     128             : 
     129             :     return true;
     130             :   }
     131           0 : 
     132             :   bool isElementEqual(const ImutAVLTree* RHS) const {
     133     1426581 :     return isElementEqual(RHS->getValue());
     134             :   }
     135           0 : 
     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     2941744 :   bool isEqual(const ImutAVLTree& RHS) const {
     140     2941744 :     if (&RHS == this)
     141             :       return true;
     142             : 
     143             :     iterator LItr = begin(), LEnd = end();
     144           0 :     iterator RItr = RHS.begin(), REnd = RHS.end();
     145             : 
     146     5511380 :     while (LItr != LEnd && RItr != REnd) {
     147     2620447 :       if (&*LItr == &*RItr) {
     148      515863 :         LItr.skipSubTree();
     149      515863 :         RItr.skipSubTree();
     150      515863 :         continue;
     151             :       }
     152             : 
     153             :       if (!LItr->isElementEqual(&*RItr))
     154             :         return false;
     155             : 
     156     1432911 :       ++LItr;
     157     1432911 :       ++RItr;
     158             :     }
     159           0 : 
     160      136676 :     return LItr == LEnd && RItr == REnd;
     161           0 :   }
     162         666 : 
     163         666 :   /// isNotEqual - Compares two trees for structural inequality.  Performance
     164             :   ///  is the same is isEqual.
     165      656872 :   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          30 :   ///  is logarithmic in the size of the tree.
     170         358 :   bool contains(key_type_ref K) { return (bool) find(K); }
     171           0 : 
     172           4 :   /// foreach - A member template the accepts invokes operator() on a functor
     173           0 :   ///  object (specifed by Callback) for every node/subtree in the tree.
     174             :   ///  Nodes are visited using an inorder traversal.
     175             :   template <typename Callback>
     176             :   void foreach(Callback& C) {
     177             :     if (ImutAVLTree* L = getLeft())
     178           5 :       L->foreach(C);
     179          12 : 
     180           7 :     C(value);
     181             : 
     182             :     if (ImutAVLTree* R = getRight())
     183           2 :       R->foreach(C);
     184             :   }
     185        1221 : 
     186        1217 :   /// validateTree - A utility method that checks that the balancing and
     187           0 :   ///  ordering invariants of the tree are satisifed.  It is a recursive
     188           0 :   ///  method that returns the height of the tree, which is then consumed
     189           0 :   ///  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        1549 :   unsigned validateTree() const {
     193         743 :     unsigned HL = getLeft() ? getLeft()->validateTree() : 0;
     194          95 :     unsigned HR = getRight() ? getRight()->validateTree() : 0;
     195          95 :     (void) HL;
     196          95 :     (void) HR;
     197             : 
     198             :     assert(getHeight() == ( HL > HR ? HL : HR ) + 1
     199           0 :             && "Height calculation wrong");
     200             : 
     201             :     assert((HL > HR ? HL-HR : HR-HL) <= 2
     202         188 :            && "Balancing invariant violated");
     203         188 : 
     204           3 :     assert((!getLeft() ||
     205             :             ImutInfo::isLess(ImutInfo::KeyOfValue(getLeft()->getValue()),
     206          63 :                              ImutInfo::KeyOfValue(getValue()))) &&
     207             :            "Value in left child is not less that current value");
     208      641805 : 
     209      641805 : 
     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     4820386 :     return getHeight();
     216     2276380 :   }
     217      454971 : 
     218      454968 :   //===----------------------------------------------------===//
     219      454982 :   // Internal values.
     220             :   //===----------------------------------------------------===//
     221          14 : 
     222             : private:
     223           6 :   Factory *factory;
     224             :   ImutAVLTree *left;
     225     1332330 :   ImutAVLTree *right;
     226     1332330 :   ImutAVLTree *prev = nullptr;
     227             :   ImutAVLTree *next = nullptr;
     228             : 
     229      133839 :   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    18498841 :   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    17937966 :       IsDigestCached(false), IsCanonicalized(false), value(v)
     249             :   {
     250    17937938 :     if (left) left->retain();
     251    18498841 :     if (right) right->retain();
     252     1687890 :   }
     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    43681651 :   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    25384172 :   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    17314069 :     IsMutable = false;
     282             :   }
     283             : 
     284          91 :   /// markedCachedDigest - Clears the NoCachedDigest flag for a tree.
     285             :   void markedCachedDigest() {
     286             :     assert(!hasCachedDigest() && "NoCachedDigest flag already removed.");
     287    15613750 :     IsDigestCached = true;
     288             :   }
     289          91 : 
     290          91 :   /// setHeight - Changes the height of the tree.  Used internally by
     291      731311 :   ///  ImutAVLFactory.
     292             :   void setHeight(unsigned h) {
     293             :     assert(isMutable() && "Only a mutable tree can have its height changed.");
     294      731311 :     height = h;
     295             :   }
     296      731311 : 
     297    16588078 :   static uint32_t computeDigest(ImutAVLTree *L, ImutAVLTree *R,
     298             :                                 value_type_ref V) {
     299         183 :     uint32_t digest = 0;
     300             : 
     301    15856767 :     if (L)
     302     8236589 :       digest += L->computeDigest();
     303         121 : 
     304             :     // Compute digest of stored data.
     305             :     FoldingSetNodeID ID;
     306     6221186 :     ImutInfo::Profile(ID,V);
     307    15856767 :     digest += ID.ComputeHash();
     308             : 
     309    15856767 :     if (R)
     310    10250516 :       digest += R->computeDigest();
     311             : 
     312    15856767 :     return digest;
     313             :   }
     314     1119416 : 
     315    16556138 :   uint32_t computeDigest() {
     316             :     // Check the lowest bit to determine if digest has actually been
     317           8 :     // pre-computed.
     318    22943284 :     if (hasCachedDigest())
     319     8885781 :       return digest;
     320      415725 : 
     321    13499369 :     uint32_t X = computeDigest(getLeft(), getRight(), getValue());
     322     3545850 :     digest = X;
     323      673622 :     markedCachedDigest();
     324    10657378 :     return X;
     325             :   }
     326      703857 : 
     327      986739 :   //===----------------------------------------------------===//
     328             :   // Reference count operations.
     329     1646264 :   //===----------------------------------------------------===//
     330             : 
     331     1343204 : public:
     332    36182576 :   void retain() { ++refCount; }
     333      269030 : 
     334    18156576 :   void release() {
     335     1343204 :     assert(refCount > 0);
     336    48597177 :     if (--refCount == 0)
     337    12322091 :       destroy();
     338    18156576 :   }
     339             : 
     340    14925107 :   void destroy() {
     341    16234166 :     if (left)
     342     7666409 :       left->release();
     343    16260046 :     if (right)
     344    11283288 :       right->release();
     345    14891029 :     if (IsCanonicalized) {
     346     3426716 :       if (next)
     347       25896 :         next->prev = prev;
     348      310525 : 
     349     2772032 :       if (prev)
     350      415230 :         prev->next = next;
     351          83 :       else
     352     3840116 :         factory->Cache[factory->maskCacheIndex(computeDigest())] = next;
     353      263118 :     }
     354             : 
     355     1244265 :     // We need to clear the mutability bit in case we are
     356     1472298 :     // destroying the node as part of a sweep in ImutAVLFactory::recoverNodes().
     357    14891068 :     IsMutable = false;
     358    15704116 :     factory->freeNodes.push_back(this);
     359    14890946 :   }
     360      402817 : };
     361       28394 : 
     362          19 : //===----------------------------------------------------------------------===//
     363      402834 : // Immutable AVL-Tree Factory class.
     364       30867 : //===----------------------------------------------------------------------===//
     365        9041 : 
     366     1312803 : template <typename ImutInfo >
     367       70136 : class ImutAVLFactory {
     368          19 :   friend class ImutAVLTree<ImutInfo>;
     369     1756035 : 
     370      793615 :   using TreeTy = ImutAVLTree<ImutInfo>;
     371      587556 :   using value_type_ref = typename TreeTy::value_type_ref;
     372      885980 :   using key_type_ref = typename TreeTy::key_type_ref;
     373      885978 :   using CacheTy = DenseMap<unsigned, TreeTy*>;
     374      587589 : 
     375      867848 :   CacheTy Cache;
     376          14 :   uintptr_t Allocator;
     377      707412 :   std::vector<TreeTy*> createdNodes;
     378      418209 :   std::vector<TreeTy*> freeNodes;
     379          35 : 
     380      707445 :   bool ownsAllocator() const {
     381     3175105 :     return (Allocator & 0x1) == 0;
     382          33 :   }
     383      177551 : 
     384      171836 :   BumpPtrAllocator& getAllocator() const {
     385    19174961 :     return *reinterpret_cast<BumpPtrAllocator*>(Allocator & ~0x1);
     386      184745 :   }
     387        2997 : 
     388    18637246 :   //===--------------------------------------------------===//
     389        9951 :   // Public interface.
     390      878267 :   //===--------------------------------------------------===//
     391      930559 : 
     392    17928420 : public:
     393     4081784 :   ImutAVLFactory()
     394     4457612 :     : Allocator(reinterpret_cast<uintptr_t>(new BumpPtrAllocator())) {}
     395      575003 : 
     396       11243 :   ImutAVLFactory(BumpPtrAllocator& Alloc)
     397      586398 :     : Allocator(reinterpret_cast<uintptr_t>(&Alloc) | 0x1) {}
     398       82891 : 
     399     3190841 :   ~ImutAVLFactory() {
     400     3842905 :     if (ownsAllocator()) delete &getAllocator();
     401     3063857 :   }
     402      808106 : 
     403     3861898 :   TreeTy* add(TreeTy* T, value_type_ref V) {
     404     4203477 :     T = add_internal(V,T);
     405     3427747 :     markImmutable(T);
     406     4538208 :     recoverNodes();
     407     4494085 :     return T;
     408      479134 :   }
     409     1110683 : 
     410     1301180 :   TreeTy* remove(TreeTy* T, key_type_ref V) {
     411     1967627 :     T = remove_internal(V,T);
     412      963573 :     markImmutable(T);
     413      882743 :     recoverNodes();
     414      882870 :     return T;
     415       80673 :   }
     416     4370756 : 
     417           0 :   TreeTy* getEmptyTree() const { return nullptr; }
     418      776211 : 
     419       25959 : protected:
     420     2014193 :   //===--------------------------------------------------===//
     421      319110 :   // A bunch of quick helper functions used for reasoning
     422      691481 :   // about the properties of trees and their children.
     423     1609893 :   // These have succinct names so that the balancing code
     424     1084727 :   // is as terse (and readable) as possible.
     425     1609890 :   //===--------------------------------------------------===//
     426      440814 : 
     427      785405 :   bool            isEmpty(TreeTy* T) const { return !T; }
     428    36957000 :   unsigned        getHeight(TreeTy* T) const { return T ? T->getHeight() : 0; }
     429    28983096 :   TreeTy*         getLeft(TreeTy* T) const { return T->getLeft(); }
     430     1042738 :   TreeTy*         getRight(TreeTy* T) const { return T->getRight(); }
     431    13022860 :   value_type_ref  getValue(TreeTy* T) const { return T->value; }
     432       36632 : 
     433      142831 :   // Make sure the index is not the Tombstone or Entry key of the DenseMap.
     434     2086721 :   static unsigned maskCacheIndex(unsigned I) { return (I & ~0x02); }
     435      149398 : 
     436       83710 :   unsigned incrementHeight(TreeTy* L, TreeTy* R) const {
     437      139543 :     unsigned hl = getHeight(L);
     438       19732 :     unsigned hr = getHeight(R);
     439    16952354 :     return (hl > hr ? hl : hr) + 1;
     440      830255 :   }
     441      303975 : 
     442     1994284 :   static bool compareTreeWithSection(TreeTy* T,
     443      642203 :                                      typename TreeTy::iterator& TI,
     444     1194372 :                                      typename TreeTy::iterator& TE) {
     445      521193 :     typename TreeTy::iterator I = T->begin(), E = T->end();
     446    44868737 :     for ( ; I!=E ; ++I, ++TI) {
     447    44866841 :       if (TI == TE || !I->isElementEqual(&*TI))
     448      781313 :         return false;
     449      842918 :     }
     450      372663 :     return true;
     451     1084698 :   }
     452       59063 : 
     453           0 :   //===--------------------------------------------------===//
     454       25894 :   // "createNode" is used to generate new tree roots that link
     455       33246 :   // to other trees.  The functon may also simply move links
     456      830283 :   // in an existing root if that root is still marked mutable.
     457      830325 :   // This is necessary because otherwise our balancing code
     458      869464 :   // would leak memory as it would create nodes that are
     459      342835 :   // then discarded later before the finished tree is
     460      342826 :   // returned to the caller.
     461      245072 :   //===--------------------------------------------------===//
     462     1404237 : 
     463    17232238 :   TreeTy* createNode(TreeTy* L, value_type_ref V, TreeTy* R) {
     464    17786436 :     BumpPtrAllocator& A = getAllocator();
     465      880906 :     TreeTy* T;
     466    18376171 :     if (!freeNodes.empty()) {
     467    10954372 :       T = freeNodes.back();
     468      544344 :       freeNodes.pop_back();
     469        1027 :       assert(T != L);
     470        1890 :       assert(T != R);
     471       50922 :     } else {
     472     6163263 :       T = (TreeTy*) A.Allocate<TreeTy>();
     473        2483 :     }
     474    16123020 :     new (T) TreeTy(this, L, R, V, incrementHeight(L,R));
     475    16367694 :     createdNodes.push_back(T);
     476    16708976 :     return T;
     477      345171 :   }
     478      342970 : 
     479      774620 :   TreeTy* createNode(TreeTy* newLeft, TreeTy* oldTree, TreeTy* newRight) {
     480     1284418 :     return createNode(newLeft, getValue(oldTree), newRight);
     481      492103 :   }
     482      618353 : 
     483     4799475 :   void recoverNodes() {
     484    24983323 :     for (unsigned i = 0, n = createdNodes.size(); i < n; ++i) {
     485    17016982 :       TreeTy *N = createdNodes[i];
     486    16868911 :       if (N->isMutable() && N->refCount == 0)
     487     1271985 :         N->destroy();
     488      879384 :     }
     489      221488 :     createdNodes.clear();
     490     5015089 :   }
     491      203320 : 
     492           0 :   /// balanceTree - Used by add_internal and remove_internal to
     493           0 :   ///  balance a newly created tree.
     494    11636430 :   TreeTy* balanceTree(TreeTy* L, value_type_ref V, TreeTy* R) {
     495          91 :     unsigned hl = getHeight(L);
     496      283038 :     unsigned hr = getHeight(R);
     497     1937224 : 
     498    11912247 :     if (hl > hr + 2) {
     499      204613 :       assert(!isEmpty(L) && "Left tree cannot be empty to have a height >= 2");
     500      204596 : 
     501       58717 :       TreeTy *LL = getLeft(L);
     502      935916 :       TreeTy *LR = getRight(L);
     503      812179 : 
     504     1081159 :       if (getHeight(LL) >= getHeight(LR))
     505      138420 :         return createNode(LL, L, createNode(LR,V,R));
     506       34684 : 
     507       34642 :       assert(!isEmpty(LR) && "LR cannot be empty because it has a height >= 1");
     508       29916 : 
     509       10584 :       TreeTy *LRL = getLeft(LR);
     510       10654 :       TreeTy *LRR = getRight(LR);
     511       59955 : 
     512      246801 :       return createNode(createNode(LL,L,LRL), LR, createNode(LRR,V,R));
     513       10667 :     }
     514        5245 : 
     515    11488614 :     if (hr > hl + 2) {
     516      204624 :       assert(!isEmpty(R) && "Right tree cannot be empty to have a height >= 2");
     517      239385 : 
     518      239315 :       TreeTy *RL = getLeft(R);
     519       34723 :       TreeTy *RR = getRight(R);
     520       11042 : 
     521      828533 :       if (getHeight(RR) >= getHeight(RL))
     522     1568560 :         return createNode(createNode(L,V,RL), R, RR);
     523       23751 : 
     524       23726 :       assert(!isEmpty(RL) && "RL cannot be empty because it has a height >= 1");
     525       23651 : 
     526           0 :       TreeTy *RLL = getLeft(RL);
     527      824155 :       TreeTy *RLR = getRight(RL);
     528      824144 : 
     529      901711 :       return createNode(createNode(L,V,RLL), RL, createNode(RLR,R,RR));
     530      824238 :     }
     531      824227 : 
     532    10666598 :     return createNode(L,V,R);
     533      319217 :   }
     534      339093 : 
     535      343470 :   /// add_internal - Creates a new tree that includes the specified
     536      327447 :   ///  data and the data from the original tree.  If the original tree
     537      327443 :   ///  already contained the data item, the original tree is returned.
     538    12710659 :   TreeTy* add_internal(value_type_ref V, TreeTy* T) {
     539    13204178 :     if (isEmpty(T))
     540     3856190 :       return createNode(T, V, T);
     541     6811502 :     assert(!T->isMutable());
     542      501830 : 
     543      501845 :     key_type_ref K = ImutInfo::KeyOfValue(V);
     544      725663 :     key_type_ref KCurrent = ImutInfo::KeyOfValue(getValue(T));
     545     6327982 : 
     546     6713885 :     if (ImutInfo::isEqual(K,KCurrent))
     547      682058 :       return createNode(getLeft(T), V, getRight(T));
     548     6634037 :     else if (ImutInfo::isLess(K,KCurrent))
     549     2672417 :       return balanceTree(add_internal(V, getLeft(T)), getValue(T), getRight(T));
     550     1080867 :     else
     551     7207191 :       return balanceTree(getLeft(T), getValue(T), add_internal(V, getRight(T)));
     552      139637 :   }
     553      143007 : 
     554      128225 :   /// remove_internal - Creates a new tree that includes all the data
     555      136606 :   ///  from the original tree except the specified data.  If the
     556      130888 :   ///  specified data did not exist in the original tree, the original
     557       16676 :   ///  tree is returned.
     558     3022624 :   TreeTy* remove_internal(key_type_ref K, TreeTy* T) {
     559     3022455 :     if (isEmpty(T))
     560      226645 :       return T;
     561      217143 : 
     562      948229 :     assert(!T->isMutable());
     563      738762 : 
     564      903961 :     key_type_ref KCurrent = ImutInfo::KeyOfValue(getValue(T));
     565       87320 : 
     566     2720148 :     if (ImutInfo::isEqual(K,KCurrent)) {
     567      882870 :       return combineTrees(getLeft(T), getRight(T));
     568     1852751 :     } else if (ImutInfo::isLess(K,KCurrent)) {
     569       13363 :       return balanceTree(remove_internal(K, getLeft(T)),
     570      991318 :                                             getValue(T), getRight(T));
     571        6184 :     } else {
     572       11021 :       return balanceTree(getLeft(T), getValue(T),
     573      952180 :                          remove_internal(K, getRight(T)));
     574           0 :     }
     575       98419 :   }
     576     2827935 : 
     577     4183315 :   TreeTy* combineTrees(TreeTy* L, TreeTy* R) {
     578      896151 :     if (isEmpty(L))
     579     1018614 :       return R;
     580      350390 :     if (isEmpty(R))
     581       11021 :       return L;
     582       38207 :     TreeTy* OldNode;
     583      262873 :     TreeTy* newRight = removeMinBinding(R,OldNode);
     584      262873 :     return balanceTree(L, getValue(OldNode), newRight);
     585           0 :   }
     586       48130 : 
     587     3712821 :   TreeTy* removeMinBinding(TreeTy* T, TreeTy*& Noderemoved) {
     588      676879 :     assert(!isEmpty(T));
     589      469642 :     if (isEmpty(getLeft(T))) {
     590      723066 :       Noderemoved = T;
     591      277444 :       return getRight(T);
     592       40064 :     }
     593      261405 :     return balanceTree(removeMinBinding(getLeft(T), Noderemoved),
     594      149669 :                        getValue(T), getRight(T));
     595           0 :   }
     596       14549 : 
     597           0 :   /// markImmutable - Clears the mutable bits of a root and all of its
     598      739801 :   ///  descendants.
     599    20130594 :   void markImmutable(TreeTy* T) {
     600    34806368 :     if (!T || !T->isMutable())
     601       69553 :       return;
     602       12793 :     T->markImmutable();
     603    15079181 :     markImmutable(getLeft(T));
     604      958741 :     markImmutable(getRight(T));
     605     1748095 :   }
     606      789768 : 
     607        9162 : public:
     608     3797012 :   TreeTy *getCanonicalTree(TreeTy *TNew) {
     609     3781060 :     if (!TNew)
     610      152148 :       return nullptr;
     611          11 : 
     612     3637898 :     if (TNew->IsCanonicalized)
     613       16154 :       return TNew;
     614      214177 : 
     615      205017 :     // Search the hashtable for another tree with the same digest, and
     616       48106 :     // if find a collision compare those trees by their contents.
     617       48193 :     unsigned digest = TNew->computeDigest();
     618     3620442 :     TreeTy *&entry = Cache[maskCacheIndex(digest)];
     619       16034 :     do {
     620     3859846 :       if (!entry)
     621       16438 :         break;
     622     1909968 :       for (TreeTy *T = entry ; T != nullptr; T = T->next) {
     623      741581 :         // Compare the Contents('T') with Contents('TNew')
     624      753315 :         typename TreeTy::iterator TI = T->begin(), TE = T->end();
     625     2642880 :         if (!compareTreeWithSection(TNew, TI, TE))
     626      339283 :           continue;
     627     1164047 :         if (TI != TE)
     628       48150 :           continue; // T has more contents than TNew.
     629      146523 :         // Trees did match!  Return 'T'.
     630     1310548 :         if (TNew->refCount == 0)
     631     1419053 :           TNew->destroy();
     632      118086 :         return T;
     633      767160 :       }
     634      741605 :       entry->prev = TNew;
     635      745234 :       TNew->next = entry;
     636       19696 :     }
     637       19692 :     while (false);
     638       92946 : 
     639     2503120 :     entry = TNew;
     640     2534484 :     TNew->IsCanonicalized = true;
     641     4345997 :     return TNew;
     642     1909984 :   }
     643      287374 : };
     644     1890533 : 
     645     1610593 : //===----------------------------------------------------------------------===//
     646        6201 : // Immutable AVL-Tree Iterators.
     647       71222 : //===----------------------------------------------------------------------===//
     648       12055 : 
     649        2620 : template <typename ImutInfo>
     650      284996 : class ImutAVLTreeGenericIterator
     651        5638 :     : public std::iterator<std::bidirectional_iterator_tag,
     652     1534810 :                            ImutAVLTree<ImutInfo>> {
     653     2195493 :   SmallVector<uintptr_t,20> stack;
     654     1573213 : 
     655      117358 : public:
     656      375742 :   enum VisitFlag { VisitedNone=0x0, VisitedLeft=0x1, VisitedRight=0x3,
     657      931113 :                    Flags=0x3 };
     658         556 : 
     659      533655 :   using TreeTy = ImutAVLTree<ImutInfo>;
     660      453938 : 
     661      244066 :   ImutAVLTreeGenericIterator() = default;
     662      277241 :   ImutAVLTreeGenericIterator(const TreeTy *Root) {
     663     4327164 :     if (Root) stack.push_back(reinterpret_cast<uintptr_t>(Root));
     664        3777 :   }
     665       79760 : 
     666      266306 :   TreeTy &operator*() const {
     667      526078 :     assert(!stack.empty());
     668    91620017 :     return *reinterpret_cast<TreeTy *>(stack.back() & ~Flags);
     669      526210 :   }
     670      298793 :   TreeTy *operator->() const { return &*this; }
     671     1296331 : 
     672     1309139 :   uintptr_t getVisitState() const {
     673       14353 :     assert(!stack.empty());
     674   594210845 :     return stack.back() & Flags;
     675     1083527 :   }
     676       20286 : 
     677   256002530 :   bool atEnd() const { return stack.empty(); }
     678        5059 : 
     679       27766 :   bool atBeginning() const {
     680      321651 :     return stack.size() == 1 && getVisitState() == VisitedNone;
     681      120628 :   }
     682     1308912 : 
     683    85745945 :   void skipToParent() {
     684     1521135 :     assert(!stack.empty());
     685      256716 :     stack.pop_back();
     686    84746030 :     if (stack.empty())
     687      252618 :       return;
     688    82764294 :     switch (getVisitState()) {
     689    41264046 :       case VisitedNone:
     690    41269756 :         stack.back() |= VisitedLeft;
     691    42926074 :         break;
     692    45769604 :       case VisitedLeft:
     693    43470248 :         stack.back() |= VisitedRight;
     694    43473656 :         break;
     695       82823 :       default:
     696       75828 :         llvm_unreachable("Unreachable.");
     697      526068 :     }
     698     1672395 :   }
     699      520751 : 
     700     1865965 :   bool operator==(const ImutAVLTreeGenericIterator &x) const {
     701    50721241 :     return stack == x.stack;
     702     2500772 :   }
     703     1583737 : 
     704        9851 :   bool operator!=(const ImutAVLTreeGenericIterator &x) const {
     705      434584 :     return !(*this == x);
     706      553361 :   }
     707     1083598 : 
     708   258635978 :   ImutAVLTreeGenericIterator &operator++() {
     709     1276741 :     assert(!stack.empty());
     710   257486754 :     TreeTy* Current = reinterpret_cast<TreeTy*>(stack.back() & ~Flags);
     711       18057 :     assert(Current);
     712   255875934 :     switch (getVisitState()) {
     713    87731161 :       case VisitedNone:
     714    87719075 :         if (TreeTy* L = Current->getLeft())
     715    42468224 :           stack.push_back(reinterpret_cast<uintptr_t>(L));
     716        1138 :         else
     717    44573279 :           stack.back() |= VisitedLeft;
     718      806968 :         break;
     719    84539124 :       case VisitedLeft:
     720    84531268 :         if (TreeTy* R = Current->getRight())
     721    41407920 :           stack.push_back(reinterpret_cast<uintptr_t>(R));
     722      790682 :         else
     723    43151784 :           stack.back() |= VisitedRight;
     724       46797 :         break;
     725    84357419 :       case VisitedRight:
     726    84355533 :         skipToParent();
     727    84395616 :         break;
     728       21671 :       default:
     729        5191 :         llvm_unreachable("Unreachable.");
     730         155 :     }
     731   255884449 :     return *this;
     732        9162 :   }
     733       14034 : 
     734      425747 :   ImutAVLTreeGenericIterator &operator--() {
     735       22729 :     assert(!stack.empty());
     736       60577 :     TreeTy* Current = reinterpret_cast<TreeTy*>(stack.back() & ~Flags);
     737        4603 :     assert(Current);
     738             :     switch (getVisitState()) {
     739      773614 :       case VisitedNone:
     740           2 :         stack.pop_back();
     741         194 :         break;
     742        6620 :       case VisitedLeft:
     743           0 :         stack.back() &= ~Flags; // Set state to "VisitedNone."
     744       46363 :         if (TreeTy* L = Current->getLeft())
     745       14516 :           stack.push_back(reinterpret_cast<uintptr_t>(L) | VisitedRight);
     746       46721 :         break;
     747        5981 :       case VisitedRight:
     748           0 :         stack.back() &= ~Flags;
     749        3212 :         stack.back() |= VisitedLeft;
     750       22258 :         if (TreeTy* R = Current->getRight())
     751        3212 :           stack.push_back(reinterpret_cast<uintptr_t>(R) | VisitedRight);
     752         309 :         break;
     753        1800 :       default:
     754        3212 :         llvm_unreachable("Unreachable.");
     755        3202 :     }
     756      766145 :     return *this;
     757       11160 :   }
     758      748200 : };
     759      880274 : 
     760       19613 : template <typename ImutInfo>
     761     3894706 : class ImutAVLTreeInOrderIterator
     762      249597 :     : public std::iterator<std::bidirectional_iterator_tag,
     763       34778 :                            ImutAVLTree<ImutInfo>> {
     764       32771 :   using InternalIteratorTy = ImutAVLTreeGenericIterator<ImutInfo>;
     765       49217 : 
     766       16625 :   InternalIteratorTy InternalItr;
     767      247123 : 
     768      228463 : public:
     769        9297 :   using TreeTy = ImutAVLTree<ImutInfo>;
     770          91 : 
     771     4273967 :   ImutAVLTreeInOrderIterator(const TreeTy* Root) : InternalItr(Root) {
     772     4075718 :     if (Root)
     773     3416450 :       ++*this; // Advance to first element.
     774     4085182 :   }
     775        9780 : 
     776       16192 :   ImutAVLTreeInOrderIterator() : InternalItr() {}
     777      215211 : 
     778        9811 :   bool operator==(const ImutAVLTreeInOrderIterator &x) const {
     779      264315 :     return InternalItr == x.InternalItr;
     780       56923 :   }
     781       69620 : 
     782      974560 :   bool operator!=(const ImutAVLTreeInOrderIterator &x) const {
     783     1002685 :     return !(*this == x);
     784      334582 :   }
     785      976118 : 
     786      631173 :   TreeTy &operator*() const { return *InternalItr; }
     787       14280 :   TreeTy *operator->() const { return &*InternalItr; }
     788          52 : 
     789    87774950 :   ImutAVLTreeInOrderIterator &operator++() {
     790   255960389 :     do ++InternalItr;
     791   256310254 :     while (!InternalItr.atEnd() &&
     792       25260 :            InternalItr.getVisitState() != InternalIteratorTy::VisitedLeft);
     793      731973 : 
     794    88427648 :     return *this;
     795      731577 :   }
     796       49309 : 
     797        2249 :   ImutAVLTreeInOrderIterator &operator--() {
     798      953985 :     do --InternalItr;
     799      135964 :     while (!InternalItr.atBeginning() &&
     800      136034 :            InternalItr.getVisitState() != InternalIteratorTy::VisitedLeft);
     801       44288 : 
     802      740393 :     return *this;
     803        2039 :   }
     804         408 : 
     805      121634 :   void skipSubTree() {
     806      364668 :     InternalItr.skipToParent();
     807      289732 : 
     808      378560 :     while (!InternalItr.atEnd() &&
     809      244405 :            InternalItr.getVisitState() != InternalIteratorTy::VisitedLeft)
     810      257854 :       ++InternalItr;
     811      121624 :   }
     812        2406 : };
     813        4880 : 
     814       33018 : /// Generic iterator that wraps a T::TreeTy::iterator and exposes
     815         849 : /// iterator::getValue() on dereference.
     816       60174 : template <typename T>
     817        2367 : struct ImutAVLValueIterator
     818       29812 :     : iterator_adaptor_base<
     819      740068 :           ImutAVLValueIterator<T>, typename T::TreeTy::iterator,
     820       15569 :           typename std::iterator_traits<
     821         256 :               typename T::TreeTy::iterator>::iterator_category,
     822      256903 :           const typename T::value_type> {
     823       11161 :   ImutAVLValueIterator() = default;
     824     1389899 :   explicit ImutAVLValueIterator(typename T::TreeTy *Tree)
     825     1413440 :       : ImutAVLValueIterator::iterator_adaptor_base(Tree) {}
     826       25919 : 
     827     2310831 :   typename ImutAVLValueIterator::reference operator*() const {
     828      735798 :     return this->I->getValue();
     829        9456 :   }
     830      779145 : };
     831     1057376 : 
     832      882163 : //===----------------------------------------------------------------------===//
     833    28599536 : // Trait classes for Profile information.
     834      217581 : //===----------------------------------------------------------------------===//
     835         588 : 
     836    14035631 : /// Generic profile template.  The default behavior is to invoke the
     837       43551 : /// profile method of an object.  Specializations for primitive integers
     838      759606 : /// and generic handling of pointers is done below.
     839      739983 : template <typename T>
     840      747281 : struct ImutProfileInfo {
     841       25454 :   using value_type = const T;
     842     5691305 :   using value_type_ref = const T&;
     843     1170939 : 
     844      672521 :   static void Profile(FoldingSetNodeID &ID, value_type_ref X) {
     845     4148365 :     FoldingSetTrait<T>::Profile(X,ID);
     846       21996 :   }
     847     4104907 : };
     848     3454145 : 
     849     2363219 : /// Profile traits for integers.
     850     2800339 : template <typename T>
     851     2058674 : struct ImutProfileInteger {
     852     2431415 :   using value_type = const T;
     853     2170018 :   using value_type_ref = const T&;
     854      560712 : 
     855      332995 :   static void Profile(FoldingSetNodeID &ID, value_type_ref X) {
     856    10068103 :     ID.AddInteger(X);
     857      236640 :   }
     858     4072045 : };
     859      201027 : 
     860       20523 : #define PROFILE_INTEGER_INFO(X)\
     861     3851212 : template<> struct ImutProfileInfo<X> : ImutProfileInteger<X> {};
     862       10283 : 
     863     3532925 : PROFILE_INTEGER_INFO(char)
     864     1729831 : PROFILE_INTEGER_INFO(unsigned char)
     865     1709942 : PROFILE_INTEGER_INFO(short)
     866     1615985 : PROFILE_INTEGER_INFO(unsigned short)
     867     1965046 : PROFILE_INTEGER_INFO(unsigned)
     868     1934269 : PROFILE_INTEGER_INFO(signed)
     869     2131637 : PROFILE_INTEGER_INFO(long)
     870      301918 : PROFILE_INTEGER_INFO(unsigned long)
     871      503377 : PROFILE_INTEGER_INFO(long long)
     872     2637122 : PROFILE_INTEGER_INFO(unsigned long long)
     873     1652038 : 
     874     1479609 : #undef PROFILE_INTEGER_INFO
     875        7540 : 
     876        3951 : /// Profile traits for booleans.
     877      303654 : template <>
     878      505070 : struct ImutProfileInfo<bool> {
     879       69249 :   using value_type = const bool;
     880      468916 :   using value_type_ref = const bool&;
     881       60577 : 
     882      910105 :   static void Profile(FoldingSetNodeID &ID, value_type_ref X) {
     883      224033 :     ID.AddBoolean(X);
     884       56963 :   }
     885      324891 : };
     886      483301 : 
     887        2334 : /// Generic profile trait for pointer types.  We treat pointers as
     888        3726 : /// references to unique objects.
     889       10334 : template <typename T>
     890       13541 : struct ImutProfileInfo<T*> {
     891        5434 :   using value_type = const T*;
     892     1700216 :   using value_type_ref = value_type;
     893      764977 : 
     894       17094 :   static void Profile(FoldingSetNodeID &ID, value_type_ref X) {
     895     9760970 :     ID.AddPointer(X);
     896       46542 :   }
     897       40491 : };
     898       14560 : 
     899    12840949 : //===----------------------------------------------------------------------===//
     900      727969 : // Trait classes that contain element comparison operators and type
     901    13109780 : //  definitions used by ImutAVLTree, ImmutableSet, and ImmutableMap.  These
     902      419479 : //  inherit from the profile traits (ImutProfileInfo) to include operations
     903    13298807 : //  for element profiling.
     904     4726799 : //===----------------------------------------------------------------------===//
     905     4671367 : 
     906     1559292 : /// ImutContainerInfo - Generic definition of comparison operations for
     907      267186 : ///   elements of immutable containers that defaults to using
     908     3023471 : ///   std::equal_to<> and std::less<> to perform comparison of elements.
     909      209271 : template <typename T>
     910     4591824 : struct ImutContainerInfo : public ImutProfileInfo<T> {
     911     4380428 :   using value_type = typename ImutProfileInfo<T>::value_type;
     912     1980510 :   using value_type_ref = typename ImutProfileInfo<T>::value_type_ref;
     913       27236 :   using key_type = value_type;
     914     2189987 :   using key_type_ref = value_type_ref;
     915       45163 :   using data_type = bool;
     916     4127590 :   using data_type_ref = bool;
     917     4126441 : 
     918     4384192 :   static key_type_ref KeyOfValue(value_type_ref D) { return D; }
     919      119809 :   static data_type_ref DataOfValue(value_type_ref) { return true; }
     920      598334 : 
     921      114581 :   static bool isEqual(key_type_ref LHS, key_type_ref RHS) {
     922    13041015 :     return std::equal_to<key_type>()(LHS,RHS);
     923        2376 :   }
     924    11495576 : 
     925      119648 :   static bool isLess(key_type_ref LHS, key_type_ref RHS) {
     926    11921650 :     return std::less<key_type>()(LHS,RHS);
     927      419331 :   }
     928    12063027 : 
     929     4824709 :   static bool isDataEqual(data_type_ref, data_type_ref) { return true; }
     930     4026366 : };
     931     1553536 : 
     932       28505 : /// ImutContainerInfo - Specialization for pointer values to treat pointers
     933     2286303 : ///  as references to unique objects.  Pointers are thus compared by
     934        5628 : ///  their addresses.
     935     4100379 : template <typename T>
     936     4350912 : struct ImutContainerInfo<T*> : public ImutProfileInfo<T*> {
     937     2499108 :   using value_type = typename ImutProfileInfo<T*>::value_type;
     938      703054 :   using value_type_ref = typename ImutProfileInfo<T*>::value_type_ref;
     939     2349138 :   using key_type = value_type;
     940       92868 :   using key_type_ref = value_type_ref;
     941     3830935 :   using data_type = bool;
     942     3834039 :   using data_type_ref = bool;
     943     4023183 : 
     944       72113 :   static key_type_ref KeyOfValue(value_type_ref D) { return D; }
     945       72105 :   static data_type_ref DataOfValue(value_type_ref) { return true; }
     946        3129 : 
     947    11770024 :   static bool isEqual(key_type_ref LHS, key_type_ref RHS) { return LHS == RHS; }
     948      321117 : 
     949     1341086 :   static bool isLess(key_type_ref LHS, key_type_ref RHS) { return LHS < RHS; }
     950      106106 : 
     951     1333288 :   static bool isDataEqual(data_type_ref, data_type_ref) { return true; }
     952          36 : };
     953     1423205 : 
     954      849905 : //===----------------------------------------------------------------------===//
     955      744478 : // Immutable Set
     956      154391 : //===----------------------------------------------------------------------===//
     957      120966 : 
     958      755839 : template <typename ValT, typename ValInfo = ImutContainerInfo<ValT>>
     959       52815 : class ImmutableSet {
     960      295050 : public:
     961      308644 :   using value_type = typename ValInfo::value_type;
     962       98047 :   using value_type_ref = typename ValInfo::value_type_ref;
     963       67731 :   using TreeTy = ImutAVLTree<ValInfo>;
     964      248750 : 
     965      157526 : private:
     966      464993 :   TreeTy *Root;
     967      301541 : 
     968      347101 : public:
     969          52 :   /// Constructs a set from a pointer to a tree root.  In general one
     970         420 :   /// should use a Factory object to create sets instead of directly
     971       29989 :   /// invoking the constructor, but there are cases where make this
     972     1362773 :   /// constructor public is useful.
     973       30161 :   explicit ImmutableSet(TreeTy* R) : Root(R) {
     974        4040 :     if (Root) { Root->retain(); }
     975      115895 :   }
     976       18698 : 
     977      123037 :   ImmutableSet(const ImmutableSet &X) : Root(X.Root) {
     978       80906 :     if (Root) { Root->retain(); }
     979      124834 :   }
     980       55236 : 
     981        9691 :   ~ImmutableSet() {
     982       33120 :     if (Root) { Root->release(); }
     983       29428 :   }
     984       65552 : 
     985           0 :   ImmutableSet &operator=(const ImmutableSet &X) {
     986      486665 :     if (Root != X.Root) {
     987      464728 :       if (X.Root) { X.Root->retain(); }
     988       60386 :       if (Root) { Root->release(); }
     989      432404 :       Root = X.Root;
     990      199433 :     }
     991       38712 :     return *this;
     992           0 :   }
     993       38423 : 
     994         161 :   class Factory {
     995      252177 :     typename TreeTy::Factory F;
     996       40446 :     const bool Canonicalize;
     997      445180 : 
     998      426592 :   public:
     999      440489 :     Factory(bool canonicalize = true)
    1000       27825 :       : Canonicalize(canonicalize) {}
    1001       17727 : 
    1002      616520 :     Factory(BumpPtrAllocator& Alloc, bool canonicalize = true)
    1003        1573 :       : F(Alloc), Canonicalize(canonicalize) {}
    1004           9 : 
    1005     2641984 :     Factory(const Factory& RHS) = delete;
    1006     5345023 :     void operator=(const Factory& RHS) = delete;
    1007      902584 : 
    1008      416794 :     /// getEmptySet - Returns an immutable set that contains no elements.
    1009     2399988 :     ImmutableSet getEmptySet() {
    1010       10668 :       return ImmutableSet(F.getEmptyTree());
    1011       10036 :     }
    1012      959637 : 
    1013     1941071 :     /// add - Creates a new immutable set that contains all of the values
    1014      267646 :     ///  of the original set with the addition of the specified value.  If
    1015      267628 :     ///  the original set already included the value, then the original set is
    1016      887688 :     ///  returned and no memory is allocated.  The time and space complexity
    1017      142537 :     ///  of this operation is logarithmic in the size of the original set.
    1018      158090 :     ///  The memory allocated to represent the set is released when the
    1019     2093453 :     ///  factory object that created the set is destroyed.
    1020     3291265 :     LLVM_NODISCARD ImmutableSet add(ImmutableSet Old, value_type_ref V) {
    1021      108402 :       TreeTy *NewT = F.add(Old.Root, V);
    1022      108632 :       return ImmutableSet(Canonicalize ? F.getCanonicalTree(NewT) : NewT);
    1023     1816176 :     }
    1024       15896 : 
    1025         496 :     /// remove - Creates a new immutable set that contains all of the values
    1026       15626 :     ///  of the original set with the exception of the specified value.  If
    1027           0 :     ///  the original set did not contain the value, the original set is
    1028      961312 :     ///  returned and no memory is allocated.  The time and space complexity
    1029      957428 :     ///  of this operation is logarithmic in the size of the original set.
    1030        4556 :     ///  The memory allocated to represent the set is released when the
    1031        7112 :     ///  factory object that created the set is destroyed.
    1032      918663 :     LLVM_NODISCARD ImmutableSet remove(ImmutableSet Old, value_type_ref V) {
    1033        7047 :       TreeTy *NewT = F.remove(Old.Root, V);
    1034          52 :       return ImmutableSet(Canonicalize ? F.getCanonicalTree(NewT) : NewT);
    1035           6 :     }
    1036        6934 : 
    1037        8311 :     BumpPtrAllocator& getAllocator() { return F.getAllocator(); }
    1038     6124753 : 
    1039    13727853 :     typename TreeTy::Factory *getTreeFactory() const {
    1040    14424486 :       return const_cast<typename TreeTy::Factory *>(&F);
    1041      415628 :     }
    1042      389012 :   };
    1043     5168648 : 
    1044          19 :   friend class Factory;
    1045     4825976 : 
    1046    12043307 :   /// Returns true if the set contains the specified value.
    1047    12431690 :   bool contains(value_type_ref V) const {
    1048      253746 :     return Root ? Root->contains(V) : false;
    1049      171954 :   }
    1050     4574243 : 
    1051      240347 :   bool operator==(const ImmutableSet &RHS) const {
    1052     1278429 :     return Root && RHS.Root ? Root->isEqual(*RHS.Root) : Root == RHS.Root;
    1053     1505338 :   }
    1054     1628966 : 
    1055       24691 :   bool operator!=(const ImmutableSet &RHS) const {
    1056      276156 :     return Root && RHS.Root ? Root->isNotEqual(*RHS.Root) : Root != RHS.Root;
    1057     1164396 :   }
    1058             : 
    1059      419616 :   TreeTy *getRoot() {
    1060      330081 :     if (Root) { Root->retain(); }
    1061      324739 :     return Root;
    1062          52 :   }
    1063      219569 : 
    1064      219558 :   TreeTy *getRootWithoutRetain() const {
    1065             :     return Root;
    1066        4109 :   }
    1067      219433 : 
    1068        4091 :   /// isEmpty - Return true if the set contains no elements.
    1069      332239 :   bool isEmpty() const { return !Root; }
    1070      172263 : 
    1071          15 :   /// isSingleton - Return true if the set contains exactly one element.
    1072          15 :   ///   This method runs in constant time.
    1073      213157 :   bool isSingleton() const { return getHeight() == 1; }
    1074      118700 : 
    1075      213157 :   template <typename Callback>
    1076       39855 :   void foreach(Callback& C) { if (Root) Root->foreach(C); }
    1077      184596 : 
    1078       15018 :   template <typename Callback>
    1079        6483 :   void foreach() { if (Root) { Callback C; Root->foreach(C); } }
    1080      874969 : 
    1081             :   //===--------------------------------------------------===//
    1082      170057 :   // Iterators.
    1083      376665 :   //===--------------------------------------------------===//
    1084       36041 : 
    1085      157926 :   using iterator = ImutAVLValueIterator<ImmutableSet>;
    1086      144177 : 
    1087      243323 :   iterator begin() const { return iterator(Root); }
    1088       65024 :   iterator end() const { return iterator(); }
    1089      192049 : 
    1090           0 :   //===--------------------------------------------------===//
    1091      502237 :   // Utility methods.
    1092      624248 :   //===--------------------------------------------------===//
    1093      232130 : 
    1094      127862 :   unsigned getHeight() const { return Root ? Root->getHeight() : 0; }
    1095      104789 : 
    1096      105903 :   static void Profile(FoldingSetNodeID &ID, const ImmutableSet &S) {
    1097      307136 :     ID.AddPointer(S.Root);
    1098      757934 :   }
    1099     1028042 : 
    1100       70187 :   void Profile(FoldingSetNodeID &ID) const { return Profile(ID, *this); }
    1101      258728 : 
    1102      871843 :   //===--------------------------------------------------===//
    1103             :   // For testing.
    1104       89312 :   //===--------------------------------------------------===//
    1105       28904 : 
    1106        3043 :   void validateTree() const { if (Root) Root->validateTree(); }
    1107         257 : };
    1108      529583 : 
    1109             : // NOTE: This may some day replace the current ImmutableSet.
    1110      513871 : template <typename ValT, typename ValInfo = ImutContainerInfo<ValT>>
    1111      568856 : class ImmutableSetRef {
    1112      736554 : public:
    1113        8003 :   using value_type = typename ValInfo::value_type;
    1114        5214 :   using value_type_ref = typename ValInfo::value_type_ref;
    1115      248984 :   using TreeTy = ImutAVLTree<ValInfo>;
    1116        7296 :   using FactoryTy = typename TreeTy::Factory;
    1117      699598 : 
    1118           0 : private:
    1119      454711 :   TreeTy *Root;
    1120      480015 :   FactoryTy *Factory;
    1121      419884 : 
    1122       34890 : public:
    1123      157754 :   /// Constructs a set from a pointer to a tree root.  In general one
    1124       93144 :   /// should use a Factory object to create sets instead of directly
    1125       18576 :   /// invoking the constructor, but there are cases where make this
    1126      110696 :   /// constructor public is useful.
    1127       29161 :   explicit ImmutableSetRef(TreeTy* R, FactoryTy *F)
    1128       29242 :     : Root(R),
    1129      304364 :       Factory(F) {
    1130      293210 :     if (Root) { Root->retain(); }
    1131      281053 :   }
    1132       17864 : 
    1133           0 :   ImmutableSetRef(const ImmutableSetRef &X)
    1134        7305 :     : Root(X.Root),
    1135       16289 :       Factory(X.Factory) {
    1136        1965 :     if (Root) { Root->retain(); }
    1137       16698 :   }
    1138       12287 : 
    1139      427836 :   ~ImmutableSetRef() {
    1140        7826 :     if (Root) { Root->release(); }
    1141        5075 :   }
    1142        3625 : 
    1143           0 :   ImmutableSetRef &operator=(const ImmutableSetRef &X) {
    1144        4242 :     if (Root != X.Root) {
    1145          33 :       if (X.Root) { X.Root->retain(); }
    1146      371376 :       if (Root) { Root->release(); }
    1147        5627 :       Root = X.Root;
    1148      368984 :       Factory = X.Factory;
    1149         701 :     }
    1150      367008 :     return *this;
    1151      122309 :   }
    1152      122100 : 
    1153     3487458 :   static ImmutableSetRef getEmptySet(FactoryTy *F) {
    1154        3864 :     return ImmutableSetRef(0, F);
    1155       86677 :   }
    1156        2454 : 
    1157      123117 :   ImmutableSetRef add(value_type_ref V) {
    1158     8846170 :     return ImmutableSetRef(Factory->add(Root, V), Factory);
    1159       24434 :   }
    1160           0 : 
    1161       99547 :   ImmutableSetRef remove(value_type_ref V) {
    1162     1100628 :     return ImmutableSetRef(Factory->remove(Root, V), Factory);
    1163      128296 :   }
    1164    34501208 : 
    1165      588353 :   /// Returns true if the set contains the specified value.
    1166      472280 :   bool contains(value_type_ref V) const {
    1167    16857287 :     return Root ? Root->contains(V) : false;
    1168        1963 :   }
    1169      366813 : 
    1170         673 :   ImmutableSet<ValT> asImmutableSet(bool canonicalize = true) const {
    1171      525718 :     return ImmutableSet<ValT>(canonicalize ?
    1172        1606 :                               Factory->getCanonicalTree(Root) : Root);
    1173     6144868 :   }
    1174      225899 : 
    1175      300845 :   TreeTy *getRootWithoutRetain() const {
    1176     5647126 :     return Root;
    1177      183506 :   }
    1178     3149434 : 
    1179     1517138 :   bool operator==(const ImmutableSetRef &RHS) const {
    1180     1597632 :     return Root && RHS.Root ? Root->isEqual(*RHS.Root) : Root == RHS.Root;
    1181     1519745 :   }
    1182     1653201 : 
    1183     1653201 :   bool operator!=(const ImmutableSetRef &RHS) const {
    1184     1865712 :     return Root && RHS.Root ? Root->isNotEqual(*RHS.Root) : Root != RHS.Root;
    1185      236205 :   }
    1186       23696 : 
    1187        9282 :   /// isEmpty - Return true if the set contains no elements.
    1188       47508 :   bool isEmpty() const { return !Root; }
    1189     2248896 : 
    1190       51353 :   /// isSingleton - Return true if the set contains exactly one element.
    1191        4001 :   ///   This method runs in constant time.
    1192     2238701 :   bool isSingleton() const { return getHeight() == 1; }
    1193       18193 : 
    1194      653828 :   //===--------------------------------------------------===//
    1195      194250 :   // Iterators.
    1196      476057 :   //===--------------------------------------------------===//
    1197      199584 : 
    1198      634543 :   using iterator = ImutAVLValueIterator<ImmutableSetRef>;
    1199      361417 : 
    1200      643942 :   iterator begin() const { return iterator(Root); }
    1201       97845 :   iterator end() const { return iterator(); }
    1202       95060 : 
    1203       33733 :   //===--------------------------------------------------===//
    1204           6 :   // Utility methods.
    1205     3468456 :   //===--------------------------------------------------===//
    1206       10730 : 
    1207      103838 :   unsigned getHeight() const { return Root ? Root->getHeight() : 0; }
    1208     3493564 : 
    1209      190429 :   static void Profile(FoldingSetNodeID &ID, const ImmutableSetRef &S) {
    1210     2593043 :     ID.AddPointer(S.Root);
    1211     1641720 :   }
    1212     1547651 : 
    1213     1589476 :   void Profile(FoldingSetNodeID &ID) const { return Profile(ID, *this); }
    1214     1372117 : 
    1215     1364193 :   //===--------------------------------------------------===//
    1216     1271319 :   // For testing.
    1217        5494 :   //===--------------------------------------------------===//
    1218        4073 : 
    1219      281315 :   void validateTree() const { if (Root) Root->validateTree(); }
    1220        4473 : };
    1221        8104 : 
    1222         223 : } // end namespace llvm
    1223    10522590 : 
    1224        4085 : #endif // LLVM_ADT_IMMUTABLESET_H

Generated by: LCOV version 1.13