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