tsearch.c revision 62321
1193323Sed/* $NetBSD: tsearch.c,v 1.3 1999/09/16 11:45:37 lukem Exp $ */ 2193323Sed/* $FreeBSD: head/lib/libc/stdlib/tsearch.c 62321 2000-07-01 06:55:11Z alfred $ */ 3193323Sed 4193323Sed/* 5193323Sed * Tree search generalized from Knuth (6.2.2) Algorithm T just like 6193323Sed * the AT&T man page says. 7193323Sed * 8193323Sed * The node_t structure is for internal use only, lint doesn't grok it. 9193323Sed * 10239462Sdim * Written by reading the System V Interface Definition, not the code. 11239462Sdim * 12239462Sdim * Totally public domain. 13193323Sed */ 14239462Sdim 15239462Sdim#include <sys/cdefs.h> 16193323Sed#if defined(LIBC_SCCS) && !defined(lint) 17193323Sed__RCSID("$NetBSD: tsearch.c,v 1.3 1999/09/16 11:45:37 lukem Exp $"); 18193323Sed#endif /* LIBC_SCCS and not lint */ 19249423Sdim 20193323Sed#include <assert.h> 21249423Sdim#define _SEARCH_PRIVATE 22226584Sdim#include <search.h> 23263508Sdim#include <stdlib.h> 24263508Sdim 25263508Sdim/* find or insert datum into search tree */ 26263508Sdimvoid * 27218885Sdimtsearch(vkey, vrootp, compar) 28193323Sed const void *vkey; /* key to be located */ 29218885Sdim void **vrootp; /* address of tree root */ 30249423Sdim int (*compar) __P((const void *, const void *)); 31193323Sed{ 32193323Sed node_t *q; 33193323Sed node_t **rootp = (node_t **)vrootp; 34234353Sdim 35249423Sdim if (rootp == NULL) 36198090Srdivacky return NULL; 37218885Sdim 38193323Sed while (*rootp != NULL) { /* Knuth's T1: */ 39193323Sed int r; 40193323Sed 41193323Sed if ((r = (*compar)(vkey, (*rootp)->key)) == 0) /* T2: */ 42218885Sdim return *rootp; /* we found it! */ 43193323Sed 44218885Sdim rootp = (r < 0) ? 45193323Sed &(*rootp)->llink : /* T3: follow left branch */ 46193323Sed &(*rootp)->rlink; /* T4: follow right branch */ 47193323Sed } 48193323Sed 49193323Sed q = malloc(sizeof(node_t)); /* T5: key not found */ 50193323Sed if (q != 0) { /* make new node */ 51193323Sed *rootp = q; /* link new node to old */ 52193323Sed /* LINTED const castaway ok */ 53193323Sed q->key = (void *)vkey; /* initialize new node */ 54193323Sed q->llink = q->rlink = NULL; 55193323Sed } 56193323Sed return q; 57193323Sed} 58193323Sed