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