hashMap.c

#include "hashMap.h"
#include <malloc.h>
#include <string.h>
#include "prime.h"

#define HM_PRIME_1 151
#define HM_PRIME_2 163
#define HM_INITIAL_BASE_SIZE 53


static hm_item* hm_new_item(const Value key, const Value val) {
    hm_item *item = malloc(sizeof(hm_item));
    if (!item) {
        perror("HM_NEW_ITEM_MALLOC_FAIL");
        exit(EXIT_FAILURE);
    }

    // If it's a string, then we use strdup to copy memory
    // (in order to prevent new pointer to point to the previous block of memory)
    // If it's an integer, we just assign it as it is
    item->key.type = key.type;
    if (key.type == TYPE_STRING) {
        item->key.data.str = strdup(key.data.str);
    } else {
        item->key.data.i = key.data.i;
    }

    item->val.type = val.type;
    if (val.type == TYPE_STRING) {
        item->val.data.str = strdup(val.data.str);
    } else {
        item->val.data.i = val.data.i;
    }

    item->is_deleted = false;
    return item;
}

hm_map* hm_new_map() {
    hm_map *map = malloc(sizeof(hm_map));
    if (!map) {
        perror("HM_NEW_MAP_MALLOC_FAIL");
        exit(EXIT_FAILURE);
    }

    map->size = HM_INITIAL_BASE_SIZE;
    map->count = 0;
    map->items = calloc(map->size, sizeof(hm_item*));
    if (!map->items) {
        perror("HM_NEW_MAP_CALLOC_FAIL");
        exit(EXIT_FAILURE);
    }
    return map;
}

static void hm_delete_item(hm_item* item) {
    if (item->key.type == TYPE_STRING && item->key.data.str) {
        free(item->key.data.str);
    }
    if (item->val.type == TYPE_STRING && item->val.data.str) {
        free(item->val.data.str);
    }
    free(item);
}

static hm_map* hm_new_sized(const int base_size) {
    hm_map* map = malloc(sizeof(hm_map));
    if (!map) {
        perror("HM_NEW_SIZED_MALLOC_FAIL");
        exit(EXIT_FAILURE);
    }
    map->base_size = base_size;
    // Calculate next closest prime number
    map->size = next_prime(map->base_size);

    map->count = 0;
    map->items = calloc(map->size, sizeof(hm_item*));
    if (!map->items) {
        perror("HM_NEW_SIZED_CALLOC_FAIL");
        exit(EXIT_FAILURE);
    }
    return map;
}

void hm_delete_map(hm_map* map) {
    for (int i = 0; i < map->size; i++) {
        if (map->items[i]) {
            hm_delete_item(map->items[i]);
        }
    }
    free(map->items);
    free(map);
}

static void hm_resize(hm_map* map, const int base_size) {
    // Check if we're not trying to shrink our map
    if (base_size < HM_INITIAL_BASE_SIZE) return;

    // Copy our map
    hm_map* new_map = hm_new_sized(base_size);
    for (int i = 0; i < map->size; i++) {
        hm_item* item = map->items[i];
        if (item && !item->is_deleted) {
            hm_insert(new_map, item->key, item->val);
        }
    }

    map->base_size = new_map->base_size;
    map->count = new_map->count;

    // To delete new_map, we give it map's size and items
    const int tmp_size = map->size;
    map->size = new_map->size;
    new_map->size = tmp_size;

    hm_item** tmp_items = map->items;
    map->items = new_map->items;
    new_map->items = tmp_items;

    hm_delete_map(new_map);
}

static void hm_resize_up(hm_map* map) {
    // Multiply by two, then find closest prime number
    const int new_size = map->base_size * 2;
    hm_resize(map, new_size);
}

static void hm_resize_down(hm_map* map) {
    // Same here, except multiplication
    const int new_size = map->base_size / 2;
    hm_resize(map, new_size);
}

// djb2 hash function for strings, don't really know how it works, but it works
static unsigned int hm_hash(Value value, int prime, size_t num_buckets) {
    unsigned long hash;
    // If it's an integer we just remove sign
    if (value.type == TYPE_INT) {
        hash = (unsigned int)value.data.i;
    } else {
        hash = 5381;
        const char* str = value.data.str;
        int c;
        while ((c = *str++)) {
            hash = ((hash << 5) + hash) + c;
        }
    }

    return (hash * prime) % num_buckets;
}

// Open adressing with double hashing
static unsigned hm_get_hash(Value value, size_t num_buckets, unsigned attempt) {
    const unsigned hash_a = hm_hash(value, HM_PRIME_1, num_buckets);
    const unsigned hash_b = hm_hash(value, HM_PRIME_2, num_buckets);
    return (hash_a + attempt * (hash_b + 1)) % num_buckets;
}

void hm_insert(hm_map* map, Value key, Value value) {
    // Multiplying by 100 in order to prevent calculations with floats
    const int load = map->count * 100 / map->size;
    // If load on a map is too high and it's not performing well
    // we should scale it
    if (load > 70) {
        hm_resize_up(map);
    }

    hm_item* item = hm_new_item(key, value);

    unsigned index = hm_get_hash(key, map->size, 0);
    hm_item* cur_item = map->items[index];

    for (int i = 1; cur_item && !cur_item->is_deleted; i++) {
        // If key is already in map, we update it's value by deleting old one and assigning new one
        if (key.type == TYPE_INT && item->key.data.i == key.data.i || key.type == TYPE_STRING && strcmp(item->key.data.str, key.data.str) == 0) {
            hm_delete_item(cur_item);
            map->items[index] = item;
            return;
        }

        index = hm_get_hash(item->key, map->size, i);
        cur_item = map->items[index];
    }
    map->items[index] = item;
    map->count++;
}

Value hm_search(hm_map * map, Value key) {
    unsigned index = hm_get_hash(key, map->size, 0);
    hm_item* item = map->items[index];
    for (int i = 1; item  && !item->is_deleted; i++) {
        if (key.type == TYPE_INT && item->key.data.i == key.data.i || key.type == TYPE_STRING && !strcmp(item->key.data.str, key.data.str)) {
            // Copy string in order for it to "live" after map deletion
            if (item->val.type == TYPE_STRING) {
                Value new = {.type = TYPE_STRING, .data.str = strdup(item->val.data.str)};
                return new;
            }
            return item->val;
        }
        index = hm_get_hash(key, map->size, i);
        item = map->items[index];
    }
    perror("HM_SEARCH_ERR");
    exit(EXIT_FAILURE);
}

void hm_delete(hm_map* map, Value key) {
    // Calculate load and shrink map in order to save memory
    const int load = map->count * 100 / map->size;
    if (load < 10) {
        hm_resize_down(map);
    }

    unsigned index = hm_get_hash(key, map->size, 0);
    hm_item* item = map->items[index];
    for (int i = 1; item; i++) {
        // In order to not mess up hash chains, we can't directly free items, so we just mark them as deleted
        if (!item->is_deleted) {
            if (key.type == TYPE_INT && item->key.data.i == key.data.i || key.type == TYPE_STRING && strcmp(item->key.data.str, key.data.str) == 0) {
                map->items[index]->is_deleted = true;
            }
        }
        index = hm_get_hash(key, map->size, i);
        item = map->items[index];
    }
    map->count--;
}