Handling Errors in Iterative BST Copying

So far, outside the exercises, we've ignored the question of handling memory allocation errors during copying. In our other routines, we've been careful to implement to handle allocation failures by cleaning up and returning an error indication to the caller. Now we will apply this same policy to tree copying, as libavl semantics require (see Creation and Destruction): a memory allocation error causes the partially copied tree to be destroyed and returns a null pointer to the caller.

This is a little harder to do than recovering after a single operation, because there are potentially many nodes that have to be freed, and each node might include additional user data that also has to be freed. The new BST might have as-yet-uninitialized pointer fields as well, and we must be careful to avoid reading from these fields as we destroy the tree.

We could use a number of strategies to destroy the partially copied tree while avoiding uninitialized pointers. The strategy that we will actually use is to initialize these pointers to NULL, then call the general tree destruction routine bst_destroy(). We haven't yet written bst_destroy(), so for now we'll treat it as a black box (see black box) that does what we want, even if we don't understand how.

Next question: which pointers in the tree are not initialized? The answer is simple: during the copy, we will not revisit nodes not currently on the stack, so only pointers in the current node (y) and on the stack can be uninitialized. For its part, depending on what we're doing to it, y might not have any of its fields initialized. As for the stack, nodes are pushed onto it because we have to come back later and build their right subtrees, so we must set their right child pointers to NULL.

We will need this error recovery code in a number of places, so it is worth making it into a small helper function:

82. <BST copy error helper function 82> =
static void 
copy_error_recovery (struct bst_node **stack, int height, 
                     struct bst_table *new, bst_item_func *destroy) 
{
  assert (stack != NULL && height >= 0 && new != NULL);

  for (; height > 2; height -= 2)
    stack[height - 1]->bst_link[1] = NULL;
  bst_destroy (new, destroy);
}

This code is included in 83 and 185.

Another problem that can arise in copying a binary tree is stack overflow. We will handle stack overflow by destroying the partial copy, balancing the original tree, and then restarting the copy. The balanced tree is guaranteed to have small enough height that it will not overflow the stack.

The code below for our final version of bst_copy() takes three new parameters: two function pointers and a memory allocator. The meaning of these parameters was explained earlier (see Creation and Destruction). Their use within the function should be self-explanatory.

83. <BST copy function 83> =
<BST copy error helper function 82>

struct bst_table *
bst_copy (const struct bst_table *org, bst_copy_func *copy,
          bst_item_func *destroy, struct libavl_allocator *allocator) 
{
  struct bst_node *stack[2 * (BST_MAX_HEIGHT + 1)];
  int height = 0;

  struct bst_table *new;
  const struct bst_node *x;
  struct bst_node *y;

  assert (org != NULL);
  new = bst_create (org->bst_compare, org->bst_param, 
                    allocator != NULL ? allocator : org->bst_alloc);
  if (new == NULL)
    return NULL;
  new->bst_count = org->bst_count;
  if (new->bst_count == 0)
    return new;

  x = (const struct bst_node *) &org->bst_root;
  y = (struct bst_node *) &new->bst_root;
  for (;;) 
    {
      while (x->bst_link[0] != NULL) 
        {
          if (height >= 2 * (BST_MAX_HEIGHT + 1)) 
            {
              y->bst_data = NULL;
              y->bst_link[0] = y->bst_link[1] = NULL;
              copy_error_recovery (stack, height, new, destroy);

              bst_balance ((struct bst_table *) org);
              return bst_copy (org, copy, destroy, allocator);
            }

          y->bst_link[0] = 
            new->bst_alloc->libavl_malloc (new->bst_alloc,
                                           sizeof *y->bst_link[0]);
          if (y->bst_link[0] == NULL) 
            {
              if (y != (struct bst_node *) &new->bst_root) 
                {
                  y->bst_data = NULL;
                  y->bst_link[1] = NULL;
                }

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

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

      for (;;) 
        {
          if (copy == NULL) 
            y->bst_data = x->bst_data;
          else 
            {
              y->bst_data = copy (x->bst_data, org->bst_param);
              if (y->bst_data == NULL) 
                {
                  y->bst_link[1] = NULL;
                  copy_error_recovery (stack, height, new, destroy);
                  return NULL;
                }
            }

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

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

          if (height <= 2)
            return new;

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

This code is included in 29.