/*
 *	tardy - a tar post-processor
 *	Copyright (C) 1998, 1999, 2002 Peter Miller;
 *	All rights reserved.
 *
 *	This program is free software; you can redistribute it and/or modify
 *	it under the terms of the GNU General Public License as published by
 *	the Free Software Foundation; either version 2 of the License, or
 *	(at your option) any later version.
 *
 *	This program is distributed in the hope that it will be useful,
 *	but WITHOUT ANY WARRANTY; without even the implied warranty of
 *	MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 *	GNU General Public License for more details.
 *
 *	You should have received a copy of the GNU General Public License
 *	along with this program; if not, write to the Free Software
 *	Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111, USA.
 *
 * MANIFEST: functions to manipulate symbol tables
 */

#include <error.h>
#include <fstrcmp.h>
#include <mem.h>
#include <symtab.h>


symtab::symtab()
{
	chain = 0;
	reap = 0;
	hash_modulus = 1 << 4; /* MUST be a power of 2 */
	hash_cutover = hash_modulus;
	hash_split = hash_modulus - hash_cutover;
	hash_cutover_mask = hash_cutover - 1;
	hash_cutover_split_mask = (hash_cutover * 2) - 1;
	hash_load = 0;
	hash_table = (row **)mem_alloc(hash_modulus * sizeof(row *));
	for (str_hash_ty j = 0; j < hash_modulus; ++j)
		hash_table[j] = 0;
}


symtab::~symtab()
{
	for (str_hash_ty j = 0; j < hash_modulus; ++j)
	{
		row **rpp = &hash_table[j];
		while (*rpp)
		{
			row *rp = *rpp; 
			*rpp = rp->overflow;
			if (reap)
				reap(rp->data);
			delete rp;
		}
	}
}


/*
 * NAME
 *	split - reduce symbol table load
 *
 * SYNOPSIS
 *	void split(symtab_ty);
 *
 * DESCRIPTION
 *	The split function is used to split symbols in the bucket indicated by
 *	the split point.  The symbols are split between that bucket and the one
 *	after the current end of the table.
 *
 * CAVEAT
 *	It is only sensable to do this when the symbol table load exceeds some
 *	reasonable threshold.  A threshold of 80% is suggested.
 */

void
symtab::split()
{
	/*
	 * get the list to be split across buckets 
	 */
	row *p = hash_table[hash_split];
	hash_table[hash_split] = 0;

	/*
	 * increase the modulus by one
	 */
	hash_modulus++;
	hash_table =
		(row **)
		mem_change_size
		(
			hash_table,
			hash_modulus * sizeof(row *)
		);
	hash_table[hash_modulus - 1] = 0;
	hash_split = hash_modulus - hash_cutover;
	if (hash_split >= hash_cutover)
	{
		hash_cutover = hash_modulus;
		hash_split = 0;
		hash_cutover_mask = hash_cutover - 1;
		hash_cutover_split_mask = (hash_cutover * 2) - 1;
	}

	/*
	 * now redistribute the list elements
	 *
	 * It is important to preserve the order of the links because
	 * they can be push-down stacks, and to simply add them to the
	 * head of the list will reverse the order of the stack!
	 */
	while (p)
	{
		row *p2 = p;
		p = p2->overflow;
		p2->overflow = 0;

		str_hash_ty index = p2->key.hash() & hash_cutover_mask;
		if (index < hash_split)
		{
			index =
				(
					p2->key.hash()
				&
					hash_cutover_split_mask
				);
		}
		row **ipp;
		for
		(
			ipp = &hash_table[index];
			*ipp;
			ipp = &(*ipp)->overflow
		)
			;
		*ipp = p2;
	}
}


/*
 * NAME
 *	symtab_query - search for a variable
 *
 * SYNOPSIS
 *	int symtab_query(symtab_ty *, string_ty *key);
 *
 * DESCRIPTION
 *	The symtab_query function is used to reference a variable.
 *
 * RETURNS
 *	If the variable has been defined, the function returns a non-zero value
 *	and the value is returned through the 'value' pointer.
 *	If the variable has not been defined, it returns zero,
 *	and 'value' is unaltered.
 */

void *
symtab::query(const rcstring &key)
	const
{
	str_hash_ty index = key.hash() & hash_cutover_mask;
	if (index < hash_split)
		index = key.hash() & hash_cutover_split_mask;
	for (row *p = hash_table[index]; p; p = p->overflow)
	{
		if (key == p->key)
			return p->data;
	}
	return 0;
}


