www.delorie.com/gnu/docs/avl/libavl_239.html

search

	Buy GNU books!

GNU libavl 2.0.1

14.6 Copying

To copy BSTs with parent pointers, we use a simple adaptation of our original algorithm for copying BSTs, as implemented in <@xref{\NODE\, , \TITLE\}.>{BST copy function,83}. That function used a stack to keep track of the nodes that need to be revisited to have their right subtrees copies. We can eliminate that by using the parent pointers. Instead of popping a pair of nodes off the stack, we ascend the tree until we moved up to the left:

<@xref{\NODE\, , PBST copy error helper function.>,510} struct pbst_table * pbst_copy (const struct pbst_table *org, pbst_copy_func *copy, pbst_item_func *destroy, struct libavl_allocator *allocator) { struct pbst_table *new; const struct pbst_node *x; struct pbst_node *y; assert (org != NULL); new = pbst_create (org->pbst_compare, org->pbst_param, allocator != NULL ? allocator : org->pbst_alloc); if (new == NULL) return NULL; new->pbst_count = org->pbst_count; if (new->pbst_count == 0) return new; x = (const struct pbst_node *) &org->pbst_root; y = (struct pbst_node *) &new->pbst_root; for (;;) { while (x->pbst_link[0] != NULL) { y->pbst_link[0] = new->pbst_alloc->libavl_malloc (new->pbst_alloc, sizeof *y->pbst_link[0]); if (y->pbst_link[0] == NULL) { if (y != (struct pbst_node *) &new->pbst_root) { y->pbst_data = NULL; y->pbst_link[1] = NULL; } copy_error_recovery (y, new, destroy); return NULL; } y->pbst_link[0]->pbst_parent = y; x = x->pbst_link[0]; y = y->pbst_link[0]; } y->pbst_link[0] = NULL; for (;;) { if (copy == NULL) y->pbst_data = x->pbst_data; else { y->pbst_data = copy (x->pbst_data, org->pbst_param); if (y->pbst_data == NULL) { y->pbst_link[1] = NULL; copy_error_recovery (y, new, destroy); return NULL; } } if (x->pbst_link[1] != NULL) { y->pbst_link[1] = new->pbst_alloc->libavl_malloc (new->pbst_alloc, sizeof *y->pbst_link[1]); if (y->pbst_link[1] == NULL) { copy_error_recovery (y, new, destroy); return NULL; } y->pbst_link[1]->pbst_parent = y; x = x->pbst_link[1]; y = y->pbst_link[1]; break; } else y->pbst_link[1] = NULL; for (;;) { const struct pbst_node *w = x; x = x->pbst_parent; if (x == NULL) { new->pbst_root->pbst_parent = NULL; return new; } y = y->pbst_parent; if (w == x->pbst_link[0]) break; } } } }

This code is included in @refalso{489

Recovering from an error changes in the same way. We ascend from the node where we were copying when memory ran out and set the right children of the nodes where we ascended to the right to null pointers, then destroy the fixed-up tree:

static void copy_error_recovery (struct pbst_node *q, struct pbst_table *new, pbst_item_func *destroy) { assert (q != NULL && new != NULL); for (;;) { struct pbst_node *p = q; q = q->pbst_parent; if (q == NULL) break; if (p == q->pbst_link[0]) q->pbst_link[1] = NULL; } pbst_destroy (new, destroy); }

This code is included in @refalso{509