126236Swpaul/* $NetBSD: tsearch.c,v 1.6 2011/05/18 19:36:36 dsl Exp $ */ 226236Swpaul 326236Swpaul/* 426236Swpaul * Tree search generalized from Knuth (6.2.2) Algorithm T just like 526236Swpaul * the AT&T man page says. 626236Swpaul * 726236Swpaul * The node_t structure is for internal use only, lint doesn't grok it. 826236Swpaul * 926236Swpaul * Written by reading the System V Interface Definition, not the code. 1026236Swpaul * 1150479Speter * Totally public domain. 1226236Swpaul */ 1326236Swpaul 1426236Swpaul#include <sys/cdefs.h> 1526236Swpaul#if defined(LIBC_SCCS) && !defined(lint) 1626236Swpaul__RCSID("$NetBSD: tsearch.c,v 1.6 2011/05/18 19:36:36 dsl Exp $"); 1726236Swpaul#endif /* LIBC_SCCS and not lint */ 1826236Swpaul 1926236Swpaul#include <assert.h> 2026236Swpaul#define _SEARCH_PRIVATE 2126236Swpaul#include <search.h> 2226236Swpaul#include <stdlib.h> 2326236Swpaul 2426236Swpaul/* find or insert datum into search tree */ 2526236Swpaulvoid * 2626236Swpaultsearch(const void *vkey, void **vrootp, 2726236Swpaul int (*compar)(const void *, const void *)) 2826236Swpaul{ 2926236Swpaul node_t *q; 3026236Swpaul node_t **rootp = (node_t **)vrootp; 3126236Swpaul 3226236Swpaul _DIAGASSERT(vkey != NULL); 3326236Swpaul _DIAGASSERT(compar != NULL); 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 q->key = __UNCONST(vkey); /* initialize new node */ 53 q->llink = q->rlink = NULL; 54 } 55 return q; 56} 57