9.3 Insertion [ToC] [Index]     [Skip Back] [Skip Fwd]     [Prev] [Up] [Next]

The structure of the insertion routine is predictable: 

339. <TRB item insertion function 339> =
void **
trb_probe (struct trb_table *tree, void *item) 
{
  struct trb_node *pa[TRB_MAX_HEIGHT]; /* Nodes on stack. */
  unsigned char da[TRB_MAX_HEIGHT];    /* Directions moved from stack nodes. */
  int k;                               /* Stack height. */

  struct trb_node *p; /* Traverses tree looking for insertion point. */
  struct trb_node *n; /* Newly inserted node. */
  int dir;            /* Side of p on which n is inserted. */

  assert (tree != NULL && item != NULL);

  <Step 1: Search TRB tree for insertion point 340>
  <Step 2: Insert TRB node 341>
  <Step 3: Rebalance after TRB insertion 342>

  return &n->trb_data;
}

This code is included in 338.