/* %Z%%M% %I% %E% */

/*
 * Copyright (c) 1990, 1991, 1995 by Wayne C. Gramlich.
 * All rights reserved.
 *
 * Permission to use, copy, modify, distribute, and sell this software
 * for any purpose is hereby granted without fee provided that the above
 * copyright notice and this permission are retained.  The author makes
 * no representations about the suitability of this software for any purpose.
 * It is provided "as is" without express or implied warranty.
 */

/* Implementation of a key-value table data abstraction: */

#ifndef FILE_EXPORTS_H
#include "file_exports.h"
#endif

#ifndef HASH_EXPORTS_H
#include "hash_exports.h"
#endif

#ifndef HEAP_EXPORTS_H
#include "heap_exports.h"
#endif

#ifndef TABLE_DEFS_H
#include "table_defs.h"
#endif

#ifndef VECTOR_DEFS_H
#include "vector_defs.h"
#endif

/* This data structure is used by tbl_iterate(). */
typedef struct {
	Tbl_value		handle;
	Tbl_routine_iterate	routine;
} *Tbl_iterate, Tbl_iterate_rec;

typedef struct {
	Tbl_handle		handle;
	Tbl_routine_write	key_write_routine;
	Stdio			out_file;
	Tbl_routine_write	value_write_routine;
} *Tbl_write, Tbl_write_rec;

extern int	tbl_key_equal(Tbl_pair, Tbl_pair, Tbl);
extern int	tbl_key_hash(Tbl_pair, Tbl);
extern int	tbl_iterate_pair(Tbl_pair, Tbl_iterate);
extern void	tbl_key_list_extract_key(Tbl_pair, Vec(Tbl_key));
extern void	tbl_value_list_extract_value(Tbl_pair, Vec(Tbl_value));
extern int	tbl_write_pair(Tbl_pair, Tbl_write);

/* LINTLIBRARY */

/*
 * tbl_client_data(hash)
 *	This routine will return the client data (i.e. handle) for "hash".
 */
Tbl_value
tbl_client_data(
	Tbl		tbl)
{
	return tbl->handle;
}

/*
 * tbl_create(size, routine_hash, routine_equal, handle, heap)
 *	This routine will create and return a new table object.  "size"
 *	specifies the initial minimum number of hash slots.  "routine_hash"
 *	is a routine that given a key object will return a hash value.
 *	"routine_equal" is a routine that given two key objects will return
 *	1 if they are equal and 0 otherwise.  "handle" is passed as the
 *	last argument to "routine_hash" and "routine_equal".  In addition,
 *	for "handle" is returned by tbl_lookup whenever an key object can
 *	not be found.  "heap" is used to allocate the new hash object.
 */
Tbl
tbl_create(
	int		size,
	Tbl_routine_equal equal_routine,
	Tbl_routine_hash hash_routine,
	Tbl_value	handle,
	Heap		heap)
{
	Tbl		tbl;

	tbl = heap_allocate(heap, Tbl);
	tbl->hash = hash_create(Tbl_pair, size, tbl_key_equal,
				tbl_key_hash, (Tbl_pair)tbl, heap);
	tbl->handle = handle;
	tbl->heap = heap;
	tbl->routine_equal = equal_routine;
	tbl->routine_hash = hash_routine;
	return tbl;
}

/*
 * tbl_delete(hash, value)
 *	This routine will remove "value" from "hash".  1 is returned if
 *	"value" was not present in "hash" and 0 otherwise.
 */
int
tbl_delete(
	Tbl		tbl,
	Tbl_key		key)
{
	Tbl_pair_rec	key_pair;

	key_pair.key = key;
	return hash_delete(Tbl_pair, tbl->hash, &key_pair);
}

/*
 * tbl_destroy(hash)
 *	This routine will release all of the storage associated with "hash".
 */
void
tbl_destroy(
	Tbl		tbl)
{
	hash_destroy(Tbl_pair, tbl->hash);
	heap_free(tbl->heap, (Pointer)tbl);
}

/*
 * tbl_erase(hash)
 *	This routine will remove all entries from "hash".
 */
void
tbl_erase(
	Tbl		tbl)
{
	hash_erase(Tbl_pair, tbl->hash);
}

