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