OpenCores
URL https://opencores.org/ocsvn/openrisc_me/openrisc_me/trunk

Subversion Repositories openrisc_me

[/] [openrisc/] [trunk/] [gnu-src/] [newlib-1.17.0/] [newlib/] [libc/] [search/] [tsearch.c] - Blame information for rev 262

Go to most recent revision | Details | Compare with Previous | View Log

Line No. Rev Author Line
1 148 jeremybenn
/*      $NetBSD: tsearch.c,v 1.3 1999/09/16 11:45:37 lukem Exp $        */
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 0
16
#if defined(LIBC_SCCS) && !defined(lint)
17
__RCSID("$NetBSD: tsearch.c,v 1.3 1999/09/16 11:45:37 lukem Exp $");
18
#endif /* LIBC_SCCS and not lint */
19
#endif
20
 
21
#include <assert.h>
22
#define _SEARCH_PRIVATE
23
#include <search.h>
24
#include <stdlib.h>
25
 
26
/* find or insert datum into search tree */
27
void *
28
_DEFUN(tsearch, (vkey, vrootp, compar),
29
        const void *vkey _AND           /* key to be located */
30
        void **vrootp _AND              /* address of tree root */
31
        int (*compar)(const void *, const void *))
32
{
33
        node_t *q;
34
        node_t **rootp = (node_t **)vrootp;
35
 
36
        if (rootp == NULL)
37
                return NULL;
38
 
39
        while (*rootp != NULL) {        /* Knuth's T1: */
40
                int r;
41
 
42
                if ((r = (*compar)(vkey, (*rootp)->key)) == 0)   /* T2: */
43
                        return *rootp;          /* we found it! */
44
 
45
                rootp = (r < 0) ?
46
                    &(*rootp)->llink :          /* T3: follow left branch */
47
                    &(*rootp)->rlink;           /* T4: follow right branch */
48
        }
49
 
50
        q = malloc(sizeof(node_t));             /* T5: key not found */
51
        if (q != 0) {                            /* make new node */
52
                *rootp = q;                     /* link new node to old */
53
                /* LINTED const castaway ok */
54
                q->key = (void *)vkey;          /* initialize new node */
55
                q->llink = q->rlink = NULL;
56
        }
57
        return q;
58
}

powered by: WebSVN 2.1.0

© copyright 1999-2024 OpenCores.org, equivalent to Oliscience, all rights reserved. OpenCores®, registered trademark.