Geografic-Information-System/lib/vector/dglib/tavl.c

/* Produced by texiweb from libavl.w on 2002/02/09 at 01:45. */

/* libavl - library for manipulation of binary trees.
   Copyright (C) 1998-2002 Free Software Foundation, Inc.

   This program is free software; you can redistribute it and/or
   modify it under the terms of the GNU General Public License as
   published by the Free Software Foundation; either version 2 of the
   License, or (at your option) any later version.

   This program is distributed in the hope that it will be useful, but
   WITHOUT ANY WARRANTY; without even the implied warranty of
   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
   See the GNU General Public License for more details.

   You should have received a copy of the GNU General Public License
   along with this program; if not, write to the Free Software
   Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA
   02111-1307, USA.

   The author may be contacted at <blp@gnu.org> on the Internet, or
   as Ben Pfaff, 12167 Airport Rd, DeWitt MI 48820, USA through more
   mundane means.
 */

#include <assert.h>
#include <stdio.h>
#include <stdlib.h>
#include "tavl.h"

/* Creates and returns a new table
   with comparison function |compare| using parameter |param|
   and memory allocator |allocator|.
   Returns |NULL| if memory allocation failed. */
struct tavl_table *tavl_create(tavl_comparison_func * compare, void *param,
			       struct libavl_allocator *allocator)
{
    struct tavl_table *tree;

    assert(compare != NULL);

    if (allocator == NULL)
	allocator = &tavl_allocator_default;

    tree = allocator->libavl_malloc(allocator, sizeof *tree);
    if (tree == NULL)
	return NULL;

    tree->tavl_root = NULL;
    tree->tavl_compare = compare;
    tree->tavl_param = param;
    tree->tavl_alloc = allocator;
    tree->tavl_count = 0;

    return tree;
}

/* Search |tree| for an item matching |item|, and return it if found.
   Otherwise return |NULL|. */
void *tavl_find(const struct tavl_table *tree, const void *item)
{
    const struct tavl_node *p;

    assert(tree != NULL && item != NULL);

    p = tree->tavl_root;
    if (p == NULL)
	return NULL;

    for (;;) {
	int cmp, dir;

	cmp = tree->tavl_compare(item, p->tavl_data, tree->tavl_param);
	if (cmp == 0)
	    return p->tavl_data;

	dir = cmp > 0;
	if (p->tavl_tag[dir] == TAVL_CHILD)
	    p = p->tavl_link[dir];
	else
	    return NULL;
    }
}

/* Inserts |item| into |tree| and returns a pointer to |item|'s address.
   If a duplicate item is found in the tree,
   returns a pointer to the duplicate without inserting |item|.
   Returns |NULL| in case of memory allocation failure. */
