#include <stdio.h>
#include <stdint.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
 
typedef uint8_t u08;
typedef uint32_t u32;
typedef uint64_t u64;
typedef int32_t i32;
typedef float f32;
typedef double f64;
 
// PRIME NUMBERS
i32 is_prime(const i32 x) {
    if (x < 2) { return -1; }
    if (x < 4) { return 1; }
    if ((x % 2) == 0) { return 0; }
    for (i32 i = 3; i <= floor(sqrt((f64) x)); i+= 2) {
        if ((x % i) == 0) {
            return 0;
        }
    }
    return 1;
}
 
i32 next_prime(i32 x) {
    while (is_prime(x) != 1) {
        x++;
    }
    return x;
} 
 
// FNV-1a hashing function
u64 hash_id(const char * id) {
    u64 hash = 0xcbf29ce484222325; // FNV_offset_basis: 14695981039346656037
    while (*id) hash = (hash ^ (u08)*id++) * 0x100000001b3; // FNV_prime: 1099511628211
    return hash;   
}
  
 
 
// key: string, value: i32
typedef struct _ht_i32_item_t {
    char * id;
    i32 data;
    struct _ht_i32_item_t * next; // linked list
} ht_i32_item_t;
 
ht_i32_item_t * ht_mk_i32_item(char * id, i32 data) {
    ht_i32_item_t * i = calloc(1, sizeof(ht_i32_item_t));
    i -> id = strdup(id);
    i -> data = data;
    i -> next = NULL;
    return i;
}
 
 
typedef struct {
    ht_i32_item_t ** e; // elements
    u64 used;
    u64 sz;
} ht_i32_t;
 
// Declarations
void ht_i32_mk(ht_i32_t * table, u64 sz);
void ht_i32_resize(ht_i32_t * table);
void ht_i32_add(ht_i32_t * table, char * id, i32 data);
i32 ht_i32_get(ht_i32_t * table, char * id);
void ht_i32_rm(ht_i32_t * table);
 
// Implementation
void ht_i32_mk(ht_i32_t * table, u64 sz) {
    // prime numbers
    table -> sz = next_prime(sz);
    table -> e = calloc(table -> sz, sizeof(ht_i32_item_t));
    table -> used = 0;
}
 
 
u32 collisions = 0;
 

void ht_i32_add(ht_i32_t * table, char * id, i32 data) {
    ht_i32_item_t * i = ht_mk_i32_item(id, data);
 
    ht_i32_resize(table);
 
    u64 idx = hash_id(id) % table -> sz;
 
    // Scenario 1: NULL -> current = i
    if (!table -> e[idx]) {
        table -> e[idx] = i;
        table -> used++;
        return;
    }
 
    // Scenario 2 + 3: Key exists or True Collision
    ht_i32_item_t * current = table -> e[idx];
    while (current -> next && strcmp(id, current -> id)) {
        current = current -> next;
    }
    if (!strcmp(id, current -> id)) {
        free(table -> e[idx]);
        table -> e[idx] = i; 
        return;
    }
    collisions++;
    current -> next = i;
    table -> used++;
    return;
}
 
#define LOAD_FACTOR 0.75
void ht_i32_resize(ht_i32_t * table) {
    if ((f32) table -> used / table -> sz > LOAD_FACTOR) {
        ht_i32_t * n = calloc(1, sizeof(ht_i32_t));
        ht_i32_mk(n, table -> sz * 3.5);
        for (u64 u = 0; u < table -> sz; u++) {
            ht_i32_item_t * current = table -> e[u];
            while (current){
                ht_i32_add(n, current -> id, current -> data);
                current = current -> next;
            }
        }
        ht_i32_rm(table);
        table -> e = n -> e;
        table -> sz = n -> sz;
        table -> used = n -> used;
    }
}
 
 
i32 ht_i32_get(ht_i32_t * table, char * id) {
    u64 idx = hash_id(id) % table -> sz; 
    
    // 1: return current_item;
    // 2: return traverse(list, id);
    ht_i32_item_t * current = table -> e[idx];  
    while (current) {
        if (!strcmp(id, current -> id)) {
            return current -> data;
        }
        current = current -> next;
    }
    return INT32_MAX;
}
 
void ht_i32_rm(ht_i32_t * table) {
    free(table -> e);
    table -> e = NULL;
    table -> sz = 0;
    table -> used = 0;
}
 
 
// Copied from some StackOverflow thread
static char *rand_string(char *str, size_t size)
{
    const char charset[] = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ";
    if (size) {
        --size;
        for (size_t n = 0; n < size; n++) {
            int key = rand() % (int) (sizeof charset - 1);
            str[n] = charset[key];
        }
        str[size] = '\0';
    }
    return str;
}
 
i32 main() {
    ht_i32_t table;
    ht_i32_mk(&table, 200); 
 
 
    char * str = calloc(24, sizeof(char));
    for (i32 u = 0; u < 1e4; u++) {
        str = rand_string(str, 20);
        ht_i32_add(&table, str, u);
    }
    ht_i32_add(&table, rand_string(str, 20),100);
 
    // ht_get
    u32 storage = 0;
    printf("%u\n", table.used);
    for (u32 u = 0; u < table.sz; u++) {
        ht_i32_item_t * current = table.e[u];
        while (current) {
            storage++;
            current = current -> next;
        }
    }
    printf("Retrieved: %u, Collisions: %u\n", storage, collisions);
 
    ht_i32_rm(&table);
    return 0;
}