diff options
Diffstat (limited to 'analyzer/utils')
| -rw-r--r-- | analyzer/utils/hashmap.c | 126 | ||||
| -rw-r--r-- | analyzer/utils/hashmap.h | 83 |
2 files changed, 209 insertions, 0 deletions
diff --git a/analyzer/utils/hashmap.c b/analyzer/utils/hashmap.c new file mode 100644 index 0000000..8af7630 --- /dev/null +++ b/analyzer/utils/hashmap.c @@ -0,0 +1,126 @@ +#include "hashmap.h" + +#include <stdint.h> +#include <stdlib.h> +#include <string.h> + +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); +} + +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 new file mode 100644 index 0000000..96e8b58 --- /dev/null +++ b/analyzer/utils/hashmap.h @@ -0,0 +1,83 @@ +// utils/hashmap.h +// a simple implementation of hashmap using linked list + +#include <stddef.h> + +#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); + +// hash uint32_t key +extern size_t hash_uint32(void *key); + +// compare uint32_t keys +extern int compare_uint32(void *key1, void *key2); |