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 * Copyright 2007 Sun Microsystems, Inc. All rights reserved.
23 * Use is subject to license terms.
24 *
25 * lut.c -- simple lookup table module
26 *
27 * this file contains a very simple lookup table (lut) implementation.
28 * the tables only support insert & lookup, no delete, and can
29 * only be walked in one order. if the key already exists
30 * for something being inserted, the previous entry is simply
31 * replaced.
32 */
33
34 #pragma ident "%Z%%M% %I% %E% SMI"
35
36 #include <stdio.h>
37 #include "alloc.h"
38 #include "out.h"
39 #include "stats.h"
40 #include "lut.h"
41 #include "lut_impl.h"
42 #include "tree.h"
43
44 static struct stats *Addtotal;
45 static struct stats *Lookuptotal;
46 static struct stats *Freetotal;
47
48 void
lut_init(void)49 lut_init(void)
50 {
51 Addtotal = stats_new_counter("lut.adds", "total adds", 1);
52 Lookuptotal = stats_new_counter("lut.lookup", "total lookups", 1);
53 Freetotal = stats_new_counter("lut.frees", "total frees", 1);
54 }
55
56 void
lut_fini(void)57 lut_fini(void)
58 {
59 stats_delete(Addtotal);
60 stats_delete(Lookuptotal);
61 stats_delete(Freetotal);
62 }
63
64 /*
65 * lut_add -- add an entry to the table
66 *
67 * use it like this:
68 * struct lut *root = NULL;
69 * root = lut_add(root, key, value, cmp_func);
70 *
71 * the cmp_func can be strcmp(). pass in NULL and instead of
72 * calling a cmp_func the routine will just look at the difference
73 * between key pointers (useful when all strings are kept in a
74 * string table so they are equal if their pointers are equal).
75 *
76 */
77 struct lut *
lut_add(struct lut * root,void * lhs,void * rhs,lut_cmp cmp_func)78 lut_add(struct lut *root, void *lhs, void *rhs, lut_cmp cmp_func)
79 {
80 int diff;
81 struct lut **tmp_hdl = &root, *parent = NULL, *tmp = root;
82
83 while (tmp) {
84 if (cmp_func)
85 diff = (*cmp_func)(tmp->lut_lhs, lhs);
86 else
87 diff = (const char *)lhs - (const char *)tmp->lut_lhs;
88
89 if (diff == 0) {
90 /* already in tree, replace node */
91 tmp->lut_rhs = rhs;
92 return (root);
93 } else if (diff > 0) {
94 tmp_hdl = &(tmp->lut_left);
95 parent = tmp;
96 tmp = tmp->lut_left;
97 } else {
98 tmp_hdl = &(tmp->lut_right);
99 parent = tmp;
100 tmp = tmp->lut_right;
101 }
102 }
103
104 /* either empty tree or not in tree, so create new node */
105 *tmp_hdl = MALLOC(sizeof (*root));
106 (*tmp_hdl)->lut_lhs = lhs;
107 (*tmp_hdl)->lut_rhs = rhs;
108 (*tmp_hdl)->lut_parent = parent;
109 (*tmp_hdl)->lut_left = (*tmp_hdl)->lut_right = NULL;
110 stats_counter_bump(Addtotal);
111
112 return (root);
113 }
114
115 void *
lut_lookup(struct lut * root,void * lhs,lut_cmp cmp_func)116 lut_lookup(struct lut *root, void *lhs, lut_cmp cmp_func)
117 {
118 int diff;
119
120 stats_counter_bump(Lookuptotal);
121
122 while (root) {
123 if (cmp_func)
124 diff = (*cmp_func)(root->lut_lhs, lhs);
125 else
126 diff = (const char *)lhs - (const char *)root->lut_lhs;
127
128 if (diff == 0)
129 return (root->lut_rhs);
130 else if (diff > 0)
131 root = root->lut_left;
132 else
133 root = root->lut_right;
134 }
135 return (NULL);
136 }
137
138 void *
lut_lookup_lhs(struct lut * root,void * lhs,lut_cmp cmp_func)139 lut_lookup_lhs(struct lut *root, void *lhs, lut_cmp cmp_func)
140 {
141 int diff;
142
143 stats_counter_bump(Lookuptotal);
144
145 while (root) {
146 if (cmp_func)
147 diff = (*cmp_func)(root->lut_lhs, lhs);
148 else
149 diff = (const char *)lhs - (const char *)root->lut_lhs;
150
151 if (diff == 0)
152 return (root->lut_lhs);
153 else if (diff > 0)
154 root = root->lut_left;
155 else
156 root = root->lut_right;
157 }
158 return (NULL);
159 }
160
161 /*
162 * lut_walk -- walk the table in lexical order
163 */
164 void
lut_walk(struct lut * root,lut_cb callback,void * arg)165 lut_walk(struct lut *root, lut_cb callback, void *arg)
166 {
167 struct lut *tmp = root;
168 struct lut *prev_child = NULL;
169
170 if (root == NULL)
171 return;
172
173 while (tmp->lut_left != NULL)
174 tmp = tmp->lut_left;
175
176 /* do callback on leftmost node */
177 (*callback)(tmp->lut_lhs, tmp->lut_rhs, arg);
178
179 for (;;) {
180 if (tmp->lut_right != NULL && tmp->lut_right != prev_child) {
181 tmp = tmp->lut_right;
182 while (tmp->lut_left != NULL)
183 tmp = tmp->lut_left;
184
185 /* do callback on leftmost node */
186 (*callback)(tmp->lut_lhs, tmp->lut_rhs, arg);
187 } else if (tmp->lut_parent != NULL) {
188 prev_child = tmp;
189 tmp = tmp->lut_parent;
190 /*
191 * do callback on parent only if we're coming up
192 * from the left
193 */
194 if (tmp->lut_right != prev_child)
195 (*callback)(tmp->lut_lhs, tmp->lut_rhs, arg);
196 } else
197 return;
198 }
199 }
200
201 /*
202 * lut_free -- free the lut
203 */
204 void
lut_free(struct lut * root,lut_cb callback,void * arg)205 lut_free(struct lut *root, lut_cb callback, void *arg)
206 {
207 struct lut *tmp = root;
208 struct lut *prev_child = NULL;
209
210 if (root == NULL)
211 return;
212
213 while (tmp->lut_left != NULL)
214 tmp = tmp->lut_left;
215
216 /* do callback on leftmost node */
217 if (callback)
218 (*callback)(tmp->lut_lhs, tmp->lut_rhs, arg);
219
220 for (;;) {
221 if (tmp->lut_right != NULL && tmp->lut_right != prev_child) {
222 tmp = tmp->lut_right;
223 while (tmp->lut_left != NULL)
224 tmp = tmp->lut_left;
225
226 /* do callback on leftmost node */
227 if (callback)
228 (*callback)(tmp->lut_lhs, tmp->lut_rhs, arg);
229 } else if (tmp->lut_parent != NULL) {
230 prev_child = tmp;
231 tmp = tmp->lut_parent;
232 FREE(prev_child);
233 /*
234 * do callback on parent only if we're coming up
235 * from the left
236 */
237 if (tmp->lut_right != prev_child && callback)
238 (*callback)(tmp->lut_lhs, tmp->lut_rhs, arg);
239 } else {
240 /*
241 * free the root node and then we're done
242 */
243 FREE(tmp);
244 return;
245 }
246 }
247 }
248