1 /////////////////////////////////////////////////////////////////////////////
3 // (C) Copyright Ion Gaztanaga 2007-2013
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)
9 // See http://www.boost.org/libs/intrusive for documentation.
11 /////////////////////////////////////////////////////////////////////////////
13 #ifndef BOOST_INTRUSIVE_AVLTREE_NODE_HPP
14 #define BOOST_INTRUSIVE_AVLTREE_NODE_HPP
16 #ifndef BOOST_CONFIG_HPP
17 # include <boost/config.hpp>
20 #if defined(BOOST_HAS_PRAGMA_ONCE)
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>
34 /////////////////////////////////////////////////////////////////////////////
36 // Generic node_traits for any pointer type //
38 /////////////////////////////////////////////////////////////////////////////
40 //This is the compact representation: 3 pointers
41 template<class VoidPointer>
42 struct compact_avltree_node
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_;
50 //This is the normal representation: 3 pointers + enum
51 template<class VoidPointer>
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_;
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
66 typedef avltree_node<VoidPointer> node;
67 typedef typename node::node_ptr node_ptr;
68 typedef typename node::const_node_ptr const_node_ptr;
70 typedef typename node::balance balance;
72 BOOST_INTRUSIVE_FORCEINLINE static node_ptr get_parent(const const_node_ptr & n)
73 { return n->parent_; }
75 BOOST_INTRUSIVE_FORCEINLINE static node_ptr get_parent(const node_ptr & n)
76 { return n->parent_; }
78 BOOST_INTRUSIVE_FORCEINLINE static void set_parent(const node_ptr & n, const node_ptr & p)
81 BOOST_INTRUSIVE_FORCEINLINE static node_ptr get_left(const const_node_ptr & n)
84 BOOST_INTRUSIVE_FORCEINLINE static node_ptr get_left(const node_ptr & n)
87 BOOST_INTRUSIVE_FORCEINLINE static void set_left(const node_ptr & n, const node_ptr & l)
90 BOOST_INTRUSIVE_FORCEINLINE static node_ptr get_right(const const_node_ptr & n)
93 BOOST_INTRUSIVE_FORCEINLINE static node_ptr get_right(const node_ptr & n)
96 BOOST_INTRUSIVE_FORCEINLINE static void set_right(const node_ptr & n, const node_ptr & r)
99 BOOST_INTRUSIVE_FORCEINLINE static balance get_balance(const const_node_ptr & n)
100 { return n->balance_; }
102 BOOST_INTRUSIVE_FORCEINLINE static balance get_balance(const node_ptr & n)
103 { return n->balance_; }
105 BOOST_INTRUSIVE_FORCEINLINE static void set_balance(const node_ptr & n, balance b)
108 BOOST_INTRUSIVE_FORCEINLINE static balance negative()
109 { return node::negative_t; }
111 BOOST_INTRUSIVE_FORCEINLINE static balance zero()
112 { return node::zero_t; }
114 BOOST_INTRUSIVE_FORCEINLINE static balance positive()
115 { return node::positive_t; }
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
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;
128 typedef pointer_plus_bits<node_ptr, 2> ptr_bit;
130 BOOST_INTRUSIVE_FORCEINLINE static node_ptr get_parent(const const_node_ptr & n)
131 { return ptr_bit::get_pointer(n->parent_); }
133 BOOST_INTRUSIVE_FORCEINLINE static void set_parent(const node_ptr & n, const node_ptr & p)
134 { ptr_bit::set_pointer(n->parent_, p); }
136 BOOST_INTRUSIVE_FORCEINLINE static node_ptr get_left(const const_node_ptr & n)
139 BOOST_INTRUSIVE_FORCEINLINE static void set_left(const node_ptr & n, const node_ptr & l)
142 BOOST_INTRUSIVE_FORCEINLINE static node_ptr get_right(const const_node_ptr & n)
143 { return n->right_; }
145 BOOST_INTRUSIVE_FORCEINLINE static void set_right(const node_ptr & n, const node_ptr & r)
148 BOOST_INTRUSIVE_FORCEINLINE static balance get_balance(const const_node_ptr & n)
149 { return (balance)ptr_bit::get_bits(n->parent_); }
151 BOOST_INTRUSIVE_FORCEINLINE static void set_balance(const node_ptr & n, balance b)
152 { ptr_bit::set_bits(n->parent_, (std::size_t)b); }
154 BOOST_INTRUSIVE_FORCEINLINE static balance negative()
155 { return node::negative_t; }
157 BOOST_INTRUSIVE_FORCEINLINE static balance zero()
158 { return node::zero_t; }
160 BOOST_INTRUSIVE_FORCEINLINE static balance positive()
161 { return node::positive_t; }
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>
170 template<class VoidPointer>
171 struct avltree_node_traits_dispatch<VoidPointer, true>
172 : public compact_avltree_node_traits_impl<VoidPointer>
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
181 max_pointer_plus_bits
183 , detail::alignment_of<compact_avltree_node<VoidPointer> >::value
188 } //namespace intrusive
191 #include <boost/intrusive/detail/config_end.hpp>
193 #endif //BOOST_INTRUSIVE_AVLTREE_NODE_HPP