1/////////////////////////////////////////////////////////////////////////////
2//
3// (C) Copyright Ion Gaztanaga 2007-2014
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// The option that yields to non-floating point 1/sqrt(2) alpha is taken
14// from the scapegoat tree implementation of the PSPP library.
15//
16/////////////////////////////////////////////////////////////////////////////
17
18#ifndef BOOST_INTRUSIVE_SGTREE_HPP
19#define BOOST_INTRUSIVE_SGTREE_HPP
20
21#include <boost/intrusive/detail/config_begin.hpp>
22#include <boost/intrusive/intrusive_fwd.hpp>
23#include <boost/intrusive/detail/assert.hpp>
24#include <boost/static_assert.hpp>
25#include <boost/intrusive/bs_set_hook.hpp>
26#include <boost/intrusive/bstree.hpp>
27#include <boost/intrusive/detail/tree_node.hpp>
28#include <boost/intrusive/pointer_traits.hpp>
29#include <boost/intrusive/detail/mpl.hpp>
30#include <boost/intrusive/detail/math.hpp>
31#include <boost/intrusive/detail/get_value_traits.hpp>
32#include <boost/intrusive/sgtree_algorithms.hpp>
33#include <boost/intrusive/detail/key_nodeptr_comp.hpp>
34#include <boost/intrusive/link_mode.hpp>
35
36#include <boost/move/utility_core.hpp>
37#include <boost/move/adl_move_swap.hpp>
38
39#include <cstddef>
40#include <boost/intrusive/detail/minimal_less_equal_header.hpp>
41#include <boost/intrusive/detail/minimal_pair_header.hpp> //std::pair
42#include <cmath>
43#include <cstddef>
44
45#if defined(BOOST_HAS_PRAGMA_ONCE)
46# pragma once
47#endif
48
49namespace boost {
50namespace intrusive {
51
52/// @cond
53
54namespace detail{
55
56/////////////////////////////////////////////////////////////
57//
58// Halpha for fixed floating_point<false> option
59//
60/////////////////////////////////////////////////////////////
61
62//! Returns floor(log2(n)/log2(sqrt(2))) -> floor(2*log2(n))
63//! Undefined if N is 0.
64//!
65//! This function does not use float point operations.
66inline std::size_t calculate_h_sqrt2 (std::size_t n)
67{
68 std::size_t f_log2 = detail::floor_log2(n);
69 return (2*f_log2) + static_cast<std::size_t>(n >= detail::sqrt2_pow_2xplus1(x: f_log2));
70}
71
72struct h_alpha_sqrt2_t
73{
74 h_alpha_sqrt2_t(void){}
75 std::size_t operator()(std::size_t n) const
76 { return calculate_h_sqrt2(n); }
77};
78
79struct alpha_0_75_by_max_size_t
80{
81 alpha_0_75_by_max_size_t(void){}
82
83 std::size_t operator()(std::size_t max_tree_size) const
84 {
85 const std::size_t max_tree_size_limit = ((~std::size_t(0))/std::size_t(3));
86 return max_tree_size > max_tree_size_limit ? max_tree_size/4*3 : max_tree_size*3/4;
87 }
88};
89
90/////////////////////////////////////////////////////////////
91//
92// Halpha for fixed floating_point<true> option
93//
94/////////////////////////////////////////////////////////////
95
96struct h_alpha_t
97{
98 explicit h_alpha_t(float inv_minus_logalpha)
99 : inv_minus_logalpha_(inv_minus_logalpha)
100 {}
101
102 std::size_t operator()(std::size_t n) const
103 {
104 ////////////////////////////////////////////////////////////
105 // This function must return "floor(log2(1/alpha(n)))" ->
106 // floor(log2(n)/log(1/alpha)) ->
107 // floor(log2(n)/-log2(alpha))
108 // floor(log2(n)*(1/-log2(alpha)))
109 ////////////////////////////////////////////////////////////
110 return static_cast<std::size_t>(detail::fast_log2(val: float(n))*inv_minus_logalpha_);
111 }
112
113 private:
114 //Since the function will be repeatedly called
115 //precalculate constant data to avoid repeated
116 //calls to log and division.
117 //This will store 1/(-std::log2(alpha_))
118 float inv_minus_logalpha_;
119};
120
121struct alpha_by_max_size_t
122{
123 explicit alpha_by_max_size_t(float alpha)
124 : alpha_(alpha)
125 {}
126
127 float operator()(std::size_t max_tree_size) const
128 { return float(max_tree_size)*alpha_; }
129
130 private:
131 float alpha_;
132};
133
134template<bool Activate, class SizeType>
135struct alpha_holder
136{
137 typedef boost::intrusive::detail::h_alpha_t h_alpha_t;
138 typedef boost::intrusive::detail::alpha_by_max_size_t multiply_by_alpha_t;
139
140 alpha_holder()
141 : max_tree_size_()
142 { set_alpha(0.70711f); } // ~1/sqrt(2)
143
144 float get_alpha() const
145 { return alpha_; }
146
147 void set_alpha(float alpha)
148 {
149 alpha_ = alpha;
150 inv_minus_logalpha_ = 1/(-detail::fast_log2(val: alpha));
151 }
152
153 h_alpha_t get_h_alpha_t() const
154 { return h_alpha_t(inv_minus_logalpha_); }
155
156 multiply_by_alpha_t get_multiply_by_alpha_t() const
157 { return multiply_by_alpha_t(alpha_); }
158
159 protected:
160 float alpha_;
161 float inv_minus_logalpha_;
162 SizeType max_tree_size_;
163};
164
165template<class SizeType>
166struct alpha_holder<false, SizeType>
167{
168 //This specialization uses alpha = 1/sqrt(2)
169 //without using floating point operations
170 //Downside: alpha CAN't be changed.
171 typedef boost::intrusive::detail::h_alpha_sqrt2_t h_alpha_t;
172 typedef boost::intrusive::detail::alpha_0_75_by_max_size_t multiply_by_alpha_t;
173
174 alpha_holder()
175 : max_tree_size_()
176 {}
177
178 float get_alpha() const
179 { return 0.70710677f; }
180
181 void set_alpha(float)
182 { //alpha CAN't be changed.
183 BOOST_INTRUSIVE_INVARIANT_ASSERT(0);
184 }
185
186 h_alpha_t get_h_alpha_t() const
187 { return h_alpha_t(); }
188
189 multiply_by_alpha_t get_multiply_by_alpha_t() const
190 { return multiply_by_alpha_t(); }
191
192 SizeType max_tree_size_;
193};
194
195} //namespace detail{
196
197struct sgtree_defaults
198 : bstree_defaults
199{
200 static const bool floating_point = true;
201};
202
203/// @endcond
204
205//! The class template sgtree is an intrusive scapegoat tree container, that
206//! is used to construct intrusive sg_set and sg_multiset containers.
207//! The no-throw guarantee holds only, if the value_compare object
208//! doesn't throw.
209//!
210//! The template parameter \c T is the type to be managed by the container.
211//! The user can specify additional options and if no options are provided
212//! default options are used.
213//!
214//! The container supports the following options:
215//! \c base_hook<>/member_hook<>/value_traits<>,
216//! \c floating_point<>, \c size_type<> and
217//! \c compare<>.
218#if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED)
219template<class T, class ...Options>
220#else
221template<class ValueTraits, class VoidOrKeyOfValue, class VoidOrKeyComp, class SizeType, bool FloatingPoint, typename HeaderHolder>
222#endif
223class sgtree_impl
224 /// @cond
225 : public bstree_impl<ValueTraits, VoidOrKeyOfValue, VoidOrKeyComp, SizeType, true, SgTreeAlgorithms, HeaderHolder>
226 , public detail::alpha_holder<FloatingPoint, SizeType>
227 /// @endcond
228{
229 public:
230 typedef ValueTraits value_traits;
231 /// @cond
232 typedef bstree_impl< ValueTraits, VoidOrKeyOfValue, VoidOrKeyComp, SizeType
233 , true, SgTreeAlgorithms, HeaderHolder> tree_type;
234 typedef tree_type implementation_defined;
235
236 /// @endcond
237
238 typedef typename implementation_defined::pointer pointer;
239 typedef typename implementation_defined::const_pointer const_pointer;
240 typedef typename implementation_defined::value_type value_type;
241 typedef typename implementation_defined::key_type key_type;
242 typedef typename implementation_defined::key_of_value key_of_value;
243 typedef typename implementation_defined::reference reference;
244 typedef typename implementation_defined::const_reference const_reference;
245 typedef typename implementation_defined::difference_type difference_type;
246 typedef typename implementation_defined::size_type size_type;
247 typedef typename implementation_defined::value_compare value_compare;
248 typedef typename implementation_defined::key_compare key_compare;
249 typedef typename implementation_defined::iterator iterator;
250 typedef typename implementation_defined::const_iterator const_iterator;
251 typedef typename implementation_defined::reverse_iterator reverse_iterator;
252 typedef typename implementation_defined::const_reverse_iterator const_reverse_iterator;
253 typedef typename implementation_defined::node_traits node_traits;
254 typedef typename implementation_defined::node node;
255 typedef typename implementation_defined::node_ptr node_ptr;
256 typedef typename implementation_defined::const_node_ptr const_node_ptr;
257 typedef BOOST_INTRUSIVE_IMPDEF(sgtree_algorithms<node_traits>) node_algorithms;
258
259 static const bool constant_time_size = implementation_defined::constant_time_size;
260 static const bool floating_point = FloatingPoint;
261 static const bool stateful_value_traits = implementation_defined::stateful_value_traits;
262
263 /// @cond
264 private:
265
266 //noncopyable
267 typedef detail::alpha_holder<FloatingPoint, SizeType> alpha_traits;
268 typedef typename alpha_traits::h_alpha_t h_alpha_t;
269 typedef typename alpha_traits::multiply_by_alpha_t multiply_by_alpha_t;
270
271 BOOST_MOVABLE_BUT_NOT_COPYABLE(sgtree_impl)
272 BOOST_STATIC_ASSERT(((int)value_traits::link_mode != (int)auto_unlink));
273
274 enum { safemode_or_autounlink =
275 (int)value_traits::link_mode == (int)auto_unlink ||
276 (int)value_traits::link_mode == (int)safe_link };
277
278 /// @endcond
279
280 public:
281
282 typedef BOOST_INTRUSIVE_IMPDEF(typename node_algorithms::insert_commit_data) insert_commit_data;
283
284 //! @copydoc ::boost::intrusive::bstree::bstree(const key_compare &,const value_traits &)
285 explicit sgtree_impl( const key_compare &cmp = key_compare()
286 , const value_traits &v_traits = value_traits())
287 : tree_type(cmp, v_traits)
288 {}
289
290 //! @copydoc ::boost::intrusive::bstree::bstree(bool,Iterator,Iterator,const key_compare &,const value_traits &)
291 template<class Iterator>
292 sgtree_impl( bool unique, Iterator b, Iterator e
293 , const key_compare &cmp = key_compare()
294 , const value_traits &v_traits = value_traits())
295 : tree_type(cmp, v_traits)
296 {
297 if(unique)
298 this->insert_unique(b, e);
299 else
300 this->insert_equal(b, e);
301 }
302
303 //! @copydoc ::boost::intrusive::bstree::bstree(bstree &&)
304 sgtree_impl(BOOST_RV_REF(sgtree_impl) x)
305 : tree_type(BOOST_MOVE_BASE(tree_type, x)), alpha_traits(x.get_alpha_traits())
306 { ::boost::adl_move_swap(this->get_alpha_traits(), x.get_alpha_traits()); }
307
308 //! @copydoc ::boost::intrusive::bstree::operator=(bstree &&)
309 sgtree_impl& operator=(BOOST_RV_REF(sgtree_impl) x)
310 {
311 this->get_alpha_traits() = x.get_alpha_traits();
312 return static_cast<sgtree_impl&>(tree_type::operator=(BOOST_MOVE_BASE(tree_type, x)));
313 }
314
315 /// @cond
316 private:
317
318 const alpha_traits &get_alpha_traits() const
319 { return *this; }
320
321 alpha_traits &get_alpha_traits()
322 { return *this; }
323
324 h_alpha_t get_h_alpha_func() const
325 { return this->get_alpha_traits().get_h_alpha_t(); }
326
327 multiply_by_alpha_t get_alpha_by_max_size_func() const
328 { return this->get_alpha_traits().get_multiply_by_alpha_t(); }
329
330 /// @endcond
331
332 public:
333
334 #ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED
335 //! @copydoc ::boost::intrusive::bstree::~bstree()
336 ~sgtree_impl();
337
338 //! @copydoc ::boost::intrusive::bstree::begin()
339 iterator begin();
340
341 //! @copydoc ::boost::intrusive::bstree::begin()const
342 const_iterator begin() const;
343
344 //! @copydoc ::boost::intrusive::bstree::cbegin()const
345 const_iterator cbegin() const;
346
347 //! @copydoc ::boost::intrusive::bstree::end()
348 iterator end();
349
350 //! @copydoc ::boost::intrusive::bstree::end()const
351 const_iterator end() const;
352
353 //! @copydoc ::boost::intrusive::bstree::cend()const
354 const_iterator cend() const;
355
356 //! @copydoc ::boost::intrusive::bstree::rbegin()
357 reverse_iterator rbegin();
358
359 //! @copydoc ::boost::intrusive::bstree::rbegin()const
360 const_reverse_iterator rbegin() const;
361
362 //! @copydoc ::boost::intrusive::bstree::crbegin()const
363 const_reverse_iterator crbegin() const;
364
365 //! @copydoc ::boost::intrusive::bstree::rend()
366 reverse_iterator rend();
367
368 //! @copydoc ::boost::intrusive::bstree::rend()const
369 const_reverse_iterator rend() const;
370
371 //! @copydoc ::boost::intrusive::bstree::crend()const
372 const_reverse_iterator crend() const;
373
374 //! @copydoc ::boost::intrusive::bstree::container_from_end_iterator(iterator)
375 static sgtree_impl &container_from_end_iterator(iterator end_iterator);
376
377 //! @copydoc ::boost::intrusive::bstree::container_from_end_iterator(const_iterator)
378 static const sgtree_impl &container_from_end_iterator(const_iterator end_iterator);
379
380 //! @copydoc ::boost::intrusive::bstree::container_from_iterator(iterator)
381 static sgtree_impl &container_from_iterator(iterator it);
382
383 //! @copydoc ::boost::intrusive::bstree::container_from_iterator(const_iterator)
384 static const sgtree_impl &container_from_iterator(const_iterator it);
385
386 //! @copydoc ::boost::intrusive::bstree::key_comp()const
387 key_compare key_comp() const;
388
389 //! @copydoc ::boost::intrusive::bstree::value_comp()const
390 value_compare value_comp() const;
391
392 //! @copydoc ::boost::intrusive::bstree::empty()const
393 bool empty() const;
394
395 //! @copydoc ::boost::intrusive::bstree::size()const
396 size_type size() const;
397
398 #endif //#ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED
399
400 //! @copydoc ::boost::intrusive::bstree::swap
401 void swap(sgtree_impl& other)
402 {
403 //This can throw
404 this->tree_type::swap(static_cast<tree_type&>(other));
405 ::boost::adl_move_swap(this->get_alpha_traits(), other.get_alpha_traits());
406 }
407
408 //! @copydoc ::boost::intrusive::bstree::clone_from(const bstree&,Cloner,Disposer)
409 //! Additional notes: it also copies the alpha factor from the source container.
410 template <class Cloner, class Disposer>
411 void clone_from(const sgtree_impl &src, Cloner cloner, Disposer disposer)
412 {
413 tree_type::clone_from(src, cloner, disposer);
414 this->get_alpha_traits() = src.get_alpha_traits();
415 }
416
417 //! @copydoc ::boost::intrusive::bstree::clone_from(bstree&&,Cloner,Disposer)
418 //! Additional notes: it also copies the alpha factor from the source container.
419 template <class Cloner, class Disposer>
420 void clone_from(BOOST_RV_REF(sgtree_impl) src, Cloner cloner, Disposer disposer)
421 {
422 tree_type::clone_from(BOOST_MOVE_BASE(tree_type, src), cloner, disposer);
423 this->get_alpha_traits() = ::boost::move(src.get_alpha_traits());
424 }
425
426 //! @copydoc ::boost::intrusive::bstree::insert_equal(reference)
427 iterator insert_equal(reference value)
428 {
429 node_ptr to_insert(this->get_value_traits().to_node_ptr(value));
430 if(safemode_or_autounlink)
431 BOOST_INTRUSIVE_SAFE_HOOK_DEFAULT_ASSERT(node_algorithms::unique(to_insert));
432 std::size_t max_tree_size = (std::size_t)this->max_tree_size_;
433 node_ptr p = node_algorithms::insert_equal_upper_bound
434 (this->tree_type::header_ptr(), to_insert, this->key_node_comp(this->key_comp())
435 , (size_type)this->size(), this->get_h_alpha_func(), max_tree_size);
436 this->tree_type::sz_traits().increment();
437 this->max_tree_size_ = (size_type)max_tree_size;
438 return iterator(p, this->priv_value_traits_ptr());
439 }
440
441 //! @copydoc ::boost::intrusive::bstree::insert_equal(const_iterator,reference)
442 iterator insert_equal(const_iterator hint, reference value)
443 {
444 node_ptr to_insert(this->get_value_traits().to_node_ptr(value));
445 if(safemode_or_autounlink)
446 BOOST_INTRUSIVE_SAFE_HOOK_DEFAULT_ASSERT(node_algorithms::unique(to_insert));
447 std::size_t max_tree_size = (std::size_t)this->max_tree_size_;
448 node_ptr p = node_algorithms::insert_equal
449 ( this->tree_type::header_ptr(), hint.pointed_node(), to_insert, this->key_node_comp(this->key_comp())
450 , (std::size_t)this->size(), this->get_h_alpha_func(), max_tree_size);
451 this->tree_type::sz_traits().increment();
452 this->max_tree_size_ = (size_type)max_tree_size;
453 return iterator(p, this->priv_value_traits_ptr());
454 }
455
456 //! @copydoc ::boost::intrusive::bstree::insert_equal(Iterator,Iterator)
457 template<class Iterator>
458 void insert_equal(Iterator b, Iterator e)
459 {
460 iterator iend(this->end());
461 for (; b != e; ++b)
462 this->insert_equal(iend, *b);
463 }
464
465 //! @copydoc ::boost::intrusive::bstree::insert_unique(reference)
466 std::pair<iterator, bool> insert_unique(reference value)
467 {
468 insert_commit_data commit_data;
469 std::pair<iterator, bool> ret = this->insert_unique_check
470 (key_of_value()(value), this->key_comp(), commit_data);
471 if(!ret.second)
472 return ret;
473 return std::pair<iterator, bool> (this->insert_unique_commit(value, commit_data), true);
474 }
475
476 //! @copydoc ::boost::intrusive::bstree::insert_unique(const_iterator,reference)
477 iterator insert_unique(const_iterator hint, reference value)
478 {
479 insert_commit_data commit_data;
480 std::pair<iterator, bool> ret = this->insert_unique_check
481 (hint, key_of_value()(value), this->key_comp(), commit_data);
482 if(!ret.second)
483 return ret.first;
484 return this->insert_unique_commit(value, commit_data);
485 }
486
487 //! @copydoc ::boost::intrusive::bstree::insert_unique_check(const KeyType&,KeyTypeKeyCompare,insert_commit_data&)
488 template<class KeyType, class KeyTypeKeyCompare>
489 std::pair<iterator, bool> insert_unique_check
490 (const KeyType &key, KeyTypeKeyCompare comp, insert_commit_data &commit_data)
491 {
492 std::pair<node_ptr, bool> ret =
493 node_algorithms::insert_unique_check
494 (this->tree_type::header_ptr(), key, this->key_node_comp(comp), commit_data);
495 return std::pair<iterator, bool>(iterator(ret.first, this->priv_value_traits_ptr()), ret.second);
496 }
497
498 //! @copydoc ::boost::intrusive::bstree::insert_unique_check(const_iterator,const KeyType&,KeyTypeKeyCompare,insert_commit_data&)
499 template<class KeyType, class KeyTypeKeyCompare>
500 std::pair<iterator, bool> insert_unique_check
501 (const_iterator hint, const KeyType &key
502 ,KeyTypeKeyCompare comp, insert_commit_data &commit_data)
503 {
504 std::pair<node_ptr, bool> ret =
505 node_algorithms::insert_unique_check
506 (this->tree_type::header_ptr(), hint.pointed_node(), key, this->key_node_comp(comp), commit_data);
507 return std::pair<iterator, bool>(iterator(ret.first, this->priv_value_traits_ptr()), ret.second);
508 }
509
510 //! @copydoc ::boost::intrusive::bstree::insert_unique_commit
511 iterator insert_unique_commit(reference value, const insert_commit_data &commit_data)
512 {
513 node_ptr to_insert(this->get_value_traits().to_node_ptr(value));
514 if(safemode_or_autounlink)
515 BOOST_INTRUSIVE_SAFE_HOOK_DEFAULT_ASSERT(node_algorithms::unique(to_insert));
516 std::size_t max_tree_size = (std::size_t)this->max_tree_size_;
517 node_algorithms::insert_unique_commit
518 ( this->tree_type::header_ptr(), to_insert, commit_data
519 , (std::size_t)this->size(), this->get_h_alpha_func(), max_tree_size);
520 this->tree_type::sz_traits().increment();
521 this->max_tree_size_ = (size_type)max_tree_size;
522 return iterator(to_insert, this->priv_value_traits_ptr());
523 }
524
525 //! @copydoc ::boost::intrusive::bstree::insert_unique(Iterator,Iterator)
526 template<class Iterator>
527 void insert_unique(Iterator b, Iterator e)
528 {
529 if(this->empty()){
530 iterator iend(this->end());
531 for (; b != e; ++b)
532 this->insert_unique(iend, *b);
533 }
534 else{
535 for (; b != e; ++b)
536 this->insert_unique(*b);
537 }
538 }
539
540 //! @copydoc ::boost::intrusive::bstree::insert_before
541 iterator insert_before(const_iterator pos, reference value)
542 {
543 node_ptr to_insert(this->get_value_traits().to_node_ptr(value));
544 if(safemode_or_autounlink)
545 BOOST_INTRUSIVE_SAFE_HOOK_DEFAULT_ASSERT(node_algorithms::unique(to_insert));
546 std::size_t max_tree_size = (std::size_t)this->max_tree_size_;
547 node_ptr p = node_algorithms::insert_before
548 ( this->tree_type::header_ptr(), pos.pointed_node(), to_insert
549 , (size_type)this->size(), this->get_h_alpha_func(), max_tree_size);
550 this->tree_type::sz_traits().increment();
551 this->max_tree_size_ = (size_type)max_tree_size;
552 return iterator(p, this->priv_value_traits_ptr());
553 }
554
555 //! @copydoc ::boost::intrusive::bstree::push_back
556 void push_back(reference value)
557 {
558 node_ptr to_insert(this->get_value_traits().to_node_ptr(value));
559 if(safemode_or_autounlink)
560 BOOST_INTRUSIVE_SAFE_HOOK_DEFAULT_ASSERT(node_algorithms::unique(to_insert));
561 std::size_t max_tree_size = (std::size_t)this->max_tree_size_;
562 node_algorithms::push_back
563 ( this->tree_type::header_ptr(), to_insert
564 , (size_type)this->size(), this->get_h_alpha_func(), max_tree_size);
565 this->tree_type::sz_traits().increment();
566 this->max_tree_size_ = (size_type)max_tree_size;
567 }
568
569 //! @copydoc ::boost::intrusive::bstree::push_front
570 void push_front(reference value)
571 {
572 node_ptr to_insert(this->get_value_traits().to_node_ptr(value));
573 if(safemode_or_autounlink)
574 BOOST_INTRUSIVE_SAFE_HOOK_DEFAULT_ASSERT(node_algorithms::unique(to_insert));
575 std::size_t max_tree_size = (std::size_t)this->max_tree_size_;
576 node_algorithms::push_front
577 ( this->tree_type::header_ptr(), to_insert
578 , (size_type)this->size(), this->get_h_alpha_func(), max_tree_size);
579 this->tree_type::sz_traits().increment();
580 this->max_tree_size_ = (size_type)max_tree_size;
581 }
582
583
584 //! @copydoc ::boost::intrusive::bstree::erase(const_iterator)
585 iterator erase(const_iterator i)
586 {
587 const_iterator ret(i);
588 ++ret;
589 node_ptr to_erase(i.pointed_node());
590 if(safemode_or_autounlink)
591 BOOST_INTRUSIVE_SAFE_HOOK_DEFAULT_ASSERT(!node_algorithms::unique(to_erase));
592 std::size_t max_tree_size = this->max_tree_size_;
593 node_algorithms::erase
594 ( this->tree_type::header_ptr(), to_erase, (std::size_t)this->size()
595 , max_tree_size, this->get_alpha_by_max_size_func());
596 this->max_tree_size_ = (size_type)max_tree_size;
597 this->tree_type::sz_traits().decrement();
598 if(safemode_or_autounlink)
599 node_algorithms::init(to_erase);
600 return ret.unconst();
601 }
602
603 //! @copydoc ::boost::intrusive::bstree::erase(const_iterator,const_iterator)
604 iterator erase(const_iterator b, const_iterator e)
605 { size_type n; return private_erase(b, e, n); }
606
607 //! @copydoc ::boost::intrusive::bstree::erase(const key_type &)
608 size_type erase(const key_type &key)
609 { return this->erase(key, this->key_comp()); }
610
611 //! @copydoc ::boost::intrusive::bstree::erase(const KeyType&,KeyTypeKeyCompare)
612 template<class KeyType, class KeyTypeKeyCompare>
613 BOOST_INTRUSIVE_DOC1ST(size_type
614 , typename detail::disable_if_convertible<KeyTypeKeyCompare BOOST_INTRUSIVE_I const_iterator BOOST_INTRUSIVE_I size_type>::type)
615 erase(const KeyType& key, KeyTypeKeyCompare comp)
616 {
617 std::pair<iterator,iterator> p = this->equal_range(key, comp);
618 size_type n;
619 private_erase(p.first, p.second, n);
620 return n;
621 }
622
623 //! @copydoc ::boost::intrusive::bstree::erase_and_dispose(const_iterator,Disposer)
624 template<class Disposer>
625 iterator erase_and_dispose(const_iterator i, Disposer disposer)
626 {
627 node_ptr to_erase(i.pointed_node());
628 iterator ret(this->erase(i));
629 disposer(this->get_value_traits().to_value_ptr(to_erase));
630 return ret;
631 }
632
633 #if !defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED)
634 template<class Disposer>
635 iterator erase_and_dispose(iterator i, Disposer disposer)
636 { return this->erase_and_dispose(const_iterator(i), disposer); }
637 #endif
638
639 //! @copydoc ::boost::intrusive::bstree::erase_and_dispose(const_iterator,const_iterator,Disposer)
640 template<class Disposer>
641 iterator erase_and_dispose(const_iterator b, const_iterator e, Disposer disposer)
642 { size_type n; return private_erase(b, e, n, disposer); }
643
644 //! @copydoc ::boost::intrusive::bstree::erase_and_dispose(const key_type &, Disposer)
645 template<class Disposer>
646 size_type erase_and_dispose(const key_type &key, Disposer disposer)
647 {
648 std::pair<iterator,iterator> p = this->equal_range(key);
649 size_type n;
650 private_erase(p.first, p.second, n, disposer);
651 return n;
652 }
653
654 //! @copydoc ::boost::intrusive::bstree::erase_and_dispose(const KeyType&,KeyTypeKeyCompare,Disposer)
655 template<class KeyType, class KeyTypeKeyCompare, class Disposer>
656 BOOST_INTRUSIVE_DOC1ST(size_type
657 , typename detail::disable_if_convertible<KeyTypeKeyCompare BOOST_INTRUSIVE_I const_iterator BOOST_INTRUSIVE_I size_type>::type)
658 erase_and_dispose(const KeyType& key, KeyTypeKeyCompare comp, Disposer disposer)
659 {
660 std::pair<iterator,iterator> p = this->equal_range(key, comp);
661 size_type n;
662 private_erase(p.first, p.second, n, disposer);
663 return n;
664 }
665
666 //! @copydoc ::boost::intrusive::bstree::clear
667 void clear()
668 {
669 tree_type::clear();
670 this->max_tree_size_ = 0;
671 }
672
673 //! @copydoc ::boost::intrusive::bstree::clear_and_dispose
674 template<class Disposer>
675 void clear_and_dispose(Disposer disposer)
676 {
677 tree_type::clear_and_dispose(disposer);
678 this->max_tree_size_ = 0;
679 }
680
681 #ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED
682 //! @copydoc ::boost::intrusive::bstree::count(const key_type &)const
683 size_type count(const key_type &key) const;
684
685 //! @copydoc ::boost::intrusive::bstree::count(const KeyType&,KeyTypeKeyCompare)const
686 template<class KeyType, class KeyTypeKeyCompare>
687 size_type count(const KeyType& key, KeyTypeKeyCompare comp) const;
688
689 //! @copydoc ::boost::intrusive::bstree::lower_bound(const key_type &)
690 iterator lower_bound(const key_type &key);
691
692 //! @copydoc ::boost::intrusive::bstree::lower_bound(const KeyType&,KeyTypeKeyCompare)
693 template<class KeyType, class KeyTypeKeyCompare>
694 iterator lower_bound(const KeyType& key, KeyTypeKeyCompare comp);
695
696 //! @copydoc ::boost::intrusive::bstree::lower_bound(const key_type &)const
697 const_iterator lower_bound(const key_type &key) const;
698
699 //! @copydoc ::boost::intrusive::bstree::lower_bound(const KeyType&,KeyTypeKeyCompare)const
700 template<class KeyType, class KeyTypeKeyCompare>
701 const_iterator lower_bound(const KeyType& key, KeyTypeKeyCompare comp) const;
702
703 //! @copydoc ::boost::intrusive::bstree::upper_bound(const key_type &)
704 iterator upper_bound(const key_type &key);
705
706 //! @copydoc ::boost::intrusive::bstree::upper_bound(const KeyType&,KeyTypeKeyCompare)
707 template<class KeyType, class KeyTypeKeyCompare>
708 iterator upper_bound(const KeyType& key, KeyTypeKeyCompare comp);
709
710 //! @copydoc ::boost::intrusive::bstree::upper_bound(const key_type &)const
711 const_iterator upper_bound(const key_type &key) const;
712
713 //! @copydoc ::boost::intrusive::bstree::upper_bound(const KeyType&,KeyTypeKeyCompare)const
714 template<class KeyType, class KeyTypeKeyCompare>
715 const_iterator upper_bound(const KeyType& key, KeyTypeKeyCompare comp) const;
716
717 //! @copydoc ::boost::intrusive::bstree::find(const key_type &)
718 iterator find(const key_type &key);
719
720 //! @copydoc ::boost::intrusive::bstree::find(const KeyType&,KeyTypeKeyCompare)
721 template<class KeyType, class KeyTypeKeyCompare>
722 iterator find(const KeyType& key, KeyTypeKeyCompare comp);
723
724 //! @copydoc ::boost::intrusive::bstree::find(const key_type &)const
725 const_iterator find(const key_type &key) const;
726
727 //! @copydoc ::boost::intrusive::bstree::find(const KeyType&,KeyTypeKeyCompare)const
728 template<class KeyType, class KeyTypeKeyCompare>
729 const_iterator find(const KeyType& key, KeyTypeKeyCompare comp) const;
730
731 //! @copydoc ::boost::intrusive::bstree::equal_range(const key_type &)
732 std::pair<iterator,iterator> equal_range(const key_type &key);
733
734 //! @copydoc ::boost::intrusive::bstree::equal_range(const KeyType&,KeyTypeKeyCompare)
735 template<class KeyType, class KeyTypeKeyCompare>
736 std::pair<iterator,iterator> equal_range(const KeyType& key, KeyTypeKeyCompare comp);
737
738 //! @copydoc ::boost::intrusive::bstree::equal_range(const key_type &)const
739 std::pair<const_iterator, const_iterator>
740 equal_range(const key_type &key) const;
741
742 //! @copydoc ::boost::intrusive::bstree::equal_range(const KeyType&,KeyTypeKeyCompare)const
743 template<class KeyType, class KeyTypeKeyCompare>
744 std::pair<const_iterator, const_iterator>
745 equal_range(const KeyType& key, KeyTypeKeyCompare comp) const;
746
747 //! @copydoc ::boost::intrusive::bstree::bounded_range(const key_type &,const key_type &,bool,bool)
748 std::pair<iterator,iterator> bounded_range
749 (const key_type &lower_key, const key_type &upper_key, bool left_closed, bool right_closed);
750
751 //! @copydoc ::boost::intrusive::bstree::bounded_range(const KeyType&,const KeyType&,KeyTypeKeyCompare,bool,bool)
752 template<class KeyType, class KeyTypeKeyCompare>
753 std::pair<iterator,iterator> bounded_range
754 (const KeyType& lower_key, const KeyType& upper_key, KeyTypeKeyCompare comp, bool left_closed, bool right_closed);
755
756 //! @copydoc ::boost::intrusive::bstree::bounded_range(const key_type &,const key_type &,bool,bool)const
757 std::pair<const_iterator, const_iterator>
758 bounded_range(const key_type &lower_key, const key_type &upper_key, bool left_closed, bool right_closed) const;
759
760 //! @copydoc ::boost::intrusive::bstree::bounded_range(const KeyType&,const KeyType&,KeyTypeKeyCompare,bool,bool)const
761 template<class KeyType, class KeyTypeKeyCompare>
762 std::pair<const_iterator, const_iterator> bounded_range
763 (const KeyType& lower_key, const KeyType& upper_key, KeyTypeKeyCompare comp, bool left_closed, bool right_closed) const;
764
765 //! @copydoc ::boost::intrusive::bstree::s_iterator_to(reference)
766 static iterator s_iterator_to(reference value);
767
768 //! @copydoc ::boost::intrusive::bstree::s_iterator_to(const_reference)
769 static const_iterator s_iterator_to(const_reference value);
770
771 //! @copydoc ::boost::intrusive::bstree::iterator_to(reference)
772 iterator iterator_to(reference value);
773
774 //! @copydoc ::boost::intrusive::bstree::iterator_to(const_reference)const
775 const_iterator iterator_to(const_reference value) const;
776
777 //! @copydoc ::boost::intrusive::bstree::init_node(reference)
778 static void init_node(reference value);
779
780 //! @copydoc ::boost::intrusive::bstree::unlink_leftmost_without_rebalance
781 pointer unlink_leftmost_without_rebalance();
782
783 //! @copydoc ::boost::intrusive::bstree::replace_node
784 void replace_node(iterator replace_this, reference with_this);
785
786 //! @copydoc ::boost::intrusive::bstree::remove_node
787 void remove_node(reference value);
788
789 //! @copydoc ::boost::intrusive::bstree::rebalance
790 void rebalance();
791
792 //! @copydoc ::boost::intrusive::bstree::rebalance_subtree
793 iterator rebalance_subtree(iterator root);
794
795 friend bool operator< (const sgtree_impl &x, const sgtree_impl &y);
796
797 friend bool operator==(const sgtree_impl &x, const sgtree_impl &y);
798
799 friend bool operator!= (const sgtree_impl &x, const sgtree_impl &y);
800
801 friend bool operator>(const sgtree_impl &x, const sgtree_impl &y);
802
803 friend bool operator<=(const sgtree_impl &x, const sgtree_impl &y);
804
805 friend bool operator>=(const sgtree_impl &x, const sgtree_impl &y);
806
807 friend void swap(sgtree_impl &x, sgtree_impl &y);
808
809 #endif //#ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED
810
811 //! <b>Returns</b>: The balance factor (alpha) used in this tree
812 //!
813 //! <b>Throws</b>: Nothing.
814 //!
815 //! <b>Complexity</b>: Constant.
816 float balance_factor() const
817 { return this->get_alpha_traits().get_alpha(); }
818
819 //! <b>Requires</b>: new_alpha must be a value between 0.5 and 1.0
820 //!
821 //! <b>Effects</b>: Establishes a new balance factor (alpha) and rebalances
822 //! the tree if the new balance factor is stricter (less) than the old factor.
823 //!
824 //! <b>Throws</b>: Nothing.
825 //!
826 //! <b>Complexity</b>: Linear to the elements in the subtree.
827 void balance_factor(float new_alpha)
828 {
829 //The alpha factor CAN't be changed if the fixed, floating operation-less
830 //1/sqrt(2) alpha factor option is activated
831 BOOST_STATIC_ASSERT((floating_point));
832 BOOST_INTRUSIVE_INVARIANT_ASSERT((new_alpha > 0.5f && new_alpha < 1.0f));
833 if(new_alpha >= 0.5f && new_alpha < 1.0f){
834 float old_alpha = this->get_alpha_traits().get_alpha();
835 this->get_alpha_traits().set_alpha(new_alpha);
836 if(new_alpha < old_alpha){
837 this->max_tree_size_ = this->size();
838 this->rebalance();
839 }
840 }
841 }
842
843 /// @cond
844 private:
845 template<class Disposer>
846 iterator private_erase(const_iterator b, const_iterator e, size_type &n, Disposer disposer)
847 {
848 for(n = 0; b != e; ++n)
849 this->erase_and_dispose(b++, disposer);
850 return b.unconst();
851 }
852
853 iterator private_erase(const_iterator b, const_iterator e, size_type &n)
854 {
855 for(n = 0; b != e; ++n)
856 this->erase(b++);
857 return b.unconst();
858 }
859 /// @endcond
860};
861
862
863//! Helper metafunction to define a \c sgtree that yields to the same type when the
864//! same options (either explicitly or implicitly) are used.
865#if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED) || defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES)
866template<class T, class ...Options>
867#else
868template<class T, class O1 = void, class O2 = void
869 , class O3 = void, class O4 = void
870 , class O5 = void, class O6 = void>
871#endif
872struct make_sgtree
873{
874 /// @cond
875 typedef typename pack_options
876 < sgtree_defaults,
877 #if !defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES)
878 O1, O2, O3, O4, O5, O6
879 #else
880 Options...
881 #endif
882 >::type packed_options;
883
884 typedef typename detail::get_value_traits
885 <T, typename packed_options::proto_value_traits>::type value_traits;
886
887 typedef sgtree_impl
888 < value_traits
889 , typename packed_options::key_of_value
890 , typename packed_options::compare
891 , typename packed_options::size_type
892 , packed_options::floating_point
893 , typename packed_options::header_holder_type
894 > implementation_defined;
895 /// @endcond
896 typedef implementation_defined type;
897};
898
899
900#ifndef BOOST_INTRUSIVE_DOXYGEN_INVOKED
901
902#if !defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES)
903template<class T, class O1, class O2, class O3, class O4, class O5, class O6>
904#else
905template<class T, class ...Options>
906#endif
907class sgtree
908 : public make_sgtree<T,
909 #if !defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES)
910 O1, O2, O3, O4, O5, O6
911 #else
912 Options...
913 #endif
914 >::type
915{
916 typedef typename make_sgtree
917 <T,
918 #if !defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES)
919 O1, O2, O3, O4, O5, O6
920 #else
921 Options...
922 #endif
923 >::type Base;
924 BOOST_MOVABLE_BUT_NOT_COPYABLE(sgtree)
925
926 public:
927 typedef typename Base::key_compare key_compare;
928 typedef typename Base::value_traits value_traits;
929 typedef typename Base::iterator iterator;
930 typedef typename Base::const_iterator const_iterator;
931 typedef typename Base::reverse_iterator reverse_iterator;
932 typedef typename Base::const_reverse_iterator const_reverse_iterator;
933
934 //Assert if passed value traits are compatible with the type
935 BOOST_STATIC_ASSERT((detail::is_same<typename value_traits::value_type, T>::value));
936
937 explicit sgtree( const key_compare &cmp = key_compare()
938 , const value_traits &v_traits = value_traits())
939 : Base(cmp, v_traits)
940 {}
941
942 template<class Iterator>
943 sgtree( bool unique, Iterator b, Iterator e
944 , const key_compare &cmp = key_compare()
945 , const value_traits &v_traits = value_traits())
946 : Base(unique, b, e, cmp, v_traits)
947 {}
948
949 sgtree(BOOST_RV_REF(sgtree) x)
950 : Base(BOOST_MOVE_BASE(Base, x))
951 {}
952
953 sgtree& operator=(BOOST_RV_REF(sgtree) x)
954 { return static_cast<sgtree &>(this->Base::operator=(BOOST_MOVE_BASE(Base, x))); }
955
956 template <class Cloner, class Disposer>
957 void clone_from(const sgtree &src, Cloner cloner, Disposer disposer)
958 { Base::clone_from(src, cloner, disposer); }
959
960 template <class Cloner, class Disposer>
961 void clone_from(BOOST_RV_REF(sgtree) src, Cloner cloner, Disposer disposer)
962 { Base::clone_from(BOOST_MOVE_BASE(Base, src), cloner, disposer); }
963
964 static sgtree &container_from_end_iterator(iterator end_iterator)
965 { return static_cast<sgtree &>(Base::container_from_end_iterator(end_iterator)); }
966
967 static const sgtree &container_from_end_iterator(const_iterator end_iterator)
968 { return static_cast<const sgtree &>(Base::container_from_end_iterator(end_iterator)); }
969
970 static sgtree &container_from_iterator(iterator it)
971 { return static_cast<sgtree &>(Base::container_from_iterator(it)); }
972
973 static const sgtree &container_from_iterator(const_iterator it)
974 { return static_cast<const sgtree &>(Base::container_from_iterator(it)); }
975};
976
977#endif
978
979} //namespace intrusive
980} //namespace boost
981
982#include <boost/intrusive/detail/config_end.hpp>
983
984#endif //BOOST_INTRUSIVE_SGTREE_HPP
985

source code of boost/boost/intrusive/sgtree.hpp