]>
Commit | Line | Data |
---|---|---|
917bbcab | 1 | /* ET-trees data structure implementation. |
5dd29ee7 | 2 | Contributed by Pavel Nejedly |
d353bf18 | 3 | Copyright (C) 2002-2015 Free Software Foundation, Inc. |
5dd29ee7 | 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 | |
8c4c00c1 | 9 | version 3 of the License, or (at your option) any later version. |
5dd29ee7 | 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 | |
8c4c00c1 | 17 | License along with libiberty; see the file COPYING3. If not see |
18 | <http://www.gnu.org/licenses/>. | |
5dd29ee7 | 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" | |
805e22b2 | 27 | #include "coretypes.h" |
b694b261 | 28 | #include "alloc-pool.h" |
63c440eb | 29 | #include "et-forest.h" |
5dd29ee7 | 30 | |
0051c76a | 31 | /* We do not enable this with ENABLE_CHECKING, since it is awfully slow. */ |
32 | #undef DEBUG_ET | |
5dd29ee7 | 33 | |
0051c76a | 34 | #ifdef DEBUG_ET |
9ef16211 | 35 | #include "backend.h" |
94ea8568 | 36 | #include "hard-reg-set.h" |
0051c76a | 37 | #endif |
5dd29ee7 | 38 | |
4885b286 | 39 | /* The occurrence of a node in the et tree. */ |
0051c76a | 40 | struct et_occ |
5dd29ee7 | 41 | { |
0051c76a | 42 | struct et_node *of; /* The node. */ |
43 | ||
44 | struct et_occ *parent; /* Parent in the splay-tree. */ | |
45 | struct et_occ *prev; /* Left son in the splay-tree. */ | |
46 | struct et_occ *next; /* Right son in the splay-tree. */ | |
47 | ||
48 | int depth; /* The depth of the node is the sum of depth | |
49 | fields on the path to the root. */ | |
50 | int min; /* The minimum value of the depth in the subtree | |
51 | is obtained by adding sum of depth fields | |
52 | on the path to the root. */ | |
4885b286 | 53 | struct et_occ *min_occ; /* The occurrence in the subtree with the minimal |
0051c76a | 54 | depth. */ |
55 | }; | |
5dd29ee7 | 56 | |
e16712b1 | 57 | static object_allocator<et_node> et_nodes ("et_nodes pool", 300); |
58 | static object_allocator<et_occ> et_occurrences ("et_occ pool", 300); | |
5dd29ee7 | 59 | |
0051c76a | 60 | /* Changes depth of OCC to D. */ |
5dd29ee7 | 61 | |
0051c76a | 62 | static inline void |
63 | set_depth (struct et_occ *occ, int d) | |
64 | { | |
65 | if (!occ) | |
66 | return; | |
5dd29ee7 | 67 | |
0051c76a | 68 | occ->min += d - occ->depth; |
69 | occ->depth = d; | |
70 | } | |
5dd29ee7 | 71 | |
0051c76a | 72 | /* Adds D to the depth of OCC. */ |
5dd29ee7 | 73 | |
0051c76a | 74 | static inline void |
75 | set_depth_add (struct et_occ *occ, int d) | |
5dd29ee7 | 76 | { |
0051c76a | 77 | if (!occ) |
78 | return; | |
5dd29ee7 | 79 | |
0051c76a | 80 | occ->min += d; |
81 | occ->depth += d; | |
82 | } | |
5dd29ee7 | 83 | |
0051c76a | 84 | /* Sets prev field of OCC to P. */ |
5dd29ee7 | 85 | |
0051c76a | 86 | static inline void |
87 | set_prev (struct et_occ *occ, struct et_occ *t) | |
5dd29ee7 | 88 | { |
0051c76a | 89 | #ifdef DEBUG_ET |
611234b4 | 90 | gcc_assert (occ != t); |
0051c76a | 91 | #endif |
5dd29ee7 | 92 | |
0051c76a | 93 | occ->prev = t; |
94 | if (t) | |
95 | t->parent = occ; | |
5dd29ee7 | 96 | } |
97 | ||
0051c76a | 98 | /* Sets next field of OCC to P. */ |
99 | ||
100 | static inline void | |
101 | set_next (struct et_occ *occ, struct et_occ *t) | |
5dd29ee7 | 102 | { |
0051c76a | 103 | #ifdef DEBUG_ET |
611234b4 | 104 | gcc_assert (occ != t); |
0051c76a | 105 | #endif |
106 | ||
107 | occ->next = t; | |
108 | if (t) | |
109 | t->parent = occ; | |
5dd29ee7 | 110 | } |
111 | ||
4885b286 | 112 | /* Recompute minimum for occurrence OCC. */ |
5dd29ee7 | 113 | |
0051c76a | 114 | static inline void |
115 | et_recomp_min (struct et_occ *occ) | |
5dd29ee7 | 116 | { |
0051c76a | 117 | struct et_occ *mson = occ->prev; |
5dd29ee7 | 118 | |
0051c76a | 119 | if (!mson |
120 | || (occ->next | |
121 | && mson->min > occ->next->min)) | |
122 | mson = occ->next; | |
5dd29ee7 | 123 | |
0051c76a | 124 | if (mson && mson->min < 0) |
125 | { | |
126 | occ->min = mson->min + occ->depth; | |
127 | occ->min_occ = mson->min_occ; | |
128 | } | |
129 | else | |
130 | { | |
131 | occ->min = occ->depth; | |
132 | occ->min_occ = occ; | |
133 | } | |
134 | } | |
5dd29ee7 | 135 | |
0051c76a | 136 | #ifdef DEBUG_ET |
91275768 | 137 | /* Checks whether neighborhood of OCC seems sane. */ |
5dd29ee7 | 138 | |
0051c76a | 139 | static void |
140 | et_check_occ_sanity (struct et_occ *occ) | |
141 | { | |
142 | if (!occ) | |
143 | return; | |
5dd29ee7 | 144 | |
611234b4 | 145 | gcc_assert (occ->parent != occ); |
146 | gcc_assert (occ->prev != occ); | |
147 | gcc_assert (occ->next != occ); | |
148 | gcc_assert (!occ->next || occ->next != occ->prev); | |
5dd29ee7 | 149 | |
0051c76a | 150 | if (occ->next) |
5dd29ee7 | 151 | { |
611234b4 | 152 | gcc_assert (occ->next != occ->parent); |
153 | gcc_assert (occ->next->parent == occ); | |
35cb5232 | 154 | } |
0051c76a | 155 | |
156 | if (occ->prev) | |
5dd29ee7 | 157 | { |
611234b4 | 158 | gcc_assert (occ->prev != occ->parent); |
159 | gcc_assert (occ->prev->parent == occ); | |
5dd29ee7 | 160 | } |
161 | ||
611234b4 | 162 | gcc_assert (!occ->parent |
163 | || occ->parent->prev == occ | |
164 | || occ->parent->next == occ); | |
5dd29ee7 | 165 | } |
166 | ||
0051c76a | 167 | /* Checks whether tree rooted at OCC is sane. */ |
168 | ||
5dd29ee7 | 169 | static void |
0051c76a | 170 | et_check_sanity (struct et_occ *occ) |
5dd29ee7 | 171 | { |
0051c76a | 172 | et_check_occ_sanity (occ); |
173 | if (occ->prev) | |
174 | et_check_sanity (occ->prev); | |
175 | if (occ->next) | |
176 | et_check_sanity (occ->next); | |
177 | } | |
5dd29ee7 | 178 | |
0051c76a | 179 | /* Checks whether tree containing OCC is sane. */ |
5dd29ee7 | 180 | |
0051c76a | 181 | static void |
182 | et_check_tree_sanity (struct et_occ *occ) | |
183 | { | |
184 | while (occ->parent) | |
185 | occ = occ->parent; | |
5dd29ee7 | 186 | |
0051c76a | 187 | et_check_sanity (occ); |
188 | } | |
5dd29ee7 | 189 | |
0051c76a | 190 | /* For recording the paths. */ |
5dd29ee7 | 191 | |
4ee9c684 | 192 | /* An ad-hoc constant; if the function has more blocks, this won't work, |
193 | but since it is used for debugging only, it does not matter. */ | |
194 | #define MAX_NODES 100000 | |
195 | ||
0051c76a | 196 | static int len; |
4ee9c684 | 197 | static void *datas[MAX_NODES]; |
198 | static int depths[MAX_NODES]; | |
5dd29ee7 | 199 | |
0051c76a | 200 | /* Records the path represented by OCC, with depth incremented by DEPTH. */ |
5dd29ee7 | 201 | |
0051c76a | 202 | static int |
203 | record_path_before_1 (struct et_occ *occ, int depth) | |
204 | { | |
205 | int mn, m; | |
5dd29ee7 | 206 | |
0051c76a | 207 | depth += occ->depth; |
208 | mn = depth; | |
209 | ||
210 | if (occ->prev) | |
211 | { | |
48e1416a | 212 | m = record_path_before_1 (occ->prev, depth); |
0051c76a | 213 | if (m < mn) |
214 | mn = m; | |
5dd29ee7 | 215 | } |
216 | ||
0051c76a | 217 | fprintf (stderr, "%d (%d); ", ((basic_block) occ->of->data)->index, depth); |
4ee9c684 | 218 | |
611234b4 | 219 | gcc_assert (len < MAX_NODES); |
4ee9c684 | 220 | |
0051c76a | 221 | depths[len] = depth; |
222 | datas[len] = occ->of; | |
223 | len++; | |
224 | ||
225 | if (occ->next) | |
5dd29ee7 | 226 | { |
0051c76a | 227 | m = record_path_before_1 (occ->next, depth); |
228 | if (m < mn) | |
229 | mn = m; | |
230 | } | |
5dd29ee7 | 231 | |
611234b4 | 232 | gcc_assert (mn == occ->min + depth - occ->depth); |
5dd29ee7 | 233 | |
0051c76a | 234 | return mn; |
235 | } | |
5dd29ee7 | 236 | |
0051c76a | 237 | /* Records the path represented by a tree containing OCC. */ |
5dd29ee7 | 238 | |
0051c76a | 239 | static void |
240 | record_path_before (struct et_occ *occ) | |
241 | { | |
242 | while (occ->parent) | |
243 | occ = occ->parent; | |
5dd29ee7 | 244 | |
0051c76a | 245 | len = 0; |
246 | record_path_before_1 (occ, 0); | |
247 | fprintf (stderr, "\n"); | |
5dd29ee7 | 248 | } |
249 | ||
0051c76a | 250 | /* Checks whether the path represented by OCC, with depth incremented by DEPTH, |
251 | was not changed since the last recording. */ | |
252 | ||
253 | static int | |
254 | check_path_after_1 (struct et_occ *occ, int depth) | |
5dd29ee7 | 255 | { |
0051c76a | 256 | int mn, m; |
257 | ||
258 | depth += occ->depth; | |
259 | mn = depth; | |
5dd29ee7 | 260 | |
0051c76a | 261 | if (occ->next) |
5dd29ee7 | 262 | { |
48e1416a | 263 | m = check_path_after_1 (occ->next, depth); |
0051c76a | 264 | if (m < mn) |
265 | mn = m; | |
266 | } | |
5dd29ee7 | 267 | |
0051c76a | 268 | len--; |
611234b4 | 269 | gcc_assert (depths[len] == depth && datas[len] == occ->of); |
0051c76a | 270 | |
271 | if (occ->prev) | |
272 | { | |
273 | m = check_path_after_1 (occ->prev, depth); | |
274 | if (m < mn) | |
275 | mn = m; | |
5dd29ee7 | 276 | } |
277 | ||
611234b4 | 278 | gcc_assert (mn == occ->min + depth - occ->depth); |
0051c76a | 279 | |
280 | return mn; | |
5dd29ee7 | 281 | } |
282 | ||
0051c76a | 283 | /* Checks whether the path represented by a tree containing OCC was |
284 | not changed since the last recording. */ | |
285 | ||
286 | static void | |
287 | check_path_after (struct et_occ *occ) | |
288 | { | |
289 | while (occ->parent) | |
290 | occ = occ->parent; | |
291 | ||
292 | check_path_after_1 (occ, 0); | |
611234b4 | 293 | gcc_assert (!len); |
0051c76a | 294 | } |
5dd29ee7 | 295 | |
0051c76a | 296 | #endif |
5dd29ee7 | 297 | |
4885b286 | 298 | /* Splay the occurrence OCC to the root of the tree. */ |
5dd29ee7 | 299 | |
89df180d | 300 | static void |
0051c76a | 301 | et_splay (struct et_occ *occ) |
5dd29ee7 | 302 | { |
0051c76a | 303 | struct et_occ *f, *gf, *ggf; |
304 | int occ_depth, f_depth, gf_depth; | |
305 | ||
306 | #ifdef DEBUG_ET | |
307 | record_path_before (occ); | |
308 | et_check_tree_sanity (occ); | |
309 | #endif | |
48e1416a | 310 | |
0051c76a | 311 | while (occ->parent) |
312 | { | |
313 | occ_depth = occ->depth; | |
5dd29ee7 | 314 | |
0051c76a | 315 | f = occ->parent; |
316 | f_depth = f->depth; | |
5dd29ee7 | 317 | |
0051c76a | 318 | gf = f->parent; |
5dd29ee7 | 319 | |
0051c76a | 320 | if (!gf) |
321 | { | |
322 | set_depth_add (occ, f_depth); | |
323 | occ->min_occ = f->min_occ; | |
324 | occ->min = f->min; | |
5dd29ee7 | 325 | |
0051c76a | 326 | if (f->prev == occ) |
327 | { | |
328 | /* zig */ | |
329 | set_prev (f, occ->next); | |
330 | set_next (occ, f); | |
331 | set_depth_add (f->prev, occ_depth); | |
332 | } | |
333 | else | |
334 | { | |
335 | /* zag */ | |
336 | set_next (f, occ->prev); | |
337 | set_prev (occ, f); | |
338 | set_depth_add (f->next, occ_depth); | |
339 | } | |
340 | set_depth (f, -occ_depth); | |
341 | occ->parent = NULL; | |
342 | ||
343 | et_recomp_min (f); | |
344 | #ifdef DEBUG_ET | |
345 | et_check_tree_sanity (occ); | |
346 | check_path_after (occ); | |
347 | #endif | |
348 | return; | |
349 | } | |
350 | ||
351 | gf_depth = gf->depth; | |
352 | ||
353 | set_depth_add (occ, f_depth + gf_depth); | |
354 | occ->min_occ = gf->min_occ; | |
355 | occ->min = gf->min; | |
356 | ||
357 | ggf = gf->parent; | |
358 | ||
359 | if (gf->prev == f) | |
360 | { | |
361 | if (f->prev == occ) | |
362 | { | |
363 | /* zig zig */ | |
364 | set_prev (gf, f->next); | |
365 | set_prev (f, occ->next); | |
366 | set_next (occ, f); | |
367 | set_next (f, gf); | |
368 | ||
369 | set_depth (f, -occ_depth); | |
370 | set_depth_add (f->prev, occ_depth); | |
371 | set_depth (gf, -f_depth); | |
372 | set_depth_add (gf->prev, f_depth); | |
373 | } | |
374 | else | |
375 | { | |
376 | /* zag zig */ | |
377 | set_prev (gf, occ->next); | |
378 | set_next (f, occ->prev); | |
379 | set_prev (occ, f); | |
380 | set_next (occ, gf); | |
381 | ||
382 | set_depth (f, -occ_depth); | |
383 | set_depth_add (f->next, occ_depth); | |
384 | set_depth (gf, -occ_depth - f_depth); | |
385 | set_depth_add (gf->prev, occ_depth + f_depth); | |
386 | } | |
387 | } | |
388 | else | |
389 | { | |
390 | if (f->prev == occ) | |
391 | { | |
392 | /* zig zag */ | |
393 | set_next (gf, occ->prev); | |
394 | set_prev (f, occ->next); | |
395 | set_prev (occ, gf); | |
396 | set_next (occ, f); | |
397 | ||
398 | set_depth (f, -occ_depth); | |
399 | set_depth_add (f->prev, occ_depth); | |
400 | set_depth (gf, -occ_depth - f_depth); | |
401 | set_depth_add (gf->next, occ_depth + f_depth); | |
402 | } | |
403 | else | |
404 | { | |
405 | /* zag zag */ | |
406 | set_next (gf, f->prev); | |
407 | set_next (f, occ->prev); | |
408 | set_prev (occ, f); | |
409 | set_prev (f, gf); | |
410 | ||
411 | set_depth (f, -occ_depth); | |
412 | set_depth_add (f->next, occ_depth); | |
413 | set_depth (gf, -f_depth); | |
414 | set_depth_add (gf->next, f_depth); | |
415 | } | |
416 | } | |
417 | ||
418 | occ->parent = ggf; | |
419 | if (ggf) | |
420 | { | |
421 | if (ggf->prev == gf) | |
422 | ggf->prev = occ; | |
423 | else | |
424 | ggf->next = occ; | |
425 | } | |
426 | ||
427 | et_recomp_min (gf); | |
428 | et_recomp_min (f); | |
429 | #ifdef DEBUG_ET | |
430 | et_check_tree_sanity (occ); | |
431 | #endif | |
432 | } | |
433 | ||
434 | #ifdef DEBUG_ET | |
435 | et_check_sanity (occ); | |
436 | check_path_after (occ); | |
437 | #endif | |
438 | } | |
439 | ||
4885b286 | 440 | /* Create a new et tree occurrence of NODE. */ |
0051c76a | 441 | |
442 | static struct et_occ * | |
443 | et_new_occ (struct et_node *node) | |
5dd29ee7 | 444 | { |
e16712b1 | 445 | et_occ *nw = et_occurrences.allocate (); |
0051c76a | 446 | |
447 | nw->of = node; | |
448 | nw->parent = NULL; | |
449 | nw->prev = NULL; | |
450 | nw->next = NULL; | |
451 | ||
452 | nw->depth = 0; | |
453 | nw->min_occ = nw; | |
454 | nw->min = 0; | |
455 | ||
456 | return nw; | |
5dd29ee7 | 457 | } |
458 | ||
0051c76a | 459 | /* Create a new et tree containing DATA. */ |
460 | ||
461 | struct et_node * | |
462 | et_new_tree (void *data) | |
5dd29ee7 | 463 | { |
e16712b1 | 464 | et_node *nw = et_nodes.allocate (); |
0051c76a | 465 | |
466 | nw->data = data; | |
467 | nw->father = NULL; | |
468 | nw->left = NULL; | |
469 | nw->right = NULL; | |
470 | nw->son = NULL; | |
471 | ||
472 | nw->rightmost_occ = et_new_occ (nw); | |
473 | nw->parent_occ = NULL; | |
474 | ||
475 | return nw; | |
5dd29ee7 | 476 | } |
477 | ||
0051c76a | 478 | /* Releases et tree T. */ |
479 | ||
480 | void | |
481 | et_free_tree (struct et_node *t) | |
5dd29ee7 | 482 | { |
0051c76a | 483 | while (t->son) |
484 | et_split (t->son); | |
5dd29ee7 | 485 | |
0051c76a | 486 | if (t->father) |
487 | et_split (t); | |
5dd29ee7 | 488 | |
e16712b1 | 489 | et_occurrences.remove (t->rightmost_occ); |
490 | et_nodes.remove (t); | |
5dd29ee7 | 491 | } |
492 | ||
108beec7 | 493 | /* Releases et tree T without maintaining other nodes. */ |
494 | ||
495 | void | |
496 | et_free_tree_force (struct et_node *t) | |
497 | { | |
e16712b1 | 498 | et_occurrences.remove (t->rightmost_occ); |
0a06d4f0 | 499 | if (t->parent_occ) |
e16712b1 | 500 | et_occurrences.remove (t->parent_occ); |
501 | et_nodes.remove (t); | |
108beec7 | 502 | } |
503 | ||
0a06d4f0 | 504 | /* Release the alloc pools, if they are empty. */ |
505 | ||
506 | void | |
507 | et_free_pools (void) | |
508 | { | |
e16712b1 | 509 | et_occurrences.release_if_empty (); |
510 | et_nodes.release_if_empty (); | |
0a06d4f0 | 511 | } |
512 | ||
0051c76a | 513 | /* Sets father of et tree T to FATHER. */ |
514 | ||
5dd29ee7 | 515 | void |
0051c76a | 516 | et_set_father (struct et_node *t, struct et_node *father) |
5dd29ee7 | 517 | { |
0051c76a | 518 | struct et_node *left, *right; |
519 | struct et_occ *rmost, *left_part, *new_f_occ, *p; | |
5dd29ee7 | 520 | |
0051c76a | 521 | /* Update the path represented in the splay tree. */ |
522 | new_f_occ = et_new_occ (father); | |
5dd29ee7 | 523 | |
0051c76a | 524 | rmost = father->rightmost_occ; |
525 | et_splay (rmost); | |
5dd29ee7 | 526 | |
0051c76a | 527 | left_part = rmost->prev; |
5dd29ee7 | 528 | |
0051c76a | 529 | p = t->rightmost_occ; |
530 | et_splay (p); | |
5dd29ee7 | 531 | |
0051c76a | 532 | set_prev (new_f_occ, left_part); |
533 | set_next (new_f_occ, p); | |
534 | ||
535 | p->depth++; | |
536 | p->min++; | |
537 | et_recomp_min (new_f_occ); | |
5dd29ee7 | 538 | |
0051c76a | 539 | set_prev (rmost, new_f_occ); |
35cb5232 | 540 | |
0051c76a | 541 | if (new_f_occ->min + rmost->depth < rmost->min) |
542 | { | |
543 | rmost->min = new_f_occ->min + rmost->depth; | |
544 | rmost->min_occ = new_f_occ->min_occ; | |
545 | } | |
5dd29ee7 | 546 | |
0051c76a | 547 | t->parent_occ = new_f_occ; |
5dd29ee7 | 548 | |
0051c76a | 549 | /* Update the tree. */ |
550 | t->father = father; | |
551 | right = father->son; | |
552 | if (right) | |
553 | left = right->left; | |
554 | else | |
555 | left = right = t; | |
5dd29ee7 | 556 | |
0051c76a | 557 | left->right = t; |
558 | right->left = t; | |
559 | t->left = left; | |
560 | t->right = right; | |
5dd29ee7 | 561 | |
0051c76a | 562 | father->son = t; |
5dd29ee7 | 563 | |
0051c76a | 564 | #ifdef DEBUG_ET |
565 | et_check_tree_sanity (rmost); | |
566 | record_path_before (rmost); | |
567 | #endif | |
5dd29ee7 | 568 | } |
569 | ||
0051c76a | 570 | /* Splits the edge from T to its father. */ |
571 | ||
572 | void | |
573 | et_split (struct et_node *t) | |
5dd29ee7 | 574 | { |
0051c76a | 575 | struct et_node *father = t->father; |
576 | struct et_occ *r, *l, *rmost, *p_occ; | |
5dd29ee7 | 577 | |
0051c76a | 578 | /* Update the path represented by the splay tree. */ |
579 | rmost = t->rightmost_occ; | |
580 | et_splay (rmost); | |
5dd29ee7 | 581 | |
0051c76a | 582 | for (r = rmost->next; r->prev; r = r->prev) |
583 | continue; | |
48e1416a | 584 | et_splay (r); |
5dd29ee7 | 585 | |
0051c76a | 586 | r->prev->parent = NULL; |
587 | p_occ = t->parent_occ; | |
588 | et_splay (p_occ); | |
589 | t->parent_occ = NULL; | |
5dd29ee7 | 590 | |
0051c76a | 591 | l = p_occ->prev; |
592 | p_occ->next->parent = NULL; | |
35cb5232 | 593 | |
0051c76a | 594 | set_prev (r, l); |
5dd29ee7 | 595 | |
0051c76a | 596 | et_recomp_min (r); |
5dd29ee7 | 597 | |
0051c76a | 598 | et_splay (rmost); |
599 | rmost->depth = 0; | |
600 | rmost->min = 0; | |
5dd29ee7 | 601 | |
e16712b1 | 602 | et_occurrences.remove (p_occ); |
5dd29ee7 | 603 | |
0051c76a | 604 | /* Update the tree. */ |
605 | if (father->son == t) | |
606 | father->son = t->right; | |
607 | if (father->son == t) | |
608 | father->son = NULL; | |
609 | else | |
5dd29ee7 | 610 | { |
0051c76a | 611 | t->left->right = t->right; |
612 | t->right->left = t->left; | |
613 | } | |
614 | t->left = t->right = NULL; | |
615 | t->father = NULL; | |
616 | ||
617 | #ifdef DEBUG_ET | |
618 | et_check_tree_sanity (rmost); | |
619 | record_path_before (rmost); | |
620 | ||
621 | et_check_tree_sanity (r); | |
622 | record_path_before (r); | |
623 | #endif | |
624 | } | |
625 | ||
626 | /* Finds the nearest common ancestor of the nodes N1 and N2. */ | |
627 | ||
628 | struct et_node * | |
629 | et_nca (struct et_node *n1, struct et_node *n2) | |
630 | { | |
631 | struct et_occ *o1 = n1->rightmost_occ, *o2 = n2->rightmost_occ, *om; | |
632 | struct et_occ *l, *r, *ret; | |
633 | int mn; | |
634 | ||
635 | if (n1 == n2) | |
636 | return n1; | |
637 | ||
638 | et_splay (o1); | |
639 | l = o1->prev; | |
640 | r = o1->next; | |
641 | if (l) | |
642 | l->parent = NULL; | |
643 | if (r) | |
644 | r->parent = NULL; | |
645 | et_splay (o2); | |
646 | ||
647 | if (l == o2 || (l && l->parent != NULL)) | |
648 | { | |
649 | ret = o2->next; | |
650 | ||
651 | set_prev (o1, o2); | |
652 | if (r) | |
653 | r->parent = o1; | |
5dd29ee7 | 654 | } |
8cb78e28 | 655 | else if (r == o2 || (r && r->parent != NULL)) |
5dd29ee7 | 656 | { |
0051c76a | 657 | ret = o2->prev; |
658 | ||
659 | set_next (o1, o2); | |
660 | if (l) | |
661 | l->parent = o1; | |
5dd29ee7 | 662 | } |
8cb78e28 | 663 | else |
664 | { | |
665 | /* O1 and O2 are in different components of the forest. */ | |
666 | if (l) | |
667 | l->parent = o1; | |
668 | if (r) | |
669 | r->parent = o1; | |
670 | return NULL; | |
671 | } | |
35cb5232 | 672 | |
0051c76a | 673 | if (0 < o2->depth) |
5dd29ee7 | 674 | { |
0051c76a | 675 | om = o1; |
676 | mn = o1->depth; | |
677 | } | |
678 | else | |
679 | { | |
680 | om = o2; | |
681 | mn = o2->depth + o1->depth; | |
5dd29ee7 | 682 | } |
683 | ||
0051c76a | 684 | #ifdef DEBUG_ET |
685 | et_check_tree_sanity (o2); | |
686 | #endif | |
5dd29ee7 | 687 | |
0051c76a | 688 | if (ret && ret->min + o1->depth + o2->depth < mn) |
689 | return ret->min_occ->of; | |
690 | else | |
691 | return om->of; | |
5dd29ee7 | 692 | } |
693 | ||
0051c76a | 694 | /* Checks whether the node UP is an ancestor of the node DOWN. */ |
695 | ||
696 | bool | |
697 | et_below (struct et_node *down, struct et_node *up) | |
5dd29ee7 | 698 | { |
0051c76a | 699 | struct et_occ *u = up->rightmost_occ, *d = down->rightmost_occ; |
700 | struct et_occ *l, *r; | |
701 | ||
702 | if (up == down) | |
703 | return true; | |
704 | ||
705 | et_splay (u); | |
706 | l = u->prev; | |
707 | r = u->next; | |
708 | ||
709 | if (!l) | |
710 | return false; | |
711 | ||
712 | l->parent = NULL; | |
713 | ||
714 | if (r) | |
715 | r->parent = NULL; | |
5dd29ee7 | 716 | |
0051c76a | 717 | et_splay (d); |
718 | ||
719 | if (l == d || l->parent != NULL) | |
5dd29ee7 | 720 | { |
0051c76a | 721 | if (r) |
722 | r->parent = u; | |
723 | set_prev (u, d); | |
724 | #ifdef DEBUG_ET | |
725 | et_check_tree_sanity (u); | |
726 | #endif | |
5dd29ee7 | 727 | } |
0051c76a | 728 | else |
729 | { | |
730 | l->parent = u; | |
731 | ||
732 | /* In case O1 and O2 are in two different trees, we must just restore the | |
733 | original state. */ | |
734 | if (r && r->parent != NULL) | |
735 | set_next (u, d); | |
736 | else | |
737 | set_next (u, r); | |
738 | ||
739 | #ifdef DEBUG_ET | |
740 | et_check_tree_sanity (u); | |
741 | #endif | |
742 | return false; | |
743 | } | |
744 | ||
745 | if (0 >= d->depth) | |
746 | return false; | |
747 | ||
748 | return !d->next || d->next->min + d->depth >= 0; | |
5dd29ee7 | 749 | } |
3f9439d7 | 750 | |
751 | /* Returns the root of the tree that contains NODE. */ | |
752 | ||
753 | struct et_node * | |
754 | et_root (struct et_node *node) | |
755 | { | |
756 | struct et_occ *occ = node->rightmost_occ, *r; | |
757 | ||
f0b5f617 | 758 | /* The root of the tree corresponds to the rightmost occurrence in the |
3f9439d7 | 759 | represented path. */ |
760 | et_splay (occ); | |
761 | for (r = occ; r->next; r = r->next) | |
762 | continue; | |
763 | et_splay (r); | |
764 | ||
765 | return r->of; | |
766 | } |