12.3.1 Steps 1 and 2: Search and Insert [ToC] [Index]     [Skip Fwd]     [Prev] [Up] [Next]

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.