1 ///////////////////////////////////////////////////////////////////////////// 2 // 3 // (C) Copyright Ion Gaztanaga 2007-2014 4 // 5 // Distributed under the Boost Software License, Version 1.0. 6 // (See accompanying file LICENSE_1_0.txt or copy at 7 // http://www.boost.org/LICENSE_1_0.txt) 8 // 9 // See http://www.boost.org/libs/intrusive for documentation. 10 // 11 ///////////////////////////////////////////////////////////////////////////// 12 // 13 // Scapegoat tree algorithms are taken from the paper titled: 14 // "Scapegoat Trees" by Igal Galperin Ronald L. Rivest. 15 // 16 ///////////////////////////////////////////////////////////////////////////// 17 #ifndef BOOST_INTRUSIVE_SGTREE_ALGORITHMS_HPP 18 #define BOOST_INTRUSIVE_SGTREE_ALGORITHMS_HPP 19 20 #include <boost/intrusive/detail/config_begin.hpp> 21 #include <boost/intrusive/intrusive_fwd.hpp> 22 23 #include <cstddef> 24 #include <boost/intrusive/detail/algo_type.hpp> 25 #include <boost/intrusive/bstree_algorithms.hpp> 26 27 #if defined(BOOST_HAS_PRAGMA_ONCE) 28 # pragma once 29 #endif 30 31 namespace boost { 32 namespace intrusive { 33 34 //! sgtree_algorithms is configured with a NodeTraits class, which encapsulates the 35 //! information about the node to be manipulated. NodeTraits must support the 36 //! following interface: 37 //! 38 //! <b>Typedefs</b>: 39 //! 40 //! <tt>node</tt>: The type of the node that forms the binary search tree 41 //! 42 //! <tt>node_ptr</tt>: A pointer to a node 43 //! 44 //! <tt>const_node_ptr</tt>: A pointer to a const node 45 //! 46 //! <b>Static functions</b>: 47 //! 48 //! <tt>static node_ptr get_parent(const_node_ptr n);</tt> 49 //! 50 //! <tt>static void set_parent(node_ptr n, node_ptr parent);</tt> 51 //! 52 //! <tt>static node_ptr get_left(const_node_ptr n);</tt> 53 //! 54 //! <tt>static void set_left(node_ptr n, node_ptr left);</tt> 55 //! 56 //! <tt>static node_ptr get_right(const_node_ptr n);</tt> 57 //! 58 //! <tt>static void set_right(node_ptr n, node_ptr right);</tt> 59 template<class NodeTraits> 60 class sgtree_algorithms 61 #ifndef BOOST_INTRUSIVE_DOXYGEN_INVOKED 62 : public bstree_algorithms<NodeTraits> 63 #endif 64 { 65 public: 66 typedef typename NodeTraits::node node; 67 typedef NodeTraits node_traits; 68 typedef typename NodeTraits::node_ptr node_ptr; 69 typedef typename NodeTraits::const_node_ptr const_node_ptr; 70 71 /// @cond 72 private: 73 74 typedef bstree_algorithms<NodeTraits> bstree_algo; 75 76 /// @endcond 77 78 public: 79 //! This type is the information that will be 80 //! filled by insert_unique_check 81 struct insert_commit_data 82 : bstree_algo::insert_commit_data 83 { 84 std::size_t depth; 85 }; 86 87 #ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED 88 //! @copydoc ::boost::intrusive::bstree_algorithms::get_header(const const_node_ptr&) 89 static node_ptr get_header(const_node_ptr n); 90 91 //! @copydoc ::boost::intrusive::bstree_algorithms::begin_node 92 static node_ptr begin_node(const_node_ptr header); 93 94 //! @copydoc ::boost::intrusive::bstree_algorithms::end_node 95 static node_ptr end_node(const_node_ptr header); 96 97 //! @copydoc ::boost::intrusive::bstree_algorithms::swap_tree 98 static void swap_tree(node_ptr header1, node_ptr header2); 99 100 //! @copydoc ::boost::intrusive::bstree_algorithms::swap_nodes(node_ptr,node_ptr) 101 static void swap_nodes(node_ptr node1, node_ptr node2); 102 103 //! @copydoc ::boost::intrusive::bstree_algorithms::swap_nodes(node_ptr,node_ptr,node_ptr,node_ptr) 104 static void swap_nodes(node_ptr node1, node_ptr header1, node_ptr node2, node_ptr header2); 105 106 //! @copydoc ::boost::intrusive::bstree_algorithms::replace_node(node_ptr,node_ptr) 107 static void replace_node(node_ptr node_to_be_replaced, node_ptr new_node); 108 109 //! @copydoc ::boost::intrusive::bstree_algorithms::replace_node(node_ptr,node_ptr,node_ptr) 110 static void replace_node(node_ptr node_to_be_replaced, node_ptr header, node_ptr new_node); 111 112 //Unlink is not possible since tree metadata is needed to update the tree 113 //!static void unlink(node_ptr node); 114 115 //! @copydoc ::boost::intrusive::bstree_algorithms::unlink_leftmost_without_rebalance 116 static node_ptr unlink_leftmost_without_rebalance(node_ptr header); 117 118 //! @copydoc ::boost::intrusive::bstree_algorithms::unique(const const_node_ptr&) 119 static bool unique(const_node_ptr node); 120 121 //! @copydoc ::boost::intrusive::bstree_algorithms::size(const const_node_ptr&) 122 static std::size_t size(const_node_ptr header); 123 124 //! @copydoc ::boost::intrusive::bstree_algorithms::next_node(const node_ptr&) 125 static node_ptr next_node(node_ptr node); 126 127 //! @copydoc ::boost::intrusive::bstree_algorithms::prev_node(const node_ptr&) 128 static node_ptr prev_node(node_ptr node); 129 130 //! @copydoc ::boost::intrusive::bstree_algorithms::init(node_ptr) 131 static void init(node_ptr node); 132 133 //! @copydoc ::boost::intrusive::bstree_algorithms::init_header(node_ptr) 134 static void init_header(node_ptr header); 135 #endif //#ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED 136 137 //! @copydoc ::boost::intrusive::bstree_algorithms::erase(node_ptr,node_ptr) 138 template<class AlphaByMaxSize> erase(node_ptr header,node_ptr z,std::size_t tree_size,std::size_t & max_tree_size,AlphaByMaxSize alpha_by_maxsize)139 static node_ptr erase(node_ptr header, node_ptr z, std::size_t tree_size, std::size_t &max_tree_size, AlphaByMaxSize alpha_by_maxsize) 140 { 141 bstree_algo::erase(header, z); 142 --tree_size; 143 if (tree_size > 0 && 144 tree_size < alpha_by_maxsize(max_tree_size)){ 145 bstree_algo::rebalance(header); 146 max_tree_size = tree_size; 147 } 148 return z; 149 } 150 151 #ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED 152 //! @copydoc ::boost::intrusive::bstree_algorithms::clone(const const_node_ptr&,node_ptr,Cloner,Disposer) 153 template <class Cloner, class Disposer> 154 static void clone 155 (const_node_ptr source_header, node_ptr target_header, Cloner cloner, Disposer disposer); 156 157 //! @copydoc ::boost::intrusive::bstree_algorithms::clear_and_dispose(const node_ptr&,Disposer) 158 template<class Disposer> 159 static void clear_and_dispose(node_ptr header, Disposer disposer); 160 161 //! @copydoc ::boost::intrusive::bstree_algorithms::lower_bound(const const_node_ptr&,const KeyType&,KeyNodePtrCompare) 162 template<class KeyType, class KeyNodePtrCompare> 163 static node_ptr lower_bound 164 (const_node_ptr header, const KeyType &key, KeyNodePtrCompare comp); 165 166 //! @copydoc ::boost::intrusive::bstree_algorithms::upper_bound(const const_node_ptr&,const KeyType&,KeyNodePtrCompare) 167 template<class KeyType, class KeyNodePtrCompare> 168 static node_ptr upper_bound 169 (const_node_ptr header, const KeyType &key, KeyNodePtrCompare comp); 170 171 //! @copydoc ::boost::intrusive::bstree_algorithms::find(const const_node_ptr&, const KeyType&,KeyNodePtrCompare) 172 template<class KeyType, class KeyNodePtrCompare> 173 static node_ptr find 174 (const_node_ptr header, const KeyType &key, KeyNodePtrCompare comp); 175 176 //! @copydoc ::boost::intrusive::bstree_algorithms::equal_range(const const_node_ptr&,const KeyType&,KeyNodePtrCompare) 177 template<class KeyType, class KeyNodePtrCompare> 178 static std::pair<node_ptr, node_ptr> equal_range 179 (const_node_ptr header, const KeyType &key, KeyNodePtrCompare comp); 180 181 //! @copydoc ::boost::intrusive::bstree_algorithms::bounded_range(const const_node_ptr&,const KeyType&,const KeyType&,KeyNodePtrCompare,bool,bool) 182 template<class KeyType, class KeyNodePtrCompare> 183 static std::pair<node_ptr, node_ptr> bounded_range 184 (const_node_ptr header, const KeyType &lower_key, const KeyType &upper_key, KeyNodePtrCompare comp 185 , bool left_closed, bool right_closed); 186 187 //! @copydoc ::boost::intrusive::bstree_algorithms::count(const const_node_ptr&,const KeyType&,KeyNodePtrCompare) 188 template<class KeyType, class KeyNodePtrCompare> 189 static std::size_t count(const_node_ptr header, const KeyType &key, KeyNodePtrCompare comp); 190 191 #endif //#ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED 192 193 //! @copydoc ::boost::intrusive::bstree_algorithms::insert_equal_upper_bound(node_ptr,node_ptr,NodePtrCompare) 194 template<class NodePtrCompare, class H_Alpha> insert_equal_upper_bound(node_ptr h,node_ptr new_node,NodePtrCompare comp,std::size_t tree_size,H_Alpha h_alpha,std::size_t & max_tree_size)195 static node_ptr insert_equal_upper_bound 196 (node_ptr h, node_ptr new_node, NodePtrCompare comp 197 ,std::size_t tree_size, H_Alpha h_alpha, std::size_t &max_tree_size) 198 { 199 std::size_t depth; 200 bstree_algo::insert_equal_upper_bound(h, new_node, comp, &depth); 201 rebalance_after_insertion(new_node, depth, tree_size+1, h_alpha, max_tree_size); 202 return new_node; 203 } 204 205 //! @copydoc ::boost::intrusive::bstree_algorithms::insert_equal_lower_bound(node_ptr,node_ptr,NodePtrCompare) 206 template<class NodePtrCompare, class H_Alpha> insert_equal_lower_bound(node_ptr h,node_ptr new_node,NodePtrCompare comp,std::size_t tree_size,H_Alpha h_alpha,std::size_t & max_tree_size)207 static node_ptr insert_equal_lower_bound 208 (node_ptr h, node_ptr new_node, NodePtrCompare comp 209 ,std::size_t tree_size, H_Alpha h_alpha, std::size_t &max_tree_size) 210 { 211 std::size_t depth; 212 bstree_algo::insert_equal_lower_bound(h, new_node, comp, &depth); 213 rebalance_after_insertion(new_node, depth, tree_size+1, h_alpha, max_tree_size); 214 return new_node; 215 } 216 217 //! @copydoc ::boost::intrusive::bstree_algorithms::insert_equal(node_ptr,node_ptr,node_ptr,NodePtrCompare) 218 template<class NodePtrCompare, class H_Alpha> insert_equal(node_ptr header,node_ptr hint,node_ptr new_node,NodePtrCompare comp,std::size_t tree_size,H_Alpha h_alpha,std::size_t & max_tree_size)219 static node_ptr insert_equal 220 (node_ptr header, node_ptr hint, node_ptr new_node, NodePtrCompare comp 221 ,std::size_t tree_size, H_Alpha h_alpha, std::size_t &max_tree_size) 222 { 223 std::size_t depth; 224 bstree_algo::insert_equal(header, hint, new_node, comp, &depth); 225 rebalance_after_insertion(new_node, depth, tree_size+1, h_alpha, max_tree_size); 226 return new_node; 227 } 228 229 //! @copydoc ::boost::intrusive::bstree_algorithms::insert_before(node_ptr,node_ptr,node_ptr) 230 template<class H_Alpha> insert_before(node_ptr header,node_ptr pos,node_ptr new_node,std::size_t tree_size,H_Alpha h_alpha,std::size_t & max_tree_size)231 static node_ptr insert_before 232 (node_ptr header, node_ptr pos, node_ptr new_node 233 ,std::size_t tree_size, H_Alpha h_alpha, std::size_t &max_tree_size) 234 { 235 std::size_t depth; 236 bstree_algo::insert_before(header, pos, new_node, &depth); 237 rebalance_after_insertion(new_node, depth, tree_size+1, h_alpha, max_tree_size); 238 return new_node; 239 } 240 241 //! @copydoc ::boost::intrusive::bstree_algorithms::push_back(node_ptr,node_ptr) 242 template<class H_Alpha> push_back(node_ptr header,node_ptr new_node,std::size_t tree_size,H_Alpha h_alpha,std::size_t & max_tree_size)243 static void push_back(node_ptr header, node_ptr new_node 244 ,std::size_t tree_size, H_Alpha h_alpha, std::size_t &max_tree_size) 245 { 246 std::size_t depth; 247 bstree_algo::push_back(header, new_node, &depth); 248 rebalance_after_insertion(new_node, depth, tree_size+1, h_alpha, max_tree_size); 249 } 250 251 //! @copydoc ::boost::intrusive::bstree_algorithms::push_front(node_ptr,node_ptr) 252 template<class H_Alpha> push_front(node_ptr header,node_ptr new_node,std::size_t tree_size,H_Alpha h_alpha,std::size_t & max_tree_size)253 static void push_front(node_ptr header, node_ptr new_node 254 ,std::size_t tree_size, H_Alpha h_alpha, std::size_t &max_tree_size) 255 { 256 std::size_t depth; 257 bstree_algo::push_front(header, new_node, &depth); 258 rebalance_after_insertion(new_node, depth, tree_size+1, h_alpha, max_tree_size); 259 } 260 261 //! @copydoc ::boost::intrusive::bstree_algorithms::insert_unique_check(const const_node_ptr&,const KeyType&,KeyNodePtrCompare,insert_commit_data&) 262 template<class KeyType, class KeyNodePtrCompare> insert_unique_check(const_node_ptr header,const KeyType & key,KeyNodePtrCompare comp,insert_commit_data & commit_data)263 static std::pair<node_ptr, bool> insert_unique_check 264 (const_node_ptr header, const KeyType &key 265 ,KeyNodePtrCompare comp, insert_commit_data &commit_data) 266 { 267 std::size_t depth; 268 std::pair<node_ptr, bool> ret = 269 bstree_algo::insert_unique_check(header, key, comp, commit_data, &depth); 270 commit_data.depth = depth; 271 return ret; 272 } 273 274 //! @copydoc ::boost::intrusive::bstree_algorithms::insert_unique_check(const const_node_ptr&,const node_ptr&,const KeyType&,KeyNodePtrCompare,insert_commit_data&) 275 template<class KeyType, class KeyNodePtrCompare> insert_unique_check(const_node_ptr header,node_ptr hint,const KeyType & key,KeyNodePtrCompare comp,insert_commit_data & commit_data)276 static std::pair<node_ptr, bool> insert_unique_check 277 (const_node_ptr header, node_ptr hint, const KeyType &key 278 ,KeyNodePtrCompare comp, insert_commit_data &commit_data) 279 { 280 std::size_t depth; 281 std::pair<node_ptr, bool> ret = 282 bstree_algo::insert_unique_check 283 (header, hint, key, comp, commit_data, &depth); 284 commit_data.depth = depth; 285 return ret; 286 } 287 288 //! @copydoc ::boost::intrusive::bstree_algorithms::insert_unique_commit(node_ptr,node_ptr,const insert_commit_data&) 289 template<class H_Alpha> insert_unique_commit(node_ptr header,node_ptr new_value,const insert_commit_data & commit_data,std::size_t tree_size,H_Alpha h_alpha,std::size_t & max_tree_size)290 BOOST_INTRUSIVE_FORCEINLINE static void insert_unique_commit 291 (node_ptr header, node_ptr new_value, const insert_commit_data &commit_data 292 ,std::size_t tree_size, H_Alpha h_alpha, std::size_t &max_tree_size) 293 { return insert_commit(header, new_value, commit_data, tree_size, h_alpha, max_tree_size); } 294 295 //! @copydoc ::boost::intrusive::bstree_algorithms::transfer_unique 296 template<class NodePtrCompare, class H_Alpha, class AlphaByMaxSize> transfer_unique(node_ptr header1,NodePtrCompare comp,std::size_t tree1_size,std::size_t & max_tree1_size,node_ptr header2,node_ptr z,std::size_t tree2_size,std::size_t & max_tree2_size,H_Alpha h_alpha,AlphaByMaxSize alpha_by_maxsize)297 static bool transfer_unique 298 ( node_ptr header1, NodePtrCompare comp, std::size_t tree1_size, std::size_t &max_tree1_size 299 , node_ptr header2, node_ptr z, std::size_t tree2_size, std::size_t &max_tree2_size 300 ,H_Alpha h_alpha, AlphaByMaxSize alpha_by_maxsize) 301 { 302 insert_commit_data commit_data; 303 bool const transferable = insert_unique_check(header1, z, comp, commit_data).second; 304 if(transferable){ 305 erase(header2, z, tree2_size, max_tree2_size, alpha_by_maxsize); 306 insert_commit(header1, z, commit_data, tree1_size, h_alpha, max_tree1_size); 307 } 308 return transferable; 309 } 310 311 //! @copydoc ::boost::intrusive::bstree_algorithms::transfer_equal 312 template<class NodePtrCompare, class H_Alpha, class AlphaByMaxSize> transfer_equal(node_ptr header1,NodePtrCompare comp,std::size_t tree1_size,std::size_t & max_tree1_size,node_ptr header2,node_ptr z,std::size_t tree2_size,std::size_t & max_tree2_size,H_Alpha h_alpha,AlphaByMaxSize alpha_by_maxsize)313 static void transfer_equal 314 ( node_ptr header1, NodePtrCompare comp, std::size_t tree1_size, std::size_t &max_tree1_size 315 , node_ptr header2, node_ptr z, std::size_t tree2_size, std::size_t &max_tree2_size 316 ,H_Alpha h_alpha, AlphaByMaxSize alpha_by_maxsize) 317 { 318 insert_commit_data commit_data; 319 insert_equal_upper_bound_check(header1, z, comp, commit_data); 320 erase(header2, z, tree2_size, max_tree2_size, alpha_by_maxsize); 321 insert_commit(header1, z, commit_data, tree1_size, h_alpha, max_tree1_size); 322 } 323 324 #ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED 325 //! @copydoc ::boost::intrusive::bstree_algorithms::is_header 326 static bool is_header(const_node_ptr p); 327 328 //! @copydoc ::boost::intrusive::bstree_algorithms::is_header 329 static void rebalance(node_ptr header); 330 331 //! @copydoc ::boost::intrusive::bstree_algorithms::rebalance_subtree 332 static node_ptr rebalance_subtree(node_ptr old_root) 333 #endif //#ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED 334 335 /// @cond 336 private: 337 338 template<class KeyType, class KeyNodePtrCompare> insert_equal_upper_bound_check(node_ptr header,const KeyType & key,KeyNodePtrCompare comp,insert_commit_data & commit_data)339 static void insert_equal_upper_bound_check 340 (node_ptr header, const KeyType &key 341 ,KeyNodePtrCompare comp, insert_commit_data &commit_data) 342 { 343 std::size_t depth; 344 bstree_algo::insert_equal_upper_bound_check(header, key, comp, commit_data, &depth); 345 commit_data.depth = depth; 346 } 347 348 template<class H_Alpha> insert_commit(node_ptr header,node_ptr new_value,const insert_commit_data & commit_data,std::size_t tree_size,H_Alpha h_alpha,std::size_t & max_tree_size)349 static void insert_commit 350 (node_ptr header, node_ptr new_value, const insert_commit_data &commit_data 351 ,std::size_t tree_size, H_Alpha h_alpha, std::size_t &max_tree_size) 352 { 353 bstree_algo::insert_unique_commit(header, new_value, commit_data); 354 rebalance_after_insertion(new_value, commit_data.depth, tree_size+1, h_alpha, max_tree_size); 355 } 356 357 template<class H_Alpha> rebalance_after_insertion(node_ptr x,std::size_t depth,std::size_t tree_size,H_Alpha h_alpha,std::size_t & max_tree_size)358 static void rebalance_after_insertion 359 (node_ptr x, std::size_t depth 360 , std::size_t tree_size, H_Alpha h_alpha, std::size_t &max_tree_size) 361 { 362 if(tree_size > max_tree_size) 363 max_tree_size = tree_size; 364 365 if(tree_size > 2 && //Nothing to do with only the root 366 //Check if the root node is unbalanced 367 //Scapegoat paper depth counts root depth as zero and "depth" counts root as 1, 368 //but since "depth" is the depth of the ancestor of x, i == depth 369 depth > h_alpha(tree_size)){ 370 371 //Find the first non height-balanced node 372 //as described in the section 4.2 of the paper. 373 //This method is the alternative method described 374 //in the paper. Authors claim that this method 375 //may tend to yield more balanced trees on the average 376 //than the weight balanced method. 377 node_ptr s = x; 378 std::size_t size = 1; 379 for(std::size_t ancestor = 1; ancestor != depth; ++ancestor){ 380 const node_ptr s_parent = NodeTraits::get_parent(s); 381 const node_ptr s_parent_left = NodeTraits::get_left(s_parent); 382 //Obtain parent's size (previous size + parent + sibling tree) 383 const node_ptr s_sibling = s_parent_left == s ? NodeTraits::get_right(s_parent) : s_parent_left; 384 size += 1 + bstree_algo::subtree_size(s_sibling); 385 s = s_parent; 386 if(ancestor > h_alpha(size)){ //is 's' scapegoat? 387 bstree_algo::rebalance_subtree(s); 388 return; 389 } 390 } 391 //The whole tree must be rebuilt 392 max_tree_size = tree_size; 393 bstree_algo::rebalance_subtree(NodeTraits::get_parent(s)); 394 } 395 } 396 /// @endcond 397 }; 398 399 /// @cond 400 401 template<class NodeTraits> 402 struct get_algo<SgTreeAlgorithms, NodeTraits> 403 { 404 typedef sgtree_algorithms<NodeTraits> type; 405 }; 406 407 template <class ValueTraits, class NodePtrCompare, class ExtraChecker> 408 struct get_node_checker<SgTreeAlgorithms, ValueTraits, NodePtrCompare, ExtraChecker> 409 { 410 typedef detail::bstree_node_checker<ValueTraits, NodePtrCompare, ExtraChecker> type; 411 }; 412 413 /// @endcond 414 415 } //namespace intrusive 416 } //namespace boost 417 418 #include <boost/intrusive/detail/config_end.hpp> 419 420 #endif //BOOST_INTRUSIVE_SGTREE_ALGORITHMS_HPP 421