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

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

340. <Step 1: Search TRB tree for insertion point 340> =
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 339.

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

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

This code is included in 339 and 670.