/* @(#)hash.c	17.1.1.1 (ES0-DMD) 01/25/02 17:47:37 */
/*===========================================================================
  Copyright (C) 1995 European Southern Observatory (ESO)
 
  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., 675 Massachusetss Ave, Cambridge, 
  MA 02139, USA.
 
  Corresponding concerning ESO-MIDAS should be addressed as follows:
	Internet e-mail: midas@eso.org
	Postal address: European Southern Observatory
			Data Management Division 
			Karl-Schwarzschild-Strasse 2
			D 85748 Garching bei Muenchen 
			GERMANY
===========================================================================*/

/*++++++++++++++
.TYPE		Module
.IDENTIFICATION hash.c
.AUTHOR    	Francois Ochsenbein [ESO-IPG]
.LANGUAGE  	C
.VERSION   1.0	18-Apr-1988: Creation
.KEYWORDS	Hash table
.ENVIRONMENT	Any
.COMMENTS	
\begin{TeX}
\end{TeX}

-----------------------------------------------------------------------*/

#define	DEBUG		1	/* For debugging only		*/

#define	PM_LEVEL 	LEVEL_STR	/* Only string-like functions 	*/

#define  PASCAL_DEF	0	/* Don't include pascalisation ... */
#include <stesodef.h>
#include <hash.h>

#define FINISH	goto FIN

MID_STATIC int index;
MID_STATIC H_ITEM *previous;
MID_STATIC int factor = 2;		/* seems to be the best factor... */

/*==========================================================================*/
int h_factor(n)
/*+++
.PURPOSE Set factor for computation of index
.RETURNS n
.REMARKS To modify for better hashing function
---*/
	int	n;		/* IN: Factor	*/
{
  factor = n;
  if (factor < 1) 	factor = 1;
  
  return(n);
}

/*==========================================================================*/
static int h_index(ht, symbol, len)
/*+++
.PURPOSE Compute index from symbol
.RETURNS The index (-1 for error)
.REMARKS Simple addition of ASCII values.
---*/
	H_TABLE	*ht;		/* IN: Descriptor of Tex table	*/
	char	*symbol;	/* IN: Symbol 	*/
	int	len;		/* IN: length of symbol		*/
{
	register int i;
	register char *p;

  for (index = 0, p = symbol, i = len; --i >=0; p++)
	index = ((index * factor) + (*p & 077)) % ht->size;

#if 0
  for (index = 0, p = symbol, i = len; --i >=0; p++)
	index += (*p & 0177);
  index %= ht->size;
#endif

  return(index);
}

/*==========================================================================*/
H_TABLE *h_create(size)
/*+++
.PURPOSE Create a Hash table.
.RETURNS Address of create table (NULL if failed)
.REMARKS Size is adjusted to have no divisor smaller than 19.
---*/
	int		size;		/* IN: size (number of elements)*/
{ 	
	register H_TABLE *ht;
	register int l;

  ENTER("*h_create");

  TRACE_ED_I("Proposed size is: ", size);

	/* Compute a number which has no divisor by 2,3,5,7,11,13,17,19 */

  for ( l = (size & 1 ? size : size+1); ; l += 2)
  {	if ( (l% 3) == 0)	continue;
	if ( (l% 5) == 0)	continue;
	if ( (l% 7) == 0)	continue;
	if ( (l%11) == 0)	continue;
	if ( (l%13) == 0)	continue;
	if ( (l%17) == 0)	continue;
	if ( (l%19) == 0)	continue;
	break;
  }

  TRACE_ED_I("Appropriate size is: ",l);

  ht = (H_TABLE *)mm_alloc(sizeof(H_TABLE) + (l-1)*sizeof(H_ITEM *));
  if(ht)
  {	ht->size = l;
	ht->symbols    = 0;
	ht->collisions = 0;
	while (--l >= 0)	ht->start[l] = NULL_PTR(H_ITEM);
  }

  EXIT_PTR(H_TABLE, ht);
}  

/*==========================================================================*/
int h_clear(ht)
/*+++
.PURPOSE Clear a h-table
.RETURNS OK 
.REMARKS 
---*/
	H_TABLE	*ht;		/* IN: Descriptor of Hash table to clear */
{
	register H_ITEM *pi, *pin;
	register int i;

  ENTER("h_clear");

  for (i=0; i < ht->size; i++)
  {	for (pi = ht->start[i]; pi; pi = pin)
		pin = pi->next, MEM_FREE(pi);
	ht->start[i] = NULL_PTR(H_ITEM);
  }
  ht->collisions = 0;
  ht->symbols    = 0;

  EXIT(OK);
}

