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