/*
 *				t a b l e s . c
 */

/*)LIBRARY
*/

#ifdef	DOCUMENTATION

title	tables	Hash Table Handler Functions
index		Hash table handler functions
index		Create a new table
index		Delete a table element
index		Insert a new element into a table
index		Look a key up in a table
index		Scan through a table
index		Update a table element

synopsis

	 typedef char TABLE;

	 TABLE *
	 table(size)
	 int size;

	 tdelete(t,key)
	 TABLE *t;
	 char *key;

	 tinsert(t,key,value)
	 TABLE *t;
	 char *key;
	 int value;

	 tlookup(t,key)
	 TABLE *t;
	 char *key;

	 tnext(t,n,key,value)
	 TABLE *t;
	 int n;
	 char **key;
	 int *value;

	 tupdate(t,key,value)
	 TABLE *t;
	 char *key;
	 int value;

internal

	The actual datatypes used are:

		typedef struct
		{	char *key;
			int value;
		} PAIR;

		typedef struct
		{	int tsize;
			PAIR tdata[];
		} TABLE;

		PAIR *
		$$locate(t,key)
		TABLE *t;
		char *key;

description

	Tables are associative memory.  They consist of keys and associated
	values.  You can add, delete, and change pairs of keys and values and
	look up the value associated with a key.

	Keys are arbitrary strings; values are arbitrary integers, except that
	NULL should not be used as a value since tlookup() returns NULL to
	indicate that a key was not found in the table.  In many cases,
	value is actually a pointer to a string.

	Note the difference in the handling of key and value.  The functions
	automatically copy the string that key points to (with savestr()) when
	they create a new table entry; hence, you can pass a pointer to a
	string in a buffer or anywhere.  value, however, is treated as a
	simple int; if it points to a string somewhere, it is your
	responsibility to make sure that that string remains unchanged as long
	as you need it.

	Tables can be freed with free(); however, note that this will not
	free the space used for the keys in the table.  You must free this
	space, and space used for value strings, if any; use tnext() to
	find all the elements.

	table(size) creates a new table and returns a pointer to it.  The
	table has room for size elements, and cannot grow; however, the space
	used for deleted elements is reclaimed automatically.  table() returns
	NULL if it cannot obtain (from malloc()) the space it needs -
	2*sizeof(char *)*size bytes, plus a small fixed overhead.

	Tables are implemented using a hashing technique.  Accesses will be
	fast as long as the table does not become too full; however,
	performance will degrade rapidly if the table fills.  A good rule of
	thumb is to allow space for 10% more elements than you will actually
	need to store.

	tdelete(t,key) deletes key and its associated value from t.  If all
	goes well, 0 is returned; if key was not in t, 1 is returned and t
	is unaltered.  Note that only the space that tinsert() allocated -
	for the key - is freed automatically; you must free any space used
	by the value associated with key.

	tinsert(t,key,value) inserts value as the value associated with
	key in table t.  If all went well, tinsert() returns 0.  If the table
	is full, or no space could be allocated to copy the key, tinsert()
	returns -1.  If key is already in t, tinsert() returns 1; the value
	currently associated with key is not changed.

	tlookup(t,key) returns the value associated with key in t or NULL if
	key isn't found.

	.tp 9
	tnext() is used to scan through all elements in a table in sequence.
	It is used thus:

		char *key;
		int value;
		for (n = -1;
		   (n = tnext(t, n, &key, &value)) >= 0;) {
			/* process pair (key, value)	*/
		}

	Unpredictable results will occur if you insert new elements into a
	table (with tinsert()) while scanning it.  The other table functions
	may be called with no problems.

	CAUTION:  The string pointed to by key as returned is the only copy
	available in the table.  Treat it as read-only!

	tupdate(t,key,value) changes the value associated with key to value.
	tupdate() returns 0 if all went well, 1 if key was not found in t.
	In the latter case, t is unaltered.

internal

	$$locate(t,key) locates key in table t.  It returns the address of an
	entry in the table.  That entry may be EMPTY or DELETED, in which case
	the caller may store key into it.  If NULL is returned, the entry
	wasn't found and no free entry could be found either.

bugs

author

	Jerry Leichter
#endif

