[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.1

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

CVSweb <webmaster@jp.NetBSD.org>