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