/*
 * tbl_exists(hash, value)
 *	This routine will return 1 if "value" is in "hash" and 0 otherwise.
 */
int
tbl_exists(
	Tbl		tbl,
	Tbl_key		key)
{
	Tbl_pair_rec	pair;

	pair.key = key;
	return hash_exists(Tbl_pair, tbl->hash, &pair);
}

/*
 * tbl_iterate(hash, routine, handle)
 *	This routine will iterate over each value in "hash" calling
 *	"routine(value, handle, hash->handle)=>int" for each value.
 *	The sum of the values returned from "routine" is returned. O(n)
 */
int
tbl_iterate(
	Tbl		tbl,
	Tbl_routine_iterate routine,
	Tbl_value	handle)
{
	Tbl_iterate_rec	iterate;

	iterate.handle = handle;
	iterate.routine = routine;
	return hash_iterate(Tbl_pair, tbl->hash, tbl_iterate_pair, &iterate);
}

/*
 * tbl_iterate_pair(pair, iterate)
 *	This routine will perform one iteration on "pair".
 */
int
tbl_iterate_pair(
	Tbl_pair	pair,
	Tbl_iterate	iterate)
{
	return (*iterate->routine)(pair->key, pair->value, iterate->handle);
}

/*
 * tbl_insert(tbl, key, value)
 *	This routine will insert "key" and "value" into "tbl" provided that
 *	"key" is not already in "tbl".  1 is returned if "key" was already in
 *	"tbl" and 0 otherwise. O(k)
 */
int
tbl_insert(
	Tbl		tbl,
	Tbl_key		key,
	Tbl_value	value)
{
	Tbl_pair	pair;

	pair = heap_allocate(tbl->heap, Tbl_pair);
	pair->key = key;
	pair->value = value;
	if (hash_insert(Tbl_pair, tbl->hash, pair)) {
		heap_free(tbl->heap, (Pointer)pair);
		return 1;
	} else {
		return 0;
	}
}

/*
 * tbl_key_equal(pair1, pair1, tbl)
 *	This routine will return 1 if the keys in "pair1" and "pair2" are
 *	equal and 0 otherwise.
 */
int
tbl_key_equal(
	Tbl_pair	pair1,
	Tbl_pair	pair2,
	Tbl		tbl)
{
	return (*tbl->routine_equal)(pair1->key, pair2->key, tbl->handle);
}

/*
 * tbl_key_hash(pair, tbl)
 *	This routine will a hash value for the key in "pair".
 */
int
tbl_key_hash(
	Tbl_pair	pair,
	Tbl		tbl)
{
	return (*tbl->routine_hash)(pair->key, tbl->handle);
}

/*
 * tbl_key_list_extract(tbl)
 *	This routine will return the list of keys from "tbl".
 */
Vec(Tbl_key)
tbl_key_list_extract(
	Tbl		tbl)
{
	Vec(Tbl_key)	keys;

	keys = vec_create(Tbl_key, tbl->heap);
	vec_predict(Tbl_key, keys, hash_size(Tbl_pair, tbl->hash));
	(void)hash_iterate(Tbl_pair, tbl->hash,
			   (Hsh_routine_iterate)tbl_key_list_extract_key,
			   keys);
	return keys;
}

/*
 * tbl_key_list_extract_key(pair, keys)
 *	This routine will append "pair"->key to "keys".
 */
void
tbl_key_list_extract_key(
	Tbl_pair	pair,
	Vec(Tbl_key)	keys)
{
	vec_append(Tbl_key, keys, pair->key);
}

/*
 * tbl_lookup(hash, value)
 *	This routine will return the "value" from "hash".  If "value" is
 *	not in "hash", the default handle (specified as an argument to
 *	tbl_create) will be returned. O(k)
 */
Tbl_value
tbl_lookup(
	Tbl		tbl,
	Tbl_key		key)
{
	Tbl_pair_rec	key_pair;
	Tbl_pair	pair;

	key_pair.key = key;
	pair = hash_lookup(Tbl_pair, tbl->hash, &key_pair);
	if (pair == (Tbl_pair)tbl) {
		return tbl->handle;
	} else {
		return pair->value;
	}
}

