Return to tfind.c CVS log

Up to [cvs.NetBSD.org] / src / lib / libc / stdlib

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

1.2     ! lukem       1: /*     $NetBSD: tfind.c,v 1.1 1999/02/22 10:33:15 christos 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.2     ! lukem      16: __RCSID("$NetBSD: tfind.c,v 1.1 1999/02/22 10:33:15 christos 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 */
                     28:        void **vrootp;                  /* address of the tree root */
                     29:        int (*compar) __P((const void *, const void *));
                     30: {
                     31:        node_t **rootp = (node_t **)vrootp;
1.2     ! lukem      32:
        !            33:        _DIAGASSERT(vkey != NULL);
        !            34:        _DIAGASSERT(compar != NULL);
        !            35: #ifdef _DIAGNOSTIC
        !            36:        if (vkey == NULL || compar == NULL)
        !            37:                return (NULL);
        !            38: #endif
1.1       christos   39:
                     40:        if (rootp == NULL)
                     41:                return NULL;
                     42:
                     43:        while (*rootp != NULL) {                /* T1: */
                     44:                int r;
                     45:
                     46:                if ((r = (*compar)(vkey, (*rootp)->key)) == 0)  /* T2: */
                     47:                        return *rootp;          /* key found */
                     48:                rootp = (r < 0) ?
                     49:                    &(*rootp)->llink :          /* T3: follow left branch */
                     50:                    &(*rootp)->rlink;           /* T4: follow right branch */
                     51:        }
                     52:        return NULL;
                     53: }