| | <@xref{\NODE\, , BST copy error helper function; bst =>.> avl,82}
struct avl_table *
avl_copy (const struct avl_table *org, avl_copy_func *copy,
avl_item_func *destroy, struct libavl_allocator *allocator)
{
struct avl_node *stack[2 * (AVL_MAX_HEIGHT + 1)];
int height = 0;
struct avl_table *new;
const struct avl_node *x;
struct avl_node *y;
assert (org != NULL);
new = avl_create (org->avl_compare, org->avl_param,
allocator != NULL ? allocator : org->avl_alloc);
if (new == NULL)
return NULL;
new->avl_count = org->avl_count;
if (new->avl_count == 0)
return new;
x = (const struct avl_node *) &org->avl_root;
y = (struct avl_node *) &new->avl_root;
for (;;)
{
while (x->avl_link[0] != NULL)
{
assert (height < 2 * (AVL_MAX_HEIGHT + 1));
y->avl_link[0] =
new->avl_alloc->libavl_malloc (new->avl_alloc,
sizeof *y->avl_link[0]);
if (y->avl_link[0] == NULL)
{
if (y != (struct avl_node *) &new->avl_root)
{
y->avl_data = NULL;
y->avl_link[1] = NULL;
}
copy_error_recovery (stack, height, new, destroy);
return NULL;
}
stack[height++] = (struct avl_node *) x;
stack[height++] = y;
x = x->avl_link[0];
y = y->avl_link[0];
}
y->avl_link[0] = NULL;
for (;;)
{
y->avl_balance = x->avl_balance;
if (copy == NULL)
y->avl_data = x->avl_data;
else
{
y->avl_data = copy (x->avl_data, org->avl_param);
if (y->avl_data == NULL)
{
y->avl_link[1] = NULL;
copy_error_recovery (stack, height, new, destroy);
return NULL;
}
}
if (x->avl_link[1] != NULL)
{
y->avl_link[1] =
new->avl_alloc->libavl_malloc (new->avl_alloc,
sizeof *y->avl_link[1]);
if (y->avl_link[1] == NULL)
{
copy_error_recovery (stack, height, new, destroy);
return NULL;
}
x = x->avl_link[1];
y = y->avl_link[1];
break;
}
else
y->avl_link[1] = NULL;
if (height <= 2)
return new;
y = stack[--height];
x = stack[--height];
}
}
}
|
