1 | /* $NetBSD: tsearch.c,v 1.3 1999/09/16 11:45:37 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 <sys/cdefs.h> |
---|
15 | #if 0 |
---|
16 | #if defined(LIBC_SCCS) && !defined(lint) |
---|
17 | __RCSID("$NetBSD: tsearch.c,v 1.3 1999/09/16 11:45:37 lukem Exp $"); |
---|
18 | #endif /* LIBC_SCCS and not lint */ |
---|
19 | #endif |
---|
20 | |
---|
21 | #include <assert.h> |
---|
22 | #define _SEARCH_PRIVATE |
---|
23 | #include <search.h> |
---|
24 | #include <stdlib.h> |
---|
25 | |
---|
26 | /* find or insert datum into search tree */ |
---|
27 | void * |
---|
28 | tsearch (const void *vkey, /* key to be located */ |
---|
29 | void **vrootp, /* address of tree root */ |
---|
30 | int (*compar)(const void *, const void *)) |
---|
31 | { |
---|
32 | node_t *q; |
---|
33 | node_t **rootp = (node_t **)vrootp; |
---|
34 | |
---|
35 | if (rootp == NULL) |
---|
36 | return NULL; |
---|
37 | |
---|
38 | while (*rootp != NULL) { /* Knuth's T1: */ |
---|
39 | int r; |
---|
40 | |
---|
41 | if ((r = (*compar)(vkey, (*rootp)->key)) == 0) /* T2: */ |
---|
42 | return *rootp; /* we found it! */ |
---|
43 | |
---|
44 | rootp = (r < 0) ? |
---|
45 | &(*rootp)->llink : /* T3: follow left branch */ |
---|
46 | &(*rootp)->rlink; /* T4: follow right branch */ |
---|
47 | } |
---|
48 | |
---|
49 | q = malloc(sizeof(node_t)); /* T5: key not found */ |
---|
50 | if (q != 0) { /* make new node */ |
---|
51 | *rootp = q; /* link new node to old */ |
---|
52 | /* LINTED const castaway ok */ |
---|
53 | q->key = (void *)vkey; /* initialize new node */ |
---|
54 | q->llink = q->rlink = NULL; |
---|
55 | } |
---|
56 | return q; |
---|
57 | } |
---|