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
17typedef struct node_t {
18    char	  *key;
19    struct node_t *left, *right;
20} node;
21
22/* find or insert datum into search tree */
23void *
24tsearch(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 */
52void *
53tdelete(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 */
94static void
95trecurse(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 */
111void
112twalk(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}
119