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 */
21void *
22tsearch (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}