xref: /illumos-gate/usr/src/cmd/fm/eversholt/common/lut.c (revision 6cb1ca52)
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