/*
 * tbl_read(tbl, key_read_routine, value_read_routine, in_file, heap, handle)
 *	This routine will read back in the contents of a table written by
 *	tbl_write().  "key_read_routine(in_file, heap, handle)=>key"
 *	and "value_read_routine(in_file, heap,handle)=>value" is used
 *	to read key-value pairs.  The number of pairs read is returned.
 */
int
tbl_read(
	Tbl		tbl,
	Tbl_routine_read key_read_routine,
	Tbl_routine_read value_read_routine,
	Stdio		in_file,
	Heap		heap,
	Tbl_handle	handle)
{
	Tbl_key		key;
	int		size;
	Tbl_value	value;

	size = getw(in_file);
	while (size-- > 0) {
		key = (*key_read_routine)(in_file, heap, handle);
		value = (*value_read_routine)(in_file, heap, handle);
		(void)tbl_insert(tbl, key, value);
	}
	return 0;
}

/*
 * tbl_replace(tbl, key, value)
 *	This routine will store "key" and "value" into "tbl" replacing
 *	any previous key-value pair.  1 is returned if "key" and "value"
 *	were not already in "tbl" and 0 otherwise. O(k)
 */
int
tbl_replace(
	Tbl		tbl,
	Tbl_key		key,
	Tbl_value	value)
{
	Tbl_pair_rec	key_pair;
	Tbl_pair	pair;

	key_pair.key = key;
	pair = hash_lookup(Tbl_pair, tbl->hash, &key_pair);
	if (pair == (Tbl_pair)tbl) {
		pair = heap_allocate(tbl->heap, Tbl_pair);
		pair->key = key;
		pair->value = value;
		(void)hash_replace(Tbl_pair, tbl->hash, pair);
		return 1;
	} else {
		pair->value = value;
		return 0;
	}
}

/*
 * tbl_size(hash)
 *	This routine will return the size of "hash".
 */
int
tbl_size(
	Tbl		tbl)
{
	return hash_size(Tbl_pair, tbl->hash);
}

/*
 * tbl_value_list_extract(tbl)
 *	This routine will return the list of values from "tbl".
 */
Vec(Tbl_value)
tbl_value_list_extract(
	Tbl		tbl)
{
	Vec(Tbl_value)	values;

	values = vec_create(Tbl_value, tbl->heap);
	vec_predict(Tbl_value, values, hash_size(Tbl_pair, tbl->hash));
	(void)hash_iterate(Tbl_pair, tbl->hash,
			   (Hsh_routine_iterate)tbl_value_list_extract_value,
			   values);
	return values;
}

/*
 * tbl_value_list_extract_value(pair, values)
 *	This routine will append "pair"->value to "values".
 */
void
tbl_value_list_extract_value(
	Tbl_pair	pair,
	Vec(Tbl_value)	values)
{
	vec_append(Tbl_value, values, pair->value);
}

/*
 * tbl_write(tbl, key_write_routine, value_write_routine, out_file, handle)
 *	This routine will write out the contents of a table such
 *	that it can be read back in using tbl_read(). 
 *	"key_write_routine(key, out_file, handle)" and
 *	"value_read_routine(in_file, heap,handle)=>value" are used
 *	to write key-value pairs.
 */
void
tbl_write(
	Tbl		tbl,
	Tbl_routine_write key_write_routine,
	Tbl_routine_write value_write_routine,
	Stdio		out_file,
	Tbl_handle	handle)
{
	Tbl_write_rec	write;

	write.handle = handle;
	write.key_write_routine = key_write_routine;
	write.out_file = out_file;
	write.value_write_routine = value_write_routine;
	(void)putw(hash_size(Tbl_pair, tbl->hash), out_file);
	(void)hash_iterate(Tbl_pair, tbl->hash,
			   tbl_write_pair, (Tbl_pair)&write);
}

/*
 * tbl_write_pair(pair, write)
 *	This routine will write "pair" out to a file using "write".  1 is
 *	returned
 */
int
tbl_write_pair(
	Tbl_pair	pair,
	Tbl_write	write)
{
	(*write->key_write_routine)(pair->key, write->out_file, write->handle);
	(*write->value_write_routine)(pair->value,
				      write->out_file, write->handle);
	return 1;
}