diff options
author | leo <leo@azuminha.com> | 2024-04-03 15:16:39 -0300 |
---|---|---|
committer | leo <leo@azuminha.com> | 2024-04-03 15:16:39 -0300 |
commit | 6a564da0f9c510c0222b05ba5da18c6ef73e8030 (patch) | |
tree | ba76677e1ce186cc31b31d3a04749b2c9889f625 /map.c |
map implementado
Diffstat (limited to 'map.c')
-rw-r--r-- | map.c | 77 |
1 files changed, 77 insertions, 0 deletions
@@ -0,0 +1,77 @@ +#include "include/map.h" +#include <stdlib.h> +#include <stdio.h> +string_map init_map(uint32_t size){ + string_map tmp; + + tmp.size = size; + tmp.head = (node **)malloc(sizeof(node *) * size); + + node **h = tmp.head; + for(int i = 0; i < size; ++i){ + h[i] = NULL; + } + + return tmp; +} + +/* + * 64-bit FNV-1 hash + * https://en.wikipedia.org/wiki/Fowler%E2%80%93Noll%E2%80%93Vo_hash_function + */ +uint32_t hash_function(char *key, uint32_t size){ + uint64_t hash = FNV_offset_basis; + uint32_t key_size = strlen(key); + + for(int i = 0; i < key_size; ++i){ + hash *= FNV_prime; + hash ^= (uint64_t)key[i]; + } + + return hash % size; +} + +node *create_node(char *key, char *value){ + node *tmp = (node *)malloc(sizeof(node)); + tmp->key = key; + tmp->value = value; + tmp->next = NULL; + return tmp; +} + +void insert_map(char *key, char *value, string_map map){ + uint32_t hash_offset = hash_function(key, map.size); + + if(*(map.head + hash_offset) == NULL){ + node *tmp = create_node(key, value); + *(map.head + hash_offset) = tmp; + return; + } + + node *head = *(map.head + hash_offset); + while(head->next != NULL){ + if(strcmp(key, (head->key)) == 0){ + printf("REPETIDO\n"); + return; + } + head = head->next; + } + + node *tmp = create_node(key, value); + (head->next) = tmp; +} + +char *get_value(char *key, string_map map){ + uint32_t hash_offset = hash_function(key, map.size); + node *head = *(map.head + hash_offset); + + while(head != NULL){ + if(strcmp(key, (head->key)) == 0){ + return head->value; + } + head = head->next; + } + + fprintf(stderr, "VALOR NAO ESTA NO HASH TABLE\n"); + return NULL; +} |