]>
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 | |
d47cc544 SB |
40 | /* The occurence of a node in the et tree. */ |
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. */ | |
54 | struct et_occ *min_occ; /* The occurence in the subtree with the minimal | |
55 | depth. */ | |
56 | }; | |
f1cfb09f | 57 | |
d47cc544 SB |
58 | static alloc_pool et_nodes; |
59 | static alloc_pool et_occurences; | |
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 | ||
d47cc544 | 115 | /* Recompute minimum for occurence 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 | |
d47cc544 SB |
209 | static int len; |
210 | static void *datas[100000]; | |
211 | static int depths[100000]; | |
f1cfb09f | 212 | |
d47cc544 | 213 | /* Records the path represented by OCC, with depth incremented by DEPTH. */ |
f1cfb09f | 214 | |
d47cc544 SB |
215 | static int |
216 | record_path_before_1 (struct et_occ *occ, int depth) | |
217 | { | |
218 | int mn, m; | |
f1cfb09f | 219 | |
d47cc544 SB |
220 | depth += occ->depth; |
221 | mn = depth; | |
222 | ||
223 | if (occ->prev) | |
224 | { | |
225 | m = record_path_before_1 (occ->prev, depth); | |
226 | if (m < mn) | |
227 | mn = m; | |
f1cfb09f JH |
228 | } |
229 | ||
d47cc544 SB |
230 | fprintf (stderr, "%d (%d); ", ((basic_block) occ->of->data)->index, depth); |
231 | depths[len] = depth; | |
232 | datas[len] = occ->of; | |
233 | len++; | |
234 | ||
235 | if (occ->next) | |
f1cfb09f | 236 | { |
d47cc544 SB |
237 | m = record_path_before_1 (occ->next, depth); |
238 | if (m < mn) | |
239 | mn = m; | |
240 | } | |
f1cfb09f | 241 | |
d47cc544 SB |
242 | if (mn != occ->min + depth - occ->depth) |
243 | abort (); | |
f1cfb09f | 244 | |
d47cc544 SB |
245 | return mn; |
246 | } | |
f1cfb09f | 247 | |
d47cc544 | 248 | /* Records the path represented by a tree containing OCC. */ |
f1cfb09f | 249 | |
d47cc544 SB |
250 | static void |
251 | record_path_before (struct et_occ *occ) | |
252 | { | |
253 | while (occ->parent) | |
254 | occ = occ->parent; | |
f1cfb09f | 255 | |
d47cc544 SB |
256 | len = 0; |
257 | record_path_before_1 (occ, 0); | |
258 | fprintf (stderr, "\n"); | |
f1cfb09f JH |
259 | } |
260 | ||
d47cc544 SB |
261 | /* Checks whether the path represented by OCC, with depth incremented by DEPTH, |
262 | was not changed since the last recording. */ | |
263 | ||
264 | static int | |
265 | check_path_after_1 (struct et_occ *occ, int depth) | |
f1cfb09f | 266 | { |
d47cc544 SB |
267 | int mn, m; |
268 | ||
269 | depth += occ->depth; | |
270 | mn = depth; | |
f1cfb09f | 271 | |
d47cc544 | 272 | if (occ->next) |
f1cfb09f | 273 | { |
d47cc544 SB |
274 | m = check_path_after_1 (occ->next, depth); |
275 | if (m < mn) | |
276 | mn = m; | |
277 | } | |
f1cfb09f | 278 | |
d47cc544 SB |
279 | len--; |
280 | if (depths[len] != depth | |
281 | || datas[len] != occ->of) | |
282 | abort (); | |
283 | ||
284 | if (occ->prev) | |
285 | { | |
286 | m = check_path_after_1 (occ->prev, depth); | |
287 | if (m < mn) | |
288 | mn = m; | |
f1cfb09f JH |
289 | } |
290 | ||
d47cc544 SB |
291 | if (mn != occ->min + depth - occ->depth) |
292 | abort (); | |
293 | ||
294 | return mn; | |
f1cfb09f JH |
295 | } |
296 | ||
d47cc544 SB |
297 | /* Checks whether the path represented by a tree containing OCC was |
298 | not changed since the last recording. */ | |
299 | ||
300 | static void | |
301 | check_path_after (struct et_occ *occ) | |
302 | { | |
303 | while (occ->parent) | |
304 | occ = occ->parent; | |
305 | ||
306 | check_path_after_1 (occ, 0); | |
307 | if (len != 0) | |
308 | abort (); | |
309 | } | |
f1cfb09f | 310 | |
d47cc544 | 311 | #endif |
f1cfb09f | 312 | |
d47cc544 | 313 | /* Splay the occurence OCC to the root of the tree. */ |
f1cfb09f | 314 | |
965514bd | 315 | static void |
d47cc544 | 316 | et_splay (struct et_occ *occ) |
f1cfb09f | 317 | { |
d47cc544 SB |
318 | struct et_occ *f, *gf, *ggf; |
319 | int occ_depth, f_depth, gf_depth; | |
320 | ||
321 | #ifdef DEBUG_ET | |
322 | record_path_before (occ); | |
323 | et_check_tree_sanity (occ); | |
324 | #endif | |
325 | ||
326 | while (occ->parent) | |
327 | { | |
328 | occ_depth = occ->depth; | |
f1cfb09f | 329 | |
d47cc544 SB |
330 | f = occ->parent; |
331 | f_depth = f->depth; | |
f1cfb09f | 332 | |
d47cc544 | 333 | gf = f->parent; |
f1cfb09f | 334 | |
d47cc544 SB |
335 | if (!gf) |
336 | { | |
337 | set_depth_add (occ, f_depth); | |
338 | occ->min_occ = f->min_occ; | |
339 | occ->min = f->min; | |
f1cfb09f | 340 | |
d47cc544 SB |
341 | if (f->prev == occ) |
342 | { | |
343 | /* zig */ | |
344 | set_prev (f, occ->next); | |
345 | set_next (occ, f); | |
346 | set_depth_add (f->prev, occ_depth); | |
347 | } | |
348 | else | |
349 | { | |
350 | /* zag */ | |
351 | set_next (f, occ->prev); | |
352 | set_prev (occ, f); | |
353 | set_depth_add (f->next, occ_depth); | |
354 | } | |
355 | set_depth (f, -occ_depth); | |
356 | occ->parent = NULL; | |
357 | ||
358 | et_recomp_min (f); | |
359 | #ifdef DEBUG_ET | |
360 | et_check_tree_sanity (occ); | |
361 | check_path_after (occ); | |
362 | #endif | |
363 | return; | |
364 | } | |
365 | ||
366 | gf_depth = gf->depth; | |
367 | ||
368 | set_depth_add (occ, f_depth + gf_depth); | |
369 | occ->min_occ = gf->min_occ; | |
370 | occ->min = gf->min; | |
371 | ||
372 | ggf = gf->parent; | |
373 | ||
374 | if (gf->prev == f) | |
375 | { | |
376 | if (f->prev == occ) | |
377 | { | |
378 | /* zig zig */ | |
379 | set_prev (gf, f->next); | |
380 | set_prev (f, occ->next); | |
381 | set_next (occ, f); | |
382 | set_next (f, gf); | |
383 | ||
384 | set_depth (f, -occ_depth); | |
385 | set_depth_add (f->prev, occ_depth); | |
386 | set_depth (gf, -f_depth); | |
387 | set_depth_add (gf->prev, f_depth); | |
388 | } | |
389 | else | |
390 | { | |
391 | /* zag zig */ | |
392 | set_prev (gf, occ->next); | |
393 | set_next (f, occ->prev); | |
394 | set_prev (occ, f); | |
395 | set_next (occ, gf); | |
396 | ||
397 | set_depth (f, -occ_depth); | |
398 | set_depth_add (f->next, occ_depth); | |
399 | set_depth (gf, -occ_depth - f_depth); | |
400 | set_depth_add (gf->prev, occ_depth + f_depth); | |
401 | } | |
402 | } | |
403 | else | |
404 | { | |
405 | if (f->prev == occ) | |
406 | { | |
407 | /* zig zag */ | |
408 | set_next (gf, occ->prev); | |
409 | set_prev (f, occ->next); | |
410 | set_prev (occ, gf); | |
411 | set_next (occ, f); | |
412 | ||
413 | set_depth (f, -occ_depth); | |
414 | set_depth_add (f->prev, occ_depth); | |
415 | set_depth (gf, -occ_depth - f_depth); | |
416 | set_depth_add (gf->next, occ_depth + f_depth); | |
417 | } | |
418 | else | |
419 | { | |
420 | /* zag zag */ | |
421 | set_next (gf, f->prev); | |
422 | set_next (f, occ->prev); | |
423 | set_prev (occ, f); | |
424 | set_prev (f, gf); | |
425 | ||
426 | set_depth (f, -occ_depth); | |
427 | set_depth_add (f->next, occ_depth); | |
428 | set_depth (gf, -f_depth); | |
429 | set_depth_add (gf->next, f_depth); | |
430 | } | |
431 | } | |
432 | ||
433 | occ->parent = ggf; | |
434 | if (ggf) | |
435 | { | |
436 | if (ggf->prev == gf) | |
437 | ggf->prev = occ; | |
438 | else | |
439 | ggf->next = occ; | |
440 | } | |
441 | ||
442 | et_recomp_min (gf); | |
443 | et_recomp_min (f); | |
444 | #ifdef DEBUG_ET | |
445 | et_check_tree_sanity (occ); | |
446 | #endif | |
447 | } | |
448 | ||
449 | #ifdef DEBUG_ET | |
450 | et_check_sanity (occ); | |
451 | check_path_after (occ); | |
452 | #endif | |
453 | } | |
454 | ||
455 | /* Create a new et tree occurence of NODE. */ | |
456 | ||
457 | static struct et_occ * | |
458 | et_new_occ (struct et_node *node) | |
f1cfb09f | 459 | { |
d47cc544 SB |
460 | struct et_occ *nw; |
461 | ||
462 | if (!et_occurences) | |
463 | et_occurences = create_alloc_pool ("et_occ pool", sizeof (struct et_occ), 300); | |
464 | nw = pool_alloc (et_occurences); | |
465 | ||
466 | nw->of = node; | |
467 | nw->parent = NULL; | |
468 | nw->prev = NULL; | |
469 | nw->next = NULL; | |
470 | ||
471 | nw->depth = 0; | |
472 | nw->min_occ = nw; | |
473 | nw->min = 0; | |
474 | ||
475 | return nw; | |
f1cfb09f JH |
476 | } |
477 | ||
d47cc544 SB |
478 | /* Create a new et tree containing DATA. */ |
479 | ||
480 | struct et_node * | |
481 | et_new_tree (void *data) | |
f1cfb09f | 482 | { |
d47cc544 SB |
483 | struct et_node *nw; |
484 | ||
485 | if (!et_nodes) | |
486 | et_nodes = create_alloc_pool ("et_node pool", sizeof (struct et_node), 300); | |
487 | nw = pool_alloc (et_nodes); | |
488 | ||
489 | nw->data = data; | |
490 | nw->father = NULL; | |
491 | nw->left = NULL; | |
492 | nw->right = NULL; | |
493 | nw->son = NULL; | |
494 | ||
495 | nw->rightmost_occ = et_new_occ (nw); | |
496 | nw->parent_occ = NULL; | |
497 | ||
498 | return nw; | |
f1cfb09f JH |
499 | } |
500 | ||
d47cc544 SB |
501 | /* Releases et tree T. */ |
502 | ||
503 | void | |
504 | et_free_tree (struct et_node *t) | |
f1cfb09f | 505 | { |
d47cc544 SB |
506 | while (t->son) |
507 | et_split (t->son); | |
f1cfb09f | 508 | |
d47cc544 SB |
509 | if (t->father) |
510 | et_split (t); | |
f1cfb09f | 511 | |
d47cc544 SB |
512 | pool_free (et_occurences, t->rightmost_occ); |
513 | pool_free (et_nodes, t); | |
f1cfb09f JH |
514 | } |
515 | ||
d47cc544 SB |
516 | /* Sets father of et tree T to FATHER. */ |
517 | ||
f1cfb09f | 518 | void |
d47cc544 | 519 | et_set_father (struct et_node *t, struct et_node *father) |
f1cfb09f | 520 | { |
d47cc544 SB |
521 | struct et_node *left, *right; |
522 | struct et_occ *rmost, *left_part, *new_f_occ, *p; | |
f1cfb09f | 523 | |
d47cc544 SB |
524 | /* Update the path represented in the splay tree. */ |
525 | new_f_occ = et_new_occ (father); | |
f1cfb09f | 526 | |
d47cc544 SB |
527 | rmost = father->rightmost_occ; |
528 | et_splay (rmost); | |
f1cfb09f | 529 | |
d47cc544 | 530 | left_part = rmost->prev; |
f1cfb09f | 531 | |
d47cc544 SB |
532 | p = t->rightmost_occ; |
533 | et_splay (p); | |
f1cfb09f | 534 | |
d47cc544 SB |
535 | set_prev (new_f_occ, left_part); |
536 | set_next (new_f_occ, p); | |
537 | ||
538 | p->depth++; | |
539 | p->min++; | |
540 | et_recomp_min (new_f_occ); | |
f1cfb09f | 541 | |
d47cc544 | 542 | set_prev (rmost, new_f_occ); |
502b8322 | 543 | |
d47cc544 SB |
544 | if (new_f_occ->min + rmost->depth < rmost->min) |
545 | { | |
546 | rmost->min = new_f_occ->min + rmost->depth; | |
547 | rmost->min_occ = new_f_occ->min_occ; | |
548 | } | |
f1cfb09f | 549 | |
d47cc544 | 550 | t->parent_occ = new_f_occ; |
f1cfb09f | 551 | |
d47cc544 SB |
552 | /* Update the tree. */ |
553 | t->father = father; | |
554 | right = father->son; | |
555 | if (right) | |
556 | left = right->left; | |
557 | else | |
558 | left = right = t; | |
f1cfb09f | 559 | |
d47cc544 SB |
560 | left->right = t; |
561 | right->left = t; | |
562 | t->left = left; | |
563 | t->right = right; | |
f1cfb09f | 564 | |
d47cc544 | 565 | father->son = t; |
f1cfb09f | 566 | |
d47cc544 SB |
567 | #ifdef DEBUG_ET |
568 | et_check_tree_sanity (rmost); | |
569 | record_path_before (rmost); | |
570 | #endif | |
f1cfb09f JH |
571 | } |
572 | ||
d47cc544 SB |
573 | /* Splits the edge from T to its father. */ |
574 | ||
575 | void | |
576 | et_split (struct et_node *t) | |
f1cfb09f | 577 | { |
d47cc544 SB |
578 | struct et_node *father = t->father; |
579 | struct et_occ *r, *l, *rmost, *p_occ; | |
f1cfb09f | 580 | |
d47cc544 SB |
581 | /* Update the path represented by the splay tree. */ |
582 | rmost = t->rightmost_occ; | |
583 | et_splay (rmost); | |
f1cfb09f | 584 | |
d47cc544 SB |
585 | for (r = rmost->next; r->prev; r = r->prev) |
586 | continue; | |
587 | et_splay (r); | |
f1cfb09f | 588 | |
d47cc544 SB |
589 | r->prev->parent = NULL; |
590 | p_occ = t->parent_occ; | |
591 | et_splay (p_occ); | |
592 | t->parent_occ = NULL; | |
f1cfb09f | 593 | |
d47cc544 SB |
594 | l = p_occ->prev; |
595 | p_occ->next->parent = NULL; | |
502b8322 | 596 | |
d47cc544 | 597 | set_prev (r, l); |
f1cfb09f | 598 | |
d47cc544 | 599 | et_recomp_min (r); |
f1cfb09f | 600 | |
d47cc544 SB |
601 | et_splay (rmost); |
602 | rmost->depth = 0; | |
603 | rmost->min = 0; | |
f1cfb09f | 604 | |
d47cc544 | 605 | pool_free (et_occurences, p_occ); |
f1cfb09f | 606 | |
d47cc544 SB |
607 | /* Update the tree. */ |
608 | if (father->son == t) | |
609 | father->son = t->right; | |
610 | if (father->son == t) | |
611 | father->son = NULL; | |
612 | else | |
f1cfb09f | 613 | { |
d47cc544 SB |
614 | t->left->right = t->right; |
615 | t->right->left = t->left; | |
616 | } | |
617 | t->left = t->right = NULL; | |
618 | t->father = NULL; | |
619 | ||
620 | #ifdef DEBUG_ET | |
621 | et_check_tree_sanity (rmost); | |
622 | record_path_before (rmost); | |
623 | ||
624 | et_check_tree_sanity (r); | |
625 | record_path_before (r); | |
626 | #endif | |
627 | } | |
628 | ||
629 | /* Finds the nearest common ancestor of the nodes N1 and N2. */ | |
630 | ||
631 | struct et_node * | |
632 | et_nca (struct et_node *n1, struct et_node *n2) | |
633 | { | |
634 | struct et_occ *o1 = n1->rightmost_occ, *o2 = n2->rightmost_occ, *om; | |
635 | struct et_occ *l, *r, *ret; | |
636 | int mn; | |
637 | ||
638 | if (n1 == n2) | |
639 | return n1; | |
640 | ||
641 | et_splay (o1); | |
642 | l = o1->prev; | |
643 | r = o1->next; | |
644 | if (l) | |
645 | l->parent = NULL; | |
646 | if (r) | |
647 | r->parent = NULL; | |
648 | et_splay (o2); | |
649 | ||
650 | if (l == o2 || (l && l->parent != NULL)) | |
651 | { | |
652 | ret = o2->next; | |
653 | ||
654 | set_prev (o1, o2); | |
655 | if (r) | |
656 | r->parent = o1; | |
f1cfb09f JH |
657 | } |
658 | else | |
659 | { | |
d47cc544 SB |
660 | ret = o2->prev; |
661 | ||
662 | set_next (o1, o2); | |
663 | if (l) | |
664 | l->parent = o1; | |
f1cfb09f | 665 | } |
502b8322 | 666 | |
d47cc544 | 667 | if (0 < o2->depth) |
f1cfb09f | 668 | { |
d47cc544 SB |
669 | om = o1; |
670 | mn = o1->depth; | |
671 | } | |
672 | else | |
673 | { | |
674 | om = o2; | |
675 | mn = o2->depth + o1->depth; | |
f1cfb09f JH |
676 | } |
677 | ||
d47cc544 SB |
678 | #ifdef DEBUG_ET |
679 | et_check_tree_sanity (o2); | |
680 | #endif | |
f1cfb09f | 681 | |
d47cc544 SB |
682 | if (ret && ret->min + o1->depth + o2->depth < mn) |
683 | return ret->min_occ->of; | |
684 | else | |
685 | return om->of; | |
f1cfb09f JH |
686 | } |
687 | ||
d47cc544 SB |
688 | /* Checks whether the node UP is an ancestor of the node DOWN. */ |
689 | ||
690 | bool | |
691 | et_below (struct et_node *down, struct et_node *up) | |
f1cfb09f | 692 | { |
d47cc544 SB |
693 | struct et_occ *u = up->rightmost_occ, *d = down->rightmost_occ; |
694 | struct et_occ *l, *r; | |
695 | ||
696 | if (up == down) | |
697 | return true; | |
698 | ||
699 | et_splay (u); | |
700 | l = u->prev; | |
701 | r = u->next; | |
702 | ||
703 | if (!l) | |
704 | return false; | |
705 | ||
706 | l->parent = NULL; | |
707 | ||
708 | if (r) | |
709 | r->parent = NULL; | |
f1cfb09f | 710 | |
d47cc544 SB |
711 | et_splay (d); |
712 | ||
713 | if (l == d || l->parent != NULL) | |
f1cfb09f | 714 | { |
d47cc544 SB |
715 | if (r) |
716 | r->parent = u; | |
717 | set_prev (u, d); | |
718 | #ifdef DEBUG_ET | |
719 | et_check_tree_sanity (u); | |
720 | #endif | |
f1cfb09f | 721 | } |
d47cc544 SB |
722 | else |
723 | { | |
724 | l->parent = u; | |
725 | ||
726 | /* In case O1 and O2 are in two different trees, we must just restore the | |
727 | original state. */ | |
728 | if (r && r->parent != NULL) | |
729 | set_next (u, d); | |
730 | else | |
731 | set_next (u, r); | |
732 | ||
733 | #ifdef DEBUG_ET | |
734 | et_check_tree_sanity (u); | |
735 | #endif | |
736 | return false; | |
737 | } | |
738 | ||
739 | if (0 >= d->depth) | |
740 | return false; | |
741 | ||
742 | return !d->next || d->next->min + d->depth >= 0; | |
f1cfb09f | 743 | } |