1 /* ET-trees datastructure implementation.
2 Contributed by Pavel Nejedly
3 Copyright (C) 2002 Free Software Foundation, Inc.
5 This file is part of the libiberty library.
6 Libiberty is free software; you can redistribute it and/or
7 modify it under the terms of the GNU Library General Public
8 License as published by the Free Software Foundation; either
9 version 2 of the License, or (at your option) any later version.
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.
16 You should have received a copy of the GNU Library General Public
17 License along with libiberty; see the file COPYING.LIB. If
18 not, write to the Free Software Foundation, Inc., 59 Temple Place - Suite 330,
19 Boston, MA 02111-1307, USA.
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.
28 #include "coretypes.h"
30 #include "et-forest.h"
32 struct et_forest_occurrence;
33 typedef struct et_forest_occurrence* et_forest_occurrence_t;
35 /* The ET-forest type. */
38 /* Linked list of nodes is used to destroy the structure. */
42 /* Single occurrence of node in ET-forest.
43 A single node may have multiple occurrences.
45 struct et_forest_occurrence
47 /* Parent in the splay-tree. */
48 et_forest_occurrence_t parent;
50 /* Children in the splay-tree. */
51 et_forest_occurrence_t left, right;
53 /* Counts of vertices in the two splay-subtrees. */
54 int count_left, count_right;
56 /* Next occurrence of this node in the sequence. */
57 et_forest_occurrence_t next;
59 /* The node, which this occurrence is of. */
60 et_forest_node_t node;
70 /* First and last occurrence of this node in the sequence. */
71 et_forest_occurrence_t first, last;
75 static et_forest_occurrence_t splay PARAMS ((et_forest_occurrence_t));
76 static void remove_all_occurrences PARAMS ((et_forest_node_t));
77 static inline et_forest_occurrence_t find_leftmost_node
78 PARAMS ((et_forest_occurrence_t));
79 static inline et_forest_occurrence_t find_rightmost_node
80 PARAMS ((et_forest_occurrence_t));
81 static int calculate_value PARAMS ((et_forest_occurrence_t));
83 /* Return leftmost node present in the tree roted by OCC. */
84 static inline et_forest_occurrence_t
85 find_leftmost_node (occ)
86 et_forest_occurrence_t occ;
94 /* Return rightmost node present in the tree roted by OCC. */
95 static inline et_forest_occurrence_t
96 find_rightmost_node (occ)
97 et_forest_occurrence_t occ;
105 /* Operation splay for splay tree structure representing ocuurences. */
106 static et_forest_occurrence_t
108 et_forest_occurrence_t node;
110 et_forest_occurrence_t parent;
111 et_forest_occurrence_t grandparent;
115 parent = node->parent;
118 return node; /* node == root. */
120 grandparent = parent->parent;
125 /* Now there are four possible combinations: */
127 if (node == parent->left)
129 if (parent == grandparent->left)
131 et_forest_occurrence_t node1, node2;
135 count1 = node->count_right;
136 node2 = parent->right;
137 count2 = parent->count_right;
139 grandparent->left = node2;
140 grandparent->count_left = count2;
142 node2->parent = grandparent;
143 parent->left = node1;
144 parent->count_left = count1;
146 node1->parent = parent;
147 parent->right = grandparent;
148 parent->count_right = count2 + grandparent->count_right + 1;
149 node->right = parent;
150 node->count_right = count1 + parent->count_right + 1;
152 node->parent = grandparent->parent;
153 parent->parent = node;
154 grandparent->parent = parent;
158 if (node->parent->left == grandparent)
159 node->parent->left = node;
161 node->parent->right = node;
166 /* parent == grandparent->right && node == parent->left*/
167 et_forest_occurrence_t node1, node2;
171 count1 = node->count_left;
173 count2 = node->count_right;
175 grandparent->right = node1;
176 grandparent->count_right = count1;
178 node1->parent = grandparent;
179 parent->left = node2;
180 parent->count_left = count2;
182 node2->parent = parent;
183 node->left = grandparent;
184 node->count_left = grandparent->count_left + count1 + 1;
185 node->right = parent;
186 node->count_right = parent->count_right + count2 + 1;
188 node->parent = grandparent->parent;
189 parent->parent = node;
190 grandparent->parent = node;
194 if (node->parent->left == grandparent)
195 node->parent->left = node;
197 node->parent->right = node;
203 /* node == parent->right. */
204 if (parent == grandparent->left)
206 et_forest_occurrence_t node1, node2;
210 count1 = node->count_left;
212 count2 = node->count_right;
214 parent->right = node1;
215 parent->count_right = count1;
217 node1->parent = parent;
218 grandparent->left = node2;
219 grandparent->count_left = count2;
221 node2->parent = grandparent;
223 node->count_left = parent->count_left + count1 + 1;
224 node->right = grandparent;
225 node->count_right = grandparent->count_right + count2 + 1;
227 node->parent = grandparent->parent;
228 parent->parent = node;
229 grandparent->parent = node;
233 if (node->parent->left == grandparent)
234 node->parent->left = node;
236 node->parent->right = node;
241 /* parent == grandparent->right && node == parent->right*/
242 et_forest_occurrence_t node1, node2;
246 count1 = node->count_left;
247 node2 = parent->left;
248 count2 = parent->count_left;
250 grandparent->right = node2;
251 grandparent->count_right = count2;
253 node2->parent = grandparent;
254 parent->right = node1;
255 parent->count_right = count1;
257 node1->parent = parent;
258 parent->left = grandparent;
259 parent->count_left = count2 + grandparent->count_left + 1;
261 node->count_left = count1 + parent->count_left + 1;
263 node->parent = grandparent->parent;
264 parent->parent = node;
265 grandparent->parent = parent;
269 if (node->parent->left == grandparent)
270 node->parent->left = node;
272 node->parent->right = node;
279 /* parent == root. */
280 /* There are two possible combinations: */
282 if (node == parent->left)
284 et_forest_occurrence_t node1;
288 count1 = node->count_right;
290 parent->left = node1;
291 parent->count_left = count1;
293 node1->parent = parent;
294 node->right = parent;
295 node->count_right = parent->count_right + 1 + count1;
296 node->parent = parent->parent; /* the same as = 0; */
297 parent->parent = node;
301 if (node->parent->left == parent)
302 node->parent->left = node;
304 node->parent->right = node;
309 /* node == parent->right. */
310 et_forest_occurrence_t node1;
314 count1 = node->count_left;
316 parent->right = node1;
317 parent->count_right = count1;
319 node1->parent = parent;
321 node->count_left = parent->count_left + 1 + count1;
322 node->parent = parent->parent; /* the same as = 0; */
323 parent->parent = node;
327 if (node->parent->left == parent)
328 node->parent->left = node;
330 node->parent->right = node;
337 /* Remove all occurences of the given node before destroying the node. */
339 remove_all_occurrences (forest_node)
340 et_forest_node_t forest_node;
342 et_forest_occurrence_t first = forest_node->first;
343 et_forest_occurrence_t last = forest_node->last;
344 et_forest_occurrence_t node;
349 first->left->parent = 0;
351 first->right->parent = 0;
358 last->left->parent = 0;
360 last->right->parent = 0;
363 if (last->right && first->left) /* actually, first->left would suffice. */
365 /* Need to join them. */
366 et_forest_occurrence_t prev_node, next_node;
368 prev_node = splay (find_rightmost_node (first->left));
369 next_node = splay (find_leftmost_node (last->right));
370 /* prev_node and next_node are consecutive occurencies
372 if (prev_node->next != next_node)
375 prev_node->right = next_node->right;
376 prev_node->count_right = next_node->count_right;
377 prev_node->next = next_node->next;
378 if (prev_node->right)
379 prev_node->right->parent = prev_node;
381 if (prev_node->node->last == next_node)
382 prev_node->node->last = prev_node;
393 et_forest_occurrence_t next_node;
398 node->left->parent = 0;
400 node->right->parent = 0;
402 next_node = node->next;
413 /* Calculate ET value of the given node. */
415 calculate_value (node)
416 et_forest_occurrence_t node;
418 int value = node->count_left;
422 if (node == node->parent->right)
423 value += node->parent->count_left + 1;
434 /* Create ET-forest structure. */
439 et_forest_t forest = xmalloc (sizeof (struct et_forest));
447 /* Deallocate the structure. */
449 et_forest_delete (forest)
458 /* Create new node with VALUE and return the edge.
459 Return NULL when memory allocation failed. */
461 et_forest_add_node (forest, value)
465 /* Create node with one occurrence. */
466 et_forest_node_t node;
467 et_forest_occurrence_t occ;
469 node = xmalloc (sizeof (struct et_forest_node));
470 occ = xmalloc (sizeof (struct et_forest_occurrence));
472 node->first = node->last = occ;
477 occ->left = occ->right = occ->parent = 0;
479 occ->count_left = occ->count_right = 0;
483 /* Add new edge to the tree, return 1 if succesfull.
484 0 indicates that creation of the edge will close the cycle in graph. */
486 et_forest_add_edge (forest, parent_node, child_node)
487 et_forest_t forest ATTRIBUTE_UNUSED;
488 et_forest_node_t parent_node;
489 et_forest_node_t child_node;
491 et_forest_occurrence_t new_occ, parent_occ, child_occ;
493 if (! parent_node || ! child_node)
496 parent_occ = parent_node->first;
497 child_occ = child_node->first;
502 if (parent_occ->parent)
503 return 0; /* Both child and parent are in the same tree. */
506 abort (); /* child must be root of its containing tree. */
508 new_occ = xmalloc (sizeof (struct et_forest_occurrence));
510 new_occ->node = parent_node;
511 new_occ->left = child_occ;
512 new_occ->count_left = child_occ->count_right + 1; /* count_left is 0. */
513 new_occ->right = parent_occ->right;
514 new_occ->count_right = parent_occ->count_right;
515 new_occ->parent = parent_occ;
516 new_occ->next = parent_occ->next;
517 child_occ->parent = new_occ;
518 parent_occ->right = new_occ;
519 parent_occ->count_right = new_occ->count_left + new_occ->count_right + 1;
520 parent_occ->next = new_occ;
522 new_occ->right->parent = new_occ;
524 if (parent_node->last == parent_occ)
525 parent_node->last = new_occ;
529 /* Remove NODE from the tree and all connected edges. */
531 et_forest_remove_node (forest, node)
533 et_forest_node_t node;
535 remove_all_occurrences (node);
541 /* Remove edge from the tree, return 1 if sucesfull,
542 0 indicates nonexisting edge. */
544 et_forest_remove_edge (forest, parent_node, child_node)
545 et_forest_t forest ATTRIBUTE_UNUSED;
546 et_forest_node_t parent_node;
547 et_forest_node_t child_node;
549 et_forest_occurrence_t parent_pre_occ, parent_post_occ;
551 splay (child_node->first);
553 if (! child_node->first->left)
556 parent_pre_occ = find_rightmost_node (child_node->first->left);
557 if (parent_pre_occ->node != parent_node)
560 splay (parent_pre_occ);
561 parent_pre_occ->right->parent = 0;
563 parent_post_occ = parent_pre_occ->next;
564 splay (parent_post_occ);
566 parent_post_occ->left->parent = 0;
568 parent_pre_occ->right = parent_post_occ->right;
569 parent_pre_occ->count_right = parent_post_occ->count_right;
570 if (parent_post_occ->right)
571 parent_post_occ->right->parent = parent_pre_occ;
573 parent_pre_occ->next = parent_post_occ->next;
575 if (parent_post_occ == parent_node->last)
576 parent_node->last = parent_pre_occ;
578 free (parent_post_occ);
582 /* Return the parent of the NODE if any, NULL otherwise. */
584 et_forest_parent (forest, node)
585 et_forest_t forest ATTRIBUTE_UNUSED;
586 et_forest_node_t node;
590 if (node->first->left)
591 return find_rightmost_node (node->first->left)->node;
597 /* Return nearest common ancestor of NODE1 and NODE2.
598 Return NULL of they are in different trees. */
600 et_forest_common_ancestor (forest, node1, node2)
601 et_forest_t forest ATTRIBUTE_UNUSED;
602 et_forest_node_t node1;
603 et_forest_node_t node2;
605 int value1, value2, max_value;
606 et_forest_node_t ancestor;
611 if (! node1 || ! node2)
614 splay (node1->first);
615 splay (node2->first);
617 if (! node1->first->parent) /* The two vertices are in different trees. */
620 value2 = calculate_value (node2->first);
621 value1 = calculate_value (node1->first);
634 while (calculate_value (ancestor->last) < max_value)
636 /* Find parent node. */
637 splay (ancestor->first);
638 ancestor = find_rightmost_node (ancestor->first->left) ->node;
644 /* Return the value pointer of node set during it's creation. */
646 et_forest_node_value (forest, node)
647 et_forest_t forest ATTRIBUTE_UNUSED;
648 et_forest_node_t node;
650 /* Alloc threading NULL as a special node of the forest. */
656 /* Find all sons of NODE and store them into ARRAY allocated by the caller.
657 Return number of nodes found. */
659 et_forest_enumerate_sons (forest, node, array)
660 et_forest_t forest ATTRIBUTE_UNUSED;
661 et_forest_node_t node;
662 et_forest_node_t *array;
665 et_forest_occurrence_t occ = node->first, stop = node->last, occ1;
667 /* Parent is the rightmost node of the left successor.
668 Look for all occurences having no right succesor
669 and lookup the sons. */
675 occ1 = find_leftmost_node (occ->right);
676 if (occ1->node->first == occ1)
677 array[n++] = occ1->node;