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 >
44class ImutAVLTree {
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.
77 ImutAVLTree* find(key_type_ref K) {
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.
93 ImutAVLTree* getMaxElement() {
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
224 value_type value;
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
366 using TreeTy = ImutAVLTree<ImutInfo>;
367 using value_type_ref = typename TreeTy::value_type_ref;
368 using key_type_ref = typename TreeTy::key_type_ref;
369 using CacheTy = DenseMap<unsigned, TreeTy*>;
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
438 static bool compareTreeWithSection(TreeTy* T,
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 // If both key and value are same, return the original tree.
544 if (ImutInfo::isDataEqual(ImutInfo::DataOfValue(V),
545 ImutInfo::DataOfValue(getValue(T))))
546 return T;
547 // Otherwise create a new node with the new value.
548 return createNode(getLeft(T), V, getRight(T));
549 }
550
551 TreeTy *NewL = getLeft(T);
552 TreeTy *NewR = getRight(T);
553 if (ImutInfo::isLess(K, KCurrent))
554 NewL = add_internal(V, NewL);
555 else
556 NewR = add_internal(V, NewR);
557
558 // If no changes were made, return the original tree. Otherwise, balance the
559 // tree and return the new root.
560 return NewL == getLeft(T) && NewR == getRight(T)
561 ? T
562 : balanceTree(NewL, getValue(T), NewR);
563 }
564
565 /// remove_internal - Creates a new tree that includes all the data
566 /// from the original tree except the specified data. If the
567 /// specified data did not exist in the original tree, the original
568 /// tree is returned.
569 TreeTy *remove_internal(key_type_ref K, TreeTy *T) {
570 if (isEmpty(T))
571 return T;
572
573 assert(!T->isMutable());
574
575 key_type_ref KCurrent = ImutInfo::KeyOfValue(getValue(T));
576
577 if (ImutInfo::isEqual(K, KCurrent))
578 return combineTrees(getLeft(T), getRight(T));
579
580 TreeTy *NewL = getLeft(T);
581 TreeTy *NewR = getRight(T);
582 if (ImutInfo::isLess(K, KCurrent))
583 NewL = remove_internal(K, NewL);
584 else
585 NewR = remove_internal(K, NewR);
586
587 // If no changes were made, return the original tree. Otherwise, balance the
588 // tree and return the new root.
589 return NewL == getLeft(T) && NewR == getRight(T)
590 ? T
591 : balanceTree(NewL, getValue(T), NewR);
592 }
593
594 TreeTy* combineTrees(TreeTy* L, TreeTy* R) {
595 if (isEmpty(L))
596 return R;
597 if (isEmpty(R))
598 return L;
599 TreeTy* OldNode;
600 TreeTy* newRight = removeMinBinding(R,OldNode);
601 return balanceTree(L, getValue(OldNode), newRight);
602 }
603
604 TreeTy* removeMinBinding(TreeTy* T, TreeTy*& Noderemoved) {
605 assert(!isEmpty(T));
606 if (isEmpty(getLeft(T))) {
607 Noderemoved = T;
608 return getRight(T);
609 }
610 return balanceTree(removeMinBinding(getLeft(T), Noderemoved),
611 getValue(T), getRight(T));
612 }
613
614 /// markImmutable - Clears the mutable bits of a root and all of its
615 /// descendants.
616 void markImmutable(TreeTy* T) {
617 if (!T || !T->isMutable())
618 return;
619 T->markImmutable();
622 }
623
624public:
625 TreeTy *getCanonicalTree(TreeTy *TNew) {
626 if (!TNew)
627 return nullptr;
628
629 if (TNew->IsCanonicalized)
630 return TNew;
631
632 // Search the hashtable for another tree with the same digest, and
633 // if find a collision compare those trees by their contents.
634 unsigned digest = TNew->computeDigest();
635 TreeTy *&entry = Cache[maskCacheIndex(digest)];
636 do {
637 if (!entry)
638 break;
639 for (TreeTy *T = entry ; T != nullptr; T = T->next) {
640 // Compare the Contents('T') with Contents('TNew')
641 typename TreeTy::iterator TI = T->begin(), TE = T->end();
642 if (!compareTreeWithSection(TNew, TI, TE))
643 continue;
644 if (TI != TE)
645 continue; // T has more contents than TNew.
646 // Trees did match! Return 'T'.
647 if (TNew->refCount == 0)
648 TNew->destroy();
649 return T;
650 }
651 entry->prev = TNew;
652 TNew->next = entry;
653 }
654 while (false);
655
656 entry = TNew;
657 TNew->IsCanonicalized = true;
658 return TNew;
659 }
660};
661
662//===----------------------------------------------------------------------===//
663// Immutable AVL-Tree Iterators.
664//===----------------------------------------------------------------------===//
665
666template <typename ImutInfo> class ImutAVLTreeGenericIterator {
668
669public:
670 using iterator_category = std::bidirectional_iterator_tag;
672 using difference_type = std::ptrdiff_t;
675
677 Flags=0x3 };
678
680
683 if (Root) stack.push_back(reinterpret_cast<uintptr_t>(Root));
684 }
685
686 TreeTy &operator*() const {
687 assert(!stack.empty());
688 return *reinterpret_cast<TreeTy *>(stack.back() & ~Flags);
689 }
690 TreeTy *operator->() const { return &*this; }
691
692 uintptr_t getVisitState() const {
693 assert(!stack.empty());
694 return stack.back() & Flags;
695 }
696
697 bool atEnd() const { return stack.empty(); }
698
699 bool atBeginning() const {
700 return stack.size() == 1 && getVisitState() == VisitedNone;
701 }
702
704 assert(!stack.empty());
705 stack.pop_back();
706 if (stack.empty())
707 return;
708 switch (getVisitState()) {
709 case VisitedNone:
710 stack.back() |= VisitedLeft;
711 break;
712 case VisitedLeft:
713 stack.back() |= VisitedRight;
714 break;
715 default:
716 llvm_unreachable("Unreachable.");
717 }
718 }
719
721 return stack == x.stack;
722 }
723
725 return !(*this == x);
726 }
727
729 assert(!stack.empty());
730 TreeTy* Current = reinterpret_cast<TreeTy*>(stack.back() & ~Flags);
731 assert(Current);
732 switch (getVisitState()) {
733 case VisitedNone:
734 if (TreeTy* L = Current->getLeft())
735 stack.push_back(reinterpret_cast<uintptr_t>(L));
736 else
737 stack.back() |= VisitedLeft;
738 break;
739 case VisitedLeft:
740 if (TreeTy* R = Current->getRight())
741 stack.push_back(reinterpret_cast<uintptr_t>(R));
742 else
743 stack.back() |= VisitedRight;
744 break;
745 case VisitedRight:
746 skipToParent();
747 break;
748 default:
749 llvm_unreachable("Unreachable.");
750 }
751 return *this;
752 }
753
755 assert(!stack.empty());
756 TreeTy* Current = reinterpret_cast<TreeTy*>(stack.back() & ~Flags);
757 assert(Current);
758 switch (getVisitState()) {
759 case VisitedNone:
760 stack.pop_back();
761 break;
762 case VisitedLeft:
763 stack.back() &= ~Flags; // Set state to "VisitedNone."
764 if (TreeTy* L = Current->getLeft())
765 stack.push_back(reinterpret_cast<uintptr_t>(L) | VisitedRight);
766 break;
767 case VisitedRight:
768 stack.back() &= ~Flags;
769 stack.back() |= VisitedLeft;
770 if (TreeTy* R = Current->getRight())
771 stack.push_back(reinterpret_cast<uintptr_t>(R) | VisitedRight);
772 break;
773 default:
774 llvm_unreachable("Unreachable.");
775 }
776 return *this;
777 }
778};
779
780template <typename ImutInfo> class ImutAVLTreeInOrderIterator {
781 using InternalIteratorTy = ImutAVLTreeGenericIterator<ImutInfo>;
782
783 InternalIteratorTy InternalItr;
784
785public:
786 using iterator_category = std::bidirectional_iterator_tag;
788 using difference_type = std::ptrdiff_t;
791
793
794 ImutAVLTreeInOrderIterator(const TreeTy* Root) : InternalItr(Root) {
795 if (Root)
796 ++*this; // Advance to first element.
797 }
798
799 ImutAVLTreeInOrderIterator() : InternalItr() {}
800
802 return InternalItr == x.InternalItr;
803 }
804
806 return !(*this == x);
807 }
808
809 TreeTy &operator*() const { return *InternalItr; }
810 TreeTy *operator->() const { return &*InternalItr; }
811
813 do ++InternalItr;
814 while (!InternalItr.atEnd() &&
815 InternalItr.getVisitState() != InternalIteratorTy::VisitedLeft);
816
817 return *this;
818 }
819
821 do --InternalItr;
822 while (!InternalItr.atBeginning() &&
823 InternalItr.getVisitState() != InternalIteratorTy::VisitedLeft);
824
825 return *this;
826 }
827
828 void skipSubTree() {
829 InternalItr.skipToParent();
830
831 while (!InternalItr.atEnd() &&
832 InternalItr.getVisitState() != InternalIteratorTy::VisitedLeft)
833 ++InternalItr;
834 }
835};
836
837/// Generic iterator that wraps a T::TreeTy::iterator and exposes
838/// iterator::getValue() on dereference.
839template <typename T>
842 ImutAVLValueIterator<T>, typename T::TreeTy::iterator,
843 typename std::iterator_traits<
844 typename T::TreeTy::iterator>::iterator_category,
845 const typename T::value_type> {
847 explicit ImutAVLValueIterator(typename T::TreeTy *Tree)
849
851 return this->I->getValue();
852 }
853};
854
855//===----------------------------------------------------------------------===//
856// Trait classes for Profile information.
857//===----------------------------------------------------------------------===//
858
859/// Generic profile template. The default behavior is to invoke the
860/// profile method of an object. Specializations for primitive integers
861/// and generic handling of pointers is done below.
862template <typename T>
864 using value_type = const T;
865 using value_type_ref = const T&;
866
870};
871
872/// Profile traits for integers.
873template <typename T>
875 using value_type = const T;
876 using value_type_ref = const T&;
877
879 ID.AddInteger(X);
880 }
881};
882
883#define PROFILE_INTEGER_INFO(X)\
884template<> struct ImutProfileInfo<X> : ImutProfileInteger<X> {};
885
887PROFILE_INTEGER_INFO(unsigned char)
889PROFILE_INTEGER_INFO(unsigned short)
890PROFILE_INTEGER_INFO(unsigned)
893PROFILE_INTEGER_INFO(unsigned long)
894PROFILE_INTEGER_INFO(long long)
895PROFILE_INTEGER_INFO(unsigned long long)
896
897#undef PROFILE_INTEGER_INFO
898
899/// Profile traits for booleans.
900template <>
902 using value_type = const bool;
903 using value_type_ref = const bool&;
904
906 ID.AddBoolean(X);
907 }
908};
909
910/// Generic profile trait for pointer types. We treat pointers as
911/// references to unique objects.
912template <typename T>
914 using value_type = const T*;
916
918 ID.AddPointer(X);
919 }
920};
921
922//===----------------------------------------------------------------------===//
923// Trait classes that contain element comparison operators and type
924// definitions used by ImutAVLTree, ImmutableSet, and ImmutableMap. These
925// inherit from the profile traits (ImutProfileInfo) to include operations
926// for element profiling.
927//===----------------------------------------------------------------------===//
928
929/// ImutContainerInfo - Generic definition of comparison operations for
930/// elements of immutable containers that defaults to using
931/// std::equal_to<> and std::less<> to perform comparison of elements.
932template <typename T>
940
942 static data_type_ref DataOfValue(value_type_ref) { return true; }
943
945 return std::equal_to<key_type>()(LHS,RHS);
946 }
947
949 return std::less<key_type>()(LHS,RHS);
950 }
951
952 static bool isDataEqual(data_type_ref, data_type_ref) { return true; }
953};
954
955/// ImutContainerInfo - Specialization for pointer values to treat pointers
956/// as references to unique objects. Pointers are thus compared by
957/// their addresses.
958template <typename T>
976
977//===----------------------------------------------------------------------===//
978// Immutable Set
979//===----------------------------------------------------------------------===//
980
981template <typename ValT, typename ValInfo = ImutContainerInfo<ValT>>
983public:
984 using value_type = typename ValInfo::value_type;
985 using value_type_ref = typename ValInfo::value_type_ref;
987
988private:
990
991public:
992 /// Constructs a set from a pointer to a tree root. In general one
993 /// should use a Factory object to create sets instead of directly
994 /// invoking the constructor, but there are cases where make this
995 /// constructor public is useful.
996 explicit ImmutableSet(TreeTy *R) : Root(R) {}
997
998 class Factory {
999 typename TreeTy::Factory F;
1000 const bool Canonicalize;
1001
1002 public:
1003 Factory(bool canonicalize = true)
1004 : Canonicalize(canonicalize) {}
1005
1006 Factory(BumpPtrAllocator& Alloc, bool canonicalize = true)
1007 : F(Alloc), Canonicalize(canonicalize) {}
1008
1009 Factory(const Factory& RHS) = delete;
1010 void operator=(const Factory& RHS) = delete;
1011
1012 /// getEmptySet - Returns an immutable set that contains no elements.
1014 return ImmutableSet(F.getEmptyTree());
1015 }
1016
1017 /// add - Creates a new immutable set that contains all of the values
1018 /// of the original set with the addition of the specified value. If
1019 /// the original set already included the value, then the original set is
1020 /// returned and no memory is allocated. The time and space complexity
1021 /// of this operation is logarithmic in the size of the original set.
1022 /// The memory allocated to represent the set is released when the
1023 /// factory object that created the set is destroyed.
1025 TreeTy *NewT = F.add(Old.Root.get(), V);
1026 return ImmutableSet(Canonicalize ? F.getCanonicalTree(NewT) : NewT);
1027 }
1028
1029 /// remove - Creates a new immutable set that contains all of the values
1030 /// of the original set with the exception of the specified value. If
1031 /// the original set did not contain the value, the original set is
1032 /// returned and no memory is allocated. The time and space complexity
1033 /// of this operation is logarithmic in the size of the original set.
1034 /// The memory allocated to represent the set is released when the
1035 /// factory object that created the set is destroyed.
1037 TreeTy *NewT = F.remove(Old.Root.get(), V);
1038 return ImmutableSet(Canonicalize ? F.getCanonicalTree(NewT) : NewT);
1039 }
1040
1041 BumpPtrAllocator& getAllocator() { return F.getAllocator(); }
1042
1044 return const_cast<typename TreeTy::Factory *>(&F);
1045 }
1046 };
1047
1048 friend class Factory;
1049
1050 /// Returns true if the set contains the specified value.
1051 bool contains(value_type_ref V) const {
1052 return Root ? Root->contains(V) : false;
1053 }
1054
1055 bool operator==(const ImmutableSet &RHS) const {
1056 return Root && RHS.Root ? Root->isEqual(*RHS.Root.get()) : Root == RHS.Root;
1057 }
1058
1059 bool operator!=(const ImmutableSet &RHS) const {
1060 return Root && RHS.Root ? Root->isNotEqual(*RHS.Root.get())
1061 : Root != RHS.Root;
1062 }
1063
1065 if (Root) { Root->retain(); }
1066 return Root.get();
1067 }
1068
1069 TreeTy *getRootWithoutRetain() const { return Root.get(); }
1070
1071 /// isEmpty - Return true if the set contains no elements.
1072 bool isEmpty() const { return !Root; }
1073
1074 /// isSingleton - Return true if the set contains exactly one element.
1075 /// This method runs in constant time.
1076 bool isSingleton() const { return getHeight() == 1; }
1077
1078 //===--------------------------------------------------===//
1079 // Iterators.
1080 //===--------------------------------------------------===//
1081
1083
1084 iterator begin() const { return iterator(Root.get()); }
1085 iterator end() const { return iterator(); }
1086
1087 //===--------------------------------------------------===//
1088 // Utility methods.
1089 //===--------------------------------------------------===//
1090
1091 unsigned getHeight() const { return Root ? Root->getHeight() : 0; }
1092
1093 static void Profile(FoldingSetNodeID &ID, const ImmutableSet &S) {
1094 ID.AddPointer(S.Root.get());
1095 }
1096
1097 void Profile(FoldingSetNodeID &ID) const { return Profile(ID, *this); }
1098
1099 //===--------------------------------------------------===//
1100 // For testing.
1101 //===--------------------------------------------------===//
1102
1103 void validateTree() const { if (Root) Root->validateTree(); }
1104};
1105
1106// NOTE: This may some day replace the current ImmutableSet.
1107template <typename ValT, typename ValInfo = ImutContainerInfo<ValT>>
1109public:
1110 using value_type = typename ValInfo::value_type;
1111 using value_type_ref = typename ValInfo::value_type_ref;
1113 using FactoryTy = typename TreeTy::Factory;
1114
1115private:
1117 FactoryTy *Factory;
1118
1119public:
1120 /// Constructs a set from a pointer to a tree root. In general one
1121 /// should use a Factory object to create sets instead of directly
1122 /// invoking the constructor, but there are cases where make this
1123 /// constructor public is useful.
1124 ImmutableSetRef(TreeTy *R, FactoryTy *F) : Root(R), Factory(F) {}
1125
1127 return ImmutableSetRef(0, F);
1128 }
1129
1131 return ImmutableSetRef(Factory->add(Root.get(), V), Factory);
1132 }
1133
1135 return ImmutableSetRef(Factory->remove(Root.get(), V), Factory);
1136 }
1137
1138 /// Returns true if the set contains the specified value.
1139 bool contains(value_type_ref V) const {
1140 return Root ? Root->contains(V) : false;
1141 }
1142
1143 ImmutableSet<ValT> asImmutableSet(bool canonicalize = true) const {
1144 return ImmutableSet<ValT>(
1145 canonicalize ? Factory->getCanonicalTree(Root.get()) : Root.get());
1146 }
1147
1148 TreeTy *getRootWithoutRetain() const { return Root.get(); }
1149
1150 bool operator==(const ImmutableSetRef &RHS) const {
1151 return Root && RHS.Root ? Root->isEqual(*RHS.Root.get()) : Root == RHS.Root;
1152 }
1153
1154 bool operator!=(const ImmutableSetRef &RHS) const {
1155 return Root && RHS.Root ? Root->isNotEqual(*RHS.Root.get())
1156 : Root != RHS.Root;
1157 }
1158
1159 /// isEmpty - Return true if the set contains no elements.
1160 bool isEmpty() const { return !Root; }
1161
1162 /// isSingleton - Return true if the set contains exactly one element.
1163 /// This method runs in constant time.
1164 bool isSingleton() const { return getHeight() == 1; }
1165
1166 //===--------------------------------------------------===//
1167 // Iterators.
1168 //===--------------------------------------------------===//
1169
1171
1172 iterator begin() const { return iterator(Root.get()); }
1173 iterator end() const { return iterator(); }
1174
1175 //===--------------------------------------------------===//
1176 // Utility methods.
1177 //===--------------------------------------------------===//
1178
1179 unsigned getHeight() const { return Root ? Root->getHeight() : 0; }
1180
1181 static void Profile(FoldingSetNodeID &ID, const ImmutableSetRef &S) {
1182 ID.AddPointer(S.Root.get());
1183 }
1184
1185 void Profile(FoldingSetNodeID &ID) const { return Profile(ID, *this); }
1186
1187 //===--------------------------------------------------===//
1188 // For testing.
1189 //===--------------------------------------------------===//
1190
1191 void validateTree() const { if (Root) Root->validateTree(); }
1192};
1193
1194} // end namespace llvm
1195
1196#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
This file defines the DenseMap class.
This file defines a hash set that can be used to remove duplication of nodes in a graph.
#define PROFILE_INTEGER_INFO(X)
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
if(PassOpts->AAPipeline)
This file defines the SmallVector class.
static TableGen::Emitter::OptClass< SkeletonEmitter > X("gen-skeleton-class", "Generate example skeleton class")
Value * RHS
Value * LHS
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)
ImutAVLTree< ValInfo > TreeTy
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)
ImmutableSet getEmptySet()
getEmptySet - Returns an immutable set that contains no elements.
Factory(bool canonicalize=true)
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
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.
bool isSingleton() const
isSingleton - Return true if the set contains exactly one element.
TreeTy * getRootWithoutRetain() const
ImutAVLTree< ValInfo > TreeTy
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
static unsigned maskCacheIndex(unsigned I)
TreeTy * balanceTree(TreeTy *L, value_type_ref V, TreeTy *R)
balanceTree - Used by add_internal and remove_internal to balance a newly created tree.
unsigned getHeight(TreeTy *T) const
ImutAVLFactory(BumpPtrAllocator &Alloc)
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...
value_type_ref getValue(TreeTy *T) const
static bool compareTreeWithSection(TreeTy *T, typename TreeTy::iterator &TI, typename TreeTy::iterator &TE)
TreeTy * getLeft(TreeTy *T) const
TreeTy * getCanonicalTree(TreeTy *TNew)
TreeTy * add(TreeTy *T, value_type_ref V)
TreeTy * getRight(TreeTy *T) const
TreeTy * getEmptyTree() const
TreeTy * removeMinBinding(TreeTy *T, TreeTy *&Noderemoved)
TreeTy * createNode(TreeTy *newLeft, TreeTy *oldTree, TreeTy *newRight)
TreeTy * combineTrees(TreeTy *L, TreeTy *R)
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...
TreeTy * createNode(TreeTy *L, value_type_ref V, TreeTy *R)
unsigned incrementHeight(TreeTy *L, TreeTy *R) const
TreeTy * remove(TreeTy *T, key_type_ref V)
void markImmutable(TreeTy *T)
markImmutable - Clears the mutable bits of a root and all of its descendants.
bool isEmpty(TreeTy *T) const
ImutAVLTree< ImutInfo > value_type
bool operator==(const ImutAVLTreeGenericIterator &x) const
std::bidirectional_iterator_tag iterator_category
ImutAVLTreeGenericIterator(const TreeTy *Root)
ImutAVLTree< ImutInfo > TreeTy
ImutAVLTreeGenericIterator & operator--()
bool operator!=(const ImutAVLTreeGenericIterator &x) const
ImutAVLTreeGenericIterator & operator++()
bool operator!=(const ImutAVLTreeInOrderIterator &x) const
ImutAVLTreeInOrderIterator & operator++()
ImutAVLTree< ImutInfo > TreeTy
ImutAVLTreeInOrderIterator & operator--()
std::bidirectional_iterator_tag iterator_category
ImutAVLTreeInOrderIterator(const TreeTy *Root)
bool operator==(const ImutAVLTreeInOrderIterator &x) const
ImutAVLTree< ImutInfo > value_type
unsigned size() const
size - Returns the number of nodes in the tree, which includes both leaves and non-leaf nodes.
iterator end() const
end - Returns an iterator for the tree that denotes the end of an inorder traversal.
const value_type & getValue() const
getValue - Returns the data value associated with the tree node.
unsigned getHeight() const
getHeight - Returns the height of the tree.
typename ValInfo::key_type_ref key_type_ref
ImutAVLFactory< ValInfo > Factory
ImutAVLTree * find(key_type_ref K)
find - Finds the subtree associated with the specified key value.
typename ValInfo::value_type_ref value_type_ref
unsigned validateTree() const
validateTree - A utility method that checks that the balancing and ordering invariants of the tree ar...
bool isNotEqual(const ImutAVLTree &RHS) const
isNotEqual - Compares two trees for structural inequality.
bool isEqual(const ImutAVLTree &RHS) const
isEqual - Compares two trees for structural equality and returns true if they are equal.
ImutAVLTree * getLeft() const
Return a pointer to the left subtree.
ImutAVLTreeInOrderIterator< ValInfo > iterator
typename ValInfo::value_type value_type
ImutAVLTree * getRight() const
Return a pointer to the right subtree.
bool isElementEqual(const ImutAVLTree *RHS) const
bool contains(key_type_ref K)
contains - Returns true if this tree contains a subtree (node) that has an data element that matches ...
ImutAVLTree * getMaxElement()
getMaxElement - Find the subtree associated with the highest ranged key value.
iterator begin() const
begin - Returns an iterator that iterates over the nodes of the tree in an inorder traversal.
bool isElementEqual(value_type_ref V) const
A smart pointer to a reference-counted object that inherits from RefCountedBase or ThreadSafeRefCount...
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
#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.
BumpPtrAllocatorImpl BumpPtrAllocator
The standard BumpPtrAllocator which just uses the default template parameters.
Definition Allocator.h:383
#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.
ImutAVLValueIterator::reference operator*() const
ImutAVLValueIterator(typename T::TreeTy *Tree)
static bool isDataEqual(data_type_ref, data_type_ref)
static key_type_ref KeyOfValue(value_type_ref D)
static bool isEqual(key_type_ref LHS, key_type_ref RHS)
typename ImutProfileInfo< T * >::value_type_ref value_type_ref
typename ImutProfileInfo< T * >::value_type value_type
static data_type_ref DataOfValue(value_type_ref)
static bool isLess(key_type_ref LHS, key_type_ref RHS)
ImutContainerInfo - Generic definition of comparison operations for elements of immutable containers ...
static bool isLess(key_type_ref LHS, key_type_ref RHS)
typename ImutProfileInfo< T >::value_type value_type
static bool isEqual(key_type_ref LHS, key_type_ref RHS)
static bool isDataEqual(data_type_ref, data_type_ref)
static data_type_ref DataOfValue(value_type_ref)
static key_type_ref KeyOfValue(value_type_ref D)
value_type_ref key_type_ref
typename ImutProfileInfo< T >::value_type_ref value_type_ref
static void Profile(FoldingSetNodeID &ID, value_type_ref X)
static void Profile(FoldingSetNodeID &ID, value_type_ref X)
Generic profile template.
static void Profile(FoldingSetNodeID &ID, value_type_ref X)
Profile traits for integers.
static void Profile(FoldingSetNodeID &ID, value_type_ref X)
static void retain(ImutAVLTree< ImutInfo > *Tree)
Class you can specialize to provide custom retain/release functionality for a type.