/* Class 'Dict' -- General Symbol Table Functions
 * To manage <key, value> pairs.
 *
 * <key> is a C string.  <value> is a pointer to an arbitrary object.
 */

/* TODO
 *
 * [X]	expansion and re-hash when full
 *
 * [X]	provide hooks for hash, compare functions
 *
 * [X]	provide sequencing over all elements.
 */

#include <stdio.h>
#include <string.h>
#include <strings.h>
extern char*	strdup();
extern int	strcasecmp();

#define _CLASS_Dict_PRIVATE_
#include "dict.h"		/* import public declarations */

/* Symtab:
 *
 * Private declarations
 */

/* Type shorthands */
typedef dict_key_t	Key_t ;
typedef dict_value_t	Value_t;
typedef dict_hash_t	Hash_t;


/* SymEnt is a private structure used only by internal functions */
typedef struct _SymEnt_* SymEnt;
struct	_SymEnt_ {
	Key_t	name;
	Value_t	value;
	Hash_t	hash;
	SymEnt	next;
};

/* Private Dict functions */
#if defined (__STDC__)

	static Dict dict_expand (Dict self);
	static SymEnt*	dict_locationOf (
				Dict	self,
				SymEnt	assoc,
				int	mayAdd
			);
	static SymEnt syment_new (void);
	static SymEnt syment_dispose (SymEnt sep);
	static Hash_t	symhash (Key_t key);
	static Hash_t	symcasehash (Key_t key);

#else

	static Dict dict_expand ();
	static SymEnt*	dict_locationOf ();
	static SymEnt syment_new ();
	static SymEnt syment_dispose ();
	static Hash_t	symhash ();
	static Hash_t	symcasehash ();

#endif

#define DFLTHASH	127		/* initial hash array size */


/* Manage private pool of SymEnt structures
 */
static SymEnt _freehd;			/* free list head */
#define DFLTSYMENT	64		/* # SymEnt struct to grab in a hunk */

#define GETSEP(SEP)	(_freehd ? \
			 (((SEP) = _freehd), _freehd = _freehd->next, (SEP)) \
			 : ((SEP) = syment_new()))
#define PUTSEP(SEP)	((SEP)->next = _freehd, _freehd = (SEP))
#define CLRSEP(SEP)	((SEP)->name=0,(SEP)->value=0,(SEP)->hash=0)


/* Even though declared above for clarity, this is a macro
 */
#define syment_dispose(SEP)	(free((SEP)->name),CLRSEP(SEP),PUTSEP(SEP),0)



/* Instance Creation, Deletion:
 *
 *	new(), dispose()
 */

/* Create a new symbol table and initialize it for business
 */
Dict
dict_new()
{
	Dict s;

	s = (Dict)calloc (1, sizeof *s);
	s->f_hash = symcasehash;
	s->f_compare = strcasecmp;
	s->nhead = DFLTHASH;
	s->head = (SymEnt*)calloc (s->nhead, sizeof(SymEnt));
	return s;
}

/* Dispose of a dictionary, freeing all the memory allocated
 * to it.
 *
 * N.B.: this does not free memory allocated to the values in
 * the table.
 */
Dict
dict_dispose (self)
Dict	self;
{
	register SymEnt* psep, sep, nsep;
	register int i;

	if (self == 0)
		return 0;

	psep = &self->head[0];
	for (i = self->nhead; i > 0; i--, psep++) {
		for (sep = *psep; sep; sep = nsep) {
			nsep = sep->next;
			syment_dispose (sep);
		}
		*psep = 0;
	}
	free (self->head);
	free (self);
	return 0;
}

int
dict_size (self)
Dict	self;
{
	return self->nitems;
}


/* Accessing:
 *
 *	add(), remove(), find(), replace(), keys(), values()
 */

/*
 * Add element <v> to dictionary with key <n>.
 *
 * Return current value stored at this key if one exists,
 * otherwise, add new <key,value> association.
 *
 */