/*
 * NAME
 *	symtab_query_fuzzy - search for a variable name
 *
 * SYNOPSIS
 *	string_ty *symtab_query_fuzzy(symtab_ty *, string_ty *key);
 *
 * DESCRIPTION
 *	The symtab_query_fuzzy function is used to search for a variable name.
 *
 * RETURNS
 *	The closest match for the variable name given.
 *	If no match is particularly close, it returns 0.
 */

rcstring
symtab::query_fuzzy(const rcstring &key)
	const
{
	rcstring best_name;
	double best_weight = 0.6;
	for (str_hash_ty index = 0; index < hash_modulus; ++index)
	{
		for (row *p = hash_table[index]; p; p = p->overflow)
		{
			double weight =
				fmemcmp
				(
					key.to_c_string(),
					key.length(),
					p->key.to_c_string(),
					p->key.length()
				);
			if (weight > best_weight)
				best_name = p->key;
		}
	}
	return best_name;
}


/*
 * NAME
 *	symtab_assign - assign a variable
 *
 * SYNOPSIS
 *	void symtab_assign(symtab_ty *, string_ty *key, void *data);
 *
 * DESCRIPTION
 *	The symtab_assign function is used to assign
 *	a value to a given variable.
 *
 * CAVEAT
 *	The name is copied, the data is not.
 */

void
symtab::assign(const rcstring &key, void *data)
{
	str_hash_ty index = key.hash() & hash_cutover_mask;
	if (index < hash_split)
		index = key.hash() & hash_cutover_split_mask;

	row *p;
	for (p = hash_table[index]; p; p = p->overflow)
	{
		if (key == p->key)
		{
			if (reap)
				reap(p->data);
			p->data = data;
			return;
		}
	}

	p = new row();
	p->key = key;
	p->overflow = hash_table[index];
	p->data = data;
	hash_table[index] = p;

	hash_load++;
	while (hash_load * 10 >= hash_modulus * 8)
		split();
}


/*
 * NAME
 *	symtab_assign_push - assign a variable
 *
 * SYNOPSIS
 *	void symtab_assign_push(symtab_ty *, string_ty *key, void *data);
 *
 * DESCRIPTION
 *	The symtab_assign function is used to assign
 *	a value to a given variable.
 *	Any previous value will be obscured until this one
 *	is deleted with symtab_delete.
 *
 * CAVEAT
 *	The name is copied, the data is not.
 */

void
symtab::assign_push(const rcstring &key, void *data)
{
	str_hash_ty index = key.hash() & hash_cutover_mask;
	if (index < hash_split)
		index = key.hash() & hash_cutover_split_mask;

	row *p = new row();
	p->key = key;
	p->overflow = hash_table[index];
	p->data = data;
	hash_table[index] = p;

	hash_load++;
	while (hash_load * 10 >= hash_modulus * 8)
		split();
}


/*
 * NAME
 *	symtab_delete - delete a variable
 *
 * SYNOPSIS
 *	void symtab_delete(string_ty *name, symtab_class_ty class);
 *
 * DESCRIPTION
 *	The symtab_delete function is used to delete variables.
 *
 * CAVEAT
 *	The name is freed, the data is reaped.
 *	(By default, reap does nothing.)
 */

void
symtab::remove(const rcstring &key)
{
	str_hash_ty index = key.hash() & hash_cutover_mask;
	if (index < hash_split)
		index = key.hash() & hash_cutover_split_mask;

	row **rpp = &hash_table[index];
	for (;;)
	{
		row *rp = *rpp;
		if (!rp)
			break;
		if (key == rp->key)
		{
			if (reap)
				reap(rp->data);
			*rpp = rp->overflow;
			delete rp;
			hash_load--;
			break;
		}
		rpp = &rp->overflow;
	}
}


/*
 * NAME
 *	symtab_dump - dump id table
 *
 * SYNOPSIS
 *	void symtab_dump(symtab_ty *stp, char *caption);
 *
 * DESCRIPTION
 *	The symtab_dump function is used to dump the contents of the
 *	symbol table.  The caption will be used to indicate why the
 *	symbol table was dumped.
 *
 * CAVEAT
 *	This function is only available when symbol DEBUG is defined.
 */

void
symtab::dump(const char *caption)
	const
{
	error("symbol table %s = {", caption);
	for (str_hash_ty j = 0; j < hash_modulus; ++j)
	{
		for (row *p = hash_table[j]; p; p = p->overflow)
		{
			error
			(
				"key = \"%s\", data = %08lX",
				p->key.to_c_string(),
				(long)p->data
			);
		}
	}
	error("}");
}


void
symtab::walk(void (*func)(const symtab &, const rcstring &, void *, void *),
	void *arg)
{
	for (str_hash_ty j = 0; j < hash_modulus; ++j)
		for (row *rp = hash_table[j]; rp; rp = rp->overflow)
			func(*this, rp->key, rp->data, arg);
}