5.7 Copying

Copying an AVL tree is similar to copying a BST. The only important difference is that we have to copy the AVL balance factor between nodes as well as node data. We don't check our stack height here, either.

185. <AVL copy function 185> =
<BST copy error helper function; bst => avl 82>

struct avl_table *
avl_copy (const struct avl_table *org, avl_copy_func *copy,
          avl_item_func *destroy, struct libavl_allocator *allocator) 
{
  struct avl_node *stack[2 * (AVL_MAX_HEIGHT + 1)];
  int height = 0;

  struct avl_table *new;
  const struct avl_node *x;
  struct avl_node *y;

  assert (org != NULL);
  new = avl_create (org->avl_compare, org->avl_param,
                    allocator != NULL ? allocator : org->avl_alloc);
  if (new == NULL)
    return NULL;
  new->avl_count = org->avl_count;
  if (new->avl_count == 0)
    return new;

  x = (const struct avl_node *) &org->avl_root;
  y = (struct avl_node *) &new->avl_root;
  for (;;) 
    {
      while (x->avl_link[0] != NULL) 
        {
          assert (height < 2 * (AVL_MAX_HEIGHT + 1));

          y->avl_link[0] = 
            new->avl_alloc->libavl_malloc (new->avl_alloc,
                                           sizeof *y->avl_link[0]);
          if (y->avl_link[0] == NULL) 
            {
              if (y != (struct avl_node *) &new->avl_root) 
                {
                  y->avl_data = NULL;
                  y->avl_link[1] = NULL;
                }

              copy_error_recovery (stack, height, new, destroy);
              return NULL;
            }

          stack[height++] = (struct avl_node *) x;
          stack[height++] = y;
          x = x->avl_link[0];
          y = y->avl_link[0];
        }
      y->avl_link[0] = NULL;

      for (;;) 
        {
          y->avl_balance = x->avl_balance;
          if (copy == NULL)
            y->avl_data = x->avl_data;
          else 
            {
              y->avl_data = copy (x->avl_data, org->avl_param);
              if (y->avl_data == NULL) 
                {
                  y->avl_link[1] = NULL;
                  copy_error_recovery (stack, height, new, destroy);
                  return NULL;
                }
            }

          if (x->avl_link[1] != NULL) 
            {
              y->avl_link[1] = 
                new->avl_alloc->libavl_malloc (new->avl_alloc,
                                               sizeof *y->avl_link[1]);
              if (y->avl_link[1] == NULL) 
                {
                  copy_error_recovery (stack, height, new, destroy);
                  return NULL;
                }

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

          if (height <= 2)
            return new;

          y = stack[–height];
          x = stack[–height];
        }
    }
}

This code is included in 145 and 196.