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