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

The structure of the insertion routine is predictable:

337. <TRB item insertion function 337> =
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 338> <Step 2: Insert TRB node 339> <Step 3: Rebalance after TRB insertion 340> return &n->trb_data; }

This code is included in 336.