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