include/llvm/ADT/ImmutableSet.h

   1 //===--- ImmutableSet.h - Immutable (functional) set interface --*- C++ -*-===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file was developed by Ted Kremenek and is distributed under
   6 // the University of Illinois Open Source 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 <cassert>
  20
  21 namespace llvm {
  22
  23 //===----------------------------------------------------------------------===//
  24 // Immutable AVL-Tree Definition.
  25 //===----------------------------------------------------------------------===//
  26
  27 template <typename ImutInfo> class ImutAVLFactory;
  28
  29 template <typename ImutInfo> class ImutAVLTreeInOrderIterator;
  30
  31 template <typename ImutInfo >
  32 class ImutAVLTree : public FoldingSetNode {
  33   struct ComputeIsEqual;
  34 public:
  35   typedef typename ImutInfo::key_type_ref   key_type_ref;
  36   typedef typename ImutInfo::value_type     value_type;
  37   typedef typename ImutInfo::value_type_ref value_type_ref;
  38
  39   typedef ImutAVLFactory<ImutInfo>          Factory;
  40   friend class ImutAVLFactory<ImutInfo>;
  41
  42   typedef ImutAVLTreeInOrderIterator<ImutInfo>  iterator;
  43
  44   //===----------------------------------------------------===//
  45   // Public Interface.
  46   //===----------------------------------------------------===//
  47
  48   ImutAVLTree* getLeft() const { return reinterpret_cast<ImutAVLTree*>(Left); }
  49
  50   ImutAVLTree* getRight() const { return Right; }
  51
  52   unsigned getHeight() const { return Height; }
  53
  54   const value_type& getValue() const { return Value; }
  55
  56   ImutAVLTree* find(key_type_ref K) {
  57     ImutAVLTree *T = this;
  58
  59     while (T) {
  60       key_type_ref CurrentKey = ImutInfo::KeyOfValue(T->getValue());
  61
  62       if (ImutInfo::isEqual(K,CurrentKey))
  63         return T;
  64       else if (ImutInfo::isLess(K,CurrentKey))
  65         T = T->getLeft();
  66       else
  67         T = T->getRight();
  68     }
  69
  70     return NULL;
  71   }
  72
  73   unsigned size() const {
  74     unsigned n = 1;
  75
  76     if (const ImutAVLTree* L = getLeft())  n += L->size();
  77     if (const ImutAVLTree* R = getRight()) n += R->size();
  78
  79     return n;
  80   }
  81
  82   iterator begin() const { return iterator(this); }
  83   iterator end() const { return iterator(); }
  84
  85   bool isEqual(const ImutAVLTree& RHS) const {
  86     if (&RHS == this)
  87       return true;
  88
  89     iterator LItr = begin(), LEnd = end();
  90     iterator RItr = RHS.begin(), REnd = RHS.end();
  91
  92     while (LItr != LEnd && RItr != REnd) {
  93       if (*LItr == *RItr) {
  94         LItr.SkipSubTree();
  95         RItr.SkipSubTree();
  96         continue;
  97       }
  98
  99       // FIXME: need to compare data values, not key values, but our
 100       // traits don't support this yet.
 101       if (!ImutInfo::isEqual(ImutInfo::KeyOfValue(LItr->getValue()),
 102                              ImutInfo::KeyOfValue(RItr->getValue())))
 103         return false;
 104
 105       ++LItr;
 106       ++RItr;
 107     }
 108
 109     return LItr == LEnd && RItr == REnd;
 110   }
 111
 112   bool isNotEqual(const ImutAVLTree& RHS) const { return !isEqual(RHS); }
 113
 114   bool contains(const key_type_ref K) { return (bool) find(K); }
 115
 116   template <typename Callback>
 117   void foreach(Callback& C) {
 118     if (ImutAVLTree* L = getLeft()) L->foreach(C);
 119
 120     C(Value);
 121
 122     if (ImutAVLTree* R = getRight()) R->foreach(C);
 123   }
 124
 125   unsigned verify() const {
 126     unsigned HL = getLeft() ? getLeft()->verify() : 0;
 127     unsigned HR = getRight() ? getRight()->verify() : 0;
 128
 129     assert (getHeight() == ( HL > HR ? HL : HR ) + 1
 130             && "Height calculation wrong.");
 131
 132     assert ((HL > HR ? HL-HR : HR-HL) <= 2
 133             && "Balancing invariant violated.");
 134
 135
 136     assert (!getLeft()
 137             || ImutInfo::isLess(ImutInfo::KeyOfValue(getLeft()->getValue()),
 138                                 ImutInfo::KeyOfValue(getValue()))
 139             && "Value in left child is not less that current value.");
 140
 141
 142     assert (!getRight()
 143             || ImutInfo::isLess(ImutInfo::KeyOfValue(getValue()),
 144                                 ImutInfo::KeyOfValue(getRight()->getValue()))
 145             && "Current value is not less that value of right child.");
 146
 147     return getHeight();
 148   }
 149
 150   //===----------------------------------------------------===//
 151   // Internal Values.
 152   //===----------------------------------------------------===//
 153
 154 private:
 155   uintptr_t        Left;
 156   ImutAVLTree*     Right;
 157   unsigned         Height;
 158   value_type       Value;
 159
 160   //===----------------------------------------------------===//
 161   // Profiling or FoldingSet.
 162   //===----------------------------------------------------===//
 163
 164   static inline
 165   void Profile(FoldingSetNodeID& ID, ImutAVLTree* L, ImutAVLTree* R,
 166                unsigned H, value_type_ref V) {
 167     ID.AddPointer(L);
 168     ID.AddPointer(R);
 169     ID.AddInteger(H);
 170     ImutInfo::Profile(ID,V);
 171   }
 172
 173 public:
 174
 175   void Profile(FoldingSetNodeID& ID) {
 176     Profile(ID,getSafeLeft(),getRight(),getHeight(),getValue());
 177   }
 178
 179   //===----------------------------------------------------===//
 180   // Internal methods (node manipulation; used by Factory).
 181   //===----------------------------------------------------===//
 182
 183 private:
 184
 185   ImutAVLTree(ImutAVLTree* l, ImutAVLTree* r, value_type_ref v, unsigned height)
 186   : Left(reinterpret_cast<uintptr_t>(l) | 0x1),
 187   Right(r), Height(height), Value(v) {}
 188
 189   bool isMutable() const { return Left & 0x1; }
 190
 191   ImutAVLTree* getSafeLeft() const {
 192     return reinterpret_cast<ImutAVLTree*>(Left & ~0x1);
 193   }
 194
 195   // Mutating operations.  A tree root can be manipulated as long as
 196   // its reference has not "escaped" from internal methods of a
 197   // factory object (see below).  When a tree pointer is externally
 198   // viewable by client code, the internal "mutable bit" is cleared
 199   // to mark the tree immutable.  Note that a tree that still has
 200   // its mutable bit set may have children (subtrees) that are themselves
 201   // immutable.
 202
 203   void RemoveMutableFlag() {
 204     assert (Left & 0x1 && "Mutable flag already removed.");
 205     Left &= ~0x1;
 206   }
 207
 208   void setLeft(ImutAVLTree* NewLeft) {
 209     assert (isMutable());
 210     Left = reinterpret_cast<uintptr_t>(NewLeft) | 0x1;
 211   }
 212
 213   void setRight(ImutAVLTree* NewRight) {
 214     assert (isMutable());
 215     Right = NewRight;
 216   }
 217
 218   void setHeight(unsigned h) {
 219     assert (isMutable());
 220     Height = h;
 221   }
 222 };
 223
 224 //===----------------------------------------------------------------------===//
 225 // Immutable AVL-Tree Factory class.
 226 //===----------------------------------------------------------------------===//
 227
 228 template <typename ImutInfo >
 229 class ImutAVLFactory {
 230   typedef ImutAVLTree<ImutInfo> TreeTy;
 231   typedef typename TreeTy::value_type_ref value_type_ref;
 232   typedef typename TreeTy::key_type_ref   key_type_ref;
 233
 234   typedef FoldingSet<TreeTy> CacheTy;
 235
 236   CacheTy Cache;
 237   BumpPtrAllocator Allocator;
 238
 239   //===--------------------------------------------------===//
 240   // Public interface.
 241   //===--------------------------------------------------===//
 242
 243 public:
 244   ImutAVLFactory() {}
 245
 246   TreeTy* Add(TreeTy* T, value_type_ref V) {
 247     T = Add_internal(V,T);
 248     MarkImmutable(T);
 249     return T;
 250   }
 251
 252   TreeTy* Remove(TreeTy* T, key_type_ref V) {
 253     T = Remove_internal(V,T);
 254     MarkImmutable(T);
 255     return T;
 256   }
 257
 258   TreeTy* GetEmptyTree() const { return NULL; }
 259
 260   //===--------------------------------------------------===//
 261   // A bunch of quick helper functions used for reasoning
 262   // about the properties of trees and their children.
 263   // These have succinct names so that the balancing code
 264   // is as terse (and readable) as possible.
 265   //===--------------------------------------------------===//
 266 private:
 267
 268   bool isEmpty(TreeTy* T) const {
 269     return !T;
 270   }
 271
 272   unsigned Height(TreeTy* T) const {
 273     return T ? T->getHeight() : 0;
 274   }
 275
 276   TreeTy* Left(TreeTy* T) const {
 277     assert (T);
 278     return T->getSafeLeft();
 279   }
 280
 281   TreeTy* Right(TreeTy* T) const {
 282     assert (T);
 283     return T->getRight();
 284   }
 285
 286   value_type_ref Value(TreeTy* T) const {
 287     assert (T);
 288     return T->Value;
 289   }
 290
 291   unsigned IncrementHeight(TreeTy* L, TreeTy* R) const {
 292     unsigned hl = Height(L);
 293     unsigned hr = Height(R);
 294     return ( hl > hr ? hl : hr ) + 1;
 295   }
 296
 297   //===--------------------------------------------------===//
 298   // "CreateNode" is used to generate new tree roots that link
 299   // to other trees.  The functon may also simply move links
 300   // in an existing root if that root is still marked mutable.
 301   // This is necessary because otherwise our balancing code
 302   // would leak memory as it would create nodes that are
 303   // then discarded later before the finished tree is
 304   // returned to the caller.
 305   //===--------------------------------------------------===//
 306
 307   TreeTy* CreateNode(TreeTy* L, value_type_ref V, TreeTy* R) {
 308     FoldingSetNodeID ID;
 309     unsigned height = IncrementHeight(L,R);
 310
 311     TreeTy::Profile(ID,L,R,height,V);
 312     void* InsertPos;
 313
 314     if (TreeTy* T = Cache.FindNodeOrInsertPos(ID,InsertPos))
 315       return T;
 316
 317     assert (InsertPos != NULL);
 318
 319     // FIXME: more intelligent calculation of alignment.
 320     TreeTy* T = (TreeTy*) Allocator.Allocate(sizeof(*T),16);
 321     new (T) TreeTy(L,R,V,height);
 322
 323     Cache.InsertNode(T,InsertPos);
 324     return T;
 325   }
 326
 327   TreeTy* CreateNode(TreeTy* L, TreeTy* OldTree, TreeTy* R) {
 328     assert (!isEmpty(OldTree));
 329
 330     if (OldTree->isMutable()) {
 331       OldTree->setLeft(L);
 332       OldTree->setRight(R);
 333       OldTree->setHeight(IncrementHeight(L,R));
 334       return OldTree;
 335     }
 336     else return CreateNode(L, Value(OldTree), R);
 337   }
 338
 339   /// Balance - Used by Add_internal and Remove_internal to
 340   ///  balance a newly created tree.
 341   TreeTy* Balance(TreeTy* L, value_type_ref V, TreeTy* R) {
 342
 343     unsigned hl = Height(L);
 344     unsigned hr = Height(R);
 345
 346     if (hl > hr + 2) {
 347       assert (!isEmpty(L) &&
 348               "Left tree cannot be empty to have a height >= 2.");
 349
 350       TreeTy* LL = Left(L);
 351       TreeTy* LR = Right(L);
 352
 353       if (Height(LL) >= Height(LR))
 354         return CreateNode(LL, L, CreateNode(LR,V,R));
 355
 356       assert (!isEmpty(LR) &&
 357               "LR cannot be empty because it has a height >= 1.");
 358
 359       TreeTy* LRL = Left(LR);
 360       TreeTy* LRR = Right(LR);
 361
 362       return CreateNode(CreateNode(LL,L,LRL), LR, CreateNode(LRR,V,R));
 363     }
 364     else if (hr > hl + 2) {
 365       assert (!isEmpty(R) &&
 366               "Right tree cannot be empty to have a height >= 2.");
 367
 368       TreeTy* RL = Left(R);
 369       TreeTy* RR = Right(R);
 370
 371       if (Height(RR) >= Height(RL))
 372         return CreateNode(CreateNode(L,V,RL), R, RR);
 373
 374       assert (!isEmpty(RL) &&
 375               "RL cannot be empty because it has a height >= 1.");
 376
 377       TreeTy* RLL = Left(RL);
 378       TreeTy* RLR = Right(RL);
 379
 380       return CreateNode(CreateNode(L,V,RLL), RL, CreateNode(RLR,R,RR));
 381     }
 382     else
 383       return CreateNode(L,V,R);
 384   }
 385
 386   /// Add_internal - Creates a new tree that includes the specified
 387   ///  data and the data from the original tree.  If the original tree
 388   ///  already contained the data item, the original tree is returned.
 389   TreeTy* Add_internal(value_type_ref V, TreeTy* T) {
 390     if (isEmpty(T))
 391       return CreateNode(T, V, T);
 392
 393     assert (!T->isMutable());
 394
 395     key_type_ref K = ImutInfo::KeyOfValue(V);
 396     key_type_ref KCurrent = ImutInfo::KeyOfValue(Value(T));
 397
 398     if (ImutInfo::isEqual(K,KCurrent))
 399       return CreateNode(Left(T), V, Right(T));
 400     else if (ImutInfo::isLess(K,KCurrent))
 401       return Balance(Add_internal(V,Left(T)), Value(T), Right(T));
 402     else
 403       return Balance(Left(T), Value(T), Add_internal(V,Right(T)));
 404   }
 405
 406   /// Remove_interal - Creates a new tree that includes all the data
 407   ///  from the original tree except the specified data.  If the
 408   ///  specified data did not exist in the original tree, the original
 409   ///  tree is returned.
 410   TreeTy* Remove_internal(key_type_ref K, TreeTy* T) {
 411     if (isEmpty(T))
 412       return T;
 413
 414     assert (!T->isMutable());
 415
 416     key_type_ref KCurrent = ImutInfo::KeyOfValue(Value(T));
 417
 418     if (ImutInfo::isEqual(K,KCurrent))
 419       return CombineLeftRightTrees(Left(T),Right(T));
 420     else if (ImutInfo::isLess(K,KCurrent))
 421       return Balance(Remove_internal(K,Left(T)), Value(T), Right(T));
 422     else
 423       return Balance(Left(T), Value(T), Remove_internal(K,Right(T)));
 424   }
 425
 426   TreeTy* CombineLeftRightTrees(TreeTy* L, TreeTy* R) {
 427     if (isEmpty(L)) return R;
 428     if (isEmpty(R)) return L;
 429
 430     TreeTy* OldNode;
 431     TreeTy* NewRight = RemoveMinBinding(R,OldNode);
 432     return Balance(L,Value(OldNode),NewRight);
 433   }
 434
 435   TreeTy* RemoveMinBinding(TreeTy* T, TreeTy*& NodeRemoved) {
 436     assert (!isEmpty(T));
 437
 438     if (isEmpty(Left(T))) {
 439       NodeRemoved = T;
 440       return Right(T);
 441     }
 442
 443     return Balance(RemoveMinBinding(Left(T),NodeRemoved),Value(T),Right(T));
 444   }
 445
 446   /// MarkImmutable - Clears the mutable bits of a root and all of its
 447   ///  descendants.
 448   void MarkImmutable(TreeTy* T) {
 449     if (!T || !T->isMutable())
 450       return;
 451
 452     T->RemoveMutableFlag();
 453     MarkImmutable(Left(T));
 454     MarkImmutable(Right(T));
 455   }
 456 };
 457
 458
 459 //===----------------------------------------------------------------------===//
 460 // Immutable AVL-Tree Iterators.
 461 //===----------------------------------------------------------------------===//
 462
 463 template <typename ImutInfo>
 464 class ImutAVLTreeGenericIterator {
 465   SmallVector<uintptr_t,20> stack;
 466 public:
 467   enum VisitFlag { VisitedNone=0x0, VisitedLeft=0x1, VisitedRight=0x3,
 468                    Flags=0x3 };
 469
 470   typedef ImutAVLTree<ImutInfo> TreeTy;
 471   typedef ImutAVLTreeGenericIterator<ImutInfo> _Self;
 472
 473   inline ImutAVLTreeGenericIterator() {}
 474   inline ImutAVLTreeGenericIterator(const TreeTy* Root) {
 475     if (Root) stack.push_back(reinterpret_cast<uintptr_t>(Root));
 476   }
 477
 478   TreeTy* operator*() const {
 479     assert (!stack.empty());
 480     return reinterpret_cast<TreeTy*>(stack.back() & ~Flags);
 481   }
 482
 483   uintptr_t getVisitState() {
 484     assert (!stack.empty());
 485     return stack.back() & Flags;
 486   }
 487
 488
 489   bool AtEnd() const { return stack.empty(); }
 490
 491   bool AtBeginning() const {
 492     return stack.size() == 1 && getVisitState() == VisitedNone;
 493   }
 494
 495   void SkipToParent() {
 496     assert (!stack.empty());
 497     stack.pop_back();
 498
 499     if (stack.empty())
 500       return;
 501
 502     switch (getVisitState()) {
 503       case VisitedNone:
 504         stack.back() |= VisitedLeft;
 505         break;
 506       case VisitedLeft:
 507         stack.back() |= VisitedRight;
 508         break;
 509       default:
 510         assert (false && "Unreachable.");
 511     }
 512   }
 513
 514   inline bool operator==(const _Self& x) const {
 515     if (stack.size() != x.stack.size())
 516       return false;
 517
 518     for (unsigned i = 0 ; i < stack.size(); i++)
 519       if (stack[i] != x.stack[i])
 520         return false;
 521
 522     return true;
 523   }
 524
 525   inline bool operator!=(const _Self& x) const { return !operator==(x); }
 526
 527   _Self& operator++() {
 528     assert (!stack.empty());
 529
 530     TreeTy* Current = reinterpret_cast<TreeTy*>(stack.back() & ~Flags);
 531     assert (Current);
 532
 533     switch (getVisitState()) {
 534       case VisitedNone:
 535         if (TreeTy* L = Current->getLeft())
 536           stack.push_back(reinterpret_cast<uintptr_t>(L));
 537         else
 538           stack.back() |= VisitedLeft;
 539
 540         break;
 541
 542       case VisitedLeft:
 543         if (TreeTy* R = Current->getRight())
 544           stack.push_back(reinterpret_cast<uintptr_t>(R));
 545         else
 546           stack.back() |= VisitedRight;
 547
 548         break;
 549
 550       case VisitedRight:
 551         SkipToParent();
 552         break;
 553
 554       default:
 555         assert (false && "Unreachable.");
 556     }
 557
 558     return *this;
 559   }
 560
 561   _Self& operator--() {
 562     assert (!stack.empty());
 563
 564     TreeTy* Current = reinterpret_cast<TreeTy*>(stack.back() & ~Flags);
 565     assert (Current);
 566
 567     switch (getVisitState()) {
 568       case VisitedNone:
 569         stack.pop_back();
 570         break;
 571
 572       case VisitedLeft:
 573         stack.back() &= ~Flags; // Set state to "VisitedNone."
 574
 575         if (TreeTy* L = Current->getLeft())
 576           stack.push_back(reinterpret_cast<uintptr_t>(L) | VisitedRight);
 577
 578         break;
 579
 580       case VisitedRight:
 581         stack.back() &= ~Flags;
 582         stack.back() |= VisitedLeft;
 583
 584         if (TreeTy* R = Current->getRight())
 585           stack.push_back(reinterpret_cast<uintptr_t>(R) | VisitedRight);
 586
 587         break;
 588
 589       default:
 590         assert (false && "Unreachable.");
 591     }
 592
 593     return *this;
 594   }
 595 };
 596
 597 template <typename ImutInfo>
 598 class ImutAVLTreeInOrderIterator {
 599   typedef ImutAVLTreeGenericIterator<ImutInfo> InternalIteratorTy;
 600   InternalIteratorTy InternalItr;
 601
 602 public:
 603   typedef ImutAVLTree<ImutInfo> TreeTy;
 604   typedef ImutAVLTreeInOrderIterator<ImutInfo> _Self;
 605
 606   ImutAVLTreeInOrderIterator(const TreeTy* Root) : InternalItr(Root) {
 607     if (Root) operator++(); // Advance to first element.
 608   }
 609
 610   ImutAVLTreeInOrderIterator() : InternalItr() {}
 611
 612   inline bool operator==(const _Self& x) const {
 613     return InternalItr == x.InternalItr;
 614   }
 615
 616   inline bool operator!=(const _Self& x) const { return !operator==(x); }
 617
 618   inline TreeTy* operator*() { return *InternalItr; }
 619   inline TreeTy* operator->() { return *InternalItr; }
 620
 621   inline _Self& operator++() {
 622     do ++InternalItr;
 623     while (!InternalItr.AtEnd() &&
 624            InternalItr.getVisitState() != InternalIteratorTy::VisitedLeft);
 625
 626     return *this;
 627   }
 628
 629   inline _Self& operator--() {
 630     do --InternalItr;
 631     while (!InternalItr.AtBeginning() &&
 632            InternalItr.getVisitState() != InternalIteratorTy::VisitedLeft);
 633
 634     return *this;
 635   }
 636
 637   inline void SkipSubTree() {
 638     InternalItr.SkipToParent();
 639
 640     while (!InternalItr.AtEnd() &&
 641            InternalItr.getVisitState() != InternalIteratorTy::VisitedLeft)
 642       ++InternalItr;
 643   }
 644 };
 645
 646 //===----------------------------------------------------------------------===//
 647 // Trait classes for Profile information.
 648 //===----------------------------------------------------------------------===//
 649
 650 /// Generic profile template.  The default behavior is to invoke the
 651 /// profile method of an object.  Specializations for primitive integers
 652 /// and generic handling of pointers is done below.
 653 template <typename T>
 654 struct ImutProfileInfo {
 655   typedef const T  value_type;
 656   typedef const T& value_type_ref;
 657
 658   static inline void Profile(FoldingSetNodeID& ID, value_type_ref X) {
 659     X.Profile(ID);
 660   }
 661 };
 662
 663 /// Profile traits for integers.
 664 template <typename T>
 665 struct ImutProfileInteger {
 666   typedef const T  value_type;
 667   typedef const T& value_type_ref;
 668
 669   static inline void Profile(FoldingSetNodeID& ID, value_type_ref X) {
 670     ID.AddInteger(X);
 671   }
 672 };
 673
 674 #define PROFILE_INTEGER_INFO(X)\
 675 template<> struct ImutProfileInfo<X> : ImutProfileInteger<X> {};
 676
 677 PROFILE_INTEGER_INFO(char)
 678 PROFILE_INTEGER_INFO(unsigned char)
 679 PROFILE_INTEGER_INFO(short)
 680 PROFILE_INTEGER_INFO(unsigned short)
 681 PROFILE_INTEGER_INFO(unsigned)
 682 PROFILE_INTEGER_INFO(signed)
 683 PROFILE_INTEGER_INFO(long)
 684 PROFILE_INTEGER_INFO(unsigned long)
 685 PROFILE_INTEGER_INFO(long long)
 686 PROFILE_INTEGER_INFO(unsigned long long)
 687
 688 #undef PROFILE_INTEGER_INFO
 689
 690 /// Generic profile trait for pointer types.  We treat pointers as
 691 /// references to unique objects.
 692 template <typename T>
 693 struct ImutProfileInfo<T*> {
 694   typedef const T*   value_type;
 695   typedef value_type value_type_ref;
 696
 697   static inline void Profile(FoldingSetNodeID &ID, value_type_ref X) {
 698     ID.AddPointer(X);
 699   }
 700 };
 701
 702 //===----------------------------------------------------------------------===//
 703 // Trait classes that contain element comparison operators and type
 704 //  definitions used by ImutAVLTree, ImmutableSet, and ImmutableMap.  These
 705 //  inherit from the profile traits (ImutProfileInfo) to include operations
 706 //  for element profiling.
 707 //===----------------------------------------------------------------------===//
 708
 709
 710 /// ImutContainerInfo - Generic definition of comparison operations for
 711 ///   elements of immutable containers that defaults to using
 712 ///   std::equal_to<> and std::less<> to perform comparison of elements.
 713 template <typename T>
 714 struct ImutContainerInfo : public ImutProfileInfo<T> {
 715   typedef typename ImutProfileInfo<T>::value_type      value_type;
 716   typedef typename ImutProfileInfo<T>::value_type_ref  value_type_ref;
 717   typedef value_type      key_type;
 718   typedef value_type_ref  key_type_ref;
 719
 720   static inline key_type_ref KeyOfValue(value_type_ref D) { return D; }
 721
 722   static inline bool isEqual(key_type_ref LHS, key_type_ref RHS) {
 723     return std::equal_to<key_type>()(LHS,RHS);
 724   }
 725
 726   static inline bool isLess(key_type_ref LHS, key_type_ref RHS) {
 727     return std::less<key_type>()(LHS,RHS);
 728   }
 729 };
 730
 731 /// ImutContainerInfo - Specialization for pointer values to treat pointers
 732 ///  as references to unique objects.  Pointers are thus compared by
 733 ///  their addresses.
 734 template <typename T>
 735 struct ImutContainerInfo<T*> : public ImutProfileInfo<T*> {
 736   typedef typename ImutProfileInfo<T*>::value_type      value_type;
 737   typedef typename ImutProfileInfo<T*>::value_type_ref  value_type_ref;
 738   typedef value_type      key_type;
 739   typedef value_type_ref  key_type_ref;
 740
 741   static inline key_type_ref KeyOfValue(value_type_ref D) { return D; }
 742
 743   static inline bool isEqual(key_type_ref LHS, key_type_ref RHS) {
 744     return LHS == RHS;
 745   }
 746
 747   static inline bool isLess(key_type_ref LHS, key_type_ref RHS) {
 748     return LHS < RHS;
 749   }
 750 };
 751
 752 //===----------------------------------------------------------------------===//
 753 // Immutable Set
 754 //===----------------------------------------------------------------------===//
 755
 756 template <typename ValT, typename ValInfo = ImutContainerInfo<ValT> >
 757 class ImmutableSet {
 758 public:
 759   typedef typename ValInfo::value_type      value_type;
 760   typedef typename ValInfo::value_type_ref  value_type_ref;
 761
 762 private:
 763   typedef ImutAVLTree<ValInfo> TreeTy;
 764   TreeTy* Root;
 765
 766   ImmutableSet(TreeTy* R) : Root(R) {}
 767
 768 public:
 769
 770   class Factory {
 771     typename TreeTy::Factory F;
 772
 773   public:
 774     Factory() {}
 775
 776     ImmutableSet GetEmptySet() { return ImmutableSet(F.GetEmptyTree()); }
 777
 778     ImmutableSet Add(ImmutableSet Old, value_type_ref V) {
 779       return ImmutableSet(F.Add(Old.Root,V));
 780     }
 781
 782     ImmutableSet Remove(ImmutableSet Old, value_type_ref V) {
 783       return ImmutableSet(F.Remove(Old.Root,V));
 784     }
 785
 786   private:
 787     Factory(const Factory& RHS) {};
 788     void operator=(const Factory& RHS) {};
 789   };
 790
 791   friend class Factory;
 792
 793   bool contains(const value_type_ref V) const {
 794     return Root ? Root->contains(V) : false;
 795   }
 796
 797   bool operator==(ImmutableSet RHS) const {
 798     return Root && RHS.Root ? Root->isEqual(*RHS.Root) : Root == RHS.Root;
 799   }
 800
 801   bool operator!=(ImmutableSet RHS) const {
 802     return Root && RHS.Root ? Root->isNotEqual(*RHS.Root) : Root != RHS.Root;
 803   }
 804
 805   bool isEmpty() const { return !Root; }
 806
 807   template <typename Callback>
 808   void foreach(Callback& C) { if (Root) Root->foreach(C); }
 809
 810   template <typename Callback>
 811   void foreach() { if (Root) { Callback C; Root->foreach(C); } }
 812
 813   //===--------------------------------------------------===//
 814   // For testing.
 815   //===--------------------------------------------------===//
 816
 817   void verify() const { if (Root) Root->verify(); }
 818   unsigned getHeight() const { return Root ? Root->getHeight() : 0; }
 819 };
 820
 821 } // end namespace llvm
 822
 823 #endif