[BACK]Return to tfind.c CVS log [TXT][DIR] Up to [cvs.NetBSD.org] / src / lib / libc / stdlib

Annotation of src/lib/libc/stdlib/tfind.c, Revision 1.5

1.5     ! kleink      1: /*     $NetBSD: tfind.c,v 1.4 2005/03/22 20:13:42 kleink Exp $ */
1.1       christos    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 defined(LIBC_SCCS) && !defined(lint)
1.5     ! kleink     16: __RCSID("$NetBSD: tfind.c,v 1.4 2005/03/22 20:13:42 kleink Exp $");
1.1       christos   17: #endif /* LIBC_SCCS and not lint */
                     18:
1.2       lukem      19: #include <assert.h>
1.1       christos   20: #define _SEARCH_PRIVATE
                     21: #include <stdlib.h>
                     22: #include <search.h>
                     23:
                     24: /* find a node, or return 0 */
                     25: void *
                     26: tfind(vkey, vrootp, compar)
                     27:        const void *vkey;               /* key to be found */
1.4       kleink     28:        void * const *vrootp;           /* address of the tree root */
1.1       christos   29:        int (*compar) __P((const void *, const void *));
                     30: {
1.5     ! kleink     31:        node_t * const *rootp = (node_t * const*)vrootp;
1.2       lukem      32:
                     33:        _DIAGASSERT(vkey != NULL);
                     34:        _DIAGASSERT(compar != NULL);
1.1       christos   35:
                     36:        if (rootp == NULL)
                     37:                return NULL;
                     38:
                     39:        while (*rootp != NULL) {                /* T1: */
                     40:                int r;
                     41:
                     42:                if ((r = (*compar)(vkey, (*rootp)->key)) == 0)  /* T2: */
                     43:                        return *rootp;          /* key found */
                     44:                rootp = (r < 0) ?
                     45:                    &(*rootp)->llink :          /* T3: follow left branch */
                     46:                    &(*rootp)->rlink;           /* T4: follow right branch */
                     47:        }
                     48:        return NULL;
                     49: }

CVSweb <webmaster@jp.NetBSD.org>