7.5 Search

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.