1 /* Produced by texiweb from libavl.w. */
2
3 /* libavl - library for manipulation of binary trees.
4 Copyright (C) 1998, 1999, 2000, 2001, 2002, 2004 Free Software
5 Foundation, Inc.
6
7 This library is free software; you can redistribute it and/or
8 modify it under the terms of the GNU Lesser 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 This library 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 Lesser General Public License for more details.
16
17 You should have received a copy of the GNU Lesser General Public
18 License along with this library; if not, write to the Free Software
19 Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
20 02110-1301 USA.
21 */
22
23 /* Nov 2016, Markus Metz
24 * from libavl-2.0.3
25 * added safety checks and speed optimizations
26 */
27
28 #include <assert.h>
29 #include <stdio.h>
30 #include <stdlib.h>
31 #include "tavl.h"
32
33 /* Creates and returns a new table
34 with comparison function |compare| using parameter |param|
35 and memory allocator |allocator|.
36 Returns |NULL| if memory allocation failed. */
tavl_create(tavl_comparison_func * compare,void * param,struct libavl_allocator * allocator)37 struct tavl_table *tavl_create(tavl_comparison_func * compare, void *param,
38 struct libavl_allocator *allocator)
39 {
40 struct tavl_table *tree;
41
42 assert(compare != NULL);
43
44 if (allocator == NULL)
45 allocator = &tavl_allocator_default;
46
47 tree = allocator->libavl_malloc(allocator, sizeof *tree);
48 if (tree == NULL)
49 return NULL;
50
51 tree->tavl_root = NULL;
52 tree->tavl_compare = compare;
53 tree->tavl_param = param;
54 tree->tavl_alloc = allocator;
55 tree->tavl_count = 0;
56
57 return tree;
58 }
59
60 /* Search |tree| for an item matching |item|, and return it if found.
61 Otherwise return |NULL|. */
tavl_find(const struct tavl_table * tree,const void * item)62 void *tavl_find(const struct tavl_table *tree, const void *item)
63 {
64 const struct tavl_node *p;
65
66 assert(tree != NULL && item != NULL);
67
68 p = tree->tavl_root;
69 while (p != NULL) {
70 int cmp, dir;
71
72 cmp = tree->tavl_compare(item, p->tavl_data, tree->tavl_param);
73 if (cmp == 0)
74 return p->tavl_data;
75
76 dir = cmp > 0;
77 if (p->tavl_tag[dir] == TAVL_CHILD)
78 p = p->tavl_link[dir];
79 else
80 p = NULL;
81 }
82
83 return NULL;
84 }
85
86 /* Inserts |item| into |tree| and returns a pointer to |item|'s address.
87 If a duplicate item is found in the tree,
88 returns a pointer to the duplicate without inserting |item|.
89 Returns |NULL| in case of memory allocation failure. */
tavl_probe(struct tavl_table * tree,void * item)90 void **tavl_probe(struct tavl_table *tree, void *item)
91 {
92 struct tavl_node *y, *z; /* Top node to update balance factor, and parent. */
93 struct tavl_node *p, *q; /* Iterator, and parent. */
94 struct tavl_node *n; /* Newly inserted node. */
95 struct tavl_node *w; /* New root of rebalanced subtree. */
96 int dir; /* Direction to descend. */
97
98 unsigned char da[TAVL_MAX_HEIGHT]; /* Cached comparison results. */
99 int k = 0; /* Number of cached results. */
100
101 assert(tree != NULL && item != NULL);
102
103 z = (struct tavl_node *)&tree->tavl_root;
104 y = tree->tavl_root;
105 dir = 0;
106 q = z, p = y;
107 while (p != NULL) {
108 int cmp =
109 tree->tavl_compare(item, p->tavl_data, tree->tavl_param);
110 if (cmp == 0)
111 return &p->tavl_data;
112
113 if (p->tavl_balance != 0)
114 z = q, y = p, k = 0;
115 da[k++] = dir = cmp > 0;
116
117 if (p->tavl_tag[dir] == TAVL_THREAD)
118 break;
119 q = p, p = p->tavl_link[dir];
120 }
121
122 n = tree->tavl_alloc->libavl_malloc(tree->tavl_alloc, sizeof *n);
123 if (n == NULL)
124 return NULL;
125
126 tree->tavl_count++;
127 n->tavl_data = item;
128 n->tavl_tag[0] = n->tavl_tag[1] = TAVL_THREAD;
129 n->tavl_balance = 0;
130 if (y == NULL) {
131 n->tavl_link[0] = n->tavl_link[1] = NULL;
132 tree->tavl_root = n;
133
134 return &n->tavl_data;
135 }
136 n->tavl_link[dir] = p->tavl_link[dir];
137 n->tavl_link[!dir] = p;
138 p->tavl_tag[dir] = TAVL_CHILD;
139 p->tavl_link[dir] = n;
140
141 p = y, k = 0;
142 while (p != n) {
143 if (da[k] == 0)
144 p->tavl_balance--;
145 else
146 p->tavl_balance++;
147 p = p->tavl_link[da[k]], k++;
148 }
149
150 if (y->tavl_balance == -2) {
151 struct tavl_node *x = y->tavl_link[0];
152
153 if (x->tavl_balance == -1) {
154 w = x;
155 if (x->tavl_tag[1] == TAVL_THREAD) {
156 x->tavl_tag[1] = TAVL_CHILD;
157 y->tavl_tag[0] = TAVL_THREAD;
158 y->tavl_link[0] = x;
159 }
160 else
161 y->tavl_link[0] = x->tavl_link[1];
162 x->tavl_link[1] = y;
163 x->tavl_balance = y->tavl_balance = 0;
164 }
165 else {
166 assert(x->tavl_balance == +1);
167 w = x->tavl_link[1];
168 x->tavl_link[1] = w->tavl_link[0];
169 w->tavl_link[0] = x;
170 y->tavl_link[0] = w->tavl_link[1];
171 w->tavl_link[1] = y;
172 if (w->tavl_balance == -1)
173 x->tavl_balance = 0, y->tavl_balance = +1;
174 else if (w->tavl_balance == 0)
175 x->tavl_balance = y->tavl_balance = 0;
176 else /* |w->tavl_balance == +1| */
177 x->tavl_balance = -1, y->tavl_balance = 0;
178 w->tavl_balance = 0;
179 if (w->tavl_tag[0] == TAVL_THREAD) {
180 x->tavl_tag[1] = TAVL_THREAD;
181 x->tavl_link[1] = w;
182 w->tavl_tag[0] = TAVL_CHILD;
183 }
184 if (w->tavl_tag[1] == TAVL_THREAD) {
185 y->tavl_tag[0] = TAVL_THREAD;
186 y->tavl_link[0] = w;
187 w->tavl_tag[1] = TAVL_CHILD;
188 }
189 }
190 }
191 else if (y->tavl_balance == +2) {
192 struct tavl_node *x = y->tavl_link[1];
193
194 if (x->tavl_balance == +1) {
195 w = x;
196 if (x->tavl_tag[0] == TAVL_THREAD) {
197 x->tavl_tag[0] = TAVL_CHILD;
198 y->tavl_tag[1] = TAVL_THREAD;
199 y->tavl_link[1] = x;
200 }
201 else
202 y->tavl_link[1] = x->tavl_link[0];
203 x->tavl_link[0] = y;
204 x->tavl_balance = y->tavl_balance = 0;
205 }
206 else {
207 assert(x->tavl_balance == -1);
208 w = x->tavl_link[0];
209 x->tavl_link[0] = w->tavl_link[1];
210 w->tavl_link[1] = x;
211 y->tavl_link[1] = w->tavl_link[0];
212 w->tavl_link[0] = y;
213 if (w->tavl_balance == +1)
214 x->tavl_balance = 0, y->tavl_balance = -1;
215 else if (w->tavl_balance == 0)
216 x->tavl_balance = y->tavl_balance = 0;
217 else /* |w->tavl_balance == -1| */
218 x->tavl_balance = +1, y->tavl_balance = 0;
219 w->tavl_balance = 0;
220 if (w->tavl_tag[0] == TAVL_THREAD) {
221 y->tavl_tag[1] = TAVL_THREAD;
222 y->tavl_link[1] = w;
223 w->tavl_tag[0] = TAVL_CHILD;
224 }
225 if (w->tavl_tag[1] == TAVL_THREAD) {
226 x->tavl_tag[0] = TAVL_THREAD;
227 x->tavl_link[0] = w;
228 w->tavl_tag[1] = TAVL_CHILD;
229 }
230 }
231 }
232 else
233 return &n->tavl_data;
234 z->tavl_link[y != z->tavl_link[0]] = w;
235
236 return &n->tavl_data;
237 }
238
239 /* Inserts |item| into |table|.
240 Returns |NULL| if |item| was successfully inserted
241 or if a memory allocation error occurred.
242 Otherwise, returns the duplicate item. */
tavl_insert(struct tavl_table * table,void * item)243 void *tavl_insert(struct tavl_table *table, void *item)
244 {
245 void **p = tavl_probe(table, item);
246
247 return p == NULL || *p == item ? NULL : *p;
248 }
249
250 /* Inserts |item| into |table|, replacing any duplicate item.
251 Returns |NULL| if |item| was inserted without replacing a duplicate,
252 or if a memory allocation error occurred.
253 Otherwise, returns the item that was replaced. */
tavl_replace(struct tavl_table * table,void * item)254 void *tavl_replace(struct tavl_table *table, void *item)
255 {
256 void **p = tavl_probe(table, item);
257
258 if (p == NULL || *p == item)
259 return NULL;
260 else {
261 void *r = *p;
262
263 *p = item;
264
265 return r;
266 }
267 }
268
269 /* Returns the parent of |node| within |tree|,
270 or a pointer to |tavl_root| if |s| is the root of the tree. */
find_parent(struct tavl_table * tree,struct tavl_node * node)271 static struct tavl_node *find_parent(struct tavl_table *tree,
272 struct tavl_node *node)
273 {
274 if (node != tree->tavl_root) {
275 struct tavl_node *x, *y;
276
277 for (x = y = node;; x = x->tavl_link[0], y = y->tavl_link[1])
278 if (y->tavl_tag[1] == TAVL_THREAD) {
279 struct tavl_node *p = y->tavl_link[1];
280
281 if (p == NULL || p->tavl_link[0] != node) {
282 while (x->tavl_tag[0] == TAVL_CHILD)
283 x = x->tavl_link[0];
284 p = x->tavl_link[0];
285 }
286 return p;
287 }
288 else if (x->tavl_tag[0] == TAVL_THREAD) {
289 struct tavl_node *p = x->tavl_link[0];
290
291 if (p == NULL || p->tavl_link[1] != node) {
292 while (y->tavl_tag[1] == TAVL_CHILD)
293 y = y->tavl_link[1];
294 p = y->tavl_link[1];
295 }
296 return p;
297 }
298 }
299 else
300 return (struct tavl_node *)&tree->tavl_root;
301 }
302
303 /* Deletes from |tree| and returns an item matching |item|.
304 Returns a null pointer if no matching item found. */
tavl_delete(struct tavl_table * tree,const void * item)305 void *tavl_delete(struct tavl_table *tree, const void *item)
306 {
307 struct tavl_node *p; /* Traverses tree to find node to delete. */
308 struct tavl_node *q; /* Parent of |p|. */
309 int dir; /* Index into |q->tavl_link[]| to get |p|. */
310 int cmp; /* Result of comparison between |item| and |p|. */
311
312 assert(tree != NULL && item != NULL);
313
314 q = (struct tavl_node *)&tree->tavl_root;
315 p = tree->tavl_root;
316 dir = 0;
317 while (p != NULL) {
318 cmp = tree->tavl_compare(item, p->tavl_data, tree->tavl_param);
319
320 if (cmp == 0)
321 break;
322
323 dir = cmp > 0;
324
325 q = p;
326 if (p->tavl_tag[dir] == TAVL_CHILD)
327 p = p->tavl_link[dir];
328 else
329 p = NULL;
330 }
331 if (p == NULL)
332 return NULL;
333
334 item = p->tavl_data;
335
336 if (p->tavl_tag[1] == TAVL_THREAD) {
337 if (p->tavl_tag[0] == TAVL_CHILD) {
338 struct tavl_node *t = p->tavl_link[0];
339
340 while (t->tavl_tag[1] == TAVL_CHILD)
341 t = t->tavl_link[1];
342 t->tavl_link[1] = p->tavl_link[1];
343 q->tavl_link[dir] = p->tavl_link[0];
344 }
345 else {
346 q->tavl_link[dir] = p->tavl_link[dir];
347 if (q != (struct tavl_node *)&tree->tavl_root)
348 q->tavl_tag[dir] = TAVL_THREAD;
349 }
350 }
351 else {
352 struct tavl_node *r = p->tavl_link[1];
353
354 if (r->tavl_tag[0] == TAVL_THREAD) {
355 r->tavl_link[0] = p->tavl_link[0];
356 r->tavl_tag[0] = p->tavl_tag[0];
357 if (r->tavl_tag[0] == TAVL_CHILD) {
358 struct tavl_node *t = r->tavl_link[0];
359
360 while (t->tavl_tag[1] == TAVL_CHILD)
361 t = t->tavl_link[1];
362 t->tavl_link[1] = r;
363 }
364 q->tavl_link[dir] = r;
365 r->tavl_balance = p->tavl_balance;
366 q = r;
367 dir = 1;
368 }
369 else {
370 struct tavl_node *s;
371
372 while (r != NULL) {
373 s = r->tavl_link[0];
374 if (s->tavl_tag[0] == TAVL_THREAD)
375 break;
376
377 r = s;
378 }
379
380 if (s->tavl_tag[1] == TAVL_CHILD)
381 r->tavl_link[0] = s->tavl_link[1];
382 else {
383 r->tavl_link[0] = s;
384 r->tavl_tag[0] = TAVL_THREAD;
385 }
386
387 s->tavl_link[0] = p->tavl_link[0];
388 if (p->tavl_tag[0] == TAVL_CHILD) {
389 struct tavl_node *t = p->tavl_link[0];
390
391 while (t->tavl_tag[1] == TAVL_CHILD)
392 t = t->tavl_link[1];
393 t->tavl_link[1] = s;
394
395 s->tavl_tag[0] = TAVL_CHILD;
396 }
397
398 s->tavl_link[1] = p->tavl_link[1];
399 s->tavl_tag[1] = TAVL_CHILD;
400
401 q->tavl_link[dir] = s;
402 s->tavl_balance = p->tavl_balance;
403 q = r;
404 dir = 0;
405 }
406 }
407
408 tree->tavl_alloc->libavl_free(tree->tavl_alloc, p);
409
410 while (q != (struct tavl_node *)&tree->tavl_root) {
411 struct tavl_node *y = q;
412
413 q = find_parent(tree, y);
414
415 if (dir == 0) {
416 dir = q->tavl_link[0] != y;
417 y->tavl_balance++;
418 if (y->tavl_balance == +1)
419 break;
420 else if (y->tavl_balance == +2) {
421 struct tavl_node *x = y->tavl_link[1];
422
423 assert(x != NULL);
424 if (x->tavl_balance == -1) {
425 struct tavl_node *w;
426
427 assert(x->tavl_balance == -1);
428 w = x->tavl_link[0];
429 x->tavl_link[0] = w->tavl_link[1];
430 w->tavl_link[1] = x;
431 y->tavl_link[1] = w->tavl_link[0];
432 w->tavl_link[0] = y;
433 if (w->tavl_balance == +1)
434 x->tavl_balance = 0, y->tavl_balance = -1;
435 else if (w->tavl_balance == 0)
436 x->tavl_balance = y->tavl_balance = 0;
437 else /* |w->tavl_balance == -1| */
438 x->tavl_balance = +1, y->tavl_balance = 0;
439 w->tavl_balance = 0;
440 if (w->tavl_tag[0] == TAVL_THREAD) {
441 y->tavl_tag[1] = TAVL_THREAD;
442 y->tavl_link[1] = w;
443 w->tavl_tag[0] = TAVL_CHILD;
444 }
445 if (w->tavl_tag[1] == TAVL_THREAD) {
446 x->tavl_tag[0] = TAVL_THREAD;
447 x->tavl_link[0] = w;
448 w->tavl_tag[1] = TAVL_CHILD;
449 }
450 q->tavl_link[dir] = w;
451 }
452 else {
453 q->tavl_link[dir] = x;
454
455 if (x->tavl_balance == 0) {
456 y->tavl_link[1] = x->tavl_link[0];
457 x->tavl_link[0] = y;
458 x->tavl_balance = -1;
459 y->tavl_balance = +1;
460 break;
461 }
462 else { /* |x->tavl_balance == +1| */
463
464 if (x->tavl_tag[0] == TAVL_CHILD)
465 y->tavl_link[1] = x->tavl_link[0];
466 else {
467 y->tavl_tag[1] = TAVL_THREAD;
468 x->tavl_tag[0] = TAVL_CHILD;
469 }
470 x->tavl_link[0] = y;
471 y->tavl_balance = x->tavl_balance = 0;
472 }
473 }
474 }
475 }
476 else {
477 dir = q->tavl_link[0] != y;
478 y->tavl_balance--;
479 if (y->tavl_balance == -1)
480 break;
481 else if (y->tavl_balance == -2) {
482 struct tavl_node *x = y->tavl_link[0];
483
484 assert(x != NULL);
485 if (x->tavl_balance == +1) {
486 struct tavl_node *w;
487
488 assert(x->tavl_balance == +1);
489 w = x->tavl_link[1];
490 x->tavl_link[1] = w->tavl_link[0];
491 w->tavl_link[0] = x;
492 y->tavl_link[0] = w->tavl_link[1];
493 w->tavl_link[1] = y;
494 if (w->tavl_balance == -1)
495 x->tavl_balance = 0, y->tavl_balance = +1;
496 else if (w->tavl_balance == 0)
497 x->tavl_balance = y->tavl_balance = 0;
498 else /* |w->tavl_balance == +1| */
499 x->tavl_balance = -1, y->tavl_balance = 0;
500 w->tavl_balance = 0;
501 if (w->tavl_tag[0] == TAVL_THREAD) {
502 x->tavl_tag[1] = TAVL_THREAD;
503 x->tavl_link[1] = w;
504 w->tavl_tag[0] = TAVL_CHILD;
505 }
506 if (w->tavl_tag[1] == TAVL_THREAD) {
507 y->tavl_tag[0] = TAVL_THREAD;
508 y->tavl_link[0] = w;
509 w->tavl_tag[1] = TAVL_CHILD;
510 }
511 q->tavl_link[dir] = w;
512 }
513 else {
514 q->tavl_link[dir] = x;
515
516 if (x->tavl_balance == 0) {
517 y->tavl_link[0] = x->tavl_link[1];
518 x->tavl_link[1] = y;
519 x->tavl_balance = +1;
520 y->tavl_balance = -1;
521 break;
522 }
523 else { /* |x->tavl_balance == -1| */
524
525 if (x->tavl_tag[1] == TAVL_CHILD)
526 y->tavl_link[0] = x->tavl_link[1];
527 else {
528 y->tavl_tag[0] = TAVL_THREAD;
529 x->tavl_tag[1] = TAVL_CHILD;
530 }
531 x->tavl_link[1] = y;
532 y->tavl_balance = x->tavl_balance = 0;
533 }
534 }
535 }
536 }
537 }
538
539 tree->tavl_count--;
540
541 return (void *)item;
542 }
543
544 /* Initializes |trav| for use with |tree|
545 and selects the null node. */
tavl_t_init(struct tavl_traverser * trav,struct tavl_table * tree)546 void tavl_t_init(struct tavl_traverser *trav, struct tavl_table *tree)
547 {
548 trav->tavl_table = tree;
549 trav->tavl_node = NULL;
550 }
551
552 /* Initializes |trav| for |tree|.
553 Returns data item in |tree| with the least value,
554 or |NULL| if |tree| is empty. */
tavl_t_first(struct tavl_traverser * trav,struct tavl_table * tree)555 void *tavl_t_first(struct tavl_traverser *trav, struct tavl_table *tree)
556 {
557 assert(tree != NULL && trav != NULL);
558
559 trav->tavl_table = tree;
560 trav->tavl_node = tree->tavl_root;
561 if (trav->tavl_node != NULL) {
562 while (trav->tavl_node->tavl_tag[0] == TAVL_CHILD)
563 trav->tavl_node = trav->tavl_node->tavl_link[0];
564 return trav->tavl_node->tavl_data;
565 }
566 else
567 return NULL;
568 }
569
570 /* Initializes |trav| for |tree|.
571 Returns data item in |tree| with the greatest value,
572 or |NULL| if |tree| is empty. */
tavl_t_last(struct tavl_traverser * trav,struct tavl_table * tree)573 void *tavl_t_last(struct tavl_traverser *trav, struct tavl_table *tree)
574 {
575 assert(tree != NULL && trav != NULL);
576
577 trav->tavl_table = tree;
578 trav->tavl_node = tree->tavl_root;
579 if (trav->tavl_node != NULL) {
580 while (trav->tavl_node->tavl_tag[1] == TAVL_CHILD)
581 trav->tavl_node = trav->tavl_node->tavl_link[1];
582 return trav->tavl_node->tavl_data;
583 }
584 else
585 return NULL;
586 }
587
588 /* Searches for |item| in |tree|.
589 If found, initializes |trav| to the item found and returns the item
590 as well.
591 If there is no matching item, initializes |trav| to the null item
592 and returns |NULL|. */
tavl_t_find(struct tavl_traverser * trav,struct tavl_table * tree,void * item)593 void *tavl_t_find(struct tavl_traverser *trav, struct tavl_table *tree,
594 void *item)
595 {
596 struct tavl_node *p;
597
598 assert(trav != NULL && tree != NULL && item != NULL);
599
600 trav->tavl_table = tree;
601 trav->tavl_node = NULL;
602
603 p = tree->tavl_root;
604 while (p != NULL) {
605 int cmp, dir;
606
607 cmp = tree->tavl_compare(item, p->tavl_data, tree->tavl_param);
608 if (cmp == 0) {
609 trav->tavl_node = p;
610
611 return p->tavl_data;
612 }
613
614 dir = cmp > 0;
615 if (p->tavl_tag[dir] == TAVL_CHILD)
616 p = p->tavl_link[dir];
617 else
618 p = NULL;
619 }
620
621 trav->tavl_node = NULL;
622
623 return NULL;
624 }
625
626 /* Attempts to insert |item| into |tree|.
627 If |item| is inserted successfully, it is returned and |trav| is
628 initialized to its location.
629 If a duplicate is found, it is returned and |trav| is initialized to
630 its location. No replacement of the item occurs.
631 If a memory allocation failure occurs, |NULL| is returned and |trav|
632 is initialized to the null item. */
tavl_t_insert(struct tavl_traverser * trav,struct tavl_table * tree,void * item)633 void *tavl_t_insert(struct tavl_traverser *trav,
634 struct tavl_table *tree, void *item)
635 {
636 void **p;
637
638 assert(trav != NULL && tree != NULL && item != NULL);
639
640 p = tavl_probe(tree, item);
641 if (p != NULL) {
642 trav->tavl_table = tree;
643 trav->tavl_node = ((struct tavl_node *)
644 ((char *)p -
645 offsetof(struct tavl_node, tavl_data)));
646 return *p;
647 }
648 else {
649 tavl_t_init(trav, tree);
650
651 return NULL;
652 }
653 }
654
655 /* Initializes |trav| to have the same current node as |src|. */
tavl_t_copy(struct tavl_traverser * trav,const struct tavl_traverser * src)656 void *tavl_t_copy(struct tavl_traverser *trav,
657 const struct tavl_traverser *src)
658 {
659 assert(trav != NULL && src != NULL);
660
661 trav->tavl_table = src->tavl_table;
662 trav->tavl_node = src->tavl_node;
663
664 return trav->tavl_node != NULL ? trav->tavl_node->tavl_data : NULL;
665 }
666
667 /* Returns the next data item in inorder
668 within the tree being traversed with |trav|,
669 or if there are no more data items returns |NULL|. */
tavl_t_next(struct tavl_traverser * trav)670 void *tavl_t_next(struct tavl_traverser *trav)
671 {
672 assert(trav != NULL);
673
674 if (trav->tavl_node == NULL)
675 return tavl_t_first(trav, trav->tavl_table);
676 else if (trav->tavl_node->tavl_tag[1] == TAVL_THREAD) {
677 trav->tavl_node = trav->tavl_node->tavl_link[1];
678 return trav->tavl_node != NULL ? trav->tavl_node->tavl_data : NULL;
679 }
680 else {
681 trav->tavl_node = trav->tavl_node->tavl_link[1];
682 while (trav->tavl_node->tavl_tag[0] == TAVL_CHILD)
683 trav->tavl_node = trav->tavl_node->tavl_link[0];
684 return trav->tavl_node->tavl_data;
685 }
686 }
687
688 /* Returns the previous data item in inorder
689 within the tree being traversed with |trav|,
690 or if there are no more data items returns |NULL|. */
tavl_t_prev(struct tavl_traverser * trav)691 void *tavl_t_prev(struct tavl_traverser *trav)
692 {
693 assert(trav != NULL);
694
695 if (trav->tavl_node == NULL)
696 return tavl_t_last(trav, trav->tavl_table);
697 else if (trav->tavl_node->tavl_tag[0] == TAVL_THREAD) {
698 trav->tavl_node = trav->tavl_node->tavl_link[0];
699 return trav->tavl_node != NULL ? trav->tavl_node->tavl_data : NULL;
700 }
701 else {
702 trav->tavl_node = trav->tavl_node->tavl_link[0];
703 while (trav->tavl_node->tavl_tag[1] == TAVL_CHILD)
704 trav->tavl_node = trav->tavl_node->tavl_link[1];
705 return trav->tavl_node->tavl_data;
706 }
707 }
708
709 /* Returns |trav|'s current item. */
tavl_t_cur(struct tavl_traverser * trav)710 void *tavl_t_cur(struct tavl_traverser *trav)
711 {
712 assert(trav != NULL);
713
714 return trav->tavl_node != NULL ? trav->tavl_node->tavl_data : NULL;
715 }
716
717 /* Replaces the current item in |trav| by |new| and returns the item replaced.
718 |trav| must not have the null item selected.
719 The new item must not upset the ordering of the tree. */
tavl_t_replace(struct tavl_traverser * trav,void * new)720 void *tavl_t_replace(struct tavl_traverser *trav, void *new)
721 {
722 void *old;
723
724 assert(trav != NULL && trav->tavl_node != NULL && new != NULL);
725 old = trav->tavl_node->tavl_data;
726 trav->tavl_node->tavl_data = new;
727
728 return old;
729 }
730
731 /* Creates a new node as a child of |dst| on side |dir|.
732 Copies data and |tavl_balance| from |src| into the new node,
733 applying |copy()|, if non-null.
734 Returns nonzero only if fully successful.
735 Regardless of success, integrity of the tree structure is assured,
736 though failure may leave a null pointer in a |tavl_data| member. */
737 static int
copy_node(struct tavl_table * tree,struct tavl_node * dst,int dir,const struct tavl_node * src,tavl_copy_func * copy)738 copy_node(struct tavl_table *tree,
739 struct tavl_node *dst, int dir,
740 const struct tavl_node *src, tavl_copy_func * copy)
741 {
742 struct tavl_node *new =
743 tree->tavl_alloc->libavl_malloc(tree->tavl_alloc, sizeof *new);
744 if (new == NULL)
745 return 0;
746
747 new->tavl_link[dir] = dst->tavl_link[dir];
748 new->tavl_tag[dir] = TAVL_THREAD;
749 new->tavl_link[!dir] = dst;
750 new->tavl_tag[!dir] = TAVL_THREAD;
751 dst->tavl_link[dir] = new;
752 dst->tavl_tag[dir] = TAVL_CHILD;
753
754 new->tavl_balance = src->tavl_balance;
755 if (copy == NULL)
756 new->tavl_data = src->tavl_data;
757 else {
758 new->tavl_data = copy(src->tavl_data, tree->tavl_param);
759 if (new->tavl_data == NULL)
760 return 0;
761 }
762
763 return 1;
764 }
765
766 /* Destroys |new| with |tavl_destroy (new, destroy)|,
767 first initializing the right link in |new| that has
768 not yet been initialized. */
769 static void
copy_error_recovery(struct tavl_node * p,struct tavl_table * new,tavl_item_func * destroy)770 copy_error_recovery(struct tavl_node *p,
771 struct tavl_table *new, tavl_item_func * destroy)
772 {
773 new->tavl_root = p;
774 if (p != NULL) {
775 while (p->tavl_tag[1] == TAVL_CHILD)
776 p = p->tavl_link[1];
777 p->tavl_link[1] = NULL;
778 }
779 tavl_destroy(new, destroy);
780 }
781
782 /* Copies |org| to a newly created tree, which is returned.
783 If |copy != NULL|, each data item in |org| is first passed to |copy|,
784 and the return values are inserted into the tree,
785 with |NULL| return values taken as indications of failure.
786 On failure, destroys the partially created new tree,
787 applying |destroy|, if non-null, to each item in the new tree so far,
788 and returns |NULL|.
789 If |allocator != NULL|, it is used for allocation in the new tree.
790 Otherwise, the same allocator used for |org| is used. */
tavl_copy(const struct tavl_table * org,tavl_copy_func * copy,tavl_item_func * destroy,struct libavl_allocator * allocator)791 struct tavl_table *tavl_copy(const struct tavl_table *org,
792 tavl_copy_func * copy, tavl_item_func * destroy,
793 struct libavl_allocator *allocator)
794 {
795 struct tavl_table *new;
796
797 const struct tavl_node *p;
798 struct tavl_node *q;
799 struct tavl_node rp, rq;
800
801 assert(org != NULL);
802 new = tavl_create(org->tavl_compare, org->tavl_param,
803 allocator != NULL ? allocator : org->tavl_alloc);
804 if (new == NULL)
805 return NULL;
806
807 new->tavl_count = org->tavl_count;
808 if (new->tavl_count == 0)
809 return new;
810
811 p = &rp;
812 rp.tavl_link[0] = org->tavl_root;
813 rp.tavl_tag[0] = TAVL_CHILD;
814
815 q = &rq;
816 rq.tavl_link[0] = NULL;
817 rq.tavl_tag[0] = TAVL_THREAD;
818
819 while (p != NULL) {
820 if (p->tavl_tag[0] == TAVL_CHILD) {
821 if (!copy_node(new, q, 0, p->tavl_link[0], copy)) {
822 copy_error_recovery(rq.tavl_link[0], new, destroy);
823 return NULL;
824 }
825
826 p = p->tavl_link[0];
827 q = q->tavl_link[0];
828 }
829 else {
830 while (p->tavl_tag[1] == TAVL_THREAD) {
831 p = p->tavl_link[1];
832 if (p == NULL) {
833 q->tavl_link[1] = NULL;
834 new->tavl_root = rq.tavl_link[0];
835 return new;
836 }
837
838 q = q->tavl_link[1];
839 }
840
841 p = p->tavl_link[1];
842 q = q->tavl_link[1];
843 }
844
845 if (p->tavl_tag[1] == TAVL_CHILD)
846 if (!copy_node(new, q, 1, p->tavl_link[1], copy)) {
847 copy_error_recovery(rq.tavl_link[0], new, destroy);
848 return NULL;
849 }
850 }
851
852 return new;
853 }
854
855 /* Frees storage allocated for |tree|.
856 If |destroy != NULL|, applies it to each data item in inorder. */
tavl_destroy(struct tavl_table * tree,tavl_item_func * destroy)857 void tavl_destroy(struct tavl_table *tree, tavl_item_func * destroy)
858 {
859 struct tavl_node *p; /* Current node. */
860 struct tavl_node *n; /* Next node. */
861
862 p = tree->tavl_root;
863 if (p != NULL) {
864 while (p->tavl_tag[0] == TAVL_CHILD)
865 p = p->tavl_link[0];
866 }
867
868 while (p != NULL) {
869 n = p->tavl_link[1];
870 if (p->tavl_tag[1] == TAVL_CHILD)
871 while (n->tavl_tag[0] == TAVL_CHILD)
872 n = n->tavl_link[0];
873
874 if (destroy != NULL && p->tavl_data != NULL)
875 destroy(p->tavl_data, tree->tavl_param);
876 tree->tavl_alloc->libavl_free(tree->tavl_alloc, p);
877
878 p = n;
879 }
880
881 tree->tavl_alloc->libavl_free(tree->tavl_alloc, tree);
882 }
883
884 /* Allocates |size| bytes of space using |malloc()|.
885 Returns a null pointer if allocation fails. */
tavl_malloc(struct libavl_allocator * allocator,size_t size)886 void *tavl_malloc(struct libavl_allocator *allocator, size_t size)
887 {
888 assert(allocator != NULL && size > 0);
889 return malloc(size);
890 }
891
892 /* Frees |block|. */
tavl_free(struct libavl_allocator * allocator,void * block)893 void tavl_free(struct libavl_allocator *allocator, void *block)
894 {
895 assert(allocator != NULL && block != NULL);
896 free(block);
897 }
898
899 /* Default memory allocator that uses |malloc()| and |free()|. */
900 struct libavl_allocator tavl_allocator_default = {
901 tavl_malloc,
902 tavl_free
903 };
904
905 #undef NDEBUG
906 #include <assert.h>
907
908 /* Asserts that |tavl_insert()| succeeds at inserting |item| into |table|. */
909 void (tavl_assert_insert) (struct tavl_table * table, void *item)
910 {
911 void **p = tavl_probe(table, item);
912
913 assert(p != NULL && *p == item);
914 }
915
916 /* Asserts that |tavl_delete()| really removes |item| from |table|,
917 and returns the removed item. */
918 void *(tavl_assert_delete) (struct tavl_table * table, void *item)
919 {
920 void *p = tavl_delete(table, item);
921
922 assert(p != NULL);
923
924 return p;
925 }
926