GCC Code Coverage Report
Directory: ./ Exec Total Coverage
File: lib/libc/stdlib/tsearch.c Lines: 0 50 0.0 %
Date: 2017-11-13 Branches: 0 36 0.0 %

Line Branch Exec Source
1
/*	$OpenBSD: tsearch.c,v 1.10 2015/09/26 16:03:48 guenther 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
8
 *
9
 * Written by reading the System V Interface Definition, not the code.
10
 *
11
 * Totally public domain.
12
 */
13
14
#include <search.h>
15
#include <stdlib.h>
16
17
typedef struct node_t {
18
    char	  *key;
19
    struct node_t *left, *right;
20
} node;
21
22
/* find or insert datum into search tree */
23
void *
24
tsearch(const void *vkey, void **vrootp,
25
    int (*compar)(const void *, const void *))
26
{
27
    node *q;
28
    char *key = (char *)vkey;
29
    node **rootp = (node **)vrootp;
30
31
    if (rootp == (struct node_t **)0)
32
	return ((void *)0);
33
    while (*rootp != (struct node_t *)0) {	/* Knuth's T1: */
34
	int r;
35
36
	if ((r = (*compar)(key, (*rootp)->key)) == 0)	/* T2: */
37
	    return ((void *)*rootp);		/* we found it! */
38
	rootp = (r < 0) ?
39
	    &(*rootp)->left :		/* T3: follow left branch */
40
	    &(*rootp)->right;		/* T4: follow right branch */
41
    }
42
    q = malloc(sizeof(node));	/* T5: key not found */
43
    if (q != (struct node_t *)0) {	/* make new node */
44
	*rootp = q;			/* link new node to old */
45
	q->key = key;			/* initialize new node */
46
	q->left = q->right = (struct node_t *)0;
47
    }
48
    return ((void *)q);
49
}
50
51
/* delete node with given key */
52
void *
53
tdelete(const void *vkey, void **vrootp,
54
    int (*compar)(const void *, const void *))
55
{
56
    node **rootp = (node **)vrootp;
57
    char *key = (char *)vkey;
58
    node *p = (node *)1;
59
    node *q;
60
    node *r;
61
    int cmp;
62
63
    if (rootp == (struct node_t **)0 || *rootp == (struct node_t *)0)
64
	return ((struct node_t *)0);
65
    while ((cmp = (*compar)(key, (*rootp)->key)) != 0) {
66
	p = *rootp;
67
	rootp = (cmp < 0) ?
68
	    &(*rootp)->left :		/* follow left branch */
69
	    &(*rootp)->right;		/* follow right branch */
70
	if (*rootp == (struct node_t *)0)
71
	    return ((void *)0);		/* key not found */
72
    }
73
    r = (*rootp)->right;			/* D1: */
74
    if ((q = (*rootp)->left) == (struct node_t *)0)	/* Left (struct node_t *)0? */
75
	q = r;
76
    else if (r != (struct node_t *)0) {		/* Right link is null? */
77
	if (r->left == (struct node_t *)0) {	/* D2: Find successor */
78
	    r->left = q;
79
	    q = r;
80
	} else {			/* D3: Find (struct node_t *)0 link */
81
	    for (q = r->left; q->left != (struct node_t *)0; q = r->left)
82
		r = q;
83
	    r->left = q->right;
84
	    q->left = (*rootp)->left;
85
	    q->right = (*rootp)->right;
86
	}
87
    }
88
    free((struct node_t *) *rootp);	/* D4: Free node */
89
    *rootp = q;				/* link parent to new node */
90
    return(p);
91
}
92
93
/* Walk the nodes of a tree */
94
static void
95
trecurse(node *root, void (*action)(const void *, VISIT, int), int level)
96
{
97
    if (root->left == (struct node_t *)0 && root->right == (struct node_t *)0)
98
	(*action)(root, leaf, level);
99
    else {
100
	(*action)(root, preorder, level);
101
	if (root->left != (struct node_t *)0)
102
	    trecurse(root->left, action, level + 1);
103
	(*action)(root, postorder, level);
104
	if (root->right != (struct node_t *)0)
105
	    trecurse(root->right, action, level + 1);
106
	(*action)(root, endorder, level);
107
    }
108
}
109
110
/* Walk the nodes of a tree */
111
void
112
twalk(const void *vroot, void (*action)(const void *, VISIT, int))
113
{
114
    node *root = (node *)vroot;
115
116
    if (root != (node *)0 && action != (void (*)(const void *, VISIT, int))0)
117
	trecurse(root, action, 0);
118
}