/*
 * Copyright (c) 2002, The Tendra Project <http://www.ten15.org/>
 * All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 * 1. Redistributions of source code must retain the above copyright
 *    notice unmodified, this list of conditions, and the following
 *    disclaimer.
 * 2. Redistributions in binary form must reproduce the above copyright
 *    notice, this list of conditions and the following disclaimer in the
 *    documentation and/or other materials provided with the distribution.
 *
 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
 * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 *
 *
 *    		 Crown Copyright (c) 1997
 *
 *    This TenDRA(r) Computer Program is subject to Copyright
 *    owned by the United Kingdom Secretary of State for Defence
 *    acting through the Defence Evaluation and Research Agency
 *    (DERA).  It is made available to Recipients with a
 *    royalty-free licence for its use, reproduction, transfer
 *    to other parties and amendment for any purpose not excluding
 *    product development provided that any such use et cetera
 *    shall be deemed to be acceptance of the following conditions:-
 *
 *        (1) Its Recipients shall ensure that this Notice is
 *        reproduced upon any copies or amended versions of it;
 *
 *        (2) Any amended version of it shall be clearly marked to
 *        show both the nature of and the organisation responsible
 *        for the relevant amendment or amendments;
 *
 *        (3) Its onward transfer from a recipient to another
 *        party shall be deemed to be that party's acceptance of
 *        these conditions;
 *
 *        (4) DERA gives no warranty or assurance as to its
 *        quality or suitability for any purpose and DERA accepts
 *        no liability whatsoever in relation to any use to which
 *        it may be put.
 *
 * $TenDRA: tendra/src/tools/tspec/hash.c,v 1.8 2004/08/08 08:50:20 stefanf Exp $
 */


#include "config.h"
#include "fmm.h"
#include "msgcat.h"

#include "object.h"
#include "hash.h"
#include "type.h"
#include "utility.h"


/*
 *    STANDARD HASH TABLES
 *
 *    These hash tables represent the various namespaces permitted in C
 *    plus the TDF token namespace.
 */

hash_table *exps;
hash_table *files;
hash_table *keywords;
hash_table *subsets;
hash_table *tags;
hash_table *tag_fields;
hash_table *tokens;
hash_table *types;
hash_table *type_fields;


/*
 *    INITIALISATION ROUTINE
 *
 *    This routine initialises the standard hash tables and sets a few
 *    miscellaneous variables.
 */

void
init_hash(void)
{
	buffer = xalloc (buffsize + 100);
	exps = make_hash_table ("Expression");
	files = make_hash_table ("Output file");
	keywords = make_hash_table ("Keyword");
	subsets = make_hash_table ("Set");
	tags = make_hash_table ("Tag");
	tag_fields = make_hash_table ("Field selector struct/union");
	tokens = make_hash_table ("Token");
	types = make_hash_table ("Type");
	type_fields = make_hash_table ("Field selector");
	return;
}


/*
 *    HASHING ROUTINE
 *
 *    This routine finds the hash value of the string nm.  This value must
 *    lie in the range [ 0, hash_size).
 */

static int
hash(char *nm)
{
	char *s;
	int n = 0;
	for (s = nm; *s; s++) n += *s;
	return (n % hash_size);
}


/*
 *    CREATE A NEW HASH TABLE
 *
 *    This routine creates a new hash table called nm.
 */

hash_table *
make_hash_table(char *nm)
{
	int i;
	hash_table *t = xalloc (sizeof (*t));
	t->name = nm;
	for (i = 0; i < hash_size; i++) t->array [i] = null;
	return (t);
}


/*
 *    LOOK UP A NAME IN A HASH TABLE
 *
 *    This routine looks up the object nm (version v) in the hth column
 *    of hash table t.  It returns the object if it is found, or null
 *    otherwise.
 */

static object *
lookup_hash(hash_table *t, char *nm, int v, int h)
{
	hash_elem *e = t->array [h];
	while (e) {
		if (streq (nm, e->obj->name)) {
			if (v == e->vers || v == any_version) return (e->obj);
		}
		e = e->next;
	}
	return (null);
}


/*
 *    ADD AN OBJECT TO A HASH TABLE
 *
 *    This routine adds the object p (version v) to the hash table t,
 *    reporting an error and returning the old value if it is already
 *    defined.  Otherwise it returns p.
 */

object *
add_hash(hash_table *t, object *p, int v)
{
	hash_elem *e;
	char *nm = p->name;
	int h = hash (nm);
	object *q = lookup_hash (t, nm, v, h);
	if (q != null) {
		char *fn = q->filename;
		if (fn) {
			MSG_name_already_defined_at(t->name, nm, fn, q->line_no);
		} else {
			MSG_name_already_defined(t->name, nm);
		}
		return (q);
	}
	e = xalloc (sizeof (*e));
	e->obj = p;
	e->vers = v;
	e->next = t->array [h];
	t->array [h] = e;
	return (p);
}


/*
 *    SEARCH A HASH TABLE FOR AN OBJECT
 *
 *    This routine searches the hash table t for the object named nm
 *    (version v), returning it if it is found.  If it is not found then
 *    null is returned.
 */

object *
search_hash(hash_table *t, char *nm, int v)
{
	int h = hash (nm);
	return (lookup_hash (t, nm, v, h));
}


/*
 *    SORT THE ELEMENTS OF A HASH LIST
 *
 *    This routine sorts the elements of the hash table t into a single
 *    alphabetical list.  The table cannot be used subsequently.
 */

hash_elem *
sort_hash(hash_table *t)
{
	int i;
	hash_elem *r = null;
	for (i = 0; i < hash_size; i++) {
		hash_elem *p = t->array [i];
		while (p) {
			hash_elem *pn = p->next;
			hash_elem *q = r, *s = null;
			while (q) {
				if (strcmp (p->obj->name, q->obj->name) <= 0) break;
				s = q;
				q = q->next;
			}
			if (s == null) {
				p->next = r;
				r = p;
			} else {
				p->next = s->next;
				s->next = p;
			}
			p = pn;
		}
	}
	return (r);
}