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
44static struct stats *Addtotal;
45static struct stats *Lookuptotal;
46static struct stats *Freetotal;
47
48void
49lut_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
56void
57lut_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 */
77struct lut *
78lut_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
115void *
116lut_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
138void *
139lut_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 */
164void
165lut_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 */
204void
205lut_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