]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
1 | ///////////////////////////////////////////////////////////////////////////// |
2 | // | |
3 | // (C) Copyright Olaf Krzikalla 2004-2006. | |
4 | // (C) Copyright Ion Gaztanaga 2006-2014. | |
5 | // | |
6 | // Distributed under the Boost Software License, Version 1.0. | |
7 | // (See accompanying file LICENSE_1_0.txt or copy at | |
8 | // http://www.boost.org/LICENSE_1_0.txt) | |
9 | // | |
10 | // See http://www.boost.org/libs/intrusive for documentation. | |
11 | // | |
12 | ///////////////////////////////////////////////////////////////////////////// | |
13 | // | |
14 | // The tree destruction algorithm is based on Julienne Walker and The EC Team code: | |
15 | // | |
16 | // This code is in the public domain. Anyone may use it or change it in any way that | |
17 | // they see fit. The author assumes no responsibility for damages incurred through | |
18 | // use of the original code or any variations thereof. | |
19 | // | |
20 | // It is requested, but not required, that due credit is given to the original author | |
21 | // and anyone who has modified the code through a header comment, such as this one. | |
22 | ||
23 | #ifndef BOOST_INTRUSIVE_RBTREE_ALGORITHMS_HPP | |
24 | #define BOOST_INTRUSIVE_RBTREE_ALGORITHMS_HPP | |
25 | ||
26 | #include <boost/intrusive/detail/config_begin.hpp> | |
27 | #include <boost/intrusive/intrusive_fwd.hpp> | |
28 | ||
29 | #include <cstddef> | |
30 | ||
31 | #include <boost/intrusive/detail/assert.hpp> | |
32 | #include <boost/intrusive/detail/algo_type.hpp> | |
33 | #include <boost/intrusive/bstree_algorithms.hpp> | |
34 | #include <boost/intrusive/detail/ebo_functor_holder.hpp> | |
35 | ||
36 | #if defined(BOOST_HAS_PRAGMA_ONCE) | |
37 | # pragma once | |
38 | #endif | |
39 | ||
40 | namespace boost { | |
41 | namespace intrusive { | |
42 | ||
43 | #ifndef BOOST_INTRUSIVE_DOXYGEN_INVOKED | |
44 | ||
45 | template<class NodeTraits, class F> | |
46 | struct rbtree_node_cloner | |
47 | //Use public inheritance to avoid MSVC bugs with closures | |
48 | : public detail::ebo_functor_holder<F> | |
49 | { | |
50 | typedef typename NodeTraits::node_ptr node_ptr; | |
51 | typedef detail::ebo_functor_holder<F> base_t; | |
52 | ||
53 | explicit rbtree_node_cloner(F f) | |
54 | : base_t(f) | |
55 | {} | |
56 | ||
92f5a8d4 | 57 | BOOST_INTRUSIVE_FORCEINLINE node_ptr operator()(node_ptr p) |
7c673cae FG |
58 | { |
59 | node_ptr n = base_t::get()(p); | |
60 | NodeTraits::set_color(n, NodeTraits::get_color(p)); | |
61 | return n; | |
62 | } | |
63 | }; | |
64 | ||
65 | namespace detail { | |
66 | ||
67 | template<class ValueTraits, class NodePtrCompare, class ExtraChecker> | |
68 | struct rbtree_node_checker | |
69 | : public bstree_node_checker<ValueTraits, NodePtrCompare, ExtraChecker> | |
70 | { | |
71 | typedef bstree_node_checker<ValueTraits, NodePtrCompare, ExtraChecker> base_checker_t; | |
72 | typedef ValueTraits value_traits; | |
73 | typedef typename value_traits::node_traits node_traits; | |
74 | typedef typename node_traits::const_node_ptr const_node_ptr; | |
75 | typedef typename node_traits::node_ptr node_ptr; | |
76 | ||
77 | struct return_type | |
78 | : public base_checker_t::return_type | |
79 | { | |
80 | return_type() : black_count_(0) {} | |
81 | std::size_t black_count_; | |
82 | }; | |
83 | ||
84 | rbtree_node_checker(const NodePtrCompare& comp, ExtraChecker extra_checker) | |
85 | : base_checker_t(comp, extra_checker) | |
86 | {} | |
87 | ||
88 | void operator () (const const_node_ptr& p, | |
89 | const return_type& check_return_left, const return_type& check_return_right, | |
90 | return_type& check_return) | |
91 | { | |
92 | ||
93 | if (node_traits::get_color(p) == node_traits::red()){ | |
94 | //Red nodes have black children | |
95 | const node_ptr p_left(node_traits::get_left(p)); (void)p_left; | |
96 | const node_ptr p_right(node_traits::get_right(p)); (void)p_right; | |
97 | BOOST_INTRUSIVE_INVARIANT_ASSERT(!p_left || node_traits::get_color(p_left) == node_traits::black()); | |
98 | BOOST_INTRUSIVE_INVARIANT_ASSERT(!p_right || node_traits::get_color(p_right) == node_traits::black()); | |
99 | //Red node can't be root | |
100 | BOOST_INTRUSIVE_INVARIANT_ASSERT(node_traits::get_parent(node_traits::get_parent(p)) != p); | |
101 | } | |
102 | //Every path to p contains the same number of black nodes | |
103 | const std::size_t l_black_count = check_return_left.black_count_; | |
104 | BOOST_INTRUSIVE_INVARIANT_ASSERT(l_black_count == check_return_right.black_count_); | |
105 | check_return.black_count_ = l_black_count + | |
106 | static_cast<std::size_t>(node_traits::get_color(p) == node_traits::black()); | |
107 | base_checker_t::operator()(p, check_return_left, check_return_right, check_return); | |
108 | } | |
109 | }; | |
110 | ||
111 | } // namespace detail | |
112 | ||
113 | #endif //#ifndef BOOST_INTRUSIVE_DOXYGEN_INVOKED | |
114 | ||
115 | //! rbtree_algorithms provides basic algorithms to manipulate | |
116 | //! nodes forming a red-black tree. The insertion and deletion algorithms are | |
117 | //! based on those in Cormen, Leiserson, and Rivest, Introduction to Algorithms | |
118 | //! (MIT Press, 1990), except that | |
119 | //! | |
120 | //! (1) the header node is maintained with links not only to the root | |
121 | //! but also to the leftmost node of the tree, to enable constant time | |
122 | //! begin(), and to the rightmost node of the tree, to enable linear time | |
123 | //! performance when used with the generic set algorithms (set_union, | |
124 | //! etc.); | |
125 | //! | |
126 | //! (2) when a node being deleted has two children its successor node is | |
127 | //! relinked into its place, rather than copied, so that the only | |
128 | //! pointers invalidated are those referring to the deleted node. | |
129 | //! | |
130 | //! rbtree_algorithms is configured with a NodeTraits class, which encapsulates the | |
131 | //! information about the node to be manipulated. NodeTraits must support the | |
132 | //! following interface: | |
133 | //! | |
134 | //! <b>Typedefs</b>: | |
135 | //! | |
136 | //! <tt>node</tt>: The type of the node that forms the binary search tree | |
137 | //! | |
138 | //! <tt>node_ptr</tt>: A pointer to a node | |
139 | //! | |
140 | //! <tt>const_node_ptr</tt>: A pointer to a const node | |
141 | //! | |
142 | //! <tt>color</tt>: The type that can store the color of a node | |
143 | //! | |
144 | //! <b>Static functions</b>: | |
145 | //! | |
146 | //! <tt>static node_ptr get_parent(const_node_ptr n);</tt> | |
147 | //! | |
148 | //! <tt>static void set_parent(node_ptr n, node_ptr parent);</tt> | |
149 | //! | |
150 | //! <tt>static node_ptr get_left(const_node_ptr n);</tt> | |
151 | //! | |
152 | //! <tt>static void set_left(node_ptr n, node_ptr left);</tt> | |
153 | //! | |
154 | //! <tt>static node_ptr get_right(const_node_ptr n);</tt> | |
155 | //! | |
156 | //! <tt>static void set_right(node_ptr n, node_ptr right);</tt> | |
157 | //! | |
158 | //! <tt>static color get_color(const_node_ptr n);</tt> | |
159 | //! | |
160 | //! <tt>static void set_color(node_ptr n, color c);</tt> | |
161 | //! | |
162 | //! <tt>static color black();</tt> | |
163 | //! | |
164 | //! <tt>static color red();</tt> | |
165 | template<class NodeTraits> | |
166 | class rbtree_algorithms | |
167 | #ifndef BOOST_INTRUSIVE_DOXYGEN_INVOKED | |
168 | : public bstree_algorithms<NodeTraits> | |
169 | #endif | |
170 | { | |
171 | public: | |
172 | typedef NodeTraits node_traits; | |
173 | typedef typename NodeTraits::node node; | |
174 | typedef typename NodeTraits::node_ptr node_ptr; | |
175 | typedef typename NodeTraits::const_node_ptr const_node_ptr; | |
176 | typedef typename NodeTraits::color color; | |
177 | ||
178 | /// @cond | |
179 | private: | |
180 | ||
181 | typedef bstree_algorithms<NodeTraits> bstree_algo; | |
182 | ||
183 | /// @endcond | |
184 | ||
185 | public: | |
186 | ||
187 | //! This type is the information that will be | |
188 | //! filled by insert_unique_check | |
189 | typedef typename bstree_algo::insert_commit_data insert_commit_data; | |
190 | ||
191 | #ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED | |
192 | ||
193 | //! @copydoc ::boost::intrusive::bstree_algorithms::get_header(const const_node_ptr&) | |
194 | static node_ptr get_header(const const_node_ptr & n); | |
195 | ||
196 | //! @copydoc ::boost::intrusive::bstree_algorithms::begin_node | |
197 | static node_ptr begin_node(const const_node_ptr & header); | |
198 | ||
199 | //! @copydoc ::boost::intrusive::bstree_algorithms::end_node | |
200 | static node_ptr end_node(const const_node_ptr & header); | |
201 | ||
202 | //! @copydoc ::boost::intrusive::bstree_algorithms::swap_tree | |
92f5a8d4 | 203 | static void swap_tree(node_ptr header1, node_ptr header2); |
7c673cae FG |
204 | |
205 | #endif //#ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED | |
206 | ||
92f5a8d4 TL |
207 | //! @copydoc ::boost::intrusive::bstree_algorithms::swap_nodes(node_ptr,node_ptr) |
208 | static void swap_nodes(node_ptr node1, node_ptr node2) | |
7c673cae FG |
209 | { |
210 | if(node1 == node2) | |
211 | return; | |
212 | ||
213 | node_ptr header1(bstree_algo::get_header(node1)), header2(bstree_algo::get_header(node2)); | |
214 | swap_nodes(node1, header1, node2, header2); | |
215 | } | |
216 | ||
92f5a8d4 TL |
217 | //! @copydoc ::boost::intrusive::bstree_algorithms::swap_nodes(node_ptr,node_ptr,node_ptr,node_ptr) |
218 | static void swap_nodes(node_ptr node1, node_ptr header1, node_ptr node2, node_ptr header2) | |
7c673cae FG |
219 | { |
220 | if(node1 == node2) return; | |
221 | ||
222 | bstree_algo::swap_nodes(node1, header1, node2, header2); | |
223 | //Swap color | |
224 | color c = NodeTraits::get_color(node1); | |
225 | NodeTraits::set_color(node1, NodeTraits::get_color(node2)); | |
226 | NodeTraits::set_color(node2, c); | |
227 | } | |
228 | ||
92f5a8d4 TL |
229 | //! @copydoc ::boost::intrusive::bstree_algorithms::replace_node(node_ptr,node_ptr) |
230 | static void replace_node(node_ptr node_to_be_replaced, node_ptr new_node) | |
7c673cae FG |
231 | { |
232 | if(node_to_be_replaced == new_node) | |
233 | return; | |
234 | replace_node(node_to_be_replaced, bstree_algo::get_header(node_to_be_replaced), new_node); | |
235 | } | |
236 | ||
92f5a8d4 TL |
237 | //! @copydoc ::boost::intrusive::bstree_algorithms::replace_node(node_ptr,node_ptr,node_ptr) |
238 | static void replace_node(node_ptr node_to_be_replaced, node_ptr header, node_ptr new_node) | |
7c673cae FG |
239 | { |
240 | bstree_algo::replace_node(node_to_be_replaced, header, new_node); | |
241 | NodeTraits::set_color(new_node, NodeTraits::get_color(node_to_be_replaced)); | |
242 | } | |
243 | ||
92f5a8d4 | 244 | //! @copydoc ::boost::intrusive::bstree_algorithms::unlink(node_ptr) |
7c673cae FG |
245 | static void unlink(const node_ptr& node) |
246 | { | |
247 | node_ptr x = NodeTraits::get_parent(node); | |
248 | if(x){ | |
249 | while(!is_header(x)) | |
250 | x = NodeTraits::get_parent(x); | |
251 | erase(x, node); | |
252 | } | |
253 | } | |
254 | ||
255 | #ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED | |
256 | //! @copydoc ::boost::intrusive::bstree_algorithms::unlink_leftmost_without_rebalance | |
257 | static node_ptr unlink_leftmost_without_rebalance(const node_ptr & header); | |
258 | ||
259 | //! @copydoc ::boost::intrusive::bstree_algorithms::unique(const const_node_ptr&) | |
260 | static bool unique(const const_node_ptr & node); | |
261 | ||
262 | //! @copydoc ::boost::intrusive::bstree_algorithms::size(const const_node_ptr&) | |
263 | static std::size_t size(const const_node_ptr & header); | |
264 | ||
265 | //! @copydoc ::boost::intrusive::bstree_algorithms::next_node(const node_ptr&) | |
266 | static node_ptr next_node(const node_ptr & node); | |
267 | ||
268 | //! @copydoc ::boost::intrusive::bstree_algorithms::prev_node(const node_ptr&) | |
269 | static node_ptr prev_node(const node_ptr & node); | |
270 | ||
92f5a8d4 | 271 | //! @copydoc ::boost::intrusive::bstree_algorithms::init(node_ptr) |
7c673cae FG |
272 | static void init(const node_ptr & node); |
273 | #endif //#ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED | |
274 | ||
92f5a8d4 TL |
275 | //! @copydoc ::boost::intrusive::bstree_algorithms::init_header(node_ptr) |
276 | BOOST_INTRUSIVE_FORCEINLINE static void init_header(node_ptr header) | |
7c673cae FG |
277 | { |
278 | bstree_algo::init_header(header); | |
279 | NodeTraits::set_color(header, NodeTraits::red()); | |
280 | } | |
281 | ||
92f5a8d4 TL |
282 | //! @copydoc ::boost::intrusive::bstree_algorithms::erase(node_ptr,node_ptr) |
283 | static node_ptr erase(node_ptr header, node_ptr z) | |
7c673cae FG |
284 | { |
285 | typename bstree_algo::data_for_rebalance info; | |
286 | bstree_algo::erase(header, z, info); | |
287 | rebalance_after_erasure(header, z, info); | |
288 | return z; | |
289 | } | |
290 | ||
291 | //! @copydoc ::boost::intrusive::bstree_algorithms::transfer_unique | |
292 | template<class NodePtrCompare> | |
293 | static bool transfer_unique | |
92f5a8d4 | 294 | (node_ptr header1, NodePtrCompare comp, node_ptr header2, node_ptr z) |
7c673cae FG |
295 | { |
296 | typename bstree_algo::data_for_rebalance info; | |
297 | bool const transferred = bstree_algo::transfer_unique(header1, comp, header2, z, info); | |
298 | if(transferred){ | |
299 | rebalance_after_erasure(header2, z, info); | |
300 | rebalance_after_insertion(header1, z); | |
301 | } | |
302 | return transferred; | |
303 | } | |
304 | ||
305 | //! @copydoc ::boost::intrusive::bstree_algorithms::transfer_equal | |
306 | template<class NodePtrCompare> | |
307 | static void transfer_equal | |
92f5a8d4 | 308 | (node_ptr header1, NodePtrCompare comp, node_ptr header2, node_ptr z) |
7c673cae FG |
309 | { |
310 | typename bstree_algo::data_for_rebalance info; | |
311 | bstree_algo::transfer_equal(header1, comp, header2, z, info); | |
312 | rebalance_after_erasure(header2, z, info); | |
313 | rebalance_after_insertion(header1, z); | |
314 | } | |
315 | ||
92f5a8d4 | 316 | //! @copydoc ::boost::intrusive::bstree_algorithms::clone(const const_node_ptr&,node_ptr,Cloner,Disposer) |
7c673cae FG |
317 | template <class Cloner, class Disposer> |
318 | static void clone | |
92f5a8d4 | 319 | (const_node_ptr source_header, node_ptr target_header, Cloner cloner, Disposer disposer) |
7c673cae FG |
320 | { |
321 | rbtree_node_cloner<NodeTraits, Cloner> new_cloner(cloner); | |
322 | bstree_algo::clone(source_header, target_header, new_cloner, disposer); | |
323 | } | |
324 | ||
325 | #ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED | |
326 | //! @copydoc ::boost::intrusive::bstree_algorithms::clear_and_dispose(const node_ptr&,Disposer) | |
327 | template<class Disposer> | |
328 | static void clear_and_dispose(const node_ptr & header, Disposer disposer); | |
329 | ||
330 | //! @copydoc ::boost::intrusive::bstree_algorithms::lower_bound(const const_node_ptr&,const KeyType&,KeyNodePtrCompare) | |
331 | template<class KeyType, class KeyNodePtrCompare> | |
332 | static node_ptr lower_bound | |
333 | (const const_node_ptr & header, const KeyType &key, KeyNodePtrCompare comp); | |
334 | ||
335 | //! @copydoc ::boost::intrusive::bstree_algorithms::upper_bound(const const_node_ptr&,const KeyType&,KeyNodePtrCompare) | |
336 | template<class KeyType, class KeyNodePtrCompare> | |
337 | static node_ptr upper_bound | |
338 | (const const_node_ptr & header, const KeyType &key, KeyNodePtrCompare comp); | |
339 | ||
340 | //! @copydoc ::boost::intrusive::bstree_algorithms::find(const const_node_ptr&, const KeyType&,KeyNodePtrCompare) | |
341 | template<class KeyType, class KeyNodePtrCompare> | |
342 | static node_ptr find | |
343 | (const const_node_ptr & header, const KeyType &key, KeyNodePtrCompare comp); | |
344 | ||
345 | //! @copydoc ::boost::intrusive::bstree_algorithms::equal_range(const const_node_ptr&,const KeyType&,KeyNodePtrCompare) | |
346 | template<class KeyType, class KeyNodePtrCompare> | |
347 | static std::pair<node_ptr, node_ptr> equal_range | |
348 | (const const_node_ptr & header, const KeyType &key, KeyNodePtrCompare comp); | |
349 | ||
350 | //! @copydoc ::boost::intrusive::bstree_algorithms::bounded_range(const const_node_ptr&,const KeyType&,const KeyType&,KeyNodePtrCompare,bool,bool) | |
351 | template<class KeyType, class KeyNodePtrCompare> | |
352 | static std::pair<node_ptr, node_ptr> bounded_range | |
353 | (const const_node_ptr & header, const KeyType &lower_key, const KeyType &upper_key, KeyNodePtrCompare comp | |
354 | , bool left_closed, bool right_closed); | |
355 | ||
356 | //! @copydoc ::boost::intrusive::bstree_algorithms::count(const const_node_ptr&,const KeyType&,KeyNodePtrCompare) | |
357 | template<class KeyType, class KeyNodePtrCompare> | |
358 | static std::size_t count(const const_node_ptr & header, const KeyType &key, KeyNodePtrCompare comp); | |
359 | ||
360 | #endif //#ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED | |
361 | ||
92f5a8d4 | 362 | //! @copydoc ::boost::intrusive::bstree_algorithms::insert_equal_upper_bound(node_ptr,node_ptr,NodePtrCompare) |
7c673cae FG |
363 | template<class NodePtrCompare> |
364 | static node_ptr insert_equal_upper_bound | |
92f5a8d4 | 365 | (node_ptr h, node_ptr new_node, NodePtrCompare comp) |
7c673cae FG |
366 | { |
367 | bstree_algo::insert_equal_upper_bound(h, new_node, comp); | |
368 | rebalance_after_insertion(h, new_node); | |
369 | return new_node; | |
370 | } | |
371 | ||
92f5a8d4 | 372 | //! @copydoc ::boost::intrusive::bstree_algorithms::insert_equal_lower_bound(node_ptr,node_ptr,NodePtrCompare) |
7c673cae FG |
373 | template<class NodePtrCompare> |
374 | static node_ptr insert_equal_lower_bound | |
92f5a8d4 | 375 | (node_ptr h, node_ptr new_node, NodePtrCompare comp) |
7c673cae FG |
376 | { |
377 | bstree_algo::insert_equal_lower_bound(h, new_node, comp); | |
378 | rebalance_after_insertion(h, new_node); | |
379 | return new_node; | |
380 | } | |
381 | ||
92f5a8d4 | 382 | //! @copydoc ::boost::intrusive::bstree_algorithms::insert_equal(node_ptr,node_ptr,node_ptr,NodePtrCompare) |
7c673cae FG |
383 | template<class NodePtrCompare> |
384 | static node_ptr insert_equal | |
92f5a8d4 | 385 | (node_ptr header, node_ptr hint, node_ptr new_node, NodePtrCompare comp) |
7c673cae FG |
386 | { |
387 | bstree_algo::insert_equal(header, hint, new_node, comp); | |
388 | rebalance_after_insertion(header, new_node); | |
389 | return new_node; | |
390 | } | |
391 | ||
92f5a8d4 | 392 | //! @copydoc ::boost::intrusive::bstree_algorithms::insert_before(node_ptr,node_ptr,node_ptr) |
7c673cae | 393 | static node_ptr insert_before |
92f5a8d4 | 394 | (node_ptr header, node_ptr pos, node_ptr new_node) |
7c673cae FG |
395 | { |
396 | bstree_algo::insert_before(header, pos, new_node); | |
397 | rebalance_after_insertion(header, new_node); | |
398 | return new_node; | |
399 | } | |
400 | ||
92f5a8d4 TL |
401 | //! @copydoc ::boost::intrusive::bstree_algorithms::push_back(node_ptr,node_ptr) |
402 | static void push_back(node_ptr header, node_ptr new_node) | |
7c673cae FG |
403 | { |
404 | bstree_algo::push_back(header, new_node); | |
405 | rebalance_after_insertion(header, new_node); | |
406 | } | |
407 | ||
92f5a8d4 TL |
408 | //! @copydoc ::boost::intrusive::bstree_algorithms::push_front(node_ptr,node_ptr) |
409 | static void push_front(node_ptr header, node_ptr new_node) | |
7c673cae FG |
410 | { |
411 | bstree_algo::push_front(header, new_node); | |
412 | rebalance_after_insertion(header, new_node); | |
413 | } | |
414 | ||
415 | #ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED | |
416 | //! @copydoc ::boost::intrusive::bstree_algorithms::insert_unique_check(const const_node_ptr&,const KeyType&,KeyNodePtrCompare,insert_commit_data&) | |
417 | template<class KeyType, class KeyNodePtrCompare> | |
418 | static std::pair<node_ptr, bool> insert_unique_check | |
92f5a8d4 | 419 | (const_node_ptr header, const KeyType &key |
7c673cae FG |
420 | ,KeyNodePtrCompare comp, insert_commit_data &commit_data); |
421 | ||
422 | //! @copydoc ::boost::intrusive::bstree_algorithms::insert_unique_check(const const_node_ptr&,const node_ptr&,const KeyType&,KeyNodePtrCompare,insert_commit_data&) | |
423 | template<class KeyType, class KeyNodePtrCompare> | |
424 | static std::pair<node_ptr, bool> insert_unique_check | |
92f5a8d4 | 425 | (const_node_ptr header, node_ptr hint, const KeyType &key |
7c673cae FG |
426 | ,KeyNodePtrCompare comp, insert_commit_data &commit_data); |
427 | #endif //#ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED | |
428 | ||
92f5a8d4 | 429 | //! @copydoc ::boost::intrusive::bstree_algorithms::insert_unique_commit(node_ptr,node_ptr,const insert_commit_data&) |
7c673cae | 430 | static void insert_unique_commit |
92f5a8d4 | 431 | (node_ptr header, node_ptr new_value, const insert_commit_data &commit_data) |
7c673cae FG |
432 | { |
433 | bstree_algo::insert_unique_commit(header, new_value, commit_data); | |
434 | rebalance_after_insertion(header, new_value); | |
435 | } | |
436 | ||
437 | //! @copydoc ::boost::intrusive::bstree_algorithms::is_header | |
438 | static bool is_header(const const_node_ptr & p) | |
439 | { | |
440 | return NodeTraits::get_color(p) == NodeTraits::red() && | |
441 | bstree_algo::is_header(p); | |
442 | } | |
443 | ||
444 | /// @cond | |
445 | private: | |
446 | ||
447 | static void rebalance_after_erasure | |
92f5a8d4 | 448 | ( node_ptr header, node_ptr z, const typename bstree_algo::data_for_rebalance &info) |
7c673cae FG |
449 | { |
450 | color new_z_color; | |
451 | if(info.y != z){ | |
452 | new_z_color = NodeTraits::get_color(info.y); | |
453 | NodeTraits::set_color(info.y, NodeTraits::get_color(z)); | |
454 | } | |
455 | else{ | |
456 | new_z_color = NodeTraits::get_color(z); | |
457 | } | |
458 | //Rebalance rbtree if needed | |
459 | if(new_z_color != NodeTraits::red()){ | |
460 | rebalance_after_erasure_restore_invariants(header, info.x, info.x_parent); | |
461 | } | |
462 | } | |
463 | ||
92f5a8d4 | 464 | static void rebalance_after_erasure_restore_invariants(node_ptr header, node_ptr x, node_ptr x_parent) |
7c673cae FG |
465 | { |
466 | while(1){ | |
467 | if(x_parent == header || (x && NodeTraits::get_color(x) != NodeTraits::black())){ | |
468 | break; | |
469 | } | |
470 | //Don't cache x_is_leftchild or similar because x can be null and | |
471 | //equal to both x_parent_left and x_parent_right | |
472 | const node_ptr x_parent_left(NodeTraits::get_left(x_parent)); | |
473 | if(x == x_parent_left){ //x is left child | |
474 | node_ptr w = NodeTraits::get_right(x_parent); | |
475 | BOOST_INTRUSIVE_INVARIANT_ASSERT(w); | |
476 | if(NodeTraits::get_color(w) == NodeTraits::red()){ | |
477 | NodeTraits::set_color(w, NodeTraits::black()); | |
478 | NodeTraits::set_color(x_parent, NodeTraits::red()); | |
479 | bstree_algo::rotate_left(x_parent, w, NodeTraits::get_parent(x_parent), header); | |
480 | w = NodeTraits::get_right(x_parent); | |
481 | BOOST_INTRUSIVE_INVARIANT_ASSERT(w); | |
482 | } | |
483 | node_ptr const w_left (NodeTraits::get_left(w)); | |
484 | node_ptr const w_right(NodeTraits::get_right(w)); | |
485 | if((!w_left || NodeTraits::get_color(w_left) == NodeTraits::black()) && | |
486 | (!w_right || NodeTraits::get_color(w_right) == NodeTraits::black())){ | |
487 | NodeTraits::set_color(w, NodeTraits::red()); | |
488 | x = x_parent; | |
489 | x_parent = NodeTraits::get_parent(x_parent); | |
490 | } | |
491 | else { | |
492 | if(!w_right || NodeTraits::get_color(w_right) == NodeTraits::black()){ | |
493 | NodeTraits::set_color(w_left, NodeTraits::black()); | |
494 | NodeTraits::set_color(w, NodeTraits::red()); | |
495 | bstree_algo::rotate_right(w, w_left, NodeTraits::get_parent(w), header); | |
496 | w = NodeTraits::get_right(x_parent); | |
497 | BOOST_INTRUSIVE_INVARIANT_ASSERT(w); | |
498 | } | |
499 | NodeTraits::set_color(w, NodeTraits::get_color(x_parent)); | |
500 | NodeTraits::set_color(x_parent, NodeTraits::black()); | |
501 | const node_ptr new_wright(NodeTraits::get_right(w)); | |
502 | if(new_wright) | |
503 | NodeTraits::set_color(new_wright, NodeTraits::black()); | |
504 | bstree_algo::rotate_left(x_parent, NodeTraits::get_right(x_parent), NodeTraits::get_parent(x_parent), header); | |
505 | break; | |
506 | } | |
507 | } | |
508 | else { | |
509 | // same as above, with right_ <-> left_. | |
510 | node_ptr w = x_parent_left; | |
511 | if(NodeTraits::get_color(w) == NodeTraits::red()){ | |
512 | NodeTraits::set_color(w, NodeTraits::black()); | |
513 | NodeTraits::set_color(x_parent, NodeTraits::red()); | |
514 | bstree_algo::rotate_right(x_parent, w, NodeTraits::get_parent(x_parent), header); | |
515 | w = NodeTraits::get_left(x_parent); | |
516 | BOOST_INTRUSIVE_INVARIANT_ASSERT(w); | |
517 | } | |
518 | node_ptr const w_left (NodeTraits::get_left(w)); | |
519 | node_ptr const w_right(NodeTraits::get_right(w)); | |
520 | if((!w_right || NodeTraits::get_color(w_right) == NodeTraits::black()) && | |
521 | (!w_left || NodeTraits::get_color(w_left) == NodeTraits::black())){ | |
522 | NodeTraits::set_color(w, NodeTraits::red()); | |
523 | x = x_parent; | |
524 | x_parent = NodeTraits::get_parent(x_parent); | |
525 | } | |
526 | else { | |
527 | if(!w_left || NodeTraits::get_color(w_left) == NodeTraits::black()){ | |
528 | NodeTraits::set_color(w_right, NodeTraits::black()); | |
529 | NodeTraits::set_color(w, NodeTraits::red()); | |
530 | bstree_algo::rotate_left(w, w_right, NodeTraits::get_parent(w), header); | |
531 | w = NodeTraits::get_left(x_parent); | |
532 | BOOST_INTRUSIVE_INVARIANT_ASSERT(w); | |
533 | } | |
534 | NodeTraits::set_color(w, NodeTraits::get_color(x_parent)); | |
535 | NodeTraits::set_color(x_parent, NodeTraits::black()); | |
536 | const node_ptr new_wleft(NodeTraits::get_left(w)); | |
537 | if(new_wleft) | |
538 | NodeTraits::set_color(new_wleft, NodeTraits::black()); | |
539 | bstree_algo::rotate_right(x_parent, NodeTraits::get_left(x_parent), NodeTraits::get_parent(x_parent), header); | |
540 | break; | |
541 | } | |
542 | } | |
543 | } | |
544 | if(x) | |
545 | NodeTraits::set_color(x, NodeTraits::black()); | |
546 | } | |
547 | ||
92f5a8d4 | 548 | static void rebalance_after_insertion(node_ptr header, node_ptr p) |
7c673cae FG |
549 | { |
550 | NodeTraits::set_color(p, NodeTraits::red()); | |
551 | while(1){ | |
552 | node_ptr p_parent(NodeTraits::get_parent(p)); | |
553 | const node_ptr p_grandparent(NodeTraits::get_parent(p_parent)); | |
554 | if(p_parent == header || NodeTraits::get_color(p_parent) == NodeTraits::black() || p_grandparent == header){ | |
555 | break; | |
556 | } | |
557 | ||
558 | NodeTraits::set_color(p_grandparent, NodeTraits::red()); | |
559 | node_ptr const p_grandparent_left (NodeTraits::get_left (p_grandparent)); | |
560 | bool const p_parent_is_left_child = p_parent == p_grandparent_left; | |
561 | node_ptr const x(p_parent_is_left_child ? NodeTraits::get_right(p_grandparent) : p_grandparent_left); | |
562 | ||
563 | if(x && NodeTraits::get_color(x) == NodeTraits::red()){ | |
564 | NodeTraits::set_color(x, NodeTraits::black()); | |
565 | NodeTraits::set_color(p_parent, NodeTraits::black()); | |
566 | p = p_grandparent; | |
567 | } | |
568 | else{ //Final step | |
569 | const bool p_is_left_child(NodeTraits::get_left(p_parent) == p); | |
570 | if(p_parent_is_left_child){ //p_parent is left child | |
571 | if(!p_is_left_child){ //p is right child | |
572 | bstree_algo::rotate_left_no_parent_fix(p_parent, p); | |
573 | //No need to link p and p_grandparent: | |
574 | // [NodeTraits::set_parent(p, p_grandparent) + NodeTraits::set_left(p_grandparent, p)] | |
575 | //as p_grandparent is not the header, another rotation is coming and p_parent | |
576 | //will be the left child of p_grandparent | |
577 | p_parent = p; | |
578 | } | |
579 | bstree_algo::rotate_right(p_grandparent, p_parent, NodeTraits::get_parent(p_grandparent), header); | |
580 | } | |
581 | else{ //p_parent is right child | |
582 | if(p_is_left_child){ //p is left child | |
583 | bstree_algo::rotate_right_no_parent_fix(p_parent, p); | |
584 | //No need to link p and p_grandparent: | |
585 | // [NodeTraits::set_parent(p, p_grandparent) + NodeTraits::set_right(p_grandparent, p)] | |
586 | //as p_grandparent is not the header, another rotation is coming and p_parent | |
587 | //will be the right child of p_grandparent | |
588 | p_parent = p; | |
589 | } | |
590 | bstree_algo::rotate_left(p_grandparent, p_parent, NodeTraits::get_parent(p_grandparent), header); | |
591 | } | |
592 | NodeTraits::set_color(p_parent, NodeTraits::black()); | |
593 | break; | |
594 | } | |
595 | } | |
596 | NodeTraits::set_color(NodeTraits::get_parent(header), NodeTraits::black()); | |
597 | } | |
598 | /// @endcond | |
599 | }; | |
600 | ||
601 | /// @cond | |
602 | ||
603 | template<class NodeTraits> | |
604 | struct get_algo<RbTreeAlgorithms, NodeTraits> | |
605 | { | |
606 | typedef rbtree_algorithms<NodeTraits> type; | |
607 | }; | |
608 | ||
609 | template <class ValueTraits, class NodePtrCompare, class ExtraChecker> | |
610 | struct get_node_checker<RbTreeAlgorithms, ValueTraits, NodePtrCompare, ExtraChecker> | |
611 | { | |
612 | typedef detail::rbtree_node_checker<ValueTraits, NodePtrCompare, ExtraChecker> type; | |
613 | }; | |
614 | ||
615 | /// @endcond | |
616 | ||
617 | } //namespace intrusive | |
618 | } //namespace boost | |
619 | ||
620 | #include <boost/intrusive/detail/config_end.hpp> | |
621 | ||
622 | #endif //BOOST_INTRUSIVE_RBTREE_ALGORITHMS_HPP |