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> |
139 | static node_ptr erase(const node_ptr & , 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> |
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> |
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> |
220 | static node_ptr insert_equal |
221 | (const node_ptr & , 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> |
232 | static node_ptr insert_before |
233 | (const node_ptr & , 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> |
244 | static void push_back(const node_ptr & , 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> |
254 | static void push_front(const node_ptr & , 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> |
264 | static std::pair<node_ptr, bool> insert_unique_check |
265 | (const const_node_ptr & , 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> |
277 | static std::pair<node_ptr, bool> insert_unique_check |
278 | (const const_node_ptr & , 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> |
291 | static void insert_unique_commit |
292 | (const node_ptr & , 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> |
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 | |