xref: /illumos-gate/usr/src/cmd/logadm/lut.c (revision 7c478bd9)
1*7c478bd9Sstevel@tonic-gate /*
2*7c478bd9Sstevel@tonic-gate  * CDDL HEADER START
3*7c478bd9Sstevel@tonic-gate  *
4*7c478bd9Sstevel@tonic-gate  * The contents of this file are subject to the terms of the
5*7c478bd9Sstevel@tonic-gate  * Common Development and Distribution License, Version 1.0 only
6*7c478bd9Sstevel@tonic-gate  * (the "License").  You may not use this file except in compliance
7*7c478bd9Sstevel@tonic-gate  * with the License.
8*7c478bd9Sstevel@tonic-gate  *
9*7c478bd9Sstevel@tonic-gate  * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE
10*7c478bd9Sstevel@tonic-gate  * or http://www.opensolaris.org/os/licensing.
11*7c478bd9Sstevel@tonic-gate  * See the License for the specific language governing permissions
12*7c478bd9Sstevel@tonic-gate  * and limitations under the License.
13*7c478bd9Sstevel@tonic-gate  *
14*7c478bd9Sstevel@tonic-gate  * When distributing Covered Code, include this CDDL HEADER in each
15*7c478bd9Sstevel@tonic-gate  * file and include the License file at usr/src/OPENSOLARIS.LICENSE.
16*7c478bd9Sstevel@tonic-gate  * If applicable, add the following below this CDDL HEADER, with the
17*7c478bd9Sstevel@tonic-gate  * fields enclosed by brackets "[]" replaced with your own identifying
18*7c478bd9Sstevel@tonic-gate  * information: Portions Copyright [yyyy] [name of copyright owner]
19*7c478bd9Sstevel@tonic-gate  *
20*7c478bd9Sstevel@tonic-gate  * CDDL HEADER END
21*7c478bd9Sstevel@tonic-gate  */
22*7c478bd9Sstevel@tonic-gate /*
23*7c478bd9Sstevel@tonic-gate  * Copyright (c) 2001 by Sun Microsystems, Inc.
24*7c478bd9Sstevel@tonic-gate  * All rights reserved.
25*7c478bd9Sstevel@tonic-gate  *
26*7c478bd9Sstevel@tonic-gate  * logadm/lut.c -- simple lookup table module
27*7c478bd9Sstevel@tonic-gate  *
28*7c478bd9Sstevel@tonic-gate  * this file contains a very simple lookup table (lut) implementation.
29*7c478bd9Sstevel@tonic-gate  * the tables only support insert & lookup, no delete, and can
30*7c478bd9Sstevel@tonic-gate  * only be walked in lexical order.  if the key already exists
31*7c478bd9Sstevel@tonic-gate  * for something being inserted, the previous entry is simply
32*7c478bd9Sstevel@tonic-gate  * replaced.  the left-hand-side (lhs), which is the key, is
33*7c478bd9Sstevel@tonic-gate  * copied into malloc'd memory.  the right-hand-side (rhs), which
34*7c478bd9Sstevel@tonic-gate  * is the datum, is not copied (in fact, the lut routines don't
35*7c478bd9Sstevel@tonic-gate  * know the size or type of the datum, just the void * pointer to it).
36*7c478bd9Sstevel@tonic-gate  *
37*7c478bd9Sstevel@tonic-gate  * yea, this module could be much fancier and do much more, but
38*7c478bd9Sstevel@tonic-gate  * the idea was to keep it really simple and just provide what
39*7c478bd9Sstevel@tonic-gate  * was needed by logadm for options processing.
40*7c478bd9Sstevel@tonic-gate  */
41*7c478bd9Sstevel@tonic-gate 
42*7c478bd9Sstevel@tonic-gate #pragma ident	"%Z%%M%	%I%	%E% SMI"
43*7c478bd9Sstevel@tonic-gate 
44*7c478bd9Sstevel@tonic-gate #include <stdio.h>
45*7c478bd9Sstevel@tonic-gate #include <strings.h>
46*7c478bd9Sstevel@tonic-gate #include "err.h"
47*7c478bd9Sstevel@tonic-gate #include "lut.h"
48*7c478bd9Sstevel@tonic-gate 
49*7c478bd9Sstevel@tonic-gate /* forward declarations of functions private to this module */
50*7c478bd9Sstevel@tonic-gate static void dooper(const char *lhs, void *rhs, void *arg);
51*7c478bd9Sstevel@tonic-gate 
52*7c478bd9Sstevel@tonic-gate /* info created by lut_add() and lut_dup(), private to this module */
53*7c478bd9Sstevel@tonic-gate struct lut {
54*7c478bd9Sstevel@tonic-gate 	struct lut *lut_left;
55*7c478bd9Sstevel@tonic-gate 	struct lut *lut_right;
56*7c478bd9Sstevel@tonic-gate 	char *lut_lhs;		/* search key */
57*7c478bd9Sstevel@tonic-gate 	void *lut_rhs;		/* the datum */
58*7c478bd9Sstevel@tonic-gate };
59*7c478bd9Sstevel@tonic-gate 
60*7c478bd9Sstevel@tonic-gate /*
61*7c478bd9Sstevel@tonic-gate  * lut_add -- add an entry to the table
62*7c478bd9Sstevel@tonic-gate  *
63*7c478bd9Sstevel@tonic-gate  * use it like this:
64*7c478bd9Sstevel@tonic-gate  *	struct lut *root = NULL;
65*7c478bd9Sstevel@tonic-gate  *	root = lut_add(root, "key", value);
66*7c478bd9Sstevel@tonic-gate  *
67*7c478bd9Sstevel@tonic-gate  * the key string gets strdup'd by lut_add(), but the memory holding
68*7c478bd9Sstevel@tonic-gate  * the *value should not be freed until the lut is freed by lut_free().
69*7c478bd9Sstevel@tonic-gate  */
70*7c478bd9Sstevel@tonic-gate struct lut *
71*7c478bd9Sstevel@tonic-gate lut_add(struct lut *root, const char *lhs, void *rhs)
72*7c478bd9Sstevel@tonic-gate {
73*7c478bd9Sstevel@tonic-gate 	int diff;
74*7c478bd9Sstevel@tonic-gate 
75*7c478bd9Sstevel@tonic-gate 	if (root == NULL) {
76*7c478bd9Sstevel@tonic-gate 		/* not in tree, create new node */
77*7c478bd9Sstevel@tonic-gate 		root = MALLOC(sizeof (*root));
78*7c478bd9Sstevel@tonic-gate 		root->lut_lhs = STRDUP(lhs);
79*7c478bd9Sstevel@tonic-gate 		root->lut_rhs = rhs;
80*7c478bd9Sstevel@tonic-gate 		root->lut_left = root->lut_right = NULL;
81*7c478bd9Sstevel@tonic-gate 	} else if ((diff = strcmp(root->lut_lhs, lhs)) == 0) {
82*7c478bd9Sstevel@tonic-gate 		/* already in tree, replace node */
83*7c478bd9Sstevel@tonic-gate 		root->lut_rhs = rhs;
84*7c478bd9Sstevel@tonic-gate 	} else if (diff > 0)
85*7c478bd9Sstevel@tonic-gate 		root->lut_left = lut_add(root->lut_left, lhs, rhs);
86*7c478bd9Sstevel@tonic-gate 	else
87*7c478bd9Sstevel@tonic-gate 		root->lut_right = lut_add(root->lut_right, lhs, rhs);
88*7c478bd9Sstevel@tonic-gate 	return (root);
89*7c478bd9Sstevel@tonic-gate }
90*7c478bd9Sstevel@tonic-gate 
91*7c478bd9Sstevel@tonic-gate /* helper function for lut_dup() */
92*7c478bd9Sstevel@tonic-gate static void
93*7c478bd9Sstevel@tonic-gate dooper(const char *lhs, void *rhs, void *arg)
94*7c478bd9Sstevel@tonic-gate {
95*7c478bd9Sstevel@tonic-gate 	struct lut **rootp = (struct lut **)arg;
96*7c478bd9Sstevel@tonic-gate 
97*7c478bd9Sstevel@tonic-gate 	*rootp = lut_add(*rootp, lhs, rhs);
98*7c478bd9Sstevel@tonic-gate }
99*7c478bd9Sstevel@tonic-gate 
100*7c478bd9Sstevel@tonic-gate /*
101*7c478bd9Sstevel@tonic-gate  * lut_dup -- duplicate a lookup table
102*7c478bd9Sstevel@tonic-gate  *
103*7c478bd9Sstevel@tonic-gate  * caller is responsible for keeping track of how many tables are keeping
104*7c478bd9Sstevel@tonic-gate  * pointers to the void * datum values.
105*7c478bd9Sstevel@tonic-gate  */
106*7c478bd9Sstevel@tonic-gate struct lut *
107*7c478bd9Sstevel@tonic-gate lut_dup(struct lut *root)
108*7c478bd9Sstevel@tonic-gate {
109*7c478bd9Sstevel@tonic-gate 	struct lut *ret = NULL;
110*7c478bd9Sstevel@tonic-gate 
111*7c478bd9Sstevel@tonic-gate 	lut_walk(root, dooper, &ret);
112*7c478bd9Sstevel@tonic-gate 
113*7c478bd9Sstevel@tonic-gate 	return (ret);
114*7c478bd9Sstevel@tonic-gate }
115*7c478bd9Sstevel@tonic-gate 
116*7c478bd9Sstevel@tonic-gate /*
117*7c478bd9Sstevel@tonic-gate  * lut_lookup -- find an entry
118*7c478bd9Sstevel@tonic-gate  */
119*7c478bd9Sstevel@tonic-gate void *
120*7c478bd9Sstevel@tonic-gate lut_lookup(struct lut *root, const char *lhs)
121*7c478bd9Sstevel@tonic-gate {
122*7c478bd9Sstevel@tonic-gate 	int diff;
123*7c478bd9Sstevel@tonic-gate 
124*7c478bd9Sstevel@tonic-gate 	if (root == NULL)
125*7c478bd9Sstevel@tonic-gate 		return (NULL);
126*7c478bd9Sstevel@tonic-gate 	else if ((diff = strcmp(root->lut_lhs, lhs)) == 0)
127*7c478bd9Sstevel@tonic-gate 		return (root->lut_rhs);
128*7c478bd9Sstevel@tonic-gate 	else if (diff > 0)
129*7c478bd9Sstevel@tonic-gate 		return (lut_lookup(root->lut_left, lhs));
130*7c478bd9Sstevel@tonic-gate 	else
131*7c478bd9Sstevel@tonic-gate 		return (lut_lookup(root->lut_right, lhs));
132*7c478bd9Sstevel@tonic-gate }
133*7c478bd9Sstevel@tonic-gate 
134*7c478bd9Sstevel@tonic-gate /*
135*7c478bd9Sstevel@tonic-gate  * lut_walk -- walk the table in lexical order
136*7c478bd9Sstevel@tonic-gate  */
137*7c478bd9Sstevel@tonic-gate void
138*7c478bd9Sstevel@tonic-gate lut_walk(struct lut *root,
139*7c478bd9Sstevel@tonic-gate     void (*callback)(const char *lhs, void *rhs, void *arg), void *arg)
140*7c478bd9Sstevel@tonic-gate {
141*7c478bd9Sstevel@tonic-gate 	if (root) {
142*7c478bd9Sstevel@tonic-gate 		lut_walk(root->lut_left, callback, arg);
143*7c478bd9Sstevel@tonic-gate 		(*callback)(root->lut_lhs, root->lut_rhs, arg);
144*7c478bd9Sstevel@tonic-gate 		lut_walk(root->lut_right, callback, arg);
145*7c478bd9Sstevel@tonic-gate 	}
146*7c478bd9Sstevel@tonic-gate }
147*7c478bd9Sstevel@tonic-gate 
148*7c478bd9Sstevel@tonic-gate /*
149*7c478bd9Sstevel@tonic-gate  * lut_free -- free a lut
150*7c478bd9Sstevel@tonic-gate  *
151*7c478bd9Sstevel@tonic-gate  * if callback is provided, it is called for each value in the table.
152*7c478bd9Sstevel@tonic-gate  * it the values are things that the caller malloc'd, then you can do:
153*7c478bd9Sstevel@tonic-gate  *	lut_free(root, free);
154*7c478bd9Sstevel@tonic-gate  */
155*7c478bd9Sstevel@tonic-gate void
156*7c478bd9Sstevel@tonic-gate lut_free(struct lut *root, void (*callback)(void *rhs))
157*7c478bd9Sstevel@tonic-gate {
158*7c478bd9Sstevel@tonic-gate 	if (root) {
159*7c478bd9Sstevel@tonic-gate 		lut_free(root->lut_left, callback);
160*7c478bd9Sstevel@tonic-gate 		lut_free(root->lut_right, callback);
161*7c478bd9Sstevel@tonic-gate 		FREE(root->lut_lhs);
162*7c478bd9Sstevel@tonic-gate 		if (callback)
163*7c478bd9Sstevel@tonic-gate 			(*callback)(root->lut_rhs);
164*7c478bd9Sstevel@tonic-gate 		FREE(root);
165*7c478bd9Sstevel@tonic-gate 	}
166*7c478bd9Sstevel@tonic-gate }
167*7c478bd9Sstevel@tonic-gate 
168*7c478bd9Sstevel@tonic-gate 
169*7c478bd9Sstevel@tonic-gate #ifdef	TESTMODULE
170*7c478bd9Sstevel@tonic-gate 
171*7c478bd9Sstevel@tonic-gate void
172*7c478bd9Sstevel@tonic-gate printer(const char *lhs, void *rhs, void *arg)
173*7c478bd9Sstevel@tonic-gate {
174*7c478bd9Sstevel@tonic-gate 	struct lut *root = (struct lut *)arg;
175*7c478bd9Sstevel@tonic-gate 
176*7c478bd9Sstevel@tonic-gate 	printf("<%s> <%s> (<%s>)\n", lhs, (char *)rhs,
177*7c478bd9Sstevel@tonic-gate 	    (char *)lut_lookup(arg, lhs));
178*7c478bd9Sstevel@tonic-gate }
179*7c478bd9Sstevel@tonic-gate 
180*7c478bd9Sstevel@tonic-gate /*
181*7c478bd9Sstevel@tonic-gate  * test main for lut module, usage: a.out [lhs[=rhs]...]
182*7c478bd9Sstevel@tonic-gate  */
183*7c478bd9Sstevel@tonic-gate main(int argc, char *argv[])
184*7c478bd9Sstevel@tonic-gate {
185*7c478bd9Sstevel@tonic-gate 	struct lut *r = NULL;
186*7c478bd9Sstevel@tonic-gate 	struct lut *dupr = NULL;
187*7c478bd9Sstevel@tonic-gate 	char *equals;
188*7c478bd9Sstevel@tonic-gate 
189*7c478bd9Sstevel@tonic-gate 	err_init(argv[0]);
190*7c478bd9Sstevel@tonic-gate 	setbuf(stdout, NULL);
191*7c478bd9Sstevel@tonic-gate 
192*7c478bd9Sstevel@tonic-gate 	for (argv++; *argv; argv++)
193*7c478bd9Sstevel@tonic-gate 		if ((equals = strchr(*argv, '=')) != NULL) {
194*7c478bd9Sstevel@tonic-gate 			*equals++ = '\0';
195*7c478bd9Sstevel@tonic-gate 			r = lut_add(r, *argv, equals);
196*7c478bd9Sstevel@tonic-gate 		} else
197*7c478bd9Sstevel@tonic-gate 			r = lut_add(r, *argv, "NULL");
198*7c478bd9Sstevel@tonic-gate 
199*7c478bd9Sstevel@tonic-gate 	printf("lut contains:\n");
200*7c478bd9Sstevel@tonic-gate 	lut_walk(r, printer, r);
201*7c478bd9Sstevel@tonic-gate 
202*7c478bd9Sstevel@tonic-gate 	dupr = lut_dup(r);
203*7c478bd9Sstevel@tonic-gate 
204*7c478bd9Sstevel@tonic-gate 	lut_free(r, NULL);
205*7c478bd9Sstevel@tonic-gate 
206*7c478bd9Sstevel@tonic-gate 	printf("dup lut contains:\n");
207*7c478bd9Sstevel@tonic-gate 	lut_walk(dupr, printer, dupr);
208*7c478bd9Sstevel@tonic-gate 
209*7c478bd9Sstevel@tonic-gate 	lut_free(dupr, NULL);
210*7c478bd9Sstevel@tonic-gate 
211*7c478bd9Sstevel@tonic-gate 	err_done(0);
212*7c478bd9Sstevel@tonic-gate }
213*7c478bd9Sstevel@tonic-gate 
214*7c478bd9Sstevel@tonic-gate #endif	/* TESTMODULE */
215