4.9.3.5 Starting at an Inserted Node [ToC] [Index]     [Skip Back] [Skip Fwd]     [Prev] [Up] [Next]

Another operation that can be useful is to insert a new node and construct a traverser to the inserted node in a single operation. The following code does this:

69. <BST traverser insertion initializer 69> =
void *
bst_t_insert (struct bst_traverser *trav, struct bst_table *tree, void *item)
{ struct bst_node **q; assert (tree != NULL && item != NULL); trav->bst_table = tree; trav->bst_height = 0; q = &tree->bst_root; while (*q != NULL)
    { int cmp = tree->bst_compare (item, (*q)->bst_data, tree->bst_param); if (cmp == 0)
        { trav->bst_node = *q; trav->bst_generation = tree->bst_generation; return (*q)->bst_data; } if (trav->bst_height >= BST_MAX_HEIGHT)
        { bst_balance (tree); return bst_t_insert (trav, tree, item); } trav->bst_stack[trav->bst_height++] = *q; q = &(*q)->bst_link[cmp > 0]; } trav->bst_node = *q = tree->bst_alloc->libavl_malloc (tree->bst_alloc,
                                                        sizeof **q); if (*q == NULL)
    { trav->bst_node = NULL; trav->bst_generation = tree->bst_generation; return NULL; } (*q)->bst_link[0] = (*q)->bst_link[1] = NULL; (*q)->bst_data = item; tree->bst_count++; trav->bst_generation = tree->bst_generation; return (*q)->bst_data; }

This code is included in 64.