/* Destroys |new| with |bst_destroy (new, destroy)|, first setting right links of nodes in |stack| within |new| to null pointers to avoid touching uninitialized data. */ static void copy_error_recovery (struct bst_node **stack, int height, struct bst_table *new, bst_item_func *destroy) { assert (stack != NULL && height >= 0 && new != NULL); for (; height > 2; height -= 2) stack[height - 1]->bst_link[1] = NULL; bst_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 bst_table * bst_copy (const struct bst_table *org, bst_copy_func *copy, bst_item_func *destroy, struct libavl_allocator *allocator) { struct bst_node *stack[2 * (BST_MAX_HEIGHT + 1)]; int height = 0; struct bst_table *new; const struct bst_node *x; struct bst_node *y; assert (org != NULL); new = bst_create (org->bst_compare, org->bst_param, allocator != NULL ? allocator : org->bst_alloc); if (new == NULL) return NULL; new->bst_count = org->bst_count; if (new->bst_count == 0) return new; x = (const struct bst_node *) &org->bst_root; y = (struct bst_node *) &new->bst_root; for (;;) { while (x->bst_link[0] != NULL) { if (height >= 2 * (BST_MAX_HEIGHT + 1)) { y->bst_data = NULL; y->bst_link[0] = y->bst_link[1] = NULL; copy_error_recovery (stack, height, new, destroy); bst_balance ((struct bst_table *) org); return bst_copy (org, copy, destroy, allocator); } y->bst_link[0] = new->bst_alloc->libavl_malloc (new->bst_alloc, sizeof *y->bst_link[0]); if (y->bst_link[0] == NULL) { if (y != (struct bst_node *) &new->bst_root) { y->bst_data = NULL; y->bst_link[1] = NULL; } copy_error_recovery (stack, height, new, destroy); return NULL; } stack[height++] = (struct bst_node *) x; stack[height++] = y; x = x->bst_link[0]; y = y->bst_link[0]; } y->bst_link[0] = NULL; for (;;) { if (copy == NULL) y->bst_data = x->bst_data; else { y->bst_data = copy (x->bst_data, org->bst_param); if (y->bst_data == NULL) { y->bst_link[1] = NULL; copy_error_recovery (stack, height, new, destroy); return NULL; } } if (x->bst_link[1] != NULL) { y->bst_link[1] = new->bst_alloc->libavl_malloc (new->bst_alloc, sizeof *y->bst_link[1]); if (y->bst_link[1] == NULL) { copy_error_recovery (stack, height, new, destroy); return NULL; } x = x->bst_link[1]; y = y->bst_link[1]; break; } else y->bst_link[1] = NULL; if (height <= 2) return new; y = stack[--height]; x = stack[--height]; } } }