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