hashtable.c

/* Author : Dario GENGA
 * Date : 18.01.2022
 * Description : Hash library.
 */

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

int hash(char *key, int64_t length) {
    // If the size of the int is too low the hash methods will generate overflow errors
    int64_t val = 0;
    for (size_t i = 0; i < strlen(key); i++) {
        val = 43 * val + key[i];
    }
    return (val % length);
}

entry *entry_create_empty() {
    entry *e = malloc(sizeof(entry));
    e->key = NULL;
    e->value = NULL;
    e->next = NULL;
    return e;
}

hm *hm_create(unsigned int length) {
    hm *hashmap = malloc(sizeof(hm));
    hashmap->length = length;
    hashmap->entries = malloc(sizeof(entry) * length);
    for (size_t i = 0; i < length; i++) {
        hashmap->entries[i] = entry_create_empty();
    }

    return hashmap;
}

entry *get_entry_by_key(entry *e, char *key) {
    if (e->key == key) {
        return e;
    } else if (e->next != NULL) {
        return get_entry_by_key(e->next, key);
    } else {
        return e;
    }
}

void hm_destroy(hm **hm) {
    for (int i = 0; i < (*hm)->length; i++) {
        entry *e = (*hm)->entries[i];
        while (e != NULL) {
            entry *to_free = e;
            e = e->next;
            free(to_free);
        }
    }
    free((*hm)->entries);
    free((*hm));
    (*hm) = NULL;
}

hm *hm_set(hm *hm, const char *const key, const char *const value) {
    // Hash the key and get the corresponding entry
    int key_index = hash((char *)key, hm->length);
    entry *e = get_entry_by_key(hm->entries[key_index], (char *)key);

    // Set the key and create the next entry if the key is not existing
    if (e->key != key) {
        e->key = (char *)key;
        if (e->next == NULL) {
            e->next = entry_create_empty();
        }
    }

    // Set the entry value and return the hashmap
    e->value = (char *)value;
    return hm;
}

char *hm_get(const hm *const hm, const char *const key) {
    int key_index = hash((char *)key, hm->length);
    char *c = get_entry_by_key(hm->entries[key_index], (char *)key)->value;
    return c;
}

char *hm_rm(hm *hm, const char *const key) {
    int key_index = hash((char *)key, hm->length);
    entry *e = get_entry_by_key(hm->entries[key_index], (char *)key);
    entry *previous_entry = NULL;
    entry *current_entry = hm->entries[key_index];
    int entry_index = 0;

    while (current_entry != e) {
        previous_entry = current_entry;
        current_entry = current_entry->next;
        entry_index++;
    }

    if (entry_index == 0) {
        hm->entries[key_index] = hm->entries[key_index]->next;
    } else if (previous_entry != NULL) {
        previous_entry->next = e->next;
    }

    char *entry_key = e->key;
    free(e);
    e = NULL;
    return entry_key;
}

int get_entry_list_size(entry *e) {
    int size = 0;
    size += sizeof(e->key) + sizeof(e->value) + 16;
    if (e->next != NULL) {
        size += get_entry_list_size(e->next);
    }
    return size;
}

char *hm_to_str(const hm *const hm) {
    int str_size = sizeof(hm) * hm->length;
    for (int i = 0; i < hm->length; i++) {
        str_size += get_entry_list_size(hm->entries[i]);
    }

    char *hm_str = malloc(str_size);
    // Ensure that the string is empty before doing anything
    hm_str[0] = '\0';

    strcat(hm_str, "[\n");
    for (int i = 0; i < hm->length; i++) {
        strcat(hm_str, "    [\n");
        entry *e = hm->entries[i];
        while (e != NULL && e->key != NULL) {
            strcat(hm_str, "        [\"");
            strcat(hm_str, e->key);
            strcat(hm_str, "\": \"");
            strcat(hm_str, e->value);
            strcat(hm_str, "\"]");
            if (e->next != NULL && e->next->key != NULL) {
                strcat(hm_str, ",");
            }
            strcat(hm_str, "\n");
            e = e->next;
        }

        strcat(hm_str, "    ]");
        if (i < hm->length - 1) {
            strcat(hm_str, ",");
        }
        strcat(hm_str, "\n");
    }

    strcat(hm_str, "]\n");
    return hm_str;
}

void hm_print(const hm *const hm) {
    char *str = hm_to_str(hm);
    printf("%s\n", str);
    free(str);
}