1*89cd0876Sguenther /* $OpenBSD: tfind.c,v 1.7 2015/09/26 16:03:48 guenther Exp $ */
248f0b646Sjsg
3e728c442Sderaadt /*
4e728c442Sderaadt * Tree search generalized from Knuth (6.2.2) Algorithm T just like
5e728c442Sderaadt * the AT&T man page says.
6e728c442Sderaadt *
7acf82b0aSguenther * The node_t structure is for internal use only
8e728c442Sderaadt *
9e728c442Sderaadt * Written by reading the System V Interface Definition, not the code.
10e728c442Sderaadt *
11e728c442Sderaadt * Totally public domain.
12e728c442Sderaadt */
13e728c442Sderaadt #include <search.h>
14e728c442Sderaadt
15e728c442Sderaadt typedef struct node_t
16e728c442Sderaadt {
17e728c442Sderaadt char *key;
18e728c442Sderaadt struct node_t *llink, *rlink;
19e728c442Sderaadt } node;
20e728c442Sderaadt
21e728c442Sderaadt /* find a node, or return 0 */
22e728c442Sderaadt void *
tfind(const void * vkey,void * const * vrootp,int (* compar)(const void *,const void *))23d8bc04e4Spat tfind(const void *vkey, void * const *vrootp,
24d8bc04e4Spat int (*compar)(const void *, const void *))
25e728c442Sderaadt {
26e728c442Sderaadt char *key = (char *)vkey;
27e728c442Sderaadt node **rootp = (node **)vrootp;
28e728c442Sderaadt
29e728c442Sderaadt if (rootp == (struct node_t **)0)
30e728c442Sderaadt return ((struct node_t *)0);
31e728c442Sderaadt while (*rootp != (struct node_t *)0) { /* T1: */
32e728c442Sderaadt int r;
33e728c442Sderaadt if ((r = (*compar)(key, (*rootp)->key)) == 0) /* T2: */
34e728c442Sderaadt return (*rootp); /* key found */
35e728c442Sderaadt rootp = (r < 0) ?
36e728c442Sderaadt &(*rootp)->llink : /* T3: follow left branch */
37e728c442Sderaadt &(*rootp)->rlink; /* T4: follow right branch */
38e728c442Sderaadt }
39e728c442Sderaadt return (node *)0;
40e728c442Sderaadt }
41