From f75a39e4c476c266efff6cff44d03d6afff3a4f7 Mon Sep 17 00:00:00 2001 From: Mosder Date: Fri, 10 Jul 2026 16:31:08 +0200 Subject: refactor: moved hashmap implementation from utils to new directory utils/structures and removed unnecessary functionality from it --- analyzer/utils/hashmap.c | 147 ------------------------------------ analyzer/utils/hashmap.h | 98 ------------------------ analyzer/utils/structures/hashmap.c | 109 ++++++++++++++++++++++++++ analyzer/utils/structures/hashmap.h | 77 +++++++++++++++++++ 4 files changed, 186 insertions(+), 245 deletions(-) delete mode 100644 analyzer/utils/hashmap.c delete mode 100644 analyzer/utils/hashmap.h create mode 100644 analyzer/utils/structures/hashmap.c create mode 100644 analyzer/utils/structures/hashmap.h diff --git a/analyzer/utils/hashmap.c b/analyzer/utils/hashmap.c deleted file mode 100644 index 2ab8bab..0000000 --- a/analyzer/utils/hashmap.c +++ /dev/null @@ -1,147 +0,0 @@ -#include "hashmap.h" - -#include -#include -#include - -HashMap *hashmap_new( - size_t key_size, size_t value_size, size_t (*hash)(void *key), int (*compare)(void *key1, void *key2), void (*key_cleanup)(void *key), - void (*value_cleanup)(void *key) -) { - HashMap *map = malloc(sizeof(HashMap)); - for (size_t i = 0; i < HASHMAP_TABLE_SIZE; i++) - map->table[i] = NULL; - map->key_size = key_size; - map->value_size = value_size; - map->hash = hash; - map->compare = compare; - map->key_cleanup = key_cleanup; - map->value_cleanup = value_cleanup; - return map; -} - -void hashmap_put(HashMap *map, void *key, void *value) { - size_t key_hash = map->hash(key); - HashMapNode *node = map->table[key_hash]; - - // check if it exists - while (node) { - // if it exists - update node - if (map->compare(key, node->key)) { - // ensure no hanging memory allocation - if (map->value_cleanup) { - map->value_cleanup(node); - } - memcpy(node->value, value, map->value_size); - return; - } - node = node->next; - } - - // if it doesn't exist - create new node - HashMapNode *new_node = malloc(sizeof(HashMapNode)); - new_node->key = malloc(map->key_size); - new_node->value = malloc(map->value_size); - memcpy(new_node->key, key, map->key_size); - memcpy(new_node->value, value, map->value_size); - - // put in front of the linked list - new_node->next = map->table[key_hash]; - map->table[key_hash] = new_node; -} - -void *hashmap_get(HashMap *map, void *key) { - size_t key_hash = map->hash(key); - HashMapNode *node = map->table[key_hash]; - - // check if it exists - while (node) { - // if it exists - return the value pointer - if (map->compare(key, node->key)) { - return node->value; - } - node = node->next; - } - - // if it doesn't exist - return NULL - return NULL; -} - -void free_node_without_next(HashMap *map, HashMapNode *node) { - if (map->key_cleanup) { - map->key_cleanup(node); - } - if (map->value_cleanup) { - map->value_cleanup(node); - } - free(node->key); - free(node->value); - free(node); -} - -void hashmap_delete(HashMap *map, void *key) { - size_t key_hash = map->hash(key); - HashMapNode **p_node = &map->table[key_hash]; - - // check if it exists - while (*p_node) { - // if it exists - delete it - if (map->compare(key, (*p_node)->key)) { - HashMapNode *next = (*p_node)->next; - free_node_without_next(map, *p_node); - *p_node = next; - return; - } - p_node = &(*p_node)->next; - } -} - -HashMapNode *hashmap_first(HashMap *map) { - for (size_t i = 0; i < HASHMAP_TABLE_SIZE; i++) { - HashMapNode *node = map->table[i]; - if (node) - return node; - } - return NULL; -} - -HashMapNode *hashmap_next(HashMap *map, HashMapNode *node) { - if (node->next) - return node->next; - - for (size_t i = map->hash(node->key) + 1; i < HASHMAP_TABLE_SIZE; i++) { - HashMapNode *node = map->table[i]; - if (node) - return node; - } - return NULL; -} - -void hashmap_free(HashMap *map) { - for (size_t i = 0; i < HASHMAP_TABLE_SIZE; i++) { - HashMapNode *curr = map->table[i]; - while (curr) { - HashMapNode *next = curr->next; - free_node_without_next(map, curr); - curr = next; - } - } - free(map); -} - -size_t hash_uint32(void *key) { - // MurmurHash3 - uint32_t k = *(uint32_t *)key; - k ^= k >> 16; - k *= 0x85ebca6b; - k ^= k >> 13; - k *= 0xc2b2ae35; - k ^= k >> 16; - return k % HASHMAP_TABLE_SIZE; -} - -int compare_uint32(void *key1, void *key2) { - uint32_t *k1 = key1; - uint32_t *k2 = key2; - return *k1 == *k2; -} diff --git a/analyzer/utils/hashmap.h b/analyzer/utils/hashmap.h deleted file mode 100644 index 22c71c6..0000000 --- a/analyzer/utils/hashmap.h +++ /dev/null @@ -1,98 +0,0 @@ -// utils/hashmap.h -// a simple implementation of hashmap using linked list - -#include - -#define HASHMAP_TABLE_SIZE 1024 - -typedef struct HashMapNode { - void *key; - void *value; - struct HashMapNode *next; -} HashMapNode; - -typedef struct { - HashMapNode *table[HASHMAP_TABLE_SIZE]; - size_t key_size; - size_t value_size; - size_t (*hash)(void *key); - int (*compare)(void *key1, void *key2); - void (*key_cleanup)(void *key); - void (*value_cleanup)(void *value); -} HashMap; - -// create a new hash map -// params: -// - key_size - size of the key type -// - value_size - size of the value type -// - hash - function for hashing keys -// params: -// - key - pointer to the key to hash -// returns: -// hash of the key (size_t in [0; HASHMAP_TABLE_SIZE)) -// - compare - function for comparing keys -// params: -// - key1 - pointer to the first of the keys to compare -// - key2 - pointer to the second of the keys to compare -// returns: -// truthy if the keys are identical, falsy if they are different -// - key_cleanup - function for cleaning up any internal allocations inside node->key (not the key itself) -// if it has no heap allocations, this should be NULL -// params: -// - key - pointer to the key to cleanup -// - value_cleanup - function for cleaning up any internal allocations inside node->value (not the value itself) -// if it has no heap allocations, this should be NULL -// params: -// - value - pointer to the value to cleanup -// returns: -// pointer to the new hash map -extern HashMap *hashmap_new( - size_t key_size, size_t value_size, size_t (*hash)(void *key), int (*compare)(void *key1, void *key2), void (*key_cleanup)(void *key), - void (*value_cleanup)(void *value) -); - -// create/update an entry in a hash map -// params: -// - map - hash map to insert to -// - key - pointer to the key -// - value - pointer to the value -extern void hashmap_put(HashMap *map, void *key, void *value); - -// get the value of given key from a hash map -// params: -// - map - hash map to get from -// - key - pointer to the key of the value to get -// returns: -// pointer to the value of specified key or NULL if it doesn't exist -extern void *hashmap_get(HashMap *map, void *key); - -// delete an entry from a hash map -// params: -// - map - hash map to delete from -// - key - pointer to the key of the entry to delete -extern void hashmap_delete(HashMap *map, void *key); - -// get first node in the hashmap, use with hashmap_next to iterate over hashmap -// params: -// - map - hash map to get the first node from -// returns: -// pointer to the first node in the hashmap or NULL if there's no entries in it -extern HashMapNode *hashmap_first(HashMap *map); - -// get next node in the hashmap, use with hashmap_first to iterate over hashmap -// params: -// - map - hash map to get the next node from -// - node - the node preceeding the one we search for -// returns: -// pointer to the next node in the hashmap or NULL if there's no next -extern HashMapNode *hashmap_next(HashMap *map, HashMapNode *node); - -// free the hash map -// - map - hash map to free -extern void hashmap_free(HashMap *map); - -// hash uint32_t key -extern size_t hash_uint32(void *key); - -// compare uint32_t keys -extern int compare_uint32(void *key1, void *key2); diff --git a/analyzer/utils/structures/hashmap.c b/analyzer/utils/structures/hashmap.c new file mode 100644 index 0000000..466f258 --- /dev/null +++ b/analyzer/utils/structures/hashmap.c @@ -0,0 +1,109 @@ +#include "hashmap.h" + +#include +#include +#include + +HashMap *hashmap_new( + size_t key_size, size_t value_size, size_t (*hash)(void *key), int (*compare)(void *key1, void *key2), void (*key_cleanup)(void *key), + void (*value_cleanup)(void *key) +) { + HashMap *map = malloc(sizeof(HashMap)); + for (size_t i = 0; i < HASHMAP_TABLE_SIZE; i++) + map->table[i] = NULL; + map->key_size = key_size; + map->value_size = value_size; + map->hash = hash; + map->compare = compare; + map->key_cleanup = key_cleanup; + map->value_cleanup = value_cleanup; + return map; +} + +void hashmap_put(HashMap *map, void *key, void *value) { + size_t key_hash = map->hash(key); + HashMapNode *node = map->table[key_hash]; + + // check if it exists + while (node) { + // if it exists - update node + if (map->compare(key, node->key)) { + // ensure no hanging memory allocation + if (map->value_cleanup) { + map->value_cleanup(node); + } + memcpy(node->value, value, map->value_size); + return; + } + node = node->next; + } + + // if it doesn't exist - create new node + HashMapNode *new_node = malloc(sizeof(HashMapNode)); + new_node->key = malloc(map->key_size); + new_node->value = malloc(map->value_size); + memcpy(new_node->key, key, map->key_size); + memcpy(new_node->value, value, map->value_size); + + // put in front of the linked list + new_node->next = map->table[key_hash]; + map->table[key_hash] = new_node; +} + +void *hashmap_get(HashMap *map, void *key) { + size_t key_hash = map->hash(key); + HashMapNode *node = map->table[key_hash]; + + // check if it exists + while (node) { + // if it exists - return the value pointer + if (map->compare(key, node->key)) { + return node->value; + } + node = node->next; + } + + // if it doesn't exist - return NULL + return NULL; +} + +void free_node_without_next(HashMap *map, HashMapNode *node) { + if (map->key_cleanup) { + map->key_cleanup(node); + } + if (map->value_cleanup) { + map->value_cleanup(node); + } + free(node->key); + free(node->value); + free(node); +} + +void hashmap_delete(HashMap *map, void *key) { + size_t key_hash = map->hash(key); + HashMapNode **p_node = &map->table[key_hash]; + + // check if it exists + while (*p_node) { + // if it exists - delete it + if (map->compare(key, (*p_node)->key)) { + HashMapNode *next = (*p_node)->next; + free_node_without_next(map, *p_node); + *p_node = next; + return; + } + p_node = &(*p_node)->next; + } +} + +void hashmap_free(HashMap *map) { + for (size_t i = 0; i < HASHMAP_TABLE_SIZE; i++) { + HashMapNode *curr = map->table[i]; + while (curr) { + HashMapNode *next = curr->next; + free_node_without_next(map, curr); + curr = next; + } + } + free(map); +} diff --git a/analyzer/utils/structures/hashmap.h b/analyzer/utils/structures/hashmap.h new file mode 100644 index 0000000..cc2c9e0 --- /dev/null +++ b/analyzer/utils/structures/hashmap.h @@ -0,0 +1,77 @@ +// utils/hashmap.h +// a simple implementation of hashmap using linked list + +#include + +#define HASHMAP_TABLE_SIZE 1024 + +typedef struct HashMapNode { + void *key; + void *value; + struct HashMapNode *next; +} HashMapNode; + +typedef struct { + HashMapNode *table[HASHMAP_TABLE_SIZE]; + size_t key_size; + size_t value_size; + size_t (*hash)(void *key); + int (*compare)(void *key1, void *key2); + void (*key_cleanup)(void *key); + void (*value_cleanup)(void *value); +} HashMap; + +// create a new hash map +// params: +// - key_size - size of the key type +// - value_size - size of the value type +// - hash - function for hashing keys +// params: +// - key - pointer to the key to hash +// returns: +// hash of the key (size_t in [0; HASHMAP_TABLE_SIZE)) +// - compare - function for comparing keys +// params: +// - key1 - pointer to the first of the keys to compare +// - key2 - pointer to the second of the keys to compare +// returns: +// truthy if the keys are identical, falsy if they are different +// - key_cleanup - function for cleaning up any internal allocations inside node->key (not the key itself) +// if it has no heap allocations, this should be NULL +// params: +// - key - pointer to the key to cleanup +// - value_cleanup - function for cleaning up any internal allocations inside node->value (not the value itself) +// if it has no heap allocations, this should be NULL +// params: +// - value - pointer to the value to cleanup +// returns: +// pointer to the new hash map +extern HashMap *hashmap_new( + size_t key_size, size_t value_size, size_t (*hash)(void *key), int (*compare)(void *key1, void *key2), void (*key_cleanup)(void *key), + void (*value_cleanup)(void *value) +); + +// create/update an entry in a hash map +// params: +// - map - hash map to insert to +// - key - pointer to the key +// - value - pointer to the value +extern void hashmap_put(HashMap *map, void *key, void *value); + +// get the value of given key from a hash map +// params: +// - map - hash map to get from +// - key - pointer to the key of the value to get +// returns: +// pointer to the value of specified key or NULL if it doesn't exist +extern void *hashmap_get(HashMap *map, void *key); + +// delete an entry from a hash map +// params: +// - map - hash map to delete from +// - key - pointer to the key of the entry to delete +extern void hashmap_delete(HashMap *map, void *key); + +// free the hash map +// - map - hash map to free +extern void hashmap_free(HashMap *map); -- cgit v1.2.3