1 /* PSPP - a program for statistical analysis.
2 Copyright (C) 2007 Free Software Foundation, Inc.
4 This program is free software: you can redistribute it and/or modify
5 it under the terms of the GNU General Public License as published by
6 the Free Software Foundation, either version 3 of the License, or
7 (at your option) any later version.
9 This program is distributed in the hope that it will be useful,
10 but WITHOUT ANY WARRANTY; without even the implied warranty of
11 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
12 GNU General Public License for more details.
14 You should have received a copy of the GNU General Public License
15 along with this program. If not, see <http://www.gnu.org/licenses/>. */
17 /* Augmented binary tree (ABT) data structure. */
19 /* These library routines have no external dependencies other
20 than the standard C library.
22 If you add routines in this file, please add a corresponding
23 test to abt-test.c. This test program should achieve 100%
24 coverage of lines and branches in this code, as reported by
31 #include <libpspp/abt.h>
35 #include <libpspp/assertion.h>
37 static struct abt_node **down_link (struct abt *, struct abt_node *);
38 static struct abt_node *skew (struct abt *, struct abt_node *);
39 static struct abt_node *split (struct abt *, struct abt_node *);
41 /* Initializes ABT as an empty ABT that uses COMPARE and
42 REAUGMENT functions, passing in AUX as auxiliary data.
44 The comparison function is optional. If it is null, this
45 indicates that the tree is being used for its augmentations
46 only. ABT functions that compare nodes may not be used with
47 trees that lack comparison functions; contrariwise, other
48 functions that could disrupt the ordering of a tree may not be
49 used if a comparison function is specified. Refer to
50 individual function descriptions for details. */
52 abt_init (struct abt *abt,
53 abt_compare_func *compare,
54 abt_reaugment_func *reaugment,
57 assert (reaugment != NULL);
59 abt->compare = compare;
60 abt->reaugment = reaugment;
64 /* Inserts the given NODE into ABT.
65 Returns a null pointer if successful.
66 Returns the existing node already in ABT equal to NODE, on
68 This function may be used only if ABT has a comparison
71 abt_insert (struct abt *abt, struct abt_node *node)
77 if (abt->root == NULL)
81 abt_reaugmented (abt, node);
85 struct abt_node *p = abt->root;
90 cmp = abt->compare (node, p, abt->aux);
95 if (p->down[dir] == NULL)
99 abt_reaugmented (abt, node);
106 while ((node = node->up) != NULL)
108 node = skew (abt, node);
109 node = split (abt, node);
115 /* Inserts NODE before or after node P in ABT, depending on the
117 If P is null, then the node is inserted as the first node in
118 the tree, if AFTER is true, or the last node, if AFTER is
121 insert_relative (struct abt *abt, const struct abt_node *p, bool after,
122 struct abt_node *node)
124 node->down[0] = NULL;
125 node->down[1] = NULL;
128 if (abt->root == NULL)
133 abt_reaugmented (abt, node);
143 while (p->down[dir] != NULL)
148 ((struct abt_node *) p)->down[dir] = node;
149 node->up = (struct abt_node *) p;
150 abt_reaugmented (abt, node);
153 while ((node = node->up) != NULL)
155 node = skew (abt, node);
156 node = split (abt, node);
160 /* Inserts NODE after node P in ABT.
161 If P is null, then the node is inserted as the first node in
163 This function may be used only if ABT lacks a comparison
166 abt_insert_after (struct abt *abt,
167 const struct abt_node *p, struct abt_node *node)
169 assert (abt->compare == NULL);
170 insert_relative (abt, p, true, node);
173 /* Inserts NODE before node P in ABT.
174 If P is null, then the node is inserted as the last node in
176 This function may be used only if ABT lacks a comparison
179 abt_insert_before (struct abt *abt,
180 const struct abt_node *p, struct abt_node *node)
182 assert (abt->compare == NULL);
183 insert_relative (abt, p, false, node);
186 /* Deletes P from ABT. */
188 abt_delete (struct abt *abt, struct abt_node *p)
190 struct abt_node **q = down_link (abt, p);
191 struct abt_node *r = p->down[1];
197 else if (r->down[0] == NULL)
199 r->down[0] = p->down[0];
202 if (r->down[0] != NULL)
209 struct abt_node *s = r->down[0];
210 while (s->down[0] != NULL)
213 r->down[0] = s->down[1];
214 s->down[0] = p->down[0];
215 s->down[1] = p->down[1];
221 if (r->down[0] != NULL)
225 abt_reaugmented (abt, p);
227 for (; p != NULL; p = p->up)
228 if ((p->down[0] != NULL ? p->down[0]->level : 0) < p->level - 1
229 || (p->down[1] != NULL ? p->down[1]->level : 0) < p->level - 1)
232 if (p->down[1] != NULL && p->down[1]->level > p->level)
233 p->down[1]->level = p->level;
236 skew (abt, p->down[1]);
237 if (p->down[1]->down[1] != NULL)
238 skew (abt, p->down[1]->down[1]);
241 split (abt, p->down[1]);
245 /* Returns the node with minimum value in ABT, or a null pointer
248 abt_first (const struct abt *abt)
250 struct abt_node *p = abt->root;
252 while (p->down[0] != NULL)
257 /* Returns the node with maximum value in ABT, or a null pointer
260 abt_last (const struct abt *abt)
262 struct abt_node *p = abt->root;
264 while (p->down[1] != NULL)
269 /* Searches ABT for a node equal to TARGET.
270 Returns the node if found, or a null pointer otherwise.
271 This function may be used only if ABT has a comparison
274 abt_find (const struct abt *abt, const struct abt_node *target)
276 const struct abt_node *p;
279 for (p = abt->root; p != NULL; p = p->down[cmp > 0])
281 cmp = abt->compare (target, p, abt->aux);
283 return (struct abt_node *) p;
289 /* Returns the node in ABT following P in in-order.
290 If P is null, returns the minimum node in ABT.
291 Returns a null pointer if P is the maximum node in ABT or if P
292 is null and ABT is empty. */
294 abt_next (const struct abt *abt, const struct abt_node *p)
297 return abt_first (abt);
298 else if (p->down[1] == NULL)
301 for (q = p->up; ; p = q, q = q->up)
302 if (q == NULL || p == q->down[0])
308 while (p->down[0] != NULL)
310 return (struct abt_node *) p;
314 /* Returns the node in ABT preceding P in in-order.
315 If P is null, returns the maximum node in ABT.
316 Returns a null pointer if P is the minimum node in ABT or if P
317 is null and ABT is empty. */
319 abt_prev (const struct abt *abt, const struct abt_node *p)
322 return abt_last (abt);
323 else if (p->down[0] == NULL)
326 for (q = p->up; ; p = q, q = q->up)
327 if (q == NULL || p == q->down[1])
333 while (p->down[1] != NULL)
335 return (struct abt_node *) p;
339 /* Calls ABT's reaugmentation function to compensate for
340 augmentation data in P having been modified. Use abt_changed,
341 instead, if the key data in P has changed.
343 It is not safe to update more than one node's augmentation
344 data, then to call this function for each node. Instead,
345 update a single node's data, call this function, update
346 another node's data, and so on. Alternatively, remove all
347 affected nodes from the tree, update their values, then
348 re-insert all of them. */
350 abt_reaugmented (const struct abt *abt, struct abt_node *p)
352 for (; p != NULL; p = p->up)
353 abt->reaugment (p, p->down[0], p->down[1], abt->aux);
356 /* Moves P around in ABT to compensate for its key having
357 changed. Returns a null pointer if successful. If P's new
358 value is equal to that of some other node in ABT, returns the
359 other node after removing P from ABT.
361 This function is an optimization only if it is likely that P
362 can actually retain its relative position in ABT, e.g. its key
363 has only been adjusted slightly. Otherwise, it is more
364 efficient to simply remove P from ABT, change its key, and
367 It is not safe to update more than one node's key, then to
368 call this function for each node. Instead, update a single
369 node's key, call this function, update another node's key, and
370 so on. Alternatively, remove all affected nodes from the
371 tree, update their keys, then re-insert all of them.
373 This function may be used only if ABT has a comparison
374 function. If it doesn't, then you probably just want
377 abt_changed (struct abt *abt, struct abt_node *p)
379 struct abt_node *prev = abt_prev (abt, p);
380 struct abt_node *next = abt_next (abt, p);
382 if ((prev != NULL && abt->compare (prev, p, abt->aux) >= 0)
383 || (next != NULL && abt->compare (p, next, abt->aux) >= 0))
386 return abt_insert (abt, p);
390 abt_reaugmented (abt, p);
395 /* ABT nodes may be moved around in memory as necessary, e.g. as
396 the result of an realloc operation on a block that contains a
397 node. Once this is done, call this function passing node P
398 that was moved and its ABT before attempting any other
401 It is not safe to move more than one node, then to call this
402 function for each node. Instead, move a single node, call
403 this function, move another node, and so on. Alternatively,
404 remove all affected nodes from the tree, move them, then
405 re-insert all of them.
407 This function may be used only if ABT has a comparison
410 abt_moved (struct abt *abt, struct abt_node *p)
414 int d = p->up->down[0] == NULL || abt->compare (p, p->up, abt->aux) > 0;
419 if (p->down[0] != NULL)
421 if (p->down[1] != NULL)
425 /* Returns the address of the pointer that points down to P
427 static struct abt_node **
428 down_link (struct abt *abt, struct abt_node *p)
430 return (p->up != NULL
431 ? &p->up->down[p->up->down[0] != p]
435 /* Remove a left "horizontal link" at A, if present.
436 Returns the node that occupies the position previously
438 static struct abt_node *
439 skew (struct abt *abt, struct abt_node *a)
441 struct abt_node *b = a->down[0];
442 if (b != NULL && b->level == a->level)
445 a->down[0] = b->down[1];
447 *down_link (abt, a) = b;
449 if (a->down[0] != NULL)
454 abt->reaugment (a, a->down[0], a->down[1], abt->aux);
455 abt->reaugment (b, b->down[0], b->down[1], abt->aux);
463 /* Removes a pair of consecutive right "horizontal links" at A,
465 Returns the node that occupies the position previously
467 static struct abt_node *
468 split (struct abt *abt, struct abt_node *a)
470 struct abt_node *b = a->down[1];
471 if (b != NULL && b->down[1] != NULL && b->down[1]->level == a->level)
474 a->down[1] = b->down[0];
476 *down_link (abt, a) = b;
478 if (a->down[1] != NULL)
485 abt->reaugment (a, a->down[0], a->down[1], abt->aux);
486 abt->reaugment (b, b->down[0], b->down[1], abt->aux);