blob: fa9e8aa5812cb7841f4d9dba1ad26a09d443df5a [file] [log] [blame]
/*
* Copyright (c) 2000 Silicon Graphics, Inc. All Rights Reserved.
*
* This program is free software; you can redistribute it and/or modify it
* under the terms of version 2 of the GNU General Public License as
* published by the Free Software Foundation.
*
* This program is distributed in the hope that it would be useful, but
* WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
*
* Further, this software is distributed without any warranty that it is
* free of the rightful claim of any third person regarding infringement
* or the like. Any license provided herein, whether implied or
* otherwise, applies only to this software file. Patent licenses, if
* any, provided herein do not apply to combinations of this program with
* other software, or any other product whatsoever.
*
* You should have received a copy of the GNU General Public License along
* with this program; if not, write the Free Software Foundation, Inc., 59
* Temple Place - Suite 330, Boston MA 02111-1307, USA.
*
* Contact information: Silicon Graphics, Inc., 1600 Amphitheatre Pkwy,
* Mountain View, CA 94043, or:
*
* http://www.sgi.com
*
* For further information regarding this notice, see:
*
* http://oss.sgi.com/projects/GenInfo/NoticeExplan/
*
*/
/* $Id: symbol.c,v 1.4 2002/05/28 16:26:16 robbiew Exp $ */
/*
* Generic Symbol Table
*
* This is intended to look a lot like ndbm, except that all information
* is kept in memory, and a multi-key, hierarchical access mode is provided.
* This is largely patterned after the Berkeley "DB" package.
*
* Requirements
*
* - "key" is ASCII (a C string, in fact)
*
* Symbol Table Structure
*
* Two data structures:
* Symbol Table Header
* Symbol Table Node
*
* A symbol table header consists of a magic number, a pointer to
* the first node in the symbol table, and a cursor that is used
* when sequentialy stepping thru the entire list.
*
* Symbol table nodes contain a pointer to a key, a pointer to this
* key's data, and a pointer to the next node in the chain.
* Note that to create a hierarchical symbol table, a node is created
* whose data points to a symbol table header.
*/
#include <stdio.h>
#include <errno.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>
#include "symbol.h"
#include "splitstr.h"
#define SYM_MAGIC 0xbadc0de
/*
* Some functions can report an error message by assigning it to this
* string.
*/
static char *sym_error=NULL;
/*
* Memory Allocators
*
* newsym() allocates a new symbol table header node
* mknode(...) allocates a new symbol table entry
*/
SYM newsym()
{
SYM h;
if((h=(SYM)malloc(sizeof(struct symh))) == NULL) {
sym_error="sym header malloc failed!";
return(NULL);
}
h->magic = SYM_MAGIC;
h->sym = NULL;
h->cursor = NULL;
return(h);
}
static struct sym *
mknode(struct sym *next, char *key, void *data)
{
struct sym *n;
if((n=(struct sym *)malloc(sizeof(struct sym))) == NULL) {
sym_error="sym node malloc failed!";
return(NULL);
}
n->next = next;
n->key = strdup(key);
n->data = data;
if(n->key == NULL) {
sym_error="sym node strdup(key) failed!";
return(NULL);
}
return(n);
}
/*
* Search for a key in a single-level symbol table hierarchy.
*/
static struct sym *
find_key1(struct sym *sym, char *key)
{
while(sym != NULL)
if(strcmp(sym->key, key) == 0)
return(sym);
else
sym=sym->next;
return(NULL);
}
/*
* Create a new key node, add it to the *end* of this list
*/
static int
add_key(SYM sym, char *key, void *data)
{
register struct sym *sn;
if(sym->sym == NULL)
{
sym->sym = mknode(NULL, key, data);
if(sym->sym == NULL)
{
return(-1);
}
}
else
{
for( sn=sym->sym; sn!=NULL && sn->next != NULL; sn=sn->next );
sn->next = mknode(NULL, key, data);
assert(sn->next != NULL);
if(sn->next == NULL)
return(-1);
}
return(0);
}
/*
* Create a new symbol table
*/
SYM sym_open(int flags, int mode, int openinfo)
{
return(newsym());
}
/*
* Add (key, data) to an existing symbol table
*
* If the key does not exist, a new key is added to the end of the list.
* If the key exists and the PUT_REPLACE flag is not supplied, return EEXIST.
* If a symbol table entry in a multi-part key is not a symbol table (i.e.
* element two of a three or more element key), return ENOTDIR.
*
* "data" is not duplicated and must not point to a static area that could
* go away before the element is deleted (such as a local string in a
* function)
*
* "key" is duplicated as needed, and is not modified.
*
* Code:
* chop up key on commas
*
* search until a key element isn't found in the key tree, the key list is
* exhausted, or a key's data element is not a sub-tree
*
* if the key list is exhausted, return a "duplicate entry" error
*
* if the last found key's data element is not a sub-tree, return
* something like "ENOTDIR".
*
* add new keys for sub-trees until key list is exhausted;
* last node gets 'data'.
*
*/
int
sym_put(SYM sym, char *key, void *data, int flags)
{
const char **keys; /* key split into a 2d string array */
char **kk;
char *nkey; /* copy of 'key' -- before split */
SYM csym, ncsym; /* search: current symbol table */
struct sym *nsym = NULL; /* search: found symbol entry */
if(sym == NULL)
return(EINVAL);
nkey = strdup(key);
keys = splitstr(key, ",",NULL);
if(keys == NULL)
return(EINVAL);
for(kk=(char **)keys, csym = sym;
*kk != NULL && (nsym=find_key1(csym->sym, *kk)) != NULL;
csym=nsym->data) {
if(*++kk == NULL)
break;
if(nsym->data == NULL) { /* fatal error */
free(nkey);
splitstr_free(keys);
return(ENOTDIR);
}
if( ((SYM) (nsym->data))->magic != SYM_MAGIC ) {
free(nkey);
splitstr_free(keys);
return(ENOTDIR);
}
}
if(*kk == NULL) { /* found a complete match */
free(nkey);
splitstr_free(keys);
if(flags == PUT_REPLACE) {
nsym->data = data;
return(0);
} else {
return(EEXIST);
}
}
/* csym is a ptr to a list */
for(;*kk != NULL; kk++) {
if(*(kk+1) != NULL) {
add_key(csym, *kk, (void *)(ncsym=newsym()));
csym = ncsym;
} else {
add_key(csym, *kk, data); /* last key */
}
}
free(nkey);
splitstr_free(keys);
return(0);
}
/*
* Retrieve a Symbol's Contents
*
* "key" is not modified.
* If the key cannot be found, NULL is returned
*/
void * sym_get(SYM sym, char *key)
{
char *nkey;
const char **keys; /* key split into a 2d string array */
char **kk;
SYM csym; /* search: current symbol table */
struct sym *nsym = NULL; /* search: found symbol entry */
if(sym == NULL)
return(NULL);
nkey=strdup(key);
keys = splitstr(nkey, ",", NULL);
if(keys == NULL)
return(NULL);
for(kk=(char **)keys, csym = sym;
*kk != NULL && (nsym=find_key1(csym->sym, *kk)) != NULL;
csym=nsym->data) {
if(*++kk == NULL)
break;
if(nsym->data == NULL) { /* fatal error */
free(nkey);
splitstr_free(keys);
return(NULL);
}
if( ((SYM)(nsym->data))->magic != SYM_MAGIC ) {
free(nkey);
splitstr_free(keys);
return(NULL);
}
}
if(*kk == NULL) { /* found a complete match */
splitstr_free(keys);
free(nkey);
return(nsym->data);
} else {
splitstr_free(keys);
free(nkey);
return(NULL);
}
}
/*
* Step thru a symbol table list
*
* The cursor must be set by R_CURSOR, R_FIRST before using R_NEXT.
* NULL is returned when no more items are available.
*/
int
sym_seq(SYM sym, DBT *key, DBT *data, int flags)
{
SYM csym;
switch(flags) {
/*
* A number of ways to do this:
* specificly: sym_seq( .., "key,key") sets to Nth element of the 2nd
* level symbol table
* sym_seq(.., "key,key,") sets to the first element of the 3rd
* level symbol table
*
* sym_seq(.., "key,key") where both must be complete keys, sets
* cursor to the first element of the 3rd level symbol table;
* if there is no 3rd level, return an error.
*/
case R_CURSOR:
csym = (SYM) sym_get(sym, (char *)key->data);
if( csym == NULL || csym->magic != SYM_MAGIC ) {
return(2);
}
sym->cursor = csym->sym;
if(sym->cursor == NULL)
return(1);
key->data = sym->cursor->key;
data->data = sym->cursor->data;
return(0);
case R_FIRST:
sym->cursor = sym->sym;
if(sym->cursor == NULL)
return(1);
key->data = sym->cursor->key;
data->data = sym->cursor->data;
return(0);
case R_NEXT:
if(sym->cursor == NULL)
return(1);
sym->cursor = sym->cursor->next;
if(sym->cursor == NULL)
return(1);
key->data = sym->cursor->key;
data->data = sym->cursor->data;
return(0);
case R_LAST:
case R_PREV:
default:
return(-1);
}
}
/*
* Dump a symbol table's keys.
* Handles hierarchies, using a double quote to indicate depth, one
* double quote for each level.
*/
int
sym_dump(SYM sym, int depth)
{
register struct sym *se; /* symbol entry */
register int d;
if(sym == NULL || sym->magic != SYM_MAGIC)
return -1;
for(se=sym->sym;se != NULL;se=se->next) {
for(d=0;d < depth; d++) {
putchar('"'); putchar(' ');
}
printf("%s\n", se->key);
sym_dump((SYM)se->data, depth+1);
}
return 0;
}
/*
* sym dump, but data is _always_ a string (print it)
*/
int
sym_dump_s(SYM sym, int depth)
{
register struct sym *se; /* symbol entry */
register int d;
if(sym == NULL)
return 0;
if(sym->magic != SYM_MAGIC) {
for(d=0;d < depth; d++) {
putchar('"'); putchar(' ');
}
printf(" = %s\n", (char *)sym);
return 0;
}
for(se=sym->sym;se != NULL;se=se->next) {
for(d=0;d < depth; d++) {
putchar('"'); putchar(' ');
}
printf("%s", se->key);
if(((SYM)se->data)->magic == SYM_MAGIC) {
putchar('\n');
sym_dump_s((SYM)se->data, depth+1);
} else {
printf("(%p) = %s (%p)\n", se->key, (char *)se->data, se->data);
}
}
return 0;
}
/*
* Remove an entire symbol table (done bottom up)
*/
int
sym_rm(SYM sym, int flags)
{
register struct sym *se, *nse; /* symbol entry */
if(sym == NULL)
return 0;
if(sym->magic != SYM_MAGIC) {
if(!(flags&RM_DATA))
free(sym);
return 0;
}
for(se=sym->sym;se != NULL;) {
sym_rm((SYM)se->data, flags);
nse=se->next;
if(flags & RM_KEY)
free(se->key);
if(flags & RM_DATA)
free(se->data);
free(se);
se=nse;
}
if(!(flags&RM_DATA))
free(sym);
return 0;
}