/***********************************
  (C) Copyright 1992-1993; dit/upm
  Distributed under the conditions stated in the
  TOPO General Public License (see file LICENSE)
  ***********************************/

/***********************************

  Juan carlos Berrocal Colmenarejo

  2 Nov 90

  Hash table management module.
  Creation and management of hash tables of any size.


  COMPILATION OPTIONS: The behaviour of this module can be modified
  by the following compilation flags:

  (none)

  ************************************/

/* LINTLIBRARY */


/* KJT 12/02/12: Added */
#include <stdlib.h>
#include "lihash.h"
#include "lilists.h"
#include "limisc.h"


/* Get_Key
 * Returns v mod nelems
 */
#define Get_Key(v,nelems) ((v<0?-v:v)%nelems)

typedef struct { int     nextUsedSlot;
		 ListTyp pElems;
	       } HTabElemTyp, *PHTabElemTyp;


typedef struct { int          firstElem;
		 int          size;
		 void       (*free)();
		 int        (*key)();
		 boolean    (*comp)();
		 void       (*print)();
		 HTabElemTyp *pht;
	       } HashTableTyp, *PHashTableTyp;


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


/* Create_HT
 * Create a hash table.
 * Return the descriptor of the table.
 * Attached functions:
 *  FreeF  -> To free the information in the table.
 *  KeyF   -> To compute the hash key of an element.
 *  CompF  -> To compare 2 elements.
 *  PrintF -> To print an element with "pstr"(a function to print strings).
 */
HashDTyp Create_HT( size, FreeF, KeyF, CompF, PrintF )
     int     size;
     void    (*FreeF)();
     int     (*KeyF)();
     boolean (*CompF)();
     void    (*PrintF)();
{
  PHTabElemTyp  pEl;
  PHashTableTyp pTable;
  int           j;

  pEl               = (PHTabElemTyp)emalloc(size*sizeof(HTabElemTyp));
  pTable            = (PHashTableTyp)emalloc(sizeof(HashTableTyp));
  pTable->size      = size;
  pTable->free      = FreeF;
  pTable->comp      = CompF;
  pTable->key       = KeyF;
  pTable->print     = PrintF;
  pTable->firstElem = -1;
  pTable->pht       = pEl;

  for ( j=0; j<size; j++ ) {
    (pEl+j)->nextUsedSlot = -1;
    (pEl+j)->pElems   = Create_list();
  }
  return (HashDTyp)pTable;
}


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


/* Free_HT
 * Free the memory allocated to the hash table d and its data.
 */
void Free_HT( d )
     HashDTyp d;
{
  PHashTableTyp tab;
  int cont;

  tab = (PHashTableTyp)d;
  for ( cont=tab->firstElem; cont!=-1 ; cont=tab->pht[cont].nextUsedSlot )
    Free_list( tab->pht[cont].pElems, tab->free );
  free((char *)tab->pht);
  free((char*)tab);
}


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


/* Clean_HT
 * Clean hash table d. ( release all stored data ).
 */
void Clean_HT( d )
     HashDTyp d;
{
  PHashTableTyp tab;
  int cont,next;

  tab = (PHashTableTyp)d;
  for ( cont=tab->firstElem; cont!=-1; cont=next ) {
    Free_list( tab->pht[cont].pElems, tab->free );
    tab->pht[cont].pElems   = NULL;
    next                    = tab->pht[cont].nextUsedSlot;
    tab->pht[cont].nextUsedSlot = -1;
  }
  tab->firstElem = -1;
}


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


/* Insert_HT
 * Insert an element in hash table d inconditionally
 * ( no matter if the element is already in the table).
 * d    is the hash table descriptor.
 * elem is the data to insert.
 */
void Insert_HT( d, elem )
     HashDTyp    d;
     DataHashTyp elem;
{
  PHashTableTyp tab;
  int key;

  tab = (PHashTableTyp)d;
  key = Get_Key( tab->key(elem), tab->size );
  if ( tab->pht[key].pElems==NULL ) {
    tab->pht[key].nextUsedSlot = tab->firstElem;
    tab->firstElem         = key;
  }
  tab->pht[key].pElems = Insert_list(elem,tab->pht[key].pElems);
}


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


/* Insert_IfNotIn_HT
 * Insert an element in hash table d, only if it is not at the table yet.
 * Otherwise : no insertion is performed.
 * d    is the hash table descriptor.
 * elem is the data to insert.
 */
