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.,
 * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 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;
}