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"
19#include "llvm/ADT/IntrusiveRefCntPtr.h"
20#include "llvm/ADT/SmallVector.h"
21#include "llvm/ADT/iterator.h"
22#include "llvm/Support/Allocator.h"
23#include "llvm/Support/ErrorHandling.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 >
43class ImutAVLTree {
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;
48 using Factory = ImutAVLFactory<ImutInfo>;
49 using iterator = ImutAVLTreeInOrderIterator<ImutInfo>;
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.
76 ImutAVLTree* find(key_type_ref K) {
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.
92 ImutAVLTree* getMaxElement() {
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
119 bool isElementEqual(value_type_ref V) const {
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
220 value_type value;
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.
231 ImutAVLTree(Factory *f, ImutAVLTree* l, ImutAVLTree* r, value_type_ref v,
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>
349struct IntrusiveRefCntPtrInfo<ImutAVLTree<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 >
359class ImutAVLFactory {
360 friend class ImutAVLTree<ImutInfo>;
361
362 using TreeTy = ImutAVLTree<ImutInfo>;
363 using value_type_ref = typename TreeTy::value_type_ref;
364 using key_type_ref = typename TreeTy::key_type_ref;
365 using CacheTy = DenseMap<unsigned, TreeTy*>;
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:
385 ImutAVLFactory()
386 : Allocator(reinterpret_cast<uintptr_t>(new BumpPtrAllocator())) {}
387
388 ImutAVLFactory(BumpPtrAllocator& Alloc)
389 : Allocator(reinterpret_cast<uintptr_t>(&Alloc) | 0x1) {}
390
391 ~ImutAVLFactory() {
392 if (ownsAllocator()) delete &getAllocator();
393 }
394
395 TreeTy* add(TreeTy* T, value_type_ref V) {
396 T = add_internal(V,T);
397 markImmutable(T);
398 recoverNodes();
399 return T;
400 }
401
402 TreeTy* remove(TreeTy* T, key_type_ref V) {
403 T = remove_internal(K: V,T);
404 markImmutable(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(T: L);
430 unsigned hr = getHeight(T: R);
431 return (hl > hr ? hl : hr) + 1;
432 }
433
434 static bool compareTreeWithSection(TreeTy* T,
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(T: oldTree), newRight);
473 }
474
475 void recoverNodes() {
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(T: L);
488 unsigned hr = getHeight(T: 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(T: L);
494 TreeTy *LR = getRight(T: L);
495
496 if (getHeight(T: LL) >= getHeight(T: 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(T: LR);
502 TreeTy *LRR = getRight(T: 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(T: R);
511 TreeTy *RR = getRight(T: R);
512
513 if (getHeight(T: RR) >= getHeight(T: 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(T: RL);
519 TreeTy *RLR = getRight(T: 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))
541 return balanceTree(L: add_internal(V, T: getLeft(T)), V: getValue(T), R: getRight(T));
542 else
543 return balanceTree(L: getLeft(T), V: getValue(T), R: add_internal(V, T: getRight(T)));
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(L: getLeft(T), R: getRight(T));
560 } else if (ImutInfo::isLess(K,KCurrent)) {
561 return balanceTree(L: remove_internal(K, T: getLeft(T)),
562 V: getValue(T), R: getRight(T));
563 } else {
564 return balanceTree(L: getLeft(T), V: getValue(T),
565 R: remove_internal(K, T: getRight(T)));
566 }
567 }
568
569 TreeTy* combineTrees(TreeTy* L, TreeTy* R) {
570 if (isEmpty(T: L))
571 return R;
572 if (isEmpty(T: R))
573 return L;
574 TreeTy* OldNode;
575 TreeTy* newRight = removeMinBinding(T: R,Noderemoved&: OldNode);
576 return balanceTree(L, V: getValue(T: OldNode), R: newRight);
577 }
578
579 TreeTy* removeMinBinding(TreeTy* T, TreeTy*& Noderemoved) {
580 assert(!isEmpty(T));
581 if (isEmpty(T: getLeft(T))) {
582 Noderemoved = T;
583 return getRight(T);
584 }
585 return balanceTree(L: removeMinBinding(T: getLeft(T), Noderemoved),
586 V: getValue(T), R: getRight(T));
587 }
588
589 /// markImmutable - Clears the mutable bits of a root and all of its
590 /// descendants.
591 void markImmutable(TreeTy* T) {
592 if (!T || !T->isMutable())
593 return;
594 T->markImmutable();
595 markImmutable(T: getLeft(T));
596 markImmutable(T: getRight(T));
597 }
598
599public:
600 TreeTy *getCanonicalTree(TreeTy *TNew) {
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(I: 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(T: 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 {
642 SmallVector<uintptr_t,20> stack;
643
644public:
645 using iterator_category = std::bidirectional_iterator_tag;
646 using value_type = ImutAVLTree<ImutInfo>;
647 using difference_type = std::ptrdiff_t;
648 using pointer = value_type *;
649 using reference = value_type &;
650
651 enum VisitFlag { VisitedNone=0x0, VisitedLeft=0x1, VisitedRight=0x3,
652 Flags=0x3 };
653
654 using TreeTy = ImutAVLTree<ImutInfo>;
655
656 ImutAVLTreeGenericIterator() = default;
657 ImutAVLTreeGenericIterator(const TreeTy *Root) {
658 if (Root) stack.push_back(Elt: 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
678 void skipToParent() {
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
695 bool operator==(const ImutAVLTreeGenericIterator &x) const {
696 return stack == x.stack;
697 }
698
699 bool operator!=(const ImutAVLTreeGenericIterator &x) const {
700 return !(*this == x);
701 }
702
703 ImutAVLTreeGenericIterator &operator++() {
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(Elt: 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(Elt: 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
729 ImutAVLTreeGenericIterator &operator--() {
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(Elt: 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(Elt: 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;
762 using value_type = ImutAVLTree<ImutInfo>;
763 using difference_type = std::ptrdiff_t;
764 using pointer = value_type *;
765 using reference = value_type &;
766
767 using TreeTy = ImutAVLTree<ImutInfo>;
768
769 ImutAVLTreeInOrderIterator(const TreeTy* Root) : InternalItr(Root) {
770 if (Root)
771 ++*this; // Advance to first element.
772 }
773
774 ImutAVLTreeInOrderIterator() : InternalItr() {}
775
776 bool operator==(const ImutAVLTreeInOrderIterator &x) const {
777 return InternalItr == x.InternalItr;
778 }
779
780 bool operator!=(const ImutAVLTreeInOrderIterator &x) const {
781 return !(*this == x);
782 }
783
784 TreeTy &operator*() const { return *InternalItr; }
785 TreeTy *operator->() const { return &*InternalItr; }
786
787 ImutAVLTreeInOrderIterator &operator++() {
788 do ++InternalItr;
789 while (!InternalItr.atEnd() &&
790 InternalItr.getVisitState() != InternalIteratorTy::VisitedLeft);
791
792 return *this;
793 }
794
795 ImutAVLTreeInOrderIterator &operator--() {
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>
815struct ImutAVLValueIterator
816 : iterator_adaptor_base<
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> {
821 ImutAVLValueIterator() = default;
822 explicit ImutAVLValueIterator(typename T::TreeTy *Tree)
823 : ImutAVLValueIterator::iterator_adaptor_base(Tree) {}
824
825 typename ImutAVLValueIterator::reference operator*() const {
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>
838struct ImutProfileInfo {
839 using value_type = const T;
840 using value_type_ref = const T&;
841
842 static void Profile(FoldingSetNodeID &ID, value_type_ref X) {
843 FoldingSetTrait<T>::Profile(X,ID);
844 }
845};
846
847/// Profile traits for integers.
848template <typename T>
849struct ImutProfileInteger {
850 using value_type = const T;
851 using value_type_ref = const T&;
852
853 static void Profile(FoldingSetNodeID &ID, value_type_ref X) {
854 ID.AddInteger(X);
855 }
856};
857
858#define PROFILE_INTEGER_INFO(X)\
859template<> struct ImutProfileInfo<X> : ImutProfileInteger<X> {};
860
861PROFILE_INTEGER_INFO(char)
862PROFILE_INTEGER_INFO(unsigned char)
863PROFILE_INTEGER_INFO(short)
864PROFILE_INTEGER_INFO(unsigned short)
865PROFILE_INTEGER_INFO(unsigned)
866PROFILE_INTEGER_INFO(signed)
867PROFILE_INTEGER_INFO(long)
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 <>
876struct ImutProfileInfo<bool> {
877 using value_type = const bool;
878 using value_type_ref = const bool&;
879
880 static void Profile(FoldingSetNodeID &ID, value_type_ref X) {
881 ID.AddBoolean(B: X);
882 }
883};
884
885/// Generic profile trait for pointer types. We treat pointers as
886/// references to unique objects.
887template <typename T>
888struct ImutProfileInfo<T*> {
889 using value_type = const T*;
890 using value_type_ref = value_type;
891
892 static void Profile(FoldingSetNodeID &ID, value_type_ref X) {
893 ID.AddPointer(Ptr: 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>
908struct ImutContainerInfo : public ImutProfileInfo<T> {
909 using value_type = typename ImutProfileInfo<T>::value_type;
910 using value_type_ref = typename ImutProfileInfo<T>::value_type_ref;
911 using key_type = value_type;
912 using key_type_ref = value_type_ref;
913 using data_type = bool;
914 using data_type_ref = bool;
915
916 static key_type_ref KeyOfValue(value_type_ref D) { return D; }
917 static data_type_ref DataOfValue(value_type_ref) { return true; }
918
919 static bool isEqual(key_type_ref LHS, key_type_ref RHS) {
920 return std::equal_to<key_type>()(LHS,RHS);
921 }
922
923 static bool isLess(key_type_ref LHS, key_type_ref RHS) {
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>
934struct ImutContainerInfo<T*> : public ImutProfileInfo<T*> {
935 using value_type = typename ImutProfileInfo<T*>::value_type;
936 using value_type_ref = typename ImutProfileInfo<T*>::value_type_ref;
937 using key_type = value_type;
938 using key_type_ref = value_type_ref;
939 using data_type = bool;
940 using data_type_ref = bool;
941
942 static key_type_ref KeyOfValue(value_type_ref D) { return D; }
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>>
957class ImmutableSet {
958public:
959 using value_type = typename ValInfo::value_type;
960 using value_type_ref = typename ValInfo::value_type_ref;
961 using TreeTy = ImutAVLTree<ValInfo>;
962
963private:
964 IntrusiveRefCntPtr<TreeTy> Root;
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.
988 ImmutableSet getEmptySet() {
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.
999 [[nodiscard]] ImmutableSet add(ImmutableSet Old, value_type_ref V) {
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.
1011 [[nodiscard]] ImmutableSet remove(ImmutableSet Old, value_type_ref V) {
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
1018 typename TreeTy::Factory *getTreeFactory() const {
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
1039 TreeTy *getRoot() {
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
1057 using iterator = ImutAVLValueIterator<ImmutableSet>;
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(Ptr: 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>>
1083class ImmutableSetRef {
1084public:
1085 using value_type = typename ValInfo::value_type;
1086 using value_type_ref = typename ValInfo::value_type_ref;
1087 using TreeTy = ImutAVLTree<ValInfo>;
1088 using FactoryTy = typename TreeTy::Factory;
1089
1090private:
1091 IntrusiveRefCntPtr<TreeTy> Root;
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
1101 static ImmutableSetRef getEmptySet(FactoryTy *F) {
1102 return ImmutableSetRef(0, F);
1103 }
1104
1105 ImmutableSetRef add(value_type_ref V) {
1106 return ImmutableSetRef(Factory->add(Root.get(), V), Factory);
1107 }
1108
1109 ImmutableSetRef remove(value_type_ref V) {
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
1145 using iterator = ImutAVLValueIterator<ImmutableSetRef>;
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(Ptr: 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
1172

source code of llvm/include/llvm/ADT/ImmutableSet.h