void **tavl_probe(struct tavl_table *tree, void *item)
{
    struct tavl_node *y, *z;	/* Top node to update balance factor, and parent. */
    struct tavl_node *p, *q;	/* Iterator, and parent. */
    struct tavl_node *n;	/* Newly inserted node. */
    struct tavl_node *w;	/* New root of rebalanced subtree. */
    int dir;			/* Direction to descend. */

    unsigned char da[TAVL_MAX_HEIGHT];	/* Cached comparison results. */
    int k = 0;			/* Number of cached results. */

    assert(tree != NULL && item != NULL);

    z = (struct tavl_node *)&tree->tavl_root;
    y = tree->tavl_root;
    if (y != NULL) {
	for (q = z, p = y;; q = p, p = p->tavl_link[dir]) {
	    int cmp =
		tree->tavl_compare(item, p->tavl_data, tree->tavl_param);
	    if (cmp == 0)
		return &p->tavl_data;

	    if (p->tavl_balance != 0)
		z = q, y = p, k = 0;
	    da[k++] = dir = cmp > 0;

	    if (p->tavl_tag[dir] == TAVL_THREAD)
		break;
	}
    }
    else {
	p = z;
	dir = 0;
    }

    n = tree->tavl_alloc->libavl_malloc(tree->tavl_alloc, sizeof *n);
    if (n == NULL)
	return NULL;

    tree->tavl_count++;
    n->tavl_data = item;
    n->tavl_tag[0] = n->tavl_tag[1] = TAVL_THREAD;
    n->tavl_link[dir] = p->tavl_link[dir];
    if (tree->tavl_root != NULL) {
	p->tavl_tag[dir] = TAVL_CHILD;
	n->tavl_link[!dir] = p;
    }
    else
	n->tavl_link[1] = NULL;
    p->tavl_link[dir] = n;
    n->tavl_balance = 0;
    if (tree->tavl_root == n)
	return &n->tavl_data;

    for (p = y, k = 0; p != n; p = p->tavl_link[da[k]], k++)
	if (da[k] == 0)
	    p->tavl_balance--;
	else
	    p->tavl_balance++;

    if (y->tavl_balance == -2) {
	struct tavl_node *x = y->tavl_link[0];

	if (x->tavl_balance == -1) {
	    w = x;
	    if (x->tavl_tag[1] == TAVL_THREAD) {
		x->tavl_tag[1] = TAVL_CHILD;
		y->tavl_tag[0] = TAVL_THREAD;
		y->tavl_link[0] = x;
	    }
	    else
		y->tavl_link[0] = x->tavl_link[1];
	    x->tavl_link[1] = y;
	    x->tavl_balance = y->tavl_balance = 0;
	}
	else {
	    assert(x->tavl_balance == +1);
	    w = x->tavl_link[1];
	    x->tavl_link[1] = w->tavl_link[0];
	    w->tavl_link[0] = x;
	    y->tavl_link[0] = w->tavl_link[1];
	    w->tavl_link[1] = y;
	    if (w->tavl_balance == -1)
		x->tavl_balance = 0, y->tavl_balance = +1;
	    else if (w->tavl_balance == 0)
		x->tavl_balance = y->tavl_balance = 0;
	    else		/* |w->tavl_balance == +1| */
		x->tavl_balance = -1, y->tavl_balance = 0;
	    w->tavl_balance = 0;
	    if (w->tavl_tag[0] == TAVL_THREAD) {
		x->tavl_tag[1] = TAVL_THREAD;
		x->tavl_link[1] = w;
		w->tavl_tag[0] = TAVL_CHILD;
	    }
	    if (w->tavl_tag[1] == TAVL_THREAD) {
		y->tavl_tag[0] = TAVL_THREAD;
		y->tavl_link[0] = w;
		w->tavl_tag[1] = TAVL_CHILD;
	    }
	}
    }
    else if (y->tavl_balance == +2) {
	struct tavl_node *x = y->tavl_link[1];

	if (x->tavl_balance == +1) {
	    w = x;
	    if (x->tavl_tag[0] == TAVL_THREAD) {
		x->tavl_tag[0] = TAVL_CHILD;
		y->tavl_tag[1] = TAVL_THREAD;
		y->tavl_link[1] = x;
	    }
	    else
		y->tavl_link[1] = x->tavl_link[0];
	    x->tavl_link[0] = y;
	    x->tavl_balance = y->tavl_balance = 0;
	}
	else {
	    assert(x->tavl_balance == -1);
	    w = x->tavl_link[0];
	    x->tavl_link[0] = w->tavl_link[1];
	    w->tavl_link[1] = x;
	    y->tavl_link[1] = w->tavl_link[0];
	    w->tavl_link[0] = y;
	    if (w->tavl_balance == +1)
		x->tavl_balance = 0, y->tavl_balance = -1;
	    else if (w->tavl_balance == 0)
		x->tavl_balance = y->tavl_balance = 0;
	    else		/* |w->tavl_balance == -1| */
		x->tavl_balance = +1, y->tavl_balance = 0;
	    w->tavl_balance = 0;
	    if (w->tavl_tag[0] == TAVL_THREAD) {
		y->tavl_tag[1] = TAVL_THREAD;
		y->tavl_link[1] = w;
		w->tavl_tag[0] = TAVL_CHILD;
	    }
	    if (w->tavl_tag[1] == TAVL_THREAD) {
		x->tavl_tag[0] = TAVL_THREAD;
		x->tavl_link[0] = w;
		w->tavl_tag[1] = TAVL_CHILD;
	    }
	}
    }
    else
	return &n->tavl_data;
    z->tavl_link[y != z->tavl_link[0]] = w;

    return &n->tavl_data;
}

