13.5.4 Starting at an Inserted Node

This function combines the functionality of search and insertion with initialization of a traverser.

508. <PBST traverser insertion initializer 508> =
void *
pbst_t_insert (struct pbst_traverser *trav, struct pbst_table *tree, 
               void *item) 
{
  struct pbst_node *p, *q; /* Current node in search and its parent. */
  int dir;                 /* Side of q on which p is located. */
  struct pbst_node *n;     /* Newly inserted node. */

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

  trav->pbst_table = tree;
  for (q = NULL, p = tree->pbst_root; p != NULL; q = p, p = p->pbst_link[dir]) 
    {
      int cmp = tree->pbst_compare (item, p->pbst_data, tree->pbst_param);
      if (cmp == 0) 
        {
          trav->pbst_node = p;
          return p->pbst_data;
        }
      dir = cmp > 0;
    }

  trav->pbst_node = n = 
    tree->pbst_alloc->libavl_malloc (tree->pbst_alloc, sizeof *p);
  if (n == NULL) 
    return NULL;

  tree->pbst_count++;
  n->pbst_link[0] = n->pbst_link[1] = NULL;
  n->pbst_parent = q;
  n->pbst_data = item;
  if (q != NULL)
    q->pbst_link[dir] = n;
  else 
    tree->pbst_root = n;

  return item;
}

This code is included in 504.