]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
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 | ||
72 | BOOST_INTRUSIVE_FORCEINLINE static node_ptr get_parent(const const_node_ptr & n) | |
73 | { return n->parent_; } | |
74 | ||
75 | BOOST_INTRUSIVE_FORCEINLINE static node_ptr get_parent(const node_ptr & n) | |
76 | { return n->parent_; } | |
77 | ||
78 | BOOST_INTRUSIVE_FORCEINLINE static void set_parent(const node_ptr & n, const node_ptr & p) | |
79 | { n->parent_ = p; } | |
80 | ||
81 | BOOST_INTRUSIVE_FORCEINLINE static node_ptr get_left(const const_node_ptr & n) | |
82 | { return n->left_; } | |
83 | ||
84 | BOOST_INTRUSIVE_FORCEINLINE static node_ptr get_left(const node_ptr & n) | |
85 | { return n->left_; } | |
86 | ||
87 | BOOST_INTRUSIVE_FORCEINLINE static void set_left(const node_ptr & n, const node_ptr & l) | |
88 | { n->left_ = l; } | |
89 | ||
90 | BOOST_INTRUSIVE_FORCEINLINE static node_ptr get_right(const const_node_ptr & n) | |
91 | { return n->right_; } | |
92 | ||
93 | BOOST_INTRUSIVE_FORCEINLINE static node_ptr get_right(const node_ptr & n) | |
94 | { return n->right_; } | |
95 | ||
96 | BOOST_INTRUSIVE_FORCEINLINE static void set_right(const node_ptr & n, const node_ptr & r) | |
97 | { n->right_ = r; } | |
98 | ||
99 | BOOST_INTRUSIVE_FORCEINLINE static balance get_balance(const const_node_ptr & n) | |
100 | { return n->balance_; } | |
101 | ||
102 | BOOST_INTRUSIVE_FORCEINLINE static balance get_balance(const node_ptr & n) | |
103 | { return n->balance_; } | |
104 | ||
105 | BOOST_INTRUSIVE_FORCEINLINE static void set_balance(const 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 | |
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 | ||
130 | BOOST_INTRUSIVE_FORCEINLINE static node_ptr get_parent(const const_node_ptr & n) | |
131 | { return ptr_bit::get_pointer(n->parent_); } | |
132 | ||
133 | BOOST_INTRUSIVE_FORCEINLINE static void set_parent(const node_ptr & n, const node_ptr & p) | |
134 | { ptr_bit::set_pointer(n->parent_, p); } | |
135 | ||
136 | BOOST_INTRUSIVE_FORCEINLINE static node_ptr get_left(const const_node_ptr & n) | |
137 | { return n->left_; } | |
138 | ||
139 | BOOST_INTRUSIVE_FORCEINLINE static void set_left(const node_ptr & n, const node_ptr & l) | |
140 | { n->left_ = l; } | |
141 | ||
142 | BOOST_INTRUSIVE_FORCEINLINE static node_ptr get_right(const const_node_ptr & n) | |
143 | { return n->right_; } | |
144 | ||
145 | BOOST_INTRUSIVE_FORCEINLINE static void set_right(const node_ptr & n, const node_ptr & r) | |
146 | { n->right_ = r; } | |
147 | ||
148 | BOOST_INTRUSIVE_FORCEINLINE static balance get_balance(const const_node_ptr & n) | |
149 | { return (balance)ptr_bit::get_bits(n->parent_); } | |
150 | ||
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); } | |
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 | |
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 |