map implementado

5 files changed, 148 insertions, 0 deletions

diff --git a/Makefile b/Makefile
new file mode 100644
index 0000000..00a226d
--- /dev/null
+++ b/Makefile
@@ -0,0 +1,2 @@
+all:
+	gcc -o main main.c map.c -g
diff --git a/include/map.h b/include/map.h
new file mode 100644
index 0000000..1dea3e7
--- /dev/null
+++ b/include/map.h
@@ -0,0 +1,31 @@
+#ifndef _MYMAP_H
+#define _MYMAP_H
+
+#include <string.h>
+#include <stdint.h>
+
+#define A
+
+typedef struct Node{
+    char *key;
+    char *value;
+    struct Node *next;
+}node;
+
+typedef struct Map{
+    uint32_t size;
+    node **head;
+}string_map;
+
+string_map init_map(uint32_t size);
+/*
+ * 64-bit FNV-1 hash
+ * https://en.wikipedia.org/wiki/Fowler%E2%80%93Noll%E2%80%93Vo_hash_function
+ */
+#define FNV_offset_basis 14695981039346656037UL
+#define FNV_prime 1099511628211UL
+uint32_t hash_function(char *key, uint32_t size);
+void insert_map(char *key, char *value, string_map map);
+node *create_node(char *key, char *value);
+char *get_value(char *key, string_map map);
+#endif
diff --git a/main b/main
new file mode 100755
index 0000000..dee5d0e
--- /dev/null
+++ b/main
diff --git a/main.c b/main.c
new file mode 100644
index 0000000..0f0d650
--- /dev/null
+++ b/main.c
@@ -0,0 +1,38 @@
+#include <stdio.h>
+#include <stdlib.h>
+
+#include "include/map.h"
+
+#define EXT_ERR_PARAMS 1
+int main(int argc, char *argv[]){
+    string_map special_char = init_map(1024);
+
+    insert_map("aa", "aa", special_char);
+    insert_map("d", "d", special_char);
+
+    char *test = get_value("aa", special_char);
+    printf("%s\n", test);
+    test = get_value("d", special_char);
+    printf("%s\n", test);
+    test = get_value("d", special_char);
+    printf("%s\n", test);
+    test = get_value("aa", special_char);
+    printf("%s\n", test);
+    /*
+    if(argc != 2){
+        fprintf(stderr, "passe o nome do arquivo\n");
+        exit(EXT_ERR_PARAMS);
+    }
+
+    char *file_path = argv[1];
+    FILE *fp = fopen(file_path, "r");
+
+    char tmp;
+    while(fscanf(fp, "%c", &tmp) != EOF){
+        printf("%c", tmp);
+    }
+
+    fclose(fp);
+    */
+    return 0;
+}
diff --git a/map.c b/map.c
new file mode 100644
index 0000000..58ed548
--- /dev/null
+++ b/map.c
@@ -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;
+}