/* Deletes from |tree| and returns an item matching |item|.
   Returns a null pointer if no matching item found. */
void *
rtavl_delete (struct rtavl_table *tree, const void *item)
{
  /* Stack of nodes. */
  struct rtavl_node *pa[RTAVL_MAX_HEIGHT]; /* Nodes. */
  unsigned char da[RTAVL_MAX_HEIGHT];     /* |rtavl_link[]| indexes. */
  int k;                                  /* Stack pointer. */

  struct rtavl_node *p; /* Traverses tree to find node to delete. */

  assert (tree != NULL && item != NULL);

  k = 1;
  da[0] = 0;
  pa[0] = (struct rtavl_node *) &tree->rtavl_root;
  p = tree->rtavl_root;
  if (p == NULL)
    return NULL;

  for (;;)
    {
      int cmp, dir;

      cmp = tree->rtavl_compare (item, p->rtavl_data, tree->rtavl_param);
      if (cmp == 0)
        break;

      dir = cmp > 0;
      if (dir == 0)
        {
          if (p->rtavl_link[0] == NULL)
            return NULL;
        }
      else /* |dir == 1| */
        {
          if (p->rtavl_rtag == RTAVL_THREAD)
            return NULL;
        }

      pa[k] = p;
      da[k++] = dir;
      p = p->rtavl_link[dir];
    }
  tree->rtavl_count--;
  item = p->rtavl_data;

  if (p->rtavl_link[0] == NULL)
    {
      if (p->rtavl_rtag == RTAVL_CHILD)
        {
          pa[k - 1]->rtavl_link[da[k - 1]] = p->rtavl_link[1];
        }
      else
        {
          pa[k - 1]->rtavl_link[da[k - 1]] = p->rtavl_link[da[k - 1]];
          if (da[k - 1] == 1)
            pa[k - 1]->rtavl_rtag = RTAVL_THREAD;
        }
    }
  else
    {
      struct rtavl_node *r = p->rtavl_link[0];
      if (r->rtavl_rtag == RTAVL_THREAD)
        {
          r->rtavl_link[1] = p->rtavl_link[1];
          r->rtavl_rtag = p->rtavl_rtag;
          r->rtavl_balance = p->rtavl_balance;
          pa[k - 1]->rtavl_link[da[k - 1]] = r;
          da[k] = 0;
          pa[k++] = r;
        }
      else
        {
          struct rtavl_node *s;
          int j = k++;

          for (;;)
            {
              da[k] = 1;
              pa[k++] = r;
              s = r->rtavl_link[1];
              if (s->rtavl_rtag == RTAVL_THREAD)
                break;

              r = s;
            }

          da[j] = 0;
          pa[j] = pa[j - 1]->rtavl_link[da[j - 1]] = s;

          if (s->rtavl_link[0] != NULL)
            r->rtavl_link[1] = s->rtavl_link[0];
          else
            {
              r->rtavl_rtag = RTAVL_THREAD;
              r->rtavl_link[1] = s;
            }

          s->rtavl_balance = p->rtavl_balance;
          s->rtavl_link[0] = p->rtavl_link[0];
          s->rtavl_link[1] = p->rtavl_link[1];
          s->rtavl_rtag = p->rtavl_rtag;
        }
    }

  tree->rtavl_alloc->libavl_free (tree->rtavl_alloc, p);

  assert (k > 0);
  while (--k > 0)
    {
      struct rtavl_node *y = pa[k];

      if (da[k] == 0)
        {
          y->rtavl_balance++;
          if (y->rtavl_balance == +1)
            break;
          else if (y->rtavl_balance == +2)
            {
              struct rtavl_node *x = y->rtavl_link[1];

              assert (x != NULL);
              if (x->rtavl_balance == -1)
                {
                  struct rtavl_node *w;

                  assert (x->rtavl_balance == -1);
                  w = x->rtavl_link[0];
                  x->rtavl_link[0] = w->rtavl_link[1];
                  w->rtavl_link[1] = x;
                  y->rtavl_link[1] = w->rtavl_link[0];
                  w->rtavl_link[0] = y;
                  if (w->rtavl_balance == +1)
                    x->rtavl_balance = 0, y->rtavl_balance = -1;
                  else if (w->rtavl_balance == 0)
                    x->rtavl_balance = y->rtavl_balance = 0;
                  else /* |w->rtavl_balance == -1| */
                    x->rtavl_balance = +1, y->rtavl_balance = 0;
                  w->rtavl_balance = 0;
                  if (y->rtavl_link[1] == NULL)
                    {
                      y->rtavl_rtag = RTAVL_THREAD;
                      y->rtavl_link[1] = w;
                    }
                  if (w->rtavl_rtag == RTAVL_THREAD)
                    {
                      x->rtavl_link[0] = NULL;
                      w->rtavl_rtag = RTAVL_CHILD;
                    }
                  pa[k - 1]->rtavl_link[da[k - 1]] = w;
                }
              else
                {
                  pa[k - 1]->rtavl_link[da[k - 1]] = x;
                  if (x->rtavl_balance == 0)
                    {
                      y->rtavl_link[1] = x->rtavl_link[0];
                      x->rtavl_link[0] = y;
                      x->rtavl_balance = -1;
                      y->rtavl_balance = +1;
                      break;
                    }
                  else /* |x->rtavl_balance == +1| */
                    {
                      if (x->rtavl_link[0] != NULL)
                        y->rtavl_link[1] = x->rtavl_link[0];
                      else
                        y->rtavl_rtag = RTAVL_THREAD;
                      x->rtavl_link[0] = y;
                      y->rtavl_balance = x->rtavl_balance = 0;
                    }
                }
            }
        }
      else
        {
          y->rtavl_balance--;
          if (y->rtavl_balance == -1)
            break;
          else if (y->rtavl_balance == -2)
            {
              struct rtavl_node *x = y->rtavl_link[0];

              assert (x != NULL);
              if (x->rtavl_balance == +1)
                {
                  struct rtavl_node *w;

                  assert (x->rtavl_balance == +1);
                  w = x->rtavl_link[1];
                  x->rtavl_link[1] = w->rtavl_link[0];
                  w->rtavl_link[0] = x;
                  y->rtavl_link[0] = w->rtavl_link[1];
                  w->rtavl_link[1] = y;
                  if (w->rtavl_balance == -1)
                    x->rtavl_balance = 0, y->rtavl_balance = +1;
                  else if (w->rtavl_balance == 0)
                    x->rtavl_balance = y->rtavl_balance = 0;
                  else /* |w->rtavl_balance == +1| */
                    x->rtavl_balance = -1, y->rtavl_balance = 0;
                  w->rtavl_balance = 0;
                  if (x->rtavl_link[1] == NULL)
                    {
                      x->rtavl_rtag = RTAVL_THREAD;
                      x->rtavl_link[1] = w;
                    }
                  if (w->rtavl_rtag == RTAVL_THREAD)
                    {
                      y->rtavl_link[0] = NULL;
                      w->rtavl_rtag = RTAVL_CHILD;
                    }
                  pa[k - 1]->rtavl_link[da[k - 1]] = w;
                }
              else
                {
                  pa[k - 1]->rtavl_link[da[k - 1]] = x;
                  if (x->rtavl_balance == 0)
                    {
                      y->rtavl_link[0] = x->rtavl_link[1];
                      x->rtavl_link[1] = y;
                      x->rtavl_balance = +1;
                      y->rtavl_balance = -1;
                      break;
                    }
                  else /* |x->rtavl_balance == -1| */
                    {
                      if (x->rtavl_rtag == RTAVL_CHILD)
                        y->rtavl_link[0] = x->rtavl_link[1];
                      else
                        {
                          y->rtavl_link[0] = NULL;
                          x->rtavl_rtag = RTAVL_CHILD;
                        }
                      x->rtavl_link[1] = y;
                      y->rtavl_balance = x->rtavl_balance = 0;
                    }
                }
            }
        }
    }

  return (void *) item;
}