1 /* 2 * Copyright (c) 2000 Silicon Graphics, Inc. All Rights Reserved. 3 * 4 * This program is free software; you can redistribute it and/or modify it 5 * under the terms of version 2 of the GNU General Public License as 6 * published by the Free Software Foundation. 7 * 8 * This program is distributed in the hope that it would be useful, but 9 * WITHOUT ANY WARRANTY; without even the implied warranty of 10 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. 11 * 12 * Further, this software is distributed without any warranty that it is 13 * free of the rightful claim of any third person regarding infringement 14 * or the like. Any license provided herein, whether implied or 15 * otherwise, applies only to this software file. Patent licenses, if 16 * any, provided herein do not apply to combinations of this program with 17 * other software, or any other product whatsoever. 18 * 19 * You should have received a copy of the GNU General Public License along 20 * with this program; if not, write the Free Software Foundation, Inc., 21 * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA. 22 * 23 * Contact information: Silicon Graphics, Inc., 1600 Amphitheatre Pkwy, 24 * Mountain View, CA 94043, or: 25 * 26 * http://www.sgi.com 27 * 28 * For further information regarding this notice, see: 29 * 30 * http://oss.sgi.com/projects/GenInfo/NoticeExplan/ 31 * 32 */ 33 /* $Id: symbol.c,v 1.4 2002/05/28 16:26:16 robbiew Exp $ */ 34 /* 35 * Generic Symbol Table 36 * 37 * This is intended to look a lot like ndbm, except that all information 38 * is kept in memory, and a multi-key, hierarchical access mode is provided. 39 * This is largely patterned after the Berkeley "DB" package. 40 * 41 * Requirements 42 * 43 * - "key" is ASCII (a C string, in fact) 44 * 45 * Symbol Table Structure 46 * 47 * Two data structures: 48 * Symbol Table Header 49 * Symbol Table Node 50 * 51 * A symbol table header consists of a magic number, a pointer to 52 * the first node in the symbol table, and a cursor that is used 53 * when sequentialy stepping thru the entire list. 54 * 55 * Symbol table nodes contain a pointer to a key, a pointer to this 56 * key's data, and a pointer to the next node in the chain. 57 * Note that to create a hierarchical symbol table, a node is created 58 * whose data points to a symbol table header. 59 */ 60 61 #include <stdio.h> 62 #include <errno.h> 63 #include <stdlib.h> 64 #include <string.h> 65 #include <assert.h> 66 #include "symbol.h" 67 #include "splitstr.h" 68 69 #define SYM_MAGIC 0xbadc0de 70 71 /* 72 * Some functions can report an error message by assigning it to this 73 * string. 74 */ 75 76 static char *sym_error = NULL; 77 78 /* 79 * Memory Allocators 80 * 81 * newsym() allocates a new symbol table header node 82 * mknode(...) allocates a new symbol table entry 83 */ 84 85 SYM newsym(void) 86 { 87 SYM h; 88 89 if ((h = malloc(sizeof(struct symh))) == NULL) { 90 sym_error = "sym header malloc failed!"; 91 return (NULL); 92 } 93 94 h->magic = SYM_MAGIC; 95 h->sym = NULL; 96 h->cursor = NULL; 97 return (h); 98 } 99 100 static struct sym *mknode(struct sym *next, char *key, void *data) 101 { 102 struct sym *n; 103 104 if ((n = malloc(sizeof(struct sym))) == NULL) { 105 sym_error = "sym node malloc failed!"; 106 return (NULL); 107 } 108 109 n->next = next; 110 n->key = strdup(key); 111 n->data = data; 112 113 if (n->key == NULL) { 114 sym_error = "sym node strdup(key) failed!"; 115 free(n); 116 return (NULL); 117 } 118 return (n); 119 } 120 121 /* 122 * Search for a key in a single-level symbol table hierarchy. 123 */ 124 static struct sym *find_key1(struct sym *sym, char *key) 125 { 126 while (sym != NULL) 127 if (strcmp(sym->key, key) == 0) 128 return (sym); 129 else 130 sym = sym->next; 131 return (NULL); 132 } 133 134 /* 135 * Create a new key node, add it to the *end* of this list 136 */ 137 static int add_key(SYM sym, char *key, void *data) 138 { 139 register struct sym *sn; 140 141 if (sym->sym == NULL) { 142 sym->sym = mknode(NULL, key, data); 143 if (sym->sym == NULL) { 144 return (-1); 145 } 146 } else { 147 for (sn = sym->sym; sn != NULL && sn->next != NULL; 148 sn = sn->next) ; 149 sn->next = mknode(NULL, key, data); 150 assert(sn->next != NULL); 151 if (sn->next == NULL) 152 return (-1); 153 } 154 return (0); 155 } 156 157 /* 158 * Create a new symbol table 159 */ 160 SYM sym_open(int flags, int mode, int openinfo) 161 { 162 return (newsym()); 163 } 164 165 /* 166 * Add (key, data) to an existing symbol table 167 * 168 * If the key does not exist, a new key is added to the end of the list. 169 * If the key exists and the PUT_REPLACE flag is not supplied, return EEXIST. 170 * If a symbol table entry in a multi-part key is not a symbol table (i.e. 171 * element two of a three or more element key), return ENOTDIR. 172 * 173 * "data" is not duplicated and must not point to a static area that could 174 * go away before the element is deleted (such as a local string in a 175 * function) 176 * 177 * "key" is duplicated as needed, and is not modified. 178 * 179 * Code: 180 * chop up key on commas 181 * 182 * search until a key element isn't found in the key tree, the key list is 183 * exhausted, or a key's data element is not a sub-tree 184 * 185 * if the key list is exhausted, return a "duplicate entry" error 186 * 187 * if the last found key's data element is not a sub-tree, return 188 * something like "ENOTDIR". 189 * 190 * add new keys for sub-trees until key list is exhausted; 191 * last node gets 'data'. 192 * 193 */ 194 int sym_put(SYM sym, char *key, void *data, int flags) 195 { 196 const char **keys; /* key split into a 2d string array */ 197 char **kk; 198 char *nkey; /* copy of 'key' -- before split */ 199 SYM csym, ncsym; /* search: current symbol table */ 200 struct sym *nsym = NULL; /* search: found symbol entry */ 201 202 if (sym == NULL) 203 return (EINVAL); 204 205 nkey = strdup(key); 206 keys = splitstr(key, ",", NULL); 207 208 if (keys == NULL) { 209 free(nkey); 210 return (EINVAL); 211 } 212 213 for (kk = (char **)keys, csym = sym; 214 *kk != NULL && (nsym = find_key1(csym->sym, *kk)) != NULL; 215 csym = nsym->data) { 216 217 if (*++kk == NULL) 218 break; 219 220 if (nsym->data == NULL) { /* fatal error */ 221 free(nkey); 222 splitstr_free(keys); 223 return (ENOTDIR); 224 } 225 if (((SYM) (nsym->data))->magic != SYM_MAGIC) { 226 free(nkey); 227 splitstr_free(keys); 228 return (ENOTDIR); 229 } 230 } 231 232 if (*kk == NULL) { /* found a complete match */ 233 free(nkey); 234 splitstr_free(keys); 235 236 if (flags == PUT_REPLACE) { 237 nsym->data = data; 238 return (0); 239 } else { 240 return (EEXIST); 241 } 242 } 243 244 /* csym is a ptr to a list */ 245 for (; *kk != NULL; kk++) { 246 if (*(kk + 1) != NULL) { 247 add_key(csym, *kk, (void *)(ncsym = newsym())); 248 csym = ncsym; 249 } else { 250 add_key(csym, *kk, data); /* last key */ 251 } 252 } 253 254 free(nkey); 255 splitstr_free(keys); 256 return (0); 257 } 258 259 /* 260 * Retrieve a Symbol's Contents 261 * 262 * "key" is not modified. 263 * If the key cannot be found, NULL is returned 264 */ 265 void *sym_get(SYM sym, char *key) 266 { 267 char *nkey; 268 const char **keys; /* key split into a 2d string array */ 269 char **kk; 270 SYM csym; /* search: current symbol table */ 271 struct sym *nsym = NULL; /* search: found symbol entry */ 272 273 if (sym == NULL) 274 return (NULL); 275 276 nkey = strdup(key); 277 keys = splitstr(nkey, ",", NULL); 278 if (keys == NULL) 279 return (NULL); 280 281 for (kk = (char **)keys, csym = sym; 282 *kk != NULL && (nsym = find_key1(csym->sym, *kk)) != NULL; 283 csym = nsym->data) { 284 285 if (*++kk == NULL) 286 break; 287 288 if (nsym->data == NULL) { /* fatal error */ 289 free(nkey); 290 splitstr_free(keys); 291 return (NULL); 292 } 293 if (((SYM) (nsym->data))->magic != SYM_MAGIC) { 294 free(nkey); 295 splitstr_free(keys); 296 return (NULL); 297 } 298 } 299 300 if (*kk == NULL) { /* found a complete match */ 301 splitstr_free(keys); 302 free(nkey); 303 return (nsym->data); 304 } else { 305 splitstr_free(keys); 306 free(nkey); 307 return (NULL); 308 } 309 } 310 311 /* 312 * Step thru a symbol table list 313 * 314 * The cursor must be set by R_CURSOR, R_FIRST before using R_NEXT. 315 * NULL is returned when no more items are available. 316 */ 317 int sym_seq(SYM sym, DBT * key, DBT * data, int flags) 318 { 319 SYM csym; 320 321 switch (flags) { 322 /* 323 * A number of ways to do this: 324 * specificly: sym_seq( .., "key,key") sets to Nth element of the 2nd 325 * level symbol table 326 * sym_seq(.., "key,key,") sets to the first element of the 3rd 327 * level symbol table 328 * 329 * sym_seq(.., "key,key") where both must be complete keys, sets 330 * cursor to the first element of the 3rd level symbol table; 331 * if there is no 3rd level, return an error. 332 */ 333 case R_CURSOR: 334 csym = (SYM) sym_get(sym, (char *)key->data); 335 if (csym == NULL || csym->magic != SYM_MAGIC) { 336 return (2); 337 } 338 sym->cursor = csym->sym; 339 if (sym->cursor == NULL) 340 return (1); 341 key->data = sym->cursor->key; 342 data->data = sym->cursor->data; 343 344 return (0); 345 346 case R_FIRST: 347 sym->cursor = sym->sym; 348 if (sym->cursor == NULL) 349 return (1); 350 key->data = sym->cursor->key; 351 data->data = sym->cursor->data; 352 353 return (0); 354 355 case R_NEXT: 356 if (sym->cursor == NULL) 357 return (1); 358 sym->cursor = sym->cursor->next; 359 360 if (sym->cursor == NULL) 361 return (1); 362 363 key->data = sym->cursor->key; 364 data->data = sym->cursor->data; 365 366 return (0); 367 368 case R_LAST: 369 case R_PREV: 370 default: 371 return (-1); 372 } 373 } 374 375 /* 376 * Dump a symbol table's keys. 377 * Handles hierarchies, using a double quote to indicate depth, one 378 * double quote for each level. 379 */ 380 int sym_dump(SYM sym, int depth) 381 { 382 383 register struct sym *se; /* symbol entry */ 384 register int d; 385 386 if (sym == NULL || sym->magic != SYM_MAGIC) 387 return -1; 388 389 for (se = sym->sym; se != NULL; se = se->next) { 390 for (d = 0; d < depth; d++) { 391 putchar('"'); 392 putchar(' '); 393 } 394 printf("%s\n", se->key); 395 sym_dump((SYM) se->data, depth + 1); 396 } 397 return 0; 398 } 399 400 /* 401 * sym dump, but data is _always_ a string (print it) 402 */ 403 int sym_dump_s(SYM sym, int depth) 404 { 405 406 register struct sym *se; /* symbol entry */ 407 register int d; 408 409 if (sym == NULL) 410 return 0; 411 412 if (sym->magic != SYM_MAGIC) { 413 for (d = 0; d < depth; d++) { 414 putchar('"'); 415 putchar(' '); 416 } 417 printf(" = %s\n", (char *)sym); 418 return 0; 419 } 420 421 for (se = sym->sym; se != NULL; se = se->next) { 422 for (d = 0; d < depth; d++) { 423 putchar('"'); 424 putchar(' '); 425 } 426 printf("%s", se->key); 427 if (((SYM) se->data)->magic == SYM_MAGIC) { 428 putchar('\n'); 429 sym_dump_s((SYM) se->data, depth + 1); 430 } else { 431 printf("(%p) = %s (%p)\n", se->key, (char *)se->data, 432 se->data); 433 } 434 } 435 return 0; 436 } 437 438 /* 439 * Remove an entire symbol table (done bottom up) 440 */ 441 int sym_rm(SYM sym, int flags) 442 { 443 register struct sym *se, *nse; /* symbol entry */ 444 445 if (sym == NULL) 446 return 0; 447 448 if (sym->magic != SYM_MAGIC) { 449 if (!(flags & RM_DATA)) 450 free(sym); 451 return 0; 452 } 453 454 for (se = sym->sym; se != NULL;) { 455 sym_rm((SYM) se->data, flags); 456 nse = se->next; 457 if (flags & RM_KEY) 458 free(se->key); 459 if (flags & RM_DATA) 460 free(se->data); 461 free(se); 462 se = nse; 463 } 464 if (!(flags & RM_DATA)) 465 free(sym); 466 return 0; 467 } 468
