/****************************************************************************/
/*                                                                          */
/*                      Chaine de CAO & VLSI   Alliance                     */
/*                                                                          */
/*    Produit : librairie TSH - Gestion de tables de hachage                */
/*    Fichier : thash.c                                                     */
/*                                                                          */
/*    (c) copyright 1991 Laboratoire MASI equipe CAO & VLSI                 */
/*    Tous droits reserves                                                  */
/*    Support : e-mail cao-vlsi@masi.ibp.fr                                 */
/*                                                                          */
/*    Auteur(s) :   Burgun Luc                          le : 07/01/92       */
/*                                                                          */
/*    Modifie par :                                     le : 20/06/92       */
/*    Modifie par :                                     le : ../../....     */
/*    Modifie par :                                     le : ../../....     */
/*                                                                          */
/****************************************************************************/

#include <stdio.h>
#include  MUT_H
#include "log200.h"

#undef MAX_CALLS
#define MAX_CALLS 20

/* les fonction de l'utilisateurs :
   ------------------------------

   a. creation de table 

   pTH createTH(len)
   int len;

   b. destruction de la table

   destroyTH(pTable)
   pTH pTable;

   c. recherche d'un element

   int searchTH(pTable,key)
   pTH pTable;
   char *key;

   d. ajout d'un element (ecrasement de la valeur s'il existe deja un element
      dans la table possedant la meme cle)

   int addTH(pTable,key,value)
   pTH pTable;
   char *key;
   int value;

   e. test d'existence et ajout d'un element dans la table.( renvoie 0 si
      l'element n'existait pas avant son ajout, 1 sinon).

   int addExistTH(pTable,key,value)
   pTH pTable;
   char *key;
   int value;

   f. destruction d'un element

   int deleteTH(pTable,key)
   pTH pTable;
   char *key;

   g. affichage total d'une table avec la cle en %s et la valeur en %d.

   void displayTH(pTable)
   pTH pTable;

   h. reallocation d'une table 

   void reAllocTH(pTable)
   pTH pTable ;
*/

/*--------------- la fonction de base pour le hachage.---------------- */


int hashTH(pn)
char *pn;
{
return(abs((int) pn * ((int) pn >> 5) >> 4));
}

   /* creation d'une table de hachage */

pTH createTH(len)
int len;
{
pTH pTable;
pElemTH pEl;
int i;

if (len <= 0)
   {
   printf("createTH : error - length <= 0\n");
   exit(-1);
   }
pTable = (pTH) mbkalloc (sizeof (struct tableTH));
pTable->length=len;

pEl = (pElemTH) mbkalloc (len * (sizeof(struct elemTH)));
pTable->pElem = pEl; 
for (i=0;i<len;i++)
    {
    pEl->key = NULL;
    pEl->value = EMPTYTH;
    pEl++;
    }
pTable->count=0;
return(pTable);
}

   /* destruction d'une table de hachage */

void destroyTH(pTable)
pTH pTable;
{
pElemTH pEl;

pEl = pTable->pElem; 
mbkfree(pEl);
mbkfree(pTable);
}

  /* recherche d'un element dans la table
     renvoie -1 si la recherche echoue. */


int searchTH(pTable,key)
pTH pTable;
char *key;
{
int co = 0;
int indice = 0;
pElemTH pEl;

indice=hashTH(key) % pTable->length;
do
   {
   if (co++ > MAX_CALLS) 
      {
      reAllocTH(pTable); 
      return(searchTH(pTable,key));
      }

   pEl=(pTable->pElem)+indice;
   if (pEl->value != EMPTYTH && pEl->value != DELETETH)
      {
      if ((int) key == (int) pEl->key)
         return(pEl->value);
      }
   else
      if (pEl->value == EMPTYTH)
         return(EMPTYTH);
   indice = (indice + 1) % pTable->length;
   }
while(1);
}


 /* ajout d'un element a la table */

