/usr/include/boost/intrusive/detail/tree_node.hpp is in libboost1.55-dev 1.55.0+dfsg-3.
This file is owned by root:root, with mode 0o644.
The actual contents of the file can be viewed below.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 | /////////////////////////////////////////////////////////////////////////////
//
// (C) Copyright Ion Gaztanaga 2007-2013
//
// Distributed under the Boost Software License, Version 1.0.
// (See accompanying file LICENSE_1_0.txt or copy at
// http://www.boost.org/LICENSE_1_0.txt)
//
// See http://www.boost.org/libs/intrusive for documentation.
//
/////////////////////////////////////////////////////////////////////////////
#ifndef BOOST_INTRUSIVE_TREE_NODE_HPP
#define BOOST_INTRUSIVE_TREE_NODE_HPP
#include <boost/intrusive/detail/config_begin.hpp>
#include <iterator>
#include <boost/intrusive/detail/utilities.hpp>
#include <boost/intrusive/options.hpp>
#include <boost/intrusive/pointer_traits.hpp>
#include <boost/intrusive/detail/mpl.hpp>
#include <boost/intrusive/bstree_algorithms.hpp>
namespace boost {
namespace intrusive {
template<class VoidPointer>
struct tree_node
{
typedef typename pointer_traits
<VoidPointer>::template rebind_pointer
<tree_node<VoidPointer> >::type node_ptr;
node_ptr parent_, left_, right_;
};
template<class VoidPointer>
struct tree_node_traits
{
typedef tree_node<VoidPointer> node;
typedef typename pointer_traits<VoidPointer>::template
rebind_pointer<node>::type node_ptr;
typedef typename pointer_traits<VoidPointer>::template
rebind_pointer<const node>::type const_node_ptr;
static node_ptr get_parent(const const_node_ptr & n)
{ return n->parent_; }
static node_ptr get_parent(const node_ptr & n)
{ return n->parent_; }
static void set_parent(const node_ptr & n, const node_ptr & p)
{ n->parent_ = p; }
static node_ptr get_left(const const_node_ptr & n)
{ return n->left_; }
static node_ptr get_left(const node_ptr & n)
{ return n->left_; }
static void set_left(const node_ptr & n, const node_ptr & l)
{ n->left_ = l; }
static node_ptr get_right(const const_node_ptr & n)
{ return n->right_; }
static node_ptr get_right(const node_ptr & n)
{ return n->right_; }
static void set_right(const node_ptr & n, const node_ptr & r)
{ n->right_ = r; }
};
/////////////////////////////////////////////////////////////////////////////
// //
// Implementation of the tree iterator //
// //
/////////////////////////////////////////////////////////////////////////////
// tree_iterator provides some basic functions for a
// node oriented bidirectional iterator:
template<class RealValueTraits, bool IsConst>
class tree_iterator
: public iiterator<RealValueTraits, IsConst, std::bidirectional_iterator_tag>::iterator_base
{
protected:
typedef iiterator< RealValueTraits, IsConst
, std::bidirectional_iterator_tag> types_t;
typedef RealValueTraits real_value_traits;
typedef typename types_t::node_traits node_traits;
typedef typename types_t::node node;
typedef typename types_t::node_ptr node_ptr;
typedef typename types_t::void_pointer void_pointer;
static const bool stateful_value_traits = types_t::stateful_value_traits;
typedef typename pointer_traits
<void_pointer>::template rebind_pointer
<const real_value_traits>::type const_real_value_traits_ptr;
public:
typedef typename types_t::value_type value_type;
typedef typename types_t::pointer pointer;
typedef typename types_t::reference reference;
typedef bstree_algorithms<node_traits> node_algorithms;
tree_iterator()
{}
explicit tree_iterator(const node_ptr & nodeptr, const const_real_value_traits_ptr &traits_ptr)
: members_(nodeptr, traits_ptr)
{}
tree_iterator(tree_iterator<real_value_traits, false> const& other)
: members_(other.pointed_node(), other.get_real_value_traits())
{}
const node_ptr &pointed_node() const
{ return members_.nodeptr_; }
tree_iterator &operator=(const node_ptr &nodeptr)
{ members_.nodeptr_ = nodeptr; return static_cast<tree_iterator&>(*this); }
public:
tree_iterator& operator++()
{
members_.nodeptr_ = node_algorithms::next_node(members_.nodeptr_);
return static_cast<tree_iterator&> (*this);
}
tree_iterator operator++(int)
{
tree_iterator result (*this);
members_.nodeptr_ = node_algorithms::next_node(members_.nodeptr_);
return result;
}
tree_iterator& operator--()
{
members_.nodeptr_ = node_algorithms::prev_node(members_.nodeptr_);
return static_cast<tree_iterator&> (*this);
}
tree_iterator operator--(int)
{
tree_iterator result (*this);
members_.nodeptr_ = node_algorithms::prev_node(members_.nodeptr_);
return result;
}
friend bool operator== (const tree_iterator& l, const tree_iterator& r)
{ return l.pointed_node() == r.pointed_node(); }
friend bool operator!= (const tree_iterator& l, const tree_iterator& r)
{ return !(l == r); }
reference operator*() const
{ return *operator->(); }
pointer operator->() const
{ return this->get_real_value_traits()->to_value_ptr(members_.nodeptr_); }
const_real_value_traits_ptr get_real_value_traits() const
{
return pointer_traits<const_real_value_traits_ptr>::static_cast_from(members_.get_ptr());
}
tree_iterator end_iterator_from_it() const
{
return tree_iterator(node_algorithms::get_header(this->pointed_node()), this->get_real_value_traits());
}
tree_iterator<real_value_traits, false> unconst() const
{ return tree_iterator<real_value_traits, false>(this->pointed_node(), this->get_real_value_traits()); }
private:
iiterator_members<node_ptr, stateful_value_traits> members_;
};
} //namespace intrusive
} //namespace boost
#include <boost/intrusive/detail/config_end.hpp>
#endif //BOOST_INTRUSIVE_TREE_NODE_HPP
|