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