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
31namespace boost {
32namespace intrusive {
33
34/////////////////////////////////////////////////////////////////////////////
35// //
36// Generic node_traits for any pointer type //
37// //
38/////////////////////////////////////////////////////////////////////////////
39
40//This is the compact representation: 3 pointers
41template<class VoidPointer>
42struct 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
51template<class VoidPointer>
52struct 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
63template<class VoidPointer>
64struct 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
72 BOOST_INTRUSIVE_FORCEINLINE static node_ptr get_parent(const_node_ptr n)
73 { return n->parent_; }
74
75 BOOST_INTRUSIVE_FORCEINLINE static node_ptr get_parent(node_ptr n)
76 { return n->parent_; }
77
78 BOOST_INTRUSIVE_FORCEINLINE static void set_parent(node_ptr n, node_ptr p)
79 { n->parent_ = p; }
80
81 BOOST_INTRUSIVE_FORCEINLINE static node_ptr get_left(const_node_ptr n)
82 { return n->left_; }
83
84 BOOST_INTRUSIVE_FORCEINLINE static node_ptr get_left(node_ptr n)
85 { return n->left_; }
86
87 BOOST_INTRUSIVE_FORCEINLINE static void set_left(node_ptr n, node_ptr l)
88 { n->left_ = l; }
89
90 BOOST_INTRUSIVE_FORCEINLINE static node_ptr get_right(const_node_ptr n)
91 { return n->right_; }
92
93 BOOST_INTRUSIVE_FORCEINLINE static node_ptr get_right(node_ptr n)
94 { return n->right_; }
95
96 BOOST_INTRUSIVE_FORCEINLINE static void set_right(node_ptr n, node_ptr r)
97 { n->right_ = r; }
98
99 BOOST_INTRUSIVE_FORCEINLINE static balance get_balance(const_node_ptr n)
100 { return n->balance_; }
101
102 BOOST_INTRUSIVE_FORCEINLINE static balance get_balance(node_ptr n)
103 { return n->balance_; }
104
105 BOOST_INTRUSIVE_FORCEINLINE static void set_balance(node_ptr n, balance b)
106 { n->balance_ = b; }
107
108 BOOST_INTRUSIVE_FORCEINLINE static balance negative()
109 { return node::negative_t; }
110
111 BOOST_INTRUSIVE_FORCEINLINE static balance zero()
112 { return node::zero_t; }
113
114 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
120template<class VoidPointer>
121struct 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
130 BOOST_INTRUSIVE_FORCEINLINE static node_ptr get_parent(const_node_ptr n)
131 { return ptr_bit::get_pointer(n->parent_); }
132
133 BOOST_INTRUSIVE_FORCEINLINE static void set_parent(node_ptr n, node_ptr p)
134 { ptr_bit::set_pointer(n->parent_, p); }
135
136 BOOST_INTRUSIVE_FORCEINLINE static node_ptr get_left(const_node_ptr n)
137 { return n->left_; }
138
139 BOOST_INTRUSIVE_FORCEINLINE static void set_left(node_ptr n, node_ptr l)
140 { n->left_ = l; }
141
142 BOOST_INTRUSIVE_FORCEINLINE static node_ptr get_right(const_node_ptr n)
143 { return n->right_; }
144
145 BOOST_INTRUSIVE_FORCEINLINE static void set_right(node_ptr n, node_ptr r)
146 { n->right_ = r; }
147
148 BOOST_INTRUSIVE_FORCEINLINE static balance get_balance(const_node_ptr n)
149 { return (balance)ptr_bit::get_bits(n->parent_); }
150
151 BOOST_INTRUSIVE_FORCEINLINE static void set_balance(node_ptr n, balance b)
152 { ptr_bit::set_bits(n->parent_, (std::size_t)b); }
153
154 BOOST_INTRUSIVE_FORCEINLINE static balance negative()
155 { return node::negative_t; }
156
157 BOOST_INTRUSIVE_FORCEINLINE static balance zero()
158 { return node::zero_t; }
159
160 BOOST_INTRUSIVE_FORCEINLINE static balance positive()
161 { return node::positive_t; }
162};
163
164//Dispatches the implementation based on the boolean
165template<class VoidPointer, bool Compact>
166struct avltree_node_traits_dispatch
167 : public default_avltree_node_traits_impl<VoidPointer>
168{};
169
170template<class VoidPointer>
171struct 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
176template<class VoidPointer, bool OptimizeSize = false>
177struct 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

source code of boost/libs/intrusive/include/boost/intrusive/detail/avltree_node.hpp