1 /* PSPP - a program for statistical analysis.
2 Copyright (C) 2007, 2009, 2011 Free Software Foundation, Inc.
3
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.
8
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.
13
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/>. */
16
17 /* Augmented binary tree (ABT) data structure. */
18
19 /* These library routines have no external dependencies other
20 than the standard C library.
21
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
25 "gcov -b". */
26
27 #ifdef HAVE_CONFIG_H
28 #include <config.h>
29 #endif
30
31 #include "libpspp/abt.h"
32
33 #include <stdbool.h>
34
35 #include "libpspp/cast.h"
36 #include "libpspp/assertion.h"
37
38 static struct abt_node **down_link (struct abt *, struct abt_node *);
39 static struct abt_node *skew (struct abt *, struct abt_node *);
40 static struct abt_node *split (struct abt *, struct abt_node *);
41
42 /* Initializes ABT as an empty ABT that uses COMPARE and
43 REAUGMENT functions, passing in AUX as auxiliary data.
44
45 The comparison function is optional. If it is null, this
46 indicates that the tree is being used for its augmentations
47 only. ABT functions that compare nodes may not be used with
48 trees that lack comparison functions; contrariwise, other
49 functions that could disrupt the ordering of a tree may not be
50 used if a comparison function is specified. Refer to
51 individual function descriptions for details. */
52 void
abt_init(struct abt * abt,abt_compare_func * compare,abt_reaugment_func * reaugment,const void * aux)53 abt_init (struct abt *abt,
54 abt_compare_func *compare,
55 abt_reaugment_func *reaugment,
56 const void *aux)
57 {
58 assert (reaugment != NULL);
59 abt->root = NULL;
60 abt->compare = compare;
61 abt->reaugment = reaugment;
62 abt->aux = aux;
63 }
64
65 /* Inserts the given NODE into ABT.
66 Returns a null pointer if successful.
67 Returns the existing node already in ABT equal to NODE, on
68 failure.
69 This function may be used only if ABT has a comparison
70 function. */
71 struct abt_node *
abt_insert(struct abt * abt,struct abt_node * node)72 abt_insert (struct abt *abt, struct abt_node *node)
73 {
74 node->down[0] = NULL;
75 node->down[1] = NULL;
76 node->level = 1;
77
78 if (abt->root == NULL)
79 {
80 abt->root = node;
81 node->up = NULL;
82 abt_reaugmented (abt, node);
83 }
84 else
85 {
86 struct abt_node *p = abt->root;
87 for (;;)
88 {
89 int cmp, dir;
90
91 cmp = abt->compare (node, p, abt->aux);
92 if (cmp == 0)
93 return p;
94
95 dir = cmp > 0;
96 if (p->down[dir] == NULL)
97 {
98 p->down[dir] = node;
99 node->up = p;
100 abt_reaugmented (abt, node);
101 break;
102 }
103 p = p->down[dir];
104 }
105 }
106
107 while ((node = node->up) != NULL)
108 {
109 node = skew (abt, node);
110 node = split (abt, node);
111 }
112
113 return NULL;
114 }
115
116 /* Inserts NODE before or after node P in ABT, depending on the
117 value of AFTER.
118 If P is null, then the node is inserted as the first node in
119 the tree, if AFTER is true, or the last node, if AFTER is
120 false. */
121 static inline void
insert_relative(struct abt * abt,const struct abt_node * p,bool after,struct abt_node * node)122 insert_relative (struct abt *abt, const struct abt_node *p, bool after,
123 struct abt_node *node)
124 {
125 node->down[0] = NULL;
126 node->down[1] = NULL;
127 node->level = 1;
128
129 if (abt->root == NULL)
130 {
131 assert (p == NULL);
132 abt->root = node;
133 node->up = NULL;
134 abt_reaugmented (abt, node);
135 }
136 else
137 {
138 int dir = after;
139 if (p == NULL)
140 {
141 p = abt->root;
142 dir = !after;
143 }
144 while (p->down[dir] != NULL)
145 {
146 p = p->down[dir];
147 dir = !after;
148 }
149 CONST_CAST (struct abt_node *, p)->down[dir] = node;
150 node->up = CONST_CAST (struct abt_node *, p);
151 abt_reaugmented (abt, node);
152 }
153
154 while ((node = node->up) != NULL)
155 {
156 node = skew (abt, node);
157 node = split (abt, node);
158 }
159 }
160
161 /* Inserts NODE after node P in ABT.
162 If P is null, then the node is inserted as the first node in
163 the tree.
164 This function may be used only if ABT lacks a comparison
165 function. */
166 void
abt_insert_after(struct abt * abt,const struct abt_node * p,struct abt_node * node)167 abt_insert_after (struct abt *abt,
168 const struct abt_node *p, struct abt_node *node)
169 {
170 assert (abt->compare == NULL);
171 insert_relative (abt, p, true, node);
172 }
173
174 /* Inserts NODE before node P in ABT.
175 If P is null, then the node is inserted as the last node in
176 the tree.
177 This function may be used only if ABT lacks a comparison
178 function. */
179 void
abt_insert_before(struct abt * abt,const struct abt_node * p,struct abt_node * node)180 abt_insert_before (struct abt *abt,
181 const struct abt_node *p, struct abt_node *node)
182 {
183 assert (abt->compare == NULL);
184 insert_relative (abt, p, false, node);
185 }
186
187 /* Deletes P from ABT. */
188 void
abt_delete(struct abt * abt,struct abt_node * p)189 abt_delete (struct abt *abt, struct abt_node *p)
190 {
191 struct abt_node **q = down_link (abt, p);
192 struct abt_node *r = p->down[1];
193 if (r == NULL)
194 {
195 *q = NULL;
196 p = p->up;
197 }
198 else if (r->down[0] == NULL)
199 {
200 r->down[0] = p->down[0];
201 *q = r;
202 r->up = p->up;
203 if (r->down[0] != NULL)
204 r->down[0]->up = r;
205 r->level = p->level;
206 p = r;
207 }
208 else
209 {
210 struct abt_node *s = r->down[0];
211 while (s->down[0] != NULL)
212 s = s->down[0];
213 r = s->up;
214 r->down[0] = s->down[1];
215 s->down[0] = p->down[0];
216 s->down[1] = p->down[1];
217 *q = s;
218 s->down[0]->up = s;
219 s->down[1]->up = s;
220 s->up = p->up;
221 s->level = p->level;
222 if (r->down[0] != NULL)
223 r->down[0]->up = r;
224 p = r;
225 }
226 abt_reaugmented (abt, p);
227
228 for (; p != NULL; p = p->up)
229 if ((p->down[0] != NULL ? p->down[0]->level : 0) < p->level - 1
230 || (p->down[1] != NULL ? p->down[1]->level : 0) < p->level - 1)
231 {
232 p->level--;
233 if (p->down[1] != NULL && p->down[1]->level > p->level)
234 p->down[1]->level = p->level;
235
236 p = skew (abt, p);
237 skew (abt, p->down[1]);
238 if (p->down[1]->down[1] != NULL)
239 skew (abt, p->down[1]->down[1]);
240
241 p = split (abt, p);
242 split (abt, p->down[1]);
243 }
244 }
245
246 /* Returns the node with minimum value in ABT, or a null pointer
247 if ABT is empty. */
248 struct abt_node *
abt_first(const struct abt * abt)249 abt_first (const struct abt *abt)
250 {
251 struct abt_node *p = abt->root;
252 if (p != NULL)
253 while (p->down[0] != NULL)
254 p = p->down[0];
255 return p;
256 }
257
258 /* Returns the node with maximum value in ABT, or a null pointer
259 if ABT is empty. */
260 struct abt_node *
abt_last(const struct abt * abt)261 abt_last (const struct abt *abt)
262 {
263 struct abt_node *p = abt->root;
264 if (p != NULL)
265 while (p->down[1] != NULL)
266 p = p->down[1];
267 return p;
268 }
269
270 /* Searches ABT for a node equal to TARGET.
271 Returns the node if found, or a null pointer otherwise.
272 This function may be used only if ABT has a comparison
273 function. */
274 struct abt_node *
abt_find(const struct abt * abt,const struct abt_node * target)275 abt_find (const struct abt *abt, const struct abt_node *target)
276 {
277 const struct abt_node *p;
278 int cmp;
279
280 for (p = abt->root; p != NULL; p = p->down[cmp > 0])
281 {
282 cmp = abt->compare (target, p, abt->aux);
283 if (cmp == 0)
284 return CONST_CAST (struct abt_node *, p);
285 }
286
287 return NULL;
288 }
289
290 /* Returns the node in ABT following P in in-order.
291 If P is null, returns the minimum node in ABT.
292 Returns a null pointer if P is the maximum node in ABT or if P
293 is null and ABT is empty. */
294 struct abt_node *
abt_next(const struct abt * abt,const struct abt_node * p)295 abt_next (const struct abt *abt, const struct abt_node *p)
296 {
297 if (p == NULL)
298 return abt_first (abt);
299 else if (p->down[1] == NULL)
300 {
301 struct abt_node *q;
302 for (q = p->up; ; p = q, q = q->up)
303 if (q == NULL || p == q->down[0])
304 return q;
305 }
306 else
307 {
308 p = p->down[1];
309 while (p->down[0] != NULL)
310 p = p->down[0];
311 return CONST_CAST (struct abt_node *, p);
312 }
313 }
314
315 /* Returns the node in ABT preceding P in in-order.
316 If P is null, returns the maximum node in ABT.
317 Returns a null pointer if P is the minimum node in ABT or if P
318 is null and ABT is empty. */
319 struct abt_node *
abt_prev(const struct abt * abt,const struct abt_node * p)320 abt_prev (const struct abt *abt, const struct abt_node *p)
321 {
322 if (p == NULL)
323 return abt_last (abt);
324 else if (p->down[0] == NULL)
325 {
326 struct abt_node *q;
327 for (q = p->up; ; p = q, q = q->up)
328 if (q == NULL || p == q->down[1])
329 return q;
330 }
331 else
332 {
333 p = p->down[0];
334 while (p->down[1] != NULL)
335 p = p->down[1];
336 return CONST_CAST (struct abt_node *, p);
337 }
338 }
339
340 /* Calls ABT's reaugmentation function to compensate for
341 augmentation data in P having been modified. Use abt_changed,
342 instead, if the key data in P has changed.
343
344 It is not safe to update more than one node's augmentation
345 data, then to call this function for each node. Instead,
346 update a single node's data, call this function, update
347 another node's data, and so on. Alternatively, remove all
348 affected nodes from the tree, update their values, then
349 re-insert all of them. */
350 void
abt_reaugmented(const struct abt * abt,struct abt_node * p)351 abt_reaugmented (const struct abt *abt, struct abt_node *p)
352 {
353 for (; p != NULL; p = p->up)
354 abt->reaugment (p, abt->aux);
355 }
356
357 /* Moves P around in ABT to compensate for its key having
358 changed. Returns a null pointer if successful. If P's new
359 value is equal to that of some other node in ABT, returns the
360 other node after removing P from ABT.
361
362 This function is an optimization only if it is likely that P
363 can actually retain its relative position in ABT, e.g. its key
364 has only been adjusted slightly. Otherwise, it is more
365 efficient to simply remove P from ABT, change its key, and
366 re-insert P.
367
368 It is not safe to update more than one node's key, then to
369 call this function for each node. Instead, update a single
370 node's key, call this function, update another node's key, and
371 so on. Alternatively, remove all affected nodes from the
372 tree, update their keys, then re-insert all of them.
373
374 This function may be used only if ABT has a comparison
375 function. If it doesn't, then you probably just want
376 abt_reaugmented. */
377 struct abt_node *
abt_changed(struct abt * abt,struct abt_node * p)378 abt_changed (struct abt *abt, struct abt_node *p)
379 {
380 struct abt_node *prev = abt_prev (abt, p);
381 struct abt_node *next = abt_next (abt, p);
382
383 if ((prev != NULL && abt->compare (prev, p, abt->aux) >= 0)
384 || (next != NULL && abt->compare (p, next, abt->aux) >= 0))
385 {
386 abt_delete (abt, p);
387 return abt_insert (abt, p);
388 }
389 else
390 {
391 abt_reaugmented (abt, p);
392 return NULL;
393 }
394 }
395
396 /* ABT nodes may be moved around in memory as necessary, e.g. as
397 the result of an realloc operation on a block that contains a
398 node. Once this is done, call this function passing node P
399 that was moved and its ABT before attempting any other
400 operation on ABT.
401
402 It is not safe to move more than one node, then to call this
403 function for each node. Instead, move a single node, call
404 this function, move another node, and so on. Alternatively,
405 remove all affected nodes from the tree, move them, then
406 re-insert all of them.
407
408 This function may be used only if ABT has a comparison
409 function. */
410 void
abt_moved(struct abt * abt,struct abt_node * p)411 abt_moved (struct abt *abt, struct abt_node *p)
412 {
413 if (p->up != NULL)
414 {
415 int d = p->up->down[0] == NULL || abt->compare (p, p->up, abt->aux) > 0;
416 p->up->down[d] = p;
417 }
418 else
419 abt->root = p;
420 if (p->down[0] != NULL)
421 p->down[0]->up = p;
422 if (p->down[1] != NULL)
423 p->down[1]->up = p;
424 }
425
426 /* Returns the address of the pointer that points down to P
427 within ABT. */
428 static struct abt_node **
down_link(struct abt * abt,struct abt_node * p)429 down_link (struct abt *abt, struct abt_node *p)
430 {
431 return (p->up != NULL
432 ? &p->up->down[p->up->down[0] != p]
433 : &abt->root);
434 }
435
436 /* Remove a left "horizontal link" at A, if present.
437 Returns the node that occupies the position previously
438 occupied by A. */
439 static struct abt_node *
skew(struct abt * abt,struct abt_node * a)440 skew (struct abt *abt, struct abt_node *a)
441 {
442 struct abt_node *b = a->down[0];
443 if (b != NULL && b->level == a->level)
444 {
445 /* Rotate right. */
446 a->down[0] = b->down[1];
447 b->down[1] = a;
448 *down_link (abt, a) = b;
449
450 if (a->down[0] != NULL)
451 a->down[0]->up = a;
452 b->up = a->up;
453 a->up = b;
454
455 abt->reaugment (a, abt->aux);
456 abt->reaugment (b, abt->aux);
457
458 return b;
459 }
460 else
461 return a;
462 }
463
464 /* Removes a pair of consecutive right "horizontal links" at A,
465 if present.
466 Returns the node that occupies the position previously
467 occupied by A. */
468 static struct abt_node *
split(struct abt * abt,struct abt_node * a)469 split (struct abt *abt, struct abt_node *a)
470 {
471 struct abt_node *b = a->down[1];
472 if (b != NULL && b->down[1] != NULL && b->down[1]->level == a->level)
473 {
474 /* Rotate left. */
475 a->down[1] = b->down[0];
476 b->down[0] = a;
477 *down_link (abt, a) = b;
478
479 if (a->down[1] != NULL)
480 a->down[1]->up = a;
481 b->up = a->up;
482 a->up = b;
483
484 b->level++;
485
486 abt->reaugment (a, abt->aux);
487 abt->reaugment (b, abt->aux);
488
489 return b;
490 }
491 else
492 return a;
493 }
494