17c478bd9Sstevel@tonic-gate /*
27c478bd9Sstevel@tonic-gate * CDDL HEADER START
37c478bd9Sstevel@tonic-gate *
47c478bd9Sstevel@tonic-gate * The contents of this file are subject to the terms of the
5*b493790cSbasabi * Common Development and Distribution License (the "License").
6*b493790cSbasabi * You may not use this file except in compliance with the License.
77c478bd9Sstevel@tonic-gate *
87c478bd9Sstevel@tonic-gate * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE
97c478bd9Sstevel@tonic-gate * or http://www.opensolaris.org/os/licensing.
107c478bd9Sstevel@tonic-gate * See the License for the specific language governing permissions
117c478bd9Sstevel@tonic-gate * and limitations under the License.
127c478bd9Sstevel@tonic-gate *
137c478bd9Sstevel@tonic-gate * When distributing Covered Code, include this CDDL HEADER in each
147c478bd9Sstevel@tonic-gate * file and include the License file at usr/src/OPENSOLARIS.LICENSE.
157c478bd9Sstevel@tonic-gate * If applicable, add the following below this CDDL HEADER, with the
167c478bd9Sstevel@tonic-gate * fields enclosed by brackets "[]" replaced with your own identifying
177c478bd9Sstevel@tonic-gate * information: Portions Copyright [yyyy] [name of copyright owner]
187c478bd9Sstevel@tonic-gate *
197c478bd9Sstevel@tonic-gate * CDDL HEADER END
207c478bd9Sstevel@tonic-gate */
217c478bd9Sstevel@tonic-gate /*
22*b493790cSbasabi * Copyright 2006 Sun Microsystems, Inc. All rights reserved.
23*b493790cSbasabi * Use is subject to license terms.
247c478bd9Sstevel@tonic-gate *
257c478bd9Sstevel@tonic-gate * logadm/lut.c -- simple lookup table module
267c478bd9Sstevel@tonic-gate *
277c478bd9Sstevel@tonic-gate * this file contains a very simple lookup table (lut) implementation.
287c478bd9Sstevel@tonic-gate * the tables only support insert & lookup, no delete, and can
297c478bd9Sstevel@tonic-gate * only be walked in lexical order. if the key already exists
307c478bd9Sstevel@tonic-gate * for something being inserted, the previous entry is simply
317c478bd9Sstevel@tonic-gate * replaced. the left-hand-side (lhs), which is the key, is
327c478bd9Sstevel@tonic-gate * copied into malloc'd memory. the right-hand-side (rhs), which
337c478bd9Sstevel@tonic-gate * is the datum, is not copied (in fact, the lut routines don't
347c478bd9Sstevel@tonic-gate * know the size or type of the datum, just the void * pointer to it).
357c478bd9Sstevel@tonic-gate *
367c478bd9Sstevel@tonic-gate * yea, this module could be much fancier and do much more, but
377c478bd9Sstevel@tonic-gate * the idea was to keep it really simple and just provide what
387c478bd9Sstevel@tonic-gate * was needed by logadm for options processing.
397c478bd9Sstevel@tonic-gate */
407c478bd9Sstevel@tonic-gate
417c478bd9Sstevel@tonic-gate #include <stdio.h>
427c478bd9Sstevel@tonic-gate #include <strings.h>
437c478bd9Sstevel@tonic-gate #include "err.h"
447c478bd9Sstevel@tonic-gate #include "lut.h"
457c478bd9Sstevel@tonic-gate
467c478bd9Sstevel@tonic-gate /* forward declarations of functions private to this module */
477c478bd9Sstevel@tonic-gate static void dooper(const char *lhs, void *rhs, void *arg);
487c478bd9Sstevel@tonic-gate
497c478bd9Sstevel@tonic-gate /* info created by lut_add() and lut_dup(), private to this module */
507c478bd9Sstevel@tonic-gate struct lut {
517c478bd9Sstevel@tonic-gate struct lut *lut_left;
527c478bd9Sstevel@tonic-gate struct lut *lut_right;
537c478bd9Sstevel@tonic-gate char *lut_lhs; /* search key */
547c478bd9Sstevel@tonic-gate void *lut_rhs; /* the datum */
557c478bd9Sstevel@tonic-gate };
567c478bd9Sstevel@tonic-gate
577c478bd9Sstevel@tonic-gate /*
587c478bd9Sstevel@tonic-gate * lut_add -- add an entry to the table
597c478bd9Sstevel@tonic-gate *
607c478bd9Sstevel@tonic-gate * use it like this:
617c478bd9Sstevel@tonic-gate * struct lut *root = NULL;
627c478bd9Sstevel@tonic-gate * root = lut_add(root, "key", value);
637c478bd9Sstevel@tonic-gate *
647c478bd9Sstevel@tonic-gate * the key string gets strdup'd by lut_add(), but the memory holding
657c478bd9Sstevel@tonic-gate * the *value should not be freed until the lut is freed by lut_free().
667c478bd9Sstevel@tonic-gate */
677c478bd9Sstevel@tonic-gate struct lut *
lut_add(struct lut * root,const char * lhs,void * rhs)687c478bd9Sstevel@tonic-gate lut_add(struct lut *root, const char *lhs, void *rhs)
697c478bd9Sstevel@tonic-gate {
70*b493790cSbasabi int diff = 0;
717c478bd9Sstevel@tonic-gate
727c478bd9Sstevel@tonic-gate if (root == NULL) {
737c478bd9Sstevel@tonic-gate /* not in tree, create new node */
747c478bd9Sstevel@tonic-gate root = MALLOC(sizeof (*root));
757c478bd9Sstevel@tonic-gate root->lut_lhs = STRDUP(lhs);
767c478bd9Sstevel@tonic-gate root->lut_rhs = rhs;
777c478bd9Sstevel@tonic-gate root->lut_left = root->lut_right = NULL;
78*b493790cSbasabi } else if (lhs != NULL && (diff = strcmp(root->lut_lhs, lhs)) == 0) {
797c478bd9Sstevel@tonic-gate /* already in tree, replace node */
807c478bd9Sstevel@tonic-gate root->lut_rhs = rhs;
817c478bd9Sstevel@tonic-gate } else if (diff > 0)
827c478bd9Sstevel@tonic-gate root->lut_left = lut_add(root->lut_left, lhs, rhs);
837c478bd9Sstevel@tonic-gate else
847c478bd9Sstevel@tonic-gate root->lut_right = lut_add(root->lut_right, lhs, rhs);
857c478bd9Sstevel@tonic-gate return (root);
867c478bd9Sstevel@tonic-gate }
877c478bd9Sstevel@tonic-gate
887c478bd9Sstevel@tonic-gate /* helper function for lut_dup() */
897c478bd9Sstevel@tonic-gate static void
dooper(const char * lhs,void * rhs,void * arg)907c478bd9Sstevel@tonic-gate dooper(const char *lhs, void *rhs, void *arg)
917c478bd9Sstevel@tonic-gate {
927c478bd9Sstevel@tonic-gate struct lut **rootp = (struct lut **)arg;
937c478bd9Sstevel@tonic-gate
947c478bd9Sstevel@tonic-gate *rootp = lut_add(*rootp, lhs, rhs);
957c478bd9Sstevel@tonic-gate }
967c478bd9Sstevel@tonic-gate
977c478bd9Sstevel@tonic-gate /*
987c478bd9Sstevel@tonic-gate * lut_dup -- duplicate a lookup table
997c478bd9Sstevel@tonic-gate *
1007c478bd9Sstevel@tonic-gate * caller is responsible for keeping track of how many tables are keeping
1017c478bd9Sstevel@tonic-gate * pointers to the void * datum values.
1027c478bd9Sstevel@tonic-gate */
1037c478bd9Sstevel@tonic-gate struct lut *
lut_dup(struct lut * root)1047c478bd9Sstevel@tonic-gate lut_dup(struct lut *root)
1057c478bd9Sstevel@tonic-gate {
1067c478bd9Sstevel@tonic-gate struct lut *ret = NULL;
1077c478bd9Sstevel@tonic-gate
1087c478bd9Sstevel@tonic-gate lut_walk(root, dooper, &ret);
1097c478bd9Sstevel@tonic-gate
1107c478bd9Sstevel@tonic-gate return (ret);
1117c478bd9Sstevel@tonic-gate }
1127c478bd9Sstevel@tonic-gate
1137c478bd9Sstevel@tonic-gate /*
1147c478bd9Sstevel@tonic-gate * lut_lookup -- find an entry
1157c478bd9Sstevel@tonic-gate */
1167c478bd9Sstevel@tonic-gate void *
lut_lookup(struct lut * root,const char * lhs)1177c478bd9Sstevel@tonic-gate lut_lookup(struct lut *root, const char *lhs)
1187c478bd9Sstevel@tonic-gate {
1197c478bd9Sstevel@tonic-gate int diff;
1207c478bd9Sstevel@tonic-gate
121*b493790cSbasabi if (root == NULL || lhs == NULL)
1227c478bd9Sstevel@tonic-gate return (NULL);
1237c478bd9Sstevel@tonic-gate else if ((diff = strcmp(root->lut_lhs, lhs)) == 0)
1247c478bd9Sstevel@tonic-gate return (root->lut_rhs);
1257c478bd9Sstevel@tonic-gate else if (diff > 0)
1267c478bd9Sstevel@tonic-gate return (lut_lookup(root->lut_left, lhs));
1277c478bd9Sstevel@tonic-gate else
1287c478bd9Sstevel@tonic-gate return (lut_lookup(root->lut_right, lhs));
1297c478bd9Sstevel@tonic-gate }
1307c478bd9Sstevel@tonic-gate
1317c478bd9Sstevel@tonic-gate /*
1327c478bd9Sstevel@tonic-gate * lut_walk -- walk the table in lexical order
1337c478bd9Sstevel@tonic-gate */
1347c478bd9Sstevel@tonic-gate void
lut_walk(struct lut * root,void (* callback)(const char * lhs,void * rhs,void * arg),void * arg)1357c478bd9Sstevel@tonic-gate lut_walk(struct lut *root,
1367c478bd9Sstevel@tonic-gate void (*callback)(const char *lhs, void *rhs, void *arg), void *arg)
1377c478bd9Sstevel@tonic-gate {
1387c478bd9Sstevel@tonic-gate if (root) {
1397c478bd9Sstevel@tonic-gate lut_walk(root->lut_left, callback, arg);
1407c478bd9Sstevel@tonic-gate (*callback)(root->lut_lhs, root->lut_rhs, arg);
1417c478bd9Sstevel@tonic-gate lut_walk(root->lut_right, callback, arg);
1427c478bd9Sstevel@tonic-gate }
1437c478bd9Sstevel@tonic-gate }
1447c478bd9Sstevel@tonic-gate
1457c478bd9Sstevel@tonic-gate /*
1467c478bd9Sstevel@tonic-gate * lut_free -- free a lut
1477c478bd9Sstevel@tonic-gate *
1487c478bd9Sstevel@tonic-gate * if callback is provided, it is called for each value in the table.
1497c478bd9Sstevel@tonic-gate * it the values are things that the caller malloc'd, then you can do:
1507c478bd9Sstevel@tonic-gate * lut_free(root, free);
1517c478bd9Sstevel@tonic-gate */
1527c478bd9Sstevel@tonic-gate void
lut_free(struct lut * root,void (* callback)(void * rhs))1537c478bd9Sstevel@tonic-gate lut_free(struct lut *root, void (*callback)(void *rhs))
1547c478bd9Sstevel@tonic-gate {
155*b493790cSbasabi if (root != NULL) {
1567c478bd9Sstevel@tonic-gate lut_free(root->lut_left, callback);
1577c478bd9Sstevel@tonic-gate lut_free(root->lut_right, callback);
1587c478bd9Sstevel@tonic-gate FREE(root->lut_lhs);
1597c478bd9Sstevel@tonic-gate if (callback)
1607c478bd9Sstevel@tonic-gate (*callback)(root->lut_rhs);
1617c478bd9Sstevel@tonic-gate FREE(root);
1627c478bd9Sstevel@tonic-gate }
1637c478bd9Sstevel@tonic-gate }
1647c478bd9Sstevel@tonic-gate
1657c478bd9Sstevel@tonic-gate
1667c478bd9Sstevel@tonic-gate #ifdef TESTMODULE
1677c478bd9Sstevel@tonic-gate
1687c478bd9Sstevel@tonic-gate void
printer(const char * lhs,void * rhs,void * arg)1697c478bd9Sstevel@tonic-gate printer(const char *lhs, void *rhs, void *arg)
1707c478bd9Sstevel@tonic-gate {
1717c478bd9Sstevel@tonic-gate printf("<%s> <%s> (<%s>)\n", lhs, (char *)rhs,
1727c478bd9Sstevel@tonic-gate (char *)lut_lookup(arg, lhs));
1737c478bd9Sstevel@tonic-gate }
1747c478bd9Sstevel@tonic-gate
1757c478bd9Sstevel@tonic-gate /*
1767c478bd9Sstevel@tonic-gate * test main for lut module, usage: a.out [lhs[=rhs]...]
1777c478bd9Sstevel@tonic-gate */
178*b493790cSbasabi int
main(int argc,char * argv[])1797c478bd9Sstevel@tonic-gate main(int argc, char *argv[])
1807c478bd9Sstevel@tonic-gate {
1817c478bd9Sstevel@tonic-gate struct lut *r = NULL;
1827c478bd9Sstevel@tonic-gate struct lut *dupr = NULL;
1837c478bd9Sstevel@tonic-gate char *equals;
1847c478bd9Sstevel@tonic-gate
1857c478bd9Sstevel@tonic-gate err_init(argv[0]);
1867c478bd9Sstevel@tonic-gate setbuf(stdout, NULL);
1877c478bd9Sstevel@tonic-gate
1887c478bd9Sstevel@tonic-gate for (argv++; *argv; argv++)
1897c478bd9Sstevel@tonic-gate if ((equals = strchr(*argv, '=')) != NULL) {
1907c478bd9Sstevel@tonic-gate *equals++ = '\0';
1917c478bd9Sstevel@tonic-gate r = lut_add(r, *argv, equals);
1927c478bd9Sstevel@tonic-gate } else
1937c478bd9Sstevel@tonic-gate r = lut_add(r, *argv, "NULL");
1947c478bd9Sstevel@tonic-gate
1957c478bd9Sstevel@tonic-gate printf("lut contains:\n");
1967c478bd9Sstevel@tonic-gate lut_walk(r, printer, r);
1977c478bd9Sstevel@tonic-gate
1987c478bd9Sstevel@tonic-gate dupr = lut_dup(r);
1997c478bd9Sstevel@tonic-gate
2007c478bd9Sstevel@tonic-gate lut_free(r, NULL);
2017c478bd9Sstevel@tonic-gate
2027c478bd9Sstevel@tonic-gate printf("dup lut contains:\n");
2037c478bd9Sstevel@tonic-gate lut_walk(dupr, printer, dupr);
2047c478bd9Sstevel@tonic-gate
2057c478bd9Sstevel@tonic-gate lut_free(dupr, NULL);
2067c478bd9Sstevel@tonic-gate
2077c478bd9Sstevel@tonic-gate err_done(0);
208*b493790cSbasabi /* NOTREACHED */
209*b493790cSbasabi return (0);
2107c478bd9Sstevel@tonic-gate }
2117c478bd9Sstevel@tonic-gate
2127c478bd9Sstevel@tonic-gate #endif /* TESTMODULE */
213