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
newsym(void)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
mknode(struct sym * next,char * key,void * data)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 */
find_key1(struct sym * sym,char * key)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 */
add_key(SYM sym,char * key,void * data)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 */
sym_open(int flags,int mode,int openinfo)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 */
sym_put(SYM sym,char * key,void * data,int flags)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 */
sym_get(SYM sym,char * key)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 */
sym_seq(SYM sym,DBT * key,DBT * data,int flags)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 */
sym_dump(SYM sym,int depth)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 */
sym_dump_s(SYM sym,int depth)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 */
sym_rm(SYM sym,int flags)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