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