13.6 Copying

To copy BSTs with parent pointers, we use a simple adaptation of our original algorithm for copying BSTs, as implemented in <BST copy function 83>. That function used a stack to keep track of the nodes that need to be revisited to have their right subtrees copies. We can eliminate that by using the parent pointers. Instead of popping a pair of nodes off the stack, we ascend the tree until we moved up to the left:

509. <PBST copy function 509> =
<PBST copy error helper function 510>

struct pbst_table *
pbst_copy (const struct pbst_table *org, pbst_copy_func *copy,
           pbst_item_func *destroy, struct libavl_allocator *allocator) 
{
  struct pbst_table *new;
  const struct pbst_node *x;
  struct pbst_node *y;

  assert (org != NULL);
  new = pbst_create (org->pbst_compare, org->pbst_param,
                    allocator != NULL ? allocator : org->pbst_alloc);
  if (new == NULL)
    return NULL;
  new->pbst_count = org->pbst_count;
  if (new->pbst_count == 0)
    return new;

  x = (const struct pbst_node *) &org->pbst_root;
  y = (struct pbst_node *) &new->pbst_root;
  for (;;) 
    {
      while (x->pbst_link[0] != NULL) 
        {
          y->pbst_link[0] = 
            new->pbst_alloc->libavl_malloc (new->pbst_alloc,
                                            sizeof *y->pbst_link[0]);
          if (y->pbst_link[0] == NULL) 
            {
              if (y != (struct pbst_node *) &new->pbst_root) 
                {
                  y->pbst_data = NULL;
                  y->pbst_link[1] = NULL;
                }

              copy_error_recovery (y, new, destroy);
              return NULL;
            }
          y->pbst_link[0]->pbst_parent = y;

          x = x->pbst_link[0];
          y = y->pbst_link[0];
        }
      y->pbst_link[0] = NULL;

      for (;;) 
        {
          if (copy == NULL)
            y->pbst_data = x->pbst_data;
          else 
            {
              y->pbst_data = copy (x->pbst_data, org->pbst_param);
              if (y->pbst_data == NULL) 
                {
                  y->pbst_link[1] = NULL;
                  copy_error_recovery (y, new, destroy);
                  return NULL;
                }
            }

          if (x->pbst_link[1] != NULL) 
            {
              y->pbst_link[1] = 
                new->pbst_alloc->libavl_malloc (new->pbst_alloc,
                                               sizeof *y->pbst_link[1]);
              if (y->pbst_link[1] == NULL) 
                {
                  copy_error_recovery (y, new, destroy);
                  return NULL;
                }
              y->pbst_link[1]->pbst_parent = y;

              x = x->pbst_link[1];
              y = y->pbst_link[1];
              break;
            }
          else 
            y->pbst_link[1] = NULL;

          for (;;) 
            {
              const struct pbst_node *w = x;
              x = x->pbst_parent;
              if (x == NULL) 
                {
                  new->pbst_root->pbst_parent = NULL;
                  return new;
                }
              y = y->pbst_parent;

              if (w == x->pbst_link[0])
                break;
            }
        }
    }
}

This code is included in 489.

Recovering from an error changes in the same way. We ascend from the node where we were copying when memory ran out and set the right children of the nodes where we ascended to the right to null pointers, then destroy the fixed-up tree:

510. <PBST copy error helper function 510> =
static void 
copy_error_recovery (struct pbst_node *q,
                     struct pbst_table *new, pbst_item_func *destroy) 
{
  assert (q != NULL && new != NULL);

  for (;;) 
    {
      struct pbst_node *p = q;
      q = q->pbst_parent;
      if (q == NULL)
        break;

      if (p == q->pbst_link[0])
        q->pbst_link[1] = NULL;
    }

  pbst_destroy (new, destroy);
}

This code is included in 509 and 547.