/* Inserts |item| into |table|.
   Returns |NULL| if |item| was successfully inserted
   or if a memory allocation error occurred.
   Otherwise, returns the duplicate item. */
void *tavl_insert(struct tavl_table *table, void *item)
{
    void **p = tavl_probe(table, item);

    return p == NULL || *p == item ? NULL : *p;
}

/* Inserts |item| into |table|, replacing any duplicate item.
   Returns |NULL| if |item| was inserted without replacing a duplicate,
   or if a memory allocation error occurred.
   Otherwise, returns the item that was replaced. */
void *tavl_replace(struct tavl_table *table, void *item)
{
    void **p = tavl_probe(table, item);

    if (p == NULL || *p == item)
	return NULL;
    else {
	void *r = *p;

	*p = item;
	return r;
    }
}

/* Returns the parent of |node| within |tree|,
   or a pointer to |tavl_root| if |s| is the root of the tree. */
static struct tavl_node *find_parent(struct tavl_table *tree,
				     struct tavl_node *node)
{
    if (node != tree->tavl_root) {
	struct tavl_node *x, *y;

	for (x = y = node;; x = x->tavl_link[0], y = y->tavl_link[1])
	    if (y->tavl_tag[1] == TAVL_THREAD) {
		struct tavl_node *p = y->tavl_link[1];

		if (p == NULL || p->tavl_link[0] != node) {
		    while (x->tavl_tag[0] == TAVL_CHILD)
			x = x->tavl_link[0];
		    p = x->tavl_link[0];
		}
		return p;
	    }
	    else if (x->tavl_tag[0] == TAVL_THREAD) {
		struct tavl_node *p = x->tavl_link[0];

		if (p == NULL || p->tavl_link[1] != node) {
		    while (y->tavl_tag[1] == TAVL_CHILD)
			y = y->tavl_link[1];
		    p = y->tavl_link[1];
		}
		return p;
	    }
    }
    else
	return (struct tavl_node *)&tree->tavl_root;
}

/* Deletes from |tree| and returns an item matching |item|.
   Returns a null pointer if no matching item found. */
