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 2006 Sun Microsystems, Inc. All rights reserved.
23 * Use is subject to license terms.
24 *
25 * logadm/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 lexical order. if the key already exists
30 * for something being inserted, the previous entry is simply
31 * replaced. the left-hand-side (lhs), which is the key, is
32 * copied into malloc'd memory. the right-hand-side (rhs), which
33 * is the datum, is not copied (in fact, the lut routines don't
34 * know the size or type of the datum, just the void * pointer to it).
35 *
36 * yea, this module could be much fancier and do much more, but
37 * the idea was to keep it really simple and just provide what
38 * was needed by logadm for options processing.
39 */
40
41 #pragma ident "%Z%%M% %I% %E% SMI"
42
43 #include <stdio.h>
44 #include <strings.h>
45 #include "err.h"
46 #include "lut.h"
47
48 /* forward declarations of functions private to this module */
49 static void dooper(const char *lhs, void *rhs, void *arg);
50
51 /* info created by lut_add() and lut_dup(), private to this module */
52 struct lut {
53 struct lut *lut_left;
54 struct lut *lut_right;
55 char *lut_lhs; /* search key */
56 void *lut_rhs; /* the datum */
57 };
58
59 /*
60 * lut_add -- add an entry to the table
61 *
62 * use it like this:
63 * struct lut *root = NULL;
64 * root = lut_add(root, "key", value);
65 *
66 * the key string gets strdup'd by lut_add(), but the memory holding
67 * the *value should not be freed until the lut is freed by lut_free().
68 */
69 struct lut *
lut_add(struct lut * root,const char * lhs,void * rhs)70 lut_add(struct lut *root, const char *lhs, void *rhs)
71 {
72 int diff = 0;
73
74 if (root == NULL) {
75 /* not in tree, create new node */
76 root = MALLOC(sizeof (*root));
77 root->lut_lhs = STRDUP(lhs);
78 root->lut_rhs = rhs;
79 root->lut_left = root->lut_right = NULL;
80 } else if (lhs != NULL && (diff = strcmp(root->lut_lhs, lhs)) == 0) {
81 /* already in tree, replace node */
82 root->lut_rhs = rhs;
83 } else if (diff > 0)
84 root->lut_left = lut_add(root->lut_left, lhs, rhs);
85 else
86 root->lut_right = lut_add(root->lut_right, lhs, rhs);
87 return (root);
88 }
89
90 /* helper function for lut_dup() */
91 static void
dooper(const char * lhs,void * rhs,void * arg)92 dooper(const char *lhs, void *rhs, void *arg)
93 {
94 struct lut **rootp = (struct lut **)arg;
95
96 *rootp = lut_add(*rootp, lhs, rhs);
97 }
98
99 /*
100 * lut_dup -- duplicate a lookup table
101 *
102 * caller is responsible for keeping track of how many tables are keeping
103 * pointers to the void * datum values.
104 */
105 struct lut *
lut_dup(struct lut * root)106 lut_dup(struct lut *root)
107 {
108 struct lut *ret = NULL;
109
110 lut_walk(root, dooper, &ret);
111
112 return (ret);
113 }
114
115 /*
116 * lut_lookup -- find an entry
117 */
118 void *
lut_lookup(struct lut * root,const char * lhs)119 lut_lookup(struct lut *root, const char *lhs)
120 {
121 int diff;
122
123 if (root == NULL || lhs == NULL)
124 return (NULL);
125 else if ((diff = strcmp(root->lut_lhs, lhs)) == 0)
126 return (root->lut_rhs);
127 else if (diff > 0)
128 return (lut_lookup(root->lut_left, lhs));
129 else
130 return (lut_lookup(root->lut_right, lhs));
131 }
132
133 /*
134 * lut_walk -- walk the table in lexical order
135 */
136 void
lut_walk(struct lut * root,void (* callback)(const char * lhs,void * rhs,void * arg),void * arg)137 lut_walk(struct lut *root,
138 void (*callback)(const char *lhs, void *rhs, void *arg), void *arg)
139 {
140 if (root) {
141 lut_walk(root->lut_left, callback, arg);
142 (*callback)(root->lut_lhs, root->lut_rhs, arg);
143 lut_walk(root->lut_right, callback, arg);
144 }
145 }
146
147 /*
148 * lut_free -- free a lut
149 *
150 * if callback is provided, it is called for each value in the table.
151 * it the values are things that the caller malloc'd, then you can do:
152 * lut_free(root, free);
153 */
154 void
lut_free(struct lut * root,void (* callback)(void * rhs))155 lut_free(struct lut *root, void (*callback)(void *rhs))
156 {
157 if (root != NULL) {
158 lut_free(root->lut_left, callback);
159 lut_free(root->lut_right, callback);
160 FREE(root->lut_lhs);
161 if (callback)
162 (*callback)(root->lut_rhs);
163 FREE(root);
164 }
165 }
166
167
168 #ifdef TESTMODULE
169
170 void
printer(const char * lhs,void * rhs,void * arg)171 printer(const char *lhs, void *rhs, void *arg)
172 {
173 struct lut *root = (struct lut *)arg;
174
175 printf("<%s> <%s> (<%s>)\n", lhs, (char *)rhs,
176 (char *)lut_lookup(arg, lhs));
177 }
178
179 /*
180 * test main for lut module, usage: a.out [lhs[=rhs]...]
181 */
182 int
main(int argc,char * argv[])183 main(int argc, char *argv[])
184 {
185 struct lut *r = NULL;
186 struct lut *dupr = NULL;
187 char *equals;
188
189 err_init(argv[0]);
190 setbuf(stdout, NULL);
191
192 for (argv++; *argv; argv++)
193 if ((equals = strchr(*argv, '=')) != NULL) {
194 *equals++ = '\0';
195 r = lut_add(r, *argv, equals);
196 } else
197 r = lut_add(r, *argv, "NULL");
198
199 printf("lut contains:\n");
200 lut_walk(r, printer, r);
201
202 dupr = lut_dup(r);
203
204 lut_free(r, NULL);
205
206 printf("dup lut contains:\n");
207 lut_walk(dupr, printer, dupr);
208
209 lut_free(dupr, NULL);
210
211 err_done(0);
212 /* NOTREACHED */
213 return (0);
214 }
215
216 #endif /* TESTMODULE */
217