| Elliott Hughes | b902641 | 2014-07-23 16:02:26 -0700 | [diff] [blame] | 1 | /* $OpenBSD: tfind.c,v 1.6 2014/03/16 18:38:30 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 | /*LINTLIBRARY*/ |
| 14 | #include <search.h> |
| 15 | |
| 16 | typedef struct node_t |
| 17 | { |
| 18 | char *key; |
| 19 | struct node_t *llink, *rlink; |
| 20 | } node; |
| 21 | |
| 22 | /* find a node, or return 0 */ |
| 23 | void * |
| 24 | tfind(const void *vkey, void * const *vrootp, |
| 25 | int (*compar)(const void *, const void *)) |
| 26 | { |
| 27 | char *key = (char *)vkey; |
| 28 | node **rootp = (node **)vrootp; |
| 29 | |
| 30 | if (rootp == (struct node_t **)0) |
| 31 | return ((struct node_t *)0); |
| 32 | while (*rootp != (struct node_t *)0) { /* T1: */ |
| 33 | int r; |
| 34 | if ((r = (*compar)(key, (*rootp)->key)) == 0) /* T2: */ |
| 35 | return (*rootp); /* key found */ |
| 36 | rootp = (r < 0) ? |
| 37 | &(*rootp)->llink : /* T3: follow left branch */ |
| 38 | &(*rootp)->rlink; /* T4: follow right branch */ |
| 39 | } |
| 40 | return (node *)0; |
| 41 | } |