1 /* PSPP - computes sample statistics.
2 Copyright (C) 2007 Free Software Foundation, Inc.
4 This program is free software; you can redistribute it and/or
5 modify it under the terms of the GNU General Public License as
6 published by the Free Software Foundation; either version 2 of the
7 License, or (at your option) any later version.
9 This program is distributed in the hope that it will be useful, but
10 WITHOUT ANY WARRANTY; without even the implied warranty of
11 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
12 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, write to the Free Software
16 Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
19 /* Augmented binary tree (ABT) data structure. */
21 /* These library routines have no external dependencies other
22 than the standard C library.
24 If you add routines in this file, please add a corresponding
25 test to abt-test.c. This test program should achieve 100%
26 coverage of lines and branches in this code, as reported by
33 #include <libpspp/abt.h>
37 #include <libpspp/assertion.h>
39 static struct abt_node **down_link (struct abt *, struct abt_node *);
40 static struct abt_node *skew (struct abt *, struct abt_node *);
41 static struct abt_node *split (struct abt *, struct abt_node *);
43 /* Initializes ABT as an empty ABT that uses COMPARE and
44 REAUGMENT functions, passing in AUX as auxiliary data.
46 The comparison function is optional. If it is null, this
47 indicates that the tree is being used for its augmentations
48 only. ABT functions that compare nodes may not be used with
49 trees that lack comparison functions; contrariwise, other
50 functions that could disrupt the ordering of a tree may not be
51 used if a comparison function is specified. Refer to
52 individual function descriptions for details. */
54 abt_init (struct abt *abt,
55 abt_compare_func *compare,
56 abt_reaugment_func *reaugment,
59 assert (reaugment != NULL);
61 abt->compare = compare;
62 abt->reaugment = reaugment;
66 /* Inserts the given NODE into ABT.
67 Returns a null pointer if successful.
68 Returns the existing node already in ABT equal to NODE, on
70 This function may be used only if ABT has a comparison
73 abt_insert (struct abt *abt, struct abt_node *node)
79 if (abt->root == NULL)
83 abt_reaugmented (abt, node);
87 struct abt_node *p = abt->root;
92 cmp = abt->compare (node, p, abt->aux);
97 if (p->down[dir] == NULL)
101 abt_reaugmented (abt, node);
108 while ((node = node->up) != NULL)
110 node = skew (abt, node);
111 node = split (abt, node);
117 /* Inserts NODE before or after node P in ABT, depending on the
119 If P is null, then the node is inserted as the first node in
120 the tree, if AFTER is true, or the last node, if AFTER is
123 insert_relative (struct abt *abt, struct abt_node *p, bool after,
124 struct abt_node *node)
126 node->down[0] = NULL;
127 node->down[1] = NULL;
130 if (abt->root == NULL)
135 abt_reaugmented (abt, node);
145 while (p->down[dir] != NULL)
152 abt_reaugmented (abt, node);
155 while ((node = node->up) != NULL)
157 node = skew (abt, node);
158 node = split (abt, node);
162 /* Inserts NODE after node P in ABT.
163 If P is null, then the node is inserted as the first node in
165 This function may be used only if ABT lacks a comparison
168 abt_insert_after (struct abt *abt,
169 const struct abt_node *p, struct abt_node *node)
171 assert (abt->compare == NULL);
172 insert_relative (abt, (struct abt_node *) p, true, node);
175 /* Inserts NODE before node P in ABT.
176 If P is null, then the node is inserted as the last node in
178 This function may be used only if ABT lacks a comparison
181 abt_insert_before (struct abt *abt,
182 const struct abt_node *p, struct abt_node *node)
184 assert (abt->compare == NULL);
185 insert_relative (abt, (struct abt_node *) p, false, node);
188 /* Deletes P from ABT. */
190 abt_delete (struct abt *abt, struct abt_node *p)
192 struct abt_node **q = down_link (abt, p);
193 struct abt_node *r = p->down[1];
199 else if (r->down[0] == NULL)
201 r->down[0] = p->down[0];
204 if (r->down[0] != NULL)
211 struct abt_node *s = r->down[0];
212 while (s->down[0] != NULL)
215 r->down[0] = s->down[1];
216 s->down[0] = p->down[0];
217 s->down[1] = p->down[1];
223 if (r->down[0] != NULL)
227 abt_reaugmented (abt, p);
229 for (; p != NULL; p = p->up)
230 if ((p->down[0] != NULL ? p->down[0]->level : 0) < p->level - 1
231 || (p->down[1] != NULL ? p->down[1]->level : 0) < p->level - 1)
234 if (p->down[1] != NULL && p->down[1]->level > p->level)
235 p->down[1]->level = p->level;
238 skew (abt, p->down[1]);
239 if (p->down[1]->down[1] != NULL)
240 skew (abt, p->down[1]->down[1]);
243 split (abt, p->down[1]);
247 /* Returns the node with minimum value in ABT, or a null pointer
250 abt_first (const struct abt *abt)
252 struct abt_node *p = abt->root;
254 while (p->down[0] != NULL)
259 /* Returns the node with maximum value in ABT, or a null pointer
262 abt_last (const struct abt *abt)
264 struct abt_node *p = abt->root;
266 while (p->down[1] != NULL)
271 /* Searches ABT for a node equal to TARGET.
272 Returns the node if found, or a null pointer otherwise.
273 This function may be used only if ABT has a comparison
276 abt_find (const struct abt *abt, const struct abt_node *target)
278 const struct abt_node *p;
281 for (p = abt->root; p != NULL; p = p->down[cmp > 0])
283 cmp = abt->compare (target, p, abt->aux);
285 return (struct abt_node *) p;
291 /* Returns the node in ABT following P in in-order.
292 If P is null, returns the minimum node in ABT.
293 Returns a null pointer if P is the maximum node in ABT or if P
294 is null and ABT is empty. */
296 abt_next (const struct abt *abt, const struct abt_node *p)
299 return abt_first (abt);
300 else if (p->down[1] == NULL)
303 for (q = p->up; ; p = q, q = q->up)
304 if (q == NULL || p == q->down[0])
310 while (p->down[0] != NULL)
312 return (struct abt_node *) p;
316 /* Returns the node in ABT preceding P in in-order.
317 If P is null, returns the maximum node in ABT.
318 Returns a null pointer if P is the minimum node in ABT or if P
319 is null and ABT is empty. */
321 abt_prev (const struct abt *abt, const struct abt_node *p)
324 return abt_last (abt);
325 else if (p->down[0] == NULL)
328 for (q = p->up; ; p = q, q = q->up)
329 if (q == NULL || p == q->down[1])
335 while (p->down[1] != NULL)
337 return (struct abt_node *) p;
341 /* Calls ABT's reaugmentation function to compensate for
342 augmentation data in P having been modified. Use abt_changed,
343 instead, if the key data in P has changed.
345 It is not safe to update more than one node's augmentation
346 data, then to call this function for each node. Instead,
347 update a single node's data, call this function, update
348 another node's data, and so on. Alternatively, remove all
349 affected nodes from the tree, update their values, then
350 re-insert all of them. */
352 abt_reaugmented (const struct abt *abt, struct abt_node *p)
354 for (; p != NULL; p = p->up)
355 abt->reaugment (p, p->down[0], p->down[1], abt->aux);
358 /* Moves P around in ABT to compensate for its key having
359 changed. Returns a null pointer if successful. If P's new
360 value is equal to that of some other node in ABT, returns the
361 other node after removing P from ABT.
363 This function is an optimization only if it is likely that P
364 can actually retain its relative position in ABT, e.g. its key
365 has only been adjusted slightly. Otherwise, it is more
366 efficient to simply remove P from ABT, change its key, and
369 It is not safe to update more than one node's key, then to
370 call this function for each node. Instead, update a single
371 node's key, call this function, update another node's key, and
372 so on. Alternatively, remove all affected nodes from the
373 tree, update their keys, then re-insert all of them.
375 This function may be used only if ABT has a comparison
376 function. If it doesn't, then you probably just want
379 abt_changed (struct abt *abt, struct abt_node *p)
381 struct abt_node *prev = abt_prev (abt, p);
382 struct abt_node *next = abt_next (abt, p);
384 if ((prev != NULL && abt->compare (prev, p, abt->aux) >= 0)
385 || (next != NULL && abt->compare (p, next, abt->aux) >= 0))
388 return abt_insert (abt, p);
392 abt_reaugmented (abt, p);
397 /* ABT nodes may be moved around in memory as necessary, e.g. as
398 the result of an realloc operation on a block that contains a
399 node. Once this is done, call this function passing node P
400 that was moved and its ABT before attempting any other
403 It is not safe to move more than one node, then to call this
404 function for each node. Instead, move a single node, call
405 this function, move another node, and so on. Alternatively,
406 remove all affected nodes from the tree, move them, then
407 re-insert all of them.
409 This function may be used only if ABT has a comparison
412 abt_moved (struct abt *abt, struct abt_node *p)
416 int d = p->up->down[0] == NULL || abt->compare (p, p->up, abt->aux) > 0;
421 if (p->down[0] != NULL)
423 if (p->down[1] != NULL)
427 /* Returns the address of the pointer that points down to P
429 static struct abt_node **
430 down_link (struct abt *abt, struct abt_node *p)
432 return (p->up != NULL
433 ? &p->up->down[p->up->down[0] != p]
437 /* Remove a left "horizontal link" at A, if present.
438 Returns the node that occupies the position previously
440 static struct abt_node *
441 skew (struct abt *abt, struct abt_node *a)
443 struct abt_node *b = a->down[0];
444 if (b != NULL && b->level == a->level)
447 a->down[0] = b->down[1];
449 *down_link (abt, a) = b;
451 if (a->down[0] != NULL)
456 abt->reaugment (a, a->down[0], a->down[1], abt->aux);
457 abt->reaugment (b, b->down[0], b->down[1], abt->aux);
465 /* Removes a pair of consecutive right "horizontal links" at A,
467 Returns the node that occupies the position previously
469 static struct abt_node *
470 split (struct abt *abt, struct abt_node *a)
472 struct abt_node *b = a->down[1];
473 if (b != NULL && b->down[1] != NULL && b->down[1]->level == a->level)
476 a->down[1] = b->down[0];
478 *down_link (abt, a) = b;
480 if (a->down[1] != NULL)
487 abt->reaugment (a, a->down[0], a->down[1], abt->aux);
488 abt->reaugment (b, b->down[0], b->down[1], abt->aux);