10Sstevel@tonic-gate /*
20Sstevel@tonic-gate * CDDL HEADER START
30Sstevel@tonic-gate *
40Sstevel@tonic-gate * The contents of this file are subject to the terms of the
5*2397Sbasabi * Common Development and Distribution License (the "License").
6*2397Sbasabi * You may not use this file except in compliance with the License.
70Sstevel@tonic-gate *
80Sstevel@tonic-gate * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE
90Sstevel@tonic-gate * or http://www.opensolaris.org/os/licensing.
100Sstevel@tonic-gate * See the License for the specific language governing permissions
110Sstevel@tonic-gate * and limitations under the License.
120Sstevel@tonic-gate *
130Sstevel@tonic-gate * When distributing Covered Code, include this CDDL HEADER in each
140Sstevel@tonic-gate * file and include the License file at usr/src/OPENSOLARIS.LICENSE.
150Sstevel@tonic-gate * If applicable, add the following below this CDDL HEADER, with the
160Sstevel@tonic-gate * fields enclosed by brackets "[]" replaced with your own identifying
170Sstevel@tonic-gate * information: Portions Copyright [yyyy] [name of copyright owner]
180Sstevel@tonic-gate *
190Sstevel@tonic-gate * CDDL HEADER END
200Sstevel@tonic-gate */
210Sstevel@tonic-gate /*
22*2397Sbasabi * Copyright 2006 Sun Microsystems, Inc. All rights reserved.
23*2397Sbasabi * Use is subject to license terms.
240Sstevel@tonic-gate *
250Sstevel@tonic-gate * logadm/lut.c -- simple lookup table module
260Sstevel@tonic-gate *
270Sstevel@tonic-gate * this file contains a very simple lookup table (lut) implementation.
280Sstevel@tonic-gate * the tables only support insert & lookup, no delete, and can
290Sstevel@tonic-gate * only be walked in lexical order. if the key already exists
300Sstevel@tonic-gate * for something being inserted, the previous entry is simply
310Sstevel@tonic-gate * replaced. the left-hand-side (lhs), which is the key, is
320Sstevel@tonic-gate * copied into malloc'd memory. the right-hand-side (rhs), which
330Sstevel@tonic-gate * is the datum, is not copied (in fact, the lut routines don't
340Sstevel@tonic-gate * know the size or type of the datum, just the void * pointer to it).
350Sstevel@tonic-gate *
360Sstevel@tonic-gate * yea, this module could be much fancier and do much more, but
370Sstevel@tonic-gate * the idea was to keep it really simple and just provide what
380Sstevel@tonic-gate * was needed by logadm for options processing.
390Sstevel@tonic-gate */
400Sstevel@tonic-gate
410Sstevel@tonic-gate #pragma ident "%Z%%M% %I% %E% SMI"
420Sstevel@tonic-gate
430Sstevel@tonic-gate #include <stdio.h>
440Sstevel@tonic-gate #include <strings.h>
450Sstevel@tonic-gate #include "err.h"
460Sstevel@tonic-gate #include "lut.h"
470Sstevel@tonic-gate
480Sstevel@tonic-gate /* forward declarations of functions private to this module */
490Sstevel@tonic-gate static void dooper(const char *lhs, void *rhs, void *arg);
500Sstevel@tonic-gate
510Sstevel@tonic-gate /* info created by lut_add() and lut_dup(), private to this module */
520Sstevel@tonic-gate struct lut {
530Sstevel@tonic-gate struct lut *lut_left;
540Sstevel@tonic-gate struct lut *lut_right;
550Sstevel@tonic-gate char *lut_lhs; /* search key */
560Sstevel@tonic-gate void *lut_rhs; /* the datum */
570Sstevel@tonic-gate };
580Sstevel@tonic-gate
590Sstevel@tonic-gate /*
600Sstevel@tonic-gate * lut_add -- add an entry to the table
610Sstevel@tonic-gate *
620Sstevel@tonic-gate * use it like this:
630Sstevel@tonic-gate * struct lut *root = NULL;
640Sstevel@tonic-gate * root = lut_add(root, "key", value);
650Sstevel@tonic-gate *
660Sstevel@tonic-gate * the key string gets strdup'd by lut_add(), but the memory holding
670Sstevel@tonic-gate * the *value should not be freed until the lut is freed by lut_free().
680Sstevel@tonic-gate */
690Sstevel@tonic-gate struct lut *
lut_add(struct lut * root,const char * lhs,void * rhs)700Sstevel@tonic-gate lut_add(struct lut *root, const char *lhs, void *rhs)
710Sstevel@tonic-gate {
72*2397Sbasabi int diff = 0;
730Sstevel@tonic-gate
740Sstevel@tonic-gate if (root == NULL) {
750Sstevel@tonic-gate /* not in tree, create new node */
760Sstevel@tonic-gate root = MALLOC(sizeof (*root));
770Sstevel@tonic-gate root->lut_lhs = STRDUP(lhs);
780Sstevel@tonic-gate root->lut_rhs = rhs;
790Sstevel@tonic-gate root->lut_left = root->lut_right = NULL;
80*2397Sbasabi } else if (lhs != NULL && (diff = strcmp(root->lut_lhs, lhs)) == 0) {
810Sstevel@tonic-gate /* already in tree, replace node */
820Sstevel@tonic-gate root->lut_rhs = rhs;
830Sstevel@tonic-gate } else if (diff > 0)
840Sstevel@tonic-gate root->lut_left = lut_add(root->lut_left, lhs, rhs);
850Sstevel@tonic-gate else
860Sstevel@tonic-gate root->lut_right = lut_add(root->lut_right, lhs, rhs);
870Sstevel@tonic-gate return (root);
880Sstevel@tonic-gate }
890Sstevel@tonic-gate
900Sstevel@tonic-gate /* helper function for lut_dup() */
910Sstevel@tonic-gate static void
dooper(const char * lhs,void * rhs,void * arg)920Sstevel@tonic-gate dooper(const char *lhs, void *rhs, void *arg)
930Sstevel@tonic-gate {
940Sstevel@tonic-gate struct lut **rootp = (struct lut **)arg;
950Sstevel@tonic-gate
960Sstevel@tonic-gate *rootp = lut_add(*rootp, lhs, rhs);
970Sstevel@tonic-gate }
980Sstevel@tonic-gate
990Sstevel@tonic-gate /*
1000Sstevel@tonic-gate * lut_dup -- duplicate a lookup table
1010Sstevel@tonic-gate *
1020Sstevel@tonic-gate * caller is responsible for keeping track of how many tables are keeping
1030Sstevel@tonic-gate * pointers to the void * datum values.
1040Sstevel@tonic-gate */
1050Sstevel@tonic-gate struct lut *
lut_dup(struct lut * root)1060Sstevel@tonic-gate lut_dup(struct lut *root)
1070Sstevel@tonic-gate {
1080Sstevel@tonic-gate struct lut *ret = NULL;
1090Sstevel@tonic-gate
1100Sstevel@tonic-gate lut_walk(root, dooper, &ret);
1110Sstevel@tonic-gate
1120Sstevel@tonic-gate return (ret);
1130Sstevel@tonic-gate }
1140Sstevel@tonic-gate
1150Sstevel@tonic-gate /*
1160Sstevel@tonic-gate * lut_lookup -- find an entry
1170Sstevel@tonic-gate */
1180Sstevel@tonic-gate void *
lut_lookup(struct lut * root,const char * lhs)1190Sstevel@tonic-gate lut_lookup(struct lut *root, const char *lhs)
1200Sstevel@tonic-gate {
1210Sstevel@tonic-gate int diff;
1220Sstevel@tonic-gate
123*2397Sbasabi if (root == NULL || lhs == NULL)
1240Sstevel@tonic-gate return (NULL);
1250Sstevel@tonic-gate else if ((diff = strcmp(root->lut_lhs, lhs)) == 0)
1260Sstevel@tonic-gate return (root->lut_rhs);
1270Sstevel@tonic-gate else if (diff > 0)
1280Sstevel@tonic-gate return (lut_lookup(root->lut_left, lhs));
1290Sstevel@tonic-gate else
1300Sstevel@tonic-gate return (lut_lookup(root->lut_right, lhs));
1310Sstevel@tonic-gate }
1320Sstevel@tonic-gate
1330Sstevel@tonic-gate /*
1340Sstevel@tonic-gate * lut_walk -- walk the table in lexical order
1350Sstevel@tonic-gate */
1360Sstevel@tonic-gate void
lut_walk(struct lut * root,void (* callback)(const char * lhs,void * rhs,void * arg),void * arg)1370Sstevel@tonic-gate lut_walk(struct lut *root,
1380Sstevel@tonic-gate void (*callback)(const char *lhs, void *rhs, void *arg), void *arg)
1390Sstevel@tonic-gate {
1400Sstevel@tonic-gate if (root) {
1410Sstevel@tonic-gate lut_walk(root->lut_left, callback, arg);
1420Sstevel@tonic-gate (*callback)(root->lut_lhs, root->lut_rhs, arg);
1430Sstevel@tonic-gate lut_walk(root->lut_right, callback, arg);
1440Sstevel@tonic-gate }
1450Sstevel@tonic-gate }
1460Sstevel@tonic-gate
1470Sstevel@tonic-gate /*
1480Sstevel@tonic-gate * lut_free -- free a lut
1490Sstevel@tonic-gate *
1500Sstevel@tonic-gate * if callback is provided, it is called for each value in the table.
1510Sstevel@tonic-gate * it the values are things that the caller malloc'd, then you can do:
1520Sstevel@tonic-gate * lut_free(root, free);
1530Sstevel@tonic-gate */
1540Sstevel@tonic-gate void
lut_free(struct lut * root,void (* callback)(void * rhs))1550Sstevel@tonic-gate lut_free(struct lut *root, void (*callback)(void *rhs))
1560Sstevel@tonic-gate {
157*2397Sbasabi if (root != NULL) {
1580Sstevel@tonic-gate lut_free(root->lut_left, callback);
1590Sstevel@tonic-gate lut_free(root->lut_right, callback);
1600Sstevel@tonic-gate FREE(root->lut_lhs);
1610Sstevel@tonic-gate if (callback)
1620Sstevel@tonic-gate (*callback)(root->lut_rhs);
1630Sstevel@tonic-gate FREE(root);
1640Sstevel@tonic-gate }
1650Sstevel@tonic-gate }
1660Sstevel@tonic-gate
1670Sstevel@tonic-gate
1680Sstevel@tonic-gate #ifdef TESTMODULE
1690Sstevel@tonic-gate
1700Sstevel@tonic-gate void
printer(const char * lhs,void * rhs,void * arg)1710Sstevel@tonic-gate printer(const char *lhs, void *rhs, void *arg)
1720Sstevel@tonic-gate {
1730Sstevel@tonic-gate struct lut *root = (struct lut *)arg;
1740Sstevel@tonic-gate
1750Sstevel@tonic-gate printf("<%s> <%s> (<%s>)\n", lhs, (char *)rhs,
1760Sstevel@tonic-gate (char *)lut_lookup(arg, lhs));
1770Sstevel@tonic-gate }
1780Sstevel@tonic-gate
1790Sstevel@tonic-gate /*
1800Sstevel@tonic-gate * test main for lut module, usage: a.out [lhs[=rhs]...]
1810Sstevel@tonic-gate */
182*2397Sbasabi int
main(int argc,char * argv[])1830Sstevel@tonic-gate main(int argc, char *argv[])
1840Sstevel@tonic-gate {
1850Sstevel@tonic-gate struct lut *r = NULL;
1860Sstevel@tonic-gate struct lut *dupr = NULL;
1870Sstevel@tonic-gate char *equals;
1880Sstevel@tonic-gate
1890Sstevel@tonic-gate err_init(argv[0]);
1900Sstevel@tonic-gate setbuf(stdout, NULL);
1910Sstevel@tonic-gate
1920Sstevel@tonic-gate for (argv++; *argv; argv++)
1930Sstevel@tonic-gate if ((equals = strchr(*argv, '=')) != NULL) {
1940Sstevel@tonic-gate *equals++ = '\0';
1950Sstevel@tonic-gate r = lut_add(r, *argv, equals);
1960Sstevel@tonic-gate } else
1970Sstevel@tonic-gate r = lut_add(r, *argv, "NULL");
1980Sstevel@tonic-gate
1990Sstevel@tonic-gate printf("lut contains:\n");
2000Sstevel@tonic-gate lut_walk(r, printer, r);
2010Sstevel@tonic-gate
2020Sstevel@tonic-gate dupr = lut_dup(r);
2030Sstevel@tonic-gate
2040Sstevel@tonic-gate lut_free(r, NULL);
2050Sstevel@tonic-gate
2060Sstevel@tonic-gate printf("dup lut contains:\n");
2070Sstevel@tonic-gate lut_walk(dupr, printer, dupr);
2080Sstevel@tonic-gate
2090Sstevel@tonic-gate lut_free(dupr, NULL);
2100Sstevel@tonic-gate
2110Sstevel@tonic-gate err_done(0);
212*2397Sbasabi /* NOTREACHED */
213*2397Sbasabi return (0);
2140Sstevel@tonic-gate }
2150Sstevel@tonic-gate
2160Sstevel@tonic-gate #endif /* TESTMODULE */
217