/* Returns the parent of |node| within |tree|,
   or a pointer to |trb_root| if |s| is the root of the tree. */
static struct trb_node *
find_parent (struct trb_table *tree, struct trb_node *node)
{
  if (node != tree->trb_root)
    {
      struct trb_node *x, *y;

      for (x = y = node; ; x = x->trb_link[0], y = y->trb_link[1])
        if (y->trb_tag[1] == TRB_THREAD)
          {
            struct trb_node *p = y->trb_link[1];
            if (p == NULL || p->trb_link[0] != node)
              {
                while (x->trb_tag[0] == TRB_CHILD)
                  x = x->trb_link[0];
                p = x->trb_link[0];
              }
            return p;
          }
        else if (x->trb_tag[0] == TRB_THREAD)
          {
            struct trb_node *p = x->trb_link[0];
            if (p == NULL || p->trb_link[1] != node)
              {
                while (y->trb_tag[1] == TRB_CHILD)
                  y = y->trb_link[1];
                p = y->trb_link[1];
              }
            return p;
          }
    }
  else
    return (struct trb_node *) &tree->trb_root;
}

/* Inserts |item| into |tree| and returns a pointer to |item|'s address.
   If a duplicate item is found in the tree,
   returns a pointer to the duplicate without inserting |item|.
   Returns |NULL| in case of memory allocation failure. */
void **
trb_probe (struct trb_table *tree, void *item)
{
  struct trb_node *p; /* Traverses tree looking for insertion point. */
  struct trb_node *n; /* Newly inserted node. */
  int dir;            /* Side of |p| on which |n| is inserted. */

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

  if (tree->trb_root != NULL)
    for (p = tree->trb_root; ; p = p->trb_link[dir])
      {
        int cmp = tree->trb_compare (item, p->trb_data, tree->trb_param);
        if (cmp == 0)
          return &p->trb_data;
        dir = cmp > 0;

        if (p->trb_tag[dir] == TRB_THREAD)
          break;
      }
  else
    {
      p = (struct trb_node *) &tree->trb_root;
      dir = 0;
    }

  n = tree->trb_alloc->libavl_malloc (tree->trb_alloc, sizeof *n);
  if (n == NULL)
    return NULL;

  tree->trb_count++;
  n->trb_data = item;
  n->trb_tag[0] = n->trb_tag[1] = TRB_THREAD;
  n->trb_link[dir] = p->trb_link[dir];
  if (tree->trb_root != NULL)
    {
      p->trb_tag[dir] = TRB_CHILD;
      n->trb_link[!dir] = p;
    }
  else
    n->trb_link[1] = NULL;
  p->trb_link[dir] = n;
  n->trb_color = TRB_RED;

  p = n;
  for (;;)
    {
      struct trb_node *f, *g;

      f = find_parent (tree, p);
      if (f == (struct trb_node *) &tree->trb_root
          || f->trb_color == TRB_BLACK)
        break;

      g = find_parent (tree, f);
      if (g == (struct trb_node *) &tree->trb_root)
        break;

      if (g->trb_link[0] == f)
        {
          struct trb_node *y = g->trb_link[1];
          if (g->trb_tag[1] == TRB_CHILD && y->trb_color == TRB_RED)
            {
              f->trb_color = y->trb_color = TRB_BLACK;
              g->trb_color = TRB_RED;
              p = g;
            }
          else
            {
              struct trb_node *c, *x;

              if (f->trb_link[0] == p)
                y = f;
              else
                {
                  x = f;
                  y = x->trb_link[1];
                  x->trb_link[1] = y->trb_link[0];
                  y->trb_link[0] = x;
                  g->trb_link[0] = y;

                  if (y->trb_tag[0] == TRB_THREAD)
                    {
                      y->trb_tag[0] = TRB_CHILD;
                      x->trb_tag[1] = TRB_THREAD;
                      x->trb_link[1] = y;
                    }
                }

              c = find_parent (tree, g);
              c->trb_link[c->trb_link[0] != g] = y;

              x = g;
              x->trb_color = TRB_RED;
              y->trb_color = TRB_BLACK;

              x->trb_link[0] = y->trb_link[1];
              y->trb_link[1] = x;

              if (y->trb_tag[1] == TRB_THREAD)
                {
                  y->trb_tag[1] = TRB_CHILD;
                  x->trb_tag[0] = TRB_THREAD;
                  x->trb_link[0] = y;
                }
              break;
            }
        }
      else
        {
          struct trb_node *y = g->trb_link[0];
          if (g->trb_tag[0] == TRB_CHILD && y->trb_color == TRB_RED)
            {
              f->trb_color = y->trb_color = TRB_BLACK;
              g->trb_color = TRB_RED;
              p = g;
            }
          else
            {
              struct trb_node *c, *x;

              if (f->trb_link[1] == p)
                y = f;
              else
                {
                  x = f;
                  y = x->trb_link[0];
                  x->trb_link[0] = y->trb_link[1];
                  y->trb_link[1] = x;
                  g->trb_link[1] = y;

                  if (y->trb_tag[1] == TRB_THREAD)
                    {
                      y->trb_tag[1] = TRB_CHILD;
                      x->trb_tag[0] = TRB_THREAD;
                      x->trb_link[0] = y;
                    }
                }

              c = find_parent (tree, g);
              c->trb_link[c->trb_link[0] != g] = y;

              x = g;
              x->trb_color = TRB_RED;
              y->trb_color = TRB_BLACK;

              x->trb_link[1] = y->trb_link[0];
              y->trb_link[0] = x;

              if (y->trb_tag[0] == TRB_THREAD)
                {
                  y->trb_tag[0] = TRB_CHILD;
                  x->trb_tag[1] = TRB_THREAD;
                  x->trb_link[1] = y;
                }
              break;
            }
        }
    }
  tree->trb_root->trb_color = TRB_BLACK;

  return &n->trb_data;
}