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 44152971 : unsigned getHeight() const { return height; }
69 :
70 : /// getValue - Returns the data value associated with the tree node.
71 15841598 : 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 27880068 : while (T) {
78 1756862 : key_type_ref CurrentKey = ImutInfo::KeyOfValue(T->getValue());
79 19109081 : if (ImutInfo::isEqual(K,CurrentKey))
80 1523672 : return T;
81 14099457 : else if (ImutInfo::isLess(K,CurrentKey))
82 8246032 : T = T->getLeft();
83 : else
84 8823842 : 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 2555468 : 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 1408474 : bool isElementEqual(value_type_ref V) const {
119 : // Compare the keys.
120 41891913 : if (!ImutInfo::isEqual(ImutInfo::KeyOfValue(getValue()),
121 : ImutInfo::KeyOfValue(V)))
122 0 : return false;
123 :
124 : // Also compare the data values.
125 42421366 : 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 1426610 : 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 2941773 : bool isEqual(const ImutAVLTree& RHS) const {
140 2941773 : if (&RHS == this)
141 : return true;
142 :
143 : iterator LItr = begin(), LEnd = end();
144 0 : iterator RItr = RHS.begin(), REnd = RHS.end();
145 :
146 5511426 : while (LItr != LEnd && RItr != REnd) {
147 2620464 : if (&*LItr == &*RItr) {
148 515875 : LItr.skipSubTree();
149 515875 : RItr.skipSubTree();
150 515875 : continue;
151 : }
152 :
153 : if (!LItr->isElementEqual(&*RItr))
154 : return false;
155 :
156 1432922 : ++LItr;
157 1432922 : ++RItr;
158 : }
159 0 :
160 136682 : 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 4820432 : return getHeight();
216 2276397 : }
217 454983 :
218 454980 : //===----------------------------------------------------===//
219 454994 : // Internal values.
220 : //===----------------------------------------------------===//
221 14 :
222 : private:
223 6 : Factory *factory;
224 : ImutAVLTree *left;
225 1332341 : ImutAVLTree *right;
226 1332341 : ImutAVLTree *prev = nullptr;
227 : ImutAVLTree *next = nullptr;
228 :
229 133845 : 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 18581247 : 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 18020371 : IsDigestCached(false), IsCanonicalized(false), value(v)
249 : {
250 18020343 : if (left) left->retain();
251 18581247 : if (right) right->retain();
252 1687410 : }
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 43855548 : 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 25527682 : 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 17395053 : 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 15695017 : 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 16669345 : static uint32_t computeDigest(ImutAVLTree *L, ImutAVLTree *R,
298 : value_type_ref V) {
299 183 : uint32_t digest = 0;
300 :
301 15938034 : if (L)
302 8247265 : digest += L->computeDigest();
303 121 :
304 : // Compute digest of stored data.
305 : FoldingSetNodeID ID;
306 6221074 : ImutInfo::Profile(ID,V);
307 15938034 : digest += ID.ComputeHash();
308 :
309 15938034 : if (R)
310 10275030 : digest += R->computeDigest();
311 :
312 15938034 : return digest;
313 : }
314 1119527 :
315 16591154 : uint32_t computeDigest() {
316 : // Check the lowest bit to determine if digest has actually been
317 8 : // pre-computed.
318 23086750 : if (hasCachedDigest())
319 8947844 : return digest;
320 415724 :
321 13580646 : uint32_t X = computeDigest(getLeft(), getRight(), getValue());
322 3599710 : digest = X;
323 673746 : markedCachedDigest();
324 10684907 : return X;
325 : }
326 703969 :
327 986851 : //===----------------------------------------------------===//
328 : // Reference count operations.
329 1646384 : //===----------------------------------------------------===//
330 :
331 1343104 : public:
332 37363533 : void retain() { ++refCount; }
333 269030 :
334 18193903 : void release() {
335 1343104 : assert(refCount > 0);
336 50283284 : if (--refCount == 0)
337 12399906 : destroy();
338 18193903 : }
339 :
340 15008229 : void destroy() {
341 16317170 : if (left)
342 7677427 : left->release();
343 16343050 : if (right)
344 11309579 : right->release();
345 14974133 : if (IsCanonicalized) {
346 3478809 : if (next)
347 25896 : next->prev = prev;
348 310532 :
349 2824437 : if (prev)
350 415241 : prev->next = next;
351 83 : else
352 3892537 : factory->Cache[factory->maskCacheIndex(computeDigest())] = next;
353 263263 : }
354 :
355 1244324 : // We need to clear the mutability bit in case we are
356 1472357 : // destroying the node as part of a sweep in ImutAVLFactory::recoverNodes().
357 14974179 : IsMutable = false;
358 15787298 : factory->freeNodes.push_back(this);
359 14974050 : }
360 402922 : };
361 28411 :
362 19 : //===----------------------------------------------------------------------===//
363 402939 : // Immutable AVL-Tree Factory class.
364 30861 : //===----------------------------------------------------------------------===//
365 9012 :
366 1312935 : template <typename ImutInfo >
367 70240 : class ImutAVLFactory {
368 19 : friend class ImutAVLTree<ImutInfo>;
369 1756105 :
370 793754 : using TreeTy = ImutAVLTree<ImutInfo>;
371 587670 : using value_type_ref = typename TreeTy::value_type_ref;
372 885931 : using key_type_ref = typename TreeTy::key_type_ref;
373 885929 : using CacheTy = DenseMap<unsigned, TreeTy*>;
374 587703 :
375 867907 : CacheTy Cache;
376 14 : uintptr_t Allocator;
377 707350 : std::vector<TreeTy*> createdNodes;
378 418013 : std::vector<TreeTy*> freeNodes;
379 35 :
380 707383 : bool ownsAllocator() const {
381 3792154 : return (Allocator & 0x1) == 0;
382 33 : }
383 177484 :
384 171835 : BumpPtrAllocator& getAllocator() const {
385 19874738 : return *reinterpret_cast<BumpPtrAllocator*>(Allocator & ~0x1);
386 184686 : }
387 2959 :
388 18637340 : //===--------------------------------------------------===//
389 9931 : // Public interface.
390 878636 : //===--------------------------------------------------===//
391 930587 :
392 17928863 : public:
393 4698590 : ImutAVLFactory()
394 5074991 : : Allocator(reinterpret_cast<uintptr_t>(new BumpPtrAllocator())) {}
395 575087 :
396 11243 : ImutAVLFactory(BumpPtrAllocator& Alloc)
397 586482 : : Allocator(reinterpret_cast<uintptr_t>(&Alloc) | 0x1) {}
398 83037 :
399 3808031 : ~ImutAVLFactory() {
400 4460200 : if (ownsAllocator()) delete &getAllocator();
401 3680905 : }
402 808353 :
403 3911159 : TreeTy* add(TreeTy* T, value_type_ref V) {
404 4253358 : T = add_internal(V,T);
405 3477381 : markImmutable(T);
406 4587666 : recoverNodes();
407 4543543 : return T;
408 479573 : }
409 1110507 :
410 1310042 : TreeTy* remove(TreeTy* T, key_type_ref V) {
411 1976363 : T = remove_internal(V,T);
412 972482 : markImmutable(T);
413 891655 : recoverNodes();
414 891782 : return T;
415 80670 : }
416 4370486 :
417 0 : TreeTy* getEmptyTree() const { return nullptr; }
418 776079 :
419 25961 : protected:
420 2014063 : //===--------------------------------------------------===//
421 319045 : // A bunch of quick helper functions used for reasoning
422 691355 : // about the properties of trees and their children.
423 1609591 : // These have succinct names so that the balancing code
424 1084551 : // is as terse (and readable) as possible.
425 1609588 : //===--------------------------------------------------===//
426 440874 :
427 785332 : bool isEmpty(TreeTy* T) const { return !T; }
428 37083293 : unsigned getHeight(TreeTy* T) const { return T ? T->getHeight() : 0; }
429 29106510 : TreeTy* getLeft(TreeTy* T) const { return T->getLeft(); }
430 1044327 : TreeTy* getRight(TreeTy* T) const { return T->getRight(); }
431 13056063 : value_type_ref getValue(TreeTy* T) const { return T->value; }
432 36631 :
433 142808 : // Make sure the index is not the Tombstone or Entry key of the DenseMap.
434 2138893 : static unsigned maskCacheIndex(unsigned I) { return (I & ~0x02); }
435 149397 :
436 83686 : unsigned incrementHeight(TreeTy* L, TreeTy* R) const {
437 139543 : unsigned hl = getHeight(L);
438 19731 : unsigned hr = getHeight(R);
439 17034961 : return (hl > hr ? hl : hr) + 1;
440 830133 : }
441 303753 :
442 1998126 : static bool compareTreeWithSection(TreeTy* T,
443 642420 : typename TreeTy::iterator& TI,
444 1194290 : typename TreeTy::iterator& TE) {
445 521269 : typename TreeTy::iterator I = T->begin(), E = T->end();
446 44880660 : for ( ; I!=E ; ++I, ++TI) {
447 44878794 : if (TI == TE || !I->isElementEqual(&*TI))
448 781686 : return false;
449 842604 : }
450 372425 : return true;
451 1084350 : }
452 59061 :
453 0 : //===--------------------------------------------------===//
454 25894 : // "createNode" is used to generate new tree roots that link
455 33244 : // to other trees. The functon may also simply move links
456 830161 : // in an existing root if that root is still marked mutable.
457 830203 : // This is necessary because otherwise our balancing code
458 869340 : // would leak memory as it would create nodes that are
459 342714 : // then discarded later before the finished tree is
460 342705 : // returned to the caller.
461 244850 : //===--------------------------------------------------===//
462 1404116 :
463 17314758 : TreeTy* createNode(TreeTy* L, value_type_ref V, TreeTy* R) {
464 17868747 : BumpPtrAllocator& A = getAllocator();
465 880581 : TreeTy* T;
466 18458869 : if (!freeNodes.empty()) {
467 10965448 : T = freeNodes.back();
468 544289 : freeNodes.pop_back();
469 1009 : assert(T != L);
470 1859 : assert(T != R);
471 50898 : } else {
472 6234830 : T = (TreeTy*) A.Allocate<TreeTy>();
473 2455 : }
474 16205814 : new (T) TreeTy(this, L, R, V, incrementHeight(L,R));
475 16450395 : createdNodes.push_back(T);
476 16791487 : return T;
477 345022 : }
478 342850 :
479 774620 : TreeTy* createNode(TreeTy* newLeft, TreeTy* oldTree, TreeTy* newRight) {
480 1286012 : return createNode(newLeft, getValue(oldTree), newRight);
481 492104 : }
482 618329 :
483 4858021 : void recoverNodes() {
484 25183177 : for (unsigned i = 0, n = createdNodes.size(); i < n; ++i) {
485 17099743 : TreeTy *N = createdNodes[i];
486 16951672 : if (N->isMutable() && N->refCount == 0)
487 1273306 : N->destroy();
488 879384 : }
489 221460 : createdNodes.clear();
490 5073607 : }
491 203292 :
492 2 : /// balanceTree - Used by add_internal and remove_internal to
493 2 : /// balance a newly created tree.
494 11667862 : TreeTy* balanceTree(TreeTy* L, value_type_ref V, TreeTy* R) {
495 93 : unsigned hl = getHeight(L);
496 283038 : unsigned hr = getHeight(R);
497 1937106 :
498 11943679 : if (hl > hr + 2) {
499 204612 : assert(!isEmpty(L) && "Left tree cannot be empty to have a height >= 2");
500 204595 :
501 58716 : TreeTy *LL = getLeft(L);
502 935915 : TreeTy *LR = getRight(L);
503 812180 :
504 1081071 : if (getHeight(LL) >= getHeight(LR))
505 138024 : 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 29892 :
509 10586 : TreeTy *LRL = getLeft(LR);
510 10656 : TreeTy *LRR = getRight(LR);
511 59933 :
512 246999 : return createNode(createNode(LL,L,LRL), LR, createNode(LRR,V,R));
513 10667 : }
514 5246 :
515 11520133 : if (hr > hl + 2) {
516 204622 : assert(!isEmpty(R) && "Right tree cannot be empty to have a height >= 2");
517 239384 :
518 239314 : TreeTy *RL = getLeft(R);
519 34723 : TreeTy *RR = getRight(R);
520 11042 :
521 830121 : if (getHeight(RR) >= getHeight(RL))
522 1571550 : 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 901897 : return createNode(createNode(L,V,RLL), RL, createNode(RLR,R,RR));
530 824238 : }
531 824227 :
532 10696532 : return createNode(L,V,R);
533 319220 : }
534 339084 :
535 343473 : /// add_internal - Creates a new tree that includes the specified
536 327452 : /// data and the data from the original tree. If the original tree
537 327446 : /// already contained the data item, the original tree is returned.
538 12786096 : TreeTy* add_internal(value_type_ref V, TreeTy* T) {
539 13279615 : if (isEmpty(T))
540 3905824 : return createNode(T, V, T);
541 6811498 : assert(!T->isMutable());
542 501830 :
543 501845 : key_type_ref K = ImutInfo::KeyOfValue(V);
544 725496 : key_type_ref KCurrent = ImutInfo::KeyOfValue(getValue(T));
545 6327978 :
546 6739929 : if (ImutInfo::isEqual(K,KCurrent))
547 682058 : return createNode(getLeft(T), V, getRight(T));
548 6660105 : else if (ImutInfo::isLess(K,KCurrent))
549 2675917 : return balanceTree(add_internal(V, getLeft(T)), getValue(T), getRight(T));
550 1080870 : else
551 7229500 : return balanceTree(getLeft(T), getValue(T), add_internal(V, getRight(T)));
552 139603 : }
553 142947 :
554 128297 : /// remove_internal - Creates a new tree that includes all the data
555 136560 : /// from the original tree except the specified data. If the
556 130787 : /// specified data did not exist in the original tree, the original
557 16643 : /// tree is returned.
558 3036364 : TreeTy* remove_internal(key_type_ref K, TreeTy* T) {
559 3036195 : if (isEmpty(T))
560 226645 : return T;
561 217144 :
562 948229 : assert(!T->isMutable());
563 738749 :
564 904002 : key_type_ref KCurrent = ImutInfo::KeyOfValue(getValue(T));
565 87374 :
566 2733884 : if (ImutInfo::isEqual(K,KCurrent)) {
567 891807 : return combineTrees(getLeft(T), getRight(T));
568 1857579 : } else if (ImutInfo::isLess(K,KCurrent)) {
569 13330 : return balanceTree(remove_internal(K, getLeft(T)),
570 992347 : getValue(T), getRight(T));
571 6145 : } else {
572 11021 : return balanceTree(getLeft(T), getValue(T),
573 955940 : remove_internal(K, getRight(T)));
574 0 : }
575 98440 : }
576 2828184 :
577 4191897 : TreeTy* combineTrees(TreeTy* L, TreeTy* R) {
578 905140 : if (isEmpty(L))
579 1018497 : return R;
580 351330 : if (isEmpty(R))
581 11021 : return L;
582 38205 : TreeTy* OldNode;
583 263502 : TreeTy* newRight = removeMinBinding(R,OldNode);
584 263502 : return balanceTree(L, getValue(OldNode), newRight);
585 0 : }
586 48130 :
587 3713011 : TreeTy* removeMinBinding(TreeTy* T, TreeTy*& Noderemoved) {
588 676646 : assert(!isEmpty(T));
589 470381 : if (isEmpty(getLeft(T))) {
590 723505 : Noderemoved = T;
591 278062 : return getRight(T);
592 40070 : }
593 261363 : return balanceTree(removeMinBinding(getLeft(T), Noderemoved),
594 149840 : getValue(T), getRight(T));
595 0 : }
596 14547 :
597 0 : /// markImmutable - Clears the mutable bits of a root and all of its
598 739621 : /// descendants.
599 20270404 : void markImmutable(TreeTy* T) {
600 35027441 : if (!T || !T->isMutable())
601 69594 : return;
602 12793 : T->markImmutable();
603 15160435 : markImmutable(getLeft(T));
604 958744 : markImmutable(getRight(T));
605 1748134 : }
606 789806 :
607 9162 : public:
608 3855556 : TreeTy *getCanonicalTree(TreeTy *TNew) {
609 3839557 : if (!TNew)
610 152145 : return nullptr;
611 12 :
612 3694129 : if (TNew->IsCanonicalized)
613 16160 : return TNew;
614 214187 :
615 205027 : // 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 3676569 : TreeTy *&entry = Cache[maskCacheIndex(digest)];
619 16034 : do {
620 3915988 : if (!entry)
621 16438 : break;
622 1913747 : for (TreeTy *T = entry ; T != nullptr; T = T->next) {
623 741414 : // Compare the Contents('T') with Contents('TNew')
624 753306 : typename TreeTy::iterator TI = T->begin(), TE = T->end();
625 2646668 : if (!compareTreeWithSection(TNew, TI, TE))
626 339156 : continue;
627 1168013 : if (TI != TE)
628 48151 : continue; // T has more contents than TNew.
629 146544 : // Trees did match! Return 'T'.
630 1314535 : if (TNew->refCount == 0)
631 1422979 : TNew->destroy();
632 118107 : return T;
633 767012 : }
634 741436 : entry->prev = TNew;
635 745065 : TNew->next = entry;
636 19698 : }
637 19692 : while (false);
638 92948 :
639 2555171 : entry = TNew;
640 2586682 : TNew->IsCanonicalized = true;
641 4398067 : return TNew;
642 1909877 : }
643 287374 : };
644 1890417 :
645 1610424 : //===----------------------------------------------------------------------===//
646 6203 : // Immutable AVL-Tree Iterators.
647 71234 : //===----------------------------------------------------------------------===//
648 12069 :
649 2620 : template <typename ImutInfo>
650 285050 : class ImutAVLTreeGenericIterator
651 5638 : : public std::iterator<std::bidirectional_iterator_tag,
652 1534682 : ImutAVLTree<ImutInfo>> {
653 2195299 : SmallVector<uintptr_t,20> stack;
654 1573085 :
655 117370 : public:
656 375746 : enum VisitFlag { VisitedNone=0x0, VisitedLeft=0x1, VisitedRight=0x3,
657 931071 : Flags=0x3 };
658 556 :
659 533674 : using TreeTy = ImutAVLTree<ImutInfo>;
660 453946 :
661 244066 : ImutAVLTreeGenericIterator() = default;
662 277249 : ImutAVLTreeGenericIterator(const TreeTy *Root) {
663 4453556 : if (Root) stack.push_back(reinterpret_cast<uintptr_t>(Root));
664 3787 : }
665 79771 :
666 266306 : TreeTy &operator*() const {
667 526088 : assert(!stack.empty());
668 91649342 : return *reinterpret_cast<TreeTy *>(stack.back() & ~Flags);
669 526220 : }
670 298801 : TreeTy *operator->() const { return &*this; }
671 1296214 :
672 1309009 : uintptr_t getVisitState() const {
673 14349 : assert(!stack.empty());
674 594651437 : return stack.back() & Flags;
675 1083349 : }
676 20288 :
677 256225650 : bool atEnd() const { return stack.empty(); }
678 5059 :
679 27766 : bool atBeginning() const {
680 321649 : return stack.size() == 1 && getVisitState() == VisitedNone;
681 120607 : }
682 1308787 :
683 85820173 : void skipToParent() {
684 1520997 : assert(!stack.empty());
685 256716 : stack.pop_back();
686 84820409 : if (stack.empty())
687 252618 : return;
688 82798788 : switch (getVisitState()) {
689 41272426 : case VisitedNone:
690 41278122 : stack.back() |= VisitedLeft;
691 42934449 : break;
692 45795388 : case VisitedLeft:
693 43496046 : stack.back() |= VisitedRight;
694 43499481 : break;
695 82818 : default:
696 75853 : llvm_unreachable("Unreachable.");
697 525978 : }
698 1672346 : }
699 520752 :
700 1865807 : bool operator==(const ImutAVLTreeGenericIterator &x) const {
701 50748197 : return stack == x.stack;
702 2500614 : }
703 1583663 :
704 9848 : bool operator!=(const ImutAVLTreeGenericIterator &x) const {
705 434510 : return !(*this == x);
706 553383 : }
707 1083522 :
708 258858855 : ImutAVLTreeGenericIterator &operator++() {
709 1276603 : assert(!stack.empty());
710 257709787 : TreeTy* Current = reinterpret_cast<TreeTy*>(stack.back() & ~Flags);
711 18125 : assert(Current);
712 256099054 : switch (getVisitState()) {
713 87805520 : case VisitedNone:
714 87793433 : if (TreeTy* L = Current->getLeft())
715 42476583 : stack.push_back(reinterpret_cast<uintptr_t>(L));
716 1138 : else
717 44639278 : stack.back() |= VisitedLeft;
718 806693 : break;
719 84613497 : case VisitedLeft:
720 84605646 : if (TreeTy* R = Current->getRight())
721 41434010 : stack.push_back(reinterpret_cast<uintptr_t>(R));
722 790474 : else
723 43200055 : stack.back() |= VisitedRight;
724 46861 : break;
725 84431751 : case VisitedRight:
726 84429900 : skipToParent();
727 84469973 : break;
728 21712 : default:
729 5339 : llvm_unreachable("Unreachable.");
730 155 : }
731 256107569 : return *this;
732 9162 : }
733 14035 :
734 425746 : ImutAVLTreeGenericIterator &operator--() {
735 22699 : assert(!stack.empty());
736 60504 : TreeTy* Current = reinterpret_cast<TreeTy*>(stack.back() & ~Flags);
737 4603 : assert(Current);
738 : switch (getVisitState()) {
739 773365 : case VisitedNone:
740 2 : stack.pop_back();
741 196 : break;
742 6619 : case VisitedLeft:
743 0 : stack.back() &= ~Flags; // Set state to "VisitedNone."
744 46383 : if (TreeTy* L = Current->getLeft())
745 14552 : stack.push_back(reinterpret_cast<uintptr_t>(L) | VisitedRight);
746 46712 : break;
747 5981 : case VisitedRight:
748 0 : stack.back() &= ~Flags;
749 3207 : stack.back() |= VisitedLeft;
750 22260 : if (TreeTy* R = Current->getRight())
751 3207 : stack.push_back(reinterpret_cast<uintptr_t>(R) | VisitedRight);
752 291 : break;
753 1878 : default:
754 3207 : llvm_unreachable("Unreachable.");
755 3197 : }
756 765851 : return *this;
757 11151 : }
758 748184 : };
759 880172 :
760 19613 : template <typename ImutInfo>
761 4021083 : class ImutAVLTreeInOrderIterator
762 249592 : : public std::iterator<std::bidirectional_iterator_tag,
763 34818 : ImutAVLTree<ImutInfo>> {
764 32775 : using InternalIteratorTy = ImutAVLTreeGenericIterator<ImutInfo>;
765 49221 :
766 16628 : InternalIteratorTy InternalItr;
767 247128 :
768 228465 : public:
769 9297 : using TreeTy = ImutAVLTree<ImutInfo>;
770 91 :
771 4400344 : ImutAVLTreeInOrderIterator(const TreeTy* Root) : InternalItr(Root) {
772 4202096 : if (Root)
773 3456355 : ++*this; // Advance to first element.
774 4211559 : }
775 9780 :
776 16191 : ImutAVLTreeInOrderIterator() : InternalItr() {}
777 215225 :
778 9812 : bool operator==(const ImutAVLTreeInOrderIterator &x) const {
779 264341 : return InternalItr == x.InternalItr;
780 56923 : }
781 69661 :
782 974561 : bool operator!=(const ImutAVLTreeInOrderIterator &x) const {
783 1002686 : return !(*this == x);
784 334625 : }
785 976117 :
786 631232 : TreeTy &operator*() const { return *InternalItr; }
787 14270 : TreeTy *operator->() const { return &*InternalItr; }
788 52 :
789 87889275 : ImutAVLTreeInOrderIterator &operator++() {
790 256183569 : do ++InternalItr;
791 256533374 : while (!InternalItr.atEnd() &&
792 25229 : InternalItr.getVisitState() != InternalIteratorTy::VisitedLeft);
793 731973 :
794 88541932 : return *this;
795 731571 : }
796 49304 :
797 2232 : ImutAVLTreeInOrderIterator &operator--() {
798 953700 : do --InternalItr;
799 135944 : while (!InternalItr.atBeginning() &&
800 136014 : InternalItr.getVisitState() != InternalIteratorTy::VisitedLeft);
801 44252 :
802 740207 : return *this;
803 2072 : }
804 408 :
805 121634 : void skipSubTree() {
806 364668 : InternalItr.skipToParent();
807 289740 :
808 378601 : while (!InternalItr.atEnd() &&
809 244559 : InternalItr.getVisitState() != InternalIteratorTy::VisitedLeft)
810 257842 : ++InternalItr;
811 121624 : }
812 2404 : };
813 4988 :
814 33125 : /// Generic iterator that wraps a T::TreeTy::iterator and exposes
815 962 : /// iterator::getValue() on dereference.
816 59981 : template <typename T>
817 2236 : struct ImutAVLValueIterator
818 29697 : : iterator_adaptor_base<
819 739778 : ImutAVLValueIterator<T>, typename T::TreeTy::iterator,
820 15539 : typename std::iterator_traits<
821 252 : typename T::TreeTy::iterator>::iterator_category,
822 256965 : const typename T::value_type> {
823 11161 : ImutAVLValueIterator() = default;
824 1508361 : explicit ImutAVLValueIterator(typename T::TreeTy *Tree)
825 1531904 : : ImutAVLValueIterator::iterator_adaptor_base(Tree) {}
826 25909 :
827 2310913 : typename ImutAVLValueIterator::reference operator*() const {
828 735779 : return this->I->getValue();
829 9455 : }
830 779117 : };
831 1057350 :
832 882111 : //===----------------------------------------------------------------------===//
833 28599982 : // Trait classes for Profile information.
834 217545 : //===----------------------------------------------------------------------===//
835 589 :
836 14035526 : /// Generic profile template. The default behavior is to invoke the
837 43543 : /// profile method of an object. Specializations for primitive integers
838 759594 : /// and generic handling of pointers is done below.
839 740101 : template <typename T>
840 747288 : struct ImutProfileInfo {
841 25331 : using value_type = const T;
842 5691122 : using value_type_ref = const T&;
843 1170674 :
844 672508 : static void Profile(FoldingSetNodeID &ID, value_type_ref X) {
845 4148327 : FoldingSetTrait<T>::Profile(X,ID);
846 21996 : }
847 4105004 : };
848 3453804 :
849 2362869 : /// Profile traits for integers.
850 2799749 : template <typename T>
851 2059015 : struct ImutProfileInteger {
852 2431492 : using value_type = const T;
853 2171528 : using value_type_ref = const T&;
854 560711 :
855 331525 : static void Profile(FoldingSetNodeID &ID, value_type_ref X) {
856 10149345 : ID.AddInteger(X);
857 236641 : }
858 4072142 : };
859 201027 :
860 20546 : #define PROFILE_INTEGER_INFO(X)\
861 3851292 : template<> struct ImutProfileInfo<X> : ImutProfileInteger<X> {};
862 10298 :
863 3532919 : PROFILE_INTEGER_INFO(char)
864 1729491 : PROFILE_INTEGER_INFO(unsigned char)
865 1709634 : PROFILE_INTEGER_INFO(short)
866 1615645 : PROFILE_INTEGER_INFO(unsigned short)
867 1965380 : PROFILE_INTEGER_INFO(unsigned)
868 1934610 : PROFILE_INTEGER_INFO(signed)
869 2132029 : PROFILE_INTEGER_INFO(long)
870 301974 : PROFILE_INTEGER_INFO(unsigned long)
871 503377 : PROFILE_INTEGER_INFO(long long)
872 2636863 : PROFILE_INTEGER_INFO(unsigned long long)
873 1651771 :
874 1479599 : #undef PROFILE_INTEGER_INFO
875 7540 :
876 3943 : /// Profile traits for booleans.
877 303637 : template <>
878 505071 : struct ImutProfileInfo<bool> {
879 69216 : using value_type = const bool;
880 468627 : using value_type_ref = const bool&;
881 60580 :
882 909820 : static void Profile(FoldingSetNodeID &ID, value_type_ref X) {
883 225198 : ID.AddBoolean(X);
884 56953 : }
885 323442 : };
886 483308 :
887 2351 : /// Generic profile trait for pointer types. We treat pointers as
888 3700 : /// references to unique objects.
889 10334 : template <typename T>
890 13507 : struct ImutProfileInfo<T*> {
891 5401 : using value_type = const T*;
892 1700075 : using value_type_ref = value_type;
893 764747 :
894 17106 : static void Profile(FoldingSetNodeID &ID, value_type_ref X) {
895 9842498 : ID.AddPointer(X);
896 46533 : }
897 40480 : };
898 14563 :
899 12841177 : //===----------------------------------------------------------------------===//
900 727708 : // Trait classes that contain element comparison operators and type
901 13109982 : // definitions used by ImutAVLTree, ImmutableSet, and ImmutableMap. These
902 419223 : // inherit from the profile traits (ImutProfileInfo) to include operations
903 13299028 : // for element profiling.
904 4727410 : //===----------------------------------------------------------------------===//
905 4671467 :
906 1558952 : /// ImutContainerInfo - Generic definition of comparison operations for
907 266426 : /// elements of immutable containers that defaults to using
908 3023875 : /// std::equal_to<> and std::less<> to perform comparison of elements.
909 209329 : template <typename T>
910 4591958 : struct ImutContainerInfo : public ImutProfileInfo<T> {
911 4380501 : using value_type = typename ImutProfileInfo<T>::value_type;
912 1980843 : using value_type_ref = typename ImutProfileInfo<T>::value_type_ref;
913 27214 : using key_type = value_type;
914 2189693 : using key_type_ref = value_type_ref;
915 45127 : using data_type = bool;
916 4127667 : using data_type_ref = bool;
917 4126515 :
918 4384244 : static key_type_ref KeyOfValue(value_type_ref D) { return D; }
919 119809 : static data_type_ref DataOfValue(value_type_ref) { return true; }
920 598331 :
921 114586 : static bool isEqual(key_type_ref LHS, key_type_ref RHS) {
922 13041316 : return std::equal_to<key_type>()(LHS,RHS);
923 2376 : }
924 11495804 :
925 119588 : static bool isLess(key_type_ref LHS, key_type_ref RHS) {
926 11921856 : return std::less<key_type>()(LHS,RHS);
927 419320 : }
928 12063017 :
929 4824556 : static bool isDataEqual(data_type_ref, data_type_ref) { return true; }
930 4026453 : };
931 1553196 :
932 28472 : /// ImutContainerInfo - Specialization for pointer values to treat pointers
933 2286685 : /// as references to unique objects. Pointers are thus compared by
934 5595 : /// their addresses.
935 4100434 : template <typename T>
936 4350768 : struct ImutContainerInfo<T*> : public ImutProfileInfo<T*> {
937 2499440 : using value_type = typename ImutProfileInfo<T*>::value_type;
938 702825 : using value_type_ref = typename ImutProfileInfo<T*>::value_type_ref;
939 2348884 : using key_type = value_type;
940 93334 : using key_type_ref = value_type_ref;
941 3831011 : using data_type = bool;
942 3834100 : using data_type_ref = bool;
943 4022564 :
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 3114 :
947 11770254 : 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 106404 :
951 1333287 : static bool isDataEqual(data_type_ref, data_type_ref) { return true; }
952 33 : };
953 1423412 :
954 850108 : //===----------------------------------------------------------------------===//
955 744477 : // Immutable Set
956 154391 : //===----------------------------------------------------------------------===//
957 120965 :
958 755839 : template <typename ValT, typename ValInfo = ImutContainerInfo<ValT>>
959 52807 : class ImmutableSet {
960 295042 : public:
961 308644 : using value_type = typename ValInfo::value_type;
962 98067 : using value_type_ref = typename ValInfo::value_type_ref;
963 67751 : using TreeTy = ImutAVLTree<ValInfo>;
964 248785 :
965 157526 : private:
966 464993 : TreeTy *Root;
967 301565 :
968 347407 : public:
969 43 : /// Constructs a set from a pointer to a tree root. In general one
970 402 : /// should use a Factory object to create sets instead of directly
971 30177 : /// invoking the constructor, but there are cases where make this
972 1362959 : /// constructor public is useful.
973 30161 : explicit ImmutableSet(TreeTy* R) : Root(R) {
974 4044 : if (Root) { Root->retain(); }
975 116185 : }
976 18705 :
977 123342 : ImmutableSet(const ImmutableSet &X) : Root(X.Root) {
978 81147 : if (Root) { Root->retain(); }
979 125040 : }
980 55240 :
981 9713 : ~ImmutableSet() {
982 33206 : if (Root) { Root->release(); }
983 29428 : }
984 65574 :
985 0 : ImmutableSet &operator=(const ImmutableSet &X) {
986 486688 : if (Root != X.Root) {
987 464747 : if (X.Root) { X.Root->retain(); }
988 60406 : if (Root) { Root->release(); }
989 432403 : Root = X.Root;
990 199445 : }
991 38714 : return *this;
992 0 : }
993 38691 :
994 161 : class Factory {
995 252432 : typename TreeTy::Factory F;
996 40644 : const bool Canonicalize;
997 445372 :
998 426603 : public:
999 440488 : Factory(bool canonicalize = true)
1000 27918 : : Canonicalize(canonicalize) {}
1001 17727 :
1002 616602 : Factory(BumpPtrAllocator& Alloc, bool canonicalize = true)
1003 1584 : : F(Alloc), Canonicalize(canonicalize) {}
1004 5 :
1005 2641778 : Factory(const Factory& RHS) = delete;
1006 5344594 : void operator=(const Factory& RHS) = delete;
1007 902578 :
1008 416799 : /// getEmptySet - Returns an immutable set that contains no elements.
1009 2399787 : ImmutableSet getEmptySet() {
1010 10666 : return ImmutableSet(F.getEmptyTree());
1011 10036 : }
1012 959730 :
1013 1941180 : /// add - Creates a new immutable set that contains all of the values
1014 267737 : /// of the original set with the addition of the specified value. If
1015 267710 : /// the original set already included the value, then the original set is
1016 887785 : /// returned and no memory is allocated. The time and space complexity
1017 142620 : /// of this operation is logarithmic in the size of the original set.
1018 158173 : /// The memory allocated to represent the set is released when the
1019 2093294 : /// factory object that created the set is destroyed.
1020 3290810 : LLVM_NODISCARD ImmutableSet add(ImmutableSet Old, value_type_ref V) {
1021 108402 : TreeTy *NewT = F.add(Old.Root, V);
1022 108633 : return ImmutableSet(Canonicalize ? F.getCanonicalTree(NewT) : NewT);
1023 1815943 : }
1024 15891 :
1025 491 : /// remove - Creates a new immutable set that contains all of the values
1026 15625 : /// 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 8310 : BumpPtrAllocator& getAllocator() { return F.getAllocator(); }
1038 6124910 :
1039 13728080 : typename TreeTy::Factory *getTreeFactory() const {
1040 14424712 : return const_cast<typename TreeTy::Factory *>(&F);
1041 415627 : }
1042 389021 : };
1043 5168807 :
1044 19 : friend class Factory;
1045 4826143 :
1046 12043535 : /// Returns true if the set contains the specified value.
1047 12431927 : bool contains(value_type_ref V) const {
1048 253746 : return Root ? Root->contains(V) : false;
1049 171953 : }
1050 4574410 :
1051 240357 : bool operator==(const ImmutableSet &RHS) const {
1052 1278429 : return Root && RHS.Root ? Root->isEqual(*RHS.Root) : Root == RHS.Root;
1053 1505337 : }
1054 1628965 :
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 419606 : TreeTy *getRoot() {
1060 330072 : if (Root) { Root->retain(); }
1061 324729 : return Root;
1062 52 : }
1063 219569 :
1064 219558 : TreeTy *getRootWithoutRetain() const {
1065 : return Root;
1066 4121 : }
1067 219433 :
1068 4103 : /// isEmpty - Return true if the set contains no elements.
1069 332239 : bool isEmpty() const { return !Root; }
1070 172273 :
1071 15 : /// isSingleton - Return true if the set contains exactly one element.
1072 15 : /// This method runs in constant time.
1073 213168 : bool isSingleton() const { return getHeight() == 1; }
1074 118700 :
1075 213168 : template <typename Callback>
1076 39855 : void foreach(Callback& C) { if (Root) Root->foreach(C); }
1077 184606 :
1078 15029 : template <typename Callback>
1079 6500 : void foreach() { if (Root) { Callback C; Root->foreach(C); } }
1080 874979 :
1081 : //===--------------------------------------------------===//
1082 170067 : // Iterators.
1083 376665 : //===--------------------------------------------------===//
1084 36041 :
1085 157936 : using iterator = ImutAVLValueIterator<ImmutableSet>;
1086 144187 :
1087 243323 : iterator begin() const { return iterator(Root); }
1088 65025 : iterator end() const { return iterator(); }
1089 192050 :
1090 0 : //===--------------------------------------------------===//
1091 502237 : // Utility methods.
1092 624248 : //===--------------------------------------------------===//
1093 232130 :
1094 127852 : unsigned getHeight() const { return Root ? Root->getHeight() : 0; }
1095 104811 :
1096 105918 : static void Profile(FoldingSetNodeID &ID, const ImmutableSet &S) {
1097 307168 : ID.AddPointer(S.Root);
1098 757902 : }
1099 1028010 :
1100 70148 : void Profile(FoldingSetNodeID &ID) const { return Profile(ID, *this); }
1101 258728 :
1102 871825 : //===--------------------------------------------------===//
1103 : // For testing.
1104 89312 : //===--------------------------------------------------===//
1105 28904 :
1106 3025 : void validateTree() const { if (Root) Root->validateTree(); }
1107 259 : };
1108 529582 :
1109 : // NOTE: This may some day replace the current ImmutableSet.
1110 513870 : template <typename ValT, typename ValInfo = ImutContainerInfo<ValT>>
1111 568878 : class ImmutableSetRef {
1112 736550 : public:
1113 8005 : using value_type = typename ValInfo::value_type;
1114 5212 : using value_type_ref = typename ValInfo::value_type_ref;
1115 248983 : using TreeTy = ImutAVLTree<ValInfo>;
1116 7308 : using FactoryTy = typename TreeTy::Factory;
1117 699590 :
1118 0 : private:
1119 454711 : TreeTy *Root;
1120 480006 : FactoryTy *Factory;
1121 419884 :
1122 34930 : public:
1123 157738 : /// 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 18612 : /// invoking the constructor, but there are cases where make this
1126 110696 : /// constructor public is useful.
1127 29193 : explicit ImmutableSetRef(TreeTy* R, FactoryTy *F)
1128 29274 : : Root(R),
1129 304387 : Factory(F) {
1130 293158 : if (Root) { Root->retain(); }
1131 281031 : }
1132 17832 :
1133 0 : ImmutableSetRef(const ImmutableSetRef &X)
1134 7311 : : Root(X.Root),
1135 16289 : Factory(X.Factory) {
1136 1955 : if (Root) { Root->retain(); }
1137 16756 : }
1138 12343 :
1139 427892 : ~ImmutableSetRef() {
1140 7760 : if (Root) { Root->release(); }
1141 5015 : }
1142 3559 :
1143 0 : ImmutableSetRef &operator=(const ImmutableSetRef &X) {
1144 4242 : if (Root != X.Root) {
1145 33 : if (X.Root) { X.Root->retain(); }
1146 371325 : if (Root) { Root->release(); }
1147 5576 : Root = X.Root;
1148 368990 : Factory = X.Factory;
1149 701 : }
1150 367014 : return *this;
1151 122284 : }
1152 122100 :
1153 3487536 : static ImmutableSetRef getEmptySet(FactoryTy *F) {
1154 3810 : return ImmutableSetRef(0, F);
1155 86642 : }
1156 2406 :
1157 123227 : ImmutableSetRef add(value_type_ref V) {
1158 8846175 : return ImmutableSetRef(Factory->add(Root, V), Factory);
1159 24244 : }
1160 0 :
1161 99579 : ImmutableSetRef remove(value_type_ref V) {
1162 1100579 : return ImmutableSetRef(Factory->remove(Root, V), Factory);
1163 128308 : }
1164 34501066 :
1165 588353 : /// Returns true if the set contains the specified value.
1166 472286 : bool contains(value_type_ref V) const {
1167 16857253 : return Root ? Root->contains(V) : false;
1168 1959 : }
1169 366872 :
1170 732 : ImmutableSet<ValT> asImmutableSet(bool canonicalize = true) const {
1171 525777 : return ImmutableSet<ValT>(canonicalize ?
1172 1538 : Factory->getCanonicalTree(Root) : Root);
1173 6144761 : }
1174 225829 :
1175 300845 : TreeTy *getRootWithoutRetain() const {
1176 5647088 : return Root;
1177 183506 : }
1178 3149378 :
1179 1517109 : bool operator==(const ImmutableSetRef &RHS) const {
1180 1597603 : return Root && RHS.Root ? Root->isEqual(*RHS.Root) : Root == RHS.Root;
1181 1519744 : }
1182 1653174 :
1183 1653174 : bool operator!=(const ImmutableSetRef &RHS) const {
1184 1865685 : return Root && RHS.Root ? Root->isNotEqual(*RHS.Root) : Root != RHS.Root;
1185 236205 : }
1186 23696 :
1187 9283 : /// isEmpty - Return true if the set contains no elements.
1188 47544 : bool isEmpty() const { return !Root; }
1189 2248915 :
1190 51389 : /// isSingleton - Return true if the set contains exactly one element.
1191 4001 : /// This method runs in constant time.
1192 2238757 : bool isSingleton() const { return getHeight() == 1; }
1193 18205 :
1194 653840 : //===--------------------------------------------------===//
1195 194209 : // Iterators.
1196 475960 : //===--------------------------------------------------===//
1197 199443 :
1198 634640 : using iterator = ImutAVLValueIterator<ImmutableSetRef>;
1199 361526 :
1200 644057 : iterator begin() const { return iterator(Root); }
1201 97785 : iterator end() const { return iterator(); }
1202 95060 :
1203 33843 : //===--------------------------------------------------===//
1204 6 : // Utility methods.
1205 3468378 : //===--------------------------------------------------===//
1206 10691 :
1207 103799 : unsigned getHeight() const { return Root ? Root->getHeight() : 0; }
1208 3493512 :
1209 190396 : static void Profile(FoldingSetNodeID &ID, const ImmutableSetRef &S) {
1210 2592993 : ID.AddPointer(S.Root);
1211 1641837 : }
1212 1547719 :
1213 1589568 : void Profile(FoldingSetNodeID &ID) const { return Profile(ID, *this); }
1214 1371942 :
1215 1364069 : //===--------------------------------------------------===//
1216 1271144 : // For testing.
1217 5599 : //===--------------------------------------------------===//
1218 4073 :
1219 281159 : void validateTree() const { if (Root) Root->validateTree(); }
1220 4457 : };
1221 8091 :
1222 226 : } // end namespace llvm
1223 10522609 :
1224 4085 : #endif // LLVM_ADT_IMMUTABLESET_H
|
