map.h

Go to the documentation of this file.

#pragma once
 
#include <assert.h>
#include <stdbool.h>
#include <stdint.h>
#include <string.h>
#include <sys/io.h>
 
#define MAP_MIN_CAPACITY 16
 
#define MAP_MAX_LOAD_PERCENTAGE 75
 
#define MAP_TOMBSTONE ((map_entry_t*)1)
 
#define MAP_KEY_MAX_LENGTH 40
 
typedef struct
{
    uint8_t key[MAP_KEY_MAX_LENGTH];
    uint64_t len;
    uint64_t hash;
} map_key_t;
 
typedef struct
{
    map_key_t key;
} map_entry_t;
 
#define MAP_ENTRY_PTR_IS_VALID(entryPtr) ((entryPtr) != NULL && (entryPtr) != MAP_TOMBSTONE)
 
typedef struct
{
    map_entry_t** entries;
    uint64_t capacity;
    uint64_t length;
    uint64_t tombstones;
} map_t;
 
uint64_t hash_object(const void* object, uint64_t length);
 
static inline map_key_t map_key_buffer(const void* buffer, uint64_t length)
{
    assert(length <= MAP_KEY_MAX_LENGTH);
    map_key_t key;
    memcpy(key.key, buffer, length);
    key.len = length;
    key.hash = hash_object(buffer, length);
    return key;
}
 
static inline map_key_t map_key_uint64(uint64_t uint64)
{
    map_key_t key;
    memcpy(key.key, &uint64, sizeof(uint64_t));
    key.len = sizeof(uint64_t);
    key.hash = hash_object(&uint64, sizeof(uint64_t));
    return key;
}
 
static inline map_key_t map_key_string(const char* str)
{
    return map_key_buffer(str, strlen(str));
}
 
void map_entry_init(map_entry_t* entry);
 
uint64_t map_init(map_t* map);
 
void map_deinit(map_t* map);
 
uint64_t map_insert(map_t* map, const map_key_t* key, map_entry_t* value);
 
map_entry_t* map_get(map_t* map, const map_key_t* key);
 
void map_remove(map_t* map, const map_key_t* key);
 
uint64_t map_size(const map_t* map);
 
uint64_t map_capacity(const map_t* map);
 
bool map_is_empty(const map_t* map);
 
bool map_contains(map_t* map, const map_key_t* key);
 
void map_clear(map_t* map);
 
uint64_t map_reserve(map_t* map, uint64_t minCapacity);