X-Git-Url: http://plrg.eecs.uci.edu/git/?a=blobdiff_plain;f=include%2Fllvm%2FADT%2FImmutableSet.h;h=87026f019fec93c500e7a713d5913983cd9cb4c1;hb=df7186636e51e63281bd318234b7d97f25efe491;hp=8e2fea565879021abf33c4f259bdbaf2c0c6a3ff;hpb=166e0539c987a5bea2432354b2437eba29bb1ce0;p=oota-llvm.git

diff --git a/include/llvm/ADT/ImmutableSet.h b/include/llvm/ADT/ImmutableSet.h
index 8e2fea56587..87026f019fe 100644
--- a/include/llvm/ADT/ImmutableSet.h
+++ b/include/llvm/ADT/ImmutableSet.h
@@ -11,17 +11,17 @@
 //
 //===----------------------------------------------------------------------===//
 
-#ifndef LLVM_ADT_IMSET_H
-#define LLVM_ADT_IMSET_H
+#ifndef LLVM_ADT_IMMUTABLESET_H
+#define LLVM_ADT_IMMUTABLESET_H
 
-#include "llvm/Support/Allocator.h"
 #include "llvm/ADT/DenseMap.h"
 #include "llvm/ADT/FoldingSet.h"
+#include "llvm/Support/Allocator.h"
 #include "llvm/Support/DataTypes.h"
+#include "llvm/Support/ErrorHandling.h"
 #include <cassert>
 #include <functional>
 #include <vector>
-#include <stdio.h>
 
 namespace llvm {
 
@@ -81,15 +81,15 @@ public:
       else
         T = T->getRight();
     }
-    return NULL;
+    return nullptr;
   }
-  
+
   /// getMaxElement - Find the subtree associated with the highest ranged
   ///  key value.
   ImutAVLTree* getMaxElement() {
     ImutAVLTree *T = this;
-    ImutAVLTree *Right = T->getRight();    
-    while (Right) { T = right; right = T->getRight(); }
+    ImutAVLTree *Right = T->getRight();
+    while (Right) { T = Right; Right = T->getRight(); }
     return T;
   }
 
