14.7 Copying

The copy function is the same as <PBST copy function 509>, except that it copies pavl_balance between copied nodes.

547. <PAVL copy function 547> =
<PBST copy error helper function; pbst => pavl 510>

struct pavl_table *
pavl_copy (const struct pavl_table *org, pavl_copy_func *copy,
           pavl_item_func *destroy, struct libavl_allocator *allocator) 
{
  struct pavl_table *new;
  const struct pavl_node *x;
  struct pavl_node *y;

  assert (org != NULL);
  new = pavl_create (org->pavl_compare, org->pavl_param,
                    allocator != NULL ? allocator : org->pavl_alloc);
  if (new == NULL)
    return NULL;
  new->pavl_count = org->pavl_count;
  if (new->pavl_count == 0)
    return new;

  x = (const struct pavl_node *) &org->pavl_root;
  y = (struct pavl_node *) &new->pavl_root;
  for (;;) 
    {
      while (x->pavl_link[0] != NULL) 
        {
          y->pavl_link[0] = 
            new->pavl_alloc->libavl_malloc (new->pavl_alloc,
                                            sizeof *y->pavl_link[0]);
          if (y->pavl_link[0] == NULL) 
            {
              if (y != (struct pavl_node *) &new->pavl_root) 
                {
                  y->pavl_data = NULL;
                  y->pavl_link[1] = NULL;
                }

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

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

      for (;;) 
        {
          y->pavl_balance = x->pavl_balance;
          if (copy == NULL)
            y->pavl_data = x->pavl_data;
          else 
            {
              y->pavl_data = copy (x->pavl_data, org->pavl_param);
              if (y->pavl_data == NULL) 
                {
                  y->pavl_link[1] = NULL;
                  copy_error_recovery (y, new, destroy);
                  return NULL;
                }
            }

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

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

          for (;;) 
            {
              const struct pavl_node *w = x;
              x = x->pavl_parent;
              if (x == NULL) 
                {
                  new->pavl_root->pavl_parent = NULL;
                  return new;
                }
              y = y->pavl_parent;

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

This code is included in 522 and 554.