void *tavl_delete(struct tavl_table *tree, const void *item)
{
    struct tavl_node *p;	/* Traverses tree to find node to delete. */
    struct tavl_node *q;	/* Parent of |p|. */
    int dir;			/* Index into |q->tavl_link[]| to get |p|. */
    int cmp;			/* Result of comparison between |item| and |p|. */

    assert(tree != NULL && item != NULL);

    if (tree->tavl_root == NULL)
	return NULL;

    p = (struct tavl_node *)&tree->tavl_root;
    for (cmp = -1; cmp != 0;
	 cmp = tree->tavl_compare(item, p->tavl_data, tree->tavl_param)) {
	dir = cmp > 0;

	q = p;
	if (p->tavl_tag[dir] == TAVL_THREAD)
	    return NULL;
	p = p->tavl_link[dir];
    }
    item = p->tavl_data;

    if (p->tavl_tag[1] == TAVL_THREAD) {
	if (p->tavl_tag[0] == TAVL_CHILD) {
	    struct tavl_node *t = p->tavl_link[0];

	    while (t->tavl_tag[1] == TAVL_CHILD)
		t = t->tavl_link[1];
	    t->tavl_link[1] = p->tavl_link[1];
	    q->tavl_link[dir] = p->tavl_link[0];
	}
	else {
	    q->tavl_link[dir] = p->tavl_link[dir];
	    if (q != (struct tavl_node *)&tree->tavl_root)
		q->tavl_tag[dir] = TAVL_THREAD;
	}
    }
    else {
	struct tavl_node *r = p->tavl_link[1];

	if (r->tavl_tag[0] == TAVL_THREAD) {
	    r->tavl_link[0] = p->tavl_link[0];
	    r->tavl_tag[0] = p->tavl_tag[0];
	    if (r->tavl_tag[0] == TAVL_CHILD) {
		struct tavl_node *t = r->tavl_link[0];

		while (t->tavl_tag[1] == TAVL_CHILD)
		    t = t->tavl_link[1];
		t->tavl_link[1] = r;
	    }
	    q->tavl_link[dir] = r;
	    r->tavl_balance = p->tavl_balance;
	    q = r;
	    dir = 1;
	}
	else {
	    struct tavl_node *s;

	    for (;;) {
		s = r->tavl_link[0];
		if (s->tavl_tag[0] == TAVL_THREAD)
		    break;

		r = s;
	    }

	    if (s->tavl_tag[1] == TAVL_CHILD)
		r->tavl_link[0] = s->tavl_link[1];
	    else {
		r->tavl_link[0] = s;
		r->tavl_tag[0] = TAVL_THREAD;
	    }

	    s->tavl_link[0] = p->tavl_link[0];
	    if (p->tavl_tag[0] == TAVL_CHILD) {
		struct tavl_node *t = p->tavl_link[0];

		while (t->tavl_tag[1] == TAVL_CHILD)
		    t = t->tavl_link[1];
		t->tavl_link[1] = s;

		s->tavl_tag[0] = TAVL_CHILD;
	    }

	    s->tavl_link[1] = p->tavl_link[1];
	    s->tavl_tag[1] = TAVL_CHILD;

	    q->tavl_link[dir] = s;
	    s->tavl_balance = p->tavl_balance;
	    q = r;
	    dir = 0;
	}
    }

    tree->tavl_alloc->libavl_free(tree->tavl_alloc, p);

    while (q != (struct tavl_node *)&tree->tavl_root) {
	struct tavl_node *y = q;

	q = find_parent(tree, y);

	if (dir == 0) {
	    dir = q->tavl_link[0] != y;
	    y->tavl_balance++;
	    if (y->tavl_balance == +1)
		break;
	    else if (y->tavl_balance == +2) {
		struct tavl_node *x = y->tavl_link[1];

		assert(x != NULL);
		if (x->tavl_balance == -1) {
		    struct tavl_node *w;

		    assert(x->tavl_balance == -1);
		    w = x->tavl_link[0];
		    x->tavl_link[0] = w->tavl_link[1];
		    w->tavl_link[1] = x;
		    y->tavl_link[1] = w->tavl_link[0];
		    w->tavl_link[0] = y;
		    if (w->tavl_balance == +1)
			x->tavl_balance = 0, y->tavl_balance = -1;
		    else if (w->tavl_balance == 0)
			x->tavl_balance = y->tavl_balance = 0;
		    else	/* |w->tavl_balance == -1| */
			x->tavl_balance = +1, y->tavl_balance = 0;
		    w->tavl_balance = 0;
		    if (w->tavl_tag[0] == TAVL_THREAD) {
			y->tavl_tag[1] = TAVL_THREAD;
			y->tavl_link[1] = w;
			w->tavl_tag[0] = TAVL_CHILD;
		    }
		    if (w->tavl_tag[1] == TAVL_THREAD) {
			x->tavl_tag[0] = TAVL_THREAD;
			x->tavl_link[0] = w;
			w->tavl_tag[1] = TAVL_CHILD;
		    }
		    q->tavl_link[dir] = w;
		}
		else {
		    q->tavl_link[dir] = x;

		    if (x->tavl_balance == 0) {
			y->tavl_link[1] = x->tavl_link[0];
			x->tavl_link[0] = y;
			x->tavl_balance = -1;
			y->tavl_balance = +1;
			break;
		    }
		    else {	/* |x->tavl_balance == +1| */

			if (x->tavl_tag[0] == TAVL_CHILD)
			    y->tavl_link[1] = x->tavl_link[0];
			else {
			    y->tavl_tag[1] = TAVL_THREAD;
			    x->tavl_tag[0] = TAVL_CHILD;
			}
			x->tavl_link[0] = y;
			y->tavl_balance = x->tavl_balance = 0;
		    }
		}
	    }
	}
	else {
	    dir = q->tavl_link[0] != y;
	    y->tavl_balance--;
	    if (y->tavl_balance == -1)
		break;
	    else if (y->tavl_balance == -2) {
		struct tavl_node *x = y->tavl_link[0];

		assert(x != NULL);
		if (x->tavl_balance == +1) {
		    struct tavl_node *w;

		    assert(x->tavl_balance == +1);
		    w = x->tavl_link[1];
		    x->tavl_link[1] = w->tavl_link[0];
		    w->tavl_link[0] = x;
		    y->tavl_link[0] = w->tavl_link[1];
		    w->tavl_link[1] = y;
		    if (w->tavl_balance == -1)
			x->tavl_balance = 0, y->tavl_balance = +1;
		    else if (w->tavl_balance == 0)
			x->tavl_balance = y->tavl_balance = 0;
		    else	/* |w->tavl_balance == +1| */
			x->tavl_balance = -1, y->tavl_balance = 0;
		    w->tavl_balance = 0;
		    if (w->tavl_tag[0] == TAVL_THREAD) {
			x->tavl_tag[1] = TAVL_THREAD;
			x->tavl_link[1] = w;
			w->tavl_tag[0] = TAVL_CHILD;
		    }
		    if (w->tavl_tag[1] == TAVL_THREAD) {
			y->tavl_tag[0] = TAVL_THREAD;
			y->tavl_link[0] = w;
			w->tavl_tag[1] = TAVL_CHILD;
		    }
		    q->tavl_link[dir] = w;
		}
		else {
		    q->tavl_link[dir] = x;

		    if (x->tavl_balance == 0) {
			y->tavl_link[0] = x->tavl_link[1];
			x->tavl_link[1] = y;
			x->tavl_balance = +1;
			y->tavl_balance = -1;
			break;
		    }
		    else {	/* |x->tavl_balance == -1| */

			if (x->tavl_tag[1] == TAVL_CHILD)
			    y->tavl_link[0] = x->tavl_link[1];
			else {
			    y->tavl_tag[0] = TAVL_THREAD;
			    x->tavl_tag[1] = TAVL_CHILD;
			}
			x->tavl_link[1] = y;
			y->tavl_balance = x->tavl_balance = 0;
		    }
		}
	    }
	}
    }

    tree->tavl_count--;
    return (void *)item;
}

