1 /* $NetBSD: tsearch.c,v 1.4 1999/09/20 04:39:43 lukem 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, lint doesn't grok it.
8 *
9 * Written by reading the System V Interface Definition, not the code.
10 *
11 * Totally public domain.
12 */
13
14 #include <assert.h>
15 #define _SEARCH_PRIVATE
16 #include <search.h>
17 #include <stdlib.h>
18
19
20 /* find or insert datum into search tree */
21 void *
tsearch(const void * __restrict__ vkey,void ** __restrict__ vrootp,int (* compar)(const void *,const void *))22 tsearch (const void * __restrict__ vkey, /* key to be located */
23 void ** __restrict__ vrootp, /* address of tree root */
24 int (*compar) (const void *, const void *))
25 {
26 node_t *q, **n;
27 node_t **rootp = (node_t **)vrootp;
28
29 if (rootp == NULL)
30 return NULL;
31
32 n = rootp;
33 while (*n != NULL)
34 {
35 /* Knuth's T1: */
36 int r;
37
38 if ((r = (*compar)(vkey, ((*n)->key))) == 0) /* T2: */
39 return *n; /* we found it! */
40
41 n = (r < 0) ?
42 &(*rootp)->llink : /* T3: follow left branch */
43 &(*rootp)->rlink; /* T4: follow right branch */
44 if (*n == NULL)
45 break;
46 rootp = n;
47 }
48
49 q = malloc(sizeof(node_t)); /* T5: key not found */
50 if (!q)
51 return q;
52 *n = q;
53 /* make new node */
54 /* LINTED const castaway ok */
55 q->key = (void *)vkey; /* initialize new node */
56 q->llink = q->rlink = NULL;
57 return q;
58 }
59