Line data Source code
1 : // Splay tree utilities -*- C++ -*-
2 : // Copyright (C) 2020-2026 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 222948646 : base_splay_tree<Accessors>::get_child (node_type node, unsigned int index)
25 : {
26 205881993 : 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 351540845 : base_splay_tree<Accessors>::set_child (node_type node, unsigned int index,
35 : node_type child)
36 : {
37 2506530 : Accessors::child (node, index) = child;
38 344770 : if (child)
39 320176 : set_parent (child, node);
40 41897865 : }
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 887937 : base_splay_tree<Accessors>::promote_child (node_type node, unsigned int index)
50 : {
51 887937 : node_type promoted = get_child (node, index);
52 380490 : set_child (node, index, get_child (promoted, 1 - index));
53 380490 : 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 53735652 : base_splay_tree<Accessors>::promote_child (node_type node, unsigned int index,
64 : node_type child)
65 : {
66 53731768 : set_child (node, index, get_child (child, 1 - index));
67 13104324 : set_child (child, 1 - index, node);
68 12505190 : }
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 887937 : 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 887937 : node_type node = promote_child (start, N);
199 887937 : 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 779283 : 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 390057 : promote_child (node, N, right);
240 390057 : node = right;
241 390057 : 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 278501 : set_child (new_spine_end, N, node);
248 278501 : new_spine_end = node;
249 278501 : node = right;
250 : }
251 : }
252 : // Perform the assembly step.
253 : //
254 : // Add NL to the new spine and make N the new root.
255 389401 : set_child (new_spine_end, N, get_child (node, 1 - N));
256 389226 : set_child (node, 1 - N, final_child);
257 : }
258 887937 : 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 2892108 : base_splay_tree<Accessors>::remove_node_internal (node_type node)
270 : {
271 2892108 : node_type left = get_child (node, 0);
272 2892108 : node_type right = get_child (node, 1);
273 2892108 : if (!left)
274 : return right;
275 :
276 1792375 : if (!right)
277 : return left;
278 :
279 1514541 : if (get_child (left, 1))
280 : {
281 486640 : left = splay_limit<1> (left);
282 486640 : gcc_checking_assert (!get_child (left, 1));
283 : }
284 1514541 : set_child (left, 1, right);
285 1514541 : return left;
286 : }
287 :
288 : // See the comment above the declaration.
289 : template<typename Accessors>
290 : inline void
291 103147241 : base_splay_tree<Accessors>::insert_child (node_type node, unsigned int index,
292 : node_type child)
293 : {
294 103147241 : gcc_checking_assert (!get_child (child, 0) && !get_child (child, 1));
295 103147241 : set_child (child, index, get_child (node, index));
296 103147241 : set_child (node, index, child);
297 103147241 : }
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 33841938 : rooted_splay_tree<Accessors>::splay_neighbor ()
304 : {
305 33841938 : node_type node = m_root;
306 33841938 : node_type new_root = get_child (node, N);
307 33841938 : if (!new_root)
308 : return false;
309 :
310 12879406 : 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 378561 : new_root = parent::template splay_limit<1 - N> (new_root);
315 378561 : gcc_checking_assert (!get_child (new_root, 1 - N));
316 378561 : set_child (node, N, node_type ());
317 378561 : set_child (new_root, 1 - N, node);
318 : }
319 : else
320 12500845 : promote_child (node, N, new_root);
321 : set_parent (new_root, node_type ());
322 12879406 : m_root = new_root;
323 12879406 : 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 8137776 : rooted_splay_tree<Accessors>::insert_relative (int comparison,
351 : node_type new_node)
352 : {
353 8137776 : gcc_checking_assert (!get_child (new_node, 0)
354 : && !get_child (new_node, 1)
355 : && (!m_root || comparison != 0));
356 8137776 : if (m_root)
357 : {
358 : // Insert NEW_NODE before M_ROOT if COMPARISON < 0 and after M_ROOT
359 : // otherwise.
360 8137776 : set_child (new_node, comparison < 0, m_root);
361 8137776 : set_child (new_node, comparison > 0, get_child (m_root, comparison > 0));
362 8137776 : set_child (m_root, comparison > 0, node_type ());
363 : }
364 8137776 : m_root = new_node;
365 8137776 : }
366 :
367 : // See the comment above the declaration.
368 : template<typename Accessors>
369 : inline void
370 63476181 : rooted_splay_tree<Accessors>::insert_max_node (node_type new_node)
371 : {
372 63476181 : gcc_checking_assert (!get_child (new_node, 0) && !get_child (new_node, 1));
373 63476181 : set_child (new_node, 0, m_root);
374 63476181 : m_root = new_node;
375 63476181 : }
376 :
377 : // See the comment above the declaration.
378 : template<typename Accessors>
379 : inline void
380 688 : rooted_splay_tree<Accessors>::splice_next_tree (rooted_splay_tree next_tree)
381 : {
382 688 : splay_max_node ();
383 688 : set_child (m_root, 1, next_tree.m_root);
384 688 : }
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 2073043 : rooted_splay_tree<Accessors>::remove_root ()
406 : {
407 2073043 : node_type node = m_root;
408 2073043 : m_root = parent::remove_node_internal (node);
409 : if (m_root)
410 2073043 : set_parent (m_root, node_type ());
411 : // Clear the links from NODE. Its parent is already node_type ().
412 2073043 : set_child (node, 0, node_type ());
413 2073043 : set_child (node, 1, node_type ());
414 2073043 : }
415 :
416 : // See the comment above the declaration.
417 : template<typename Accessors>
418 : inline bool
419 20845 : rooted_splay_tree<Accessors>::remove_root_and_splay_next ()
420 : {
421 20845 : node_type node = m_root;
422 20845 : node_type right = get_child (node, 1);
423 20845 : if (right)
424 : {
425 : // Bring the minimum right-hand node to the root.
426 229 : if (get_child (right, 0))
427 : {
428 19 : right = parent::template splay_limit<0> (right);
429 19 : gcc_checking_assert (!get_child (right, 0));
430 : }
431 229 : set_child (right, 0, get_child (node, 0));
432 229 : m_root = right;
433 : }
434 : else
435 20616 : m_root = get_child (node, 0);
436 : if (m_root)
437 20845 : set_parent (m_root, node_type ());
438 :
439 : // Clear the links from NODE. Its parent is already node_type ().
440 20845 : set_child (node, 0, node_type ());
441 20845 : set_child (node, 1, node_type ());
442 20845 : return right;
443 : }
444 :
445 : // See the comment above the declaration.
446 : template<typename Accessors>
447 : inline rooted_splay_tree<Accessors>
448 4 : rooted_splay_tree<Accessors>::split_before_root ()
449 : {
450 4 : node_type new_root = get_child (m_root, 0);
451 4 : set_child (m_root, 0, node_type ());
452 0 : set_parent (new_root, node_type ());
453 4 : 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 9860380 : rooted_splay_tree<Accessors>::splay_prev_node ()
471 : {
472 9860380 : return splay_neighbor<0> ();
473 : }
474 :
475 : // See the comment above the declaration.
476 : template<typename Accessors>
477 : inline bool
478 23981558 : rooted_splay_tree<Accessors>::splay_next_node ()
479 : {
480 23981558 : return splay_neighbor<1> ();
481 : }
482 :
483 : // See the comment above the declaration.
484 : template<typename Accessors>
485 : inline void
486 15032 : rooted_splay_tree<Accessors>::splay_min_node ()
487 : {
488 15032 : if (m_root && get_child (m_root, 0))
489 : {
490 10704 : m_root = parent::template splay_limit<0> (m_root);
491 10704 : set_parent (m_root, node_type ());
492 : }
493 15032 : }
494 :
495 : // See the comment above the declaration.
496 : template<typename Accessors>
497 : inline void
498 16915 : rooted_splay_tree<Accessors>::splay_max_node ()
499 : {
500 16915 : if (m_root && get_child (m_root, 1))
501 : {
502 12013 : m_root = parent::template splay_limit<1> (m_root);
503 12013 : set_parent (m_root, node_type ());
504 : }
505 16915 : }
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 62040895 : 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 62040895 : node_type link_left_root = node_type ();
539 62040895 : node_type link_right_root = node_type ();
540 :
541 : // Where to add new nodes to the left and right trees.
542 62040895 : node_type *link_left_ptr = &link_left_root;
543 62040895 : 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 330115 : node_type link_left_parent = node_type ();
548 330115 : node_type link_right_parent = node_type ();
549 :
550 75951749 : auto link_left = [&](node_type node)
551 : {
552 13910854 : *link_left_ptr = node;
553 13910854 : link_left_ptr = &Accessors::child (node, 1);
554 548640 : set_parent (node, link_left_parent);
555 548640 : link_left_parent = node;
556 : };
557 :
558 100670833 : auto link_right = [&](node_type node)
559 : {
560 38629938 : *link_right_ptr = node;
561 38629938 : link_right_ptr = &Accessors::child (node, 0);
562 32483 : set_parent (node, link_right_parent);
563 32483 : link_right_parent = node;
564 : };
565 :
566 62040895 : node_type node = m_root;
567 62040895 : node_type parent = node_type ();
568 : result_type result;
569 62040895 : 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 143678043 : result = compare (node);
581 143678043 : if (old_result < 0)
582 : {
583 40302580 : if (result < 0)
584 : {
585 : // SEARCH < NODE < PARENT
586 : //
587 : // Promote NODE (rotate right).
588 25482653 : promote_child (parent, 0, node);
589 25482653 : node_type next = get_child (node, 0);
590 25482653 : if (!next)
591 : break;
592 :
593 23810011 : link_right (node);
594 :
595 : // NEXT is now the root of the middle tree.
596 23810011 : node = next;
597 23810011 : old_result = 0;
598 23810011 : continue;
599 23810011 : }
600 :
601 : // SEARCH >= NODE, NODE < PARENT
602 14819927 : link_right (parent);
603 : }
604 103375463 : else if (old_result > 0)
605 : {
606 14265351 : if (result > 0)
607 : {
608 : // SEARCH > NODE > PARENT
609 : //
610 : // Promote NODE (rotate left).
611 3613703 : promote_child (parent, 1, node);
612 3613703 : node_type next = get_child (node, 1);
613 3613703 : if (!next)
614 : break;
615 :
616 3259206 : link_left (node);
617 :
618 : // NEXT is now the root of the middle tree.
619 3259206 : node = next;
620 3259206 : old_result = 0;
621 3259206 : continue;
622 3259206 : }
623 :
624 : // SEARCH <= NODE, NODE > PARENT
625 10651648 : link_left (parent);
626 : }
627 :
628 : // Microoptimization to allow NODE to be read even if RESULT == 0.
629 114581687 : node_type next = get_child (node, result >= 0);
630 114581687 : 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 62040895 : node_type new_left = link_left_root;
640 62040895 : node_type new_right = link_right_root;
641 :
642 62040895 : if (new_left)
643 : {
644 11970916 : node_type old_left = get_child (node, 0);
645 11970916 : *link_left_ptr = old_left;
646 306745 : if (old_left)
647 982 : set_parent (old_left, link_left_parent);
648 11970916 : set_child (node, 0, new_left);
649 : }
650 :
651 62040895 : if (new_right)
652 : {
653 17808925 : node_type old_right = get_child (node, 1);
654 17808925 : *link_right_ptr = old_right;
655 28182 : if (old_right)
656 1728 : set_parent (old_right, link_right_parent);
657 17808925 : set_child (node, 1, new_right);
658 : }
659 :
660 330115 : set_parent (node, node_type ());
661 62040895 : m_root = node;
662 62040895 : return result;
663 : }
664 :
665 : // See the comment above the declaration.
666 : template<typename Accessors>
667 : template<typename LeftPredicate, typename RightPredicate>
668 : int
669 2886388 : 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 2886388 : node_type link_left_root = node_type ();
678 2886388 : node_type link_right_root = node_type ();
679 :
680 : // Where to add new nodes to the left and right trees.
681 2886388 : node_type *link_left_ptr = &link_left_root;
682 2886388 : 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 2886388 : node_type link_left_parent = node_type ();
687 2886388 : node_type link_right_parent = node_type ();
688 :
689 2886388 : node_type node = m_root;
690 : int result;
691 : for (;;)
692 : {
693 : // NODE is the root of the middle tree.
694 16931724 : if (want_something_smaller (node))
695 : {
696 12622241 : result = -1;
697 12622241 : node_type next = get_child (node, 0);
698 12622241 : if (!next)
699 : break;
700 :
701 12186998 : if (want_something_smaller (next))
702 : {
703 : // Promote NODE (rotate right).
704 11069766 : promote_child (node, 0, next);
705 11069766 : node = next;
706 11069766 : next = get_child (node, 0);
707 11069766 : if (!next)
708 : break;
709 : }
710 :
711 : // Add NODE to the right tree (link right).
712 11970835 : *link_right_ptr = node;
713 11970835 : link_right_ptr = &Accessors::child (node, 0);
714 : set_parent (node, link_right_parent);
715 11970835 : link_right_parent = node;
716 :
717 11970835 : node = next;
718 : }
719 4309483 : else if (want_something_bigger (node))
720 : {
721 2984497 : result = 1;
722 2984497 : node_type next = get_child (node, 1);
723 2984497 : if (!next)
724 : break;
725 :
726 2191363 : if (want_something_bigger (next))
727 : {
728 : // Promote NODE (rotate left).
729 670399 : promote_child (node, 1, next);
730 670399 : node = next;
731 670399 : next = get_child (node, 1);
732 670399 : if (!next)
733 : break;
734 : }
735 :
736 : // Add NODE to the left tree (link left).
737 2074501 : *link_left_ptr = node;
738 2074501 : link_left_ptr = &Accessors::child (node, 1);
739 : set_parent (node, link_left_parent);
740 2074501 : link_left_parent = node;
741 :
742 2074501 : node = next;
743 : }
744 : else
745 : {
746 : result = 0;
747 : break;
748 : }
749 : }
750 :
751 2886388 : node_type new_left = link_left_root;
752 2886388 : node_type new_right = link_right_root;
753 :
754 2886388 : if (new_left)
755 : {
756 1445014 : node_type old_left = get_child (node, 0);
757 1445014 : *link_left_ptr = old_left;
758 : if (old_left)
759 : set_parent (old_left, link_left_parent);
760 1445014 : set_child (node, 0, new_left);
761 : }
762 :
763 2886388 : if (new_right)
764 : {
765 1767447 : node_type old_right = get_child (node, 1);
766 1767447 : *link_right_ptr = old_right;
767 : if (old_right)
768 : set_parent (old_right, link_right_parent);
769 1767447 : set_child (node, 1, new_right);
770 : }
771 :
772 : set_parent (node, node_type ());
773 2886388 : m_root = node;
774 2886388 : return result;
775 : }
776 :
777 : // See the comment above the declaration.
778 : template<typename Accessors>
779 : template<typename LeftPredicate, typename RightPredicate>
780 : int
781 208785 : rooted_splay_tree<Accessors>::lookup_le (LeftPredicate want_something_smaller,
782 : RightPredicate want_something_bigger)
783 : {
784 208785 : int comparison = lookup (want_something_smaller, want_something_bigger);
785 228031 : if (comparison < 0 && splay_prev_node ())
786 : comparison = 1;
787 208785 : 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 833284 : rootless_splay_tree<Accessors>::get_parent (node_type node)
803 : {
804 833284 : 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 473601 : rootless_splay_tree<Accessors>::child_index (node_type parent, node_type child)
811 : {
812 478395 : 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 819065 : rootless_splay_tree<Accessors>::remove_node (node_type node)
851 : {
852 819065 : node_type replacement = parent::remove_node_internal (node);
853 819065 : if (node_type parent = get_parent (node))
854 465997 : set_child (parent, child_index (parent, node), replacement);
855 353068 : else if (replacement)
856 353067 : set_parent (replacement, node_type ());
857 : // Clear the links from NODE.
858 819065 : set_parent (node, node_type ());
859 819065 : set_child (node, 0, node_type ());
860 819065 : set_child (node, 1, node_type ());
861 819065 : 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 4170 : 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 4170 : node_type child = node;
934 4170 : node_type parent = get_parent (child);
935 4170 : 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 7604 : unsigned int index = child_index (parent, child);
943 2349 : if (Result result = predicate (parent, index))
944 : {
945 2349 : set_child (parent, index, node);
946 2349 : return result;
947 : }
948 5255 : if (node_type grandparent = get_parent (parent))
949 : {
950 4794 : node_type greatgrandparent = get_parent (grandparent);
951 4794 : unsigned int parent_index = child_index (grandparent, parent);
952 910 : if (Result result = predicate (grandparent, parent_index))
953 : {
954 910 : set_child (parent, index, node);
955 910 : return result;
956 : }
957 3884 : if (index == parent_index)
958 : {
959 2236 : promote_child (grandparent, parent_index, parent);
960 2236 : promote_child (parent, index, node);
961 : }
962 : else
963 : {
964 1648 : promote_child (parent, index, node);
965 1648 : promote_child (grandparent, parent_index, node);
966 : }
967 3884 : child = grandparent;
968 3884 : parent = greatgrandparent;
969 : }
970 : else
971 : {
972 461 : promote_child (parent, index, node);
973 : break;
974 : }
975 : }
976 3884 : while (parent);
977 805 : set_parent (node, node_type ());
978 805 : 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 2570 : rootless_splay_tree<Accessors>::compare_nodes_one_way (node_type node1,
987 : node_type node2)
988 : {
989 12759 : auto compare = [&](node_type parent, unsigned int index) -> int
990 : {
991 10189 : if (parent == node2)
992 1659 : return index ? 1 : -1;
993 : return 0;
994 : };
995 2570 : return splay_and_search (node1, 0, compare);
996 : }
997 :
998 : // See the comment above the declaration.
999 : template<typename Accessors>
1000 : int
1001 1659 : rootless_splay_tree<Accessors>::compare_nodes (node_type node1,
1002 : node_type node2)
1003 : {
1004 1659 : if (node1 == node2)
1005 : return 0;
1006 :
1007 : // Splay NODE1 looking for NODE2.
1008 1659 : int cmp = compare_nodes_one_way (node1, node2);
1009 1659 : 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 911 : cmp = compare_nodes_one_way (node2, node1);
1015 911 : gcc_checking_assert (cmp);
1016 911 : return -cmp;
1017 : }
|
