Branch data Line data Source code
1 : : /* ET-trees data structure implementation.
2 : : Contributed by Pavel Nejedly
3 : : Copyright (C) 2002-2024 Free Software Foundation, Inc.
4 : :
5 : : This file is part of the libiberty library.
6 : : Libiberty is free software; you can redistribute it and/or
7 : : modify it under the terms of the GNU Library General Public
8 : : License as published by the Free Software Foundation; either
9 : : version 3 of the License, or (at your option) any later version.
10 : :
11 : : Libiberty is distributed in the hope that it will be useful,
12 : : but WITHOUT ANY WARRANTY; without even the implied warranty of
13 : : MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
14 : : Library General Public License for more details.
15 : :
16 : : You should have received a copy of the GNU Library General Public
17 : : License along with libiberty; see the file COPYING3. If not see
18 : : <http://www.gnu.org/licenses/>.
19 : :
20 : : The ET-forest structure is described in:
21 : : D. D. Sleator and R. E. Tarjan. A data structure for dynamic trees.
22 : : J. G'omput. System Sci., 26(3):362 381, 1983.
23 : : */
24 : :
25 : : #include "config.h"
26 : : #include "system.h"
27 : : #include "coretypes.h"
28 : : #include "alloc-pool.h"
29 : : #include "et-forest.h"
30 : : #include "selftest.h"
31 : :
32 : : /* We do not enable this with CHECKING_P, since it is awfully slow. */
33 : : #undef DEBUG_ET
34 : :
35 : : #ifdef DEBUG_ET
36 : : #include "backend.h"
37 : : #include "hard-reg-set.h"
38 : : #endif
39 : :
40 : : /* The occurrence of a node in the et tree. */
41 : : struct et_occ
42 : : {
43 : : struct et_node *of; /* The node. */
44 : :
45 : : struct et_occ *parent; /* Parent in the splay-tree. */
46 : : struct et_occ *prev; /* Left son in the splay-tree. */
47 : : struct et_occ *next; /* Right son in the splay-tree. */
48 : :
49 : : int depth; /* The depth of the node is the sum of depth
50 : : fields on the path to the root. */
51 : : int min; /* The minimum value of the depth in the subtree
52 : : is obtained by adding sum of depth fields
53 : : on the path to the root. */
54 : : struct et_occ *min_occ; /* The occurrence in the subtree with the minimal
55 : : depth. */
56 : : };
57 : :
58 : : static object_allocator<et_node> et_nodes ("et_nodes pool");
59 : : static object_allocator<et_occ> et_occurrences ("et_occ pool");
60 : :
61 : : /* Changes depth of OCC to D. */
62 : :
63 : : static inline void
64 : 6246184815 : set_depth (struct et_occ *occ, int d)
65 : : {
66 : 6246184815 : if (!occ)
67 : : return;
68 : :
69 : 6246184815 : occ->min += d - occ->depth;
70 : 6246184815 : occ->depth = d;
71 : : }
72 : :
73 : : /* Adds D to the depth of OCC. */
74 : :
75 : : static inline void
76 : 9724185102 : set_depth_add (struct et_occ *occ, int d)
77 : : {
78 : 9724185102 : if (!occ)
79 : : return;
80 : :
81 : 6672516934 : occ->min += d;
82 : 2769442350 : occ->depth += d;
83 : : }
84 : :
85 : : /* Sets prev field of OCC to P. */
86 : :
87 : : static inline void
88 : 10116041980 : set_prev (struct et_occ *occ, struct et_occ *t)
89 : : {
90 : : #ifdef DEBUG_ET
91 : : gcc_assert (occ != t);
92 : : #endif
93 : :
94 : 10116041980 : occ->prev = t;
95 : 10116041980 : if (t)
96 : 2661213590 : t->parent = occ;
97 : : }
98 : :
99 : : /* Sets next field of OCC to P. */
100 : :
101 : : static inline void
102 : 8258283375 : set_next (struct et_occ *occ, struct et_occ *t)
103 : : {
104 : : #ifdef DEBUG_ET
105 : : gcc_assert (occ != t);
106 : : #endif
107 : :
108 : 8258283375 : occ->next = t;
109 : 8258283375 : if (t)
110 : 2372371461 : t->parent = occ;
111 : : }
112 : :
113 : : /* Recompute minimum for occurrence OCC. */
114 : :
115 : : static inline void
116 : 8026249375 : et_recomp_min (struct et_occ *occ)
117 : : {
118 : 8026249375 : struct et_occ *mson = occ->prev;
119 : :
120 : 8026249375 : if (!mson
121 : 5870043080 : || (occ->next
122 : 4373857517 : && mson->min > occ->next->min))
123 : 3308264704 : mson = occ->next;
124 : :
125 : 8026249375 : if (mson && mson->min < 0)
126 : : {
127 : 6498358164 : occ->min = mson->min + occ->depth;
128 : 6498358164 : occ->min_occ = mson->min_occ;
129 : : }
130 : : else
131 : : {
132 : 1527891211 : occ->min = occ->depth;
133 : 1527891211 : occ->min_occ = occ;
134 : : }
135 : 8026249375 : }
136 : :
137 : : #ifdef DEBUG_ET
138 : : /* Checks whether neighborhood of OCC seems sane. */
139 : :
140 : : static void
141 : : et_check_occ_sanity (struct et_occ *occ)
142 : : {
143 : : if (!occ)
144 : : return;
145 : :
146 : : gcc_assert (occ->parent != occ);
147 : : gcc_assert (occ->prev != occ);
148 : : gcc_assert (occ->next != occ);
149 : : gcc_assert (!occ->next || occ->next != occ->prev);
150 : :
151 : : if (occ->next)
152 : : {
153 : : gcc_assert (occ->next != occ->parent);
154 : : gcc_assert (occ->next->parent == occ);
155 : : }
156 : :
157 : : if (occ->prev)
158 : : {
159 : : gcc_assert (occ->prev != occ->parent);
160 : : gcc_assert (occ->prev->parent == occ);
161 : : }
162 : :
163 : : gcc_assert (!occ->parent
164 : : || occ->parent->prev == occ
165 : : || occ->parent->next == occ);
166 : : }
167 : :
168 : : /* Checks whether tree rooted at OCC is sane. */
169 : :
170 : : static void
171 : : et_check_sanity (struct et_occ *occ)
172 : : {
173 : : et_check_occ_sanity (occ);
174 : : if (occ->prev)
175 : : et_check_sanity (occ->prev);
176 : : if (occ->next)
177 : : et_check_sanity (occ->next);
178 : : }
179 : :
180 : : /* Checks whether tree containing OCC is sane. */
181 : :
182 : : static void
183 : : et_check_tree_sanity (struct et_occ *occ)
184 : : {
185 : : while (occ->parent)
186 : : occ = occ->parent;
187 : :
188 : : et_check_sanity (occ);
189 : : }
190 : :
191 : : /* For recording the paths. */
192 : :
193 : : /* An ad-hoc constant; if the function has more blocks, this won't work,
194 : : but since it is used for debugging only, it does not matter. */
195 : : #define MAX_NODES 100000
196 : :
197 : : static int len;
198 : : static void *datas[MAX_NODES];
199 : : static int depths[MAX_NODES];
200 : :
201 : : /* Records the path represented by OCC, with depth incremented by DEPTH. */
202 : :
203 : : static int
204 : : record_path_before_1 (struct et_occ *occ, int depth)
205 : : {
206 : : int mn, m;
207 : :
208 : : depth += occ->depth;
209 : : mn = depth;
210 : :
211 : : if (occ->prev)
212 : : {
213 : : m = record_path_before_1 (occ->prev, depth);
214 : : if (m < mn)
215 : : mn = m;
216 : : }
217 : :
218 : : fprintf (stderr, "%d (%d); ", ((basic_block) occ->of->data)->index, depth);
219 : :
220 : : gcc_assert (len < MAX_NODES);
221 : :
222 : : depths[len] = depth;
223 : : datas[len] = occ->of;
224 : : len++;
225 : :
226 : : if (occ->next)
227 : : {
228 : : m = record_path_before_1 (occ->next, depth);
229 : : if (m < mn)
230 : : mn = m;
231 : : }
232 : :
233 : : gcc_assert (mn == occ->min + depth - occ->depth);
234 : :
235 : : return mn;
236 : : }
237 : :
238 : : /* Records the path represented by a tree containing OCC. */
239 : :
240 : : static void
241 : : record_path_before (struct et_occ *occ)
242 : : {
243 : : while (occ->parent)
244 : : occ = occ->parent;
245 : :
246 : : len = 0;
247 : : record_path_before_1 (occ, 0);
248 : : fprintf (stderr, "\n");
249 : : }
250 : :
251 : : /* Checks whether the path represented by OCC, with depth incremented by DEPTH,
252 : : was not changed since the last recording. */
253 : :
254 : : static int
255 : : check_path_after_1 (struct et_occ *occ, int depth)
256 : : {
257 : : int mn, m;
258 : :
259 : : depth += occ->depth;
260 : : mn = depth;
261 : :
262 : : if (occ->next)
263 : : {
264 : : m = check_path_after_1 (occ->next, depth);
265 : : if (m < mn)
266 : : mn = m;
267 : : }
268 : :
269 : : len--;
270 : : gcc_assert (depths[len] == depth && datas[len] == occ->of);
271 : :
272 : : if (occ->prev)
273 : : {
274 : : m = check_path_after_1 (occ->prev, depth);
275 : : if (m < mn)
276 : : mn = m;
277 : : }
278 : :
279 : : gcc_assert (mn == occ->min + depth - occ->depth);
280 : :
281 : : return mn;
282 : : }
283 : :
284 : : /* Checks whether the path represented by a tree containing OCC was
285 : : not changed since the last recording. */
286 : :
287 : : static void
288 : : check_path_after (struct et_occ *occ)
289 : : {
290 : : while (occ->parent)
291 : : occ = occ->parent;
292 : :
293 : : check_path_after_1 (occ, 0);
294 : : gcc_assert (!len);
295 : : }
296 : :
297 : : #endif
298 : :
299 : : /* Splay the occurrence OCC to the root of the tree. */
300 : :
301 : : static void
302 : 5071240792 : et_splay (struct et_occ *occ)
303 : : {
304 : 5071240792 : struct et_occ *f, *gf, *ggf;
305 : 5071240792 : int occ_depth, f_depth, gf_depth;
306 : :
307 : : #ifdef DEBUG_ET
308 : : record_path_before (occ);
309 : : et_check_tree_sanity (occ);
310 : : #endif
311 : :
312 : 7839425320 : while (occ->parent)
313 : : {
314 : 3478000287 : occ_depth = occ->depth;
315 : :
316 : 3478000287 : f = occ->parent;
317 : 3478000287 : f_depth = f->depth;
318 : :
319 : 3478000287 : gf = f->parent;
320 : :
321 : 3478000287 : if (!gf)
322 : : {
323 : 709815759 : set_depth_add (occ, f_depth);
324 : 709815759 : occ->min_occ = f->min_occ;
325 : 709815759 : occ->min = f->min;
326 : :
327 : 709815759 : if (f->prev == occ)
328 : : {
329 : : /* zig */
330 : 300636439 : set_prev (f, occ->next);
331 : 300636439 : set_next (occ, f);
332 : 300636439 : set_depth_add (f->prev, occ_depth);
333 : : }
334 : : else
335 : : {
336 : : /* zag */
337 : 409179320 : set_next (f, occ->prev);
338 : 409179320 : set_prev (occ, f);
339 : 409179320 : set_depth_add (f->next, occ_depth);
340 : : }
341 : 709815759 : set_depth (f, -occ_depth);
342 : 709815759 : occ->parent = NULL;
343 : :
344 : 709815759 : et_recomp_min (f);
345 : : #ifdef DEBUG_ET
346 : : et_check_tree_sanity (occ);
347 : : check_path_after (occ);
348 : : #endif
349 : 709815759 : return;
350 : : }
351 : :
352 : 2768184528 : gf_depth = gf->depth;
353 : :
354 : 2768184528 : set_depth_add (occ, f_depth + gf_depth);
355 : 2768184528 : occ->min_occ = gf->min_occ;
356 : 2768184528 : occ->min = gf->min;
357 : :
358 : 2768184528 : ggf = gf->parent;
359 : :
360 : 2768184528 : if (gf->prev == f)
361 : : {
362 : 1782441298 : if (f->prev == occ)
363 : : {
364 : : /* zig zig */
365 : 707010047 : set_prev (gf, f->next);
366 : 707010047 : set_prev (f, occ->next);
367 : 707010047 : set_next (occ, f);
368 : 707010047 : set_next (f, gf);
369 : :
370 : 707010047 : set_depth (f, -occ_depth);
371 : 707010047 : set_depth_add (f->prev, occ_depth);
372 : 707010047 : set_depth (gf, -f_depth);
373 : 707010047 : set_depth_add (gf->prev, f_depth);
374 : : }
375 : : else
376 : : {
377 : : /* zag zig */
378 : 1075431251 : set_prev (gf, occ->next);
379 : 1075431251 : set_next (f, occ->prev);
380 : 1075431251 : set_prev (occ, f);
381 : 1075431251 : set_next (occ, gf);
382 : :
383 : 1075431251 : set_depth (f, -occ_depth);
384 : 1075431251 : set_depth_add (f->next, occ_depth);
385 : 1075431251 : set_depth (gf, -occ_depth - f_depth);
386 : 1075431251 : set_depth_add (gf->prev, occ_depth + f_depth);
387 : : }
388 : : }
389 : : else
390 : : {
391 : 985743230 : if (f->prev == occ)
392 : : {
393 : : /* zig zag */
394 : 298766280 : set_next (gf, occ->prev);
395 : 298766280 : set_prev (f, occ->next);
396 : 298766280 : set_prev (occ, gf);
397 : 298766280 : set_next (occ, f);
398 : :
399 : 298766280 : set_depth (f, -occ_depth);
400 : 298766280 : set_depth_add (f->prev, occ_depth);
401 : 298766280 : set_depth (gf, -occ_depth - f_depth);
402 : 298766280 : set_depth_add (gf->next, occ_depth + f_depth);
403 : : }
404 : : else
405 : : {
406 : : /* zag zag */
407 : 686976950 : set_next (gf, f->prev);
408 : 686976950 : set_next (f, occ->prev);
409 : 686976950 : set_prev (occ, f);
410 : 686976950 : set_prev (f, gf);
411 : :
412 : 686976950 : set_depth (f, -occ_depth);
413 : 686976950 : set_depth_add (f->next, occ_depth);
414 : 686976950 : set_depth (gf, -f_depth);
415 : 686976950 : set_depth_add (gf->next, f_depth);
416 : : }
417 : : }
418 : :
419 : 2768184528 : occ->parent = ggf;
420 : 2768184528 : if (ggf)
421 : : {
422 : 1520861479 : if (ggf->prev == gf)
423 : 820736391 : ggf->prev = occ;
424 : : else
425 : 700125088 : ggf->next = occ;
426 : : }
427 : :
428 : 2768184528 : et_recomp_min (gf);
429 : 2768184528 : et_recomp_min (f);
430 : : #ifdef DEBUG_ET
431 : : et_check_tree_sanity (occ);
432 : : #endif
433 : : }
434 : :
435 : : #ifdef DEBUG_ET
436 : : et_check_sanity (occ);
437 : : check_path_after (occ);
438 : : #endif
439 : : }
440 : :
441 : : /* Create a new et tree occurrence of NODE. */
442 : :
443 : : static struct et_occ *
444 : 3839788909 : et_new_occ (struct et_node *node)
445 : : {
446 : 3839788909 : et_occ *nw = et_occurrences.allocate ();
447 : :
448 : 3839788909 : nw->of = node;
449 : 3839788909 : nw->parent = NULL;
450 : 3839788909 : nw->prev = NULL;
451 : 3839788909 : nw->next = NULL;
452 : :
453 : 3839788909 : nw->depth = 0;
454 : 3839788909 : nw->min_occ = nw;
455 : 3839788909 : nw->min = 0;
456 : :
457 : 3839788909 : return nw;
458 : : }
459 : :
460 : : /* Create a new et tree containing DATA. */
461 : :
462 : : struct et_node *
463 : 2128636358 : et_new_tree (void *data)
464 : : {
465 : 2128636358 : et_node *nw = et_nodes.allocate ();
466 : :
467 : 2128636358 : nw->data = data;
468 : 2128636358 : nw->father = NULL;
469 : 2128636358 : nw->left = NULL;
470 : 2128636358 : nw->right = NULL;
471 : 2128636358 : nw->son = NULL;
472 : :
473 : 2128636358 : nw->rightmost_occ = et_new_occ (nw);
474 : 2128636358 : nw->parent_occ = NULL;
475 : :
476 : 2128636358 : return nw;
477 : : }
478 : :
479 : : /* Releases et tree T. */
480 : :
481 : : void
482 : 41198892 : et_free_tree (struct et_node *t)
483 : : {
484 : 42004364 : while (t->son)
485 : 805472 : et_split (t->son);
486 : :
487 : 41198892 : if (t->father)
488 : 40614167 : et_split (t);
489 : :
490 : 41198892 : et_occurrences.remove (t->rightmost_occ);
491 : 41198892 : et_nodes.remove (t);
492 : 41198892 : }
493 : :
494 : : /* Releases et tree T without maintaining other nodes. */
495 : :
496 : : void
497 : 2087088789 : et_free_tree_force (struct et_node *t)
498 : : {
499 : 2087088789 : et_occurrences.remove (t->rightmost_occ);
500 : 2087088789 : if (t->parent_occ)
501 : 1642001231 : et_occurrences.remove (t->parent_occ);
502 : 2087088789 : et_nodes.remove (t);
503 : 2087088789 : }
504 : :
505 : : /* Release the alloc pools, if they are empty. */
506 : :
507 : : void
508 : 221423639 : et_free_pools (void)
509 : : {
510 : 221423639 : et_occurrences.release_if_empty ();
511 : 221423639 : et_nodes.release_if_empty ();
512 : 221423639 : }
513 : :
514 : : /* Sets father of et tree T to FATHER. */
515 : :
516 : : void
517 : 1711152551 : et_set_father (struct et_node *t, struct et_node *father)
518 : : {
519 : 1711152551 : struct et_node *left, *right;
520 : 1711152551 : struct et_occ *rmost, *left_part, *new_f_occ, *p;
521 : :
522 : : /* Update the path represented in the splay tree. */
523 : 1711152551 : new_f_occ = et_new_occ (father);
524 : :
525 : 1711152551 : rmost = father->rightmost_occ;
526 : 1711152551 : et_splay (rmost);
527 : :
528 : 1711152551 : left_part = rmost->prev;
529 : :
530 : 1711152551 : p = t->rightmost_occ;
531 : 1711152551 : et_splay (p);
532 : :
533 : 1711152551 : set_prev (new_f_occ, left_part);
534 : 1711152551 : set_next (new_f_occ, p);
535 : :
536 : 1711152551 : p->depth++;
537 : 1711152551 : p->min++;
538 : 1711152551 : et_recomp_min (new_f_occ);
539 : :
540 : 1711152551 : set_prev (rmost, new_f_occ);
541 : :
542 : 1711152551 : if (new_f_occ->min + rmost->depth < rmost->min)
543 : : {
544 : 0 : rmost->min = new_f_occ->min + rmost->depth;
545 : 0 : rmost->min_occ = new_f_occ->min_occ;
546 : : }
547 : :
548 : 1711152551 : t->parent_occ = new_f_occ;
549 : :
550 : : /* Update the tree. */
551 : 1711152551 : t->father = father;
552 : 1711152551 : right = father->son;
553 : 1711152551 : if (right)
554 : 692796716 : left = right->left;
555 : : else
556 : : left = right = t;
557 : :
558 : 1711152551 : left->right = t;
559 : 1711152551 : right->left = t;
560 : 1711152551 : t->left = left;
561 : 1711152551 : t->right = right;
562 : :
563 : 1711152551 : father->son = t;
564 : :
565 : : #ifdef DEBUG_ET
566 : : et_check_tree_sanity (rmost);
567 : : record_path_before (rmost);
568 : : #endif
569 : 1711152551 : }
570 : :
571 : : /* Splits the edge from T to its father. */
572 : :
573 : : void
574 : 68912009 : et_split (struct et_node *t)
575 : : {
576 : 68912009 : struct et_node *father = t->father;
577 : 68912009 : struct et_occ *r, *l, *rmost, *p_occ;
578 : :
579 : : /* Update the path represented by the splay tree. */
580 : 68912009 : rmost = t->rightmost_occ;
581 : 68912009 : et_splay (rmost);
582 : :
583 : 138989400 : for (r = rmost->next; r->prev; r = r->prev)
584 : 70077391 : continue;
585 : 68912009 : et_splay (r);
586 : :
587 : 68912009 : r->prev->parent = NULL;
588 : 68912009 : p_occ = t->parent_occ;
589 : 68912009 : et_splay (p_occ);
590 : 68912009 : t->parent_occ = NULL;
591 : :
592 : 68912009 : l = p_occ->prev;
593 : 68912009 : p_occ->next->parent = NULL;
594 : :
595 : 68912009 : set_prev (r, l);
596 : :
597 : 68912009 : et_recomp_min (r);
598 : :
599 : 68912009 : et_splay (rmost);
600 : 68912009 : rmost->depth = 0;
601 : 68912009 : rmost->min = 0;
602 : :
603 : 68912009 : et_occurrences.remove (p_occ);
604 : :
605 : : /* Update the tree. */
606 : 68912009 : if (father->son == t)
607 : 40383346 : father->son = t->right;
608 : 68912009 : if (father->son == t)
609 : 26537055 : father->son = NULL;
610 : : else
611 : : {
612 : 42374954 : t->left->right = t->right;
613 : 42374954 : t->right->left = t->left;
614 : : }
615 : 68912009 : t->left = t->right = NULL;
616 : 68912009 : t->father = NULL;
617 : :
618 : : #ifdef DEBUG_ET
619 : : et_check_tree_sanity (rmost);
620 : : record_path_before (rmost);
621 : :
622 : : et_check_tree_sanity (r);
623 : : record_path_before (r);
624 : : #endif
625 : 70077391 : }
626 : :
627 : : /* Finds the nearest common ancestor of the nodes N1 and N2. */
628 : :
629 : : struct et_node *
630 : 93601545 : et_nca (struct et_node *n1, struct et_node *n2)
631 : : {
632 : 93601545 : struct et_occ *o1 = n1->rightmost_occ, *o2 = n2->rightmost_occ, *om;
633 : 93601545 : struct et_occ *l, *r, *ret;
634 : 93601545 : int mn;
635 : :
636 : 93601545 : if (n1 == n2)
637 : : return n1;
638 : :
639 : 77944376 : et_splay (o1);
640 : 77944376 : l = o1->prev;
641 : 77944376 : r = o1->next;
642 : 77944376 : if (l)
643 : 77944376 : l->parent = NULL;
644 : 77944376 : if (r)
645 : 77935987 : r->parent = NULL;
646 : 77944376 : et_splay (o2);
647 : :
648 : 77944376 : if (l == o2 || (l && l->parent != NULL))
649 : : {
650 : 70704545 : ret = o2->next;
651 : :
652 : 70704545 : set_prev (o1, o2);
653 : 70704545 : if (r)
654 : 70696156 : r->parent = o1;
655 : : }
656 : 7239831 : else if (r == o2 || (r && r->parent != NULL))
657 : : {
658 : 7239831 : ret = o2->prev;
659 : :
660 : 7239831 : set_next (o1, o2);
661 : 7239831 : if (l)
662 : 7239831 : l->parent = o1;
663 : : }
664 : : else
665 : : {
666 : : /* O1 and O2 are in different components of the forest. */
667 : 0 : if (l)
668 : 0 : l->parent = o1;
669 : 0 : if (r)
670 : 0 : r->parent = o1;
671 : 0 : return NULL;
672 : : }
673 : :
674 : 77944376 : if (o2->depth > 0)
675 : : {
676 : 70310777 : om = o1;
677 : 70310777 : mn = o1->depth;
678 : : }
679 : : else
680 : : {
681 : 7633599 : om = o2;
682 : 7633599 : mn = o2->depth + o1->depth;
683 : : }
684 : :
685 : : #ifdef DEBUG_ET
686 : : et_check_tree_sanity (o2);
687 : : #endif
688 : :
689 : 77944376 : if (ret && ret->min + o1->depth + o2->depth < mn)
690 : 5573133 : return ret->min_occ->of;
691 : : else
692 : 72371243 : return om->of;
693 : : }
694 : :
695 : : /* Checks whether the node UP is an ancestor of the node DOWN. */
696 : :
697 : : bool
698 : 619668247 : et_below (struct et_node *down, struct et_node *up)
699 : : {
700 : 619668247 : struct et_occ *u = up->rightmost_occ, *d = down->rightmost_occ;
701 : 619668247 : struct et_occ *l, *r;
702 : :
703 : 619668247 : if (up == down)
704 : : return true;
705 : :
706 : 601927297 : et_splay (u);
707 : 601927297 : l = u->prev;
708 : 601927297 : r = u->next;
709 : :
710 : 601927297 : if (!l)
711 : : return false;
712 : :
713 : 601641687 : l->parent = NULL;
714 : :
715 : 601641687 : if (r)
716 : 600881971 : r->parent = NULL;
717 : :
718 : 601641687 : et_splay (d);
719 : :
720 : 601641687 : if (l == d || l->parent != NULL)
721 : : {
722 : 307935509 : if (r)
723 : 307688038 : r->parent = u;
724 : 307935509 : set_prev (u, d);
725 : : #ifdef DEBUG_ET
726 : : et_check_tree_sanity (u);
727 : : #endif
728 : : }
729 : : else
730 : : {
731 : 293706178 : l->parent = u;
732 : :
733 : : /* In case O1 and O2 are in two different trees, we must just restore the
734 : : original state. */
735 : 293706178 : if (r && r->parent != NULL)
736 : 115284800 : set_next (u, d);
737 : : else
738 : 178421378 : set_next (u, r);
739 : :
740 : : #ifdef DEBUG_ET
741 : : et_check_tree_sanity (u);
742 : : #endif
743 : 293706178 : return false;
744 : : }
745 : :
746 : 307935509 : if (d->depth <= 0)
747 : : return false;
748 : :
749 : 270028247 : return !d->next || d->next->min + d->depth >= 0;
750 : : }
751 : :
752 : : /* Returns the root of the tree that contains NODE. */
753 : :
754 : : struct et_node *
755 : 6914959 : et_root (struct et_node *node)
756 : : {
757 : 6914959 : struct et_occ *occ = node->rightmost_occ, *r;
758 : :
759 : : /* The root of the tree corresponds to the rightmost occurrence in the
760 : : represented path. */
761 : 6914959 : et_splay (occ);
762 : 26071552 : for (r = occ; r->next; r = r->next)
763 : 12241634 : continue;
764 : 6914959 : et_splay (r);
765 : :
766 : 6914959 : return r->of;
767 : 12241634 : }
768 : :
769 : : #if CHECKING_P
770 : :
771 : : namespace selftest {
772 : :
773 : : /* Selftests for et-forest.cc. */
774 : :
775 : : /* Perform sanity checks for a tree consisting of a single node. */
776 : :
777 : : static void
778 : 4 : test_single_node ()
779 : : {
780 : 4 : void *test_data = (void *)0xcafebabe;
781 : :
782 : 4 : et_node *n = et_new_tree (test_data);
783 : 4 : ASSERT_EQ (n->data, test_data);
784 : 4 : ASSERT_EQ (n, et_root (n));
785 : 4 : et_free_tree (n);
786 : 4 : }
787 : :
788 : : /* Test of this tree:
789 : : a
790 : : / \
791 : : / \
792 : : b c
793 : : / \ |
794 : : d e f. */
795 : :
796 : : static void
797 : 4 : test_simple_tree ()
798 : : {
799 : 4 : et_node *a = et_new_tree (NULL);
800 : 4 : et_node *b = et_new_tree (NULL);
801 : 4 : et_node *c = et_new_tree (NULL);
802 : 4 : et_node *d = et_new_tree (NULL);
803 : 4 : et_node *e = et_new_tree (NULL);
804 : 4 : et_node *f = et_new_tree (NULL);
805 : :
806 : 4 : et_set_father (b, a);
807 : 4 : et_set_father (c, a);
808 : 4 : et_set_father (d, b);
809 : 4 : et_set_father (e, b);
810 : 4 : et_set_father (f, c);
811 : :
812 : 4 : ASSERT_TRUE (et_below (a, a));
813 : 4 : ASSERT_TRUE (et_below (b, a));
814 : 4 : ASSERT_TRUE (et_below (c, a));
815 : 4 : ASSERT_TRUE (et_below (d, a));
816 : 4 : ASSERT_TRUE (et_below (e, a));
817 : 4 : ASSERT_TRUE (et_below (f, a));
818 : :
819 : 4 : ASSERT_FALSE (et_below (a, b));
820 : 4 : ASSERT_TRUE (et_below (b, b));
821 : 4 : ASSERT_FALSE (et_below (c, b));
822 : 4 : ASSERT_TRUE (et_below (d, b));
823 : 4 : ASSERT_TRUE (et_below (e, b));
824 : 4 : ASSERT_FALSE (et_below (f, b));
825 : :
826 : 4 : ASSERT_FALSE (et_below (a, c));
827 : 4 : ASSERT_FALSE (et_below (b, c));
828 : 4 : ASSERT_TRUE (et_below (c, c));
829 : 4 : ASSERT_FALSE (et_below (d, c));
830 : 4 : ASSERT_FALSE (et_below (e, c));
831 : 4 : ASSERT_TRUE (et_below (f, c));
832 : :
833 : 4 : ASSERT_FALSE (et_below (a, d));
834 : 4 : ASSERT_FALSE (et_below (b, d));
835 : 4 : ASSERT_FALSE (et_below (c, d));
836 : 4 : ASSERT_TRUE (et_below (d, d));
837 : 4 : ASSERT_FALSE (et_below (e, d));
838 : 4 : ASSERT_FALSE (et_below (f, d));
839 : :
840 : 4 : ASSERT_FALSE (et_below (a, e));
841 : 4 : ASSERT_FALSE (et_below (b, e));
842 : 4 : ASSERT_FALSE (et_below (c, e));
843 : 4 : ASSERT_FALSE (et_below (d, e));
844 : 4 : ASSERT_TRUE (et_below (e, e));
845 : 4 : ASSERT_FALSE (et_below (f, e));
846 : :
847 : 4 : ASSERT_FALSE (et_below (a, f));
848 : 4 : ASSERT_FALSE (et_below (b, f));
849 : 4 : ASSERT_FALSE (et_below (c, f));
850 : 4 : ASSERT_FALSE (et_below (d, f));
851 : 4 : ASSERT_FALSE (et_below (e, f));
852 : 4 : ASSERT_TRUE (et_below (f, f));
853 : :
854 : 4 : et_free_tree_force (a);
855 : 4 : }
856 : :
857 : : /* Verify that two disconnected nodes are unrelated. */
858 : :
859 : : static void
860 : 4 : test_disconnected_nodes ()
861 : : {
862 : 4 : et_node *a = et_new_tree (NULL);
863 : 4 : et_node *b = et_new_tree (NULL);
864 : :
865 : 4 : ASSERT_FALSE (et_below (a, b));
866 : 4 : ASSERT_FALSE (et_below (b, a));
867 : :
868 : 4 : et_free_tree (a);
869 : 4 : et_free_tree (b);
870 : 4 : }
871 : :
872 : : /* Run all of the selftests within this file. */
873 : :
874 : : void
875 : 4 : et_forest_cc_tests ()
876 : : {
877 : 4 : test_single_node ();
878 : 4 : test_simple_tree ();
879 : 4 : test_disconnected_nodes ();
880 : 4 : }
881 : :
882 : : } // namespace selftest
883 : :
884 : : #endif /* CHECKING_P */
|
