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