1 files changed, 104 insertions, 0 deletions
diff --git a/src/io/map.c b/src/io/map.c
new file mode 100644
index 0000000..cb4642e
--- /dev/null
+++ b/src/io/map.c
@@ -0,0 +1,104 @@
+#include <string.h>
+#include <stdlib.h>
+
+#include "map.h"
+
+void record_map_init(RecordMap* map) {
+    map->capacity = 0;
+    map->len = 0;
+    map->entries = NULL;
+}
+
+void record_map_free(RecordMap* map) {
+    for(uint32_t i = 0; i < map->capacity; i++) {
+        Entry* e = &map->entries[i];
+        if (e->key != NULL) {
+            free_question(e->key);
+            free(e->key);
+            free_packet(e->value);
+            free(e->value);
+        }
+    }
+    free(map->entries);
+}
+
+static size_t hash_question(const Question* question) {
+    size_t hash = 5381;
+    for(int i = 0; i < question->domain[0]; i++) {
+        uint8_t c = question->domain[i+1];
+        hash = ((hash << 5) + hash) + c;
+    }
+    hash = ((hash << 5) + hash) + (uint8_t)question->cls;
+    hash = ((hash << 5) + hash) + (uint8_t)question->qtype;
+    return hash;
+}
+
+static bool question_equals(const Question* a, const Question* b) {
+    if (a->qtype != b->qtype) return false;
+    if (a->cls != b->cls) return false;
+    if (a->domain[0] != b->domain[0]) return false;
+    return memcmp(a->domain+1, b->domain+1, a->domain[0]) == 0;
+}
+
+static Entry* record_map_find(Entry* entries, uint32_t capacity, const Question* key) {
+    uint32_t index = hash_question(key) % capacity;
+    while(true) {
+        Entry* entry = &entries[index];
+        if(entry->key == NULL) {
+            return entry;
+        } else if(question_equals(entry->key, key)) {
+            return entry;
+        }
+        index += 1;
+        index %= capacity;
+    }
+}
+
+static void record_map_grow(RecordMap* map, uint32_t capacity) {
+    Entry* entries = malloc(capacity * sizeof(Entry));
+    for(uint32_t i = 0; i < capacity; i++) {
+        entries[i].key = NULL;
+        entries[i].value = NULL;
+    }
+    map->len = 0;
+    for(uint32_t i = 0; i < map->capacity; i++) {
+        Entry* entry = &map->entries[i];
+        if(entry->key == NULL) continue;
+        
+        Entry* dest = record_map_find(entries, capacity, entry->key);
+        dest->key = entry->key;
+        dest->value = entry->value;
+        map->len++;
+    }
+    free(map->entries);
+
+    map->entries = entries;
+    map->capacity = capacity;
+}
+
+bool record_map_get(const RecordMap* map, const Question* key, Packet* value) {
+    if(map->len == 0) return false;
+    
+    Entry* e = record_map_find(map->entries, map->capacity, key);
+    if (e->key == NULL) return false;
+
+    *value = *(e->value);
+    return true;
+}
+
+void record_map_add(RecordMap* map, Question* key, Packet* value) {
+     if(map->len + 1 > map->capacity * 0.75) {
+        int capacity = (map->capacity == 0 ? 8 : (2 * map->capacity));
+        record_map_grow(map, capacity);
+    }
+    Entry* e = record_map_find(map->entries, map->capacity, key);
+    bool new_key = e->key == NULL;
+    if(new_key) {
+        map->len++;
+        e->key = key;
+    }
+
+    value->header.z = true;
+    e->value = value;                
+}
+