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_AVLTREE_NODE_HPP
14 #define BOOST_INTRUSIVE_AVLTREE_NODE_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/pointer_rebind.hpp>
27 #include <boost/intrusive/avltree_algorithms.hpp>
28 #include <boost/intrusive/pointer_plus_bits.hpp>
29 #include <boost/intrusive/detail/mpl.hpp>
30 
31 namespace boost {
32 namespace intrusive {
33 
34 /////////////////////////////////////////////////////////////////////////////
35 //                                                                         //
36 //                Generic node_traits for any pointer type                 //
37 //                                                                         //
38 /////////////////////////////////////////////////////////////////////////////
39 
40 //This is the compact representation: 3 pointers
41 template<class VoidPointer>
42 struct compact_avltree_node
43 {
44    typedef typename pointer_rebind<VoidPointer, compact_avltree_node<VoidPointer> >::type       node_ptr;
45    typedef typename pointer_rebind<VoidPointer, const compact_avltree_node<VoidPointer> >::type const_node_ptr;
46    enum balance { negative_t, zero_t, positive_t };
47    node_ptr parent_, left_, right_;
48 };
49 
50 //This is the normal representation: 3 pointers + enum
51 template<class VoidPointer>
52 struct avltree_node
53 {
54    typedef typename pointer_rebind<VoidPointer, avltree_node<VoidPointer> >::type         node_ptr;
55    typedef typename pointer_rebind<VoidPointer, const avltree_node<VoidPointer> >::type   const_node_ptr;
56    enum balance { negative_t, zero_t, positive_t };
57    node_ptr parent_, left_, right_;
58    balance balance_;
59 };
60 
61 //This is the default node traits implementation
62 //using a node with 3 generic pointers plus an enum
63 template<class VoidPointer>
64 struct default_avltree_node_traits_impl
65 {
66    typedef avltree_node<VoidPointer>      node;
67    typedef typename node::node_ptr        node_ptr;
68    typedef typename node::const_node_ptr  const_node_ptr;
69 
70    typedef typename node::balance balance;
71 
get_parentboost::intrusive::default_avltree_node_traits_impl72    BOOST_INTRUSIVE_FORCEINLINE static node_ptr get_parent(const const_node_ptr & n)
73    {  return n->parent_;  }
74 
get_parentboost::intrusive::default_avltree_node_traits_impl75    BOOST_INTRUSIVE_FORCEINLINE static node_ptr get_parent(const node_ptr & n)
76    {  return n->parent_;  }
77 
set_parentboost::intrusive::default_avltree_node_traits_impl78    BOOST_INTRUSIVE_FORCEINLINE static void set_parent(node_ptr n, node_ptr p)
79    {  n->parent_ = p;  }
80 
get_leftboost::intrusive::default_avltree_node_traits_impl81    BOOST_INTRUSIVE_FORCEINLINE static node_ptr get_left(const const_node_ptr & n)
82    {  return n->left_;  }
83 
get_leftboost::intrusive::default_avltree_node_traits_impl84    BOOST_INTRUSIVE_FORCEINLINE static node_ptr get_left(const node_ptr & n)
85    {  return n->left_;  }
86 
set_leftboost::intrusive::default_avltree_node_traits_impl87    BOOST_INTRUSIVE_FORCEINLINE static void set_left(node_ptr n, node_ptr l)
88    {  n->left_ = l;  }
89 
get_rightboost::intrusive::default_avltree_node_traits_impl90    BOOST_INTRUSIVE_FORCEINLINE static node_ptr get_right(const const_node_ptr & n)
91    {  return n->right_;  }
92 
get_rightboost::intrusive::default_avltree_node_traits_impl93    BOOST_INTRUSIVE_FORCEINLINE static node_ptr get_right(const node_ptr & n)
94    {  return n->right_;  }
95 
set_rightboost::intrusive::default_avltree_node_traits_impl96    BOOST_INTRUSIVE_FORCEINLINE static void set_right(node_ptr n, node_ptr r)
97    {  n->right_ = r;  }
98 
get_balanceboost::intrusive::default_avltree_node_traits_impl99    BOOST_INTRUSIVE_FORCEINLINE static balance get_balance(const const_node_ptr & n)
100    {  return n->balance_;  }
101 
get_balanceboost::intrusive::default_avltree_node_traits_impl102    BOOST_INTRUSIVE_FORCEINLINE static balance get_balance(const node_ptr & n)
103    {  return n->balance_;  }
104 
set_balanceboost::intrusive::default_avltree_node_traits_impl105    BOOST_INTRUSIVE_FORCEINLINE static void set_balance(const node_ptr & n, balance b)
106    {  n->balance_ = b;  }
107 
negativeboost::intrusive::default_avltree_node_traits_impl108    BOOST_INTRUSIVE_FORCEINLINE static balance negative()
109    {  return node::negative_t;  }
110 
zeroboost::intrusive::default_avltree_node_traits_impl111    BOOST_INTRUSIVE_FORCEINLINE static balance zero()
112    {  return node::zero_t;  }
113 
positiveboost::intrusive::default_avltree_node_traits_impl114    BOOST_INTRUSIVE_FORCEINLINE static balance positive()
115    {  return node::positive_t;  }
116 };
117 
118 //This is the compact node traits implementation
119 //using a node with 3 generic pointers
120 template<class VoidPointer>
121 struct compact_avltree_node_traits_impl
122 {
123    typedef compact_avltree_node<VoidPointer> node;
124    typedef typename node::node_ptr           node_ptr;
125    typedef typename node::const_node_ptr     const_node_ptr;
126    typedef typename node::balance balance;
127 
128    typedef pointer_plus_bits<node_ptr, 2> ptr_bit;
129 
get_parentboost::intrusive::compact_avltree_node_traits_impl130    BOOST_INTRUSIVE_FORCEINLINE static node_ptr get_parent(const const_node_ptr & n)
131    {  return ptr_bit::get_pointer(n->parent_);  }
132 
set_parentboost::intrusive::compact_avltree_node_traits_impl133    BOOST_INTRUSIVE_FORCEINLINE static void set_parent(node_ptr n, node_ptr p)
134    {  ptr_bit::set_pointer(n->parent_, p);  }
135 
get_leftboost::intrusive::compact_avltree_node_traits_impl136    BOOST_INTRUSIVE_FORCEINLINE static node_ptr get_left(const const_node_ptr & n)
137    {  return n->left_;  }
138 
set_leftboost::intrusive::compact_avltree_node_traits_impl139    BOOST_INTRUSIVE_FORCEINLINE static void set_left(node_ptr n, node_ptr l)
140    {  n->left_ = l;  }
141 
get_rightboost::intrusive::compact_avltree_node_traits_impl142    BOOST_INTRUSIVE_FORCEINLINE static node_ptr get_right(const const_node_ptr & n)
143    {  return n->right_;  }
144 
set_rightboost::intrusive::compact_avltree_node_traits_impl145    BOOST_INTRUSIVE_FORCEINLINE static void set_right(node_ptr n, node_ptr r)
146    {  n->right_ = r;  }
147 
get_balanceboost::intrusive::compact_avltree_node_traits_impl148    BOOST_INTRUSIVE_FORCEINLINE static balance get_balance(const const_node_ptr & n)
149    {  return (balance)ptr_bit::get_bits(n->parent_);  }
150 
set_balanceboost::intrusive::compact_avltree_node_traits_impl151    BOOST_INTRUSIVE_FORCEINLINE static void set_balance(const node_ptr & n, balance b)
152    {  ptr_bit::set_bits(n->parent_, (std::size_t)b);  }
153 
negativeboost::intrusive::compact_avltree_node_traits_impl154    BOOST_INTRUSIVE_FORCEINLINE static balance negative()
155    {  return node::negative_t;  }
156 
zeroboost::intrusive::compact_avltree_node_traits_impl157    BOOST_INTRUSIVE_FORCEINLINE static balance zero()
158    {  return node::zero_t;  }
159 
positiveboost::intrusive::compact_avltree_node_traits_impl160    BOOST_INTRUSIVE_FORCEINLINE static balance positive()
161    {  return node::positive_t;  }
162 };
163 
164 //Dispatches the implementation based on the boolean
165 template<class VoidPointer, bool Compact>
166 struct avltree_node_traits_dispatch
167    :  public default_avltree_node_traits_impl<VoidPointer>
168 {};
169 
170 template<class VoidPointer>
171 struct avltree_node_traits_dispatch<VoidPointer, true>
172    :  public compact_avltree_node_traits_impl<VoidPointer>
173 {};
174 
175 //Inherit from rbtree_node_traits_dispatch depending on the embedding capabilities
176 template<class VoidPointer, bool OptimizeSize = false>
177 struct avltree_node_traits
178    :  public avltree_node_traits_dispatch
179          < VoidPointer
180          , OptimizeSize &&
181             max_pointer_plus_bits
182             < VoidPointer
183             , detail::alignment_of<compact_avltree_node<VoidPointer> >::value
184             >::value >= 2u
185          >
186 {};
187 
188 } //namespace intrusive
189 } //namespace boost
190 
191 #include <boost/intrusive/detail/config_end.hpp>
192 
193 #endif //BOOST_INTRUSIVE_AVLTREE_NODE_HPP
194