xref: /illumos-gate/usr/src/lib/libc/port/gen/tsearch.c (revision 7257d1b4)
1 /*
2  * CDDL HEADER START
3  *
4  * The contents of this file are subject to the terms of the
5  * Common Development and Distribution License (the "License").
6  * You may not use this file except in compliance with the License.
7  *
8  * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE
9  * or http://www.opensolaris.org/os/licensing.
10  * See the License for the specific language governing permissions
11  * and limitations under the License.
12  *
13  * When distributing Covered Code, include this CDDL HEADER in each
14  * file and include the License file at usr/src/OPENSOLARIS.LICENSE.
15  * If applicable, add the following below this CDDL HEADER, with the
16  * fields enclosed by brackets "[]" replaced with your own identifying
17  * information: Portions Copyright [yyyy] [name of copyright owner]
18  *
19  * CDDL HEADER END
20  */
21 
22 /*
23  * Copyright 2008 Sun Microsystems, Inc.  All rights reserved.
24  * Use is subject to license terms.
25  */
26 
27 /*	Copyright (c) 1988 AT&T	*/
28 /*	  All Rights Reserved  	*/
29 
30 #pragma ident	"%Z%%M%	%I%	%E% SMI"
31 
32 /*
33  * Tree search algorithm, generalized from Knuth (6.2.2) Algorithm T.
34  *
35  *
36  * The NODE * arguments are declared in the lint files as char *,
37  * because the definition of NODE isn't available to the user.
38  */
39 
40 #pragma weak _tdelete = tdelete
41 #pragma weak _tsearch = tsearch
42 #pragma weak _twalk = twalk
43 
44 #include "lint.h"
45 #include "mtlib.h"
46 #include "libc.h"
47 #include <sys/types.h>
48 #include <search.h>
49 #include <stdlib.h>
50 #include <thread.h>
51 #include <synch.h>
52 
53 
54 
55 typedef struct node { char *key; struct node *llink, *rlink; } NODE;
56 
57 static void __twalk(NODE *, void (*)(const void *, VISIT, int), int);
58 
59 
60 /* Find or insert key into search tree */
61 void *
tsearch(const void * ky,void ** rtp,int (* compar)())62 tsearch(const void *ky, void **rtp, int (*compar)())
63 {
64 	char *key = (char *)ky;
65 	NODE **rootp = (NODE **)rtp;
66 	NODE *q;	/* New node if key not found */
67 
68 	if (rootp == NULL)
69 		return (NULL);
70 	while (*rootp != NULL) {			/* T1: */
71 		int r = (*compar)(key, (*rootp)->key);	/* T2: */
72 		if (r == 0)
73 			return ((void *)*rootp);	/* Key found */
74 		rootp = (r < 0) ?
75 		    &(*rootp)->llink :		/* T3: Take left branch */
76 		    &(*rootp)->rlink;		/* T4: Take right branch */
77 	}
78 	q = lmalloc(sizeof (NODE));		/* T5: Not found */
79 	if (q != NULL) {			/* Allocate new node */
80 		*rootp = q;			/* Link new node to old */
81 		q->key = key;			/* Initialize new node */
82 		q->llink = q->rlink = NULL;
83 	}
84 	return ((void *)q);
85 }
86 
87 /* Delete node with key key */
88 void *
tdelete(const void * ky,void ** rtp,int (* compar)())89 tdelete(const void *ky, void **rtp, int (*compar)())
90 {
91 	char *key = (char *)ky;
92 	NODE **rootp = (NODE **)rtp;
93 	NODE *p;		/* Parent of node to be deleted */
94 	NODE *q;	/* Successor node */
95 	NODE *r;	/* Right son node */
96 	int ans;		/* Result of comparison */
97 
98 	if (rootp == NULL || (p = *rootp) == NULL)
99 		return (NULL);
100 	while ((ans = (*compar)(key, (*rootp)->key)) != 0) {
101 		p = *rootp;
102 		rootp = (ans < 0) ?
103 		    &(*rootp)->llink :		/* Take left branch */
104 		    &(*rootp)->rlink;		/* Take right branch */
105 		if (*rootp == NULL)
106 			return (NULL);		/* Key not found */
107 	}
108 	r = (*rootp)->rlink;			/* D1: */
109 	if ((q = (*rootp)->llink) == NULL)	/* Llink NULL? */
110 		q = r;
111 	else if (r != NULL) {			/* Rlink NULL? */
112 		if (r->llink == NULL) {		/* D2: Find successor */
113 			r->llink = q;
114 			q = r;
115 		} else {			/* D3: Find NULL link */
116 			for (q = r->llink; q->llink != NULL; q = r->llink)
117 				r = q;
118 			r->llink = q->rlink;
119 			q->llink = (*rootp)->llink;
120 			q->rlink = (*rootp)->rlink;
121 		}
122 	}
123 	lfree(*rootp, sizeof (NODE));		/* D4: Free node */
124 	*rootp = q;			/* Link parent to replacement */
125 	return ((void *)p);
126 }
127 
128 
129 /* Walk the nodes of a tree */
130 void
twalk(const void * rt,void (* action)(const void *,VISIT,int))131 twalk(const void *rt,		/* Root of the tree to be walked */
132 	void (*action)(const void *, VISIT, int))
133 {
134 	NODE *root = (NODE *)rt;
135 
136 	if (root != NULL && action != NULL)
137 		__twalk(root, action, 0);
138 }
139 
140 
141 /* Walk the nodes of a tree */
142 static void
__twalk(NODE * root,void (* action)(const void *,VISIT,int),int level)143 __twalk(NODE *root,		/* Root of the tree to be walked */
144 	void (*action)(const void *, VISIT, int),
145 	int level)
146 {
147 	if (root->llink == NULL && root->rlink == NULL)
148 		(*action)(root, leaf, level);
149 	else {
150 		(*action)(root, preorder, level);
151 		if (root->llink != NULL)
152 			__twalk(root->llink, action, level + 1);
153 		(*action)(root, postorder, level);
154 		if (root->rlink != NULL)
155 			__twalk(root->rlink, action, level + 1);
156 		(*action)(root, endorder, level);
157 	}
158 }
159