Branch data Line data Source code
1 : : // Splay tree utilities -*- C++ -*-
2 : : // Copyright (C) 2020-2025 Free Software Foundation, Inc.
3 : : //
4 : : // This file is part of GCC.
5 : : //
6 : : // GCC is free software; you can redistribute it and/or modify it under
7 : : // the terms of the GNU General Public License as published by the Free
8 : : // Software Foundation; either version 3, or (at your option) any later
9 : : // version.
10 : : //
11 : : // GCC is distributed in the hope that it will be useful, but WITHOUT ANY
12 : : // WARRANTY; without even the implied warranty of MERCHANTABILITY or
13 : : // FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
14 : : // for more details.
15 : : //
16 : : // You should have received a copy of the GNU General Public License
17 : : // along with GCC; see the file COPYING3. If not see
18 : : // <http://www.gnu.org/licenses/>.
19 : :
20 : : // INDEX is either 0 or 1. If it is 0, return NODE's left child,
21 : : // otherwise return NODE's right child.
22 : : template<typename Accessors>
23 : : inline typename base_splay_tree<Accessors>::node_type
24 : 166126517 : base_splay_tree<Accessors>::get_child (node_type node, unsigned int index)
25 : : {
26 : 174337429 : return Accessors::child (node, index);
27 : : }
28 : :
29 : : // INDEX is either 0 or 1. If it is 0, change NODE's left child to CHILD,
30 : : // otherwise change NODE's right child to CHILD. If CHILD has a parent
31 : : // field, record that its parent is now NODE.
32 : : template<typename Accessors>
33 : : inline void
34 : 2155593 : base_splay_tree<Accessors>::set_child (node_type node, unsigned int index,
35 : : node_type child)
36 : : {
37 : 71204097 : Accessors::child (node, index) = child;
38 : 331446 : if (child)
39 : 321928 : set_parent (child, node);
40 : 30845298 : }
41 : :
42 : : // Rotate the tree to promote child number INDEX of NODE, so that that
43 : : // child becomes a parent of NODE. Return the promoted node.
44 : : //
45 : : // The caller has the responsibility of assigning a correct parent
46 : : // to the returned node.
47 : : template<typename Accessors>
48 : : inline typename base_splay_tree<Accessors>::node_type
49 : 828409 : base_splay_tree<Accessors>::promote_child (node_type node, unsigned int index)
50 : : {
51 : 828409 : node_type promoted = get_child (node, index);
52 : 376051 : set_child (node, index, get_child (promoted, 1 - index));
53 : 376051 : set_child (promoted, 1 - index, node);
54 : : return promoted;
55 : : }
56 : :
57 : : // Treat child number INDEX of NODE as being CHILD and rotate the tree
58 : : // so that CHILD becomes a parent of NODE.
59 : : //
60 : : // The caller has the responsibility of assigning a correct parent to CHILD.
61 : : template<typename Accessors>
62 : : inline void
63 : 44672260 : base_splay_tree<Accessors>::promote_child (node_type node, unsigned int index,
64 : : node_type child)
65 : : {
66 : 44668381 : set_child (node, index, get_child (child, 1 - index));
67 : 13257748 : set_child (child, 1 - index, node);
68 : 12695142 : }
69 : :
70 : : // Print NODE to PP, using PRINTER (PP, N) to print the contents of node N.
71 : : // Prefix each new line with INDENT_STRING. CODE is 'T' if NODE is the root
72 : : // node, 'L' if NODE is the left child of its parent, or 'R' if NODE is the
73 : : // right child of its parent.
74 : : template<typename Accessors>
75 : : template<typename Printer>
76 : : void
77 : 800 : base_splay_tree<Accessors>::print (pretty_printer *pp, node_type node,
78 : : Printer printer, char code,
79 : : vec<char> &indent_string)
80 : : {
81 : : // In the comments below, PREFIX refers to the incoming contents
82 : : // of INDENT_STRING.
83 : 800 : node_type left = get_child (node, 0);
84 : 800 : node_type right = get_child (node, 1);
85 : :
86 : 800 : auto orig_indent_len = indent_string.length ();
87 : 800 : indent_string.safe_grow (orig_indent_len + 3);
88 : 800 : char *extra_indent = indent_string.address () + orig_indent_len;
89 : :
90 : : // Print [T], [L], or [R].
91 : 800 : extra_indent[0] = '[';
92 : 800 : extra_indent[1] = code;
93 : 800 : extra_indent[2] = ']';
94 : 800 : pp_append_text (pp, extra_indent, indent_string.end ());
95 : 800 : pp_space (pp);
96 : :
97 : : // Print the node itself, using PREFIX + " | " or PREFIX + " " to indent
98 : : // new lines under the "[_]" that we just printed.
99 : 800 : extra_indent[0] = ' ';
100 : 800 : extra_indent[1] = (left || right ? '|' : ' ');
101 : 800 : extra_indent[2] = ' ';
102 : : {
103 : 800 : pretty_printer sub_pp;
104 : 800 : printer (&sub_pp, node);
105 : 800 : const char *text = pp_formatted_text (&sub_pp);
106 : 800 : while (const char *end = strchr (text, '\n'))
107 : : {
108 : 0 : pp_append_text (pp, text, end);
109 : 0 : pp_newline_and_indent (pp, 0);
110 : 0 : pp_append_text (pp, indent_string.begin (), indent_string.end ());
111 : 0 : text = end + 1;
112 : : }
113 : 800 : pp_string (pp, text);
114 : 800 : }
115 : :
116 : 800 : if (left)
117 : : {
118 : : // Print PREFIX + " +-" for the first line of the left subtree,
119 : : // to be followed by "[L]".
120 : 412 : extra_indent[1] = '+';
121 : 412 : extra_indent[2] = '-';
122 : 412 : pp_newline_and_indent (pp, 0);
123 : 412 : pp_append_text (pp, indent_string.begin (), indent_string.end ());
124 : :
125 : : // Print the left subtree, using PREFIX + " | " or PREFIX + " "
126 : : // to indent under the PREFIX + " +-" that we just printed.
127 : 412 : extra_indent[1] = right ? '|' : ' ';
128 : 412 : extra_indent[2] = ' ';
129 : 412 : print (pp, left, printer, 'L', indent_string);
130 : 412 : extra_indent = indent_string.address () + orig_indent_len;
131 : :
132 : : // If LEFT is not a leaf and we also have a right subtree, use a
133 : : // PREFIX + " |" line to separate them.
134 : 412 : if (right && (get_child (left, 0) || get_child (left, 1)))
135 : : {
136 : 192 : pp_newline_and_indent (pp, 0);
137 : 384 : pp_append_text (pp, indent_string.begin (), &extra_indent[2]);
138 : : }
139 : : }
140 : 800 : if (right)
141 : : {
142 : : // Print PREFIX + " +-" for the first line of the right subtree,
143 : : // to be followed by "[R]".
144 : 384 : extra_indent[1] = '+';
145 : 384 : extra_indent[2] = '-';
146 : 384 : pp_newline_and_indent (pp, 0);
147 : 384 : pp_append_text (pp, indent_string.begin (), indent_string.end ());
148 : :
149 : : // Print the right subtree, using PREFIX + " " to indent under the
150 : : // PREFIX + " +-" that we just printed.
151 : 384 : extra_indent[1] = ' ';
152 : 384 : extra_indent[2] = ' ';
153 : 384 : print (pp, right, printer, 'R', indent_string);
154 : : }
155 : 800 : indent_string.truncate (orig_indent_len);
156 : 800 : }
157 : :
158 : : // See the comment above the declaration.
159 : : template<typename Accessors>
160 : : template<typename Printer>
161 : : void
162 : 4 : base_splay_tree<Accessors>::print (pretty_printer *pp, node_type node,
163 : : Printer printer)
164 : : {
165 : 4 : if (!node)
166 : : {
167 : 0 : pp_string (pp, "null");
168 : 0 : return;
169 : : }
170 : 4 : auto_vec<char, 64> indent_string;
171 : 4 : print (pp, node, printer, 'T', indent_string);
172 : 4 : }
173 : :
174 : : // If N is 1, splay the last (rightmost) node reachable from START
175 : : // to the position that START current holds and return the splayed node.
176 : : // START is not itself the last node.
177 : : //
178 : : // If N is 0, splay the first (leftmost) node reachable from START
179 : : // to the position that START current holds and return the splayed node.
180 : : // START is not itself the first node.
181 : : //
182 : : // The caller has the responsibility of updating the parent of the
183 : : // returned node.
184 : : template<typename Accessors>
185 : : template<unsigned int N>
186 : : typename base_splay_tree<Accessors>::node_type
187 : 828409 : base_splay_tree<Accessors>::splay_limit (node_type start)
188 : : {
189 : : // This essentially follows the simpilfied top-down method described
190 : : // in Sleator and Tarjan's "Self-adjusting Binary Search Trees", but
191 : : // specialized for the case in which the comparison result is fixed.
192 : : // The first iteration is peeled to avoid the need for stack temporaries.
193 : : //
194 : : // The comments and names reflect the behavior for N == 1, but the
195 : : // N == 0 case behaves analogously.
196 : :
197 : : // Rotate the tree to promote the right child of START to the root.
198 : 828409 : node_type node = promote_child (start, N);
199 : 828409 : if (node_type right = get_child (node, N))
200 : : {
201 : : // Perform the link left step, which for this first iteration
202 : : // means making NODE the root of the left tree.
203 : : //
204 : : // NODE will become left child of the final node. For a right
205 : : // spine starting at NODE of the form:
206 : : //
207 : : // 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> ... -> N
208 : : // | | | | | | | |
209 : : // V V V V V V V V
210 : : // A B C D E F G NL
211 : : //
212 : : // the next step is to create a subtree of N whose right spine contains
213 : : // the odd-numbered nodes, as follows:
214 : : //
215 : : // N
216 : : // |
217 : : // V
218 : : // 1 ------> 3 ------> 5 ------> 7 -> .... -> NL
219 : : // | | | |
220 : : // V V V V
221 : : // A 2 -> C 4 -> E 6 -> G
222 : : // | | |
223 : : // V V V
224 : : // B D F
225 : : //
226 : : // First record 1 as the left child of the final root (N) and move
227 : : // on to node 2.
228 : : node_type final_child = node;
229 : : node_type new_spine_end = node;
230 : : node = right;
231 : 770851 : while (node_type right = get_child (node, N))
232 : : {
233 : : // Perform another rotate left step.
234 : : //
235 : : // We've built the tree rooted at 1 in the diagram above up to,
236 : : // but not including, an even-numbered node NODE on the original
237 : : // right spine. Rotate the tree at NODE to promote the following
238 : : // odd-numbered node.
239 : 376786 : promote_child (node, N, right);
240 : 376786 : node = right;
241 : 376786 : if (node_type right = get_child (node, N))
242 : : {
243 : : // Perform another link left step.
244 : : //
245 : : // Add the promoted odd-numbered node to the right spine of the
246 : : // tree rooted at 1 and move on to the next even-numbered node.
247 : 258201 : set_child (new_spine_end, N, node);
248 : 258201 : new_spine_end = node;
249 : 258201 : node = right;
250 : : }
251 : : }
252 : : // Perform the assembly step.
253 : : //
254 : : // Add NL to the new spine and make N the new root.
255 : 394256 : set_child (new_spine_end, N, get_child (node, 1 - N));
256 : 394065 : set_child (node, 1 - N, final_child);
257 : : }
258 : 828409 : return node;
259 : : }
260 : :
261 : : // Remove NODE from its position in the splay tree. If NODE has at least
262 : : // one child node, return the node that should now hold NODE's position in
263 : : // the splay tree. If NODE has no children, return null.
264 : : //
265 : : // The caller has the responsibility of updating the parent of the
266 : : // returned node.
267 : : template<typename Accessors>
268 : : inline typename base_splay_tree<Accessors>::node_type
269 : 2385377 : base_splay_tree<Accessors>::remove_node_internal (node_type node)
270 : : {
271 : 2385377 : node_type left = get_child (node, 0);
272 : 2385377 : node_type right = get_child (node, 1);
273 : 2385377 : if (!left)
274 : : return right;
275 : :
276 : 1428673 : if (!right)
277 : : return left;
278 : :
279 : 1184850 : if (get_child (left, 1))
280 : : {
281 : 434653 : left = splay_limit<1> (left);
282 : 434653 : gcc_checking_assert (!get_child (left, 1));
283 : : }
284 : 1184850 : set_child (left, 1, right);
285 : 1184850 : return left;
286 : : }
287 : :
288 : : // See the comment above the declaration.
289 : : template<typename Accessors>
290 : : inline void
291 : 74729394 : base_splay_tree<Accessors>::insert_child (node_type node, unsigned int index,
292 : : node_type child)
293 : : {
294 : 74729394 : gcc_checking_assert (!get_child (child, 0) && !get_child (child, 1));
295 : 74729394 : set_child (child, index, get_child (node, index));
296 : 74729394 : set_child (node, index, child);
297 : 74729394 : }
298 : :
299 : : // Implement splay_next_node if N == 1 and splay_prev_node if N == 0.
300 : : template<typename Accessors>
301 : : template<unsigned int N>
302 : : bool
303 : 30635762 : rooted_splay_tree<Accessors>::splay_neighbor ()
304 : : {
305 : 30635762 : node_type node = m_root;
306 : 30635762 : node_type new_root = get_child (node, N);
307 : 30635762 : if (!new_root)
308 : : return false;
309 : :
310 : 13064849 : if (get_child (new_root, 1 - N))
311 : : {
312 : : // NEW_ROOT is not itself the required node, so splay the required
313 : : // node into its place.
314 : 374055 : new_root = parent::template splay_limit<1 - N> (new_root);
315 : 374055 : gcc_checking_assert (!get_child (new_root, 1 - N));
316 : 374055 : set_child (node, N, node_type ());
317 : 374055 : set_child (new_root, 1 - N, node);
318 : : }
319 : : else
320 : 12690794 : promote_child (node, N, new_root);
321 : : set_parent (new_root, node_type ());
322 : 13064849 : m_root = new_root;
323 : 13064849 : return true;
324 : : }
325 : :
326 : : // See the comment above the declaration.
327 : : template<typename Accessors>
328 : : template<typename Comparator>
329 : : bool
330 : 800 : rooted_splay_tree<Accessors>::insert (node_type new_node, Comparator compare)
331 : : {
332 : 800 : gcc_checking_assert (!get_child (new_node, 0) && !get_child (new_node, 1));
333 : 800 : if (!m_root)
334 : : {
335 : 4 : m_root = new_node;
336 : 4 : return true;
337 : : }
338 : :
339 : 796 : int comparison = lookup (compare);
340 : 796 : if (comparison == 0)
341 : : return false;
342 : :
343 : 796 : insert_relative (comparison, new_node);
344 : 796 : return true;
345 : : }
346 : :
347 : : // See the comment above the declaration.
348 : : template<typename Accessors>
349 : : inline void
350 : 3949638 : rooted_splay_tree<Accessors>::insert_relative (int comparison,
351 : : node_type new_node)
352 : : {
353 : 3949638 : gcc_checking_assert (!get_child (new_node, 0)
354 : : && !get_child (new_node, 1)
355 : : && (!m_root || comparison != 0));
356 : 3949638 : if (m_root)
357 : : {
358 : : // Insert NEW_NODE before M_ROOT if COMPARISON < 0 and after M_ROOT
359 : : // otherwise.
360 : 3949638 : set_child (new_node, comparison < 0, m_root);
361 : 3949638 : set_child (new_node, comparison > 0, get_child (m_root, comparison > 0));
362 : 3949638 : set_child (m_root, comparison > 0, node_type ());
363 : : }
364 : 3949638 : m_root = new_node;
365 : 3949638 : }
366 : :
367 : : // See the comment above the declaration.
368 : : template<typename Accessors>
369 : : inline void
370 : 46279164 : rooted_splay_tree<Accessors>::insert_max_node (node_type new_node)
371 : : {
372 : 46279164 : gcc_checking_assert (!get_child (new_node, 0) && !get_child (new_node, 1));
373 : 46279164 : set_child (new_node, 0, m_root);
374 : 46279164 : m_root = new_node;
375 : 46279164 : }
376 : :
377 : : // See the comment above the declaration.
378 : : template<typename Accessors>
379 : : inline void
380 : 543 : rooted_splay_tree<Accessors>::splice_next_tree (rooted_splay_tree next_tree)
381 : : {
382 : 543 : splay_max_node ();
383 : 543 : set_child (m_root, 1, next_tree.m_root);
384 : 543 : }
385 : :
386 : : // See the comment above the declaration.
387 : : template<typename Accessors>
388 : : inline void
389 : : rooted_splay_tree<Accessors>::replace_max_node_at_root (node_type new_node)
390 : : {
391 : : node_type old_node = m_root;
392 : : gcc_checking_assert (!get_child (new_node, 0)
393 : : && !get_child (new_node, 1)
394 : : && !get_child (old_node, 1));
395 : : set_child (new_node, 0, get_child (old_node, 0));
396 : : // Clear the links from OLD_NODE. Its parent and right child are
397 : : // already node_type ().
398 : : set_child (old_node, 0, node_type ());
399 : : m_root = new_node;
400 : : }
401 : :
402 : : // See the comment above the declaration.
403 : : template<typename Accessors>
404 : : inline void
405 : 1598410 : rooted_splay_tree<Accessors>::remove_root ()
406 : : {
407 : 1598410 : node_type node = m_root;
408 : 1598410 : m_root = parent::remove_node_internal (node);
409 : : if (m_root)
410 : 1598410 : set_parent (m_root, node_type ());
411 : : // Clear the links from NODE. Its parent is already node_type ().
412 : 1598410 : set_child (node, 0, node_type ());
413 : 1598410 : set_child (node, 1, node_type ());
414 : 1598410 : }
415 : :
416 : : // See the comment above the declaration.
417 : : template<typename Accessors>
418 : : inline bool
419 : 19172 : rooted_splay_tree<Accessors>::remove_root_and_splay_next ()
420 : : {
421 : 19172 : node_type node = m_root;
422 : 19172 : node_type right = get_child (node, 1);
423 : 19172 : if (right)
424 : : {
425 : : // Bring the minimum right-hand node to the root.
426 : 163 : if (get_child (right, 0))
427 : : {
428 : 7 : right = parent::template splay_limit<0> (right);
429 : 7 : gcc_checking_assert (!get_child (right, 0));
430 : : }
431 : 163 : set_child (right, 0, get_child (node, 0));
432 : 163 : m_root = right;
433 : : }
434 : : else
435 : 19009 : m_root = get_child (node, 0);
436 : : if (m_root)
437 : 19172 : set_parent (m_root, node_type ());
438 : :
439 : : // Clear the links from NODE. Its parent is already node_type ().
440 : 19172 : set_child (node, 0, node_type ());
441 : 19172 : set_child (node, 1, node_type ());
442 : 19172 : return right;
443 : : }
444 : :
445 : : // See the comment above the declaration.
446 : : template<typename Accessors>
447 : : inline rooted_splay_tree<Accessors>
448 : 7 : rooted_splay_tree<Accessors>::split_before_root ()
449 : : {
450 : 7 : node_type new_root = get_child (m_root, 0);
451 : 7 : set_child (m_root, 0, node_type ());
452 : 3 : set_parent (new_root, node_type ());
453 : 7 : return new_root;
454 : : }
455 : :
456 : : // See the comment above the declaration.
457 : : template<typename Accessors>
458 : : inline rooted_splay_tree<Accessors>
459 : 4 : rooted_splay_tree<Accessors>::split_after_root ()
460 : : {
461 : 4 : node_type new_root = get_child (m_root, 1);
462 : 4 : set_child (m_root, 1, node_type ());
463 : 0 : set_parent (new_root, node_type ());
464 : 4 : return new_root;
465 : : }
466 : :
467 : : // See the comment above the declaration.
468 : : template<typename Accessors>
469 : : inline bool
470 : 8614397 : rooted_splay_tree<Accessors>::splay_prev_node ()
471 : : {
472 : 8614397 : return splay_neighbor<0> ();
473 : : }
474 : :
475 : : // See the comment above the declaration.
476 : : template<typename Accessors>
477 : : inline bool
478 : 22021365 : rooted_splay_tree<Accessors>::splay_next_node ()
479 : : {
480 : 22021365 : return splay_neighbor<1> ();
481 : : }
482 : :
483 : : // See the comment above the declaration.
484 : : template<typename Accessors>
485 : : inline void
486 : 13110 : rooted_splay_tree<Accessors>::splay_min_node ()
487 : : {
488 : 13110 : if (m_root && get_child (m_root, 0))
489 : : {
490 : 8973 : m_root = parent::template splay_limit<0> (m_root);
491 : 8973 : set_parent (m_root, node_type ());
492 : : }
493 : 13110 : }
494 : :
495 : : // See the comment above the declaration.
496 : : template<typename Accessors>
497 : : inline void
498 : 15505 : rooted_splay_tree<Accessors>::splay_max_node ()
499 : : {
500 : 15505 : if (m_root && get_child (m_root, 1))
501 : : {
502 : 10721 : m_root = parent::template splay_limit<1> (m_root);
503 : 10721 : set_parent (m_root, node_type ());
504 : : }
505 : 15505 : }
506 : :
507 : : // See the comment above the declaration.
508 : : template<typename Accessors>
509 : : inline typename rooted_splay_tree<Accessors>::node_type
510 : 4 : rooted_splay_tree<Accessors>::min_node ()
511 : : {
512 : 4 : splay_min_node ();
513 : 4 : return m_root;
514 : : }
515 : :
516 : : // See the comment above the declaration.
517 : : template<typename Accessors>
518 : : inline typename rooted_splay_tree<Accessors>::node_type
519 : 4 : rooted_splay_tree<Accessors>::max_node ()
520 : : {
521 : 4 : splay_max_node ();
522 : 4 : return m_root;
523 : : }
524 : :
525 : : // See the comment above the declaration.
526 : : template<typename Accessors>
527 : : template<typename Comparator>
528 : : auto
529 : 48224360 : rooted_splay_tree<Accessors>::lookup (Comparator compare)
530 : : -> decltype (compare (m_root))
531 : : {
532 : : // This essentially follows the simpilfied top-down method described
533 : : // in Sleator and Tarjan's "Self-adjusting Binary Search Trees", but
534 : : // with the complication that the comparisons are done only once.
535 : : using result_type = decltype (compare (m_root));
536 : :
537 : : // The roots of the left and right trees.
538 : 48224360 : node_type link_left_root = node_type ();
539 : 48224360 : node_type link_right_root = node_type ();
540 : :
541 : : // Where to add new nodes to the left and right trees.
542 : 48224360 : node_type *link_left_ptr = &link_left_root;
543 : 48224360 : node_type *link_right_ptr = &link_right_root;
544 : :
545 : : // The nodes that contain *LINK_LEFT_PTR and *LINK_RIGHT_PTR,
546 : : // once they no longer point to the roots above.
547 : 48224360 : node_type link_left_parent = node_type ();
548 : 48224360 : node_type link_right_parent = node_type ();
549 : :
550 : 57688016 : auto link_left = [&](node_type node)
551 : : {
552 : 9463656 : *link_left_ptr = node;
553 : 9463656 : link_left_ptr = &Accessors::child (node, 1);
554 : 533945 : set_parent (node, link_left_parent);
555 : 9463656 : link_left_parent = node;
556 : : };
557 : :
558 : 79637119 : auto link_right = [&](node_type node)
559 : : {
560 : 31412759 : *link_right_ptr = node;
561 : 31412759 : link_right_ptr = &Accessors::child (node, 0);
562 : 34889 : set_parent (node, link_right_parent);
563 : 31412759 : link_right_parent = node;
564 : : };
565 : :
566 : 48224360 : node_type node = m_root;
567 : 48224360 : node_type parent = node_type ();
568 : : result_type result;
569 : 48224360 : result_type old_result = 0;
570 : : while (1)
571 : : {
572 : : // OLD_RESULT is 0 if NODE is the root of the middle tree.
573 : : // Otherwise, PARENT is the root of the middle tree and OLD_RESULT
574 : : // is how it compared.
575 : : //
576 : : // Results are:
577 : : // < 0 if we want something smaller.
578 : : // = 0 if we found the right node.
579 : : // > 0 if we want something bigger.
580 : 110237438 : result = compare (node);
581 : 110237438 : if (old_result < 0)
582 : : {
583 : 32757298 : if (result < 0)
584 : : {
585 : : // SEARCH < NODE < PARENT
586 : : //
587 : : // Promote NODE (rotate right).
588 : 19685858 : promote_child (parent, 0, node);
589 : 19685858 : node_type next = get_child (node, 0);
590 : 19685858 : if (!next)
591 : : break;
592 : :
593 : 18341319 : link_right (node);
594 : :
595 : : // NEXT is now the root of the middle tree.
596 : 18341319 : node = next;
597 : 18341319 : old_result = 0;
598 : 18341319 : continue;
599 : 18341319 : }
600 : :
601 : : // SEARCH >= NODE, NODE < PARENT
602 : 13071440 : link_right (parent);
603 : : }
604 : 77480140 : else if (old_result > 0)
605 : : {
606 : 9611377 : if (result > 0)
607 : : {
608 : : // SEARCH > NODE > PARENT
609 : : //
610 : : // Promote NODE (rotate left).
611 : 1450805 : promote_child (parent, 1, node);
612 : 1450805 : node_type next = get_child (node, 1);
613 : 1450805 : if (!next)
614 : : break;
615 : :
616 : 1303084 : link_left (node);
617 : :
618 : : // NEXT is now the root of the middle tree.
619 : 1303084 : node = next;
620 : 1303084 : old_result = 0;
621 : 1303084 : continue;
622 : 1303084 : }
623 : :
624 : : // SEARCH <= NODE, NODE > PARENT
625 : 8160572 : link_left (parent);
626 : : }
627 : :
628 : : // Microoptimization to allow NODE to be read even if RESULT == 0.
629 : 89100775 : node_type next = get_child (node, result >= 0);
630 : 89100775 : if (result == 0 || !next)
631 : : break;
632 : :
633 : : // NODE is now the root of the tree.
634 : : parent = node;
635 : : node = next;
636 : : old_result = result;
637 : : }
638 : :
639 : 48224360 : node_type new_left = link_left_root;
640 : 48224360 : node_type new_right = link_right_root;
641 : :
642 : 48224360 : if (new_left)
643 : : {
644 : 8514758 : node_type old_left = get_child (node, 0);
645 : 8514758 : *link_left_ptr = old_left;
646 : 309556 : if (old_left)
647 : 1112 : set_parent (old_left, link_left_parent);
648 : 8514758 : set_child (node, 0, new_left);
649 : : }
650 : :
651 : 48224360 : if (new_right)
652 : : {
653 : 14785289 : node_type old_right = get_child (node, 1);
654 : 14785289 : *link_right_ptr = old_right;
655 : 28931 : if (old_right)
656 : 950 : set_parent (old_right, link_right_parent);
657 : 14785289 : set_child (node, 1, new_right);
658 : : }
659 : :
660 : 334217 : set_parent (node, node_type ());
661 : 48224360 : m_root = node;
662 : 48224360 : return result;
663 : : }
664 : :
665 : : // See the comment above the declaration.
666 : : template<typename Accessors>
667 : : template<typename LeftPredicate, typename RightPredicate>
668 : : int
669 : 2663472 : rooted_splay_tree<Accessors>::lookup (LeftPredicate want_something_smaller,
670 : : RightPredicate want_something_bigger)
671 : : {
672 : : // This essentially follows the simpilfied top-down method described
673 : : // in Sleator and Tarjan's "Self-adjusting Binary Search Trees"
674 : : // (and follows it more closely than the single-comparator version above).
675 : :
676 : : // The roots of the left and right trees.
677 : 2663472 : node_type link_left_root = node_type ();
678 : 2663472 : node_type link_right_root = node_type ();
679 : :
680 : : // Where to add new nodes to the left and right trees.
681 : 2663472 : node_type *link_left_ptr = &link_left_root;
682 : 2663472 : node_type *link_right_ptr = &link_right_root;
683 : :
684 : : // The nodes that contain *LINK_LEFT_PTR and *LINK_RIGHT_PTR,
685 : : // once they no longer point to the roots above.
686 : 2663472 : node_type link_left_parent = node_type ();
687 : 2663472 : node_type link_right_parent = node_type ();
688 : :
689 : 2663472 : node_type node = m_root;
690 : : int result;
691 : : for (;;)
692 : : {
693 : : // NODE is the root of the middle tree.
694 : 15137926 : if (want_something_smaller (node))
695 : : {
696 : 11241760 : result = -1;
697 : 11241760 : node_type next = get_child (node, 0);
698 : 11241760 : if (!next)
699 : : break;
700 : :
701 : 10862476 : if (want_something_smaller (next))
702 : : {
703 : : // Promote NODE (rotate right).
704 : 9871683 : promote_child (node, 0, next);
705 : 9871683 : node = next;
706 : 9871683 : next = get_child (node, 0);
707 : 9871683 : if (!next)
708 : : break;
709 : : }
710 : :
711 : : // Add NODE to the right tree (link right).
712 : 10674895 : *link_right_ptr = node;
713 : 10674895 : link_right_ptr = &Accessors::child (node, 0);
714 : : set_parent (node, link_right_parent);
715 : 10674895 : link_right_parent = node;
716 : :
717 : 10674895 : node = next;
718 : : }
719 : 3896166 : else if (want_something_bigger (node))
720 : : {
721 : 2662412 : result = 1;
722 : 2662412 : node_type next = get_child (node, 1);
723 : 2662412 : if (!next)
724 : : break;
725 : :
726 : 1908373 : if (want_something_bigger (next))
727 : : {
728 : : // Promote NODE (rotate left).
729 : 588107 : promote_child (node, 1, next);
730 : 588107 : node = next;
731 : 588107 : next = get_child (node, 1);
732 : 588107 : if (!next)
733 : : break;
734 : : }
735 : :
736 : : // Add NODE to the left tree (link left).
737 : 1799559 : *link_left_ptr = node;
738 : 1799559 : link_left_ptr = &Accessors::child (node, 1);
739 : : set_parent (node, link_left_parent);
740 : 1799559 : link_left_parent = node;
741 : :
742 : 1799559 : node = next;
743 : : }
744 : : else
745 : : {
746 : : result = 0;
747 : : break;
748 : : }
749 : : }
750 : :
751 : 2663472 : node_type new_left = link_left_root;
752 : 2663472 : node_type new_right = link_right_root;
753 : :
754 : 2663472 : if (new_left)
755 : : {
756 : 1258718 : node_type old_left = get_child (node, 0);
757 : 1258718 : *link_left_ptr = old_left;
758 : : if (old_left)
759 : : set_parent (old_left, link_left_parent);
760 : 1258718 : set_child (node, 0, new_left);
761 : : }
762 : :
763 : 2663472 : if (new_right)
764 : : {
765 : 1568775 : node_type old_right = get_child (node, 1);
766 : 1568775 : *link_right_ptr = old_right;
767 : : if (old_right)
768 : : set_parent (old_right, link_right_parent);
769 : 1568775 : set_child (node, 1, new_right);
770 : : }
771 : :
772 : : set_parent (node, node_type ());
773 : 2663472 : m_root = node;
774 : 2663472 : return result;
775 : : }
776 : :
777 : : // See the comment above the declaration.
778 : : template<typename Accessors>
779 : : template<typename LeftPredicate, typename RightPredicate>
780 : : int
781 : 226467 : rooted_splay_tree<Accessors>::lookup_le (LeftPredicate want_something_smaller,
782 : : RightPredicate want_something_bigger)
783 : : {
784 : 226467 : int comparison = lookup (want_something_smaller, want_something_bigger);
785 : 244201 : if (comparison < 0 && splay_prev_node ())
786 : : comparison = 1;
787 : 226467 : return comparison;
788 : : }
789 : :
790 : : // See the comment above the declaration.
791 : : template<typename Accessors>
792 : : template<typename Printer>
793 : : inline void
794 : 4 : rooted_splay_tree<Accessors>::print (pretty_printer *pp, Printer printer) const
795 : : {
796 : 4 : print (pp, m_root, printer);
797 : : }
798 : :
799 : : // Return NODE's current parent.
800 : : template<typename Accessors>
801 : : inline typename rootless_splay_tree<Accessors>::node_type
802 : 800756 : rootless_splay_tree<Accessors>::get_parent (node_type node)
803 : : {
804 : 800756 : return Accessors::parent (node);
805 : : }
806 : :
807 : : // CHILD is known to be a child of PARENT. Return which index it has.
808 : : template<typename Accessors>
809 : : inline unsigned int
810 : 458623 : rootless_splay_tree<Accessors>::child_index (node_type parent, node_type child)
811 : : {
812 : 463215 : return get_child (parent, 1) == child;
813 : : }
814 : :
815 : : // If N == 1, implement splay_known_max_node, otherwise implement
816 : : // splay_known_min_node.
817 : : template<typename Accessors>
818 : : template<unsigned int N>
819 : : inline void
820 : : rootless_splay_tree<Accessors>::splay_known_limit (node_type node)
821 : : {
822 : : node_type child = node;
823 : : node_type parent = get_parent (child);
824 : : if (!parent)
825 : : return;
826 : :
827 : : do
828 : : // At this point, NODE conceptually replaces CHILD as a child of
829 : : // PARENT, but we haven't yet updated PARENT accordingly.
830 : : if (node_type grandparent = get_parent (parent))
831 : : {
832 : : node_type greatgrandparent = get_parent (grandparent);
833 : : promote_child (grandparent, N, parent);
834 : : promote_child (parent, N, node);
835 : : child = grandparent;
836 : : parent = greatgrandparent;
837 : : }
838 : : else
839 : : {
840 : : promote_child (parent, N, node);
841 : : break;
842 : : }
843 : : while (parent);
844 : : set_parent (node, node_type ());
845 : : }
846 : :
847 : : // See the comment above the declaration.
848 : : template<typename Accessors>
849 : : typename rootless_splay_tree<Accessors>::node_type
850 : 786967 : rootless_splay_tree<Accessors>::remove_node (node_type node)
851 : : {
852 : 786967 : node_type replacement = parent::remove_node_internal (node);
853 : 786967 : if (node_type parent = get_parent (node))
854 : 451161 : set_child (parent, child_index (parent, node), replacement);
855 : 335806 : else if (replacement)
856 : 335806 : set_parent (replacement, node_type ());
857 : : // Clear the links from NODE.
858 : 786967 : set_parent (node, node_type ());
859 : 786967 : set_child (node, 0, node_type ());
860 : 786967 : set_child (node, 1, node_type ());
861 : 786967 : return replacement;
862 : : }
863 : :
864 : : // See the comment above the declaration.
865 : : template<typename Accessors>
866 : : void
867 : : rootless_splay_tree<Accessors>::splay (node_type node)
868 : : {
869 : : node_type child = node;
870 : : node_type parent = get_parent (child);
871 : : if (!parent)
872 : : return;
873 : :
874 : : do
875 : : {
876 : : // At this point, NODE conceptually replaces CHILD as a child of
877 : : // PARENT, but we haven't yet updated PARENT accordingly.
878 : : unsigned int index = child_index (parent, child);
879 : : if (node_type grandparent = get_parent (parent))
880 : : {
881 : : node_type greatgrandparent = get_parent (grandparent);
882 : : unsigned int parent_index = child_index (grandparent, parent);
883 : : if (index == parent_index)
884 : : {
885 : : promote_child (grandparent, parent_index, parent);
886 : : promote_child (parent, index, node);
887 : : }
888 : : else
889 : : {
890 : : promote_child (parent, index, node);
891 : : promote_child (grandparent, parent_index, node);
892 : : }
893 : : child = grandparent;
894 : : parent = greatgrandparent;
895 : : }
896 : : else
897 : : {
898 : : promote_child (parent, index, node);
899 : : break;
900 : : }
901 : : }
902 : : while (parent);
903 : : set_parent (node, node_type ());
904 : : }
905 : :
906 : : // See the comment above the declaration.
907 : : template<typename Accessors>
908 : : inline void
909 : : rootless_splay_tree<Accessors>::splay_known_min_node (node_type node)
910 : : {
911 : : splay_known_limit<0> (node);
912 : : }
913 : :
914 : : // See the comment above the declaration.
915 : : template<typename Accessors>
916 : : inline void
917 : : rootless_splay_tree<Accessors>::splay_known_max_node (node_type node)
918 : : {
919 : : splay_known_limit<1> (node);
920 : : }
921 : :
922 : : // See the comment above the declaration.
923 : : template<typename Accessors>
924 : : template<typename DefaultResult, typename Predicate>
925 : : auto
926 : 4136 : rootless_splay_tree<Accessors>::
927 : : splay_and_search (node_type node, DefaultResult default_result,
928 : : Predicate predicate)
929 : : -> decltype (predicate (node, 0))
930 : : {
931 : : using Result = decltype (predicate (node, 0));
932 : :
933 : 4136 : node_type child = node;
934 : 4136 : node_type parent = get_parent (child);
935 : 4136 : if (!parent)
936 : : return default_result;
937 : :
938 : : do
939 : : {
940 : : // At this point, NODE conceptually replaces CHILD as a child of
941 : : // PARENT, but we haven't yet updated PARENT accordingly.
942 : 7462 : unsigned int index = child_index (parent, child);
943 : 2401 : if (Result result = predicate (parent, index))
944 : : {
945 : 2401 : set_child (parent, index, node);
946 : 2401 : return result;
947 : : }
948 : 5061 : if (node_type grandparent = get_parent (parent))
949 : : {
950 : 4592 : node_type greatgrandparent = get_parent (grandparent);
951 : 4592 : unsigned int parent_index = child_index (grandparent, parent);
952 : 713 : if (Result result = predicate (grandparent, parent_index))
953 : : {
954 : 713 : set_child (parent, index, node);
955 : 713 : return result;
956 : : }
957 : 3879 : if (index == parent_index)
958 : : {
959 : 2225 : promote_child (grandparent, parent_index, parent);
960 : 2225 : promote_child (parent, index, node);
961 : : }
962 : : else
963 : : {
964 : 1654 : promote_child (parent, index, node);
965 : 1654 : promote_child (grandparent, parent_index, node);
966 : : }
967 : 3879 : child = grandparent;
968 : 3879 : parent = greatgrandparent;
969 : : }
970 : : else
971 : : {
972 : 469 : promote_child (parent, index, node);
973 : : break;
974 : : }
975 : : }
976 : 3879 : while (parent);
977 : 815 : set_parent (node, node_type ());
978 : 815 : return default_result;
979 : : }
980 : :
981 : : // Splay NODE1 looking to see if one of its ancestors is NODE2. If it is,
982 : : // return -1 if NODE1 comes before NODE2 or 1 if NODE1 comes after NODE2.
983 : : // Return 0 if NODE2 is not an ancestor of NODE1.
984 : : template<typename Accessors>
985 : : int
986 : 3039 : rootless_splay_tree<Accessors>::compare_nodes_one_way (node_type node1,
987 : : node_type node2)
988 : : {
989 : 13707 : auto compare = [&](node_type parent, unsigned int index) -> int
990 : : {
991 : 10668 : if (parent == node2)
992 : 2017 : return index ? 1 : -1;
993 : : return 0;
994 : : };
995 : 3039 : return splay_and_search (node1, 0, compare);
996 : : }
997 : :
998 : : // See the comment above the declaration.
999 : : template<typename Accessors>
1000 : : int
1001 : 2017 : rootless_splay_tree<Accessors>::compare_nodes (node_type node1,
1002 : : node_type node2)
1003 : : {
1004 : 2017 : if (node1 == node2)
1005 : : return 0;
1006 : :
1007 : : // Splay NODE1 looking for NODE2.
1008 : 2017 : int cmp = compare_nodes_one_way (node1, node2);
1009 : 2017 : if (cmp)
1010 : : return cmp;
1011 : :
1012 : : // That failed, but NODE1 is now the root of the tree. Splay NODE2
1013 : : // to see on which side of NODE1 it falls.
1014 : 1022 : cmp = compare_nodes_one_way (node2, node1);
1015 : 1022 : gcc_checking_assert (cmp);
1016 : 1022 : return -cmp;
1017 : : }
|