Value_t
dict_add (self, n, v)
Dict	self;
Key_t	n;
Value_t	v;
{
	SymEnt* psep, sep;
	struct _SymEnt_ tmp;
	Hash_t hsh;

	tmp.name = n;
	psep = dict_locationOf (self, &tmp, 1);
	if (psep == 0)
		return 0;

	else if (tmp.value != 0)
		return tmp.value;


	GETSEP(sep);
	sep->hash = tmp.hash;
	sep->name = strdup (n);
	sep->value = v;

	/* link it in at the front
	 * If this is the first element on this chain, increment
	 * the count of heads in use.
	 */
	if ((sep->next = *psep) == 0)
		self->nheadinuse++;
	*psep = sep;
	self->nitems++;

	return 0;
}

/*
 * Remove element with key <n> from symbol table <self>
 *
 * Return value associated with that key (if any).
 *
 */
Value_t
dict_remove (self, n)
Dict	self;
Key_t	n;
{
	register SymEnt* psep, sep;
	struct _SymEnt_ tmp;
	Value_t v = 0;

	tmp.name = n;
	psep = dict_locationOf (self, &tmp, 0);
	if (psep == 0 || (sep = *psep) == 0 || tmp.value == 0)
		return 0;

	self->nitems--;
	*psep = sep->next;
	if (psep >= self->head && psep < &self->head[self->nhead])
		self->nheadinuse--;
	syment_dispose(sep);
	return tmp.value;
}

/*
 * Find element matching key <n> in symbol table <self>
 */
Value_t
dict_find (self, n)
Dict	self;
Key_t	n;
{
	register SymEnt* psep;
	struct _SymEnt_ tmp;

	tmp.name = n;
	psep = dict_locationOf (self, &tmp, 0);

	return psep ? tmp.value : 0;
}

/*
 * Returns the actual key of the entry matching argument key.
 * Useful sometimes (with care) when you want to use the value
 * in dynamically allocated key storage without duplicating
 * the string.
 *
 * Any modification of the return value is disasterous.
 */

Key_t
dict_findKey (self, key)
Dict	self;
Key_t	key;
{
	register SymEnt* psep;
	struct _SymEnt_ tmp;

	tmp.name = key;
	psep = dict_locationOf (self, &tmp, 0);

	return psep ? tmp.name : 0;
}

/* Like add above, but replace any existing value
 */
Value_t
dict_replace (self, n, v)
Dict	self;
Key_t	n;
Value_t	v;
{
	SymEnt* psep, sep;
	struct _SymEnt_ tmp;
	Hash_t hsh;
	Value_t oldValue;


	tmp.name = n;
	psep = dict_locationOf (self, &tmp, 1);
	if (psep == 0)
		return 0;

	/* If key matches existing entry, just replace the old
	 * value with the new one and return it.
	 */
	else if ((oldValue = tmp.value) != 0) {
		(*psep)->value = v;
		return oldValue;
	}


	/* Otherwise, we have to add the association
	 */
	GETSEP(sep);
	*sep = tmp;
	sep->name = strdup (sep->name);
	sep->value = v;

	/* link it in at the front
	 * If this is the first element on this chain, increment
	 * the count of heads in use.
	 */
	if ((sep->next = *psep) == 0)
		self->nheadinuse++;
	*psep = sep;
	self->nitems++;

	return 0;
}

/* Return list of keys in this Dict
 */
Key_t*
dict_keys (self)
Dict	self;
{
	Key_t* retvec;
	register int i, j;
	register SymEnt* psep, sep;

	retvec = (Key_t*)calloc (self->nitems+1, sizeof (Key_t));
	if (retvec == 0) {
		self->error = "Allocation failure";
		return 0;
	}
	j = 0;

	for (i = self->nhead, psep = self->head; i > 0; i--, psep++) {
		for (sep = *psep; sep != 0; sep = sep->next) {
			retvec[j++] = sep->name;
		}
	}
	return retvec;
}

/* Return list of values in this Dict
 */
