|
0
|
1 /* ET-trees data structure implementation.
|
|
|
2 Contributed by Pavel Nejedly
|
|
|
3 Copyright (C) 2002, 2003, 2004, 2005, 2007, 2008 Free Software
|
|
|
4 Foundation, Inc.
|
|
|
5
|
|
|
6 This file is part of the libiberty library.
|
|
|
7 Libiberty is free software; you can redistribute it and/or
|
|
|
8 modify it under the terms of the GNU Library General Public
|
|
|
9 License as published by the Free Software Foundation; either
|
|
|
10 version 3 of the License, or (at your option) any later version.
|
|
|
11
|
|
|
12 Libiberty is distributed in the hope that it will be useful,
|
|
|
13 but WITHOUT ANY WARRANTY; without even the implied warranty of
|
|
|
14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
|
|
|
15 Library General Public License for more details.
|
|
|
16
|
|
|
17 You should have received a copy of the GNU Library General Public
|
|
|
18 License along with libiberty; see the file COPYING3. If not see
|
|
|
19 <http://www.gnu.org/licenses/>.
|
|
|
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 "coretypes.h"
|
|
|
29 #include "tm.h"
|
|
|
30 #include "et-forest.h"
|
|
|
31 #include "alloc-pool.h"
|
|
|
32
|
|
|
33 /* We do not enable this with ENABLE_CHECKING, since it is awfully slow. */
|
|
|
34 #undef DEBUG_ET
|
|
|
35
|
|
|
36 #ifdef DEBUG_ET
|
|
|
37 #include "basic-block.h"
|
|
|
38 #endif
|
|
|
39
|
|
|
40 /* The occurrence of a node in the et tree. */
|
|
|
41 struct et_occ
|
|
|
42 {
|
|
|
43 struct et_node *of; /* The node. */
|
|
|
44
|
|
|
45 struct et_occ *parent; /* Parent in the splay-tree. */
|
|
|
46 struct et_occ *prev; /* Left son in the splay-tree. */
|
|
|
47 struct et_occ *next; /* Right son in the splay-tree. */
|
|
|
48
|
|
|
49 int depth; /* The depth of the node is the sum of depth
|
|
|
50 fields on the path to the root. */
|
|
|
51 int min; /* The minimum value of the depth in the subtree
|
|
|
52 is obtained by adding sum of depth fields
|
|
|
53 on the path to the root. */
|
|
|
54 struct et_occ *min_occ; /* The occurrence in the subtree with the minimal
|
|
|
55 depth. */
|
|
|
56 };
|
|
|
57
|
|
|
58 static alloc_pool et_nodes;
|
|
|
59 static alloc_pool et_occurrences;
|
|
|
60
|
|
|
61 /* Changes depth of OCC to D. */
|
|
|
62
|
|
|
63 static inline void
|
|
|
64 set_depth (struct et_occ *occ, int d)
|
|
|
65 {
|
|
|
66 if (!occ)
|
|
|
67 return;
|
|
|
68
|
|
|
69 occ->min += d - occ->depth;
|
|
|
70 occ->depth = d;
|
|
|
71 }
|
|
|
72
|
|
|
73 /* Adds D to the depth of OCC. */
|
|
|
74
|
|
|
75 static inline void
|
|
|
76 set_depth_add (struct et_occ *occ, int d)
|
|
|
77 {
|
|
|
78 if (!occ)
|
|
|
79 return;
|
|
|
80
|
|
|
81 occ->min += d;
|
|
|
82 occ->depth += d;
|
|
|
83 }
|
|
|
84
|
|
|
85 /* Sets prev field of OCC to P. */
|
|
|
86
|
|
|
87 static inline void
|
|
|
88 set_prev (struct et_occ *occ, struct et_occ *t)
|
|
|
89 {
|
|
|
90 #ifdef DEBUG_ET
|
|
|
91 gcc_assert (occ != t);
|
|
|
92 #endif
|
|
|
93
|
|
|
94 occ->prev = t;
|
|
|
95 if (t)
|
|
|
96 t->parent = occ;
|
|
|
97 }
|
|
|
98
|
|
|
99 /* Sets next field of OCC to P. */
|
|
|
100
|
|
|
101 static inline void
|
|
|
102 set_next (struct et_occ *occ, struct et_occ *t)
|
|
|
103 {
|
|
|
104 #ifdef DEBUG_ET
|
|
|
105 gcc_assert (occ != t);
|
|
|
106 #endif
|
|
|
107
|
|
|
108 occ->next = t;
|
|
|
109 if (t)
|
|
|
110 t->parent = occ;
|
|
|
111 }
|
|
|
112
|
|
|
113 /* Recompute minimum for occurrence OCC. */
|
|
|
114
|
|
|
115 static inline void
|
|
|
116 et_recomp_min (struct et_occ *occ)
|
|
|
117 {
|
|
|
118 struct et_occ *mson = occ->prev;
|
|
|
119
|
|
|
120 if (!mson
|
|
|
121 || (occ->next
|
|
|
122 && mson->min > occ->next->min))
|
|
|
123 mson = occ->next;
|
|
|
124
|
|
|
125 if (mson && mson->min < 0)
|
|
|
126 {
|
|
|
127 occ->min = mson->min + occ->depth;
|
|
|
128 occ->min_occ = mson->min_occ;
|
|
|
129 }
|
|
|
130 else
|
|
|
131 {
|
|
|
132 occ->min = occ->depth;
|
|
|
133 occ->min_occ = occ;
|
|
|
134 }
|
|
|
135 }
|
|
|
136
|
|
|
137 #ifdef DEBUG_ET
|
|
|
138 /* Checks whether neighborhood of OCC seems sane. */
|
|
|
139
|
|
|
140 static void
|
|
|
141 et_check_occ_sanity (struct et_occ *occ)
|
|
|
142 {
|
|
|
143 if (!occ)
|
|
|
144 return;
|
|
|
145
|
|
|
146 gcc_assert (occ->parent != occ);
|
|
|
147 gcc_assert (occ->prev != occ);
|
|
|
148 gcc_assert (occ->next != occ);
|
|
|
149 gcc_assert (!occ->next || occ->next != occ->prev);
|
|
|
150
|
|
|
151 if (occ->next)
|
|
|
152 {
|
|
|
153 gcc_assert (occ->next != occ->parent);
|
|
|
154 gcc_assert (occ->next->parent == occ);
|
|
|
155 }
|
|
|
156
|
|
|
157 if (occ->prev)
|
|
|
158 {
|
|
|
159 gcc_assert (occ->prev != occ->parent);
|
|
|
160 gcc_assert (occ->prev->parent == occ);
|
|
|
161 }
|
|
|
162
|
|
|
163 gcc_assert (!occ->parent
|
|
|
164 || occ->parent->prev == occ
|
|
|
165 || occ->parent->next == occ);
|
|
|
166 }
|
|
|
167
|
|
|
168 /* Checks whether tree rooted at OCC is sane. */
|
|
|
169
|
|
|
170 static void
|
|
|
171 et_check_sanity (struct et_occ *occ)
|
|
|
172 {
|
|
|
173 et_check_occ_sanity (occ);
|
|
|
174 if (occ->prev)
|
|
|
175 et_check_sanity (occ->prev);
|
|
|
176 if (occ->next)
|
|
|
177 et_check_sanity (occ->next);
|
|
|
178 }
|
|
|
179
|
|
|
180 /* Checks whether tree containing OCC is sane. */
|
|
|
181
|
|
|
182 static void
|
|
|
183 et_check_tree_sanity (struct et_occ *occ)
|
|
|
184 {
|
|
|
185 while (occ->parent)
|
|
|
186 occ = occ->parent;
|
|
|
187
|
|
|
188 et_check_sanity (occ);
|
|
|
189 }
|
|
|
190
|
|
|
191 /* For recording the paths. */
|
|
|
192
|
|
|
193 /* An ad-hoc constant; if the function has more blocks, this won't work,
|
|
|
194 but since it is used for debugging only, it does not matter. */
|
|
|
195 #define MAX_NODES 100000
|
|
|
196
|
|
|
197 static int len;
|
|
|
198 static void *datas[MAX_NODES];
|
|
|
199 static int depths[MAX_NODES];
|
|
|
200
|
|
|
201 /* Records the path represented by OCC, with depth incremented by DEPTH. */
|
|
|
202
|
|
|
203 static int
|
|
|
204 record_path_before_1 (struct et_occ *occ, int depth)
|
|
|
205 {
|
|
|
206 int mn, m;
|
|
|
207
|
|
|
208 depth += occ->depth;
|
|
|
209 mn = depth;
|
|
|
210
|
|
|
211 if (occ->prev)
|
|
|
212 {
|
|
|
213 m = record_path_before_1 (occ->prev, depth);
|
|
|
214 if (m < mn)
|
|
|
215 mn = m;
|
|
|
216 }
|
|
|
217
|
|
|
218 fprintf (stderr, "%d (%d); ", ((basic_block) occ->of->data)->index, depth);
|
|
|
219
|
|
|
220 gcc_assert (len < MAX_NODES);
|
|
|
221
|
|
|
222 depths[len] = depth;
|
|
|
223 datas[len] = occ->of;
|
|
|
224 len++;
|
|
|
225
|
|
|
226 if (occ->next)
|
|
|
227 {
|
|
|
228 m = record_path_before_1 (occ->next, depth);
|
|
|
229 if (m < mn)
|
|
|
230 mn = m;
|
|
|
231 }
|
|
|
232
|
|
|
233 gcc_assert (mn == occ->min + depth - occ->depth);
|
|
|
234
|
|
|
235 return mn;
|
|
|
236 }
|
|
|
237
|
|
|
238 /* Records the path represented by a tree containing OCC. */
|
|
|
239
|
|
|
240 static void
|
|
|
241 record_path_before (struct et_occ *occ)
|
|
|
242 {
|
|
|
243 while (occ->parent)
|
|
|
244 occ = occ->parent;
|
|
|
245
|
|
|
246 len = 0;
|
|
|
247 record_path_before_1 (occ, 0);
|
|
|
248 fprintf (stderr, "\n");
|
|
|
249 }
|
|
|
250
|
|
|
251 /* Checks whether the path represented by OCC, with depth incremented by DEPTH,
|
|
|
252 was not changed since the last recording. */
|
|
|
253
|
|
|
254 static int
|
|
|
255 check_path_after_1 (struct et_occ *occ, int depth)
|
|
|
256 {
|
|
|
257 int mn, m;
|
|
|
258
|
|
|
259 depth += occ->depth;
|
|
|
260 mn = depth;
|
|
|
261
|
|
|
262 if (occ->next)
|
|
|
263 {
|
|
|
264 m = check_path_after_1 (occ->next, depth);
|
|
|
265 if (m < mn)
|
|
|
266 mn = m;
|
|
|
267 }
|
|
|
268
|
|
|
269 len--;
|
|
|
270 gcc_assert (depths[len] == depth && datas[len] == occ->of);
|
|
|
271
|
|
|
272 if (occ->prev)
|
|
|
273 {
|
|
|
274 m = check_path_after_1 (occ->prev, depth);
|
|
|
275 if (m < mn)
|
|
|
276 mn = m;
|
|
|
277 }
|
|
|
278
|
|
|
279 gcc_assert (mn == occ->min + depth - occ->depth);
|
|
|
280
|
|
|
281 return mn;
|
|
|
282 }
|
|
|
283
|
|
|
284 /* Checks whether the path represented by a tree containing OCC was
|
|
|
285 not changed since the last recording. */
|
|
|
286
|
|
|
287 static void
|
|
|
288 check_path_after (struct et_occ *occ)
|
|
|
289 {
|
|
|
290 while (occ->parent)
|
|
|
291 occ = occ->parent;
|
|
|
292
|
|
|
293 check_path_after_1 (occ, 0);
|
|
|
294 gcc_assert (!len);
|
|
|
295 }
|
|
|
296
|
|
|
297 #endif
|
|
|
298
|
|
|
299 /* Splay the occurrence OCC to the root of the tree. */
|
|
|
300
|
|
|
301 static void
|
|
|
302 et_splay (struct et_occ *occ)
|
|
|
303 {
|
|
|
304 struct et_occ *f, *gf, *ggf;
|
|
|
305 int occ_depth, f_depth, gf_depth;
|
|
|
306
|
|
|
307 #ifdef DEBUG_ET
|
|
|
308 record_path_before (occ);
|
|
|
309 et_check_tree_sanity (occ);
|
|
|
310 #endif
|
|
|
311
|
|
|
312 while (occ->parent)
|
|
|
313 {
|
|
|
314 occ_depth = occ->depth;
|
|
|
315
|
|
|
316 f = occ->parent;
|
|
|
317 f_depth = f->depth;
|
|
|
318
|
|
|
319 gf = f->parent;
|
|
|
320
|
|
|
321 if (!gf)
|
|
|
322 {
|
|
|
323 set_depth_add (occ, f_depth);
|
|
|
324 occ->min_occ = f->min_occ;
|
|
|
325 occ->min = f->min;
|
|
|
326
|
|
|
327 if (f->prev == occ)
|
|
|
328 {
|
|
|
329 /* zig */
|
|
|
330 set_prev (f, occ->next);
|
|
|
331 set_next (occ, f);
|
|
|
332 set_depth_add (f->prev, occ_depth);
|
|
|
333 }
|
|
|
334 else
|
|
|
335 {
|
|
|
336 /* zag */
|
|
|
337 set_next (f, occ->prev);
|
|
|
338 set_prev (occ, f);
|
|
|
339 set_depth_add (f->next, occ_depth);
|
|
|
340 }
|
|
|
341 set_depth (f, -occ_depth);
|
|
|
342 occ->parent = NULL;
|
|
|
343
|
|
|
344 et_recomp_min (f);
|
|
|
345 #ifdef DEBUG_ET
|
|
|
346 et_check_tree_sanity (occ);
|
|
|
347 check_path_after (occ);
|
|
|
348 #endif
|
|
|
349 return;
|
|
|
350 }
|
|
|
351
|
|
|
352 gf_depth = gf->depth;
|
|
|
353
|
|
|
354 set_depth_add (occ, f_depth + gf_depth);
|
|
|
355 occ->min_occ = gf->min_occ;
|
|
|
356 occ->min = gf->min;
|
|
|
357
|
|
|
358 ggf = gf->parent;
|
|
|
359
|
|
|
360 if (gf->prev == f)
|
|
|
361 {
|
|
|
362 if (f->prev == occ)
|
|
|
363 {
|
|
|
364 /* zig zig */
|
|
|
365 set_prev (gf, f->next);
|
|
|
366 set_prev (f, occ->next);
|
|
|
367 set_next (occ, f);
|
|
|
368 set_next (f, gf);
|
|
|
369
|
|
|
370 set_depth (f, -occ_depth);
|
|
|
371 set_depth_add (f->prev, occ_depth);
|
|
|
372 set_depth (gf, -f_depth);
|
|
|
373 set_depth_add (gf->prev, f_depth);
|
|
|
374 }
|
|
|
375 else
|
|
|
376 {
|
|
|
377 /* zag zig */
|
|
|
378 set_prev (gf, occ->next);
|
|
|
379 set_next (f, occ->prev);
|
|
|
380 set_prev (occ, f);
|
|
|
381 set_next (occ, gf);
|
|
|
382
|
|
|
383 set_depth (f, -occ_depth);
|
|
|
384 set_depth_add (f->next, occ_depth);
|
|
|
385 set_depth (gf, -occ_depth - f_depth);
|
|
|
386 set_depth_add (gf->prev, occ_depth + f_depth);
|
|
|
387 }
|
|
|
388 }
|
|
|
389 else
|
|
|
390 {
|
|
|
391 if (f->prev == occ)
|
|
|
392 {
|
|
|
393 /* zig zag */
|
|
|
394 set_next (gf, occ->prev);
|
|
|
395 set_prev (f, occ->next);
|
|
|
396 set_prev (occ, gf);
|
|
|
397 set_next (occ, f);
|
|
|
398
|
|
|
399 set_depth (f, -occ_depth);
|
|
|
400 set_depth_add (f->prev, occ_depth);
|
|
|
401 set_depth (gf, -occ_depth - f_depth);
|
|
|
402 set_depth_add (gf->next, occ_depth + f_depth);
|
|
|
403 }
|
|
|
404 else
|
|
|
405 {
|
|
|
406 /* zag zag */
|
|
|
407 set_next (gf, f->prev);
|
|
|
408 set_next (f, occ->prev);
|
|
|
409 set_prev (occ, f);
|
|
|
410 set_prev (f, gf);
|
|
|
411
|
|
|
412 set_depth (f, -occ_depth);
|
|
|
413 set_depth_add (f->next, occ_depth);
|
|
|
414 set_depth (gf, -f_depth);
|
|
|
415 set_depth_add (gf->next, f_depth);
|
|
|
416 }
|
|
|
417 }
|
|
|
418
|
|
|
419 occ->parent = ggf;
|
|
|
420 if (ggf)
|
|
|
421 {
|
|
|
422 if (ggf->prev == gf)
|
|
|
423 ggf->prev = occ;
|
|
|
424 else
|
|
|
425 ggf->next = occ;
|
|
|
426 }
|
|
|
427
|
|
|
428 et_recomp_min (gf);
|
|
|
429 et_recomp_min (f);
|
|
|
430 #ifdef DEBUG_ET
|
|
|
431 et_check_tree_sanity (occ);
|
|
|
432 #endif
|
|
|
433 }
|
|
|
434
|
|
|
435 #ifdef DEBUG_ET
|
|
|
436 et_check_sanity (occ);
|
|
|
437 check_path_after (occ);
|
|
|
438 #endif
|
|
|
439 }
|
|
|
440
|
|
|
441 /* Create a new et tree occurrence of NODE. */
|
|
|
442
|
|
|
443 static struct et_occ *
|
|
|
444 et_new_occ (struct et_node *node)
|
|
|
445 {
|
|
|
446 struct et_occ *nw;
|
|
|
447
|
|
|
448 if (!et_occurrences)
|
|
|
449 et_occurrences = create_alloc_pool ("et_occ pool", sizeof (struct et_occ), 300);
|
|
|
450 nw = (struct et_occ *) pool_alloc (et_occurrences);
|
|
|
451
|
|
|
452 nw->of = node;
|
|
|
453 nw->parent = NULL;
|
|
|
454 nw->prev = NULL;
|
|
|
455 nw->next = NULL;
|
|
|
456
|
|
|
457 nw->depth = 0;
|
|
|
458 nw->min_occ = nw;
|
|
|
459 nw->min = 0;
|
|
|
460
|
|
|
461 return nw;
|
|
|
462 }
|
|
|
463
|
|
|
464 /* Create a new et tree containing DATA. */
|
|
|
465
|
|
|
466 struct et_node *
|
|
|
467 et_new_tree (void *data)
|
|
|
468 {
|
|
|
469 struct et_node *nw;
|
|
|
470
|
|
|
471 if (!et_nodes)
|
|
|
472 et_nodes = create_alloc_pool ("et_node pool", sizeof (struct et_node), 300);
|
|
|
473 nw = (struct et_node *) pool_alloc (et_nodes);
|
|
|
474
|
|
|
475 nw->data = data;
|
|
|
476 nw->father = NULL;
|
|
|
477 nw->left = NULL;
|
|
|
478 nw->right = NULL;
|
|
|
479 nw->son = NULL;
|
|
|
480
|
|
|
481 nw->rightmost_occ = et_new_occ (nw);
|
|
|
482 nw->parent_occ = NULL;
|
|
|
483
|
|
|
484 return nw;
|
|
|
485 }
|
|
|
486
|
|
|
487 /* Releases et tree T. */
|
|
|
488
|
|
|
489 void
|
|
|
490 et_free_tree (struct et_node *t)
|
|
|
491 {
|
|
|
492 while (t->son)
|
|
|
493 et_split (t->son);
|
|
|
494
|
|
|
495 if (t->father)
|
|
|
496 et_split (t);
|
|
|
497
|
|
|
498 pool_free (et_occurrences, t->rightmost_occ);
|
|
|
499 pool_free (et_nodes, t);
|
|
|
500 }
|
|
|
501
|
|
|
502 /* Releases et tree T without maintaining other nodes. */
|
|
|
503
|
|
|
504 void
|
|
|
505 et_free_tree_force (struct et_node *t)
|
|
|
506 {
|
|
|
507 pool_free (et_occurrences, t->rightmost_occ);
|
|
|
508 if (t->parent_occ)
|
|
|
509 pool_free (et_occurrences, t->parent_occ);
|
|
|
510 pool_free (et_nodes, t);
|
|
|
511 }
|
|
|
512
|
|
|
513 /* Release the alloc pools, if they are empty. */
|
|
|
514
|
|
|
515 void
|
|
|
516 et_free_pools (void)
|
|
|
517 {
|
|
|
518 free_alloc_pool_if_empty (&et_occurrences);
|
|
|
519 free_alloc_pool_if_empty (&et_nodes);
|
|
|
520 }
|
|
|
521
|
|
|
522 /* Sets father of et tree T to FATHER. */
|
|
|
523
|
|
|
524 void
|
|
|
525 et_set_father (struct et_node *t, struct et_node *father)
|
|
|
526 {
|
|
|
527 struct et_node *left, *right;
|
|
|
528 struct et_occ *rmost, *left_part, *new_f_occ, *p;
|
|
|
529
|
|
|
530 /* Update the path represented in the splay tree. */
|
|
|
531 new_f_occ = et_new_occ (father);
|
|
|
532
|
|
|
533 rmost = father->rightmost_occ;
|
|
|
534 et_splay (rmost);
|
|
|
535
|
|
|
536 left_part = rmost->prev;
|
|
|
537
|
|
|
538 p = t->rightmost_occ;
|
|
|
539 et_splay (p);
|
|
|
540
|
|
|
541 set_prev (new_f_occ, left_part);
|
|
|
542 set_next (new_f_occ, p);
|
|
|
543
|
|
|
544 p->depth++;
|
|
|
545 p->min++;
|
|
|
546 et_recomp_min (new_f_occ);
|
|
|
547
|
|
|
548 set_prev (rmost, new_f_occ);
|
|
|
549
|
|
|
550 if (new_f_occ->min + rmost->depth < rmost->min)
|
|
|
551 {
|
|
|
552 rmost->min = new_f_occ->min + rmost->depth;
|
|
|
553 rmost->min_occ = new_f_occ->min_occ;
|
|
|
554 }
|
|
|
555
|
|
|
556 t->parent_occ = new_f_occ;
|
|
|
557
|
|
|
558 /* Update the tree. */
|
|
|
559 t->father = father;
|
|
|
560 right = father->son;
|
|
|
561 if (right)
|
|
|
562 left = right->left;
|
|
|
563 else
|
|
|
564 left = right = t;
|
|
|
565
|
|
|
566 left->right = t;
|
|
|
567 right->left = t;
|
|
|
568 t->left = left;
|
|
|
569 t->right = right;
|
|
|
570
|
|
|
571 father->son = t;
|
|
|
572
|
|
|
573 #ifdef DEBUG_ET
|
|
|
574 et_check_tree_sanity (rmost);
|
|
|
575 record_path_before (rmost);
|
|
|
576 #endif
|
|
|
577 }
|
|
|
578
|
|
|
579 /* Splits the edge from T to its father. */
|
|
|
580
|
|
|
581 void
|
|
|
582 et_split (struct et_node *t)
|
|
|
583 {
|
|
|
584 struct et_node *father = t->father;
|
|
|
585 struct et_occ *r, *l, *rmost, *p_occ;
|
|
|
586
|
|
|
587 /* Update the path represented by the splay tree. */
|
|
|
588 rmost = t->rightmost_occ;
|
|
|
589 et_splay (rmost);
|
|
|
590
|
|
|
591 for (r = rmost->next; r->prev; r = r->prev)
|
|
|
592 continue;
|
|
|
593 et_splay (r);
|
|
|
594
|
|
|
595 r->prev->parent = NULL;
|
|
|
596 p_occ = t->parent_occ;
|
|
|
597 et_splay (p_occ);
|
|
|
598 t->parent_occ = NULL;
|
|
|
599
|
|
|
600 l = p_occ->prev;
|
|
|
601 p_occ->next->parent = NULL;
|
|
|
602
|
|
|
603 set_prev (r, l);
|
|
|
604
|
|
|
605 et_recomp_min (r);
|
|
|
606
|
|
|
607 et_splay (rmost);
|
|
|
608 rmost->depth = 0;
|
|
|
609 rmost->min = 0;
|
|
|
610
|
|
|
611 pool_free (et_occurrences, p_occ);
|
|
|
612
|
|
|
613 /* Update the tree. */
|
|
|
614 if (father->son == t)
|
|
|
615 father->son = t->right;
|
|
|
616 if (father->son == t)
|
|
|
617 father->son = NULL;
|
|
|
618 else
|
|
|
619 {
|
|
|
620 t->left->right = t->right;
|
|
|
621 t->right->left = t->left;
|
|
|
622 }
|
|
|
623 t->left = t->right = NULL;
|
|
|
624 t->father = NULL;
|
|
|
625
|
|
|
626 #ifdef DEBUG_ET
|
|
|
627 et_check_tree_sanity (rmost);
|
|
|
628 record_path_before (rmost);
|
|
|
629
|
|
|
630 et_check_tree_sanity (r);
|
|
|
631 record_path_before (r);
|
|
|
632 #endif
|
|
|
633 }
|
|
|
634
|
|
|
635 /* Finds the nearest common ancestor of the nodes N1 and N2. */
|
|
|
636
|
|
|
637 struct et_node *
|
|
|
638 et_nca (struct et_node *n1, struct et_node *n2)
|
|
|
639 {
|
|
|
640 struct et_occ *o1 = n1->rightmost_occ, *o2 = n2->rightmost_occ, *om;
|
|
|
641 struct et_occ *l, *r, *ret;
|
|
|
642 int mn;
|
|
|
643
|
|
|
644 if (n1 == n2)
|
|
|
645 return n1;
|
|
|
646
|
|
|
647 et_splay (o1);
|
|
|
648 l = o1->prev;
|
|
|
649 r = o1->next;
|
|
|
650 if (l)
|
|
|
651 l->parent = NULL;
|
|
|
652 if (r)
|
|
|
653 r->parent = NULL;
|
|
|
654 et_splay (o2);
|
|
|
655
|
|
|
656 if (l == o2 || (l && l->parent != NULL))
|
|
|
657 {
|
|
|
658 ret = o2->next;
|
|
|
659
|
|
|
660 set_prev (o1, o2);
|
|
|
661 if (r)
|
|
|
662 r->parent = o1;
|
|
|
663 }
|
|
|
664 else
|
|
|
665 {
|
|
|
666 ret = o2->prev;
|
|
|
667
|
|
|
668 set_next (o1, o2);
|
|
|
669 if (l)
|
|
|
670 l->parent = o1;
|
|
|
671 }
|
|
|
672
|
|
|
673 if (0 < o2->depth)
|
|
|
674 {
|
|
|
675 om = o1;
|
|
|
676 mn = o1->depth;
|
|
|
677 }
|
|
|
678 else
|
|
|
679 {
|
|
|
680 om = o2;
|
|
|
681 mn = o2->depth + o1->depth;
|
|
|
682 }
|
|
|
683
|
|
|
684 #ifdef DEBUG_ET
|
|
|
685 et_check_tree_sanity (o2);
|
|
|
686 #endif
|
|
|
687
|
|
|
688 if (ret && ret->min + o1->depth + o2->depth < mn)
|
|
|
689 return ret->min_occ->of;
|
|
|
690 else
|
|
|
691 return om->of;
|
|
|
692 }
|
|
|
693
|
|
|
694 /* Checks whether the node UP is an ancestor of the node DOWN. */
|
|
|
695
|
|
|
696 bool
|
|
|
697 et_below (struct et_node *down, struct et_node *up)
|
|
|
698 {
|
|
|
699 struct et_occ *u = up->rightmost_occ, *d = down->rightmost_occ;
|
|
|
700 struct et_occ *l, *r;
|
|
|
701
|
|
|
702 if (up == down)
|
|
|
703 return true;
|
|
|
704
|
|
|
705 et_splay (u);
|
|
|
706 l = u->prev;
|
|
|
707 r = u->next;
|
|
|
708
|
|
|
709 if (!l)
|
|
|
710 return false;
|
|
|
711
|
|
|
712 l->parent = NULL;
|
|
|
713
|
|
|
714 if (r)
|
|
|
715 r->parent = NULL;
|
|
|
716
|
|
|
717 et_splay (d);
|
|
|
718
|
|
|
719 if (l == d || l->parent != NULL)
|
|
|
720 {
|
|
|
721 if (r)
|
|
|
722 r->parent = u;
|
|
|
723 set_prev (u, d);
|
|
|
724 #ifdef DEBUG_ET
|
|
|
725 et_check_tree_sanity (u);
|
|
|
726 #endif
|
|
|
727 }
|
|
|
728 else
|
|
|
729 {
|
|
|
730 l->parent = u;
|
|
|
731
|
|
|
732 /* In case O1 and O2 are in two different trees, we must just restore the
|
|
|
733 original state. */
|
|
|
734 if (r && r->parent != NULL)
|
|
|
735 set_next (u, d);
|
|
|
736 else
|
|
|
737 set_next (u, r);
|
|
|
738
|
|
|
739 #ifdef DEBUG_ET
|
|
|
740 et_check_tree_sanity (u);
|
|
|
741 #endif
|
|
|
742 return false;
|
|
|
743 }
|
|
|
744
|
|
|
745 if (0 >= d->depth)
|
|
|
746 return false;
|
|
|
747
|
|
|
748 return !d->next || d->next->min + d->depth >= 0;
|
|
|
749 }
|
|
|
750
|
|
|
751 /* Returns the root of the tree that contains NODE. */
|
|
|
752
|
|
|
753 struct et_node *
|
|
|
754 et_root (struct et_node *node)
|
|
|
755 {
|
|
|
756 struct et_occ *occ = node->rightmost_occ, *r;
|
|
|
757
|
|
|
758 /* The root of the tree corresponds to the rightmost occurrence in the
|
|
|
759 represented path. */
|
|
|
760 et_splay (occ);
|
|
|
761 for (r = occ; r->next; r = r->next)
|
|
|
762 continue;
|
|
|
763 et_splay (r);
|
|
|
764
|
|
|
765 return r->of;
|
|
|
766 }
|
