X-Git-Url: http://plrg.eecs.uci.edu/git/?a=blobdiff_plain;f=include%2Fllvm%2FADT%2FImmutableSet.h;h=87026f019fec93c500e7a713d5913983cd9cb4c1;hb=b1ce35cdfb58d4e93de58445aef744cded16b386;hp=53c990f7eb4cbd41aacdaf024a9656370d9f7dd1;hpb=635114fece75e011a375c0c38d527176ab1d1e01;p=oota-llvm.git

diff --git a/include/llvm/ADT/ImmutableSet.h b/include/llvm/ADT/ImmutableSet.h
index 53c990f7eb4..87026f019fe 100644
--- a/include/llvm/ADT/ImmutableSet.h
+++ b/include/llvm/ADT/ImmutableSet.h
@@ -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;
@@ -442,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;
@@ -645,24 +645,26 @@ 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> ImutAVLTreeGenericIterator;
 
   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() const {
     assert(!stack.empty());
@@ -754,13 +756,14 @@ public:
 };
 
 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> ImutAVLTreeGenericIterator;
 
   ImutAVLTreeInOrderIterator(const TreeTy* Root) : InternalItr(Root) {
     if (Root)
@@ -769,18 +772,18 @@ public:
 
   ImutAVLTreeInOrderIterator() : InternalItr() {}
 
-  bool operator==(const ImutAVLTreeGenericIterator &x) const {
+  bool operator==(const ImutAVLTreeInOrderIterator &x) const {
     return InternalItr == x.InternalItr;
   }
 
-  bool operator!=(const ImutAVLTreeGenericIterator &x) const {
+  bool operator!=(const ImutAVLTreeInOrderIterator &x) const {
     return !(*this == x);
   }
 
-  TreeTy *operator*() const { return *InternalItr; }
-  TreeTy *operator->() const { return *InternalItr; }
+  TreeTy &operator*() const { return *InternalItr; }
+  TreeTy *operator->() const { return &*InternalItr; }
 
-  ImutAVLTreeGenericIterator &operator++() {
+  ImutAVLTreeInOrderIterator &operator++() {
     do ++InternalItr;
     while (!InternalItr.atEnd() &&
            InternalItr.getVisitState() != InternalIteratorTy::VisitedLeft);
@@ -788,7 +791,7 @@ public:
     return *this;
   }
 
-  ImutAVLTreeGenericIterator &operator--() {
+  ImutAVLTreeInOrderIterator &operator--() {
     do --InternalItr;
     while (!InternalItr.atBeginning() &&
            InternalItr.getVisitState() != InternalIteratorTy::VisitedLeft);
@@ -805,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.
 //===----------------------------------------------------------------------===//
@@ -1058,31 +1079,7 @@ public:
   // Iterators.
   //===--------------------------------------------------===//
 
-  class iterator {
-    typename TreeTy::iterator itr;
-
-    iterator() {}
-    iterator(TreeTy* t) : itr(t) {}
-    friend class ImmutableSet<ValT,ValInfo>;
-
-  public:
-    typedef ptrdiff_t difference_type;
-    typedef typename ImmutableSet<ValT,ValInfo>::value_type value_type;
-    typedef typename ImmutableSet<ValT,ValInfo>::value_type_ref reference;
-    typedef typename iterator::value_type *pointer;
-    typedef std::bidirectional_iterator_tag iterator_category;
-
-    typename iterator::reference operator*() const { return itr->getValue(); }
-    typename iterator::pointer operator->() const { return &**this; }
-
-    iterator& operator++() { ++itr; return *this; }
-    iterator  operator++(int) { iterator tmp(*this); ++itr; return tmp; }
-    iterator& operator--() { --itr; return *this; }
-    iterator  operator--(int) { iterator tmp(*this); --itr; return tmp; }
-
-    bool operator==(const iterator& RHS) const { return RHS.itr == itr; }
-    bool operator!=(const iterator& RHS) const { return RHS.itr != itr; }
-  };
+  typedef ImutAVLValueIterator<ImmutableSet> iterator;
 
   iterator begin() const { return iterator(Root); }
   iterator end() const { return iterator(); }
@@ -1192,35 +1189,7 @@ public:
   // Iterators.
   //===--------------------------------------------------===//
 
-  class iterator {
-    typename TreeTy::iterator itr;
-    iterator(TreeTy* t) : itr(t) {}
-    friend class ImmutableSetRef<ValT,ValInfo>;
-  public:
-    iterator() {}
-    value_type_ref operator*() const { return itr->getValue(); }
-    iterator &operator++() {
-      ++itr;
-      return *this;
-    }
-    iterator operator++(int) {
-      iterator tmp(*this);
-      ++itr;
-      return tmp;
-    }
-    iterator &operator--() {
-      --itr;
-      return *this;
-    }
-    iterator operator--(int) {
-      iterator tmp(*this);
-      --itr;
-      return tmp;
-    }
-    bool operator==(const iterator &RHS) const { return RHS.itr == itr; }
-    bool operator!=(const iterator &RHS) const { return RHS.itr != itr; }
-    value_type *operator->() const { return &**this; }
-  };
+  typedef ImutAVLValueIterator<ImmutableSetRef> iterator;
 
   iterator begin() const { return iterator(Root); }
   iterator end() const { return iterator(); }