1 /* Produced by texiweb from libavl.w. */
3 /* libavl - library for manipulation of binary trees.
4 Copyright (C) 1998-2002, 2004 Free Software Foundation, Inc.
6 This program is free software; you can redistribute it and/or
7 modify it under the terms of the GNU General Public License as
8 published by the Free Software Foundation; either version 2 of the
9 License, or (at your option) any later version.
11 This program is distributed in the hope that it will be useful, but
12 WITHOUT ANY WARRANTY; without even the implied warranty of
13 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
14 See the GNU General Public License for more details.
16 You should have received a copy of the GNU General Public License
17 along with this program; if not, write to the Free Software
18 Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA
21 The author may be contacted at <blp@gnu.org> on the Internet, or
22 write to Ben Pfaff, Stanford University, Computer Science Dept., 353
23 Serra Mall, Stanford CA 94305, USA.
31 /* Creates and returns a new table
32 with comparison function |compare| using parameter |param|
33 and memory allocator |allocator|.
34 Returns |NULL| if memory allocation failed. */
36 tavl_create (tavl_comparison_func *compare, void *param,
37 struct libavl_allocator *allocator)
39 struct tavl_table *tree;
41 assert (compare != NULL);
43 if (allocator == NULL)
44 allocator = &tavl_allocator_default;
46 tree = allocator->libavl_malloc (allocator, sizeof *tree);
50 tree->tavl_root = NULL;
51 tree->tavl_compare = compare;
52 tree->tavl_param = param;
53 tree->tavl_alloc = allocator;
59 /* Search |tree| for an item matching |item|, and return it if found.
60 Otherwise return |NULL|. */
62 tavl_find (const struct tavl_table *tree, const void *item)
64 const struct tavl_node *p;
66 assert (tree != NULL && item != NULL);
76 cmp = tree->tavl_compare (item, p->tavl_data, tree->tavl_param);
81 if (p->tavl_tag[dir] == TAVL_CHILD)
82 p = p->tavl_link[dir];
88 /* Search |tree| for an item matching |item|, and return it if found.
89 Otherwise return |NULL| and set predecessor and successor to point to
90 the relevant nodes. */
92 tavl_bracket (const struct tavl_table *tree, const void *item, const void **predecessor, const void **successor)
94 const struct tavl_node *p;
96 assert (tree != NULL && item != NULL);
108 cmp = tree->tavl_compare (item, p->tavl_data, tree->tavl_param);
113 if (p->tavl_tag[dir] == TAVL_CHILD)
114 p = p->tavl_link[dir];
115 else /* no match, bracket */
117 if (dir) /* match would have been above p */
119 *predecessor = p->tavl_data;
120 p = p->tavl_link[dir]; /* follow thread up */
122 *successor = p->tavl_data;
124 else /* match would have been below p */
126 *successor = p->tavl_data;
127 p = p->tavl_link[dir]; /* follow thread down */
129 *predecessor = p->tavl_data;
136 /* Inserts |item| into |tree| and returns a pointer to |item|'s address.
137 If a duplicate item is found in the tree,
138 returns a pointer to the duplicate without inserting |item|.
139 Returns |NULL| in case of memory allocation failure. */
141 tavl_probe (struct tavl_table *tree, void *item)
143 struct tavl_node *y, *z; /* Top node to update balance factor, and parent. */
144 struct tavl_node *p, *q; /* Iterator, and parent. */
145 struct tavl_node *n; /* Newly inserted node. */
146 struct tavl_node *w; /* New root of rebalanced subtree. */
147 int dir; /* Direction to descend. */
149 unsigned char da[TAVL_MAX_HEIGHT]; /* Cached comparison results. */
150 int k = 0; /* Number of cached results. */
152 assert (tree != NULL && item != NULL);
154 z = (struct tavl_node *) &tree->tavl_root;
158 for (q = z, p = y; ; q = p, p = p->tavl_link[dir])
160 int cmp = tree->tavl_compare (item, p->tavl_data, tree->tavl_param);
162 return &p->tavl_data;
164 if (p->tavl_balance != 0)
166 da[k++] = dir = cmp > 0;
168 if (p->tavl_tag[dir] == TAVL_THREAD)
178 n = tree->tavl_alloc->libavl_malloc (tree->tavl_alloc, sizeof *n);
184 n->tavl_tag[0] = n->tavl_tag[1] = TAVL_THREAD;
185 n->tavl_link[dir] = p->tavl_link[dir];
186 if (tree->tavl_root != NULL)
188 p->tavl_tag[dir] = TAVL_CHILD;
189 n->tavl_link[!dir] = p;
192 n->tavl_link[1] = NULL;
193 p->tavl_link[dir] = n;
195 if (tree->tavl_root == n)
196 return &n->tavl_data;
198 for (p = y, k = 0; p != n; p = p->tavl_link[da[k]], k++)
204 if (y->tavl_balance == -2)
206 struct tavl_node *x = y->tavl_link[0];
207 if (x->tavl_balance == -1)
210 if (x->tavl_tag[1] == TAVL_THREAD)
212 x->tavl_tag[1] = TAVL_CHILD;
213 y->tavl_tag[0] = TAVL_THREAD;
217 y->tavl_link[0] = x->tavl_link[1];
219 x->tavl_balance = y->tavl_balance = 0;
223 assert (x->tavl_balance == +1);
225 x->tavl_link[1] = w->tavl_link[0];
227 y->tavl_link[0] = w->tavl_link[1];
229 if (w->tavl_balance == -1)
230 x->tavl_balance = 0, y->tavl_balance = +1;
231 else if (w->tavl_balance == 0)
232 x->tavl_balance = y->tavl_balance = 0;
233 else /* |w->tavl_balance == +1| */
234 x->tavl_balance = -1, y->tavl_balance = 0;
236 if (w->tavl_tag[0] == TAVL_THREAD)
238 x->tavl_tag[1] = TAVL_THREAD;
240 w->tavl_tag[0] = TAVL_CHILD;
242 if (w->tavl_tag[1] == TAVL_THREAD)
244 y->tavl_tag[0] = TAVL_THREAD;
246 w->tavl_tag[1] = TAVL_CHILD;
250 else if (y->tavl_balance == +2)
252 struct tavl_node *x = y->tavl_link[1];
253 if (x->tavl_balance == +1)
256 if (x->tavl_tag[0] == TAVL_THREAD)
258 x->tavl_tag[0] = TAVL_CHILD;
259 y->tavl_tag[1] = TAVL_THREAD;
263 y->tavl_link[1] = x->tavl_link[0];
265 x->tavl_balance = y->tavl_balance = 0;
269 assert (x->tavl_balance == -1);
271 x->tavl_link[0] = w->tavl_link[1];
273 y->tavl_link[1] = w->tavl_link[0];
275 if (w->tavl_balance == +1)
276 x->tavl_balance = 0, y->tavl_balance = -1;
277 else if (w->tavl_balance == 0)
278 x->tavl_balance = y->tavl_balance = 0;
279 else /* |w->tavl_balance == -1| */
280 x->tavl_balance = +1, y->tavl_balance = 0;
282 if (w->tavl_tag[0] == TAVL_THREAD)
284 y->tavl_tag[1] = TAVL_THREAD;
286 w->tavl_tag[0] = TAVL_CHILD;
288 if (w->tavl_tag[1] == TAVL_THREAD)
290 x->tavl_tag[0] = TAVL_THREAD;
292 w->tavl_tag[1] = TAVL_CHILD;
297 return &n->tavl_data;
298 z->tavl_link[y != z->tavl_link[0]] = w;
300 return &n->tavl_data;
303 /* Inserts |item| into |table|.
304 Returns |NULL| if |item| was successfully inserted
305 or if a memory allocation error occurred.
306 Otherwise, returns the duplicate item. */
308 tavl_insert (struct tavl_table *table, void *item)
310 void **p = tavl_probe (table, item);
311 return p == NULL || *p == item ? NULL : *p;
314 /* Inserts |item| into |table|, replacing any duplicate item.
315 Returns |NULL| if |item| was inserted without replacing a duplicate,
316 or if a memory allocation error occurred.
317 Otherwise, returns the item that was replaced. */
319 tavl_replace (struct tavl_table *table, void *item)
321 void **p = tavl_probe (table, item);
322 if (p == NULL || *p == item)
332 /* Returns the parent of |node| within |tree|,
333 or a pointer to |tavl_root| if |s| is the root of the tree. */
334 static struct tavl_node *
335 find_parent (struct tavl_table *tree, struct tavl_node *node)
337 if (node != tree->tavl_root)
339 struct tavl_node *x, *y;
341 for (x = y = node; ; x = x->tavl_link[0], y = y->tavl_link[1])
342 if (y->tavl_tag[1] == TAVL_THREAD)
344 struct tavl_node *p = y->tavl_link[1];
345 if (p == NULL || p->tavl_link[0] != node)
347 while (x->tavl_tag[0] == TAVL_CHILD)
353 else if (x->tavl_tag[0] == TAVL_THREAD)
355 struct tavl_node *p = x->tavl_link[0];
356 if (p == NULL || p->tavl_link[1] != node)
358 while (y->tavl_tag[1] == TAVL_CHILD)
366 return (struct tavl_node *) &tree->tavl_root;
369 /* Deletes from |tree| and returns an item matching |item|.
370 Returns a null pointer if no matching item found. */
372 tavl_delete (struct tavl_table *tree, const void *item)
374 struct tavl_node *p; /* Traverses tree to find node to delete. */
375 struct tavl_node *q; /* Parent of |p|. */
376 int dir; /* Index into |q->tavl_link[]| to get |p|. */
377 int cmp; /* Result of comparison between |item| and |p|. */
379 assert (tree != NULL && item != NULL);
381 if (tree->tavl_root == NULL)
384 q = (struct tavl_node *) &tree->tavl_root;
389 cmp = tree->tavl_compare (item, p->tavl_data, tree->tavl_param);
395 if (p->tavl_tag[dir] == TAVL_THREAD)
397 p = p->tavl_link[dir];
401 if (p->tavl_tag[1] == TAVL_THREAD)
403 if (p->tavl_tag[0] == TAVL_CHILD)
405 struct tavl_node *t = p->tavl_link[0];
406 while (t->tavl_tag[1] == TAVL_CHILD)
408 t->tavl_link[1] = p->tavl_link[1];
409 q->tavl_link[dir] = p->tavl_link[0];
413 q->tavl_link[dir] = p->tavl_link[dir];
414 if (q != (struct tavl_node *) &tree->tavl_root)
415 q->tavl_tag[dir] = TAVL_THREAD;
420 struct tavl_node *r = p->tavl_link[1];
421 if (r->tavl_tag[0] == TAVL_THREAD)
423 r->tavl_link[0] = p->tavl_link[0];
424 r->tavl_tag[0] = p->tavl_tag[0];
425 if (r->tavl_tag[0] == TAVL_CHILD)
427 struct tavl_node *t = r->tavl_link[0];
428 while (t->tavl_tag[1] == TAVL_CHILD)
432 q->tavl_link[dir] = r;
433 r->tavl_balance = p->tavl_balance;
444 if (s->tavl_tag[0] == TAVL_THREAD)
450 if (s->tavl_tag[1] == TAVL_CHILD)
451 r->tavl_link[0] = s->tavl_link[1];
455 r->tavl_tag[0] = TAVL_THREAD;
458 s->tavl_link[0] = p->tavl_link[0];
459 if (p->tavl_tag[0] == TAVL_CHILD)
461 struct tavl_node *t = p->tavl_link[0];
462 while (t->tavl_tag[1] == TAVL_CHILD)
466 s->tavl_tag[0] = TAVL_CHILD;
469 s->tavl_link[1] = p->tavl_link[1];
470 s->tavl_tag[1] = TAVL_CHILD;
472 q->tavl_link[dir] = s;
473 s->tavl_balance = p->tavl_balance;
479 tree->tavl_alloc->libavl_free (tree->tavl_alloc, p);
481 while (q != (struct tavl_node *) &tree->tavl_root)
483 struct tavl_node *y = q;
485 q = find_parent (tree, y);
489 dir = q->tavl_link[0] != y;
491 if (y->tavl_balance == +1)
493 else if (y->tavl_balance == +2)
495 struct tavl_node *x = y->tavl_link[1];
498 if (x->tavl_balance == -1)
502 assert (x->tavl_balance == -1);
504 x->tavl_link[0] = w->tavl_link[1];
506 y->tavl_link[1] = w->tavl_link[0];
508 if (w->tavl_balance == +1)
509 x->tavl_balance = 0, y->tavl_balance = -1;
510 else if (w->tavl_balance == 0)
511 x->tavl_balance = y->tavl_balance = 0;
512 else /* |w->tavl_balance == -1| */
513 x->tavl_balance = +1, y->tavl_balance = 0;
515 if (w->tavl_tag[0] == TAVL_THREAD)
517 y->tavl_tag[1] = TAVL_THREAD;
519 w->tavl_tag[0] = TAVL_CHILD;
521 if (w->tavl_tag[1] == TAVL_THREAD)
523 x->tavl_tag[0] = TAVL_THREAD;
525 w->tavl_tag[1] = TAVL_CHILD;
527 q->tavl_link[dir] = w;
531 q->tavl_link[dir] = x;
533 if (x->tavl_balance == 0)
535 y->tavl_link[1] = x->tavl_link[0];
537 x->tavl_balance = -1;
538 y->tavl_balance = +1;
541 else /* |x->tavl_balance == +1| */
543 if (x->tavl_tag[0] == TAVL_CHILD)
544 y->tavl_link[1] = x->tavl_link[0];
547 y->tavl_tag[1] = TAVL_THREAD;
548 x->tavl_tag[0] = TAVL_CHILD;
551 y->tavl_balance = x->tavl_balance = 0;
558 dir = q->tavl_link[0] != y;
560 if (y->tavl_balance == -1)
562 else if (y->tavl_balance == -2)
564 struct tavl_node *x = y->tavl_link[0];
566 if (x->tavl_balance == +1)
570 assert (x->tavl_balance == +1);
572 x->tavl_link[1] = w->tavl_link[0];
574 y->tavl_link[0] = w->tavl_link[1];
576 if (w->tavl_balance == -1)
577 x->tavl_balance = 0, y->tavl_balance = +1;
578 else if (w->tavl_balance == 0)
579 x->tavl_balance = y->tavl_balance = 0;
580 else /* |w->tavl_balance == +1| */
581 x->tavl_balance = -1, y->tavl_balance = 0;
583 if (w->tavl_tag[0] == TAVL_THREAD)
585 x->tavl_tag[1] = TAVL_THREAD;
587 w->tavl_tag[0] = TAVL_CHILD;
589 if (w->tavl_tag[1] == TAVL_THREAD)
591 y->tavl_tag[0] = TAVL_THREAD;
593 w->tavl_tag[1] = TAVL_CHILD;
595 q->tavl_link[dir] = w;
599 q->tavl_link[dir] = x;
601 if (x->tavl_balance == 0)
603 y->tavl_link[0] = x->tavl_link[1];
605 x->tavl_balance = +1;
606 y->tavl_balance = -1;
609 else /* |x->tavl_balance == -1| */
611 if (x->tavl_tag[1] == TAVL_CHILD)
612 y->tavl_link[0] = x->tavl_link[1];
615 y->tavl_tag[0] = TAVL_THREAD;
616 x->tavl_tag[1] = TAVL_CHILD;
619 y->tavl_balance = x->tavl_balance = 0;
627 return (void *) item;
630 /* Initializes |trav| for use with |tree|
631 and selects the null node. */
633 tavl_t_init (struct tavl_traverser *trav, struct tavl_table *tree)
635 trav->tavl_table = tree;
636 trav->tavl_node = NULL;
639 /* Initializes |trav| for |tree|.
640 Returns data item in |tree| with the least value,
641 or |NULL| if |tree| is empty. */
643 tavl_t_first (struct tavl_traverser *trav, struct tavl_table *tree)
645 assert (tree != NULL && trav != NULL);
647 trav->tavl_table = tree;
648 trav->tavl_node = tree->tavl_root;
649 if (trav->tavl_node != NULL)
651 while (trav->tavl_node->tavl_tag[0] == TAVL_CHILD)
652 trav->tavl_node = trav->tavl_node->tavl_link[0];
653 return trav->tavl_node->tavl_data;
659 /* Initializes |trav| for |tree|.
660 Returns data item in |tree| with the greatest value,
661 or |NULL| if |tree| is empty. */
663 tavl_t_last (struct tavl_traverser *trav, struct tavl_table *tree)
665 assert (tree != NULL && trav != NULL);
667 trav->tavl_table = tree;
668 trav->tavl_node = tree->tavl_root;
669 if (trav->tavl_node != NULL)
671 while (trav->tavl_node->tavl_tag[1] == TAVL_CHILD)
672 trav->tavl_node = trav->tavl_node->tavl_link[1];
673 return trav->tavl_node->tavl_data;
679 /* Searches for |item| in |tree|.
680 If found, initializes |trav| to the item found and returns the item
682 If there is no matching item, initializes |trav| to the null item
683 and returns |NULL|. */
685 tavl_t_find (struct tavl_traverser *trav, struct tavl_table *tree, void *item)
689 assert (trav != NULL && tree != NULL && item != NULL);
691 trav->tavl_table = tree;
692 trav->tavl_node = NULL;
702 cmp = tree->tavl_compare (item, p->tavl_data, tree->tavl_param);
710 if (p->tavl_tag[dir] == TAVL_CHILD)
711 p = p->tavl_link[dir];
717 /* Attempts to insert |item| into |tree|.
718 If |item| is inserted successfully, it is returned and |trav| is
719 initialized to its location.
720 If a duplicate is found, it is returned and |trav| is initialized to
721 its location. No replacement of the item occurs.
722 If a memory allocation failure occurs, |NULL| is returned and |trav|
723 is initialized to the null item. */
725 tavl_t_insert (struct tavl_traverser *trav,
726 struct tavl_table *tree, void *item)
730 assert (trav != NULL && tree != NULL && item != NULL);
732 p = tavl_probe (tree, item);
735 trav->tavl_table = tree;
737 ((struct tavl_node *)
738 ((char *) p - offsetof (struct tavl_node, tavl_data)));
743 tavl_t_init (trav, tree);
748 /* Initializes |trav| to have the same current node as |src|. */
750 tavl_t_copy (struct tavl_traverser *trav, const struct tavl_traverser *src)
752 assert (trav != NULL && src != NULL);
754 trav->tavl_table = src->tavl_table;
755 trav->tavl_node = src->tavl_node;
757 return trav->tavl_node != NULL ? trav->tavl_node->tavl_data : NULL;
760 /* Returns the next data item in inorder
761 within the tree being traversed with |trav|,
762 or if there are no more data items returns |NULL|. */
764 tavl_t_next (struct tavl_traverser *trav)
766 assert (trav != NULL);
768 if (trav->tavl_node == NULL)
769 return tavl_t_first (trav, trav->tavl_table);
770 else if (trav->tavl_node->tavl_tag[1] == TAVL_THREAD)
772 trav->tavl_node = trav->tavl_node->tavl_link[1];
773 return trav->tavl_node != NULL ? trav->tavl_node->tavl_data : NULL;
777 trav->tavl_node = trav->tavl_node->tavl_link[1];
778 while (trav->tavl_node->tavl_tag[0] == TAVL_CHILD)
779 trav->tavl_node = trav->tavl_node->tavl_link[0];
780 return trav->tavl_node->tavl_data;
784 /* Returns the previous data item in inorder
785 within the tree being traversed with |trav|,
786 or if there are no more data items returns |NULL|. */
788 tavl_t_prev (struct tavl_traverser *trav)
790 assert (trav != NULL);
792 if (trav->tavl_node == NULL)
793 return tavl_t_last (trav, trav->tavl_table);
794 else if (trav->tavl_node->tavl_tag[0] == TAVL_THREAD)
796 trav->tavl_node = trav->tavl_node->tavl_link[0];
797 return trav->tavl_node != NULL ? trav->tavl_node->tavl_data : NULL;
801 trav->tavl_node = trav->tavl_node->tavl_link[0];
802 while (trav->tavl_node->tavl_tag[1] == TAVL_CHILD)
803 trav->tavl_node = trav->tavl_node->tavl_link[1];
804 return trav->tavl_node->tavl_data;
808 /* Returns |trav|'s current item. */
810 tavl_t_cur (struct tavl_traverser *trav)
812 assert (trav != NULL);
814 return trav->tavl_node != NULL ? trav->tavl_node->tavl_data : NULL;
817 /* Replaces the current item in |trav| by |new| and returns the item replaced.
818 |trav| must not have the null item selected.
819 The new item must not upset the ordering of the tree. */
821 tavl_t_replace (struct tavl_traverser *trav, void *new)
825 assert (trav != NULL && trav->tavl_node != NULL && new != NULL);
826 old = trav->tavl_node->tavl_data;
827 trav->tavl_node->tavl_data = new;
831 /* Creates a new node as a child of |dst| on side |dir|.
832 Copies data and |tavl_balance| from |src| into the new node,
833 applying |copy()|, if non-null.
834 Returns nonzero only if fully successful.
835 Regardless of success, integrity of the tree structure is assured,
836 though failure may leave a null pointer in a |tavl_data| member. */
838 copy_node (struct tavl_table *tree,
839 struct tavl_node *dst, int dir,
840 const struct tavl_node *src, tavl_copy_func *copy)
842 struct tavl_node *new =
843 tree->tavl_alloc->libavl_malloc (tree->tavl_alloc, sizeof *new);
847 new->tavl_link[dir] = dst->tavl_link[dir];
848 new->tavl_tag[dir] = TAVL_THREAD;
849 new->tavl_link[!dir] = dst;
850 new->tavl_tag[!dir] = TAVL_THREAD;
851 dst->tavl_link[dir] = new;
852 dst->tavl_tag[dir] = TAVL_CHILD;
854 new->tavl_balance = src->tavl_balance;
856 new->tavl_data = src->tavl_data;
859 new->tavl_data = copy (src->tavl_data, tree->tavl_param);
860 if (new->tavl_data == NULL)
867 /* Destroys |new| with |tavl_destroy (new, destroy)|,
868 first initializing the right link in |new| that has
869 not yet been initialized. */
871 copy_error_recovery (struct tavl_node *p,
872 struct tavl_table *new, tavl_item_func *destroy)
877 while (p->tavl_tag[1] == TAVL_CHILD)
879 p->tavl_link[1] = NULL;
881 tavl_destroy (new, destroy);
884 /* Copies |org| to a newly created tree, which is returned.
885 If |copy != NULL|, each data item in |org| is first passed to |copy|,
886 and the return values are inserted into the tree,
887 with |NULL| return values taken as indications of failure.
888 On failure, destroys the partially created new tree,
889 applying |destroy|, if non-null, to each item in the new tree so far,
891 If |allocator != NULL|, it is used for allocation in the new tree.
892 Otherwise, the same allocator used for |org| is used. */
894 tavl_copy (const struct tavl_table *org, tavl_copy_func *copy,
895 tavl_item_func *destroy, struct libavl_allocator *allocator)
897 struct tavl_table *new;
899 const struct tavl_node *p;
901 struct tavl_node rp, rq;
903 assert (org != NULL);
904 new = tavl_create (org->tavl_compare, org->tavl_param,
905 allocator != NULL ? allocator : org->tavl_alloc);
909 new->tavl_count = org->tavl_count;
910 if (new->tavl_count == 0)
914 rp.tavl_link[0] = org->tavl_root;
915 rp.tavl_tag[0] = TAVL_CHILD;
918 rq.tavl_link[0] = NULL;
919 rq.tavl_tag[0] = TAVL_THREAD;
923 if (p->tavl_tag[0] == TAVL_CHILD)
925 if (!copy_node (new, q, 0, p->tavl_link[0], copy))
927 copy_error_recovery (rq.tavl_link[0], new, destroy);
936 while (p->tavl_tag[1] == TAVL_THREAD)
941 q->tavl_link[1] = NULL;
942 new->tavl_root = rq.tavl_link[0];
953 if (p->tavl_tag[1] == TAVL_CHILD)
954 if (!copy_node (new, q, 1, p->tavl_link[1], copy))
956 copy_error_recovery (rq.tavl_link[0], new, destroy);
962 /* Frees storage allocated for |tree|.
963 If |destroy != NULL|, applies it to each data item in inorder. */
965 tavl_destroy (struct tavl_table *tree, tavl_item_func *destroy)
967 struct tavl_node *p; /* Current node. */
968 struct tavl_node *n; /* Next node. */
972 while (p->tavl_tag[0] == TAVL_CHILD)
978 if (p->tavl_tag[1] == TAVL_CHILD)
979 while (n->tavl_tag[0] == TAVL_CHILD)
982 if (destroy != NULL && p->tavl_data != NULL)
983 destroy (p->tavl_data, tree->tavl_param);
984 tree->tavl_alloc->libavl_free (tree->tavl_alloc, p);
989 tree->tavl_alloc->libavl_free (tree->tavl_alloc, tree);
992 /* Allocates |size| bytes of space using |malloc()|.
993 Returns a null pointer if allocation fails. */
995 tavl_malloc (struct libavl_allocator *allocator, size_t size)
997 assert (allocator != NULL && size > 0);
998 return malloc (size);
1001 /* Frees |block|. */
1003 tavl_free (struct libavl_allocator *allocator, void *block)
1005 assert (allocator != NULL && block != NULL);
1009 /* Default memory allocator that uses |malloc()| and |free()|. */
1010 struct libavl_allocator tavl_allocator_default =
1019 /* Asserts that |tavl_insert()| succeeds at inserting |item| into |table|. */
1021 (tavl_assert_insert) (struct tavl_table *table, void *item)
1023 void **p = tavl_probe (table, item);
1024 assert (p != NULL && *p == item);
1027 /* Asserts that |tavl_delete()| really removes |item| from |table|,
1028 and returns the removed item. */
1030 (tavl_assert_delete) (struct tavl_table *table, void *item)
1032 void *p = tavl_delete (table, item);