ceph/src/boost/libs/intrusive/include/boost/intrusive/splaytree_algorithms.hpp

   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
  57    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
  66    ~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
  82    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.
 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>
 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>
 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>
 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>
 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>
 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>
 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>
 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>
 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>
 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>
 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>
 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>
 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>
 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>
 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>
 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>
 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>
 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>
 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>
 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
 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
 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
 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>
 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>
 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
 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>
 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>
 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>
 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
 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
 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
 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