| 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 * |
| 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 | } |