gdb - Local mods (compile)
[dragonfly.git] / lib / libc / stdlib / tfind.c
1 /*
2  * Tree search generalized from Knuth (6.2.2) Algorithm T just like
3  * the AT&T man page says.
4  *
5  * The node_t structure is for internal use only, lint doesn't grok it.
6  *
7  * Written by reading the System V Interface Definition, not the code.
8  *
9  * Totally public domain.
10  *
11  * $NetBSD: tfind.c,v 1.2 1999/09/16 11:45:37 lukem Exp $
12  * $FreeBSD: src/lib/libc/stdlib/tfind.c,v 1.5 2003/01/05 02:43:18 tjr Exp $
13  * $DragonFly: src/lib/libc/stdlib/tsearch.c,v 1.6 2005/11/24 17:18:30 swildner Exp $
14  */
15
16 #define _SEARCH_PRIVATE
17 #include <stdlib.h>
18 #include <search.h>
19
20 /*
21  * find a node, or return 0
22  *
23  * Parameters:
24  *      vkey:   key to be found
25  *      vrootp: address of the tree root
26  */
27 void *
28 tfind(const void *vkey, void * const *vrootp,
29       int (*compar)(const void *, const void *))
30 {
31         node_t **rootp = (node_t **)vrootp;
32
33         if (rootp == NULL)
34                 return NULL;
35
36         while (*rootp != NULL) {                /* T1: */
37                 int r;
38
39                 if ((r = (*compar)(vkey, (*rootp)->key)) == 0)  /* T2: */
40                         return *rootp;          /* key found */
41                 rootp = (r < 0) ?
42                     &(*rootp)->llink :          /* T3: follow left branch */
43                     &(*rootp)->rlink;           /* T4: follow right branch */
44         }
45         return NULL;
46 }