#include <stdlib.h>
#include <string.h>
#include "etc.h"

#define SIZE_HASHELM (sizeof(HASHELM)+ctl->sizdata-1)
/*
	Initialisation du table de controle hashing
	Retourne -1 si erreur (manque de mémoire)
*/
export int hash_init (
	HASHCTL *ctl,
	int minelm,		/* Portion d'allocation pour table */
	int sizdata,	/* Dimension du data à préserver avec la clé */
	int quit)		/* Termine si erreur d'allocation ? */
{
	int ret = -1;
	ctl->maxelm = ctl->nbelm = 0;
	ctl->minelm = minelm;
	size_align(sizeof(HASHELM)-1+sizdata,sizdata);
	ctl->sizdata = sizdata;
	ctl->nbindx = 256;
	ctl->freeelm = -1;
	ctl->index = (int*)malloc_err (256*sizeof(int),quit);
	if (ctl->index != NULL){
		memset (ctl->index,-1,256*sizeof(int));
		ctl->elms = (HASHELM*) malloc_err (minelm*SIZE_HASHELM,quit);
		if (ctl->elms != NULL){
			ctl->maxelm = minelm;
			ret = 0;
		}else{
			free (ctl->index);
			ctl->index = NULL;
		}
	}
	return ret;
}
/*
	Retourne un pointeur vers l'item noitem de la table
	La dimensions des items dépend de sizdata
*/
static HASHELM * near hash_item (HASHCTL *ctl, int noitem)
{
	return (HASHELM*)((char*)ctl->elms + noitem*SIZE_HASHELM);
}
/*
	Libère espace associé à un système de hashing
*/
export void hash_end (HASHCTL *ctl)
{
	int i;
	for (i=0; i<ctl->nbelm; i++){
		HASHELM *elm = hash_item (ctl,i);
		free ((void*)elm->str);
	}
	ctl->nbelm = ctl->maxelm = 0;
	ctl->nbindx = 0;
	free (ctl->elms);
	ctl->elms = NULL;
	free (ctl->index);
	ctl->index = NULL;
}

/*
	Calcul l'index d'accès d'une clé
*/
static int near hash_eval (const char *pt)
{
	int hash = 0;
	while (*pt != '\0'){
		hash = (hash << 1) ^ *pt;
		pt++;
	}
	return hash & 0xff;
}


/*
	Localise information associé à une chaine
	Retourne NULL si ne trouve pas
*/
export HASHELM *hash_find (HASHCTL *ctl, const char *str)
{
	HASHELM *ret = NULL;
	int item = ctl->index[hash_eval(str)];
	while (item != -1){
		HASHELM *elm = hash_item (ctl,item);
		if (strcmp(str,elm->str)==0){
			ret = elm;
			break;
		}else{
			item = elm->next;
		}
	}
	return ret;
}

/*
	Elimine un élément de la table hashing
	Retourne -1 si la chaine ne faisait pas partie de la liste
*/
export int hash_remove (HASHCTL *ctl, const char *str)
{
	int ret = -1;
	int *prec = &ctl->index[hash_eval(str)];
	int item = *prec;
	while (item != -1){
		HASHELM *elm = hash_item (ctl,item);
		if (strcmp(str,elm->str)==0){
			*prec = elm->next;
			free ((void*)elm->str);
			elm->str = NULL;
			elm->next = ctl->freeelm;
			ctl->freeelm = item;
			ret = 0;
			break;
		}else{
			prec = &elm->next;
			item = *prec;
		}
	}
	return ret;
}
/*
	Ajoute un élément dans la table hashing
	La chaine est duplicaté par strdup_err
	Le data sera copié (selon la longueur spécifié à hash_init()).
	Retourne -1 si pas de place pour ajouter
*/
export int hash_add (HASHCTL *ctl, const char *str, void *data, int quit)
{
	int ret = -1;
	int noelm = -1;
	if (ctl->freeelm != -1){
		HASHELM *elm = hash_item (ctl,ctl->freeelm);
		noelm = ctl->freeelm;
		ctl->freeelm = elm->next;
	}else if (ctl->nbelm == ctl->maxelm){
		int maxelm = ctl->maxelm + ctl->minelm;
		HASHELM *elms = (HASHELM*) realloc_err (ctl->elms
			,maxelm*SIZE_HASHELM,quit);
		if (elms != NULL && data != NULL){
			ctl->elms = elms;
			ctl->maxelm = maxelm;
			noelm = ctl->nbelm;
		}
	}else{
		noelm = ctl->nbelm;
	}
	if (noelm != -1){
		HASHELM *elm = hash_item (ctl,noelm);
		elm->str = strdup_err (str,quit);
		if (elm->str != NULL){
			int item = hash_eval(str);
			memmove (elm->data,data,ctl->sizdata);
			elm->next = ctl->index[item];
			ctl->index[item] = noelm;
			if (noelm == ctl->nbelm) ctl->nbelm++;
			ret = 0;
		}
	}
	return ret;
}

/*
	Elimine tous les éléments d'un index hashing
*/
export void hash_reset (
	HASHCTL *ctl,
	void (*fctfree)(HASHELM *elm))		/* Appelée pour chaque item usager */
										/* Cette fonction fait des free() */
{
	int i;
	for (i=0; i<ctl->nbelm; i++){
		HASHELM *elm = hash_item (ctl,i);
		if (elm->str != NULL) (*fctfree) (elm);
	}
	memset (ctl->index,-1,256*sizeof(int));
	ctl->freeelm = -1;
	ctl->nbelm = 0;
}

#ifdef TEST

static void near testget (HASHCTL *ctl, int nb)
{
	int i;
	for (i=0; i<nb; i++){
		char buf[100];
		HASHELM *elm ;
		sprintf (buf,"allo%d",i);
		elm = hash_find (ctl,buf);
		if (elm != NULL && strcmp(buf,elm->str)==0){
			printf ("%s == %s : %d\n",buf,elm->str,*(int*)elm->data);
		}else{
			printf ("%s : ************* Trouve pas (%p)\n",buf,elm);
		}
	}
}


void main (void)
{
	HASHCTL ctl;
	if (hash_init (&ctl,10,sizeof(int),1)!=-1){
		int i;
		for (i=0; i<50; i++){
			char buf[100];
			sprintf (buf,"allo%d",i);
			if (hash_add (&ctl,buf,&i,1) != -1){
				printf ("Ajoute %s ok\n",buf);
			}else{
				printf ("Ajoute %s ********** Pas ok\n",buf);
			}
		}
		testget(&ctl,50);
		for (i=0; i<50; i += 10){
			char buf[100];
			sprintf (buf,"allo%d",i);
			hash_remove (&ctl,buf);
		}
		testget(&ctl,50);
		for (i=0; i<50; i += 10){
			char buf[100];
			int tmp = i*100;
			sprintf (buf,"allo%d",i);
			hash_add (&ctl,buf,&tmp,1);
		}
		testget(&ctl,50);
		hash_end (&ctl);
	}
}

#endif