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