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