/* Initializes |trav| for use with |tree|
   and selects the null node. */
void tavl_t_init(struct tavl_traverser *trav, struct tavl_table *tree)
{
    trav->tavl_table = tree;
    trav->tavl_node = NULL;
}

/* Initializes |trav| for |tree|.
   Returns data item in |tree| with the least value,
   or |NULL| if |tree| is empty. */
void *tavl_t_first(struct tavl_traverser *trav, struct tavl_table *tree)
{
    assert(tree != NULL && trav != NULL);

    trav->tavl_table = tree;
    trav->tavl_node = tree->tavl_root;
    if (trav->tavl_node != NULL) {
	while (trav->tavl_node->tavl_tag[0] == TAVL_CHILD)
	    trav->tavl_node = trav->tavl_node->tavl_link[0];
	return trav->tavl_node->tavl_data;
    }
    else
	return NULL;
}

/* Initializes |trav| for |tree|.
   Returns data item in |tree| with the greatest value,
   or |NULL| if |tree| is empty. */
void *tavl_t_last(struct tavl_traverser *trav, struct tavl_table *tree)
{
    assert(tree != NULL && trav != NULL);

    trav->tavl_table = tree;
    trav->tavl_node = tree->tavl_root;
    if (trav->tavl_node != NULL) {
	while (trav->tavl_node->tavl_tag[1] == TAVL_CHILD)
	    trav->tavl_node = trav->tavl_node->tavl_link[1];
	return trav->tavl_node->tavl_data;
    }
    else
	return NULL;
}

