hashmap.c

#include "hashmap.h"
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>
#include <stdbool.h>

#define BINS 33703

uint32_t hash_key(uint32_t val)
{
    return (val * 2654435761) % BINS;
}


/* first, make a hashmap that's just a linked list of key, value pairs */

struct LinkedListNode;

typedef struct LinkedListNode LinkedListNode;

struct LinkedListNode
{
    uint32_t key;
    void *value;
    LinkedListNode *next;
};

typedef struct ListHashmap
{
    LinkedListNode *head;
} ListHashmap;

LinkedListNode *LinkedListNode_init(uint32_t key, void *value, LinkedListNode *next)
{
    LinkedListNode *lln = malloc(sizeof(LinkedListNode));
    assert(lln);
    lln->key = key;
    lln->value = value;
    lln->next = next;
    return lln;
}

void LinkedListNode_free(LinkedListNode *lln)
{
    free(lln);
}

void ListHashmap_init(ListHashmap *lh)
{
    lh->head = NULL;
}

void ListHashmap_deinit(ListHashmap *lh)
{
    LinkedListNode *pos = lh->head;
    while (pos)
    {
        LinkedListNode *next = pos->next;
        LinkedListNode_free(pos);
        pos = next;
    }
}

void ListHashmap_update(ListHashmap *lh, uint32_t key, void *value)
{
    LinkedListNode *pos = lh->head;
    LinkedListNode *prev = NULL;

    while (pos)
    {
        if (pos->key == key)
        {
            pos->value = value;
            return;
        }

        prev = pos;
        pos = pos->next;
    }

    /* must make a new pair */

    LinkedListNode *new = LinkedListNode_init(key, value, NULL);

    if (prev)
        prev->next = new;
    else
        lh->head = new;
}

bool ListHashmap_contains(ListHashmap *lh, uint32_t key)
{
    LinkedListNode *pos = lh->head;
    
    while (pos)
    {
        if (pos->key == key) return true;

        pos = pos->next;
    }

    return false;
}

void *ListHashmap_get(ListHashmap *lh, uint32_t key)
{
    LinkedListNode *pos = lh->head;
    
    while (pos)
    {
        if (pos->key == key) return pos->value;

        pos = pos->next;
    }

    assert(false);
}

void ListHashmap_delete(ListHashmap *lh, uint32_t key)
{
    assert(ListHashmap_contains(lh, key));

    if (lh->head->key == key)
    {
        LinkedListNode *next = lh->head->next;
        LinkedListNode_free(lh->head);
        lh->head = next;
    }
    else
    {
        LinkedListNode *pos = lh->head->next;
        LinkedListNode *prev = lh->head;

        while (pos)
        {
            if (pos->key == key)
            {
                prev->next = pos->next;
                LinkedListNode_free(pos);
                return;
            }

            prev = pos;
            pos = pos->next;
        }
    }
}

void ListHashmap_printPairs(ListHashmap *lh)
{
    LinkedListNode *pos = lh->head;

    while (pos)
    {
        uint32_t key = pos->key;
        int *ptr = ListHashmap_get(lh, key);
        printf("(%d, %d)\n", key, *ptr);
        pos = pos->next;
    }
}

struct Hashmap
{
    ListHashmap bins[BINS];
};

Hashmap *Hashmap_init()
{
    Hashmap *hm = malloc(sizeof(Hashmap));
    assert(hm);
    for (size_t i = 0; i < BINS; i++)
    {
        ListHashmap_init(&hm->bins[i]);
    }
    return hm;
}

void Hashmap_free(Hashmap *hm)
{
    for (size_t i = 0; i < BINS; i++)
    {
        ListHashmap_deinit(&hm->bins[i]);
    }
    free(hm);
}

void Hashmap_update(Hashmap *hm, uint32_t key, void *value)
{
    uint32_t hash = hash_key(key);
    ListHashmap_update(&hm->bins[hash], key, value);
}

bool Hashmap_contains(Hashmap *hm, uint32_t key)
{
    uint32_t hash = hash_key(key);
    return ListHashmap_contains(&hm->bins[hash], key);
}

void *Hashmap_get(Hashmap *hm, uint32_t key)
{
    uint32_t hash = hash_key(key);
    return ListHashmap_get(&hm->bins[hash], key);
}

void Hashmap_delete(Hashmap *hm, uint32_t key)
{
    uint32_t hash = hash_key(key);
    ListHashmap_delete(&hm->bins[hash], key);
}