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