`#include <stdlib.h>
#include <stdbool.h>
#include<string.h>
#include<stdio.h>
#include <assert.h>
#include <stdint.h>

#define FNV_OFFSET 14695981039346656037UL
#define FNV_PRIME 1099511628211UL

uint64_t hash_key(char* key){
    uint64_t hash=FNV_OFFSET;
    for (char* p =key; *p!='\0'; p++){
        hash=hash^(uint64_t)(*p);//on fait un xor avec la valeur du caractère.
        hash=hash*FNV_PRIME;
    }
    return hash;
}

struct hashtbl {
    char** table;
    int capacity;
    int taille;
};

typedef struct hashtbl hashtbl;


hashtbl* create_ht(int capacity){

    hashtbl* res = malloc(sizeof(hashtbl));
    res->table = malloc(capacity*sizeof(char*));
    for (int i = 0; i< capacity;i++){
        res->table[i]=NULL;
    } 
    res->capacity=capacity;
    res->taille=0;
    return res;
}

void destroy_ht(hashtbl* t){
    free(t->table);
    free(t);
}

bool appar_th(hashtbl* t, char* s){
    int n = hash_key(s) %(t->capacity);
    while(strcmp(t->table[n],s)!=0 && t->table[n]!=NULL){
        n=(n+1)%(t->capacity);
    }
    return(t->table[n]);


}

void insert_ht_ssalloc(char** new_tab,int capacity, char* s){
    int n = hash_key(s)%capacity;
    while(new_tab[n]!=NULL){
        if (strcmp(new_tab[n],s)==0) return;
        n=(n+1)%capacity;
    }
    new_tab[n]=s;
}

void realloc_ht(hashtbl* t){
    int old_cap=t->capacity;
    int new_cap=2*t->capacity;
    char** new_tab = malloc(new_cap*sizeof(char*));
    for (int i=0;i<new_cap;i++){
        new_tab[i]=NULL;
    }
    
    for (int i=0;i<old_cap;i++){
        if (t->table[i]!=NULL){
            insert_ht_ssalloc(new_tab,new_cap,t->table[i]);
        }
    }
    char** old_tab=t->table;
    t->table=new_tab;
    t->capacity=new_cap;
    free(old_tab);
}


void insert_ht(hashtbl* t, char* s){
    if(t->capacity==2*t->taille){
        realloc_ht(t); printf("reallocation effectuee\n");
    }

    t->taille++;
    insert_ht_ssalloc(t->table,t->capacity,s);
}

void print_ht(hashtbl* t){
    int cap = t->capacity;
    char** table=t->table;
    for (int i =0;i<cap;i++){
        if(table[i]!=NULL){
            printf("%d %s %d\n", i, table[i], (int)(hash_key(table[i])%cap));
        }
        else{
            printf("%d\n", i);
        }

    }
}

void delete_ht(hashtbl* t, char*s){
    int case_hash = hash_key(s)%t->capacity;
    int case_reelle=case_hash;
    //on commence par chercher l'élément à supprimer
    while(t->table[case_reelle]!=NULL && strcmp(t->table[case_reelle],s)!=0){
        case_reelle=(case_reelle+1)%t->capacity;
    }
    assert(t->table[case_reelle]!=NULL);
    //on cherche les elements qui ne seraient plus accessibles apres la suppression à cause de l'apparition du trou
    int curr = (case_reelle+1)%t->capacity;
    int hole = case_reelle;
    while(t->table[curr]!=NULL){//on avance jusqu'au prochain trou
        int hash = (hash_key(t->table[curr]))%t->capacity;
        //si de la valeur hachée à la valeur courante on passe par le trou
        if ((hash<=hole && hole<curr)||(hash<=hole && curr < hash)||( curr<hash && hole < curr)){
            //alors on déplace le trou
            //printf("on deplace %d->%d\n",curr,hole);
            t->table[hole]=t->table[curr];
            hole=curr;
        }
        curr=(curr+1)%t->capacity;

    }
    t->table[hole]=NULL;
    t->taille--;


}
int main(){

    hashtbl* hash_tab = create_ht(2);
    char* test[]={"", "il", "en", "faut", "peu", "pour", "etre" , "heureux"};
    for (int i=0;i<8;i++){
        insert_ht(hash_tab,test[i]);
       // print_ht(hash_tab);

    }

    for (int i=0;i<8;i++){
        delete_ht(hash_tab,test[i]);
        //print_ht(hash_tab);

    }

    for (int i=0;i<8;i++){
        insert_ht(hash_tab,test[i]);

    }

    delete_ht(hash_tab, "faut");
    print_ht(hash_tab);
    destroy_ht(hash_tab);
    return 0;
}