#ifndef HASHTABLE_H
#define HASHTABLE_H

typedef struct {
    void **table;
    unsigned int n_items;
    unsigned int n_buckets;
    unsigned int next_resize;
} Hashtable_Data_t;

typedef struct {
    Hashtable_Data_t *data; // should not be stack allocated
    unsigned int (*hashcode)(void *);
    #ifndef NO_HASH_EQUALS
    unsigned int (*equals)(void *, void *);
    #endif
} Hashtable_t;

// buckets must be > 3
Hashtable_t *table_create(Hashtable_t *ht, unsigned int (*hashcode)(void *),
    #ifndef NO_HASH_EQUALS
    unsigned int (*equals)(void *, void *),
    #endif
    unsigned int initial_buckets);


int table_insert(Hashtable_t *ht, void *item);

int table_insert_fast(Hashtable_t *ht, void *item);

int table_contains(Hashtable_t *ht, void *item);

int table_remove(Hashtable_t *ht, void *item);

void table_free(Hashtable_t *ht);

#endif /* HASHTABLE_H */

#include <stdlib.h>
#include "hashtable.h"

static int rehash(Hashtable_t *);
inline static void internal_table_insert(Hashtable_t *ht, Hashtable_Data_t *data, void *item);
inline static unsigned int internal_hashpos(Hashtable_t *ht, Hashtable_Data_t *data, void *item);

Hashtable_t *table_create(Hashtable_t *ht, unsigned int (*hashcode)(void *),
    #ifndef NO_HASH_EQUALS
    unsigned int (*equals)(void *, void *),
    #endif
    unsigned int buckets) {
    Hashtable_t *ht_local;

    if(ht == NULL) {
        ht_local = (Hashtable_t *) malloc(sizeof(Hashtable_t));
        if(ht_local == NULL)
            return NULL;
    } else {
        ht_local = ht;
    }

    ht_local->data = (Hashtable_Data_t *) malloc(sizeof(Hashtable_Data_t));

    if(ht_local->data == NULL) {
        if(ht == NULL)
            free(ht_local);

        return NULL;
    }

    ht_local->data->table = calloc(buckets, sizeof(void *));

    if(ht_local->data->table == NULL) {
        if(ht == NULL) {
            free(ht_local->data);
            free(ht_local);
        }

        return NULL;
    }
    ht_local->hashcode = hashcode;
    #ifndef NO_HASH_EQUALS
    ht_local->equals = equals;
    #endif

    ht_local->data->n_items = 0;
    ht_local->data->n_buckets = buckets;
    ht_local->data->next_resize = (buckets >> 1) + (buckets >> 2);

    return ht_local;
}

// returns -1 on failure, 0 if no failure.
static int rehash(Hashtable_t *ht) {
    Hashtable_Data_t *new_data = (Hashtable_Data_t *) malloc(sizeof(Hashtable_Data_t));

    if(new_data == NULL)
        return -1;

    new_data->n_buckets = ht->data->n_buckets << 1;
    new_data->table = calloc(new_data->n_buckets, sizeof(void *));

    if(new_data->table == NULL) {
        free(new_data);
        return -1;
    }

    // 1.5 of old data so 75% of new bucket size. (75% load factor)
    new_data->next_resize = ht->data->n_buckets + (ht->data->n_buckets >> 1);

    unsigned int a;
    for(a=0; a<ht->data->n_buckets; a++)
        if(ht->data->table[a] != NULL)
            internal_table_insert(ht, new_data, ht->data->table[a]);

    free(ht->data->table);
    free(ht->data);
    ht->data = new_data;

    return 0;
}

inline static unsigned int internal_hashpos(Hashtable_t *ht, Hashtable_Data_t *data, void *item) {
    return ht->hashcode(item)%data->n_buckets;
}

// returns NULL for no entry, &item if item is in table, and table[a] ifndef NO_HASH_EQUALS && ht->equals returned 1
inline static void *internal_table_nexthit(Hashtable_t *ht, void *item) {
    unsigned int hashcode = internal_hashpos(ht, ht->data, item);

    unsigned int a, lim;

    a = hashcode;
    lim = ht->data->n_buckets;
    for(;;) {
        if(ht->data->table[a] == NULL || ht->data->table[a] == item
        #ifndef NO_HASH_EQUALS
        || ht->equals(ht->data->table[a], item)
        #endif
            ) return ht->data->table[a];

        a++;
        if(a == lim) {
            if(lim != hashcode) {
                a = 0;
                lim = hashcode;
            }/* else {
                return;
                // table will never be full, so returning here is unneccessary.
            }*/
        }
    }
}

// uses table Hashtable_t for function pointers.
// optimized for just inserting, use internal_table_nexthit if
// you want to see if table contains, and then insert.
inline static void internal_table_insert(Hashtable_t *ht, Hashtable_Data_t *data, void *item) {
    unsigned int hashcode = internal_hashpos(ht, data, item);

    unsigned int a, lim;

    a = hashcode;
    lim = data->n_buckets;
    for(;;) {
        if(data->table[a] == NULL) {
            data->table[a] = item;
            return;
        }

        a++;
        if(a == lim) {
            if(lim != hashcode) {
                a = 0;
                lim = hashcode;
            }/* else {
                return;
                // table will never be full, so returning here is unneccessary.
            }*/
        }
    }
}

int table_insert(Hashtable_t *ht, void *item) {
    unsigned int tmp = ht->data->n_items+1;
    if(tmp > ht->data->next_resize)
        if(rehash(ht) == -1) return -1;

    internal_table_insert(ht, ht->data, item);

    ht->data->n_items = tmp;
    return 0;
}

// up to caller to free table if not stack allocated
void table_free(Hashtable_t *ht) {
    free(ht->data->table);
    free(ht->data);
}
#include <stdlib.h>
#include <stdio.h>
#include "hashtable.h"
#define NULLCHK(ptr) if(ptr == NULL) memoryerror()

unsigned int hashcode(void *);
unsigned int equals(void *, void *);
void memoryerror(void);
void disptable(Hashtable_t *);

int main(void) {
    int items[] = {
        5123,
        1283,
        1235,
        634,
        12356,
        12356,
        534,
        654,
    };
    size_t itemsize = sizeof(items)/sizeof(items[0]);
    Hashtable_t *ht = table_create(NULL, hashcode, equals, (itemsize << 1)-(itemsize >> 1));
    NULLCHK(ht);

    unsigned int a;
    for(a=0; a<itemsize; a++) {
        if(table_insert(ht, items+a) == -1) memoryerror();
    }

    disptable(ht);
}

void disptable(Hashtable_t *ht) {
    printf("items: %u\nbuckets: %u\n", ht->data->n_items, ht->data->n_buckets);
    unsigned int a;
    for(a=0; a<ht->data->n_buckets; a++) {
        void *item = ht->data->table[a];
        if(item != NULL) {
            printf("[%d] %d\n", a, *((int *)item));
        }
    }
}

void memoryerror() {
    puts("Memory error.");
    exit(1);
}

unsigned int hashcode(void *item) {
    return *((int *)item);
}

unsigned int equals(void *item1, void *item2) {
    return 0;
}