12.3.1 Steps 1 and 2: Search and Insert

The process of search and insertion proceeds as usual. Stack pa[], with pa[k - 1] at top of stack, records the parents of the node p currently under consideration, with corresponding stack da[] indicating the direction moved. We use the standard code for insertion into an RTBST. When the loop exits, p is the node under which a new node should be inserted on side dir.

457. <Step 1: Search RTRB tree for insertion point 457> =
da[0] = 0;
pa[0] = (struct rtrb_node *) &tree->rtrb_root;
k = 1;
if (tree->rtrb_root != NULL)
  for (p = tree->rtrb_root; ; p = p->rtrb_link[dir]) 
    {
      int cmp = tree->rtrb_compare (item, p->rtrb_data, tree->rtrb_param);
      if (cmp == 0)
        return &p->rtrb_data;

      pa[k] = p;
      da[k++] = dir = cmp > 0;

      if (dir == 0) 
        {
          if (p->rtrb_link[0] == NULL)
            break;
        } 
      else /* dir == 1 */ 
        {
          if (p->rtrb_rtag == RTRB_THREAD)
            break;
        }
    }
else 
  {
    p = (struct rtrb_node *) &tree->rtrb_root;
    dir = 0;
  }

This code is included in 456.

458. <Step 2: Insert RTRB node 458> =
n = tree->rtrb_alloc->libavl_malloc (tree->rtrb_alloc, sizeof *n);
if (n == NULL)
  return NULL;

tree->rtrb_count++;
n->rtrb_data = item;
n->rtrb_link[0] = NULL;
if (dir == 0) 
  {
    if (tree->rtrb_root != NULL)
      n->rtrb_link[1] = p;
    else 
      n->rtrb_link[1] = NULL;
  } 
else /* dir == 1 */ 
  {
    p->rtrb_rtag = RTRB_CHILD;
    n->rtrb_link[1] = p->rtrb_link[1];
  }
n->rtrb_rtag = RTRB_THREAD;
n->rtrb_color = RTRB_RED;
p->rtrb_link[dir] = n;

This code is included in 456.