7.5 Search [ToC] [Index]     [Skip Back] [Skip Fwd]     [Prev] [Up] [Next]

In searching a TBST we just have to be careful to distinguish threads from child pointers. If we hit a thread link, then we've run off the bottom of the tree and the search is unsuccessful. Other that that, a search in a TBST works the same as in any other binary search tree.

255. <TBST search function 255> =
void *
tbst_find (const struct tbst_table *tree, const void *item)
{ const struct tbst_node *p; assert (tree != NULL && item != NULL); p = tree->tbst_root; if (p == NULL) return NULL; for (;;)
    { int cmp, dir; cmp = tree->tbst_compare (item, p->tbst_data, tree->tbst_param); if (cmp == 0) return p->tbst_data; dir = cmp > 0; if (p->tbst_tag[dir] == TBST_CHILD) p = p->tbst_link[dir]; else
        return NULL; } }

This code is included in 253, 302, and 338.