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

1.7     ! abs         1: /*     $NetBSD: tfind.c,v 1.6 2011/05/18 19:36:36 dsl 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.7     ! abs        16: __RCSID("$NetBSD: tfind.c,v 1.6 2011/05/18 19:36:36 dsl 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:
1.7     ! abs        24: /* find a node by key "vkey" in tree "vrootp", or return 0 */
1.1       christos   25: void *
1.7     ! abs        26: tfind(const void *vkey, void * const *vrootp,
        !            27:     int (*compar)(const void *, const void *))
1.1       christos   28: {
1.5       kleink     29:        node_t * const *rootp = (node_t * const*)vrootp;
1.2       lukem      30:
                     31:        _DIAGASSERT(vkey != NULL);
                     32:        _DIAGASSERT(compar != NULL);
1.1       christos   33:
                     34:        if (rootp == NULL)
                     35:                return NULL;
                     36:
                     37:        while (*rootp != NULL) {                /* T1: */
                     38:                int r;
                     39:
                     40:                if ((r = (*compar)(vkey, (*rootp)->key)) == 0)  /* T2: */
                     41:                        return *rootp;          /* key found */
                     42:                rootp = (r < 0) ?
                     43:                    &(*rootp)->llink :          /* T3: follow left branch */
                     44:                    &(*rootp)->rlink;           /* T4: follow right branch */
                     45:        }
                     46:        return NULL;
                     47: }

CVSweb <webmaster@jp.NetBSD.org>