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