@@ -142,13 +142,13 @@ public:
     iterator RItr = RHS.begin(), REnd = RHS.end();
 
     while (LItr != LEnd && RItr != REnd) {
-      if (*LItr == *RItr) {
+      if (&*LItr == &*RItr) {
         LItr.skipSubTree();
         RItr.skipSubTree();
         continue;
       }
 
-      if (!LItr->isElementEqual(*RItr))
+      if (!LItr->isElementEqual(&*RItr))
         return false;
 
       ++LItr;
@@ -242,9 +242,9 @@ private:
   ///   ImutAVLFactory.
   ImutAVLTree(Factory *f, ImutAVLTree* l, ImutAVLTree* r, value_type_ref v,
               unsigned height)
-    : factory(f), left(l), right(r), prev(0), next(0), height(height),
-      IsMutable(true), IsDigestCached(false), IsCanonicalized(0),
-      value(v), digest(0), refCount(0)
+    : factory(f), left(l), right(r), prev(nullptr), next(nullptr),
+      height(height), IsMutable(true), IsDigestCached(false),
+      IsCanonicalized(0), value(v), digest(0), refCount(0)
   {
     if (left) left->retain();
     if (right) right->retain();
@@ -257,7 +257,7 @@ private:
   ///  method returns false for an instance of ImutAVLTree, all subtrees
   ///  will also have this method return false.  The converse is not true.
   bool isMutable() const { return IsMutable; }
-  
+
   /// hasCachedDigest - Returns true if the digest for this tree is cached.
   ///  This can only be true if the tree is immutable.
   bool hasCachedDigest() const { return IsDigestCached; }
@@ -279,7 +279,7 @@ private:
     assert(isMutable() && "Mutable flag already removed.");
     IsMutable = false;
   }
-  
+
   /// markedCachedDigest - Clears the NoCachedDigest flag for a tree.
   void markedCachedDigest() {
     assert(!hasCachedDigest() && "NoCachedDigest flag already removed.");
@@ -293,8 +293,8 @@ private:
     height = h;
   }
 
-  static inline
-  uint32_t computeDigest(ImutAVLTree* L, ImutAVLTree* R, value_type_ref V) {
+  static uint32_t computeDigest(ImutAVLTree *L, ImutAVLTree *R,
+                                value_type_ref V) {
     uint32_t digest = 0;
 
     if (L)
@@ -311,7 +311,7 @@ private:
     return digest;
   }
 
-  inline uint32_t computeDigest() {
+  uint32_t computeDigest() {
     // Check the lowest bit to determine if digest has actually been
     // pre-computed.
     if (hasCachedDigest())
@@ -346,9 +346,9 @@ public:
       if (prev)
         prev->next = next;
       else
-        factory->Cache[computeDigest()] = next;
+        factory->Cache[factory->maskCacheIndex(computeDigest())] = next;
     }
-    
+
     // We need to clear the mutability bit in case we are
     // destroying the node as part of a sweep in ImutAVLFactory::recoverNodes().
     IsMutable = false;
@@ -411,10 +411,10 @@ public:
     return T;
   }
 
-  TreeTy* getEmptyTree() const { return NULL; }
+  TreeTy* getEmptyTree() const { return nullptr; }
 
 protected:
-  
+
   //===--------------------------------------------------===//
   // A bunch of quick helper functions used for reasoning
   // about the properties of trees and their children.
@@ -428,6 +428,9 @@ protected:
   TreeTy*         getRight(TreeTy* T) const { return T->getRight(); }
   value_type_ref  getValue(TreeTy* T) const { return T->value; }
 
+  // Make sure the index is not the Tombstone or Entry key of the DenseMap.
+  static unsigned maskCacheIndex(unsigned I) { return (I & ~0x02); }
+
   unsigned incrementHeight(TreeTy* L, TreeTy* R) const {
     unsigned hl = getHeight(L);
     unsigned hr = getHeight(R);
@@ -439,7 +442,7 @@ protected:
                                      typename TreeTy::iterator& TE) {
     typename TreeTy::iterator I = T->begin(), E = T->end();
     for ( ; I!=E ; ++I, ++TI) {
-      if (TI == TE || !I->isElementEqual(*TI))
+      if (TI == TE || !I->isElementEqual(&*TI))
         return false;
     }
     return true;
@@ -455,7 +458,7 @@ protected:
   // returned to the caller.
   //===--------------------------------------------------===//
 
-  TreeTy* createNode(TreeTy* L, value_type_ref V, TreeTy* R) {   
+  TreeTy* createNode(TreeTy* L, value_type_ref V, TreeTy* R) {
     BumpPtrAllocator& A = getAllocator();
     TreeTy* T;
     if (!freeNodes.empty()) {
@@ -463,8 +466,7 @@ protected:
       freeNodes.pop_back();
       assert(T != L);
       assert(T != R);
-    }
-    else {
+    } else {
       T = (TreeTy*) A.Allocate<TreeTy>();
     }
     new (T) TreeTy(this, L, R, V, incrementHeight(L,R));
@@ -507,7 +509,8 @@ protected:
 
       return createNode(createNode(LL,L,LRL), LR, createNode(LRR,V,R));
     }
-    else if (hr > hl + 2) {
+
+    if (hr > hl + 2) {
       assert(!isEmpty(R) && "Right tree cannot be empty to have a height >= 2");
 
       TreeTy *RL = getLeft(R);
@@ -523,8 +526,8 @@ protected:
 
       return createNode(createNode(L,V,RLL), RL, createNode(RLR,R,RR));
     }
-    else
-      return createNode(L,V,R);
+
+    return createNode(L,V,R);
   }
 
   /// add_internal - Creates a new tree that includes the specified
@@ -598,11 +601,11 @@ protected:
     markImmutable(getLeft(T));
     markImmutable(getRight(T));
   }
-  
+
 public:
   TreeTy *getCanonicalTree(TreeTy *TNew) {
     if (!TNew)
-      return 0;
+      return nullptr;
 
     if (TNew->IsCanonicalized)
       return TNew;
@@ -610,11 +613,11 @@ public:
     // Search the hashtable for another tree with the same digest, and
     // if find a collision compare those trees by their contents.
     unsigned digest = TNew->computeDigest();
-    TreeTy *&entry = Cache[digest];
+    TreeTy *&entry = Cache[maskCacheIndex(digest)];
     do {
       if (!entry)
         break;
-      for (TreeTy *T = entry ; T != 0; T = T->next) {
+      for (TreeTy *T = entry ; T != nullptr; T = T->next) {
         // Compare the Contents('T') with Contents('TNew')
         typename TreeTy::iterator TI = T->begin(), TE = T->end();
         if (!compareTreeWithSection(TNew, TI, TE))
@@ -642,26 +645,28 @@ public:
 //===----------------------------------------------------------------------===//
 
 template <typename ImutInfo>
-class ImutAVLTreeGenericIterator {
+class ImutAVLTreeGenericIterator
+    : public std::iterator<std::bidirectional_iterator_tag,
+                           ImutAVLTree<ImutInfo>> {
   SmallVector<uintptr_t,20> stack;
 public:
   enum VisitFlag { VisitedNone=0x0, VisitedLeft=0x1, VisitedRight=0x3,
                    Flags=0x3 };
 
   typedef ImutAVLTree<ImutInfo> TreeTy;
-  typedef ImutAVLTreeGenericIterator<ImutInfo> _Self;
 
-  inline ImutAVLTreeGenericIterator() {}
-  inline ImutAVLTreeGenericIterator(const TreeTy* Root) {
+  ImutAVLTreeGenericIterator() {}
+  ImutAVLTreeGenericIterator(const TreeTy *Root) {
     if (Root) stack.push_back(reinterpret_cast<uintptr_t>(Root));
   }
 
-  TreeTy* operator*() const {
+  TreeTy &operator*() const {
     assert(!stack.empty());
-    return reinterpret_cast<TreeTy*>(stack.back() & ~Flags);
+    return *reinterpret_cast<TreeTy *>(stack.back() & ~Flags);
   }
+  TreeTy *operator->() const { return &*this; }
 
-  uintptr_t getVisitState() {
+  uintptr_t getVisitState() const {
     assert(!stack.empty());
     return stack.back() & Flags;
   }
@@ -686,22 +691,19 @@ public:
         stack.back() |= VisitedRight;
         break;
       default:
-        assert(false && "Unreachable.");
+        llvm_unreachable("Unreachable.");
     }
   }
 
-  inline bool operator==(const _Self& x) const {
-    if (stack.size() != x.stack.size())
-      return false;
-    for (unsigned i = 0 ; i < stack.size(); i++)
-      if (stack[i] != x.stack[i])
-        return false;
-    return true;
+  bool operator==(const ImutAVLTreeGenericIterator &x) const {
+    return stack == x.stack;
   }
 
-  inline bool operator!=(const _Self& x) const { return !operator==(x); }
+  bool operator!=(const ImutAVLTreeGenericIterator &x) const {
+    return !(*this == x);
+  }
 
-  _Self& operator++() {
+  ImutAVLTreeGenericIterator &operator++() {
     assert(!stack.empty());
     TreeTy* Current = reinterpret_cast<TreeTy*>(stack.back() & ~Flags);
     assert(Current);
@@ -722,12 +724,12 @@ public:
         skipToParent();
         break;
       default:
-        assert(false && "Unreachable.");
+        llvm_unreachable("Unreachable.");
     }
     return *this;
   }
 
-  _Self& operator--() {
+  ImutAVLTreeGenericIterator &operator--() {
     assert(!stack.empty());
     TreeTy* Current = reinterpret_cast<TreeTy*>(stack.back() & ~Flags);
     assert(Current);
@@ -747,37 +749,41 @@ public:
           stack.push_back(reinterpret_cast<uintptr_t>(R) | VisitedRight);
         break;
       default:
-        assert(false && "Unreachable.");
+        llvm_unreachable("Unreachable.");
     }
     return *this;
   }
 };
 
 template <typename ImutInfo>
-class ImutAVLTreeInOrderIterator {
+class ImutAVLTreeInOrderIterator
+    : public std::iterator<std::bidirectional_iterator_tag,
+                           ImutAVLTree<ImutInfo>> {
   typedef ImutAVLTreeGenericIterator<ImutInfo> InternalIteratorTy;
   InternalIteratorTy InternalItr;
 
 public:
   typedef ImutAVLTree<ImutInfo> TreeTy;
-  typedef ImutAVLTreeInOrderIterator<ImutInfo> _Self;
 
   ImutAVLTreeInOrderIterator(const TreeTy* Root) : InternalItr(Root) {
-    if (Root) operator++(); // Advance to first element.
+    if (Root)
+      ++*this; // Advance to first element.
   }
 
   ImutAVLTreeInOrderIterator() : InternalItr() {}
 
-  inline bool operator==(const _Self& x) const {
+  bool operator==(const ImutAVLTreeInOrderIterator &x) const {
     return InternalItr == x.InternalItr;
   }
 
-  inline bool operator!=(const _Self& x) const { return !operator==(x); }
+  bool operator!=(const ImutAVLTreeInOrderIterator &x) const {
+    return !(*this == x);
+  }
 
-  inline TreeTy* operator*() const { return *InternalItr; }
-  inline TreeTy* operator->() const { return *InternalItr; }
+  TreeTy &operator*() const { return *InternalItr; }
+  TreeTy *operator->() const { return &*InternalItr; }
 
-  inline _Self& operator++() {
+  ImutAVLTreeInOrderIterator &operator++() {
     do ++InternalItr;
     while (!InternalItr.atEnd() &&
            InternalItr.getVisitState() != InternalIteratorTy::VisitedLeft);
@@ -785,7 +791,7 @@ public:
     return *this;
   }
 
-  inline _Self& operator--() {
+  ImutAVLTreeInOrderIterator &operator--() {
     do --InternalItr;
     while (!InternalItr.atBeginning() &&
            InternalItr.getVisitState() != InternalIteratorTy::VisitedLeft);
@@ -793,7 +799,7 @@ public:
     return *this;
   }
 
-  inline void skipSubTree() {
+  void skipSubTree() {
     InternalItr.skipToParent();
 
     while (!InternalItr.atEnd() &&
@@ -802,6 +808,24 @@ public:
   }
 };
 
+/// Generic iterator that wraps a T::TreeTy::iterator and exposes
+/// iterator::getValue() on dereference.
+template <typename T>
+struct ImutAVLValueIterator
+    : iterator_adaptor_base<
+          ImutAVLValueIterator<T>, typename T::TreeTy::iterator,
+          typename std::iterator_traits<
+              typename T::TreeTy::iterator>::iterator_category,
+          const typename T::value_type> {
+  ImutAVLValueIterator() = default;
+  explicit ImutAVLValueIterator(typename T::TreeTy *Tree)
+      : ImutAVLValueIterator::iterator_adaptor_base(Tree) {}
+
+  typename ImutAVLValueIterator::reference operator*() const {
+    return this->I->getValue();
+  }
+};
+
 //===----------------------------------------------------------------------===//
 // Trait classes for Profile information.
 //===----------------------------------------------------------------------===//
@@ -814,7 +838,7 @@ struct ImutProfileInfo {
   typedef const T  value_type;
   typedef const T& value_type_ref;
 
-  static inline void Profile(FoldingSetNodeID& ID, value_type_ref X) {
+  static void Profile(FoldingSetNodeID &ID, value_type_ref X) {
     FoldingSetTrait<T>::Profile(X,ID);
   }
 };
@@ -825,7 +849,7 @@ struct ImutProfileInteger {
   typedef const T  value_type;
   typedef const T& value_type_ref;
 
-  static inline void Profile(FoldingSetNodeID& ID, value_type_ref X) {
+  static void Profile(FoldingSetNodeID &ID, value_type_ref X) {
     ID.AddInteger(X);
   }
 };
@@ -846,6 +870,18 @@ PROFILE_INTEGER_INFO(unsigned long long)
 
 #undef PROFILE_INTEGER_INFO
 
+/// Profile traits for booleans.
+template <>
+struct ImutProfileInfo<bool> {
+  typedef const bool  value_type;
+  typedef const bool& value_type_ref;
+
+  static void Profile(FoldingSetNodeID &ID, value_type_ref X) {
+    ID.AddBoolean(X);
+  }
+};
+
+
 /// Generic profile trait for pointer types.  We treat pointers as
 /// references to unique objects.
 template <typename T>
@@ -853,7 +889,7 @@ struct ImutProfileInfo<T*> {
   typedef const T*   value_type;
   typedef value_type value_type_ref;
 
-  static inline void Profile(FoldingSetNodeID &ID, value_type_ref X) {
+  static void Profile(FoldingSetNodeID &ID, value_type_ref X) {
     ID.AddPointer(X);
   }
 };
@@ -878,18 +914,18 @@ struct ImutContainerInfo : public ImutProfileInfo<T> {
   typedef bool            data_type;
   typedef bool            data_type_ref;
 
-  static inline key_type_ref KeyOfValue(value_type_ref D) { return D; }
-  static inline data_type_ref DataOfValue(value_type_ref) { return true; }
+  static key_type_ref KeyOfValue(value_type_ref D) { return D; }
+  static data_type_ref DataOfValue(value_type_ref) { return true; }
 
-  static inline bool isEqual(key_type_ref LHS, key_type_ref RHS) {
+  static bool isEqual(key_type_ref LHS, key_type_ref RHS) {
     return std::equal_to<key_type>()(LHS,RHS);
   }
 
-  static inline bool isLess(key_type_ref LHS, key_type_ref RHS) {
+  static bool isLess(key_type_ref LHS, key_type_ref RHS) {
     return std::less<key_type>()(LHS,RHS);
   }
 
-  static inline bool isDataEqual(data_type_ref,data_type_ref) { return true; }
+  static bool isDataEqual(data_type_ref, data_type_ref) { return true; }
 };
 
 /// ImutContainerInfo - Specialization for pointer values to treat pointers
@@ -904,18 +940,14 @@ struct ImutContainerInfo<T*> : public ImutProfileInfo<T*> {
   typedef bool            data_type;
   typedef bool            data_type_ref;
 
-  static inline key_type_ref KeyOfValue(value_type_ref D) { return D; }
-  static inline data_type_ref DataOfValue(value_type_ref) { return true; }
+  static key_type_ref KeyOfValue(value_type_ref D) { return D; }
+  static data_type_ref DataOfValue(value_type_ref) { return true; }
 
-  static inline bool isEqual(key_type_ref LHS, key_type_ref RHS) {
-    return LHS == RHS;
-  }
+  static bool isEqual(key_type_ref LHS, key_type_ref RHS) { return LHS == RHS; }
 
-  static inline bool isLess(key_type_ref LHS, key_type_ref RHS) {
-    return LHS < RHS;
-  }
+  static bool isLess(key_type_ref LHS, key_type_ref RHS) { return LHS < RHS; }
 
-  static inline bool isDataEqual(data_type_ref,data_type_ref) { return true; }
+  static bool isDataEqual(data_type_ref, data_type_ref) { return true; }
 };
 
 //===----------------------------------------------------------------------===//
@@ -931,7 +963,7 @@ public:
 
 private:
   TreeTy *Root;
-  
+
 public:
   /// Constructs a set from a pointer to a tree root.  In general one
   /// should use a Factory object to create sets instead of directly
@@ -1000,10 +1032,10 @@ public:
     typename TreeTy::Factory *getTreeFactory() const {
       return const_cast<typename TreeTy::Factory *>(&F);
     }
-    
+
   private:
-    Factory(const Factory& RHS); // DO NOT IMPLEMENT
-    void operator=(const Factory& RHS); // DO NOT IMPLEMENT
+    Factory(const Factory& RHS) = delete;
+    void operator=(const Factory& RHS) = delete;
   };
 
   friend class Factory;
@@ -1021,11 +1053,11 @@ public:
     return Root && RHS.Root ? Root->isNotEqual(*RHS.Root) : Root != RHS.Root;
   }
 
-  TreeTy *getRoot() { 
+  TreeTy *getRoot() {
     if (Root) { Root->retain(); }
     return Root;
   }
-  
+
   TreeTy *getRootWithoutRetain() const {
     return Root;
   }
@@ -1047,21 +1079,7 @@ public:
   // Iterators.
   //===--------------------------------------------------===//
 
-  class iterator {
-    typename TreeTy::iterator itr;
-    iterator(TreeTy* t) : itr(t) {}
-    friend class ImmutableSet<ValT,ValInfo>;
-  public:
-    iterator() {}
-    inline value_type_ref operator*() const { return itr->getValue(); }
-    inline iterator& operator++() { ++itr; return *this; }
-    inline iterator  operator++(int) { iterator tmp(*this); ++itr; return tmp; }
-    inline iterator& operator--() { --itr; return *this; }
-    inline iterator  operator--(int) { iterator tmp(*this); --itr; return tmp; }
-    inline bool operator==(const iterator& RHS) const { return RHS.itr == itr; }
-    inline bool operator!=(const iterator& RHS) const { return RHS.itr != itr; }
-    inline value_type *operator->() const { return &(operator*()); }
-  };
+  typedef ImutAVLValueIterator<ImmutableSet> iterator;
 
   iterator begin() const { return iterator(Root); }
   iterator end() const { return iterator(); }
@@ -1072,13 +1090,11 @@ public:
 
   unsigned getHeight() const { return Root ? Root->getHeight() : 0; }
 
-  static inline void Profile(FoldingSetNodeID& ID, const ImmutableSet& S) {
+  static void Profile(FoldingSetNodeID &ID, const ImmutableSet &S) {
     ID.AddPointer(S.Root);
   }
 
-  inline void Profile(FoldingSetNodeID& ID) const {
-    return Profile(ID,*this);
-  }
+  void Profile(FoldingSetNodeID &ID) const { return Profile(ID, *this); }
 
   //===--------------------------------------------------===//
   // For testing.
@@ -1086,7 +1102,7 @@ public:
 
   void validateTree() const { if (Root) Root->validateTree(); }
 };
-  
+
 // NOTE: This may some day replace the current ImmutableSet.
 template <typename ValT, typename ValInfo = ImutContainerInfo<ValT> >
 class ImmutableSetRef {
@@ -1095,11 +1111,11 @@ public:
   typedef typename ValInfo::value_type_ref  value_type_ref;
   typedef ImutAVLTree<ValInfo> TreeTy;
   typedef typename TreeTy::Factory          FactoryTy;
-  
+
 private:
   TreeTy *Root;
   FactoryTy *Factory;
-  
+
 public:
   /// Constructs a set from a pointer to a tree root.  In general one
   /// should use a Factory object to create sets instead of directly
@@ -1127,43 +1143,44 @@ public:
   ~ImmutableSetRef() {
     if (Root) { Root->release(); }
   }
-  
-  static inline ImmutableSetRef getEmptySet(FactoryTy *F) {
+
+  static ImmutableSetRef getEmptySet(FactoryTy *F) {
     return ImmutableSetRef(0, F);
   }
-  
+
   ImmutableSetRef add(value_type_ref V) {
     return ImmutableSetRef(Factory->add(Root, V), Factory);
   }
-  
+
   ImmutableSetRef remove(value_type_ref V) {
     return ImmutableSetRef(Factory->remove(Root, V), Factory);
   }
-    
+
   /// Returns true if the set contains the specified value.
   bool contains(value_type_ref V) const {
     return Root ? Root->contains(V) : false;
   }
-  
-  ImmutableSet<ValT> asImmutableSet() const {
-    return ImmutableSet<ValT>(Factory->getCanonicalTree(Root));
+
+  ImmutableSet<ValT> asImmutableSet(bool canonicalize = true) const {
+    return ImmutableSet<ValT>(canonicalize ?
+                              Factory->getCanonicalTree(Root) : Root);
   }
-  
+
   TreeTy *getRootWithoutRetain() const {
     return Root;
   }
-  
+
   bool operator==(const ImmutableSetRef &RHS) const {
     return Root && RHS.Root ? Root->isEqual(*RHS.Root) : Root == RHS.Root;
   }
-  
+
   bool operator!=(const ImmutableSetRef &RHS) const {
     return Root && RHS.Root ? Root->isNotEqual(*RHS.Root) : Root != RHS.Root;
   }
 
   /// isEmpty - Return true if the set contains no elements.
   bool isEmpty() const { return !Root; }
-  
+
   /// isSingleton - Return true if the set contains exactly one element.
   ///   This method runs in constant time.
   bool isSingleton() const { return getHeight() == 1; }
@@ -1171,44 +1188,28 @@ public:
   //===--------------------------------------------------===//
   // Iterators.
   //===--------------------------------------------------===//
-  
-  class iterator {
-    typename TreeTy::iterator itr;
-    iterator(TreeTy* t) : itr(t) {}
-    friend class ImmutableSetRef<ValT,ValInfo>;
-  public:
-    iterator() {}
-    inline value_type_ref operator*() const { return itr->getValue(); }
-    inline iterator& operator++() { ++itr; return *this; }
-    inline iterator  operator++(int) { iterator tmp(*this); ++itr; return tmp; }
-    inline iterator& operator--() { --itr; return *this; }
-    inline iterator  operator--(int) { iterator tmp(*this); --itr; return tmp; }
-    inline bool operator==(const iterator& RHS) const { return RHS.itr == itr; }
-    inline bool operator!=(const iterator& RHS) const { return RHS.itr != itr; }
-    inline value_type *operator->() const { return &(operator*()); }
-  };
-  
+
+  typedef ImutAVLValueIterator<ImmutableSetRef> iterator;
+
   iterator begin() const { return iterator(Root); }
   iterator end() const { return iterator(); }
-  
+
   //===--------------------------------------------------===//
   // Utility methods.
   //===--------------------------------------------------===//
-  
+
   unsigned getHeight() const { return Root ? Root->getHeight() : 0; }
-  
-  static inline void Profile(FoldingSetNodeID& ID, const ImmutableSetRef& S) {
+
+  static void Profile(FoldingSetNodeID &ID, const ImmutableSetRef &S) {
     ID.AddPointer(S.Root);
   }
-  
-  inline void Profile(FoldingSetNodeID& ID) const {
-    return Profile(ID,*this);
-  }
-  
+
+  void Profile(FoldingSetNodeID &ID) const { return Profile(ID, *this); }
+
   //===--------------------------------------------------===//
   // For testing.
   //===--------------------------------------------------===//
-  
+
   void validateTree() const { if (Root) Root->validateTree(); }
 };