/* Searches for |item| in |tree|.
   If found, initializes |trav| to the item found and returns the item
   as well.
   If there is no matching item, initializes |trav| to the null item
   and returns |NULL|. */
void *tavl_t_find(struct tavl_traverser *trav, struct tavl_table *tree,
		  void *item)
{
    struct tavl_node *p;

    assert(trav != NULL && tree != NULL && item != NULL);

    trav->tavl_table = tree;
    trav->tavl_node = NULL;

    p = tree->tavl_root;
    if (p == NULL)
	return NULL;

    for (;;) {
	int cmp, dir;

	cmp = tree->tavl_compare(item, p->tavl_data, tree->tavl_param);
	if (cmp == 0) {
	    trav->tavl_node = p;
	    return p->tavl_data;
	}

	dir = cmp > 0;
	if (p->tavl_tag[dir] == TAVL_CHILD)
	    p = p->tavl_link[dir];
	else
	    return NULL;
    }
}

/* Attempts to insert |item| into |tree|.
   If |item| is inserted successfully, it is returned and |trav| is
   initialized to its location.
   If a duplicate is found, it is returned and |trav| is initialized to
   its location.  No replacement of the item occurs.
   If a memory allocation failure occurs, |NULL| is returned and |trav|
   is initialized to the null item. */
void *tavl_t_insert(struct tavl_traverser *trav,
		    struct tavl_table *tree, void *item)
{
    void **p;

    assert(trav != NULL && tree != NULL && item != NULL);

    p = tavl_probe(tree, item);
    if (p != NULL) {
	trav->tavl_table = tree;
	trav->tavl_node = ((struct tavl_node *)
			   ((char *)p -
			    offsetof(struct tavl_node, tavl_data)));
	return *p;
    }
    else {
	tavl_t_init(trav, tree);
	return NULL;
    }
}

/* Initializes |trav| to have the same current node as |src|. */
void *tavl_t_copy(struct tavl_traverser *trav,
		  const struct tavl_traverser *src)
{
    assert(trav != NULL && src != NULL);

    trav->tavl_table = src->tavl_table;
    trav->tavl_node = src->tavl_node;

    return trav->tavl_node != NULL ? trav->tavl_node->tavl_data : NULL;
}

/* Returns the next data item in inorder
   within the tree being traversed with |trav|,
   or if there are no more data items returns |NULL|. */
void *tavl_t_next(struct tavl_traverser *trav)
{
    assert(trav != NULL);

    if (trav->tavl_node == NULL)
	return tavl_t_first(trav, trav->tavl_table);
    else if (trav->tavl_node->tavl_tag[1] == TAVL_THREAD) {
	trav->tavl_node = trav->tavl_node->tavl_link[1];
	return trav->tavl_node != NULL ? trav->tavl_node->tavl_data : NULL;
    }
    else {
	trav->tavl_node = trav->tavl_node->tavl_link[1];
	while (trav->tavl_node->tavl_tag[0] == TAVL_CHILD)
	    trav->tavl_node = trav->tavl_node->tavl_link[0];
	return trav->tavl_node->tavl_data;
    }
}

