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