hashmap.c

Go to the documentation of this file.

// Copyright (C) 2023 Ethan Uppal. All rights reserved.
 
#include <stdio.h>
#include <stdlib.h>  // malloc, free
#include "hashmap.h"
#include "util/abort.h"
#include "util/mtrack.h"
 
#define PS_HASH_MAP_INITIAL_CAPACITY 16
 
void ps_hash_map_assert_inv(const struct ps_hash_map* map) {
    usize calc_count = 0;
    for (usize i = 0; i < map->length; i++) {
        const struct ps_hash_map_entry* entry = &map->entries[i];
        if (entry->key == NULL) {
            continue;
        }
 
        const usize hash_idx = map->hasher(entry->key) % map->length;
 
        usize local_count = 1;
        while (entry->next) {
            local_count++;
            entry = entry->next;
            if (entry) {
                ps_assert(entry->key != NULL,
                    "hash map: only the first entry can have a NULL key");
                ps_assert(map->hasher(entry->key) % map->length == hash_idx,
                    "hash map: all entries in a bucket should have the same "
                    "hash index");
            }
        }
        calc_count += local_count;
    }
 
    ps_assert(map->count == calc_count, "hash map: invalid count");
}
 
inline struct ps_hash_map* ps_hash_map_new(is_equal_t is_equal, hasher_t hasher,
    free_fn_t free_fn) {
    return _ps_hash_map_new(is_equal, hasher, free_fn,
        PS_HASH_MAP_INITIAL_CAPACITY);
}
 
struct ps_hash_map* _ps_hash_map_new(is_equal_t is_equal, hasher_t hasher,
    free_fn_t free_fn, u64 capacity) {
    struct ps_hash_map* map = malloc(sizeof(*map)
                                     + sizeof(*map->entries) * capacity);
    CHECK(if (!map) {
        PS_NO_MEMORY();
        return NULL;
    })
 
    map->is_equal = is_equal;
    map->hasher = hasher;
    map->free_fn = free_fn;
 
    map->length = capacity;
    map->count = 0;
 
    for (usize i = 0; i < map->length; i++) {
        map->entries[i].key = NULL;
        map->entries[i].value = NULL;
        map->entries[i].next = NULL;
    }
 
    CHECK({ ps_hash_map_assert_inv(map); });
    return map;
}
 
void ps_hash_map_free(struct ps_hash_map* map) {
    for (usize i = 0; i < map->length; i++) {
        struct ps_hash_map_entry* entry = &map->entries[i];
        while (entry) {
            struct ps_hash_map_entry* next = entry->next;
            if (map->free_fn) {
                map->free_fn(entry->value);
            }
            entry = next;
            free(entry);  // should not free first entry
        }
    }
 
    free(map);
}
 
void ps_hash_map_redistribute(struct ps_hash_map** map_ptr) {
    struct ps_hash_map* map = *map_ptr;
    struct ps_hash_map* new_map = _ps_hash_map_new(map->is_equal, map->hasher,
        map->free_fn, map->length * 2);
    if (!new_map) {
        PS_NO_MEMORY();
    }
 
    for (usize i = 0; i < map->length; i++) {
        struct ps_hash_map_entry* entry = &map->entries[i];
        while (entry && entry->key) {
            ps_hash_map_insert(&new_map, entry->key, entry->value);
            entry = entry->next;
        }
    }
    *map_ptr = new_map;
 
    // free old map pointer
    free(map);
}
 
void ps_hash_map_insert(struct ps_hash_map** map_ptr, void* key, void* value) {
    if (!key) {
        return;
    }
 
    struct ps_hash_map* map = *map_ptr;
    CHECK({ ps_hash_map_assert_inv(map); });
 
    // compute hash index
    hash_t hash = map->hasher(key);
    usize index = hash % map->length;
    struct ps_hash_map_entry* entry = &map->entries[index];
 
    // try to find the bucket associated with the key
    if (entry->key) {
        while (entry) {
            if (entry->key != NULL && map->is_equal(entry->key, key)) {
                break;
            }
            if (entry->next == NULL) {
                // add new bucket if doesn't exist
                struct ps_hash_map_entry* new_entry =
                    malloc(sizeof(*new_entry));
                CHECK(if (!new_entry) {
                    PS_NO_MEMORY();
                    return;
                })
                new_entry->next = NULL;
                entry->next = new_entry;
                map->count++;
                entry = new_entry;
                break;
            }
            entry = entry->next;
        }
    } else {
        // we are setting the first entry
        map->count++;
    }
 
    // insert the key-value pair
    entry->key = key;
    entry->value = value;
    entry->next = NULL;
 
    // if load factor > 1, redistribute
    // can be inefficient if just malloc'd for new entry?
    if (map->count > map->length) {
        *map_ptr = map;
        ps_hash_map_redistribute(map_ptr);
    }
 
    CHECK({ ps_hash_map_assert_inv(*map_ptr); });
}
 
void* ps_hash_map_get(struct ps_hash_map* map, void* key) {
    CHECK({ ps_hash_map_assert_inv(map); });
 
    // compute hash index
    hash_t hash = map->hasher(key);
    usize index = hash % map->length;
    struct ps_hash_map_entry* entry = &map->entries[index];
 
    // simply walks the linked list
    while (entry) {
        if (entry->key && map->is_equal(entry->key, key)) {
            return entry->value;
        }
        entry = entry->next;
    }
 
    return NULL;
}
 
void ps_hash_map_remove(struct ps_hash_map* map, void* key) {
    CHECK({ ps_hash_map_assert_inv(map); });
 
    // compute hash index
    hash_t hash = map->hasher(key);
    usize index = hash % map->length;
    struct ps_hash_map_entry* entry = &map->entries[index];
    struct ps_hash_map_entry* prev = NULL;
 
    while (entry) {
        // find the entry
        if (entry->key && map->is_equal(entry->key, key)) {
            // we found the entry
            if (map->free_fn) {
                map->free_fn(entry->value);
            }
 
            if (prev == NULL) {
                // if it's the first node we have to see if there's a tail
                if (entry->next) {
                    // if so, we move that forward
                    entry->key = entry->next->key;
                    entry->value = entry->next->value;
                    auto_t afterward = entry->next->next;
                    free(entry->next);
                    entry->next = afterward;
                } else {
                    // if not, just set key to NULL
                    entry->key = NULL;
                    entry->value = NULL;
                }
            } else {
                // otherwise remove the node
                prev->next = entry->next;
                free(entry);
            }
            map->count--;
            return;
        }
 
        prev = entry;
        entry = entry->next;
    }
 
    CHECK({ ps_hash_map_assert_inv(map); });
}
 
bool ps_hash_map_contains(struct ps_hash_map* map, void* key) {
    return ps_hash_map_get(map, key) != NULL;
}
 
u64 ps_hash_map_count(const struct ps_hash_map* map) {
    return map->count;
}