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