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 // The implementation of splay trees is based on the article and code published 13 // in C++ Users Journal "Implementing Splay Trees in C++" (September 1, 2005). 14 // 15 // The splay code has been modified and (supposedly) improved by Ion Gaztanaga. 16 // 17 // Here is the copyright notice of the original file containing the splay code: 18 // 19 // splay_tree.h -- implementation of a STL compatible splay tree. 20 // 21 // Copyright (c) 2004 Ralf Mattethat 22 // 23 // Permission to copy, use, modify, sell and distribute this software 24 // is granted provided this copyright notice appears in all copies. 25 // This software is provided "as is" without express or implied 26 // warranty, and with no claim as to its suitability for any purpose. 27 // 28 ///////////////////////////////////////////////////////////////////////////// 29 30 #ifndef BOOST_INTRUSIVE_SPLAYTREE_ALGORITHMS_HPP 31 #define BOOST_INTRUSIVE_SPLAYTREE_ALGORITHMS_HPP 32 33 #include <boost/intrusive/detail/config_begin.hpp> 34 #include <boost/intrusive/intrusive_fwd.hpp> 35 #include <boost/intrusive/detail/assert.hpp> 36 #include <boost/intrusive/detail/algo_type.hpp> 37 #include <boost/intrusive/detail/uncast.hpp> 38 #include <boost/intrusive/bstree_algorithms.hpp> 39 40 #include <cstddef> 41 42 #if defined(BOOST_HAS_PRAGMA_ONCE) 43 # pragma once 44 #endif 45 46 namespace boost { 47 namespace intrusive { 48 49 /// @cond 50 namespace detail { 51 52 template<class NodeTraits> 53 struct splaydown_assemble_and_fix_header 54 { 55 typedef typename NodeTraits::node_ptr node_ptr; 56 splaydown_assemble_and_fix_headerboost::intrusive::detail::splaydown_assemble_and_fix_header57 splaydown_assemble_and_fix_header(const node_ptr & t, const node_ptr & header, const node_ptr &leftmost, const node_ptr &rightmost) 58 : t_(t) 59 , null_node_(header) 60 , l_(null_node_) 61 , r_(null_node_) 62 , leftmost_(leftmost) 63 , rightmost_(rightmost) 64 {} 65 ~splaydown_assemble_and_fix_headerboost::intrusive::detail::splaydown_assemble_and_fix_header66 ~splaydown_assemble_and_fix_header() 67 { 68 this->assemble(); 69 70 //Now recover the original header except for the 71 //splayed root node. 72 //"t_" is the current root and "null_node_" is the header node 73 NodeTraits::set_parent(null_node_, t_); 74 NodeTraits::set_parent(t_, null_node_); 75 //Recover leftmost/rightmost pointers 76 NodeTraits::set_left (null_node_, leftmost_); 77 NodeTraits::set_right(null_node_, rightmost_); 78 } 79 80 private: 81 assembleboost::intrusive::detail::splaydown_assemble_and_fix_header82 void assemble() 83 { 84 //procedure assemble; 85 // left(r), right(l) := right(t), left(t); 86 // left(t), right(t) := right(null), left(null); 87 //end assemble; 88 { // left(r), right(l) := right(t), left(t); 89 90 node_ptr const old_t_left = NodeTraits::get_left(t_); 91 node_ptr const old_t_right = NodeTraits::get_right(t_); 92 NodeTraits::set_right(l_, old_t_left); 93 NodeTraits::set_left (r_, old_t_right); 94 if(old_t_left){ 95 NodeTraits::set_parent(old_t_left, l_); 96 } 97 if(old_t_right){ 98 NodeTraits::set_parent(old_t_right, r_); 99 } 100 } 101 { // left(t), right(t) := right(null), left(null); 102 node_ptr const null_right = NodeTraits::get_right(null_node_); 103 node_ptr const null_left = NodeTraits::get_left(null_node_); 104 NodeTraits::set_left (t_, null_right); 105 NodeTraits::set_right(t_, null_left); 106 if(null_right){ 107 NodeTraits::set_parent(null_right, t_); 108 } 109 if(null_left){ 110 NodeTraits::set_parent(null_left, t_); 111 } 112 } 113 } 114 115 public: 116 node_ptr t_, null_node_, l_, r_, leftmost_, rightmost_; 117 }; 118 119 } //namespace detail { 120 /// @endcond 121 122 //! A splay tree is an implementation of a binary search tree. The tree is 123 //! self balancing using the splay algorithm as described in 124 //! 125 //! "Self-Adjusting Binary Search Trees 126 //! by Daniel Dominic Sleator and Robert Endre Tarjan 127 //! AT&T Bell Laboratories, Murray Hill, NJ 128 //! Journal of the ACM, Vol 32, no 3, July 1985, pp 652-686 129 //! 130 //! splaytree_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 //! <b>Static functions</b>: 143 //! 144 //! <tt>static node_ptr get_parent(const_node_ptr n);</tt> 145 //! 146 //! <tt>static void set_parent(node_ptr n, node_ptr parent);</tt> 147 //! 148 //! <tt>static node_ptr get_left(const_node_ptr n);</tt> 149 //! 150 //! <tt>static void set_left(node_ptr n, node_ptr left);</tt> 151 //! 152 //! <tt>static node_ptr get_right(const_node_ptr n);</tt> 153 //! 154 //! <tt>static void set_right(node_ptr n, node_ptr right);</tt> 155 template<class NodeTraits> 156 class splaytree_algorithms 157 #ifndef BOOST_INTRUSIVE_DOXYGEN_INVOKED 158 : public bstree_algorithms<NodeTraits> 159 #endif 160 { 161 /// @cond 162 private: 163 typedef bstree_algorithms<NodeTraits> bstree_algo; 164 /// @endcond 165 166 public: 167 typedef typename NodeTraits::node node; 168 typedef NodeTraits node_traits; 169 typedef typename NodeTraits::node_ptr node_ptr; 170 typedef typename NodeTraits::const_node_ptr const_node_ptr; 171 172 //! This type is the information that will be 173 //! filled by insert_unique_check 174 typedef typename bstree_algo::insert_commit_data insert_commit_data; 175 176 public: 177 #ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED 178 //! @copydoc ::boost::intrusive::bstree_algorithms::get_header(const const_node_ptr&) 179 static node_ptr get_header(const const_node_ptr & n); 180 181 //! @copydoc ::boost::intrusive::bstree_algorithms::begin_node 182 static node_ptr begin_node(const const_node_ptr & header); 183 184 //! @copydoc ::boost::intrusive::bstree_algorithms::end_node 185 static node_ptr end_node(const const_node_ptr & header); 186 187 //! @copydoc ::boost::intrusive::bstree_algorithms::swap_tree 188 static void swap_tree(const node_ptr & header1, const node_ptr & header2); 189 190 //! @copydoc ::boost::intrusive::bstree_algorithms::swap_nodes(const node_ptr&,const node_ptr&) 191 static void swap_nodes(const node_ptr & node1, const node_ptr & node2); 192 193 //! @copydoc ::boost::intrusive::bstree_algorithms::swap_nodes(const node_ptr&,const node_ptr&,const node_ptr&,const node_ptr&) 194 static void swap_nodes(const node_ptr & node1, const node_ptr & header1, const node_ptr & node2, const node_ptr & header2); 195 196 //! @copydoc ::boost::intrusive::bstree_algorithms::replace_node(const node_ptr&,const node_ptr&) 197 static void replace_node(const node_ptr & node_to_be_replaced, const node_ptr & new_node); 198 199 //! @copydoc ::boost::intrusive::bstree_algorithms::replace_node(const node_ptr&,const node_ptr&,const node_ptr&) 200 static void replace_node(const node_ptr & node_to_be_replaced, const node_ptr & header, const node_ptr & new_node); 201 202 //! @copydoc ::boost::intrusive::bstree_algorithms::unlink(const node_ptr&) 203 static void unlink(const node_ptr & node); 204 205 //! @copydoc ::boost::intrusive::bstree_algorithms::unlink_leftmost_without_rebalance 206 static node_ptr unlink_leftmost_without_rebalance(const node_ptr & header); 207 208 //! @copydoc ::boost::intrusive::bstree_algorithms::unique(const const_node_ptr&) 209 static bool unique(const const_node_ptr & node); 210 211 //! @copydoc ::boost::intrusive::bstree_algorithms::size(const const_node_ptr&) 212 static std::size_t size(const const_node_ptr & header); 213 214 //! @copydoc ::boost::intrusive::bstree_algorithms::next_node(const node_ptr&) 215 static node_ptr next_node(const node_ptr & node); 216 217 //! @copydoc ::boost::intrusive::bstree_algorithms::prev_node(const node_ptr&) 218 static node_ptr prev_node(const node_ptr & node); 219 220 //! @copydoc ::boost::intrusive::bstree_algorithms::init(const node_ptr&) 221 static void init(const node_ptr & node); 222 223 //! @copydoc ::boost::intrusive::bstree_algorithms::init_header(const node_ptr&) 224 static void init_header(const node_ptr & header); 225 226 #endif //#ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED 227 228 //! @copydoc ::boost::intrusive::bstree_algorithms::erase(const node_ptr&,const node_ptr&) 229 //! Additional notes: the previous node of z is splayed to speed up range deletions. erase(const node_ptr & header,const node_ptr & z)230 static void erase(const node_ptr & header, const node_ptr & z) 231 { 232 //posibility 1 233 if(NodeTraits::get_left(z)){ 234 splay_up(bstree_algo::prev_node(z), header); 235 } 236 237 //possibility 2 238 //if(NodeTraits::get_left(z)){ 239 // node_ptr l = NodeTraits::get_left(z); 240 // splay_up(l, header); 241 //} 242 243 //if(NodeTraits::get_left(z)){ 244 // node_ptr l = bstree_algo::prev_node(z); 245 // splay_up_impl(l, z); 246 //} 247 248 //possibility 4 249 //splay_up(z, header); 250 251 bstree_algo::erase(header, z); 252 } 253 254 #ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED 255 //! @copydoc ::boost::intrusive::bstree_algorithms::clone(const const_node_ptr&,const node_ptr&,Cloner,Disposer) 256 template <class Cloner, class Disposer> 257 static void clone 258 (const const_node_ptr & source_header, const node_ptr & target_header, Cloner cloner, Disposer disposer); 259 260 //! @copydoc ::boost::intrusive::bstree_algorithms::clear_and_dispose(const node_ptr&,Disposer) 261 template<class Disposer> 262 static void clear_and_dispose(const node_ptr & header, Disposer disposer); 263 264 #endif //#ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED 265 //! @copydoc ::boost::intrusive::bstree_algorithms::count(const const_node_ptr&,const KeyType&,KeyNodePtrCompare) 266 //! Additional notes: an element with key `key` is splayed. 267 template<class KeyType, class KeyNodePtrCompare> count(const node_ptr & header,const KeyType & key,KeyNodePtrCompare comp)268 static std::size_t count 269 (const node_ptr & header, const KeyType &key, KeyNodePtrCompare comp) 270 { 271 std::pair<node_ptr, node_ptr> ret = equal_range(header, key, comp); 272 std::size_t n = 0; 273 while(ret.first != ret.second){ 274 ++n; 275 ret.first = next_node(ret.first); 276 } 277 return n; 278 } 279 280 //! @copydoc ::boost::intrusive::bstree_algorithms::count(const const_node_ptr&,const KeyType&,KeyNodePtrCompare) 281 //! Additional note: no splaying is performed 282 template<class KeyType, class KeyNodePtrCompare> count(const const_node_ptr & header,const KeyType & key,KeyNodePtrCompare comp)283 static std::size_t count 284 (const const_node_ptr & header, const KeyType &key, KeyNodePtrCompare comp) 285 { return bstree_algo::count(header, key, comp); } 286 287 //! @copydoc ::boost::intrusive::bstree_algorithms::lower_bound(const const_node_ptr&,const KeyType&,KeyNodePtrCompare) 288 //! Additional notes: the first node of the range is splayed. 289 template<class KeyType, class KeyNodePtrCompare> lower_bound(const node_ptr & header,const KeyType & key,KeyNodePtrCompare comp)290 static node_ptr lower_bound 291 (const node_ptr & header, const KeyType &key, KeyNodePtrCompare comp) 292 { 293 splay_down(detail::uncast(header), key, comp); 294 node_ptr y = bstree_algo::lower_bound(header, key, comp); 295 //splay_up(y, detail::uncast(header)); 296 return y; 297 } 298 299 //! @copydoc ::boost::intrusive::bstree_algorithms::lower_bound(const const_node_ptr&,const KeyType&,KeyNodePtrCompare) 300 //! Additional note: no splaying is performed 301 template<class KeyType, class KeyNodePtrCompare> lower_bound(const const_node_ptr & header,const KeyType & key,KeyNodePtrCompare comp)302 static node_ptr lower_bound 303 (const const_node_ptr & header, const KeyType &key, KeyNodePtrCompare comp) 304 { return bstree_algo::lower_bound(header, key, comp); } 305 306 //! @copydoc ::boost::intrusive::bstree_algorithms::upper_bound(const const_node_ptr&,const KeyType&,KeyNodePtrCompare) 307 //! Additional notes: the first node of the range is splayed. 308 template<class KeyType, class KeyNodePtrCompare> upper_bound(const node_ptr & header,const KeyType & key,KeyNodePtrCompare comp)309 static node_ptr upper_bound 310 (const node_ptr & header, const KeyType &key, KeyNodePtrCompare comp) 311 { 312 splay_down(detail::uncast(header), key, comp); 313 node_ptr y = bstree_algo::upper_bound(header, key, comp); 314 //splay_up(y, detail::uncast(header)); 315 return y; 316 } 317 318 //! @copydoc ::boost::intrusive::bstree_algorithms::upper_bound(const const_node_ptr&,const KeyType&,KeyNodePtrCompare) 319 //! Additional note: no splaying is performed 320 template<class KeyType, class KeyNodePtrCompare> upper_bound(const const_node_ptr & header,const KeyType & key,KeyNodePtrCompare comp)321 static node_ptr upper_bound 322 (const const_node_ptr & header, const KeyType &key, KeyNodePtrCompare comp) 323 { return bstree_algo::upper_bound(header, key, comp); } 324 325 //! @copydoc ::boost::intrusive::bstree_algorithms::find(const const_node_ptr&, const KeyType&,KeyNodePtrCompare) 326 //! Additional notes: the found node of the lower bound is splayed. 327 template<class KeyType, class KeyNodePtrCompare> find(const node_ptr & header,const KeyType & key,KeyNodePtrCompare comp)328 static node_ptr find 329 (const node_ptr & header, const KeyType &key, KeyNodePtrCompare comp) 330 { 331 splay_down(detail::uncast(header), key, comp); 332 return bstree_algo::find(header, key, comp); 333 } 334 335 //! @copydoc ::boost::intrusive::bstree_algorithms::find(const const_node_ptr&, const KeyType&,KeyNodePtrCompare) 336 //! Additional note: no splaying is performed 337 template<class KeyType, class KeyNodePtrCompare> find(const const_node_ptr & header,const KeyType & key,KeyNodePtrCompare comp)338 static node_ptr find 339 (const const_node_ptr & header, const KeyType &key, KeyNodePtrCompare comp) 340 { return bstree_algo::find(header, key, comp); } 341 342 //! @copydoc ::boost::intrusive::bstree_algorithms::equal_range(const const_node_ptr&,const KeyType&,KeyNodePtrCompare) 343 //! Additional notes: the first node of the range is splayed. 344 template<class KeyType, class KeyNodePtrCompare> equal_range(const node_ptr & header,const KeyType & key,KeyNodePtrCompare comp)345 static std::pair<node_ptr, node_ptr> equal_range 346 (const node_ptr & header, const KeyType &key, KeyNodePtrCompare comp) 347 { 348 splay_down(detail::uncast(header), key, comp); 349 std::pair<node_ptr, node_ptr> ret = bstree_algo::equal_range(header, key, comp); 350 //splay_up(ret.first, detail::uncast(header)); 351 return ret; 352 } 353 354 //! @copydoc ::boost::intrusive::bstree_algorithms::equal_range(const const_node_ptr&,const KeyType&,KeyNodePtrCompare) 355 //! Additional note: no splaying is performed 356 template<class KeyType, class KeyNodePtrCompare> equal_range(const const_node_ptr & header,const KeyType & key,KeyNodePtrCompare comp)357 static std::pair<node_ptr, node_ptr> equal_range 358 (const const_node_ptr & header, const KeyType &key, KeyNodePtrCompare comp) 359 { return bstree_algo::equal_range(header, key, comp); } 360 361 //! @copydoc ::boost::intrusive::bstree_algorithms::lower_bound_range(const const_node_ptr&,const KeyType&,KeyNodePtrCompare) 362 //! Additional notes: the first node of the range is splayed. 363 template<class KeyType, class KeyNodePtrCompare> lower_bound_range(const node_ptr & header,const KeyType & key,KeyNodePtrCompare comp)364 static std::pair<node_ptr, node_ptr> lower_bound_range 365 (const node_ptr & header, const KeyType &key, KeyNodePtrCompare comp) 366 { 367 splay_down(detail::uncast(header), key, comp); 368 std::pair<node_ptr, node_ptr> ret = bstree_algo::lower_bound_range(header, key, comp); 369 //splay_up(ret.first, detail::uncast(header)); 370 return ret; 371 } 372 373 //! @copydoc ::boost::intrusive::bstree_algorithms::lower_bound_range(const const_node_ptr&,const KeyType&,KeyNodePtrCompare) 374 //! Additional note: no splaying is performed 375 template<class KeyType, class KeyNodePtrCompare> lower_bound_range(const const_node_ptr & header,const KeyType & key,KeyNodePtrCompare comp)376 static std::pair<node_ptr, node_ptr> lower_bound_range 377 (const const_node_ptr & header, const KeyType &key, KeyNodePtrCompare comp) 378 { return bstree_algo::lower_bound_range(header, key, comp); } 379 380 //! @copydoc ::boost::intrusive::bstree_algorithms::bounded_range(const const_node_ptr&,const KeyType&,const KeyType&,KeyNodePtrCompare,bool,bool) 381 //! Additional notes: the first node of the range is splayed. 382 template<class KeyType, class KeyNodePtrCompare> bounded_range(const node_ptr & header,const KeyType & lower_key,const KeyType & upper_key,KeyNodePtrCompare comp,bool left_closed,bool right_closed)383 static std::pair<node_ptr, node_ptr> bounded_range 384 (const node_ptr & header, const KeyType &lower_key, const KeyType &upper_key, KeyNodePtrCompare comp 385 , bool left_closed, bool right_closed) 386 { 387 splay_down(detail::uncast(header), lower_key, comp); 388 std::pair<node_ptr, node_ptr> ret = 389 bstree_algo::bounded_range(header, lower_key, upper_key, comp, left_closed, right_closed); 390 //splay_up(ret.first, detail::uncast(header)); 391 return ret; 392 } 393 394 //! @copydoc ::boost::intrusive::bstree_algorithms::bounded_range(const const_node_ptr&,const KeyType&,const KeyType&,KeyNodePtrCompare,bool,bool) 395 //! Additional note: no splaying is performed 396 template<class KeyType, class KeyNodePtrCompare> bounded_range(const const_node_ptr & header,const KeyType & lower_key,const KeyType & upper_key,KeyNodePtrCompare comp,bool left_closed,bool right_closed)397 static std::pair<node_ptr, node_ptr> bounded_range 398 (const const_node_ptr & header, const KeyType &lower_key, const KeyType &upper_key, KeyNodePtrCompare comp 399 , bool left_closed, bool right_closed) 400 { return bstree_algo::bounded_range(header, lower_key, upper_key, comp, left_closed, right_closed); } 401 402 //! @copydoc ::boost::intrusive::bstree_algorithms::insert_equal_upper_bound(const node_ptr&,const node_ptr&,NodePtrCompare) 403 //! Additional note: the inserted node is splayed 404 template<class NodePtrCompare> insert_equal_upper_bound(const node_ptr & header,const node_ptr & new_node,NodePtrCompare comp)405 static node_ptr insert_equal_upper_bound 406 (const node_ptr & header, const node_ptr & new_node, NodePtrCompare comp) 407 { 408 splay_down(header, new_node, comp); 409 return bstree_algo::insert_equal_upper_bound(header, new_node, comp); 410 } 411 412 //! @copydoc ::boost::intrusive::bstree_algorithms::insert_equal_lower_bound(const node_ptr&,const node_ptr&,NodePtrCompare) 413 //! Additional note: the inserted node is splayed 414 template<class NodePtrCompare> insert_equal_lower_bound(const node_ptr & header,const node_ptr & new_node,NodePtrCompare comp)415 static node_ptr insert_equal_lower_bound 416 (const node_ptr & header, const node_ptr & new_node, NodePtrCompare comp) 417 { 418 splay_down(header, new_node, comp); 419 return bstree_algo::insert_equal_lower_bound(header, new_node, comp); 420 } 421 422 //! @copydoc ::boost::intrusive::bstree_algorithms::insert_equal(const node_ptr&,const node_ptr&,const node_ptr&,NodePtrCompare) 423 //! Additional note: the inserted node is splayed 424 template<class NodePtrCompare> insert_equal(const node_ptr & header,const node_ptr & hint,const node_ptr & new_node,NodePtrCompare comp)425 static node_ptr insert_equal 426 (const node_ptr & header, const node_ptr & hint, const node_ptr & new_node, NodePtrCompare comp) 427 { 428 splay_down(header, new_node, comp); 429 return bstree_algo::insert_equal(header, hint, new_node, comp); 430 } 431 432 //! @copydoc ::boost::intrusive::bstree_algorithms::insert_before(const node_ptr&,const node_ptr&,const node_ptr&) 433 //! Additional note: the inserted node is splayed insert_before(const node_ptr & header,const node_ptr & pos,const node_ptr & new_node)434 static node_ptr insert_before 435 (const node_ptr & header, const node_ptr & pos, const node_ptr & new_node) 436 { 437 bstree_algo::insert_before(header, pos, new_node); 438 splay_up(new_node, header); 439 return new_node; 440 } 441 442 //! @copydoc ::boost::intrusive::bstree_algorithms::push_back(const node_ptr&,const node_ptr&) 443 //! Additional note: the inserted node is splayed push_back(const node_ptr & header,const node_ptr & new_node)444 static void push_back(const node_ptr & header, const node_ptr & new_node) 445 { 446 bstree_algo::push_back(header, new_node); 447 splay_up(new_node, header); 448 } 449 450 //! @copydoc ::boost::intrusive::bstree_algorithms::push_front(const node_ptr&,const node_ptr&) 451 //! Additional note: the inserted node is splayed push_front(const node_ptr & header,const node_ptr & new_node)452 static void push_front(const node_ptr & header, const node_ptr & new_node) 453 { 454 bstree_algo::push_front(header, new_node); 455 splay_up(new_node, header); 456 } 457 458 //! @copydoc ::boost::intrusive::bstree_algorithms::insert_unique_check(const const_node_ptr&,const KeyType&,KeyNodePtrCompare,insert_commit_data&) 459 //! Additional note: nodes with the given key are splayed 460 template<class KeyType, class KeyNodePtrCompare> insert_unique_check(const node_ptr & header,const KeyType & key,KeyNodePtrCompare comp,insert_commit_data & commit_data)461 static std::pair<node_ptr, bool> insert_unique_check 462 (const node_ptr & header, const KeyType &key 463 ,KeyNodePtrCompare comp, insert_commit_data &commit_data) 464 { 465 splay_down(header, key, comp); 466 return bstree_algo::insert_unique_check(header, key, comp, commit_data); 467 } 468 469 //! @copydoc ::boost::intrusive::bstree_algorithms::insert_unique_check(const const_node_ptr&,const node_ptr&,const KeyType&,KeyNodePtrCompare,insert_commit_data&) 470 //! Additional note: nodes with the given key are splayed 471 template<class KeyType, class KeyNodePtrCompare> insert_unique_check(const node_ptr & header,const node_ptr & hint,const KeyType & key,KeyNodePtrCompare comp,insert_commit_data & commit_data)472 static std::pair<node_ptr, bool> insert_unique_check 473 (const node_ptr & header, const node_ptr &hint, const KeyType &key 474 ,KeyNodePtrCompare comp, insert_commit_data &commit_data) 475 { 476 splay_down(header, key, comp); 477 return bstree_algo::insert_unique_check(header, hint, key, comp, commit_data); 478 } 479 480 #ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED 481 //! @copydoc ::boost::intrusive::bstree_algorithms::insert_unique_commit(const node_ptr&,const node_ptr&,const insert_commit_data&) 482 static void insert_unique_commit 483 (const node_ptr & header, const node_ptr & new_value, const insert_commit_data &commit_data); 484 485 //! @copydoc ::boost::intrusive::bstree_algorithms::is_header 486 static bool is_header(const const_node_ptr & p); 487 488 //! @copydoc ::boost::intrusive::bstree_algorithms::rebalance 489 static void rebalance(const node_ptr & header); 490 491 //! @copydoc ::boost::intrusive::bstree_algorithms::rebalance_subtree 492 static node_ptr rebalance_subtree(const node_ptr & old_root); 493 494 #endif //#ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED 495 496 // bottom-up splay, use data_ as parent for n | complexity : logarithmic | exception : nothrow splay_up(const node_ptr & node,const node_ptr & header)497 static void splay_up(const node_ptr & node, const node_ptr & header) 498 { priv_splay_up<true>(node, header); } 499 500 // top-down splay | complexity : logarithmic | exception : strong, note A 501 template<class KeyType, class KeyNodePtrCompare> splay_down(const node_ptr & header,const KeyType & key,KeyNodePtrCompare comp,bool * pfound=0)502 static node_ptr splay_down(const node_ptr & header, const KeyType &key, KeyNodePtrCompare comp, bool *pfound = 0) 503 { return priv_splay_down<true>(header, key, comp, pfound); } 504 505 private: 506 507 /// @cond 508 509 // bottom-up splay, use data_ as parent for n | complexity : logarithmic | exception : nothrow 510 template<bool SimpleSplay> priv_splay_up(const node_ptr & node,const node_ptr & header)511 static void priv_splay_up(const node_ptr & node, const node_ptr & header) 512 { 513 // If (node == header) do a splay for the right most node instead 514 // this is to boost performance of equal_range/count on equivalent containers in the case 515 // where there are many equal elements at the end 516 node_ptr n((node == header) ? NodeTraits::get_right(header) : node); 517 node_ptr t(header); 518 519 if( n == t ) return; 520 521 for( ;; ){ 522 node_ptr p(NodeTraits::get_parent(n)); 523 node_ptr g(NodeTraits::get_parent(p)); 524 525 if( p == t ) break; 526 527 if( g == t ){ 528 // zig 529 rotate(n); 530 } 531 else if ((NodeTraits::get_left(p) == n && NodeTraits::get_left(g) == p) || 532 (NodeTraits::get_right(p) == n && NodeTraits::get_right(g) == p) ){ 533 // zig-zig 534 rotate(p); 535 rotate(n); 536 } 537 else { 538 // zig-zag 539 rotate(n); 540 if(!SimpleSplay){ 541 rotate(n); 542 } 543 } 544 } 545 } 546 547 template<bool SimpleSplay, class KeyType, class KeyNodePtrCompare> priv_splay_down(const node_ptr & header,const KeyType & key,KeyNodePtrCompare comp,bool * pfound=0)548 static node_ptr priv_splay_down(const node_ptr & header, const KeyType &key, KeyNodePtrCompare comp, bool *pfound = 0) 549 { 550 //Most splay tree implementations use a dummy/null node to implement. 551 //this function. This has some problems for a generic library like Intrusive: 552 // 553 // * The node might not have a default constructor. 554 // * The default constructor could throw. 555 // 556 //We already have a header node. Leftmost and rightmost nodes of the tree 557 //are not changed when splaying (because the invariants of the tree don't 558 //change) We can back up them, use the header as the null node and 559 //reassign old values after the function has been completed. 560 node_ptr const old_root = NodeTraits::get_parent(header); 561 node_ptr const leftmost = NodeTraits::get_left(header); 562 node_ptr const rightmost = NodeTraits::get_right(header); 563 if(leftmost == rightmost){ //Empty or unique node 564 if(pfound){ 565 *pfound = old_root && !comp(key, old_root) && !comp(old_root, key); 566 } 567 return old_root ? old_root : header; 568 } 569 else{ 570 //Initialize "null node" (the header in our case) 571 NodeTraits::set_left (header, node_ptr()); 572 NodeTraits::set_right(header, node_ptr()); 573 //Class that will backup leftmost/rightmost from header, commit the assemble(), 574 //and will restore leftmost/rightmost to header even if "comp" throws 575 detail::splaydown_assemble_and_fix_header<NodeTraits> commit(old_root, header, leftmost, rightmost); 576 bool found = false; 577 578 for( ;; ){ 579 if(comp(key, commit.t_)){ 580 node_ptr const t_left = NodeTraits::get_left(commit.t_); 581 if(!t_left) 582 break; 583 if(comp(key, t_left)){ 584 bstree_algo::rotate_right_no_parent_fix(commit.t_, t_left); 585 commit.t_ = t_left; 586 if( !NodeTraits::get_left(commit.t_) ) 587 break; 588 link_right(commit.t_, commit.r_); 589 } 590 else{ 591 link_right(commit.t_, commit.r_); 592 if(!SimpleSplay && comp(t_left, key)){ 593 if( !NodeTraits::get_right(commit.t_) ) 594 break; 595 link_left(commit.t_, commit.l_); 596 } 597 } 598 } 599 else if(comp(commit.t_, key)){ 600 node_ptr const t_right = NodeTraits::get_right(commit.t_); 601 if(!t_right) 602 break; 603 604 if(comp(t_right, key)){ 605 bstree_algo::rotate_left_no_parent_fix(commit.t_, t_right); 606 commit.t_ = t_right; 607 if( !NodeTraits::get_right(commit.t_) ) 608 break; 609 link_left(commit.t_, commit.l_); 610 } 611 else{ 612 link_left(commit.t_, commit.l_); 613 if(!SimpleSplay && comp(key, t_right)){ 614 if( !NodeTraits::get_left(commit.t_) ) 615 break; 616 link_right(commit.t_, commit.r_); 617 } 618 } 619 } 620 else{ 621 found = true; 622 break; 623 } 624 } 625 626 //commit.~splaydown_assemble_and_fix_header<NodeTraits>() will first 627 //"assemble()" + link the new root & recover header's leftmost & rightmost 628 if(pfound){ 629 *pfound = found; 630 } 631 return commit.t_; 632 } 633 } 634 635 // break link to left child node and attach it to left tree pointed to by l | complexity : constant | exception : nothrow link_left(node_ptr & t,node_ptr & l)636 static void link_left(node_ptr & t, node_ptr & l) 637 { 638 //procedure link_left; 639 // t, l, right(l) := right(t), t, t 640 //end link_left 641 NodeTraits::set_right(l, t); 642 NodeTraits::set_parent(t, l); 643 l = t; 644 t = NodeTraits::get_right(t); 645 } 646 647 // break link to right child node and attach it to right tree pointed to by r | complexity : constant | exception : nothrow link_right(node_ptr & t,node_ptr & r)648 static void link_right(node_ptr & t, node_ptr & r) 649 { 650 //procedure link_right; 651 // t, r, left(r) := left(t), t, t 652 //end link_right; 653 NodeTraits::set_left(r, t); 654 NodeTraits::set_parent(t, r); 655 r = t; 656 t = NodeTraits::get_left(t); 657 } 658 659 // rotate n with its parent | complexity : constant | exception : nothrow rotate(const node_ptr & n)660 static void rotate(const node_ptr & n) 661 { 662 //procedure rotate_left; 663 // t, right(t), left(right(t)) := right(t), left(right(t)), t 664 //end rotate_left; 665 node_ptr p = NodeTraits::get_parent(n); 666 node_ptr g = NodeTraits::get_parent(p); 667 //Test if g is header before breaking tree 668 //invariants that would make is_header invalid 669 bool g_is_header = bstree_algo::is_header(g); 670 671 if(NodeTraits::get_left(p) == n){ 672 NodeTraits::set_left(p, NodeTraits::get_right(n)); 673 if(NodeTraits::get_left(p)) 674 NodeTraits::set_parent(NodeTraits::get_left(p), p); 675 NodeTraits::set_right(n, p); 676 } 677 else{ // must be ( p->right == n ) 678 NodeTraits::set_right(p, NodeTraits::get_left(n)); 679 if(NodeTraits::get_right(p)) 680 NodeTraits::set_parent(NodeTraits::get_right(p), p); 681 NodeTraits::set_left(n, p); 682 } 683 684 NodeTraits::set_parent(p, n); 685 NodeTraits::set_parent(n, g); 686 687 if(g_is_header){ 688 if(NodeTraits::get_parent(g) == p) 689 NodeTraits::set_parent(g, n); 690 else{//must be ( g->right == p ) 691 BOOST_INTRUSIVE_INVARIANT_ASSERT(false); 692 NodeTraits::set_right(g, n); 693 } 694 } 695 else{ 696 if(NodeTraits::get_left(g) == p) 697 NodeTraits::set_left(g, n); 698 else //must be ( g->right == p ) 699 NodeTraits::set_right(g, n); 700 } 701 } 702 703 /// @endcond 704 }; 705 706 /// @cond 707 708 template<class NodeTraits> 709 struct get_algo<SplayTreeAlgorithms, NodeTraits> 710 { 711 typedef splaytree_algorithms<NodeTraits> type; 712 }; 713 714 template <class ValueTraits, class NodePtrCompare, class ExtraChecker> 715 struct get_node_checker<SplayTreeAlgorithms, ValueTraits, NodePtrCompare, ExtraChecker> 716 { 717 typedef detail::bstree_node_checker<ValueTraits, NodePtrCompare, ExtraChecker> type; 718 }; 719 720 /// @endcond 721 722 } //namespace intrusive 723 } //namespace boost 724 725 #include <boost/intrusive/detail/config_end.hpp> 726 727 #endif //BOOST_INTRUSIVE_SPLAYTREE_ALGORITHMS_HPP 728