/* Destroys |new| with |pbst_destroy (new, destroy)|,
   first initializing right links in |new| that have
   not yet been initialized at time of call. */
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);
}

/* Copies |org| to a newly created tree, which is returned.
   If |copy != NULL|, each data item in |org| is first passed to |copy|,
   and the return values are inserted into the tree;
   |NULL| return values are taken as indications of failure.
   On failure, destroys the partially created new tree,
   applying |destroy|, if non-null, to each item in the new tree so far,
   and returns |NULL|.
   If |allocator != NULL|, it is used for allocation in the new tree;
   otherwise, the same allocator used for |org| is used. */
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;
            }
        }
    }
}