10.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 <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.

403. <RTBST main copy function 403> =
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->rtbst_compare, org->rtbst_param,
                     allocator != NULL ? allocator : org->rtbst_alloc);
  if (new == NULL)
    return NULL;

  new->rtbst_count = org->rtbst_count;
  if (new->rtbst_count == 0)
    return new;

  p = (struct rtbst_node *) &org->rtbst_root;
  q = (struct rtbst_node *) &new->rtbst_root;
  for (;;) 
    {
      if (p->rtbst_link[0] != NULL) 
        {
          if (!copy_node (new, q, 0, p->rtbst_link[0], copy)) 
            {
              copy_error_recovery (new, destroy);
              return NULL;
            }

          p = p->rtbst_link[0];
          q = q->rtbst_link[0];
        } 
      else 
        {
          while (p->rtbst_rtag == RTBST_THREAD) 
            {
              p = p->rtbst_link[1];
              if (p == NULL) 
                {
                  q->rtbst_link[1] = NULL;
                  return new;
                }

              q = q->rtbst_link[1];
            }

          p = p->rtbst_link[1];
          q = q->rtbst_link[1];
        }

      if (p->rtbst_rtag == RTBST_CHILD)
        if (!copy_node (new, q, 1, p->rtbst_link[1], copy)) 
          {
            copy_error_recovery (new, destroy);
            return NULL;
          }
    }
}

This code is included in 406 and 447.

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

404. <RTBST node copy function 404> =
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->rtbst_alloc->libavl_malloc (tree->rtbst_alloc, sizeof *new);
  if (new == NULL)
    return 0;

  new->rtbst_link[0] = NULL;
  new->rtbst_rtag = RTBST_THREAD;
  if (dir == 0)
    new->rtbst_link[1] = dst;
  else 
    {
      new->rtbst_link[1] = dst->rtbst_link[1];
      dst->rtbst_rtag = RTBST_CHILD;
    }
  dst->rtbst_link[dir] = new;

  if (copy == NULL)
    new->rtbst_data = src->rtbst_data;
  else 
    {
      new->rtbst_data = copy (src->rtbst_data, tree->rtbst_param);
      if (new->rtbst_data == NULL)
        return 0;
    }

  return 1;
}

This code is included in 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:

405. <RTBST copy error helper function 405> =
static void 
copy_error_recovery (struct rtbst_table *new, rtbst_item_func *destroy) 
{
  struct rtbst_node *p = new->rtbst_root;
  if (p != NULL) 
    {
      while (p->rtbst_rtag == RTBST_CHILD)
        p = p->rtbst_link[1];
      p->rtbst_link[1] = NULL;
    }
  rtbst_destroy (new, destroy);
}

This code is included in 406 and 447.

406. <RTBST copy function 406> =
<RTBST node copy function 404>
<RTBST copy error helper function 405>
<RTBST main copy function 403>

This code is included in 375.