www.delorie.com/gnu/docs/avl/libavl_198.html   search  
 
Buy GNU books!


GNU libavl 2.0.1

[ < ] [ > ]   [ << ] [ Up ] [ >> ]         [Top] [Contents] [Index] [ ? ]

11.7 Copying

The algorithm that we used for copying a TBST makes use of threads, but only right threads, so we can apply this algorithm essentially unmodified to RTBSTs.

We will make one change that superficially simplifies and improves the elegance of the algorithm. Function tbst_copy() in &#60;@xref{\NODE\, , \TITLE\}.&#62;{TBST main copy function,279} uses a pair of local variables rp and rq to store pointers to the original and new tree's root, because accessing the tag field of a cast "pseudo-root" pointer produces undefined behavior. However, in an RTBST there is no tag for a node's left subtree. During a TBST copy, only the left tags of the root nodes are accessed, so this means that we can use the pseudo-roots in the RTBST copy, with no need for rp or rq.

 
struct rtbst_table *
rtbst_copy (const struct rtbst_table *org, rtbst_copy_func *copy, rtbst_item_func *destroy, struct libavl_allocator *allocator) { struct rtbst_table *new; const struct rtbst_node *p; struct rtbst_node *q; assert (org != NULL); new = rtbst_create (org-&#62;rtbst_compare, org-&#62;rtbst_param, allocator != NULL ? allocator : org-&#62;rtbst_alloc); if (new == NULL) return NULL; new-&#62;rtbst_count = org-&#62;rtbst_count; if (new-&#62;rtbst_count == 0) return new; p = (struct rtbst_node *) &org-&#62;rtbst_root; q = (struct rtbst_node *) &new-&#62;rtbst_root; for (;;)
{ if (p-&#62;rtbst_link[0] != NULL)
{ if (!copy_node (new, q, 0, p-&#62;rtbst_link[0], copy))
{ copy_error_recovery (new, destroy); return NULL; } p = p-&#62;rtbst_link[0]; q = q-&#62;rtbst_link[0]; }
else
{ while (p-&#62;rtbst_rtag == RTBST_THREAD)
{ p = p-&#62;rtbst_link[1]; if (p == NULL)
{ q-&#62;rtbst_link[1] = NULL; return new; } q = q-&#62;rtbst_link[1]; } p = p-&#62;rtbst_link[1]; q = q-&#62;rtbst_link[1]; } if (p-&#62;rtbst_rtag == RTBST_CHILD) if (!copy_node (new, q, 1, p-&#62;rtbst_link[1], copy))
{ copy_error_recovery (new, destroy); return NULL; } } }
This code is included in @refalso{406

The code to copy a node must be modified to deal with the asymmetrical nature of insertion in an RTBST:

 
static int 
copy_node (struct rtbst_table *tree,
struct rtbst_node *dst, int dir, const struct rtbst_node *src, rtbst_copy_func *copy)
{ struct rtbst_node *new =
tree-&#62;rtbst_alloc-&#62;libavl_malloc (tree-&#62;rtbst_alloc, sizeof *new); if (new == NULL) return 0; new-&#62;rtbst_link[0] = NULL; new-&#62;rtbst_rtag = RTBST_THREAD; if (dir == 0) new-&#62;rtbst_link[1] = dst; else
{ new-&#62;rtbst_link[1] = dst-&#62;rtbst_link[1]; dst-&#62;rtbst_rtag = RTBST_CHILD; } dst-&#62;rtbst_link[dir] = new; if (copy == NULL) new-&#62;rtbst_data = src-&#62;rtbst_data; else
{ new-&#62;rtbst_data = copy (src-&#62;rtbst_data, tree-&#62;rtbst_param); if (new-&#62;rtbst_data == NULL) return 0; } return 1; }
This code is included in @refalso{406

The error recovery function for copying is a bit simpler now, because the use of the pseudo-root means that no assignment to the new tree's root need take place, eliminating the need for one of the function's parameters:

 
static void 
copy_error_recovery (struct rtbst_table *new, rtbst_item_func *destroy)
{ struct rtbst_node *p = new-&#62;rtbst_root; if (p != NULL)
{ while (p-&#62;rtbst_rtag == RTBST_CHILD) p = p-&#62;rtbst_link[1]; p-&#62;rtbst_link[1] = NULL; } rtbst_destroy (new, destroy); }
This code is included in @refalso{406

 
&#60;@xref{\NODE\, , RTBST node copy function.&#62;,404}
&#60;@xref{\NODE\, , RTBST copy error helper function.&#62;,405}
&#60;@xref{\NODE\, , RTBST main copy function.&#62;,403}
This code is included in @refalso{375


[ < ] [ > ]   [ << ] [ Up ] [ >> ]         [Top] [Contents] [Index] [ ? ]

  webmaster   donations   bookstore     delorie software   privacy  
  Copyright 2003   by The Free Software Foundation     Updated Jun 2003