hash_table.c

#include <stdio.h>
#include <stdint.h>
#include <stdlib.h>
#include <string.h>

struct linked_list {
    void *data;
    struct linked_list *next;
};

struct linked_list_base {
    struct linked_list *head;
    struct linked_list *tail;
};

struct hash_table {
    struct linked_list_base **table;
    int n_items;
};

struct hash_table *table;

uint32_t hash_djb(uint8_t *buf, size_t bufsize)
{
    unsigned int hash = 5381;
    unsigned int i = 0;

    for (i = 0; i < bufsize; i ++) {
        hash = ((hash << 5) + hash) + buf[i];
    }
    return hash;
}

int hash_table_init(int items)
{
    table = calloc(1, sizeof(struct hash_table));
    if (!table) {
        return -1;
    }

    table->table = calloc(items, sizeof(struct linked_list_base));
    if (!table->table) {
        return -1;
    }

    int i;

    for (i = 0; i < items; i ++) {
        table->table[i] = calloc(1, sizeof(struct linked_list_base));
        if (!table->table[i]) {
            return -1;
        }
    }
    table->n_items = items;
    return 0;
}

int hash_table_add_item(void *item, uint32_t hash)
{
    struct linked_list *node;
    int hash_val;

    hash_val = hash % table->n_items;

    printf("item %p hash_val %d\n", item, hash_val);
    node = calloc(1, sizeof(struct linked_list));
    if (!node) {
        return -1;
    }

    node->data = item;

    if (table->table[hash_val]->tail) {
        table->table[hash_val]->tail->next = node;
        table->table[hash_val]->tail = node;
    } else {
        table->table[hash_val]->head = node;
        table->table[hash_val]->tail = node;
    }
    return 0;
}

void *hash_table_find_item(void *item, uint32_t hash)
{
    struct linked_list *node;
    int hash_val;
    int iterations = 0;

    hash_val = hash % table->n_items;

    for (node = table->table[hash_val]->head; node != NULL; node = node->next) {
        iterations ++;
        if (node->data == item) {
            printf("took %d iterations to find\n", iterations);
            return item;
        }
    }
    return NULL;
}

void hash_table_dump(void (*callback)(void *data, int table_index))
{
    int i ;

    for (i = 0; i < table->n_items; i ++) {
        struct linked_list *node;

        for (node = table->table[i]->head; node != NULL; node = node->next) {
            callback(node->data, i);
        }
    }
}

void hash_table_free()
{
    int i;

    for (i = 0; i < table->n_items; i ++) {
        struct linked_list *cur, *follow;

        cur = table->table[i]->head;

        while (cur) {
            follow = cur;
            cur = cur->next;
            free(follow);
        }

        free(table->table[i]);
    }
    free(table->table);
    free(table);
}

void print_items(void *data, int index)
{
    printf("entry item [%s] in hash table index [%d]\n", (char *)data, index);
}

int main()
{
    hash_table_init(20);
    char *items[] = {"house", "shoes", "clothes", "bucket", "beds", "computer"};
    size_t i ;

    for (i = 0; i < sizeof(items) / sizeof(items[0]); i ++) {
        uint32_t hash = hash_djb(items[i], strlen(items[i]));

        hash_table_add_item(items[i], hash);
    }

    hash_table_dump(print_items);

    void *item = hash_table_find_item(items[1], hash_djb(items[1], strlen(items[1])));

    printf("found item ? %p\n", item);

    char *search_key = "keys";

    item = hash_table_find_item(search_key, hash_djb(search_key, strlen(search_key)));

    printf("found item ? %p\n", item);

    hash_table_free();
}