#include <stdlib.h>
#include <stdbool.h>
#include<string.h>
#include<stdio.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(t->table[n]!=NULL && strcmp(t->table[n],s)!=0){
        n=(n+1)%(t->capacity);
    }
    return (t->table[n]!=NULL); //on peut se contenter de return(t->table[n]);
        


}

void insert_ht(hashtbl* t, char* s){
    if (t->taille==0.5*t->capacity){
        char** new_table = malloc(2*t->capacity*sizeof(char*));
        for (int i = 0; i< 2*t->capacity;i++){
        new_table[i]=NULL;
    }
        char** table= t->table;
        t->table= new_table;
        t->taille=0;
        int n = t->capacity;
        t->capacity=2*n;
        for (int i=0;i<n;i++){
            if (table[i]!=NULL){
                insert_ht(t,table[i]);
            }
        }
        free(table);
    }
    int n = hash_key(s)%t->capacity;
    while(t->table[n]!=NULL){
        if (strcmp(t->table[n],s)==0) return;
        n=(n+1)%t->capacity;
    }
    t->table[n]=s;
    t->taille++;
}

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);
        }

    }
}

int main(){

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

    }
    if (appar_th(hash_tab,"vraiment")){printf("oui vraiment");} else printf("non");
    destroy_ht(hash_tab);
    return 0;
}