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. |
22 | template<typename Accessors> |
23 | inline typename base_splay_tree<Accessors>::node_type |
24 | base_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. |
32 | template<typename Accessors> |
33 | inline void |
34 | base_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. |
47 | template<typename Accessors> |
48 | inline typename base_splay_tree<Accessors>::node_type |
49 | base_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. |
61 | template<typename Accessors> |
62 | inline void |
63 | base_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. |
74 | template<typename Accessors> |
75 | template<typename Printer> |
76 | void |
77 | 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 | 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 * = 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. |
159 | template<typename Accessors> |
160 | template<typename Printer> |
161 | void |
162 | base_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. |
184 | template<typename Accessors> |
185 | template<unsigned int N> |
186 | typename base_splay_tree<Accessors>::node_type |
187 | 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 | 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. |
267 | template<typename Accessors> |
268 | inline typename base_splay_tree<Accessors>::node_type |
269 | base_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. |
289 | template<typename Accessors> |
290 | inline void |
291 | base_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. |
300 | template<typename Accessors> |
301 | template<unsigned int N> |
302 | bool |
303 | rooted_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. |
327 | template<typename Accessors> |
328 | template<typename Comparator> |
329 | bool |
330 | rooted_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. |
353 | template<typename Accessors> |
354 | inline void |
355 | rooted_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. |
363 | template<typename Accessors> |
364 | inline void |
365 | rooted_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. |
372 | template<typename Accessors> |
373 | inline void |
374 | rooted_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. |
388 | template<typename Accessors> |
389 | inline void |
390 | rooted_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. |
402 | template<typename Accessors> |
403 | inline rooted_splay_tree<Accessors> |
404 | rooted_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. |
413 | template<typename Accessors> |
414 | inline rooted_splay_tree<Accessors> |
415 | rooted_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. |
424 | template<typename Accessors> |
425 | inline bool |
426 | rooted_splay_tree<Accessors>::splay_prev_node () |
427 | { |
428 | return splay_neighbor<0> (); |
429 | } |
430 | |
431 | // See the comment above the declaration. |
432 | template<typename Accessors> |
433 | inline bool |
434 | rooted_splay_tree<Accessors>::splay_next_node () |
435 | { |
436 | return splay_neighbor<1> (); |
437 | } |
438 | |
439 | // See the comment above the declaration. |
440 | template<typename Accessors> |
441 | inline void |
442 | rooted_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. |
452 | template<typename Accessors> |
453 | inline void |
454 | rooted_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. |
464 | template<typename Accessors> |
465 | inline typename rooted_splay_tree<Accessors>::node_type |
466 | rooted_splay_tree<Accessors>::min_node () |
467 | { |
468 | splay_min_node (); |
469 | return m_root; |
470 | } |
471 | |
472 | // See the comment above the declaration. |
473 | template<typename Accessors> |
474 | inline typename rooted_splay_tree<Accessors>::node_type |
475 | rooted_splay_tree<Accessors>::max_node () |
476 | { |
477 | splay_max_node (); |
478 | return m_root; |
479 | } |
480 | |
481 | // See the comment above the declaration. |
482 | template<typename Accessors> |
483 | template<typename Comparator> |
484 | auto |
485 | rooted_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. |
622 | template<typename Accessors> |
623 | template<typename LeftPredicate, typename RightPredicate> |
624 | int |
625 | rooted_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. |
734 | template<typename Accessors> |
735 | template<typename Printer> |
736 | inline void |
737 | rooted_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. |
743 | template<typename Accessors> |
744 | inline typename rootless_splay_tree<Accessors>::node_type |
745 | rootless_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. |
751 | template<typename Accessors> |
752 | inline unsigned int |
753 | rootless_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. |
760 | template<typename Accessors> |
761 | template<unsigned int N> |
762 | inline void |
763 | rootless_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. |
791 | template<typename Accessors> |
792 | typename rootless_splay_tree<Accessors>::node_type |
793 | rootless_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. |
808 | template<typename Accessors> |
809 | void |
810 | rootless_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. |
850 | template<typename Accessors> |
851 | inline void |
852 | rootless_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. |
858 | template<typename Accessors> |
859 | inline void |
860 | rootless_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. |
866 | template<typename Accessors> |
867 | template<typename DefaultResult, typename Predicate> |
868 | auto |
869 | rootless_splay_tree<Accessors>:: |
870 | splay_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. |
927 | template<typename Accessors> |
928 | int |
929 | rootless_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. |
942 | template<typename Accessors> |
943 | int |
944 | rootless_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 | |