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
|
#include "map.h"
#include "lib.h"
#include "tag.h"
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
void map_init(map_t *map) {
map->len = 0;
map->capacity = 0;
map->entries = NULL;
}
void map_free(map_t *map) {
if (map->entries == NULL)
return;
for (uint32_t i = 0; i < map->capacity; i++) {
if (map->entries[i].name != NULL)
tag_free(&map->entries[i]);
}
free(map->entries);
}
static uint32_t hash(const char *name, uint16_t len) {
uint32_t hash = 2166136261u;
while(len > 0) {
hash ^= (uint8_t)(*name);
hash *= 16777619;
name++;
len--;
}
return hash;
}
static tag_t *map_find(tag_t *entries, uint32_t capacity, tag_t *tag) {
uint32_t index = hash(tag->name, tag->name_len) % capacity;
while(true) {
tag_t *entry = &entries[index];
if (entry->name == NULL) {
return entry;
} else if (
entry->name_len == tag->name_len &&
memcmp(entry->name, tag->name, tag->name_len) == 0
) {
return entry;
}
index += 1;
index %= capacity;
}
}
static void map_grow(map_t *map, uint32_t capacity) {
tag_t *entries = xzalloc(capacity * sizeof(tag_t));
for (uint32_t i = 0; i < capacity; i++) {
entries[i].name = NULL;
entries[i].name_len = 0;
}
map->len = 0;
for (uint32_t i = 0; i < map->capacity; i++) {
tag_t *tag = &map->entries[i];
if (tag->name == NULL) continue;
tag_t *dest = map_find(entries, capacity, tag);
*dest = *tag;
map->len++;
}
free(map->entries);
map->entries = entries;
map->capacity = capacity;
}
void map_put(map_t *map, tag_t *tag) {
if (map->len + 1 > map->capacity * 0.75) {
int capacity = (map->capacity == 0 ? 8 : (2 * map->capacity));
map_grow(map, capacity);
}
tag_t *dest = map_find(map->entries, map->capacity, tag);
if (dest->name == NULL) {
map->len++;
} else {
tag_free(dest);
}
*dest = *tag;
}
|
