1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
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;
}
|
