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