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