ceph/src/boost/boost/intrusive/detail/tree_iterator.hpp

   1 /////////////////////////////////////////////////////////////////////////////
   2 //
   3 // (C) Copyright Ion Gaztanaga  2007-2013
   4 //
   5 // Distributed under the Boost Software License, Version 1.0.
   6 //    (See accompanying file LICENSE_1_0.txt or copy at
   7 //          http://www.boost.org/LICENSE_1_0.txt)
   8 //
   9 // See http://www.boost.org/libs/intrusive for documentation.
  10 //
  11 /////////////////////////////////////////////////////////////////////////////
  12
  13 #ifndef BOOST_INTRUSIVE_TREE_ITERATOR_HPP
  14 #define BOOST_INTRUSIVE_TREE_ITERATOR_HPP
  15
  16 #ifndef BOOST_CONFIG_HPP
  17 #  include <boost/config.hpp>
  18 #endif
  19
  20 #if defined(BOOST_HAS_PRAGMA_ONCE)
  21 #  pragma once
  22 #endif
  23
  24 #include <boost/intrusive/detail/config_begin.hpp>
  25 #include <boost/intrusive/detail/workaround.hpp>
  26 #include <boost/intrusive/detail/std_fwd.hpp>
  27 #include <boost/intrusive/detail/iiterator.hpp>
  28 #include <boost/intrusive/detail/bstree_algorithms_base.hpp>
  29
  30 namespace boost {
  31 namespace intrusive {
  32
  33 /////////////////////////////////////////////////////////////////////////////
  34 //                                                                         //
  35 //                   Implementation of the tree iterator                   //
  36 //                                                                         //
  37 /////////////////////////////////////////////////////////////////////////////
  38
  39 // tree_iterator provides some basic functions for a
  40 // node oriented bidirectional iterator:
  41 template<class ValueTraits, bool IsConst>
  42 class tree_iterator
  43 {
  44    private:
  45    typedef iiterator< ValueTraits, IsConst
  46                     , std::bidirectional_iterator_tag>   types_t;
  47    typedef typename types_t::value_traits                value_traits;
  48    typedef typename types_t::node_traits                 node_traits;
  49    typedef typename types_t::node                        node;
  50    typedef typename types_t::node_ptr                    node_ptr;
  51    typedef typename types_t::const_value_traits_ptr      const_value_traits_ptr;
  52    typedef bstree_algorithms_base<node_traits>           node_algorithms;
  53
  54    static const bool stateful_value_traits = types_t::stateful_value_traits;
  55
  56    void unspecified_bool_type_func() const {}
  57    typedef void (tree_iterator::*unspecified_bool_type)() const;
  58
  59    public:
  60    typedef typename types_t::iterator_type::difference_type    difference_type;
  61    typedef typename types_t::iterator_type::value_type         value_type;
  62    typedef typename types_t::iterator_type::pointer            pointer;
  63    typedef typename types_t::iterator_type::reference          reference;
  64    typedef typename types_t::iterator_type::iterator_category  iterator_category;
  65
  66    BOOST_INTRUSIVE_FORCEINLINE tree_iterator()
  67    {}
  68
  69    BOOST_INTRUSIVE_FORCEINLINE explicit tree_iterator(const node_ptr & nodeptr, const const_value_traits_ptr &traits_ptr)
  70       : members_(nodeptr, traits_ptr)
  71    {}
  72
  73    BOOST_INTRUSIVE_FORCEINLINE tree_iterator(tree_iterator<value_traits, false> const& other)
  74       :  members_(other.pointed_node(), other.get_value_traits())
  75    {}
  76
  77    BOOST_INTRUSIVE_FORCEINLINE const node_ptr &pointed_node() const
  78    { return members_.nodeptr_; }
  79
  80    BOOST_INTRUSIVE_FORCEINLINE tree_iterator &operator=(const node_ptr &nodeptr)
  81    {  members_.nodeptr_ = nodeptr;  return static_cast<tree_iterator&>(*this);  }
  82
  83    public:
  84    tree_iterator& operator++()
  85    {
  86       members_.nodeptr_ = node_algorithms::next_node(members_.nodeptr_);
  87       return static_cast<tree_iterator&> (*this);
  88    }
  89
  90    tree_iterator operator++(int)
  91    {
  92       tree_iterator result (*this);
  93       members_.nodeptr_ = node_algorithms::next_node(members_.nodeptr_);
  94       return result;
  95    }
  96
  97    tree_iterator& operator--()
  98    {
  99       members_.nodeptr_ = node_algorithms::prev_node(members_.nodeptr_);
 100       return static_cast<tree_iterator&> (*this);
 101    }
 102
 103    tree_iterator operator--(int)
 104    {
 105       tree_iterator result (*this);
 106       members_.nodeptr_ = node_algorithms::prev_node(members_.nodeptr_);
 107       return result;
 108    }
 109
 110    BOOST_INTRUSIVE_FORCEINLINE tree_iterator&  go_left()
 111    {
 112       members_.nodeptr_ = node_traits::get_left(members_.nodeptr_);
 113       return static_cast<tree_iterator&> (*this);
 114    }
 115
 116    BOOST_INTRUSIVE_FORCEINLINE tree_iterator&  go_right()
 117    {
 118       members_.nodeptr_ = node_traits::get_right(members_.nodeptr_);
 119       return static_cast<tree_iterator&> (*this);
 120    }
 121
 122    BOOST_INTRUSIVE_FORCEINLINE tree_iterator&  go_parent()
 123    {
 124       members_.nodeptr_ = node_traits::get_parent(members_.nodeptr_);
 125       return static_cast<tree_iterator&> (*this);
 126    }
 127
 128    BOOST_INTRUSIVE_FORCEINLINE operator unspecified_bool_type() const
 129    {  return members_.nodeptr_ ? &tree_iterator::unspecified_bool_type_func : 0;   }
 130
 131    BOOST_INTRUSIVE_FORCEINLINE bool operator! () const
 132    {  return !members_.nodeptr_;   }
 133
 134    BOOST_INTRUSIVE_FORCEINLINE friend bool operator== (const tree_iterator& l, const tree_iterator& r)
 135    { return l.pointed_node() == r.pointed_node(); }
 136
 137    BOOST_INTRUSIVE_FORCEINLINE friend bool operator!= (const tree_iterator& l, const tree_iterator& r)
 138    {  return !(l == r);   }
 139
 140    BOOST_INTRUSIVE_FORCEINLINE reference operator*() const
 141    {  return *operator->();   }
 142
 143    BOOST_INTRUSIVE_FORCEINLINE pointer operator->() const
 144    { return this->operator_arrow(detail::bool_<stateful_value_traits>()); }
 145
 146    BOOST_INTRUSIVE_FORCEINLINE const_value_traits_ptr get_value_traits() const
 147    {  return members_.get_ptr();  }
 148
 149    tree_iterator end_iterator_from_it() const
 150    {
 151       return tree_iterator(node_algorithms::get_header(this->pointed_node()), this->get_value_traits());
 152    }
 153
 154    tree_iterator<value_traits, false> unconst() const
 155    {  return tree_iterator<value_traits, false>(this->pointed_node(), this->get_value_traits());   }
 156
 157    private:
 158    BOOST_INTRUSIVE_FORCEINLINE pointer operator_arrow(detail::false_) const
 159    { return ValueTraits::to_value_ptr(members_.nodeptr_); }
 160
 161    BOOST_INTRUSIVE_FORCEINLINE pointer operator_arrow(detail::true_) const
 162    { return this->get_value_traits()->to_value_ptr(members_.nodeptr_); }
 163
 164    iiterator_members<node_ptr, const_value_traits_ptr, stateful_value_traits> members_;
 165 };
 166
 167 } //namespace intrusive
 168 } //namespace boost
 169
 170 #include <boost/intrusive/detail/config_end.hpp>
 171
 172 #endif //BOOST_INTRUSIVE_TREE_ITERATOR_HPP