/* Creates a new node as a child of |dst| on side |dir|. Copies data 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 |tbst_data| member. */ static int copy_node (struct tbst_table *tree, struct tbst_node *dst, int dir, const struct tbst_node *src, tbst_copy_func *copy) { struct tbst_node *new = tree->tbst_alloc->libavl_malloc (tree->tbst_alloc, sizeof *new); if (new == NULL) return 0; new->tbst_link[dir] = dst->tbst_link[dir]; new->tbst_tag[dir] = TBST_THREAD; new->tbst_link[!dir] = dst; new->tbst_tag[!dir] = TBST_THREAD; dst->tbst_link[dir] = new; dst->tbst_tag[dir] = TBST_CHILD; if (copy == NULL) new->tbst_data = src->tbst_data; else { new->tbst_data = copy (src->tbst_data, tree->tbst_param); if (new->tbst_data == NULL) return 0; } return 1; } /* Destroys |new| with |tbst_destroy (new, destroy)|, first initializing the right link in |new| that has not yet been initialized. */ static void copy_error_recovery (struct tbst_node *p, struct tbst_table *new, tbst_item_func *destroy) { new->tbst_root = p; if (p != NULL) { while (p->tbst_tag[1] == TBST_CHILD) p = p->tbst_link[1]; p->tbst_link[1] = NULL; } tbst_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 tbst_table * tbst_copy (const struct tbst_table *org, tbst_copy_func *copy, tbst_item_func *destroy, struct libavl_allocator *allocator) { struct tbst_table *new; const struct tbst_node *p; struct tbst_node *q; struct tbst_node rp, rq; assert (org != NULL); new = tbst_create (org->tbst_compare, org->tbst_param, allocator != NULL ? allocator : org->tbst_alloc); if (new == NULL) return NULL; new->tbst_count = org->tbst_count; if (new->tbst_count == 0) return new; p = &rp; rp.tbst_link[0] = org->tbst_root; rp.tbst_tag[0] = TBST_CHILD; q = &rq; rq.tbst_link[0] = NULL; rq.tbst_tag[0] = TBST_THREAD; for (;;) { if (p->tbst_tag[0] == TBST_CHILD) { if (!copy_node (new, q, 0, p->tbst_link[0], copy)) { copy_error_recovery (rq.tbst_link[0], new, destroy); return NULL; } p = p->tbst_link[0]; q = q->tbst_link[0]; } else { while (p->tbst_tag[1] == TBST_THREAD) { p = p->tbst_link[1]; if (p == NULL) { q->tbst_link[1] = NULL; new->tbst_root = rq.tbst_link[0]; return new; } q = q->tbst_link[1]; } p = p->tbst_link[1]; q = q->tbst_link[1]; } if (p->tbst_tag[1] == TBST_CHILD) if (!copy_node (new, q, 1, p->tbst_link[1], copy)) { copy_error_recovery (rq.tbst_link[0], new, destroy); return NULL; } } }