Value_t*
dict_values (self)
Dict	self;
{
	Value_t* retvec;
	register int i, j;
	register SymEnt* psep, sep;

	retvec = (Value_t*)calloc (self->nitems+1, sizeof (Value_t));
	if (retvec == 0) {
		self->error = "Allocation failure";
		return 0;
	}
	j = 0;

	for (i = self->nhead, psep = self->head; i > 0; i--, psep++) {
		for (sep = *psep; sep != 0; sep = sep->next) {
			retvec[j++] = sep->value;
		}
	}
	return retvec;
}

/* Miscellaneous:
 *
 *	ignoreCase(), printOn()
 */

/* Set up to either respect or ignore case distinctions
 * in keys.
 */
int
dict_ignoreCase (self, yesno)
Dict	self;
int	yesno;
{
	/* Can't do this if there's stuff already in the Dict
	 */
	if (self->nitems > 0) {
		self->error = "Dictionary not empty";
		return -1;
	}

	/* Ignore case on key comparisons */
	if (yesno) {
		self->f_hash = symcasehash;
		self->f_compare = strcasecmp;
	}
	else {
		self->f_hash = symhash;
		self->f_compare = strcmp;
	}
	return 0;
}

dict_printOn (self, file)
Dict	self;
FILE*	file;
{
	fprintf (file, "Dict(0x%x): nhead=%d; nheadinuse=%d\n",
		 self, self->nhead, self->nheadinuse);
	fprintf (file, "  nitems=%d; avgChain = %.2f\n", self->nitems,
		self->nheadinuse ? (double)self->nitems/self->nheadinuse : (double )0);
}

/* Private Functions:
 *
 *	expand(), symhash(), symcasehash(), locationOf()
 */

/* Expand dictionary by 50% or DFLTHASH, whichever is smaller
 *
 * This may invert the order in a list of two keys which hash to 
 * the same location.
 */
static Dict
dict_expand (self)
Dict self;
{
	SymEnt* oldhead, p, n;
	SymEnt* psep;
	register int i;
	int oldnhead;
	int newnhead = self->nhead/2;

	if (newnhead > DFLTHASH)
		newnhead = DFLTHASH;
	newnhead += self->nhead;

	/* Save current parameters */
	oldhead = self->head;
	oldnhead = self->nhead;

	/* allocate larger list array */
	self->nhead = newnhead;
	self->head = (SymEnt*)calloc (newnhead, sizeof (SymEnt));
	self->nheadinuse = 0;

	/* move current contents to new list */
	for (i = 0; i < oldnhead; i++) {
		for (p = oldhead[i]; p; p = n) {
			n = p->next;
			psep = &self->head[p->hash % self->nhead];
			if ((p->next = *psep) == 0)
				self->nheadinuse++;
			*psep = p;
		}
	}

	/* free the old list head */
	free (oldhead);
	return self;
}

/* Compute a simple hash function on a string
 * This one is case-sensitive.
 */
static Hash_t
symhash (ptr)
Key_t	ptr;
{
	Hash_t ret = 0;
	register unsigned char* nhp = (unsigned char*)ptr;

	while (*nhp) {
		ret = (ret << 1) + *nhp++;
		if (ret & 0x8000) {
			ret &= 0x7fff;
			ret++;
		}
	}
	return ret;
}

/* As above, but case-insensitive
 */
#include <ctype.h>
static Hash_t
symcasehash (ptr)
Key_t	ptr;
{
	Hash_t ret = 0;
	register unsigned char* nhp = (unsigned char*)ptr;
	register cv;

	while (*nhp) {
		cv = *nhp++;
		if (isupper(cv))
			cv = tolower(cv);
		ret = (ret << 1) + cv;
		if (ret & 0x8000) {
			ret &= 0x7fff;
			ret++;
		}
	}
	return ret;
}

/* Return the location of the Assoc identified by <key>
 * This is can be used to return an existing entry, replace
 * an existing entry, or add a new entry.
 *
 * This is the common function supporting find, add, replace,
 * and delete operations.
 */
