pan/symbol.c

/*
 * 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.2 2001/02/28 17:42:00 nstraz 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;
    char *strdup();

    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, *strdup();	/* copy of 'key' -- before split */
    SYM csym, ncsym;		/* search: current symbol table */
    struct sym *nsym;		/* 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, *strdup();
    const char **keys;		/* key split into a 2d string array */
    char **kk;
    SYM csym;			/* search: current symbol table */
    struct sym *nsym;		/* 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("(%#x) = %s (%#x)\n", (unsigned int)se->key, (char *)se->data, (unsigned int)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;
}