summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
-rw-r--r--Makefile2
-rw-r--r--include/map.h31
-rwxr-xr-xmainbin0 -> 20504 bytes
-rw-r--r--main.c38
-rw-r--r--map.c77
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
Binary files differ
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;
+}