/* 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 |rtavl_data| member. */ static int copy_node (struct rtavl_table *tree, struct rtavl_node *dst, int dir, const struct rtavl_node *src, rtavl_copy_func *copy) { struct rtavl_node *new = tree->rtavl_alloc->libavl_malloc (tree->rtavl_alloc, sizeof *new); if (new == NULL) return 0; new->rtavl_link[0] = NULL; new->rtavl_rtag = RTAVL_THREAD; if (dir == 0) new->rtavl_link[1] = dst; else { new->rtavl_link[1] = dst->rtavl_link[1]; dst->rtavl_rtag = RTAVL_CHILD; } dst->rtavl_link[dir] = new; new->rtavl_balance = src->rtavl_balance; if (copy == NULL) new->rtavl_data = src->rtavl_data; else { new->rtavl_data = copy (src->rtavl_data, tree->rtavl_param); if (new->rtavl_data == NULL) return 0; } return 1; } /* Destroys |new| with |rtavl_destroy (new, destroy)|, first initializing right links in |new| that have not yet been initialized at time of call. */ static void copy_error_recovery (struct rtavl_table *new, rtavl_item_func *destroy) { struct rtavl_node *p = new->rtavl_root; if (p != NULL) { while (p->rtavl_rtag == RTAVL_CHILD) p = p->rtavl_link[1]; p->rtavl_link[1] = NULL; } rtavl_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 are 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 rtavl_table * rtavl_copy (const struct rtavl_table *org, rtavl_copy_func *copy, rtavl_item_func *destroy, struct libavl_allocator *allocator) { struct rtavl_table *new; const struct rtavl_node *p; struct rtavl_node *q; assert (org != NULL); new = rtavl_create (org->rtavl_compare, org->rtavl_param, allocator != NULL ? allocator : org->rtavl_alloc); if (new == NULL) return NULL; new->rtavl_count = org->rtavl_count; if (new->rtavl_count == 0) return new; p = (struct rtavl_node *) &org->rtavl_root; q = (struct rtavl_node *) &new->rtavl_root; for (;;) { if (p->rtavl_link[0] != NULL) { if (!copy_node (new, q, 0, p->rtavl_link[0], copy)) { copy_error_recovery (new, destroy); return NULL; } p = p->rtavl_link[0]; q = q->rtavl_link[0]; } else { while (p->rtavl_rtag == RTAVL_THREAD) { p = p->rtavl_link[1]; if (p == NULL) { q->rtavl_link[1] = NULL; return new; } q = q->rtavl_link[1]; } p = p->rtavl_link[1]; q = q->rtavl_link[1]; } if (p->rtavl_rtag == RTAVL_CHILD) if (!copy_node (new, q, 1, p->rtavl_link[1], copy)) { copy_error_recovery (new, destroy); return NULL; } } }