8.5.1 Step 1: Search

We use p to search down the tree and keep track of p's parent with q. We keep the invariant at the beginning of the loop here that q->tavl_link[dir] == p. As the final step, we record the item deleted and update the tree's item count.

314. <Step 1: Search TAVL tree for item to delete 314> =
if (tree->tavl_root == NULL)
  return NULL;

q = (struct tavl_node *) &tree->tavl_root;
p = tree->tavl_root;
dir = 0;
for (;;) 
  {
    cmp = tree->tavl_compare (item, p->tavl_data, tree->tavl_param);
    if (cmp == 0)
      break;
    dir = cmp > 0;

    q = p;
    if (p->tavl_tag[dir] == TAVL_THREAD)
      return NULL;
    p = p->tavl_link[dir];
  }
item = p->tavl_data;

This code is included in 313 and 672.