static SymEnt*
dict_locationOf (self, assoc, mayAdd)
Dict	self;
SymEnt	assoc;
int	mayAdd;
{
	register Hash_t hsh;
	register SymEnt* psep, *newsep, sep;

	if (self == 0 || assoc == 0 || assoc->name == 0) {
		if (self)
			self->error = "NIL argument(s)";
		return 0;
	}

	/* See if table should be expanded */
	if (mayAdd && self->nheadinuse
	    && ((self->nitems / self->nheadinuse) >= 4
	    || self->nheadinuse >= ((self->nhead*4)/5)))
		self = dict_expand (self);

	hsh = self->f_hash(assoc->name);
	assoc->hash = hsh;
	assoc->value = 0;

	newsep = &self->head[hsh % self->nhead];

	for ( psep = newsep; (sep = *psep) != 0; psep = &sep->next) {
		if (sep->hash == hsh
		    && (assoc->value == sep->value
			|| self->f_compare(sep->name, assoc->name) == 0)) {
			assoc->name = sep->name;
			assoc->value = sep->value;
			return psep;
		}
	}
	self->error = "element not found";
	return newsep;
}


/* Get another glob of SymEnts and stick them on a local free list
 */
static SymEnt
syment_new()
{
	register SymEnt sep;
	register n;

	sep = (SymEnt) calloc (DFLTSYMENT, sizeof (*sep));
	for (n = 0; n < DFLTSYMENT; n++, sep++)
		PUTSEP(sep);

	GETSEP(sep);
	return sep;
}

#ifdef TEST

struct DATA {
	char* name; int value;
} init_data[] ={
	"red",		0x01,
	"white",	0x02,
	"bleu",		0x03,
	"orange",	0x04,
	"lavender",	0x14,
	"purple",	0x24,
	"fuscia",	0x34,
	"aqua",		0x44,
	"brown",	0x54,
	"green",	0x64,
	"turquoise",	0x74,
	"yellow",	0x84,
	"beige",	0x94,
	"pink",		0xa4,
	"black",	0xb4,
	"cyan",		0xc4,
	"magenta",	0xd4,
	"ruby",		0xe4,
	"carnelian",	0xf4,
	"plum",		0x15,
	"saffron",	0x25,
	"wheat",	0x35,
	{ 0, 0 }
};

main(argc, argv)
int	argc;
char**	argv;
{
	Dict s;
	int i;
	void* v;

	s = dict_new();

	/* Test insertion */
	for (i = 0; init_data[i].name; i++) {
		v = dict_add (s, init_data[i].name,
			(void*)init_data[i].value);
		printf ("Adding <'%s',%x> yields %x\n",
			init_data[i].name, init_data[i].value, v);
	}
	dict_printOn(s, stdout);

	/* Test retrieval */
	for (i = 0; init_data[i].name; i++) {
		v = dict_find (s, init_data[i].name);
		printf ("finding <'%s'> yields %x\n",
			init_data[i].name, v);
	}


	/* Test keys, values, array */
	{
		dict_key_t* retval;
		register i;

		retval = dict_keys (s);
		printf ("keys of 0x%x:\n", s);
		for (i = 0; retval[i] != 0; i++)
			printf (" >> %s\n", retval[i]);
		free (retval);
	}
	{
		dict_value_t* retval;
		register i;

		retval = dict_values (s);
		printf ("values of 0x%x:\n", s);
		for (i = 0; retval[i] != 0; i++)
			printf (" >> 0x%08x\n", retval[i]);
		free (retval);
	}

	/* Test deletion */
	for (i = 0; init_data[i].name; i++) {
		v = dict_remove (s, init_data[i].name);
		printf ("deleting <'%s'> yields %x\n",
			init_data[i].name, v);
	}
	dict_printOn(s, stdout);

	/* Test replacement */
	for (i = 0; init_data[i].name; i++) {
		static char* one = "one";
		static char* two = "two";

		v = dict_replace (s, init_data[i].name, one);
		if (v != 0) {
			printf ("initial replacement of '%s' non-zero!\n",
				init_data[i].name);
		}

		v = dict_replace (s, init_data[i].name, two);
		if (v != one) {
			printf ("2nd replacement of '%s' returns wrong value\n",
				init_data[i].name);
		}
	}
	printf ("After replace operations:\n");
	dict_printOn(s, stdout);
	s = dict_dispose(s);
}
#endif