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