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 | |
31 | namespace llvm { |
32 | |
33 | //===----------------------------------------------------------------------===// |
34 | // Immutable AVL-Tree Definition. |
35 | //===----------------------------------------------------------------------===// |
36 | |
37 | template <typename ImutInfo> class ImutAVLFactory; |
38 | template <typename ImutInfo> class ImutIntervalAVLFactory; |
39 | template <typename ImutInfo> class ImutAVLTreeInOrderIterator; |
40 | template <typename ImutInfo> class ImutAVLTreeGenericIterator; |
41 | |
42 | template <typename ImutInfo > |
43 | class ImutAVLTree { |
44 | public: |
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 | |
208 | private: |
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 | |
228 | private: |
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 | |
317 | public: |
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 | |
348 | template <typename ImutInfo> |
349 | struct 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 | |
358 | template <typename ImutInfo > |
359 | class 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 | |
384 | public: |
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 | |
411 | protected: |
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 | |
599 | public: |
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 | |
641 | template <typename ImutInfo> class ImutAVLTreeGenericIterator { |
642 | SmallVector<uintptr_t,20> stack; |
643 | |
644 | public: |
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 | |
755 | template <typename ImutInfo> class ImutAVLTreeInOrderIterator { |
756 | using InternalIteratorTy = ImutAVLTreeGenericIterator<ImutInfo>; |
757 | |
758 | InternalIteratorTy InternalItr; |
759 | |
760 | public: |
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. |
814 | template <typename T> |
815 | struct 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. |
837 | template <typename T> |
838 | struct 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. |
848 | template <typename T> |
849 | struct 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)\ |
859 | template<> struct ImutProfileInfo<X> : ImutProfileInteger<X> {}; |
860 | |
861 | PROFILE_INTEGER_INFO(char) |
862 | PROFILE_INTEGER_INFO(unsigned char) |
863 | PROFILE_INTEGER_INFO(short) |
864 | PROFILE_INTEGER_INFO(unsigned short) |
865 | PROFILE_INTEGER_INFO(unsigned) |
866 | PROFILE_INTEGER_INFO(signed) |
867 | PROFILE_INTEGER_INFO(long) |
868 | PROFILE_INTEGER_INFO(unsigned long) |
869 | PROFILE_INTEGER_INFO(long long) |
870 | PROFILE_INTEGER_INFO(unsigned long long) |
871 | |
872 | #undef PROFILE_INTEGER_INFO |
873 | |
874 | /// Profile traits for booleans. |
875 | template <> |
876 | struct 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. |
887 | template <typename T> |
888 | struct 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. |
907 | template <typename T> |
908 | struct 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. |
933 | template <typename T> |
934 | struct 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 | |
956 | template <typename ValT, typename ValInfo = ImutContainerInfo<ValT>> |
957 | class ImmutableSet { |
958 | public: |
959 | using value_type = typename ValInfo::value_type; |
960 | using value_type_ref = typename ValInfo::value_type_ref; |
961 | using TreeTy = ImutAVLTree<ValInfo>; |
962 | |
963 | private: |
964 | IntrusiveRefCntPtr<TreeTy> Root; |
965 | |
966 | public: |
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. |
1082 | template <typename ValT, typename ValInfo = ImutContainerInfo<ValT>> |
1083 | class ImmutableSetRef { |
1084 | public: |
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 | |
1090 | private: |
1091 | IntrusiveRefCntPtr<TreeTy> Root; |
1092 | FactoryTy *Factory; |
1093 | |
1094 | public: |
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 | |