1// Splay tree utilities -*- C++ -*-
2// Copyright (C) 2020-2023 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.
22template<typename Accessors>
23inline typename base_splay_tree<Accessors>::node_type
24base_splay_tree<Accessors>::get_child (node_type node, unsigned int index)
25{
26 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.
32template<typename Accessors>
33inline void
34base_splay_tree<Accessors>::set_child (node_type node, unsigned int index,
35 node_type child)
36{
37 Accessors::child (node, index) = child;
38 if (child)
39 set_parent (child, node);
40}
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.
47template<typename Accessors>
48inline typename base_splay_tree<Accessors>::node_type
49base_splay_tree<Accessors>::promote_child (node_type node, unsigned int index)
50{
51 node_type promoted = get_child (node, index);
52 set_child (node, index, child: get_child (node: promoted, index: 1 - index));
53 set_child (node: promoted, index: 1 - index, child: 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.
61template<typename Accessors>
62inline void
63base_splay_tree<Accessors>::promote_child (node_type node, unsigned int index,
64 node_type child)
65{
66 set_child (node, index, child: get_child (node: child, index: 1 - index));
67 set_child (node: child, index: 1 - index, child: node);
68}
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.
74template<typename Accessors>
75template<typename Printer>
76void
77base_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 node_type left = get_child (node, index: 0);
84 node_type right = get_child (node, index: 1);
85
86 auto orig_indent_len = indent_string.length ();
87 indent_string.safe_grow (len: orig_indent_len + 3);
88 char *extra_indent = indent_string.address () + orig_indent_len;
89
90 // Print [T], [L], or [R].
91 extra_indent[0] = '[';
92 extra_indent[1] = code;
93 extra_indent[2] = ']';
94 pp_append_text (pp, extra_indent, indent_string.end ());
95 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 extra_indent[0] = ' ';
100 extra_indent[1] = (left || right ? '|' : ' ');
101 extra_indent[2] = ' ';
102 {
103 pretty_printer sub_pp;
104 printer (&sub_pp, node);
105 const char *text = pp_formatted_text (&sub_pp);
106 while (const char *end = strchr (s: text, c: '\n'))
107 {
108 pp_append_text (pp, text, end);
109 pp_newline_and_indent (pp, 0);
110 pp_append_text (pp, indent_string.begin (), indent_string.end ());
111 text = end + 1;
112 }
113 pp_string (pp, text);
114 }
115
116 if (left)
117 {
118 // Print PREFIX + " +-" for the first line of the left subtree,
119 // to be followed by "[L]".
120 extra_indent[1] = '+';
121 extra_indent[2] = '-';
122 pp_newline_and_indent (pp, 0);
123 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 extra_indent[1] = right ? '|' : ' ';
128 extra_indent[2] = ' ';
129 print (pp, left, printer, 'L', indent_string);
130 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 if (right && (get_child (node: left, index: 0) || get_child (node: left, index: 1)))
135 {
136 pp_newline_and_indent (pp, 0);
137 pp_append_text (pp, indent_string.begin (), &extra_indent[2]);
138 }
139 }
140 if (right)
141 {
142 // Print PREFIX + " +-" for the first line of the right subtree,
143 // to be followed by "[R]".
144 extra_indent[1] = '+';
145 extra_indent[2] = '-';
146 pp_newline_and_indent (pp, 0);
147 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 extra_indent[1] = ' ';
152 extra_indent[2] = ' ';
153 print (pp, right, printer, 'R', indent_string);
154 }
155 indent_string.truncate (size: orig_indent_len);
156}
157
158// See the comment above the declaration.
159template<typename Accessors>
160template<typename Printer>
161void
162base_splay_tree<Accessors>::print (pretty_printer *pp, node_type node,
163 Printer printer)
164{
165 if (!node)
166 {
167 pp_string (pp, "null");
168 return;
169 }
170 auto_vec<char, 64> indent_string;
171 print (pp, node, printer, 'T', indent_string);
172}
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.
184template<typename Accessors>
185template<unsigned int N>
186typename base_splay_tree<Accessors>::node_type
187base_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 node_type node = promote_child (start, N);
199 if (node_type right = get_child (node, index: 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 while (node_type right = get_child (node, index: 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 promote_child (node, N, right);
240 node = right;
241 if (node_type right = get_child (node, index: 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 set_child (node: new_spine_end, index: N, child: node);
248 new_spine_end = node;
249 node = right;
250 }
251 }
252 // Perform the assembly step.
253 //
254 // Add NL to the new spine and make N the new root.
255 set_child (node: new_spine_end, index: N, child: get_child (node, index: 1 - N));
256 set_child (node, index: 1 - N, child: final_child);
257 }
258 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.
267template<typename Accessors>
268inline typename base_splay_tree<Accessors>::node_type
269base_splay_tree<Accessors>::remove_node_internal (node_type node)
270{
271 node_type left = get_child (node, index: 0);
272 node_type right = get_child (node, index: 1);
273 if (!left)
274 return right;
275
276 if (!right)
277 return left;
278
279 if (get_child (node: left, index: 1))
280 {
281 left = splay_limit<1> (left);
282 gcc_checking_assert (!get_child (left, 1));
283 }
284 set_child (node: left, index: 1, child: right);
285 return left;
286}
287
288// See the comment above the declaration.
289template<typename Accessors>
290inline void
291base_splay_tree<Accessors>::insert_child (node_type node, unsigned int index,
292 node_type child)
293{
294 gcc_checking_assert (!get_child (child, 0) && !get_child (child, 1));
295 set_child (node: child, index, child: get_child (node, index));
296 set_child (node, index, child);
297}
298
299// Implement splay_next_node if N == 1 and splay_prev_node if N == 0.
300template<typename Accessors>
301template<unsigned int N>
302bool
303rooted_splay_tree<Accessors>::splay_neighbor ()
304{
305 node_type node = m_root;
306 node_type new_root = get_child (node, N);
307 if (!new_root)
308 return false;
309
310 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 new_root = parent::template splay_limit<1 - N> (new_root);
315 gcc_checking_assert (!get_child (new_root, 1 - N));
316 set_child (node, N, node_type ());
317 set_child (new_root, 1 - N, node);
318 }
319 else
320 promote_child (node, N, new_root);
321 set_parent (new_root, node_type ());
322 m_root = new_root;
323 return true;
324}
325
326// See the comment above the declaration.
327template<typename Accessors>
328template<typename Comparator>
329bool
330rooted_splay_tree<Accessors>::insert (node_type new_node, Comparator compare)
331{
332 gcc_checking_assert (!get_child (new_node, 0) && !get_child (new_node, 1));
333 if (!m_root)
334 {
335 m_root = new_node;
336 return true;
337 }
338
339 int comparison = lookup (compare);
340 if (comparison == 0)
341 return false;
342
343 // Insert NEW_NODE before M_ROOT if COMPARISON < 0 and after M_ROOT
344 // otherwise.
345 set_child (new_node, comparison < 0, m_root);
346 set_child (new_node, comparison > 0, get_child (m_root, comparison > 0));
347 set_child (m_root, comparison > 0, nullptr);
348 m_root = new_node;
349 return true;
350}
351
352// See the comment above the declaration.
353template<typename Accessors>
354inline void
355rooted_splay_tree<Accessors>::insert_max_node (node_type new_node)
356{
357 gcc_checking_assert (!get_child (new_node, 0) && !get_child (new_node, 1));
358 set_child (new_node, 0, m_root);
359 m_root = new_node;
360}
361
362// See the comment above the declaration.
363template<typename Accessors>
364inline void
365rooted_splay_tree<Accessors>::splice_next_tree (rooted_splay_tree next_tree)
366{
367 splay_max_node ();
368 set_child (m_root, 1, next_tree.m_root);
369}
370
371// See the comment above the declaration.
372template<typename Accessors>
373inline void
374rooted_splay_tree<Accessors>::replace_max_node_at_root (node_type new_node)
375{
376 node_type old_node = m_root;
377 gcc_checking_assert (!get_child (new_node, 0)
378 && !get_child (new_node, 1)
379 && !get_child (old_node, 1));
380 set_child (new_node, 0, get_child (old_node, 0));
381 // Clear the links from OLD_NODE. Its parent and right child are
382 // already node_type ().
383 set_child (old_node, 0, node_type ());
384 m_root = new_node;
385}
386
387// See the comment above the declaration.
388template<typename Accessors>
389inline void
390rooted_splay_tree<Accessors>::remove_root ()
391{
392 node_type node = m_root;
393 m_root = parent::remove_node_internal (node);
394 if (m_root)
395 set_parent (m_root, node_type ());
396 // Clear the links from NODE. Its parent is already node_type ().
397 set_child (node, 0, node_type ());
398 set_child (node, 1, node_type ());
399}
400
401// See the comment above the declaration.
402template<typename Accessors>
403inline rooted_splay_tree<Accessors>
404rooted_splay_tree<Accessors>::split_before_root ()
405{
406 node_type new_root = get_child (m_root, 0);
407 set_child (m_root, 0, node_type ());
408 set_parent (new_root, node_type ());
409 return new_root;
410}
411
412// See the comment above the declaration.
413template<typename Accessors>
414inline rooted_splay_tree<Accessors>
415rooted_splay_tree<Accessors>::split_after_root ()
416{
417 node_type new_root = get_child (m_root, 1);
418 set_child (m_root, 1, node_type ());
419 set_parent (new_root, node_type ());
420 return new_root;
421}
422
423// See the comment above the declaration.
424template<typename Accessors>
425inline bool
426rooted_splay_tree<Accessors>::splay_prev_node ()
427{
428 return splay_neighbor<0> ();
429}
430
431// See the comment above the declaration.
432template<typename Accessors>
433inline bool
434rooted_splay_tree<Accessors>::splay_next_node ()
435{
436 return splay_neighbor<1> ();
437}
438
439// See the comment above the declaration.
440template<typename Accessors>
441inline void
442rooted_splay_tree<Accessors>::splay_min_node ()
443{
444 if (m_root && get_child (m_root, 0))
445 {
446 m_root = parent::template splay_limit<0> (m_root);
447 set_parent (m_root, node_type ());
448 }
449}
450
451// See the comment above the declaration.
452template<typename Accessors>
453inline void
454rooted_splay_tree<Accessors>::splay_max_node ()
455{
456 if (m_root && get_child (m_root, 1))
457 {
458 m_root = parent::template splay_limit<1> (m_root);
459 set_parent (m_root, node_type ());
460 }
461}
462
463// See the comment above the declaration.
464template<typename Accessors>
465inline typename rooted_splay_tree<Accessors>::node_type
466rooted_splay_tree<Accessors>::min_node ()
467{
468 splay_min_node ();
469 return m_root;
470}
471
472// See the comment above the declaration.
473template<typename Accessors>
474inline typename rooted_splay_tree<Accessors>::node_type
475rooted_splay_tree<Accessors>::max_node ()
476{
477 splay_max_node ();
478 return m_root;
479}
480
481// See the comment above the declaration.
482template<typename Accessors>
483template<typename Comparator>
484auto
485rooted_splay_tree<Accessors>::lookup (Comparator compare)
486 -> decltype (compare (m_root))
487{
488 // This essentially follows the simpilfied top-down method described
489 // in Sleator and Tarjan's "Self-adjusting Binary Search Trees", but
490 // with the complication that the comparisons are done only once.
491 using result_type = decltype (compare (m_root));
492
493 // The roots of the left and right trees.
494 node_type link_left_root = node_type ();
495 node_type link_right_root = node_type ();
496
497 // Where to add new nodes to the left and right trees.
498 node_type *link_left_ptr = &link_left_root;
499 node_type *link_right_ptr = &link_right_root;
500
501 // The nodes that contain *LINK_LEFT_PTR and *LINK_RIGHT_PTR,
502 // once they no longer point to the roots above.
503 node_type link_left_parent = node_type ();
504 node_type link_right_parent = node_type ();
505
506 auto link_left = [&](node_type node)
507 {
508 *link_left_ptr = node;
509 link_left_ptr = &Accessors::child (node, 1);
510 set_parent (node, link_left_parent);
511 link_left_parent = node;
512 };
513
514 auto link_right = [&](node_type node)
515 {
516 *link_right_ptr = node;
517 link_right_ptr = &Accessors::child (node, 0);
518 set_parent (node, link_right_parent);
519 link_right_parent = node;
520 };
521
522 node_type node = m_root;
523 node_type parent = node_type ();
524 result_type result;
525 result_type old_result = 0;
526 while (1)
527 {
528 // OLD_RESULT is 0 if NODE is the root of the middle tree.
529 // Otherwise, PARENT is the root of the middle tree and OLD_RESULT
530 // is how it compared.
531 //
532 // Results are:
533 // < 0 if we want something smaller.
534 // = 0 if we found the right node.
535 // > 0 if we want something bigger.
536 result = compare (node);
537 if (old_result < 0)
538 {
539 if (result < 0)
540 {
541 // SEARCH < NODE < PARENT
542 //
543 // Promote NODE (rotate right).
544 promote_child (parent, 0, node);
545 node_type next = get_child (node, 0);
546 if (!next)
547 break;
548
549 link_right (node);
550
551 // NEXT is now the root of the middle tree.
552 node = next;
553 old_result = 0;
554 continue;
555 }
556
557 // SEARCH >= NODE, NODE < PARENT
558 link_right (parent);
559 }
560 else if (old_result > 0)
561 {
562 if (result > 0)
563 {
564 // SEARCH > NODE > PARENT
565 //
566 // Promote NODE (rotate left).
567 promote_child (parent, 1, node);
568 node_type next = get_child (node, 1);
569 if (!next)
570 break;
571
572 link_left (node);
573
574 // NEXT is now the root of the middle tree.
575 node = next;
576 old_result = 0;
577 continue;
578 }
579
580 // SEARCH <= NODE, NODE > PARENT
581 link_left (parent);
582 }
583
584 // Microoptimization to allow NODE to be read even if RESULT == 0.
585 node_type next = get_child (node, result >= 0);
586 if (result == 0 || !next)
587 break;
588
589 // NODE is now the root of the tree.
590 parent = node;
591 node = next;
592 old_result = result;
593 }
594
595 node_type new_left = link_left_root;
596 node_type new_right = link_right_root;
597
598 if (new_left)
599 {
600 node_type old_left = get_child (node, 0);
601 *link_left_ptr = old_left;
602 if (old_left)
603 set_parent (old_left, link_left_parent);
604 set_child (node, 0, new_left);
605 }
606
607 if (new_right)
608 {
609 node_type old_right = get_child (node, 1);
610 *link_right_ptr = old_right;
611 if (old_right)
612 set_parent (old_right, link_right_parent);
613 set_child (node, 1, new_right);
614 }
615
616 set_parent (node, node_type ());
617 m_root = node;
618 return result;
619}
620
621// See the comment above the declaration.
622template<typename Accessors>
623template<typename LeftPredicate, typename RightPredicate>
624int
625rooted_splay_tree<Accessors>::lookup (LeftPredicate want_something_smaller,
626 RightPredicate want_something_bigger)
627{
628 // This essentially follows the simpilfied top-down method described
629 // in Sleator and Tarjan's "Self-adjusting Binary Search Trees"
630 // (and follows it more closely than the single-comparator version above).
631
632 // The roots of the left and right trees.
633 node_type link_left_root = node_type ();
634 node_type link_right_root = node_type ();
635
636 // Where to add new nodes to the left and right trees.
637 node_type *link_left_ptr = &link_left_root;
638 node_type *link_right_ptr = &link_right_root;
639
640 // The nodes that contain *LINK_LEFT_PTR and *LINK_RIGHT_PTR,
641 // once they no longer point to the roots above.
642 node_type link_left_parent = node_type ();
643 node_type link_right_parent = node_type ();
644
645 node_type node = m_root;
646 int result;
647 for (;;)
648 {
649 // NODE is the root of the middle tree.
650 if (want_something_smaller (node))
651 {
652 result = -1;
653 node_type next = get_child (node, 0);
654 if (!next)
655 break;
656
657 if (want_something_smaller (next))
658 {
659 // Promote NODE (rotate right).
660 promote_child (node, 0, next);
661 node = next;
662 next = get_child (node, 0);
663 if (!next)
664 break;
665 }
666
667 // Add NODE to the right tree (link right).
668 *link_right_ptr = node;
669 link_right_ptr = &Accessors::child (node, 0);
670 set_parent (node, link_right_parent);
671 link_right_parent = node;
672
673 node = next;
674 }
675 else if (want_something_bigger (node))
676 {
677 result = 1;
678 node_type next = get_child (node, 1);
679 if (!next)
680 break;
681
682 if (want_something_bigger (next))
683 {
684 // Promote NODE (rotate left).
685 promote_child (node, 1, next);
686 node = next;
687 next = get_child (node, 1);
688 if (!next)
689 break;
690 }
691
692 // Add NODE to the left tree (link left).
693 *link_left_ptr = node;
694 link_left_ptr = &Accessors::child (node, 1);
695 set_parent (node, link_left_parent);
696 link_left_parent = node;
697
698 node = next;
699 }
700 else
701 {
702 result = 0;
703 break;
704 }
705 }
706
707 node_type new_left = link_left_root;
708 node_type new_right = link_right_root;
709
710 if (new_left)
711 {
712 node_type old_left = get_child (node, 0);
713 *link_left_ptr = old_left;
714 if (old_left)
715 set_parent (old_left, link_left_parent);
716 set_child (node, 0, new_left);
717 }
718
719 if (new_right)
720 {
721 node_type old_right = get_child (node, 1);
722 *link_right_ptr = old_right;
723 if (old_right)
724 set_parent (old_right, link_right_parent);
725 set_child (node, 1, new_right);
726 }
727
728 set_parent (node, node_type ());
729 m_root = node;
730 return result;
731}
732
733// See the comment above the declaration.
734template<typename Accessors>
735template<typename Printer>
736inline void
737rooted_splay_tree<Accessors>::print (pretty_printer *pp, Printer printer) const
738{
739 print (pp, m_root, printer);
740}
741
742// Return NODE's current parent.
743template<typename Accessors>
744inline typename rootless_splay_tree<Accessors>::node_type
745rootless_splay_tree<Accessors>::get_parent (node_type node)
746{
747 return Accessors::parent (node);
748}
749
750// CHILD is known to be a child of PARENT. Return which index it has.
751template<typename Accessors>
752inline unsigned int
753rootless_splay_tree<Accessors>::child_index (node_type parent, node_type child)
754{
755 return get_child (parent, 1) == child;
756}
757
758// If N == 1, implement splay_known_max_node, otherwise implement
759// splay_known_min_node.
760template<typename Accessors>
761template<unsigned int N>
762inline void
763rootless_splay_tree<Accessors>::splay_known_limit (node_type node)
764{
765 node_type child = node;
766 node_type parent = get_parent (node: child);
767 if (!parent)
768 return;
769
770 do
771 // At this point, NODE conceptually replaces CHILD as a child of
772 // PARENT, but we haven't yet updated PARENT accordingly.
773 if (node_type grandparent = get_parent (node: parent))
774 {
775 node_type greatgrandparent = get_parent (node: grandparent);
776 promote_child (grandparent, N, parent);
777 promote_child (parent, N, node);
778 child = grandparent;
779 parent = greatgrandparent;
780 }
781 else
782 {
783 promote_child (parent, N, node);
784 break;
785 }
786 while (parent);
787 set_parent (node, node_type ());
788}
789
790// See the comment above the declaration.
791template<typename Accessors>
792typename rootless_splay_tree<Accessors>::node_type
793rootless_splay_tree<Accessors>::remove_node (node_type node)
794{
795 node_type replacement = parent::remove_node_internal (node);
796 if (node_type parent = get_parent (node))
797 set_child (parent, child_index (parent, child: node), replacement);
798 else if (replacement)
799 set_parent (replacement, node_type ());
800 // Clear the links from NODE.
801 set_parent (node, node_type ());
802 set_child (node, 0, node_type ());
803 set_child (node, 1, node_type ());
804 return replacement;
805}
806
807// See the comment above the declaration.
808template<typename Accessors>
809void
810rootless_splay_tree<Accessors>::splay (node_type node)
811{
812 node_type child = node;
813 node_type parent = get_parent (node: child);
814 if (!parent)
815 return;
816
817 do
818 {
819 // At this point, NODE conceptually replaces CHILD as a child of
820 // PARENT, but we haven't yet updated PARENT accordingly.
821 unsigned int index = child_index (parent, child);
822 if (node_type grandparent = get_parent (node: parent))
823 {
824 node_type greatgrandparent = get_parent (node: grandparent);
825 unsigned int parent_index = child_index (parent: grandparent, child: parent);
826 if (index == parent_index)
827 {
828 promote_child (grandparent, parent_index, parent);
829 promote_child (parent, index, node);
830 }
831 else
832 {
833 promote_child (parent, index, node);
834 promote_child (grandparent, parent_index, node);
835 }
836 child = grandparent;
837 parent = greatgrandparent;
838 }
839 else
840 {
841 promote_child (parent, index, node);
842 break;
843 }
844 }
845 while (parent);
846 set_parent (node, node_type ());
847}
848
849// See the comment above the declaration.
850template<typename Accessors>
851inline void
852rootless_splay_tree<Accessors>::splay_known_min_node (node_type node)
853{
854 splay_known_limit<0> (node);
855}
856
857// See the comment above the declaration.
858template<typename Accessors>
859inline void
860rootless_splay_tree<Accessors>::splay_known_max_node (node_type node)
861{
862 splay_known_limit<1> (node);
863}
864
865// See the comment above the declaration.
866template<typename Accessors>
867template<typename DefaultResult, typename Predicate>
868auto
869rootless_splay_tree<Accessors>::
870splay_and_search (node_type node, DefaultResult default_result,
871 Predicate predicate)
872 -> decltype (predicate (node, 0))
873{
874 using Result = decltype (predicate (node, 0));
875
876 node_type child = node;
877 node_type parent = get_parent (node: child);
878 if (!parent)
879 return default_result;
880
881 do
882 {
883 // At this point, NODE conceptually replaces CHILD as a child of
884 // PARENT, but we haven't yet updated PARENT accordingly.
885 unsigned int index = child_index (parent, child);
886 if (Result result = predicate (parent, index))
887 {
888 set_child (parent, index, node);
889 return result;
890 }
891 if (node_type grandparent = get_parent (node: parent))
892 {
893 node_type greatgrandparent = get_parent (node: grandparent);
894 unsigned int parent_index = child_index (parent: grandparent, child: parent);
895 if (Result result = predicate (grandparent, parent_index))
896 {
897 set_child (parent, index, node);
898 return result;
899 }
900 if (index == parent_index)
901 {
902 promote_child (grandparent, parent_index, parent);
903 promote_child (parent, index, node);
904 }
905 else
906 {
907 promote_child (parent, index, node);
908 promote_child (grandparent, parent_index, node);
909 }
910 child = grandparent;
911 parent = greatgrandparent;
912 }
913 else
914 {
915 promote_child (parent, index, node);
916 break;
917 }
918 }
919 while (parent);
920 set_parent (node, node_type ());
921 return default_result;
922}
923
924// Splay NODE1 looking to see if one of its ancestors is NODE2. If it is,
925// return -1 if NODE1 comes before NODE2 or 1 if NODE1 comes after NODE2.
926// Return 0 if NODE2 is not an ancestor of NODE1.
927template<typename Accessors>
928int
929rootless_splay_tree<Accessors>::compare_nodes_one_way (node_type node1,
930 node_type node2)
931{
932 auto compare = [&](node_type parent, unsigned int index) -> int
933 {
934 if (parent == node2)
935 return index ? 1 : -1;
936 return 0;
937 };
938 return splay_and_search (node1, 0, compare);
939}
940
941// See the comment above the declaration.
942template<typename Accessors>
943int
944rootless_splay_tree<Accessors>::compare_nodes (node_type node1,
945 node_type node2)
946{
947 if (node1 == node2)
948 return 0;
949
950 // Splay NODE1 looking for NODE2.
951 int cmp = compare_nodes_one_way (node1, node2);
952 if (cmp)
953 return cmp;
954
955 // That failed, but NODE1 is now the root of the tree. Splay NODE2
956 // to see on which side of NODE1 it falls.
957 cmp = compare_nodes_one_way (node1: node2, node2: node1);
958 gcc_checking_assert (cmp);
959 return -cmp;
960}
961

source code of gcc/splay-tree-utils.tcc