1/*
2 * Tree search generalized from Knuth (6.2.2) Algorithm T just like
3 * the AT&T man page says.
4 *
5 * The node_t structure is for internal use only, lint doesn't grok it.
6 *
7 * Written by reading the System V Interface Definition, not the code.
8 *
9 * Totally public domain.
10 *
11 * $NetBSD: tsearch.c,v 1.3 1999/09/16 11:45:37 lukem Exp $
12 * $NetBSD: twalk.c,v 1.1 1999/02/22 10:33:16 christos Exp $
13 * $NetBSD: tdelete.c,v 1.2 1999/09/16 11:45:37 lukem Exp $
14 * $NetBSD: tfind.c,v 1.2 1999/09/16 11:45:37 lukem Exp $
15 */
16
17#include <config.h>
18#include "roken.h"
19#include "search.h"
20#include <stdlib.h>
21
22typedef struct node {
23  char         *key;
24  struct node  *llink, *rlink;
25} node_t;
26
27#ifndef __DECONST
28#define __DECONST(type, var)    ((type)(uintptr_t)(const void *)(var))
29#endif
30
31/*
32 * find or insert datum into search tree
33 *
34 * Parameters:
35 *	vkey:	key to be located
36 *	vrootp:	address of tree root
37 */
38
39ROKEN_LIB_FUNCTION void *
40rk_tsearch(const void *vkey, void **vrootp,
41	int (*compar)(const void *, const void *))
42{
43	node_t *q;
44	node_t **rootp = (node_t **)vrootp;
45
46	if (rootp == NULL)
47		return NULL;
48
49	while (*rootp != NULL) {	/* Knuth's T1: */
50		int r;
51
52		if ((r = (*compar)(vkey, (*rootp)->key)) == 0)	/* T2: */
53			return *rootp;		/* we found it! */
54
55		rootp = (r < 0) ?
56		    &(*rootp)->llink :		/* T3: follow left branch */
57		    &(*rootp)->rlink;		/* T4: follow right branch */
58	}
59
60	q = malloc(sizeof(node_t));		/* T5: key not found */
61	if (q != 0) {				/* make new node */
62		*rootp = q;			/* link new node to old */
63		/* LINTED const castaway ok */
64		q->key = __DECONST(void *, vkey); /* initialize new node */
65		q->llink = q->rlink = NULL;
66	}
67	return q;
68}
69
70/*
71 * Walk the nodes of a tree
72 *
73 * Parameters:
74 *	root:	Root of the tree to be walked
75 */
76static void
77trecurse(const node_t *root, void (*action)(const void *, VISIT, int),
78	 int level)
79{
80
81	if (root->llink == NULL && root->rlink == NULL)
82		(*action)(root, leaf, level);
83	else {
84		(*action)(root, preorder, level);
85		if (root->llink != NULL)
86			trecurse(root->llink, action, level + 1);
87		(*action)(root, postorder, level);
88		if (root->rlink != NULL)
89			trecurse(root->rlink, action, level + 1);
90		(*action)(root, endorder, level);
91	}
92}
93
94/*
95 * Walk the nodes of a tree
96 *
97 * Parameters:
98 *	vroot:	Root of the tree to be walked
99 */
100ROKEN_LIB_FUNCTION void
101rk_twalk(const void *vroot,
102      void (*action)(const void *, VISIT, int))
103{
104	if (vroot != NULL && action != NULL)
105		trecurse(vroot, action, 0);
106}
107
108/*
109 * delete node with given key
110 *
111 * vkey:   key to be deleted
112 * vrootp: address of the root of the tree
113 * compar: function to carry out node comparisons
114 */
115ROKEN_LIB_FUNCTION void *
116rk_tdelete(const void * vkey, void ** vrootp,
117	int (*compar)(const void *, const void *))
118{
119	node_t **rootp = (node_t **)vrootp;
120	node_t *p, *q, *r;
121	int cmp;
122
123	if (rootp == NULL || (p = *rootp) == NULL)
124		return NULL;
125
126	while ((cmp = (*compar)(vkey, (*rootp)->key)) != 0) {
127		p = *rootp;
128		rootp = (cmp < 0) ?
129		    &(*rootp)->llink :		/* follow llink branch */
130		    &(*rootp)->rlink;		/* follow rlink branch */
131		if (*rootp == NULL)
132			return NULL;		/* key not found */
133	}
134	r = (*rootp)->rlink;			/* D1: */
135	if ((q = (*rootp)->llink) == NULL)	/* Left NULL? */
136		q = r;
137	else if (r != NULL) {			/* Right link is NULL? */
138		if (r->llink == NULL) {		/* D2: Find successor */
139			r->llink = q;
140			q = r;
141		} else {			/* D3: Find NULL link */
142			for (q = r->llink; q->llink != NULL; q = r->llink)
143				r = q;
144			r->llink = q->rlink;
145			q->llink = (*rootp)->llink;
146			q->rlink = (*rootp)->rlink;
147		}
148	}
149	free(*rootp);				/* D4: Free node */
150	*rootp = q;				/* link parent to new node */
151	return p;
152}
153
154/*
155 * find a node, or return 0
156 *
157 * Parameters:
158 *	vkey:	key to be found
159 *	vrootp:	address of the tree root
160 */
161ROKEN_LIB_FUNCTION void *
162rk_tfind(const void *vkey, void * const *vrootp,
163      int (*compar)(const void *, const void *))
164{
165	node_t **rootp = (node_t **)vrootp;
166
167	if (rootp == NULL)
168		return NULL;
169
170	while (*rootp != NULL) {		/* T1: */
171		int r;
172
173		if ((r = (*compar)(vkey, (*rootp)->key)) == 0)	/* T2: */
174			return *rootp;		/* key found */
175		rootp = (r < 0) ?
176		    &(*rootp)->llink :		/* T3: follow left branch */
177		    &(*rootp)->rlink;		/* T4: follow right branch */
178	}
179	return NULL;
180}
181