11.4.1 Steps 1–2: Search and Insert

The basic insertion step itself follows the same steps as <RTBST item insertion function 379> does for a plain RTBST. We do keep track of the directions moved on stack da[] and the last-seen node with nonzero balance factor, in the same way as <Step 1: Search AVL tree for insertion point 150> for unthreaded AVL trees.

422. <Step 1: Search RTAVL tree for insertion point 422> =
z = (struct rtavl_node *) &tree->rtavl_root;
y = tree->rtavl_root;
if (tree->rtavl_root != NULL)
  for (q = z, p = y; ; q = p, p = p->rtavl_link[dir]) 
    {
      int cmp = tree->rtavl_compare (item, p->rtavl_data, tree->rtavl_param);
      if (cmp == 0)
        return &p->rtavl_data;

      if (p->rtavl_balance != 0)
        z = q, y = p, k = 0;
      da[k++] = dir = cmp > 0;

      if (dir == 0) 
        {
          if (p->rtavl_link[0] == NULL)
            break;
        } 
      else /* dir == 1 */ 
        {
          if (p->rtavl_rtag == RTAVL_THREAD)
            break;
        }
    }
else 
  {
    p = (struct rtavl_node *) &tree->rtavl_root;
    dir = 0;
  }

This code is included in 421.

423. <Step 2: Insert RTAVL node 423> =
n = tree->rtavl_alloc->libavl_malloc (tree->rtavl_alloc, sizeof *n);
if (n == NULL)
  return NULL;

tree->rtavl_count++;
n->rtavl_data = item;
n->rtavl_link[0] = NULL;
if (dir == 0)
  n->rtavl_link[1] = p;
else /* dir == 1 */ 
  {
    p->rtavl_rtag = RTAVL_CHILD;
    n->rtavl_link[1] = p->rtavl_link[1];
  }
n->rtavl_rtag = RTAVL_THREAD;
n->rtavl_balance = 0;
p->rtavl_link[dir] = n;
if (y == NULL) 
  {
    n->rtavl_link[1] = NULL;
    return &n->rtavl_data;
  }

This code is included in 421.