/* Returns the previous data item in inorder
   within the tree being traversed with |trav|,
   or if there are no more data items returns |NULL|. */
void *tavl_t_prev(struct tavl_traverser *trav)
{
    assert(trav != NULL);

    if (trav->tavl_node == NULL)
	return tavl_t_last(trav, trav->tavl_table);
    else if (trav->tavl_node->tavl_tag[0] == TAVL_THREAD) {
	trav->tavl_node = trav->tavl_node->tavl_link[0];
	return trav->tavl_node != NULL ? trav->tavl_node->tavl_data : NULL;
    }
    else {
	trav->tavl_node = trav->tavl_node->tavl_link[0];
	while (trav->tavl_node->tavl_tag[1] == TAVL_CHILD)
	    trav->tavl_node = trav->tavl_node->tavl_link[1];
	return trav->tavl_node->tavl_data;
    }
}

/* Returns |trav|'s current item. */
void *tavl_t_cur(struct tavl_traverser *trav)
{
    assert(trav != NULL);

    return trav->tavl_node != NULL ? trav->tavl_node->tavl_data : NULL;
}

/* Replaces the current item in |trav| by |new| and returns the item replaced.
   |trav| must not have the null item selected.
   The new item must not upset the ordering of the tree. */
void *tavl_t_replace(struct tavl_traverser *trav, void *new)
{
    struct tavl_node *old;

    assert(trav != NULL && trav->tavl_node != NULL && new != NULL);
    old = trav->tavl_node->tavl_data;
    trav->tavl_node->tavl_data = new;
    return old;
}

/* Creates a new node as a child of |dst| on side |dir|.
   Copies data and |tavl_balance| from |src| into the new node,
   applying |copy()|, if non-null.
   Returns nonzero only if fully successful.
   Regardless of success, integrity of the tree structure is assured,
   though failure may leave a null pointer in a |tavl_data| member. */
static int
copy_node(struct tavl_table *tree,
	  struct tavl_node *dst, int dir,
	  const struct tavl_node *src, tavl_copy_func * copy)
{
    struct tavl_node *new =
	tree->tavl_alloc->libavl_malloc(tree->tavl_alloc, sizeof *new);
    if (new == NULL)
	return 0;

    new->tavl_link[dir] = dst->tavl_link[dir];
    new->tavl_tag[dir] = TAVL_THREAD;
    new->tavl_link[!dir] = dst;
    new->tavl_tag[!dir] = TAVL_THREAD;
    dst->tavl_link[dir] = new;
    dst->tavl_tag[dir] = TAVL_CHILD;

    new->tavl_balance = src->tavl_balance;
    if (copy == NULL)
	new->tavl_data = src->tavl_data;
    else {
	new->tavl_data = copy(src->tavl_data, tree->tavl_param);
	if (new->tavl_data == NULL)
	    return 0;
    }

    return 1;
}

static void
copy_error_recovery(struct tavl_node *p,
		    struct tavl_table *new, tavl_item_func * destroy)
{
    new->tavl_root = p;
    if (p != NULL) {
	while (p->tavl_tag[1] == TAVL_CHILD)
	    p = p->tavl_link[1];
	p->tavl_link[1] = NULL;
    }
    tavl_destroy(new, destroy);
}

/* Copies |org| to a newly created tree, which is returned.
   If |copy != NULL|, each data item in |org| is first passed to |copy|,
   and the return values are inserted into the tree,
   with |NULL| return values taken as indications of failure.
   On failure, destroys the partially created new tree,
   applying |destroy|, if non-null, to each item in the new tree so far,
   and returns |NULL|.
   If |allocator != NULL|, it is used for allocation in the new tree.
   Otherwise, the same allocator used for |org| is used. */
struct tavl_table *tavl_copy(const struct tavl_table *org,
			     tavl_copy_func * copy, tavl_item_func * destroy,
			     struct libavl_allocator *allocator)
{
    struct tavl_table *new;

