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