1 files changed, 169 insertions, 0 deletions

diff --git a/src/hashmap.c b/src/hashmap.c
new file mode 100644
index 0000000..a712134
--- /dev/null
+++ b/src/hashmap.c
@@ -0,0 +1,169 @@
+#include "hashmap.h"
+
+#include <stdlib.h>
+#include <string.h>
+#include <assert.h>
+
+
+#define INITIAL_SIZE (16)
+#define LOAD_FACTOR_THRESHOLD (0.75)
+
+
+typedef struct Pair {
+  char *key;
+  void *value;
+  struct Pair *next;
+} Pair;
+
+typedef struct HashMap {
+  Pair **table;
+  size_t size;
+  size_t count;
+} HashMap;
+
+typedef struct HashMapKeys {
+  char **keys;
+  size_t count;
+  size_t index;
+} HashMapKeys;
+
+
+static unsigned int hash(const char *key, size_t size) {
+  unsigned int hash_value = 0;
+  while (*key) hash_value = (hash_value * 31) + *key++;
+  return hash_value % size;
+}
+
+static void resize(HashMap *map) {
+  size_t new_size = map->size * 2;
+  Pair **new_table = (Pair**)calloc(new_size, sizeof(Pair*));
+  assert(new_table);
+  for (size_t i = 0; i < map->size; ++i) {
+    Pair *pair = map->table[i];
+    while (pair) {
+      unsigned int index = hash(pair->key, new_size);
+      Pair *next = pair->next;
+      pair->next = new_table[index];
+      new_table[index] = pair;
+      pair = next;
+    }
+  }
+  
+  free(map->table);
+  map->table = new_table;
+  map->size = new_size;
+}
+
+HashMap *hashmap_create(void) {
+  HashMap *map = (HashMap*)malloc(sizeof(HashMap));
+  assert(map);
+  map->size = INITIAL_SIZE;
+  map->count = 0;
+  map->table = (Pair**)calloc(map->size, sizeof(Pair*));
+  assert(map->table);
+  return map;
+}
+
+void hashmap_insert(HashMap *map, const char *key, void *value) {
+  void **old_value = hashmap_get(map, key);
+  if (old_value) {
+    *old_value = value;
+    return;
+  }
+  if ((float)map->count / map->size > LOAD_FACTOR_THRESHOLD) resize(map);
+  unsigned int index = hash(key, map->size);
+  Pair *new_pair = (Pair*)malloc(sizeof(Pair));
+  assert(new_pair);
+  new_pair->key = strdup(key);
+  assert(new_pair->key);
+  new_pair->value = value;
+  new_pair->next = map->table[index];
+  map->table[index] = new_pair;
+  map->count++;
+}
+
+void **hashmap_get(HashMap *map, const char *key) {
+  unsigned int index = hash(key, map->size);
+  Pair *pair = map->table[index];
+  while (pair) {
+    if (strcmp(pair->key, key) == 0) return &pair->value;
+    pair = pair->next;
+  }
+  return NULL;
+}
+
+int hashmap_delete(HashMap *map, const char *key) {
+  unsigned int index = hash(key, map->size);
+  Pair *pair = map->table[index];
+  Pair *prev = NULL;
+  while (pair) {
+    if (strcmp(pair->key, key) == 0) {
+      if (prev) prev->next = pair->next;
+      else map->table[index] = pair->next;
+      free(pair->key);
+      free(pair);
+      map->count--;
+      return 0;
+    }
+    prev = pair;
+    pair = pair->next;
+  }
+  return -1;
+}
+
+void hashmap_free(HashMap *map) {
+  for (size_t i = 0; i < map->size; ++i) {
+    Pair *pair = map->table[i];
+    while (pair) {
+      Pair *temp = pair;
+      pair = pair->next;
+      free(temp->key);
+      free(temp);
+    }
+  }
+  free(map->table);
+  free(map);
+}
+
+void hashmap_iterate(HashMap *map, void (*callback)(const char *key, void *value)) {
+  for (size_t i = 0; i < map->size; ++i) {
+    Pair *pair = map->table[i];
+    while (pair) {
+      callback(pair->key, pair->value);
+      pair = pair->next;
+    }
+  }
+}
+
+HashMapKeys *hashmap_keys_create(HashMap *map) {
+  HashMapKeys *iter = malloc(sizeof(HashMapKeys));
+  assert(iter);
+  iter->keys = malloc(map->count * sizeof(char*));
+  assert(iter->keys);
+  iter->count = 0;
+  iter->index = 0;
+  for (size_t i = 0; i < map->size; ++i) {
+    Pair *pair = map->table[i];
+    while (pair) {
+      iter->keys[iter->count++] = strdup(pair->key);
+      pair = pair->next;
+    }
+  }
+  return iter;
+}
+
+const char *hashmap_keys_next(HashMapKeys *iter) {
+  if (iter->index < iter->count) {
+    return iter->keys[iter->index++];
+  }
+  return NULL;
+}
+
+void hashmap_keys_free(HashMapKeys *iter) {
+  if (!iter) return;
+  for (size_t i = 0; i < iter->count; ++i) {
+    free(iter->keys[i]);
+  }
+  free(iter->keys);
+  free(iter);
+}
\ No newline at end of file