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