1*9e66e6d7Sabs /* $NetBSD: tfind.c,v 1.7 2012/06/25 22:32:45 abs Exp $ */
27975455dSchristos
37975455dSchristos /*
47975455dSchristos * Tree search generalized from Knuth (6.2.2) Algorithm T just like
57975455dSchristos * the AT&T man page says.
67975455dSchristos *
77975455dSchristos * The node_t structure is for internal use only, lint doesn't grok it.
87975455dSchristos *
97975455dSchristos * Written by reading the System V Interface Definition, not the code.
107975455dSchristos *
117975455dSchristos * Totally public domain.
127975455dSchristos */
137975455dSchristos
147975455dSchristos #include <sys/cdefs.h>
157975455dSchristos #if defined(LIBC_SCCS) && !defined(lint)
16*9e66e6d7Sabs __RCSID("$NetBSD: tfind.c,v 1.7 2012/06/25 22:32:45 abs Exp $");
177975455dSchristos #endif /* LIBC_SCCS and not lint */
187975455dSchristos
19b48252f3Slukem #include <assert.h>
207975455dSchristos #define _SEARCH_PRIVATE
217975455dSchristos #include <stdlib.h>
227975455dSchristos #include <search.h>
237975455dSchristos
24*9e66e6d7Sabs /* find a node by key "vkey" in tree "vrootp", or return 0 */
257975455dSchristos void *
tfind(const void * vkey,void * const * vrootp,int (* compar)(const void *,const void *))26*9e66e6d7Sabs tfind(const void *vkey, void * const *vrootp,
27*9e66e6d7Sabs int (*compar)(const void *, const void *))
287975455dSchristos {
29a6636f0fSkleink node_t * const *rootp = (node_t * const*)vrootp;
307975455dSchristos
31b48252f3Slukem _DIAGASSERT(vkey != NULL);
32b48252f3Slukem _DIAGASSERT(compar != NULL);
33b48252f3Slukem
347975455dSchristos if (rootp == NULL)
357975455dSchristos return NULL;
367975455dSchristos
377975455dSchristos while (*rootp != NULL) { /* T1: */
387975455dSchristos int r;
397975455dSchristos
407975455dSchristos if ((r = (*compar)(vkey, (*rootp)->key)) == 0) /* T2: */
417975455dSchristos return *rootp; /* key found */
427975455dSchristos rootp = (r < 0) ?
437975455dSchristos &(*rootp)->llink : /* T3: follow left branch */
447975455dSchristos &(*rootp)->rlink; /* T4: follow right branch */
457975455dSchristos }
467975455dSchristos return NULL;
477975455dSchristos }
48