ht.c

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

#include "ht.h"

#define RETURN_IF_NULL(p) \
    if (p == NULL)        \
        return NULL;

size_t hash(const char *key)
{
    size_t val = 0, i, key_length = strlen(key);

    for (i = 0; i < key_length; ++i)
        val = val * 37 + key[i];

    /* value must be between 0 <= val < TABLE_SIZE */
    val %= TABLE_SIZE;

    return val;
}

Entry *ht_pair(const char *key, const char *val)
{
    /* allocate the entry */
    Entry *entry = malloc(sizeof(Entry) * 1);

    RETURN_IF_NULL(entry);

    entry->key = malloc(strlen(key) + 1);
    entry->val = malloc(strlen(val) + 1);

    /* copy the key and value in place */
    strcpy(entry->key, key);
    strcpy(entry->val, val);

    /* next starts out null but may be set later on */
    entry->next = NULL;

    return entry;
}

HT *ht_init(void)
{
    /* allocate table */
    HT *ht = malloc(sizeof(HT) * 1);

    RETURN_IF_NULL(ht);

    /* allocate table entries */
    ht->entries = malloc(sizeof(Entry *) * TABLE_SIZE);

    /* set each to null (needed for proper operation) */
    size_t i;
    for (i = 0; i < TABLE_SIZE; ++i)
        ht->entries[i] = NULL;

    return ht;
}

void ht_set(HT *ht, const char *key, const char *val)
{
    size_t slot = hash(key);

    /* try to look up an entry set */
    Entry *entry = ht->entries[slot];

    /* no entry means slot empty, insert immediately */
    if (entry == NULL)
    {
        ht->entries[slot] = ht_pair(key, val);
        return;
    }

    Entry *prev;

    /* walk through each entry until either the end is
    reached or a matching key is found */
    while (entry != NULL)
    {
        /* check key */
        if (strcmp(entry->key, key) == 0)
        {
            /* match found, replace val */
            free(entry->val);
            entry->val = malloc(strlen(val) + 1);
            strcpy(entry->val, val);
            return;
        }

        /* walk to next */
        prev = entry;
        entry = prev->next;
    }

    /* end of chain reached without a match, add new */
    prev->next = ht_pair(key, val);
}

char *ht_get(HT *ht, const char *key)
{
    size_t slot = hash(key);

    /* try to find a valid slot */
    Entry *entry = ht->entries[slot];

    /* no slot means no entry */
    RETURN_IF_NULL(entry);

    /* walk through each entry in the slot, which could just be a single thing */
    while (entry != NULL)
    {
        /* return value if found */
        if (strcmp(entry->key, key) == 0)
            return entry->val;

        /* proceed to next key if available */
        entry = entry->next;
    }

    /* reaching here means there were >= 1 entries but no key match */
    return NULL;
}

int ht_has(HT *ht, const char *key)
{
    size_t slot = hash(key);

    /* try to find a valid slot */
    Entry *entry = ht->entries[slot];

    /* no slot means no entry */
    if (entry == NULL)
        return 0;

    /* walk through each entry in the slot, which could just be a single thing */
    while (entry != NULL)
    {
        /* return value if found */
        if (strcmp(entry->key, key) == 0)
            return 1;

        /* proceed to next key if available */
        entry = entry->next;
    }

    /* reaching here means there were >= 1 entries but no key match */
    return 0;
}

void ht_del(HT *ht, const char *key)
{
    size_t slot = hash(key);

    /* try to find a valid slot */
    Entry *entry = ht->entries[slot];

    /* no slot means no entry */
    if (entry == NULL)
        return;

    Entry *prev;
    int idx = 0;

    /* walk through each entry until either the end is reached or a matching key is found */
    while (entry != NULL)
    {
        /* check key */
        if (strcmp(entry->key, key) == 0)
        {
            /* first item and no next entry */
            if (entry->next == NULL && idx == 0)
                ht->entries[slot] = NULL;

            /* first item with a next entry */
            if (entry->next != NULL && idx == 0)
                ht->entries[slot] = entry->next;

            /* last item */
            if (entry->next == NULL && idx != 0)
                prev->next = NULL;

            /* middle item */
            if (entry->next != NULL && idx != 0)
                prev->next = entry->next;

            /* free the deleted entry */
            free(entry->key);
            free(entry->val);
            free(entry);

            return;
        }

        /* walk to next */
        prev = entry;
        entry = prev->next;

        ++idx;
    }
}

#ifdef DEBUG
void ht_debug(HT *ht)
{
    size_t i;
    for (i = 0; i < TABLE_SIZE; ++i)
    {
        Entry *entry = ht->entries[i];

        if (entry == NULL)
            continue;

        printf("slot[%lu]: ", i);

        while (1)
        {
            printf("%s = %s ", entry->key, entry->val);

            if (entry->next == NULL)
                break;

            entry = entry->next;
        }

        printf("\n");
    }
}
#endif