9.3.1 Steps 1 and 2: Search and Insert

As usual, we search the tree from the root and record parents as we go.

338. <Step 1: Search TRB tree for insertion point 338> =
da[0] = 0;
pa[0] = (struct trb_node *) &tree->trb_root;
k = 1;
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;

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

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

This code is included in 337.

The code for insertion is included within the loop for easy access to the dir variable.

339. <Step 2: Insert TRB node 339> =
<Step 2: Insert TBST node; tbst => trb 256>
n->trb_color = TRB_RED;

This code is included in 337 and 668.