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