hash_map.c

Go to the documentation of this file.

/*
 * This file is part of the Aaru Data Preservation Suite.
 * Copyright (c) 2019-2026 Natalia Portillo.
 *
 * This library is free software; you can redistribute it and/or modify
 * it under the terms of the GNU Lesser General Public License as
 * published by the Free Software Foundation; either version 2.1 of the
 * License, or (at your option) any later version.
 *
 * This library is distributed in the hope that it will be useful, but
 * WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
 * Lesser General Public License for more details.
 *
 * You should have received a copy of the GNU Lesser General Public
 * License along with this library; if not, see <http://www.gnu.org/licenses/>.
 */
 
#include <stdbool.h>
#include <stdint.h>
#include <stdlib.h>
 
#include "hash_map.h"
 
#define INITIAL_SIZE        1024
#define LOAD_FACTOR         0.75
#define LARGE_MAP_THRESHOLD (2ULL * 1024 * 1024 * 1024 / sizeof(kv_pair_t))  // ~2GB worth of entries
#define LARGE_GROWTH_FACTOR 1.25                                             // 25% growth for large maps

hash_map_t *create_map(size_t size)
{
    // Enforce minimum size to prevent division by zero in modulo operations
    if(size < INITIAL_SIZE) size = INITIAL_SIZE;
 
    hash_map_t *map = malloc(sizeof(hash_map_t));
    map->table      = calloc(size, sizeof(kv_pair_t));
    map->size       = size;
    map->count      = 0;
 
    return map;
}

void free_map(hash_map_t *map)
{
    free(map->table);
    free(map);
}

static size_t calculate_new_size(size_t current_size)
{
    if(current_size < LARGE_MAP_THRESHOLD) return current_size * 2;
 
    return (size_t)((double)current_size * LARGE_GROWTH_FACTOR);
}

static void resize_map(hash_map_t *map, size_t new_size)
{
    kv_pair_t *old_table = map->table;
    size_t     old_size  = map->size;
 
    map->table = calloc(new_size, sizeof(kv_pair_t));
    map->size  = new_size;
    map->count = 0;
 
    for(size_t i = 0; i < old_size; i++)
        if(old_table[i].key != 0)
        {
            // Re-insert
            size_t idx = old_table[i].key % new_size;
 
            while(map->table[idx].key != 0) idx = (idx + 1) % new_size;
 
            map->table[idx] = old_table[i];
            map->count++;
        }
 
    free(old_table);
}

bool insert_map(hash_map_t *map, uint64_t key, uint64_t value)
{
    if((double)map->count / map->size > LOAD_FACTOR) resize_map(map, calculate_new_size(map->size));
 
    size_t idx = key % map->size;
 
    while(map->table[idx].key != 0 && map->table[idx].key != key) idx = (idx + 1) % map->size;
 
    if(map->table[idx].key == key) return false;  // Already present
 
    map->table[idx].key   = key;
    map->table[idx].value = value;
    map->count++;
 
    return true;
}

bool lookup_map(const hash_map_t *map, uint64_t key, uint64_t *out_value)
{
    size_t idx = key % map->size;
 
    while(map->table[idx].key != 0)
    {
        if(map->table[idx].key == key)
        {
            *out_value = map->table[idx].value;
            return true;
        }
 
        idx = (idx + 1) % map->size;
    }
 
    return false;
}