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 //! @copydoc ::boost::intrusive::bstree_algorithms::transfer_unique 255 template<class NodePtrCompare> transfer_unique(const node_ptr & header1,NodePtrCompare comp,const node_ptr & header2,const node_ptr & z)256 static bool transfer_unique 257 (const node_ptr & header1, NodePtrCompare comp, const node_ptr &header2, const node_ptr & z) 258 { 259 typename bstree_algo::insert_commit_data commit_data; 260 bool const transferable = bstree_algo::insert_unique_check(header1, z, comp, commit_data).second; 261 if(transferable){ 262 erase(header2, z); 263 bstree_algo::insert_commit(header1, z, commit_data); 264 splay_up(z, header1); 265 } 266 return transferable; 267 } 268 269 //! @copydoc ::boost::intrusive::bstree_algorithms::transfer_equal 270 template<class NodePtrCompare> transfer_equal(const node_ptr & header1,NodePtrCompare comp,const node_ptr & header2,const node_ptr & z)271 static void transfer_equal 272 (const node_ptr & header1, NodePtrCompare comp, const node_ptr &header2, const node_ptr & z) 273 { 274 insert_commit_data commit_data; 275 splay_down(header1, z, comp); 276 bstree_algo::insert_equal_upper_bound_check(header1, z, comp, commit_data); 277 erase(header2, z); 278 bstree_algo::insert_commit(header1, z, commit_data); 279 } 280 281 #ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED 282 //! @copydoc ::boost::intrusive::bstree_algorithms::clone(const const_node_ptr&,const node_ptr&,Cloner,Disposer) 283 template <class Cloner, class Disposer> 284 static void clone 285 (const const_node_ptr & source_header, const node_ptr & target_header, Cloner cloner, Disposer disposer); 286 287 //! @copydoc ::boost::intrusive::bstree_algorithms::clear_and_dispose(const node_ptr&,Disposer) 288 template<class Disposer> 289 static void clear_and_dispose(const node_ptr & header, Disposer disposer); 290 291 #endif //#ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED 292 //! @copydoc ::boost::intrusive::bstree_algorithms::count(const const_node_ptr&,const KeyType&,KeyNodePtrCompare) 293 //! Additional notes: an element with key `key` is splayed. 294 template<class KeyType, class KeyNodePtrCompare> count(const node_ptr & header,const KeyType & key,KeyNodePtrCompare comp)295 static std::size_t count 296 (const node_ptr & header, const KeyType &key, KeyNodePtrCompare comp) 297 { 298 std::pair<node_ptr, node_ptr> ret = equal_range(header, key, comp); 299 std::size_t n = 0; 300 while(ret.first != ret.second){ 301 ++n; 302 ret.first = next_node(ret.first); 303 } 304 return n; 305 } 306 307 //! @copydoc ::boost::intrusive::bstree_algorithms::count(const const_node_ptr&,const KeyType&,KeyNodePtrCompare) 308 //! Additional note: no splaying is performed 309 template<class KeyType, class KeyNodePtrCompare> count(const const_node_ptr & header,const KeyType & key,KeyNodePtrCompare comp)310 static std::size_t count 311 (const const_node_ptr & header, const KeyType &key, KeyNodePtrCompare comp) 312 { return bstree_algo::count(header, key, comp); } 313 314 //! @copydoc ::boost::intrusive::bstree_algorithms::lower_bound(const const_node_ptr&,const KeyType&,KeyNodePtrCompare) 315 //! Additional notes: the first node of the range is splayed. 316 template<class KeyType, class KeyNodePtrCompare> lower_bound(const node_ptr & header,const KeyType & key,KeyNodePtrCompare comp)317 static node_ptr lower_bound 318 (const node_ptr & header, const KeyType &key, KeyNodePtrCompare comp) 319 { 320 splay_down(detail::uncast(header), key, comp); 321 node_ptr y = bstree_algo::lower_bound(header, key, comp); 322 //splay_up(y, detail::uncast(header)); 323 return y; 324 } 325 326 //! @copydoc ::boost::intrusive::bstree_algorithms::lower_bound(const const_node_ptr&,const KeyType&,KeyNodePtrCompare) 327 //! Additional note: no splaying is performed 328 template<class KeyType, class KeyNodePtrCompare> lower_bound(const const_node_ptr & header,const KeyType & key,KeyNodePtrCompare comp)329 static node_ptr lower_bound 330 (const const_node_ptr & header, const KeyType &key, KeyNodePtrCompare comp) 331 { return bstree_algo::lower_bound(header, key, comp); } 332 333 //! @copydoc ::boost::intrusive::bstree_algorithms::upper_bound(const const_node_ptr&,const KeyType&,KeyNodePtrCompare) 334 //! Additional notes: the first node of the range is splayed. 335 template<class KeyType, class KeyNodePtrCompare> upper_bound(const node_ptr & header,const KeyType & key,KeyNodePtrCompare comp)336 static node_ptr upper_bound 337 (const node_ptr & header, const KeyType &key, KeyNodePtrCompare comp) 338 { 339 splay_down(detail::uncast(header), key, comp); 340 node_ptr y = bstree_algo::upper_bound(header, key, comp); 341 //splay_up(y, detail::uncast(header)); 342 return y; 343 } 344 345 //! @copydoc ::boost::intrusive::bstree_algorithms::upper_bound(const const_node_ptr&,const KeyType&,KeyNodePtrCompare) 346 //! Additional note: no splaying is performed 347 template<class KeyType, class KeyNodePtrCompare> upper_bound(const const_node_ptr & header,const KeyType & key,KeyNodePtrCompare comp)348 static node_ptr upper_bound 349 (const const_node_ptr & header, const KeyType &key, KeyNodePtrCompare comp) 350 { return bstree_algo::upper_bound(header, key, comp); } 351 352 //! @copydoc ::boost::intrusive::bstree_algorithms::find(const const_node_ptr&, const KeyType&,KeyNodePtrCompare) 353 //! Additional notes: the found node of the lower bound is splayed. 354 template<class KeyType, class KeyNodePtrCompare> find(const node_ptr & header,const KeyType & key,KeyNodePtrCompare comp)355 static node_ptr find 356 (const node_ptr & header, const KeyType &key, KeyNodePtrCompare comp) 357 { 358 splay_down(detail::uncast(header), key, comp); 359 return bstree_algo::find(header, key, comp); 360 } 361 362 //! @copydoc ::boost::intrusive::bstree_algorithms::find(const const_node_ptr&, const KeyType&,KeyNodePtrCompare) 363 //! Additional note: no splaying is performed 364 template<class KeyType, class KeyNodePtrCompare> find(const const_node_ptr & header,const KeyType & key,KeyNodePtrCompare comp)365 static node_ptr find 366 (const const_node_ptr & header, const KeyType &key, KeyNodePtrCompare comp) 367 { return bstree_algo::find(header, key, comp); } 368 369 //! @copydoc ::boost::intrusive::bstree_algorithms::equal_range(const const_node_ptr&,const KeyType&,KeyNodePtrCompare) 370 //! Additional notes: the first node of the range is splayed. 371 template<class KeyType, class KeyNodePtrCompare> equal_range(const node_ptr & header,const KeyType & key,KeyNodePtrCompare comp)372 static std::pair<node_ptr, node_ptr> equal_range 373 (const node_ptr & header, const KeyType &key, KeyNodePtrCompare comp) 374 { 375 splay_down(detail::uncast(header), key, comp); 376 std::pair<node_ptr, node_ptr> ret = bstree_algo::equal_range(header, key, comp); 377 //splay_up(ret.first, detail::uncast(header)); 378 return ret; 379 } 380 381 //! @copydoc ::boost::intrusive::bstree_algorithms::equal_range(const const_node_ptr&,const KeyType&,KeyNodePtrCompare) 382 //! Additional note: no splaying is performed 383 template<class KeyType, class KeyNodePtrCompare> equal_range(const const_node_ptr & header,const KeyType & key,KeyNodePtrCompare comp)384 static std::pair<node_ptr, node_ptr> equal_range 385 (const const_node_ptr & header, const KeyType &key, KeyNodePtrCompare comp) 386 { return bstree_algo::equal_range(header, key, comp); } 387 388 //! @copydoc ::boost::intrusive::bstree_algorithms::lower_bound_range(const const_node_ptr&,const KeyType&,KeyNodePtrCompare) 389 //! Additional notes: the first node of the range is splayed. 390 template<class KeyType, class KeyNodePtrCompare> lower_bound_range(const node_ptr & header,const KeyType & key,KeyNodePtrCompare comp)391 static std::pair<node_ptr, node_ptr> lower_bound_range 392 (const node_ptr & header, const KeyType &key, KeyNodePtrCompare comp) 393 { 394 splay_down(detail::uncast(header), key, comp); 395 std::pair<node_ptr, node_ptr> ret = bstree_algo::lower_bound_range(header, key, comp); 396 //splay_up(ret.first, detail::uncast(header)); 397 return ret; 398 } 399 400 //! @copydoc ::boost::intrusive::bstree_algorithms::lower_bound_range(const const_node_ptr&,const KeyType&,KeyNodePtrCompare) 401 //! Additional note: no splaying is performed 402 template<class KeyType, class KeyNodePtrCompare> lower_bound_range(const const_node_ptr & header,const KeyType & key,KeyNodePtrCompare comp)403 static std::pair<node_ptr, node_ptr> lower_bound_range 404 (const const_node_ptr & header, const KeyType &key, KeyNodePtrCompare comp) 405 { return bstree_algo::lower_bound_range(header, key, comp); } 406 407 //! @copydoc ::boost::intrusive::bstree_algorithms::bounded_range(const const_node_ptr&,const KeyType&,const KeyType&,KeyNodePtrCompare,bool,bool) 408 //! Additional notes: the first node of the range is splayed. 409 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)410 static std::pair<node_ptr, node_ptr> bounded_range 411 (const node_ptr & header, const KeyType &lower_key, const KeyType &upper_key, KeyNodePtrCompare comp 412 , bool left_closed, bool right_closed) 413 { 414 splay_down(detail::uncast(header), lower_key, comp); 415 std::pair<node_ptr, node_ptr> ret = 416 bstree_algo::bounded_range(header, lower_key, upper_key, comp, left_closed, right_closed); 417 //splay_up(ret.first, detail::uncast(header)); 418 return ret; 419 } 420 421 //! @copydoc ::boost::intrusive::bstree_algorithms::bounded_range(const const_node_ptr&,const KeyType&,const KeyType&,KeyNodePtrCompare,bool,bool) 422 //! Additional note: no splaying is performed 423 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)424 static std::pair<node_ptr, node_ptr> bounded_range 425 (const const_node_ptr & header, const KeyType &lower_key, const KeyType &upper_key, KeyNodePtrCompare comp 426 , bool left_closed, bool right_closed) 427 { return bstree_algo::bounded_range(header, lower_key, upper_key, comp, left_closed, right_closed); } 428 429 //! @copydoc ::boost::intrusive::bstree_algorithms::insert_equal_upper_bound(const node_ptr&,const node_ptr&,NodePtrCompare) 430 //! Additional note: the inserted node is splayed 431 template<class NodePtrCompare> insert_equal_upper_bound(const node_ptr & header,const node_ptr & new_node,NodePtrCompare comp)432 static node_ptr insert_equal_upper_bound 433 (const node_ptr & header, const node_ptr & new_node, NodePtrCompare comp) 434 { 435 splay_down(header, new_node, comp); 436 return bstree_algo::insert_equal_upper_bound(header, new_node, comp); 437 } 438 439 //! @copydoc ::boost::intrusive::bstree_algorithms::insert_equal_lower_bound(const node_ptr&,const node_ptr&,NodePtrCompare) 440 //! Additional note: the inserted node is splayed 441 template<class NodePtrCompare> insert_equal_lower_bound(const node_ptr & header,const node_ptr & new_node,NodePtrCompare comp)442 static node_ptr insert_equal_lower_bound 443 (const node_ptr & header, const node_ptr & new_node, NodePtrCompare comp) 444 { 445 splay_down(header, new_node, comp); 446 return bstree_algo::insert_equal_lower_bound(header, new_node, comp); 447 } 448 449 //! @copydoc ::boost::intrusive::bstree_algorithms::insert_equal(const node_ptr&,const node_ptr&,const node_ptr&,NodePtrCompare) 450 //! Additional note: the inserted node is splayed 451 template<class NodePtrCompare> insert_equal(const node_ptr & header,const node_ptr & hint,const node_ptr & new_node,NodePtrCompare comp)452 static node_ptr insert_equal 453 (const node_ptr & header, const node_ptr & hint, const node_ptr & new_node, NodePtrCompare comp) 454 { 455 splay_down(header, new_node, comp); 456 return bstree_algo::insert_equal(header, hint, new_node, comp); 457 } 458 459 //! @copydoc ::boost::intrusive::bstree_algorithms::insert_before(const node_ptr&,const node_ptr&,const node_ptr&) 460 //! Additional note: the inserted node is splayed insert_before(const node_ptr & header,const node_ptr & pos,const node_ptr & new_node)461 static node_ptr insert_before 462 (const node_ptr & header, const node_ptr & pos, const node_ptr & new_node) 463 { 464 bstree_algo::insert_before(header, pos, new_node); 465 splay_up(new_node, header); 466 return new_node; 467 } 468 469 //! @copydoc ::boost::intrusive::bstree_algorithms::push_back(const node_ptr&,const node_ptr&) 470 //! Additional note: the inserted node is splayed push_back(const node_ptr & header,const node_ptr & new_node)471 static void push_back(const node_ptr & header, const node_ptr & new_node) 472 { 473 bstree_algo::push_back(header, new_node); 474 splay_up(new_node, header); 475 } 476 477 //! @copydoc ::boost::intrusive::bstree_algorithms::push_front(const node_ptr&,const node_ptr&) 478 //! Additional note: the inserted node is splayed push_front(const node_ptr & header,const node_ptr & new_node)479 static void push_front(const node_ptr & header, const node_ptr & new_node) 480 { 481 bstree_algo::push_front(header, new_node); 482 splay_up(new_node, header); 483 } 484 485 //! @copydoc ::boost::intrusive::bstree_algorithms::insert_unique_check(const const_node_ptr&,const KeyType&,KeyNodePtrCompare,insert_commit_data&) 486 //! Additional note: nodes with the given key are splayed 487 template<class KeyType, class KeyNodePtrCompare> insert_unique_check(const node_ptr & header,const KeyType & key,KeyNodePtrCompare comp,insert_commit_data & commit_data)488 static std::pair<node_ptr, bool> insert_unique_check 489 (const node_ptr & header, const KeyType &key 490 ,KeyNodePtrCompare comp, insert_commit_data &commit_data) 491 { 492 splay_down(header, key, comp); 493 return bstree_algo::insert_unique_check(header, key, comp, commit_data); 494 } 495 496 //! @copydoc ::boost::intrusive::bstree_algorithms::insert_unique_check(const const_node_ptr&,const node_ptr&,const KeyType&,KeyNodePtrCompare,insert_commit_data&) 497 //! Additional note: nodes with the given key are splayed 498 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)499 static std::pair<node_ptr, bool> insert_unique_check 500 (const node_ptr & header, const node_ptr &hint, const KeyType &key 501 ,KeyNodePtrCompare comp, insert_commit_data &commit_data) 502 { 503 splay_down(header, key, comp); 504 return bstree_algo::insert_unique_check(header, hint, key, comp, commit_data); 505 } 506 507 #ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED 508 //! @copydoc ::boost::intrusive::bstree_algorithms::insert_unique_commit(const node_ptr&,const node_ptr&,const insert_commit_data&) 509 static void insert_unique_commit 510 (const node_ptr & header, const node_ptr & new_value, const insert_commit_data &commit_data); 511 512 //! @copydoc ::boost::intrusive::bstree_algorithms::is_header 513 static bool is_header(const const_node_ptr & p); 514 515 //! @copydoc ::boost::intrusive::bstree_algorithms::rebalance 516 static void rebalance(const node_ptr & header); 517 518 //! @copydoc ::boost::intrusive::bstree_algorithms::rebalance_subtree 519 static node_ptr rebalance_subtree(const node_ptr & old_root); 520 521 #endif //#ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED 522 523 // bottom-up splay, use data_ as parent for n | complexity : logarithmic | exception : nothrow splay_up(const node_ptr & node,const node_ptr & header)524 static void splay_up(const node_ptr & node, const node_ptr & header) 525 { priv_splay_up<true>(node, header); } 526 527 // top-down splay | complexity : logarithmic | exception : strong, note A 528 template<class KeyType, class KeyNodePtrCompare> splay_down(const node_ptr & header,const KeyType & key,KeyNodePtrCompare comp,bool * pfound=0)529 static node_ptr splay_down(const node_ptr & header, const KeyType &key, KeyNodePtrCompare comp, bool *pfound = 0) 530 { return priv_splay_down<true>(header, key, comp, pfound); } 531 532 private: 533 534 /// @cond 535 536 // bottom-up splay, use data_ as parent for n | complexity : logarithmic | exception : nothrow 537 template<bool SimpleSplay> priv_splay_up(const node_ptr & node,const node_ptr & header)538 static void priv_splay_up(const node_ptr & node, const node_ptr & header) 539 { 540 // If (node == header) do a splay for the right most node instead 541 // this is to boost performance of equal_range/count on equivalent containers in the case 542 // where there are many equal elements at the end 543 node_ptr n((node == header) ? NodeTraits::get_right(header) : node); 544 node_ptr t(header); 545 546 if( n == t ) return; 547 548 for( ;; ){ 549 node_ptr p(NodeTraits::get_parent(n)); 550 node_ptr g(NodeTraits::get_parent(p)); 551 552 if( p == t ) break; 553 554 if( g == t ){ 555 // zig 556 rotate(n); 557 } 558 else if ((NodeTraits::get_left(p) == n && NodeTraits::get_left(g) == p) || 559 (NodeTraits::get_right(p) == n && NodeTraits::get_right(g) == p) ){ 560 // zig-zig 561 rotate(p); 562 rotate(n); 563 } 564 else { 565 // zig-zag 566 rotate(n); 567 if(!SimpleSplay){ 568 rotate(n); 569 } 570 } 571 } 572 } 573 574 template<bool SimpleSplay, class KeyType, class KeyNodePtrCompare> priv_splay_down(const node_ptr & header,const KeyType & key,KeyNodePtrCompare comp,bool * pfound=0)575 static node_ptr priv_splay_down(const node_ptr & header, const KeyType &key, KeyNodePtrCompare comp, bool *pfound = 0) 576 { 577 //Most splay tree implementations use a dummy/null node to implement. 578 //this function. This has some problems for a generic library like Intrusive: 579 // 580 // * The node might not have a default constructor. 581 // * The default constructor could throw. 582 // 583 //We already have a header node. Leftmost and rightmost nodes of the tree 584 //are not changed when splaying (because the invariants of the tree don't 585 //change) We can back up them, use the header as the null node and 586 //reassign old values after the function has been completed. 587 node_ptr const old_root = NodeTraits::get_parent(header); 588 node_ptr const leftmost = NodeTraits::get_left(header); 589 node_ptr const rightmost = NodeTraits::get_right(header); 590 if(leftmost == rightmost){ //Empty or unique node 591 if(pfound){ 592 *pfound = old_root && !comp(key, old_root) && !comp(old_root, key); 593 } 594 return old_root ? old_root : header; 595 } 596 else{ 597 //Initialize "null node" (the header in our case) 598 NodeTraits::set_left (header, node_ptr()); 599 NodeTraits::set_right(header, node_ptr()); 600 //Class that will backup leftmost/rightmost from header, commit the assemble(), 601 //and will restore leftmost/rightmost to header even if "comp" throws 602 detail::splaydown_assemble_and_fix_header<NodeTraits> commit(old_root, header, leftmost, rightmost); 603 bool found = false; 604 605 for( ;; ){ 606 if(comp(key, commit.t_)){ 607 node_ptr const t_left = NodeTraits::get_left(commit.t_); 608 if(!t_left) 609 break; 610 if(comp(key, t_left)){ 611 bstree_algo::rotate_right_no_parent_fix(commit.t_, t_left); 612 commit.t_ = t_left; 613 if( !NodeTraits::get_left(commit.t_) ) 614 break; 615 link_right(commit.t_, commit.r_); 616 } 617 else{ 618 link_right(commit.t_, commit.r_); 619 if(!SimpleSplay && comp(t_left, key)){ 620 if( !NodeTraits::get_right(commit.t_) ) 621 break; 622 link_left(commit.t_, commit.l_); 623 } 624 } 625 } 626 else if(comp(commit.t_, key)){ 627 node_ptr const t_right = NodeTraits::get_right(commit.t_); 628 if(!t_right) 629 break; 630 631 if(comp(t_right, key)){ 632 bstree_algo::rotate_left_no_parent_fix(commit.t_, t_right); 633 commit.t_ = t_right; 634 if( !NodeTraits::get_right(commit.t_) ) 635 break; 636 link_left(commit.t_, commit.l_); 637 } 638 else{ 639 link_left(commit.t_, commit.l_); 640 if(!SimpleSplay && comp(key, t_right)){ 641 if( !NodeTraits::get_left(commit.t_) ) 642 break; 643 link_right(commit.t_, commit.r_); 644 } 645 } 646 } 647 else{ 648 found = true; 649 break; 650 } 651 } 652 653 //commit.~splaydown_assemble_and_fix_header<NodeTraits>() will first 654 //"assemble()" + link the new root & recover header's leftmost & rightmost 655 if(pfound){ 656 *pfound = found; 657 } 658 return commit.t_; 659 } 660 } 661 662 // 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)663 static void link_left(node_ptr & t, node_ptr & l) 664 { 665 //procedure link_left; 666 // t, l, right(l) := right(t), t, t 667 //end link_left 668 NodeTraits::set_right(l, t); 669 NodeTraits::set_parent(t, l); 670 l = t; 671 t = NodeTraits::get_right(t); 672 } 673 674 // 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)675 static void link_right(node_ptr & t, node_ptr & r) 676 { 677 //procedure link_right; 678 // t, r, left(r) := left(t), t, t 679 //end link_right; 680 NodeTraits::set_left(r, t); 681 NodeTraits::set_parent(t, r); 682 r = t; 683 t = NodeTraits::get_left(t); 684 } 685 686 // rotate n with its parent | complexity : constant | exception : nothrow rotate(const node_ptr & n)687 static void rotate(const node_ptr & n) 688 { 689 //procedure rotate_left; 690 // t, right(t), left(right(t)) := right(t), left(right(t)), t 691 //end rotate_left; 692 node_ptr p = NodeTraits::get_parent(n); 693 node_ptr g = NodeTraits::get_parent(p); 694 //Test if g is header before breaking tree 695 //invariants that would make is_header invalid 696 bool g_is_header = bstree_algo::is_header(g); 697 698 if(NodeTraits::get_left(p) == n){ 699 NodeTraits::set_left(p, NodeTraits::get_right(n)); 700 if(NodeTraits::get_left(p)) 701 NodeTraits::set_parent(NodeTraits::get_left(p), p); 702 NodeTraits::set_right(n, p); 703 } 704 else{ // must be ( p->right == n ) 705 NodeTraits::set_right(p, NodeTraits::get_left(n)); 706 if(NodeTraits::get_right(p)) 707 NodeTraits::set_parent(NodeTraits::get_right(p), p); 708 NodeTraits::set_left(n, p); 709 } 710 711 NodeTraits::set_parent(p, n); 712 NodeTraits::set_parent(n, g); 713 714 if(g_is_header){ 715 if(NodeTraits::get_parent(g) == p) 716 NodeTraits::set_parent(g, n); 717 else{//must be ( g->right == p ) 718 BOOST_INTRUSIVE_INVARIANT_ASSERT(false); 719 NodeTraits::set_right(g, n); 720 } 721 } 722 else{ 723 if(NodeTraits::get_left(g) == p) 724 NodeTraits::set_left(g, n); 725 else //must be ( g->right == p ) 726 NodeTraits::set_right(g, n); 727 } 728 } 729 730 /// @endcond 731 }; 732 733 /// @cond 734 735 template<class NodeTraits> 736 struct get_algo<SplayTreeAlgorithms, NodeTraits> 737 { 738 typedef splaytree_algorithms<NodeTraits> type; 739 }; 740 741 template <class ValueTraits, class NodePtrCompare, class ExtraChecker> 742 struct get_node_checker<SplayTreeAlgorithms, ValueTraits, NodePtrCompare, ExtraChecker> 743 { 744 typedef detail::bstree_node_checker<ValueTraits, NodePtrCompare, ExtraChecker> type; 745 }; 746 747 /// @endcond 748 749 } //namespace intrusive 750 } //namespace boost 751 752 #include <boost/intrusive/detail/config_end.hpp> 753 754 #endif //BOOST_INTRUSIVE_SPLAYTREE_ALGORITHMS_HPP 755