    const struct tavl_node *p;
    struct tavl_node *q;
    struct tavl_node rp, rq;

    assert(org != NULL);
    new = tavl_create(org->tavl_compare, org->tavl_param,
		      allocator != NULL ? allocator : org->tavl_alloc);
    if (new == NULL)
	return NULL;

    new->tavl_count = org->tavl_count;
    if (new->tavl_count == 0)
	return new;

    p = &rp;
    rp.tavl_link[0] = org->tavl_root;
    rp.tavl_tag[0] = TAVL_CHILD;

    q = &rq;
    rq.tavl_link[0] = NULL;
    rq.tavl_tag[0] = TAVL_THREAD;

    for (;;) {
	if (p->tavl_tag[0] == TAVL_CHILD) {
	    if (!copy_node(new, q, 0, p->tavl_link[0], copy)) {
		copy_error_recovery(rq.tavl_link[0], new, destroy);
		return NULL;
	    }

	    p = p->tavl_link[0];
	    q = q->tavl_link[0];
	}
	else {
	    while (p->tavl_tag[1] == TAVL_THREAD) {
		p = p->tavl_link[1];
		if (p == NULL) {
		    q->tavl_link[1] = NULL;
		    new->tavl_root = rq.tavl_link[0];
		    return new;
		}

		q = q->tavl_link[1];
	    }

	    p = p->tavl_link[1];
	    q = q->tavl_link[1];
	}

	if (p->tavl_tag[1] == TAVL_CHILD)
	    if (!copy_node(new, q, 1, p->tavl_link[1], copy)) {
		copy_error_recovery(rq.tavl_link[0], new, destroy);
		return NULL;
	    }
    }
}

/* Frees storage allocated for |tree|.
   If |destroy != NULL|, applies it to each data item in inorder. */
void tavl_destroy(struct tavl_table *tree, tavl_item_func * destroy)
{
    struct tavl_node *p;	/* Current node. */
    struct tavl_node *n;	/* Next node. */

    p = tree->tavl_root;
    if (p != NULL)
	while (p->tavl_tag[0] == TAVL_CHILD)
	    p = p->tavl_link[0];

    while (p != NULL) {
	n = p->tavl_link[1];
	if (p->tavl_tag[1] == TAVL_CHILD)
	    while (n->tavl_tag[0] == TAVL_CHILD)
		n = n->tavl_link[0];

	if (destroy != NULL && p->tavl_data != NULL)
	    destroy(p->tavl_data, tree->tavl_param);
	tree->tavl_alloc->libavl_free(tree->tavl_alloc, p);

	p = n;
    }

    tree->tavl_alloc->libavl_free(tree->tavl_alloc, tree);
}

/* Allocates |size| bytes of space using |malloc()|.
   Returns a null pointer if allocation fails. */
void *tavl_malloc(struct libavl_allocator *allocator, size_t size)
{
    assert(allocator != NULL && size > 0);
    return malloc(size);
}

/* Frees |block|. */
void tavl_free(struct libavl_allocator *allocator, void *block)
{
    assert(allocator != NULL && block != NULL);
    free(block);
}

/* Default memory allocator that uses |malloc()| and |free()|. */
struct libavl_allocator tavl_allocator_default = {
    tavl_malloc,
    tavl_free
};

/* Asserts that |tavl_insert()| succeeds at inserting |item| into |table|. */
void (tavl_assert_insert) (struct tavl_table * table, void *item)
{
    void **p = tavl_probe(table, item);

    assert(p != NULL && *p == item);
}

/* Asserts that |tavl_delete()| really removes |item| from |table|,
   and returns the removed item. */
void *(tavl_assert_delete) (struct tavl_table * table, void *item)
{
    void *p = tavl_delete(table, item);

    assert(p != NULL);
    return p;
}