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"
31 #include "alloc-pool.h"
33 struct et_forest_occurrence;
34 typedef struct et_forest_occurrence* et_forest_occurrence_t;
36 /* The ET-forest type. */
39 /* Linked list of nodes is used to destroy the structure. */
42 alloc_pool occur_pool;
45 /* Single occurrence of node in ET-forest.
46 A single node may have multiple occurrences.
48 struct et_forest_occurrence
50 /* Parent in the splay-tree. */
51 et_forest_occurrence_t parent;
53 /* Children in the splay-tree. */
54 et_forest_occurrence_t left, right;
56 /* Counts of vertices in the two splay-subtrees. */
57 int count_left, count_right;
59 /* Next occurrence of this node in the sequence. */
60 et_forest_occurrence_t next;
62 /* The node, which this occurrence is of. */
63 et_forest_node_t node;
73 /* First and last occurrence of this node in the sequence. */
74 et_forest_occurrence_t first, last;
78 static et_forest_occurrence_t splay PARAMS ((et_forest_occurrence_t));
79 static void remove_all_occurrences PARAMS ((et_forest_t, et_forest_node_t));
80 static inline et_forest_occurrence_t find_leftmost_node
81 PARAMS ((et_forest_occurrence_t));
82 static inline et_forest_occurrence_t find_rightmost_node
83 PARAMS ((et_forest_occurrence_t));
84 static int calculate_value PARAMS ((et_forest_occurrence_t));
86 /* Return leftmost node present in the tree roted by OCC. */
87 static inline et_forest_occurrence_t
88 find_leftmost_node (occ)
89 et_forest_occurrence_t occ;
97 /* Return rightmost node present in the tree roted by OCC. */
98 static inline et_forest_occurrence_t
99 find_rightmost_node (occ)
100 et_forest_occurrence_t occ;
108 /* Operation splay for splay tree structure representing occurrences. */
109 static et_forest_occurrence_t
111 et_forest_occurrence_t node;
113 et_forest_occurrence_t parent;
114 et_forest_occurrence_t grandparent;
118 parent = node->parent;
121 return node; /* node == root. */
123 grandparent = parent->parent;
128 /* Now there are four possible combinations: */
130 if (node == parent->left)
132 if (parent == grandparent->left)
134 et_forest_occurrence_t node1, node2;
138 count1 = node->count_right;
139 node2 = parent->right;
140 count2 = parent->count_right;
142 grandparent->left = node2;
143 grandparent->count_left = count2;
145 node2->parent = grandparent;
146 parent->left = node1;
147 parent->count_left = count1;
149 node1->parent = parent;
150 parent->right = grandparent;
151 parent->count_right = count2 + grandparent->count_right + 1;
152 node->right = parent;
153 node->count_right = count1 + parent->count_right + 1;
155 node->parent = grandparent->parent;
156 parent->parent = node;
157 grandparent->parent = parent;
161 if (node->parent->left == grandparent)
162 node->parent->left = node;
164 node->parent->right = node;
169 /* parent == grandparent->right && node == parent->left*/
170 et_forest_occurrence_t node1, node2;
174 count1 = node->count_left;
176 count2 = node->count_right;
178 grandparent->right = node1;
179 grandparent->count_right = count1;
181 node1->parent = grandparent;
182 parent->left = node2;
183 parent->count_left = count2;
185 node2->parent = parent;
186 node->left = grandparent;
187 node->count_left = grandparent->count_left + count1 + 1;
188 node->right = parent;
189 node->count_right = parent->count_right + count2 + 1;
191 node->parent = grandparent->parent;
192 parent->parent = node;
193 grandparent->parent = node;
197 if (node->parent->left == grandparent)
198 node->parent->left = node;
200 node->parent->right = node;
206 /* node == parent->right. */
207 if (parent == grandparent->left)
209 et_forest_occurrence_t node1, node2;
213 count1 = node->count_left;
215 count2 = node->count_right;
217 parent->right = node1;
218 parent->count_right = count1;
220 node1->parent = parent;
221 grandparent->left = node2;
222 grandparent->count_left = count2;
224 node2->parent = grandparent;
226 node->count_left = parent->count_left + count1 + 1;
227 node->right = grandparent;
228 node->count_right = grandparent->count_right + count2 + 1;
230 node->parent = grandparent->parent;
231 parent->parent = node;
232 grandparent->parent = node;
236 if (node->parent->left == grandparent)
237 node->parent->left = node;
239 node->parent->right = node;
244 /* parent == grandparent->right && node == parent->right*/
245 et_forest_occurrence_t node1, node2;
249 count1 = node->count_left;
250 node2 = parent->left;
251 count2 = parent->count_left;
253 grandparent->right = node2;
254 grandparent->count_right = count2;
256 node2->parent = grandparent;
257 parent->right = node1;
258 parent->count_right = count1;
260 node1->parent = parent;
261 parent->left = grandparent;
262 parent->count_left = count2 + grandparent->count_left + 1;
264 node->count_left = count1 + parent->count_left + 1;
266 node->parent = grandparent->parent;
267 parent->parent = node;
268 grandparent->parent = parent;
272 if (node->parent->left == grandparent)
273 node->parent->left = node;
275 node->parent->right = node;
282 /* parent == root. */
283 /* There are two possible combinations: */
285 if (node == parent->left)
287 et_forest_occurrence_t node1;
291 count1 = node->count_right;
293 parent->left = node1;
294 parent->count_left = count1;
296 node1->parent = parent;
297 node->right = parent;
298 node->count_right = parent->count_right + 1 + count1;
299 node->parent = parent->parent; /* the same as = 0; */
300 parent->parent = node;
304 if (node->parent->left == parent)
305 node->parent->left = node;
307 node->parent->right = node;
312 /* node == parent->right. */
313 et_forest_occurrence_t node1;
317 count1 = node->count_left;
319 parent->right = node1;
320 parent->count_right = count1;
322 node1->parent = parent;
324 node->count_left = parent->count_left + 1 + count1;
325 node->parent = parent->parent; /* the same as = 0; */
326 parent->parent = node;
330 if (node->parent->left == parent)
331 node->parent->left = node;
333 node->parent->right = node;
340 /* Remove all occurrences of the given node before destroying the node. */
342 remove_all_occurrences (forest, forest_node)
344 et_forest_node_t forest_node;
346 et_forest_occurrence_t first = forest_node->first;
347 et_forest_occurrence_t last = forest_node->last;
348 et_forest_occurrence_t node;
353 first->left->parent = 0;
355 first->right->parent = 0;
362 last->left->parent = 0;
364 last->right->parent = 0;
367 if (last->right && first->left) /* actually, first->left would suffice. */
369 /* Need to join them. */
370 et_forest_occurrence_t prev_node, next_node;
372 prev_node = splay (find_rightmost_node (first->left));
373 next_node = splay (find_leftmost_node (last->right));
374 /* prev_node and next_node are consecutive occurrences
376 if (prev_node->next != next_node)
379 prev_node->right = next_node->right;
380 prev_node->count_right = next_node->count_right;
381 prev_node->next = next_node->next;
382 if (prev_node->right)
383 prev_node->right->parent = prev_node;
385 if (prev_node->node->last == next_node)
386 prev_node->node->last = prev_node;
388 pool_free (forest->occur_pool, next_node);
397 et_forest_occurrence_t next_node;
402 node->left->parent = 0;
404 node->right->parent = 0;
406 next_node = node->next;
407 pool_free (forest->occur_pool, node);
412 pool_free (forest->occur_pool, first);
414 pool_free (forest->occur_pool, last);
417 /* Calculate ET value of the given node. */
419 calculate_value (node)
420 et_forest_occurrence_t node;
422 int value = node->count_left;
426 if (node == node->parent->right)
427 value += node->parent->count_left + 1;
438 /* Create ET-forest structure. */
443 et_forest_t forest = xmalloc (sizeof (struct et_forest));
446 forest->occur_pool = create_alloc_pool ("et_forest_occurrence pool", sizeof (struct et_forest_occurrence), 300);
447 forest->node_pool = create_alloc_pool ("et_forest_node pool", sizeof (struct et_forest_node), 300);
453 /* Deallocate the structure. */
455 et_forest_delete (forest)
460 free_alloc_pool (forest->occur_pool);
461 free_alloc_pool (forest->node_pool);
465 /* Create new node with VALUE and return the edge.
466 Return NULL when memory allocation failed. */
468 et_forest_add_node (forest, value)
472 /* Create node with one occurrence. */
473 et_forest_node_t node;
474 et_forest_occurrence_t occ;
476 node = pool_alloc (forest->node_pool);
477 occ = pool_alloc (forest->occur_pool);
479 node->first = node->last = occ;
484 occ->left = occ->right = occ->parent = 0;
486 occ->count_left = occ->count_right = 0;
490 /* Add new edge to the tree, return 1 if successful.
491 0 indicates that creation of the edge will close the cycle in graph. */
493 et_forest_add_edge (forest, parent_node, child_node)
494 et_forest_t forest ATTRIBUTE_UNUSED;
495 et_forest_node_t parent_node;
496 et_forest_node_t child_node;
498 et_forest_occurrence_t new_occ, parent_occ, child_occ;
500 if (! parent_node || ! child_node)
503 parent_occ = parent_node->first;
504 child_occ = child_node->first;
509 if (parent_occ->parent)
510 return 0; /* Both child and parent are in the same tree. */
513 abort (); /* child must be root of its containing tree. */
515 new_occ = pool_alloc (forest->occur_pool);
517 new_occ->node = parent_node;
518 new_occ->left = child_occ;
519 new_occ->count_left = child_occ->count_right + 1; /* count_left is 0. */
520 new_occ->right = parent_occ->right;
521 new_occ->count_right = parent_occ->count_right;
522 new_occ->parent = parent_occ;
523 new_occ->next = parent_occ->next;
524 child_occ->parent = new_occ;
525 parent_occ->right = new_occ;
526 parent_occ->count_right = new_occ->count_left + new_occ->count_right + 1;
527 parent_occ->next = new_occ;
529 new_occ->right->parent = new_occ;
531 if (parent_node->last == parent_occ)
532 parent_node->last = new_occ;
536 /* Remove NODE from the tree and all connected edges. */
538 et_forest_remove_node (forest, node)
540 et_forest_node_t node;
542 remove_all_occurrences (forest, node);
545 pool_free (forest->node_pool, node);
548 /* Remove edge from the tree, return 1 if successful,
549 0 indicates nonexisting edge. */
551 et_forest_remove_edge (forest, parent_node, child_node)
552 et_forest_t forest ATTRIBUTE_UNUSED;
553 et_forest_node_t parent_node;
554 et_forest_node_t child_node;
556 et_forest_occurrence_t parent_pre_occ, parent_post_occ;
558 splay (child_node->first);
560 if (! child_node->first->left)
563 parent_pre_occ = find_rightmost_node (child_node->first->left);
564 if (parent_pre_occ->node != parent_node)
567 splay (parent_pre_occ);
568 parent_pre_occ->right->parent = 0;
570 parent_post_occ = parent_pre_occ->next;
571 splay (parent_post_occ);
573 parent_post_occ->left->parent = 0;
575 parent_pre_occ->right = parent_post_occ->right;
576 parent_pre_occ->count_right = parent_post_occ->count_right;
577 if (parent_post_occ->right)
578 parent_post_occ->right->parent = parent_pre_occ;
580 parent_pre_occ->next = parent_post_occ->next;
582 if (parent_post_occ == parent_node->last)
583 parent_node->last = parent_pre_occ;
585 pool_free (forest->occur_pool, parent_post_occ);
589 /* Return the parent of the NODE if any, NULL otherwise. */
591 et_forest_parent (forest, node)
592 et_forest_t forest ATTRIBUTE_UNUSED;
593 et_forest_node_t node;
597 if (node->first->left)
598 return find_rightmost_node (node->first->left)->node;
604 /* Return nearest common ancestor of NODE1 and NODE2.
605 Return NULL of they are in different trees. */
607 et_forest_common_ancestor (forest, node1, node2)
608 et_forest_t forest ATTRIBUTE_UNUSED;
609 et_forest_node_t node1;
610 et_forest_node_t node2;
612 int value1, value2, max_value;
613 et_forest_node_t ancestor;
618 if (! node1 || ! node2)
621 splay (node1->first);
622 splay (node2->first);
624 if (! node1->first->parent) /* The two vertices are in different trees. */
627 value2 = calculate_value (node2->first);
628 value1 = calculate_value (node1->first);
641 while (calculate_value (ancestor->last) < max_value)
643 /* Find parent node. */
644 splay (ancestor->first);
645 ancestor = find_rightmost_node (ancestor->first->left) ->node;
651 /* Return the value pointer of node set during it's creation. */
653 et_forest_node_value (forest, node)
654 et_forest_t forest ATTRIBUTE_UNUSED;
655 et_forest_node_t node;
657 /* Alloc threading NULL as a special node of the forest. */
663 /* Find all sons of NODE and store them into ARRAY allocated by the caller.
664 Return number of nodes found. */
666 et_forest_enumerate_sons (forest, node, array)
667 et_forest_t forest ATTRIBUTE_UNUSED;
668 et_forest_node_t node;
669 et_forest_node_t *array;
672 et_forest_occurrence_t occ = node->first, stop = node->last, occ1;
674 /* Parent is the rightmost node of the left successor.
675 Look for all occurrences having no right successor
676 and lookup the sons. */
682 occ1 = find_leftmost_node (occ->right);
683 if (occ1->node->first == occ1)
684 array[n++] = occ1->node;