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    class nat;
  59    typedef typename
  60       detail::if_c< IsConst
  61                   , tree_iterator<value_traits, false>
  62                   , nat>::type                           nonconst_iterator;
  63
  64    public:
  65    typedef typename types_t::iterator_type::difference_type    difference_type;
  66    typedef typename types_t::iterator_type::value_type         value_type;
  67    typedef typename types_t::iterator_type::pointer            pointer;
  68    typedef typename types_t::iterator_type::reference          reference;
  69    typedef typename types_t::iterator_type::iterator_category  iterator_category;
  70
  71    BOOST_INTRUSIVE_FORCEINLINE tree_iterator()
  72    {}
  73
  74    BOOST_INTRUSIVE_FORCEINLINE explicit tree_iterator(const node_ptr & nodeptr, const const_value_traits_ptr &traits_ptr)
  75       : members_(nodeptr, traits_ptr)
  76    {}
  77
  78    BOOST_INTRUSIVE_FORCEINLINE tree_iterator(const tree_iterator &other)
  79       :  members_(other.pointed_node(), other.get_value_traits())
  80    {}
  81
  82    BOOST_INTRUSIVE_FORCEINLINE tree_iterator(const nonconst_iterator &other)
  83       :  members_(other.pointed_node(), other.get_value_traits())
  84    {}
  85
  86    BOOST_INTRUSIVE_FORCEINLINE tree_iterator &operator=(const tree_iterator &other)
  87    {  members_.nodeptr_ = other.members_.nodeptr_;  return *this;  }
  88
  89    BOOST_INTRUSIVE_FORCEINLINE tree_iterator &operator=(const node_ptr &nodeptr)
  90    {  members_.nodeptr_ = nodeptr;  return *this;  }
  91
  92    BOOST_INTRUSIVE_FORCEINLINE node_ptr pointed_node() const
  93    { return members_.nodeptr_; }
  94
  95    public:
  96    BOOST_INTRUSIVE_FORCEINLINE tree_iterator& operator++()
  97    {
  98       members_.nodeptr_ = node_algorithms::next_node(members_.nodeptr_);
  99       return *this;
 100    }
 101
 102    tree_iterator operator++(int)
 103    {
 104       tree_iterator result (*this);
 105       members_.nodeptr_ = node_algorithms::next_node(members_.nodeptr_);
 106       return result;
 107    }
 108
 109    BOOST_INTRUSIVE_FORCEINLINE tree_iterator& operator--()
 110    {
 111       members_.nodeptr_ = node_algorithms::prev_node(members_.nodeptr_);
 112       return *this;
 113    }
 114
 115    tree_iterator operator--(int)
 116    {
 117       tree_iterator result (*this);
 118       members_.nodeptr_ = node_algorithms::prev_node(members_.nodeptr_);
 119       return result;
 120    }
 121
 122    BOOST_INTRUSIVE_FORCEINLINE tree_iterator&  go_left()
 123    {
 124       members_.nodeptr_ = node_traits::get_left(members_.nodeptr_);
 125       return *this;
 126    }
 127
 128    BOOST_INTRUSIVE_FORCEINLINE tree_iterator&  go_right()
 129    {
 130       members_.nodeptr_ = node_traits::get_right(members_.nodeptr_);
 131       return *this;
 132    }
 133
 134    BOOST_INTRUSIVE_FORCEINLINE tree_iterator&  go_parent()
 135    {
 136       members_.nodeptr_ = node_traits::get_parent(members_.nodeptr_);
 137       return *this;
 138    }
 139
 140    BOOST_INTRUSIVE_FORCEINLINE operator unspecified_bool_type() const
 141    {  return members_.nodeptr_ ? &tree_iterator::unspecified_bool_type_func : 0;   }
 142
 143    BOOST_INTRUSIVE_FORCEINLINE bool operator! () const
 144    {  return !members_.nodeptr_;   }
 145
 146    BOOST_INTRUSIVE_FORCEINLINE friend bool operator== (const tree_iterator& l, const tree_iterator& r)
 147    { return l.pointed_node() == r.pointed_node(); }
 148
 149    BOOST_INTRUSIVE_FORCEINLINE friend bool operator!= (const tree_iterator& l, const tree_iterator& r)
 150    {  return !(l == r);   }
 151
 152    BOOST_INTRUSIVE_FORCEINLINE reference operator*() const
 153    {  return *operator->();   }
 154
 155    BOOST_INTRUSIVE_FORCEINLINE pointer operator->() const
 156    { return this->operator_arrow(detail::bool_<stateful_value_traits>()); }
 157
 158    BOOST_INTRUSIVE_FORCEINLINE const_value_traits_ptr get_value_traits() const
 159    {  return members_.get_ptr();  }
 160
 161    tree_iterator end_iterator_from_it() const
 162    {
 163       return tree_iterator(node_algorithms::get_header(this->pointed_node()), this->get_value_traits());
 164    }
 165
 166    tree_iterator<value_traits, false> unconst() const
 167    {  return tree_iterator<value_traits, false>(this->pointed_node(), this->get_value_traits());   }
 168
 169    private:
 170    BOOST_INTRUSIVE_FORCEINLINE pointer operator_arrow(detail::false_) const
 171    { return ValueTraits::to_value_ptr(members_.nodeptr_); }
 172
 173    BOOST_INTRUSIVE_FORCEINLINE pointer operator_arrow(detail::true_) const
 174    { return this->get_value_traits()->to_value_ptr(members_.nodeptr_); }
 175
 176    iiterator_members<node_ptr, const_value_traits_ptr, stateful_value_traits> members_;
 177 };
 178
 179 } //namespace intrusive
 180 } //namespace boost
 181
 182 #include <boost/intrusive/detail/config_end.hpp>
 183
 184 #endif //BOOST_INTRUSIVE_TREE_ITERATOR_HPP