void Insert_IfNotIn_HT( d, elem )
     HashDTyp    d;
     DataHashTyp elem;
{
  PHashTableTyp tab;
  int key;

  tab = (PHashTableTyp)d;
  key = Get_Key( tab->key(elem), tab->size );
  if ( tab->pht[key].pElems==NULL ) {
    tab->pht[key].nextUsedSlot = tab->firstElem;
    tab->firstElem         = key;
  }
  tab->pht[key].pElems = Add_IfNotIn_list(elem,tab->pht[key].pElems,tab->comp);
}


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


/* In_HT
 * returns TRUE if element elem is in the hash table.
 * d     is the hash table descriptor.
 * elem  is the data to be looked for.
 */
boolean In_HT( d, elem )
     HashDTyp    d;
     DataHashTyp elem;
{
  PHashTableTyp tab;

  tab = (PHashTableTyp)d;
  return In_list( elem,
		 tab->pht[Get_Key(tab->key(elem),tab->size)].pElems,
		 tab->comp
		 );
}


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


/* Remove_HT
 * Removes an element from a hash table d.
 */
void Remove_HT( d, elem )
     HashDTyp    d;
     DataHashTyp elem;
{
  int key;
  PHashTableTyp tab;
  ListTyp l;
  int aux,cont;
  boolean out;


  tab = (PHashTableTyp)d;
  key = Get_Key(tab->key(elem),tab->size);
  l   = tab->pht[key].pElems;
  l   = LookFor_list(elem,l,tab->comp);
  if (l!=NULL) {
    tab->free(LookInfo_list(l));
    tab->pht[key].pElems = DeleteNode_list(l,tab->pht[key].pElems);
  }
  l = tab->pht[key].pElems;
  if (l == NULL)
    {
      if (tab->firstElem == key)
	tab->firstElem = tab->pht[key].nextUsedSlot;
      else
	{
	  aux = tab->pht[key].nextUsedSlot;
	  out = FALSE;
	  for (cont=tab->firstElem ; ((cont != -1) && (out == FALSE)) ; cont=tab->pht[cont].nextUsedSlot)
	    if (tab->pht[cont].nextUsedSlot == key)
	      {
		tab->pht[cont].nextUsedSlot = aux;
		out = TRUE;
	      }
	}
    }
}


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


/* LookFor_HT
 * Look for an element equal to elem in the hash table.
 * If not found return NULL.
 */
DataHashTyp LookFor_HT( d, elem )
     HashDTyp    d;
     DataHashTyp elem;
{
  ListTyp l;

  l   = LookFor_list( elem,
		     ((PHashTableTyp)d) ->
		     pht[ Get_Key( ((PHashTableTyp)d)->key(elem),
				  ((PHashTableTyp)d)->size )
			 ].pElems,
		     ((PHashTableTyp)d) -> comp );

  return (l==NULL)? NULL : LookInfo_list(l);

}


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


/* Print_HT
 * Print a hash table "d".
 * "pstr" is the function used to print strings.
 */
void Print_HT( d, pstr )
     HashDTyp d;
     void (*pstr)();
{
  int i, nodesCont, usedSlots;
  PHashTableTyp  tab;
  ListTyp l;
  char str[15];

  nodesCont = 0;
  usedSlots = 0;
  tab = (PHashTableTyp)d;
  pstr("\n");
  for ( i=0 ; i<tab->size ; i++ )
    if ( tab->pht[i].pElems != NULL ){
      pstr("position ");
      PrintInt(pstr,i);
      pstr("\n");
      for ( l=tab->pht[i].pElems; l!=NULL; l=Next_list(l) ) {
	nodesCont++;
	tab->print(pstr,LookInfo_list(l));
      }
      if ( tab->pht[i].pElems!=NULL )
	usedSlots++;
    }
  PrintInt(pstr,nodesCont);
  pstr(" elements in the hash table. ");
  (void)sprintf(str,"%.1f",(usedSlots/(tab->size))*100);
  pstr(str);
  pstr("% slots used.\n");
}


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


/* Stat_HT
 * Returns the number of slots used and the total number of elements
 * in the hash table.
 */
void Stat_HT( d, slotsUsed, nelem )
     HashDTyp d;
     int *slotsUsed,*nelem;
{
  int i;
  PHashTableTyp tab;
  ListTyp list;

  *slotsUsed = 0;
  *nelem     = 0;
  tab        = (PHashTableTyp)d;
  for ( i=0; i<tab->size; i++ )  {
    list = (tab->pht+i)->pElems;
    if ( list!=NULL ){
      (*slotsUsed)++;
      *nelem = (*nelem) + Length_list( list );
    }
  }
}