int addTH(pTable,key,value)
pTH pTable;
char *key;
int value;
{
int indice = 0;
pElemTH pEl;
int co =0;

if (value == EMPTYTH || value == DELETETH)
   {
   printf("addTH : error - value is EMPTYTH or DELETETH\n");
   exit(-1);
   }
if (pTable->count++ > (pTable->length) * 8/10)
   {
   reAllocTH(pTable);
   return(addTH(pTable,key,value));
   }

indice=hashTH(key) % pTable->length;
do
   {
   if (co++ > MAX_CALLS)
      {
      reAllocTH(pTable);
      return(addTH(pTable,key,value));
      }
   pEl=(pTable->pElem)+indice;
   if (pEl->value == EMPTYTH || pEl->value == DELETETH)
      {
      pEl->value = value;
      pEl->key= key;
      return(value);
      }
   else
      if ((int) pEl->key == (int) key)
         {
         pTable->count--;
         pEl->value = value;
         return(value);
         }
         
   indice = (indice + 1) % pTable->length;
  }
while (1);
}

 /* test d'existence et ajout d'un element a la table */

int addExistTH(pTable,key,value)
pTH pTable;
char *key;
int value;
{
int indice = 0;
pElemTH pEl;
int co =0;

if (value == EMPTYTH || value == DELETETH)
   {
   printf("addExistTH : error - value is EMPTYTH or DELETETH\n");
   exit(-1);
   }
if (pTable->count++ > (pTable->length) * 8/10)
   {
   reAllocTH(pTable);
   return(addExistTH(pTable,key,value));
   }

indice=hashTH(key) % pTable->length;
do
   {
   if (co++ > MAX_CALLS)
      {
      reAllocTH(pTable);
      return(addExistTH(pTable,key,value));
      }
   pEl=(pTable->pElem)+indice;
   if (pEl->value == EMPTYTH || pEl->value == DELETETH)
      {
      pEl->value = value;
      pEl->key= key;
      return(0);
      }
   else
      if ((int) pEl->key == (int) key)
         {
         pTable->count--;
         pEl->value = value;
         return(1);
         }
         
   indice = (indice + 1) % pTable->length;
  }
while (1);
}




   /* elimination d'un element de la table */


int deleteTH(pTable,key)
pTH pTable;
char *key;
{
int indice =0;
pElemTH pEl;
int co = 0;

indice=hashTH(key) % pTable->length;
do
   {
   if (co++ > MAX_CALLS)
      {
      reAllocTH(pTable);
      return(deleteTH(pTable,key));
      }
   pEl=(pTable->pElem)+indice;
   if (pEl->value != EMPTYTH && pEl->value != DELETETH)
      {
      if ((int) key == (int) pEl->key)
         {
         pTable->count--;
         pEl->value = DELETETH;
         return(pEl->value);
         }
      }
   else
      if (pEl->value==EMPTYTH)
         return(EMPTYTH);
   indice = (indice + 1) % pTable->length;
   }
while (1);   /* on sort quand on arrive sur EMPTYTH */
}


/* affichage des elements de la table */

void displayTH(pTable)
pTH pTable;
{
int i;
pElemTH pEl;
pEl=pTable->pElem; 
printf("================== DISPLAYTH ================\n");
printf("length = %d\t		count = %d\n",pTable->length,pTable->count);
printf("=============================================\n");
for (i=0;i<pTable->length;i++)
    {
    if (pEl->value != EMPTYTH && pEl->value !=DELETETH)
       {
       printf("index  %d\t",i);
       printf("key    %s\t",pEl->key);
       printf("value  %d \n",pEl->value);
       }
    pEl++;
    }
}

/********** reallocation table d'entiers **************/

void reAllocTH(pTable)
pTH pTable ;
{
pTH tabBis ;
pElemTH pEl ;
int i ;

pEl = pTable->pElem ;
tabBis = createTH((pTable->length) * 5) ;
for(i = 0;i < pTable->length ; i++)
     	{
     	if(pEl->value != EMPTYTH && pEl->value != DELETETH)
		addTH(tabBis,pEl->key,pEl->value) ;
	pEl++ ;
	}
mbkfree(pTable->pElem);
pTable->length = tabBis->length;
pTable->pElem = tabBis->pElem; 
pTable->count = tabBis->count; 
mbkfree(tabBis);
}