/*==========================================================================*/
H_ITEM *h_look(ht, symbol, len)
/*+++
.PURPOSE Look for a specified symbol in the table.
.RETURNS Address of found item, or NULL
.REMARKS Use hash-table
---*/
	H_TABLE	*ht;		/* IN: Descriptor of Hash table	*/
	char	*symbol;	/* IN: symbol to retrieve	*/
	int len;		/* IN: Length of symbol		*/
{
	register H_ITEM *pi;

  ENTER("*h_look");

#if DEBUG
  TRACE_ED_STR2("Looking for: ", symbol, len);
#endif

  pi = ht->start[h_index(ht, symbol, len)];		/* Position	*/
  for ( previous = NULL_PTR(H_ITEM); pi; previous = pi, pi = pi->next)
  {	if (pi->ls != len)	continue;
	if (oscomp(symbol, &(pi->strings[0]), len) == 0)
		break;
  }

  EXIT_PTR(H_ITEM, pi);
}

/*==========================================================================*/
int h_remove(ht, symbol, len)
/*+++
.PURPOSE Remove an item from table.
.RETURNS OK / NOK (didn't exist)
.REMARKS 
---*/
	H_TABLE	*ht;		/* IN: Descriptor of Tex table	*/
	char	*symbol;	/* IN: Symbol to remove	*/
	int	len;		/* IN: Length of symbol	*/
{ 	
	register H_ITEM *pi;
	int st;
  
  ENTER("h_remove");

  st = NOK;
  if_not(pi = h_look(ht, symbol, len))	FINISH;
  
  if (previous)					/* Modify Links	*/
  	previous->next 	 = pi->next;
  else	ht->start[index] = pi->next;

  ht->symbols -= 1;
  if (ht->start[index])	 ht->collisions -= 1;	/* Update collisions	*/
  st = OK;

  MEM_FREE(pi);				/* Free Allocated Memory	*/

  FIN:
  EXIT(st);
}

/*==========================================================================*/
H_ITEM *h_add(ht, symbol, ls, eq, leq)
/*+++
.PURPOSE Insert the item (symboling, equivalence) in the table.
.RETURNS Address of allocated item
.REMARKS If symbol already exists, it's modified.
---*/
	H_TABLE	*ht;		/* IN: Descriptor of Tex table	*/
	char	*symbol;	/* IN: Symbol to insert	*/
	int	ls;		/* IN: Length of Symbol		*/
	char 	*eq;		/* IN: Equivalence string	*/
	int	leq;		/* IN: Length of Equivalence String	*/
{ 	
	register H_ITEM *pi;
	register char *p;

  ENTER("*h_add");

#if DEBUG
  TRACE_ED_STR2("Insert: ", symbol, ls);
  TRACE_ED_STR2("Equate: ", eq, leq);
#endif

	/* 1. Check if symbol already exists. 
		If not, create it.		*/

  pi = h_look(ht, symbol, ls);
  if(pi)
  {  	if (pi->leq == leq)	goto REPLACE;
	h_remove(ht, symbol, ls);
	pi = h_look(ht, symbol, ls);
  }

	/* 2. Allocate H_ITEM: strings are terminated with EOS	*/

  if_not(pi = (H_ITEM *) mm_alloc(leq + ls + sizeof(H_ITEM)))
  	FINISH;
  pi->next = NULL_PTR(H_ITEM);
  ht->symbols += 1;

  if (previous)
  	previous->next 	 = pi, ht->collisions += 1;
  else	ht->start[index] = pi;


	/* 3. Fill H_ITEM, and copy strings	*/
	
  REPLACE:
  pi->leq = leq;
  pi->ls  = ls;
  p = &(pi->strings[0]);
  p += oscopy(p, symbol, ls);
  *(p++) = EOS;
  p += oscopy(p, eq, leq);
  *(p++) = EOS;
  
  FIN:
  EXIT_PTR(H_ITEM, pi);
}

/*==========================================================================*/
char *h_get(ht, symbol, len)
/*+++
.PURPOSE Retrieve the string equated to a given symbol
.RETURNS Address of equivalence string, or NULL
.REMARKS 
---*/
	H_TABLE	*ht;		/* IN: Descriptor of Tex table	*/
	char	*symbol;	/* IN: symbol to retrieve	*/
	int 	len;		/* IN: Length of symbol		*/
{ 	
	register H_ITEM *pi;
	char *r;

  ENTER("*h_get");

#if DEBUG
  TRACE_ED_STR2("Looking for an equivalence to: ", symbol, len);
#endif

  pi = h_look(ht, symbol, len);
  if(pi)
  	r = &(pi->strings[1+pi->ls]);
  else	r = NULL_PTR(char);

#if DEBUG
  if(r)
  TRACE_ED_STR2("===================>", r, pi->leq);
#endif

  EXITp(r);
}

/*==========================================================================*/
int h_log(ht)
/*+++
.PURPOSE Log the statistics for a hash table.
.RETURNS Number of free symbols.
.REMARKS Not traced.
---*/
	H_TABLE	*ht;		/* IN: Descriptor of Tex table	*/
{ 	
	int	n, i;

  for (n = 0, i = ht->size; --i >= 0; )
	if_not(ht->start[i])	n++;	/* Free entries */

  LOG_ED_I("Size of h-table: ", ht->size);
  LOG_ED_I(" Unused entries: ", n);
  LOG_ED_I("  Total symbols: ", ht->symbols);
  LOG_ED_I("     Collisions: ", ht->collisions);

  return(n);
}