1 /* ET-trees datastructure implementation.
2 Contributed by Pavel Nejedly
3 Copyright (C) 2002 Free Software Foundation, Inc.
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 2 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 COPYING.LIB. If
18 not, write to the Free Software Foundation, Inc., 59 Temple Place - Suite 330,
19 Boston, MA 02111-1307, USA.
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 "et-forest.h"
29
30 struct et_forest_occurrence;
31 typedef struct et_forest_occurrence* et_forest_occurrence_t;
32
33 /* The ET-forest type. */
34 struct et_forest
35 {
36 /* Linked list of nodes is used to destroy the structure. */
37 int nnodes;
38 };
39
40 /* Single occurrence of node in ET-forest.
41 A single node may have multiple occurrences.
42 */
43 struct et_forest_occurrence
44 {
45 /* Parent in the splay-tree. */
46 et_forest_occurrence_t parent;
47
48 /* Children in the splay-tree. */
49 et_forest_occurrence_t left, right;
50
51 /* Counts of vertices in the two splay-subtrees. */
52 int count_left, count_right;
53
54 /* Next occurrence of this node in the sequence. */
55 et_forest_occurrence_t next;
56
57 /* The node, which this occurrence is of. */
58 et_forest_node_t node;
59 };
60
61
62 /* ET-forest node. */
63 struct et_forest_node
64 {
65 et_forest_t forest;
66 void *value;
67
68 /* First and last occurrence of this node in the sequence. */
69 et_forest_occurrence_t first, last;
70 };
71
72
73 static et_forest_occurrence_t splay PARAMS ((et_forest_occurrence_t));
74 static void remove_all_occurrences PARAMS ((et_forest_node_t));
75 static inline et_forest_occurrence_t find_leftmost_node
76 PARAMS ((et_forest_occurrence_t));
77 static inline et_forest_occurrence_t find_rightmost_node
78 PARAMS ((et_forest_occurrence_t));
79 static int calculate_value PARAMS ((et_forest_occurrence_t));
80
81 /* Return leftmost node present in the tree roted by OCC. */
82 static inline et_forest_occurrence_t
find_leftmost_node(occ)83 find_leftmost_node (occ)
84 et_forest_occurrence_t occ;
85 {
86 while (occ->left)
87 occ = occ->left;
88
89 return occ;
90 }
91
92 /* Return rightmost node present in the tree roted by OCC. */
93 static inline et_forest_occurrence_t
find_rightmost_node(occ)94 find_rightmost_node (occ)
95 et_forest_occurrence_t occ;
96 {
97 while (occ->right)
98 occ = occ->right;
99 return occ;
100 }
101
102
103 /* Operation splay for splay tree structure representing ocuurences. */
104 static et_forest_occurrence_t
splay(node)105 splay (node)
106 et_forest_occurrence_t node;
107 {
108 et_forest_occurrence_t parent;
109 et_forest_occurrence_t grandparent;
110
111 while (1)
112 {
113 parent = node->parent;
114
115 if (! parent)
116 return node; /* node == root. */
117
118 grandparent = parent->parent;
119
120 if (! grandparent)
121 break;
122
123 /* Now there are four possible combinations: */
124
125 if (node == parent->left)
126 {
127 if (parent == grandparent->left)
128 {
129 et_forest_occurrence_t node1, node2;
130 int count1, count2;
131
132 node1 = node->right;
133 count1 = node->count_right;
134 node2 = parent->right;
135 count2 = parent->count_right;
136
137 grandparent->left = node2;
138 grandparent->count_left = count2;
139 if (node2)
140 node2->parent = grandparent;
141 parent->left = node1;
142 parent->count_left = count1;
143 if (node1)
144 node1->parent = parent;
145 parent->right = grandparent;
146 parent->count_right = count2 + grandparent->count_right + 1;
147 node->right = parent;
148 node->count_right = count1 + parent->count_right + 1;
149
150 node->parent = grandparent->parent;
151 parent->parent = node;
152 grandparent->parent = parent;
153
154 if (node->parent)
155 {
156 if (node->parent->left == grandparent)
157 node->parent->left = node;
158 else
159 node->parent->right = node;
160 }
161 }
162 else
163 {
164 /* parent == grandparent->right && node == parent->left*/
165 et_forest_occurrence_t node1, node2;
166 int count1, count2;
167
168 node1 = node->left;
169 count1 = node->count_left;
170 node2 = node->right;
171 count2 = node->count_right;
172
173 grandparent->right = node1;
174 grandparent->count_right = count1;
175 if (node1)
176 node1->parent = grandparent;
177 parent->left = node2;
178 parent->count_left = count2;
179 if (node2)
180 node2->parent = parent;
181 node->left = grandparent;
182 node->count_left = grandparent->count_left + count1 + 1;
183 node->right = parent;
184 node->count_right = parent->count_right + count2 + 1;
185
186 node->parent = grandparent->parent;
187 parent->parent = node;
188 grandparent->parent = node;
189
190 if (node->parent)
191 {
192 if (node->parent->left == grandparent)
193 node->parent->left = node;
194 else
195 node->parent->right = node;
196 }
197 }
198 }
199 else
200 {
201 /* node == parent->right. */
202 if (parent == grandparent->left)
203 {
204 et_forest_occurrence_t node1, node2;
205 int count1, count2;
206
207 node1 = node->left;
208 count1 = node->count_left;
209 node2 = node->right;
210 count2 = node->count_right;
211
212 parent->right = node1;
213 parent->count_right = count1;
214 if (node1)
215 node1->parent = parent;
216 grandparent->left = node2;
217 grandparent->count_left = count2;
218 if (node2)
219 node2->parent = grandparent;
220 node->left = parent;
221 node->count_left = parent->count_left + count1 + 1;
222 node->right = grandparent;
223 node->count_right = grandparent->count_right + count2 + 1;
224
225 node->parent = grandparent->parent;
226 parent->parent = node;
227 grandparent->parent = node;
228
229 if (node->parent)
230 {
231 if (node->parent->left == grandparent)
232 node->parent->left = node;
233 else
234 node->parent->right = node;
235 }
236 }
237 else
238 {
239 /* parent == grandparent->right && node == parent->right*/
240 et_forest_occurrence_t node1, node2;
241 int count1, count2;
242
243 node1 = node->left;
244 count1 = node->count_left;
245 node2 = parent->left;
246 count2 = parent->count_left;
247
248 grandparent->right = node2;
249 grandparent->count_right = count2;
250 if (node2)
251 node2->parent = grandparent;
252 parent->right = node1;
253 parent->count_right = count1;
254 if (node1)
255 node1->parent = parent;
256 parent->left = grandparent;
257 parent->count_left = count2 + grandparent->count_left + 1;
258 node->left = parent;
259 node->count_left = count1 + parent->count_left + 1;
260
261 node->parent = grandparent->parent;
262 parent->parent = node;
263 grandparent->parent = parent;
264
265 if (node->parent)
266 {
267 if (node->parent->left == grandparent)
268 node->parent->left = node;
269 else
270 node->parent->right = node;
271 }
272 }
273 }
274
275 }
276
277 /* parent == root. */
278 /* There are two possible combinations: */
279
280 if (node == parent->left)
281 {
282 et_forest_occurrence_t node1;
283 int count1;
284
285 node1 = node->right;
286 count1 = node->count_right;
287
288 parent->left = node1;
289 parent->count_left = count1;
290 if (node1)
291 node1->parent = parent;
292 node->right = parent;
293 node->count_right = parent->count_right + 1 + count1;
294 node->parent = parent->parent; /* the same as = 0; */
295 parent->parent = node;
296
297 if (node->parent)
298 {
299 if (node->parent->left == parent)
300 node->parent->left = node;
301 else
302 node->parent->right = node;
303 }
304 }
305 else
306 {
307 /* node == parent->right. */
308 et_forest_occurrence_t node1;
309 int count1;
310
311 node1 = node->left;
312 count1 = node->count_left;
313
314 parent->right = node1;
315 parent->count_right = count1;
316 if (node1)
317 node1->parent = parent;
318 node->left = parent;
319 node->count_left = parent->count_left + 1 + count1;
320 node->parent = parent->parent; /* the same as = 0; */
321 parent->parent = node;
322
323 if (node->parent)
324 {
325 if (node->parent->left == parent)
326 node->parent->left = node;
327 else
328 node->parent->right = node;
329 }
330 }
331
332 return node;
333 }
334
335 /* Remove all occurences of the given node before destroying the node. */
336 static void
remove_all_occurrences(forest_node)337 remove_all_occurrences (forest_node)
338 et_forest_node_t forest_node;
339 {
340 et_forest_occurrence_t first = forest_node->first;
341 et_forest_occurrence_t last = forest_node->last;
342 et_forest_occurrence_t node;
343
344 splay (first);
345
346 if (first->left)
347 first->left->parent = 0;
348 if (first->right)
349 first->right->parent = 0;
350
351 if (last != first)
352 {
353 splay (last);
354
355 if (last->left)
356 last->left->parent = 0;
357 if (last->right)
358 last->right->parent = 0;
359 }
360
361 if (last->right && first->left) /* actually, first->left would suffice. */
362 {
363 /* Need to join them. */
364 et_forest_occurrence_t prev_node, next_node;
365
366 prev_node = splay (find_rightmost_node (first->left));
367 next_node = splay (find_leftmost_node (last->right));
368 /* prev_node and next_node are consecutive occurencies
369 of the same node. */
370 if (prev_node->next != next_node)
371 abort ();
372
373 prev_node->right = next_node->right;
374 prev_node->count_right = next_node->count_right;
375 prev_node->next = next_node->next;
376 if (prev_node->right)
377 prev_node->right->parent = prev_node;
378
379 if (prev_node->node->last == next_node)
380 prev_node->node->last = prev_node;
381
382 free (next_node);
383 }
384
385 if (first != last)
386 {
387 node = first->next;
388
389 while (node != last)
390 {
391 et_forest_occurrence_t next_node;
392
393 splay (node);
394
395 if (node->left)
396 node->left->parent = 0;
397 if (node->right)
398 node->right->parent = 0;
399
400 next_node = node->next;
401 free (node);
402 node = next_node;
403 }
404 }
405
406 free (first);
407 if (first != last)
408 free (last);
409 }
410
411 /* Calculate ET value of the given node. */
412 static inline int
calculate_value(node)413 calculate_value (node)
414 et_forest_occurrence_t node;
415 {
416 int value = node->count_left;
417
418 while (node->parent)
419 {
420 if (node == node->parent->right)
421 value += node->parent->count_left + 1;
422
423 node = node->parent;
424 }
425
426 return value;
427 }
428
429
430
431
432 /* Create ET-forest structure. */
433 et_forest_t
et_forest_create()434 et_forest_create ()
435 {
436
437 et_forest_t forest = xmalloc (sizeof (struct et_forest));
438
439 forest->nnodes = 0;
440 return forest;
441 }
442
443
444
445 /* Deallocate the structure. */
446 void
et_forest_delete(forest)447 et_forest_delete (forest)
448 et_forest_t forest;
449 {
450 if (forest->nnodes)
451 abort ();
452
453 free (forest);
454 }
455
456 /* Create new node with VALUE and return the edge.
457 Return NULL when memory allocation failed. */
458 et_forest_node_t
et_forest_add_node(forest,value)459 et_forest_add_node (forest, value)
460 et_forest_t forest;
461 void *value;
462 {
463 /* Create node with one occurrence. */
464 et_forest_node_t node;
465 et_forest_occurrence_t occ;
466
467 node = xmalloc (sizeof (struct et_forest_node));
468 occ = xmalloc (sizeof (struct et_forest_occurrence));
469
470 node->first = node->last = occ;
471 node->value = value;
472 forest->nnodes++;
473
474 occ->node = node;
475 occ->left = occ->right = occ->parent = 0;
476 occ->next = 0;
477 occ->count_left = occ->count_right = 0;
478 return node;
479 }
480
481 /* Add new edge to the tree, return 1 if succesfull.
482 0 indicates that creation of the edge will close the cycle in graph. */
483 int
et_forest_add_edge(forest,parent_node,child_node)484 et_forest_add_edge (forest, parent_node, child_node)
485 et_forest_t forest ATTRIBUTE_UNUSED;
486 et_forest_node_t parent_node;
487 et_forest_node_t child_node;
488 {
489 et_forest_occurrence_t new_occ, parent_occ, child_occ;
490
491 if (! parent_node || ! child_node)
492 abort ();
493
494 parent_occ = parent_node->first;
495 child_occ = child_node->first;
496
497 splay (parent_occ);
498 splay (child_occ);
499
500 if (parent_occ->parent)
501 return 0; /* Both child and parent are in the same tree. */
502
503 if (child_occ->left)
504 abort (); /* child must be root of its containing tree. */
505
506 new_occ = xmalloc (sizeof (struct et_forest_occurrence));
507
508 new_occ->node = parent_node;
509 new_occ->left = child_occ;
510 new_occ->count_left = child_occ->count_right + 1; /* count_left is 0. */
511 new_occ->right = parent_occ->right;
512 new_occ->count_right = parent_occ->count_right;
513 new_occ->parent = parent_occ;
514 new_occ->next = parent_occ->next;
515 child_occ->parent = new_occ;
516 parent_occ->right = new_occ;
517 parent_occ->count_right = new_occ->count_left + new_occ->count_right + 1;
518 parent_occ->next = new_occ;
519 if (new_occ->right)
520 new_occ->right->parent = new_occ;
521
522 if (parent_node->last == parent_occ)
523 parent_node->last = new_occ;
524 return 1;
525 }
526
527 /* Remove NODE from the tree and all connected edges. */
528 void
et_forest_remove_node(forest,node)529 et_forest_remove_node (forest, node)
530 et_forest_t forest;
531 et_forest_node_t node;
532 {
533 remove_all_occurrences (node);
534 forest->nnodes--;
535
536 free (node);
537 }
538
539 /* Remove edge from the tree, return 1 if sucesfull,
540 0 indicates nonexisting edge. */
541 int
et_forest_remove_edge(forest,parent_node,child_node)542 et_forest_remove_edge (forest, parent_node, child_node)
543 et_forest_t forest ATTRIBUTE_UNUSED;
544 et_forest_node_t parent_node;
545 et_forest_node_t child_node;
546 {
547 et_forest_occurrence_t parent_pre_occ, parent_post_occ;
548
549 splay (child_node->first);
550
551 if (! child_node->first->left)
552 return 0;
553
554 parent_pre_occ = find_rightmost_node (child_node->first->left);
555 if (parent_pre_occ->node != parent_node)
556 abort ();
557
558 splay (parent_pre_occ);
559 parent_pre_occ->right->parent = 0;
560
561 parent_post_occ = parent_pre_occ->next;
562 splay (parent_post_occ);
563
564 parent_post_occ->left->parent = 0;
565
566 parent_pre_occ->right = parent_post_occ->right;
567 parent_pre_occ->count_right = parent_post_occ->count_right;
568 if (parent_post_occ->right)
569 parent_post_occ->right->parent = parent_pre_occ;
570
571 parent_pre_occ->next = parent_post_occ->next;
572
573 if (parent_post_occ == parent_node->last)
574 parent_node->last = parent_pre_occ;
575
576 free (parent_post_occ);
577 return 1;
578 }
579
580 /* Return the parent of the NODE if any, NULL otherwise. */
581 et_forest_node_t
et_forest_parent(forest,node)582 et_forest_parent (forest, node)
583 et_forest_t forest ATTRIBUTE_UNUSED;
584 et_forest_node_t node;
585 {
586 splay (node->first);
587
588 if (node->first->left)
589 return find_rightmost_node (node->first->left)->node;
590 else
591 return 0;
592 }
593
594
595 /* Return nearest common ancestor of NODE1 and NODE2.
596 Return NULL of they are in different trees. */
597 et_forest_node_t
et_forest_common_ancestor(forest,node1,node2)598 et_forest_common_ancestor (forest, node1, node2)
599 et_forest_t forest ATTRIBUTE_UNUSED;
600 et_forest_node_t node1;
601 et_forest_node_t node2;
602 {
603 int value1, value2, max_value;
604 et_forest_node_t ancestor;
605
606 if (node1 == node2)
607 return node1;
608
609 if (! node1 || ! node2)
610 abort ();
611
612 splay (node1->first);
613 splay (node2->first);
614
615 if (! node1->first->parent) /* The two vertices are in different trees. */
616 return 0;
617
618 value2 = calculate_value (node2->first);
619 value1 = calculate_value (node1->first);
620
621 if (value1 < value2)
622 {
623 ancestor = node1;
624 max_value = value2;
625 }
626 else
627 {
628 ancestor = node2;
629 max_value = value1;
630 }
631
632 while (calculate_value (ancestor->last) < max_value)
633 {
634 /* Find parent node. */
635 splay (ancestor->first);
636 ancestor = find_rightmost_node (ancestor->first->left) ->node;
637 }
638
639 return ancestor;
640 }
641
642 /* Return the value pointer of node set during it's creation. */
643 void *
et_forest_node_value(forest,node)644 et_forest_node_value (forest, node)
645 et_forest_t forest ATTRIBUTE_UNUSED;
646 et_forest_node_t node;
647 {
648 /* Alloc threading NULL as a special node of the forest. */
649 if (!node)
650 return NULL;
651 return node->value;
652 }
653
654 /* Find all sons of NODE and store them into ARRAY allocated by the caller.
655 Return number of nodes found. */
656 int
et_forest_enumerate_sons(forest,node,array)657 et_forest_enumerate_sons (forest, node, array)
658 et_forest_t forest ATTRIBUTE_UNUSED;
659 et_forest_node_t node;
660 et_forest_node_t *array;
661 {
662 int n = 0;
663 et_forest_occurrence_t occ = node->first, stop = node->last, occ1;
664
665 /* Parent is the rightmost node of the left successor.
666 Look for all occurences having no right succesor
667 and lookup the sons. */
668 while (occ != stop)
669 {
670 splay (occ);
671 if (occ->right)
672 {
673 occ1 = find_leftmost_node (occ->right);
674 if (occ1->node->first == occ1)
675 array[n++] = occ1->node;
676 }
677 occ = occ->next;
678 }
679 return n;
680 }
681