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 const_node_ptr & n); 90 91 //! @copydoc ::boost::intrusive::bstree_algorithms::begin_node 92 static node_ptr begin_node(const const_node_ptr & header); 93 94 //! @copydoc ::boost::intrusive::bstree_algorithms::end_node 95 static node_ptr end_node(const const_node_ptr & header); 96 97 //! @copydoc ::boost::intrusive::bstree_algorithms::swap_tree 98 static void swap_tree(const node_ptr & header1, const node_ptr & header2); 99 100 //! @copydoc ::boost::intrusive::bstree_algorithms::swap_nodes(const node_ptr&,const node_ptr&) 101 static void swap_nodes(const node_ptr & node1, const node_ptr & node2); 102 103 //! @copydoc ::boost::intrusive::bstree_algorithms::swap_nodes(const node_ptr&,const node_ptr&,const node_ptr&,const node_ptr&) 104 static void swap_nodes(const node_ptr & node1, const node_ptr & header1, const node_ptr & node2, const node_ptr & header2); 105 106 //! @copydoc ::boost::intrusive::bstree_algorithms::replace_node(const node_ptr&,const node_ptr&) 107 static void replace_node(const node_ptr & node_to_be_replaced, const node_ptr & new_node); 108 109 //! @copydoc ::boost::intrusive::bstree_algorithms::replace_node(const node_ptr&,const node_ptr&,const node_ptr&) 110 static void replace_node(const node_ptr & node_to_be_replaced, const node_ptr & header, const node_ptr & new_node); 111 112 //Unlink is not possible since tree metadata is needed to update the tree 113 //!static void unlink(const node_ptr & node); 114 115 //! @copydoc ::boost::intrusive::bstree_algorithms::unlink_leftmost_without_rebalance 116 static node_ptr unlink_leftmost_without_rebalance(const node_ptr & header); 117 118 //! @copydoc ::boost::intrusive::bstree_algorithms::unique(const const_node_ptr&) 119 static bool unique(const const_node_ptr & node); 120 121 //! @copydoc ::boost::intrusive::bstree_algorithms::size(const const_node_ptr&) 122 static std::size_t size(const const_node_ptr & header); 123 124 //! @copydoc ::boost::intrusive::bstree_algorithms::next_node(const node_ptr&) 125 static node_ptr next_node(const node_ptr & node); 126 127 //! @copydoc ::boost::intrusive::bstree_algorithms::prev_node(const node_ptr&) 128 static node_ptr prev_node(const node_ptr & node); 129 130 //! @copydoc ::boost::intrusive::bstree_algorithms::init(const node_ptr&) 131 static void init(const node_ptr & node); 132 133 //! @copydoc ::boost::intrusive::bstree_algorithms::init_header(const node_ptr&) 134 static void init_header(const node_ptr & header); 135 #endif //#ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED 136 137 //! @copydoc ::boost::intrusive::bstree_algorithms::erase(const node_ptr&,const node_ptr&) 138 template<class AlphaByMaxSize> erase(const node_ptr & header,const node_ptr & z,std::size_t tree_size,std::size_t & max_tree_size,AlphaByMaxSize alpha_by_maxsize)139 static node_ptr erase(const node_ptr & header, const node_ptr & z, std::size_t tree_size, std::size_t &max_tree_size, AlphaByMaxSize alpha_by_maxsize) 140 { 141 //typename bstree_algo::data_for_rebalance info; 142 bstree_algo::erase(header, z); 143 --tree_size; 144 if (tree_size > 0 && 145 tree_size < alpha_by_maxsize(max_tree_size)){ 146 bstree_algo::rebalance(header); 147 max_tree_size = tree_size; 148 } 149 return z; 150 } 151 152 #ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED 153 //! @copydoc ::boost::intrusive::bstree_algorithms::clone(const const_node_ptr&,const node_ptr&,Cloner,Disposer) 154 template <class Cloner, class Disposer> 155 static void clone 156 (const const_node_ptr & source_header, const node_ptr & target_header, Cloner cloner, Disposer disposer); 157 158 //! @copydoc ::boost::intrusive::bstree_algorithms::clear_and_dispose(const node_ptr&,Disposer) 159 template<class Disposer> 160 static void clear_and_dispose(const node_ptr & header, Disposer disposer); 161 162 //! @copydoc ::boost::intrusive::bstree_algorithms::lower_bound(const const_node_ptr&,const KeyType&,KeyNodePtrCompare) 163 template<class KeyType, class KeyNodePtrCompare> 164 static node_ptr lower_bound 165 (const const_node_ptr & header, const KeyType &key, KeyNodePtrCompare comp); 166 167 //! @copydoc ::boost::intrusive::bstree_algorithms::upper_bound(const const_node_ptr&,const KeyType&,KeyNodePtrCompare) 168 template<class KeyType, class KeyNodePtrCompare> 169 static node_ptr upper_bound 170 (const const_node_ptr & header, const KeyType &key, KeyNodePtrCompare comp); 171 172 //! @copydoc ::boost::intrusive::bstree_algorithms::find(const const_node_ptr&, const KeyType&,KeyNodePtrCompare) 173 template<class KeyType, class KeyNodePtrCompare> 174 static node_ptr find 175 (const const_node_ptr & header, const KeyType &key, KeyNodePtrCompare comp); 176 177 //! @copydoc ::boost::intrusive::bstree_algorithms::equal_range(const const_node_ptr&,const KeyType&,KeyNodePtrCompare) 178 template<class KeyType, class KeyNodePtrCompare> 179 static std::pair<node_ptr, node_ptr> equal_range 180 (const const_node_ptr & header, const KeyType &key, KeyNodePtrCompare comp); 181 182 //! @copydoc ::boost::intrusive::bstree_algorithms::bounded_range(const const_node_ptr&,const KeyType&,const KeyType&,KeyNodePtrCompare,bool,bool) 183 template<class KeyType, class KeyNodePtrCompare> 184 static std::pair<node_ptr, node_ptr> bounded_range 185 (const const_node_ptr & header, const KeyType &lower_key, const KeyType &upper_key, KeyNodePtrCompare comp 186 , bool left_closed, bool right_closed); 187 188 //! @copydoc ::boost::intrusive::bstree_algorithms::count(const const_node_ptr&,const KeyType&,KeyNodePtrCompare) 189 template<class KeyType, class KeyNodePtrCompare> 190 static std::size_t count(const const_node_ptr & header, const KeyType &key, KeyNodePtrCompare comp); 191 192 #endif //#ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED 193 194 //! @copydoc ::boost::intrusive::bstree_algorithms::insert_equal_upper_bound(const node_ptr&,const node_ptr&,NodePtrCompare) 195 template<class NodePtrCompare, class H_Alpha> insert_equal_upper_bound(const node_ptr & h,const node_ptr & new_node,NodePtrCompare comp,std::size_t tree_size,H_Alpha h_alpha,std::size_t & max_tree_size)196 static node_ptr insert_equal_upper_bound 197 (const node_ptr & h, const node_ptr & new_node, NodePtrCompare comp 198 ,std::size_t tree_size, H_Alpha h_alpha, std::size_t &max_tree_size) 199 { 200 std::size_t depth; 201 bstree_algo::insert_equal_upper_bound(h, new_node, comp, &depth); 202 rebalance_after_insertion(new_node, depth, tree_size+1, h_alpha, max_tree_size); 203 return new_node; 204 } 205 206 //! @copydoc ::boost::intrusive::bstree_algorithms::insert_equal_lower_bound(const node_ptr&,const node_ptr&,NodePtrCompare) 207 template<class NodePtrCompare, class H_Alpha> insert_equal_lower_bound(const node_ptr & h,const node_ptr & new_node,NodePtrCompare comp,std::size_t tree_size,H_Alpha h_alpha,std::size_t & max_tree_size)208 static node_ptr insert_equal_lower_bound 209 (const node_ptr & h, const node_ptr & new_node, NodePtrCompare comp 210 ,std::size_t tree_size, H_Alpha h_alpha, std::size_t &max_tree_size) 211 { 212 std::size_t depth; 213 bstree_algo::insert_equal_lower_bound(h, new_node, comp, &depth); 214 rebalance_after_insertion(new_node, depth, tree_size+1, h_alpha, max_tree_size); 215 return new_node; 216 } 217 218 //! @copydoc ::boost::intrusive::bstree_algorithms::insert_equal(const node_ptr&,const node_ptr&,const node_ptr&,NodePtrCompare) 219 template<class NodePtrCompare, class H_Alpha> insert_equal(const node_ptr & header,const node_ptr & hint,const node_ptr & new_node,NodePtrCompare comp,std::size_t tree_size,H_Alpha h_alpha,std::size_t & max_tree_size)220 static node_ptr insert_equal 221 (const node_ptr & header, const node_ptr & hint, const node_ptr & new_node, NodePtrCompare comp 222 ,std::size_t tree_size, H_Alpha h_alpha, std::size_t &max_tree_size) 223 { 224 std::size_t depth; 225 bstree_algo::insert_equal(header, hint, new_node, comp, &depth); 226 rebalance_after_insertion(new_node, depth, tree_size+1, h_alpha, max_tree_size); 227 return new_node; 228 } 229 230 //! @copydoc ::boost::intrusive::bstree_algorithms::insert_before(const node_ptr&,const node_ptr&,const node_ptr&) 231 template<class H_Alpha> insert_before(const node_ptr & header,const node_ptr & pos,const node_ptr & new_node,std::size_t tree_size,H_Alpha h_alpha,std::size_t & max_tree_size)232 static node_ptr insert_before 233 (const node_ptr & header, const node_ptr & pos, const node_ptr & new_node 234 ,std::size_t tree_size, H_Alpha h_alpha, std::size_t &max_tree_size) 235 { 236 std::size_t depth; 237 bstree_algo::insert_before(header, pos, new_node, &depth); 238 rebalance_after_insertion(new_node, depth, tree_size+1, h_alpha, max_tree_size); 239 return new_node; 240 } 241 242 //! @copydoc ::boost::intrusive::bstree_algorithms::push_back(const node_ptr&,const node_ptr&) 243 template<class H_Alpha> push_back(const node_ptr & header,const node_ptr & new_node,std::size_t tree_size,H_Alpha h_alpha,std::size_t & max_tree_size)244 static void push_back(const node_ptr & header, const node_ptr & new_node 245 ,std::size_t tree_size, H_Alpha h_alpha, std::size_t &max_tree_size) 246 { 247 std::size_t depth; 248 bstree_algo::push_back(header, new_node, &depth); 249 rebalance_after_insertion(new_node, depth, tree_size+1, h_alpha, max_tree_size); 250 } 251 252 //! @copydoc ::boost::intrusive::bstree_algorithms::push_front(const node_ptr&,const node_ptr&) 253 template<class H_Alpha> push_front(const node_ptr & header,const node_ptr & new_node,std::size_t tree_size,H_Alpha h_alpha,std::size_t & max_tree_size)254 static void push_front(const node_ptr & header, const node_ptr & new_node 255 ,std::size_t tree_size, H_Alpha h_alpha, std::size_t &max_tree_size) 256 { 257 std::size_t depth; 258 bstree_algo::push_front(header, new_node, &depth); 259 rebalance_after_insertion(new_node, depth, tree_size+1, h_alpha, max_tree_size); 260 } 261 262 //! @copydoc ::boost::intrusive::bstree_algorithms::insert_unique_check(const const_node_ptr&,const KeyType&,KeyNodePtrCompare,insert_commit_data&) 263 template<class KeyType, class KeyNodePtrCompare> insert_unique_check(const const_node_ptr & header,const KeyType & key,KeyNodePtrCompare comp,insert_commit_data & commit_data)264 static std::pair<node_ptr, bool> insert_unique_check 265 (const const_node_ptr & header, const KeyType &key 266 ,KeyNodePtrCompare comp, insert_commit_data &commit_data) 267 { 268 std::size_t depth; 269 std::pair<node_ptr, bool> ret = 270 bstree_algo::insert_unique_check(header, key, comp, commit_data, &depth); 271 commit_data.depth = depth; 272 return ret; 273 } 274 275 //! @copydoc ::boost::intrusive::bstree_algorithms::insert_unique_check(const const_node_ptr&,const node_ptr&,const KeyType&,KeyNodePtrCompare,insert_commit_data&) 276 template<class KeyType, class KeyNodePtrCompare> insert_unique_check(const const_node_ptr & header,const node_ptr & hint,const KeyType & key,KeyNodePtrCompare comp,insert_commit_data & commit_data)277 static std::pair<node_ptr, bool> insert_unique_check 278 (const const_node_ptr & header, const node_ptr &hint, const KeyType &key 279 ,KeyNodePtrCompare comp, insert_commit_data &commit_data) 280 { 281 std::size_t depth; 282 std::pair<node_ptr, bool> ret = 283 bstree_algo::insert_unique_check 284 (header, hint, key, comp, commit_data, &depth); 285 commit_data.depth = depth; 286 return ret; 287 } 288 289 //! @copydoc ::boost::intrusive::bstree_algorithms::insert_unique_commit(const node_ptr&,const node_ptr&,const insert_commit_data&) 290 template<class H_Alpha> insert_unique_commit(const node_ptr & header,const 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)291 static void insert_unique_commit 292 (const node_ptr & header, const node_ptr & new_value, const insert_commit_data &commit_data 293 ,std::size_t tree_size, H_Alpha h_alpha, std::size_t &max_tree_size) 294 { 295 bstree_algo::insert_unique_commit(header, new_value, commit_data); 296 rebalance_after_insertion(new_value, commit_data.depth, tree_size+1, h_alpha, max_tree_size); 297 } 298 299 #ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED 300 //! @copydoc ::boost::intrusive::bstree_algorithms::is_header 301 static bool is_header(const const_node_ptr & p); 302 303 //! @copydoc ::boost::intrusive::bstree_algorithms::is_header 304 static void rebalance(const node_ptr & header); 305 306 //! @copydoc ::boost::intrusive::bstree_algorithms::rebalance_subtree 307 static node_ptr rebalance_subtree(const node_ptr & old_root) 308 #endif //#ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED 309 310 /// @cond 311 private: 312 313 template<class H_Alpha> rebalance_after_insertion(const node_ptr & x,std::size_t depth,std::size_t tree_size,H_Alpha h_alpha,std::size_t & max_tree_size)314 static void rebalance_after_insertion 315 (const node_ptr &x, std::size_t depth 316 , std::size_t tree_size, H_Alpha h_alpha, std::size_t &max_tree_size) 317 { 318 if(tree_size > max_tree_size) 319 max_tree_size = tree_size; 320 321 if(tree_size > 2 && //Nothing to do with only the root 322 //Check if the root node is unbalanced 323 //Scapegoat paper depth counts root depth as zero and "depth" counts root as 1, 324 //but since "depth" is the depth of the ancestor of x, i == depth 325 depth > h_alpha(tree_size)){ 326 327 //Find the first non height-balanced node 328 //as described in the section 4.2 of the paper. 329 //This method is the alternative method described 330 //in the paper. Authors claim that this method 331 //may tend to yield more balanced trees on the average 332 //than the weight balanced method. 333 node_ptr s = x; 334 std::size_t size = 1; 335 for(std::size_t ancestor = 1; ancestor != depth; ++ancestor){ 336 const node_ptr s_parent = NodeTraits::get_parent(s); 337 const node_ptr s_parent_left = NodeTraits::get_left(s_parent); 338 //Obtain parent's size (previous size + parent + sibling tree) 339 const node_ptr s_sibling = s_parent_left == s ? NodeTraits::get_right(s_parent) : s_parent_left; 340 size += 1 + bstree_algo::subtree_size(s_sibling); 341 s = s_parent; 342 if(ancestor > h_alpha(size)){ //is 's' scapegoat? 343 bstree_algo::rebalance_subtree(s); 344 return; 345 } 346 } 347 //The whole tree must be rebuilt 348 max_tree_size = tree_size; 349 bstree_algo::rebalance_subtree(NodeTraits::get_parent(s)); 350 } 351 } 352 /// @endcond 353 }; 354 355 /// @cond 356 357 template<class NodeTraits> 358 struct get_algo<SgTreeAlgorithms, NodeTraits> 359 { 360 typedef sgtree_algorithms<NodeTraits> type; 361 }; 362 363 template <class ValueTraits, class NodePtrCompare, class ExtraChecker> 364 struct get_node_checker<SgTreeAlgorithms, ValueTraits, NodePtrCompare, ExtraChecker> 365 { 366 typedef detail::bstree_node_checker<ValueTraits, NodePtrCompare, ExtraChecker> type; 367 }; 368 369 /// @endcond 370 371 } //namespace intrusive 372 } //namespace boost 373 374 #include <boost/intrusive/detail/config_end.hpp> 375 376 #endif //BOOST_INTRUSIVE_SGTREE_ALGORITHMS_HPP 377