/*
 *)EDITLEVEL=30
 * Edit history
 * 0.0 21-May-81 JSL	Invention
 * 0.1 22-May-81 JSL	Use signed arithmetic for speed; bug fixed; add tnext.
 * 1.0 28-May-81 JSL	Bugs arising from oddball unsigned conversions finally
 *			fixed; clean up user interface; add documentation.
 * 1.1 23-Jun-81 JSL	Improve (and fix) documentation; declare malloc().
 * 1.2 13-Jul-82 JSL	Removed extra argument from tdelete().
 */

#define NULL 0

#define TOOBIG 8192		/* Table size limit */
/* Define TOOBIG so that TOOBIG * sizeof(PAIR) just overflows an int */

#define EMPTY 0			/* Empty table entry key value */
#define DELETED 1		/* Deleted table entry value */
/*
 * EMPTY and DELETED must be two different values each distinct from any
 * possible string address.
 *
 */

#define LIMIT 5			/* "Random probe" limit */

extern char *malloc();
extern char *savestr();

typedef struct			/* One table entry */
{	char *key;
	int value;
} PAIR;

typedef struct
{	int tsize;
	PAIR tdata[];
} TABLE;

TABLE *				/* Create a new table */
table(size)
register int size;
{	register TABLE *t;
	register int i;

	if ( size < 0 || size >= TOOBIG
	  || (t = malloc(size*sizeof(PAIR)+sizeof(int))) == NULL )
		return(NULL);

	t->tsize = size;
	for (i = 0; i < size; i++)
		t->tdata[i].key = EMPTY;
	return(t);
}

PAIR *
$$locate(t,key)
TABLE *t;
char *key;
{	register int bigh, i;
	register char *p;
	int h, size;
	char *free;
	long temp;

	bigh = 0;
	for (p = key; *p; )
		bigh = 253*bigh + *p++;
	free = NULL;
	size = t->tsize;

	for (i = 0; i < LIMIT; i++)		/* Random probes */
	{	bigh = 251 * bigh + 1233;
		temp = (unsigned)bigh;		/* Avoid compiler bug... */
		h = (temp * size) >> 16;
#ifdef DEBUG
		printf("Probe %d: bigh = %d[%u], h = %d[%u], size = %d, \
			temp = %ld\n",i,bigh,bigh,h,h,size,temp);
#endif
		p = t->tdata[h].key;
		if (free == NULL && (p == EMPTY || p == DELETED))
			free = &t->tdata[h];
		if (p == EMPTY)
			return(free);
		if (p != DELETED && streq(p,key))
			return(&t->tdata[h]);
	}

#ifdef DEBUG
	printf("Random probes failed...\n");
#endif

	for (h = 0; h < size; h++)		/* Exhaustive search */
	{	p = t->tdata[h].key;
		if (free == NULL && (p == EMPTY || p == DELETED))
			free = &t->tdata[h];
		if (p == EMPTY)
			return(free);
		if (p != DELETED && streq(p,key))
			return(&t->tdata[h]);
	}
	return(free);
}

tdelete(t,key)
TABLE *t;
char *key;
{	register PAIR *p;

	p = $$locate(t,key);
	if (p == NULL || p->key == EMPTY || p->key == DELETED)
		return(1);
	free(p->key);
	p->key = DELETED;
	return(0);
}

tinsert(t,key,value)
TABLE *t;
char *key;
int value;
{	register PAIR *p;

	p = $$locate(t,key);
	if (p == NULL)					/* Table overflow */
		return(-1);
	if (p->key != EMPTY && p->key != DELETED)	/* It's there */
		return(1);
	if ((p->key = savestr(key)) == NULL)		/* No core */
		return(-1);
	p->value = value;
	return(0);
}

tlookup(t,key)
TABLE *t;
char *key;
{	register PAIR *p;

	p = $$locate(t,key);
	if (p == NULL || p->key == EMPTY || p->key == DELETED)
		return(0);
	return(p->value);
}

tnext(t,n,key,value)
TABLE *t;
int n;
char **key;
int *value;
{	register int i, size;
	register PAIR *p;

	if ( n < 0 )
		n = -1;

	size = t->tsize;
	for (i = n + 1; i < size; i++)
		if ((p = t->tdata[i].key) != EMPTY && p != DELETED)
		{	*key = p;
			*value = t->tdata[i].value;
			return(i);
		}
	return(-1);
}

tupdate(t,key,value)
TABLE *t;
char *key;
int value;
{	register PAIR *p;

	p = $$locate(t,key);
	if (p == NULL || p->key == EMPTY || p->key == DELETED)
		return(1);
	p->value = value;
	return(0);
}
