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
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
| | /*
* Copyright (C) 2024 olang maintainers
*
* This program is free software: you can redistribute it and/or modify
* it under the terms of the GNU General Public License as published by
* the Free Software Foundation, either version 3 of the License, or
* (at your option) any later version.
*
* This program is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
* GNU General Public License for more details.
*
* You should have received a copy of the GNU General Public License
* along with this program. If not, see <https://www.gnu.org/licenses/>.
*/
#include "map.h"
#include "arena.h"
#include <assert.h>
#include <errno.h>
#include <stdbool.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
static uint32_t
u32_fnv1a_hash(const char *s);
static void
map_init(map_t *map);
static char *
__strdup(const char *s, arena_t *arena);
map_t *
map_new(arena_t *arena)
{
map_t *map = (map_t *)arena_alloc(arena, sizeof(map_t));
if (map == NULL) {
fprintf(stderr, "[FATAL] Out of memory: map_new: %s\n", strerror(errno));
exit(EXIT_FAILURE);
}
map->arena = arena;
map_init(map);
return map;
}
static void
map_init(map_t *map)
{
assert(map);
map->entries = (map_entry_t *)arena_alloc(map->arena, MAP_INITIAL_CAPACITY * sizeof(map_entry_t));
assert(map->entries != NULL);
memset(map->entries, 0, MAP_INITIAL_CAPACITY * sizeof(map_entry_t));
if (map->entries == NULL) {
fprintf(stderr, "[FATAL] Out of memory: map_init: %s\n", strerror(errno));
exit(EXIT_FAILURE);
}
map->capacity = MAP_INITIAL_CAPACITY;
}
static uint32_t
u32_fnv1a_hash(const char *s)
{
uint32_t hash = U32_FNV1A_OFFSET_BASIS;
size_t len = strlen(s);
for (size_t i = 0; i < len; ++i) {
hash ^= s[i];
hash *= U32_FNV1A_PRIME;
}
return hash;
}
bool
map_put(map_t *map, char *key, void *value)
{
assert(map && key);
uint32_t hash = u32_fnv1a_hash(key);
map_entry_t *entry = &(map->entries[hash & (map->capacity - 1)]);
while (entry != NULL) {
if (entry->hash == hash && strcmp(entry->key, key) == 0) {
entry->value = value;
return true;
}
if (entry->next == NULL)
break;
entry = entry->next;
}
if (entry->key == NULL) {
*entry = (map_entry_t){ .key = __strdup(key, map->arena), .hash = hash, .value = value, .next = NULL };
} else {
entry->next = (map_entry_t *)arena_alloc(map->arena, sizeof(map_entry_t));
*entry->next = (map_entry_t){ .key = __strdup(key, map->arena), .hash = hash, .value = value, .next = NULL };
}
return true;
}
void *
map_get(map_t *map, char *key)
{
uint32_t hash = u32_fnv1a_hash(key);
map_entry_t *entry = &map->entries[hash & (map->capacity - 1)];
while (entry != NULL) {
if (entry->hash == hash && strcmp(entry->key, key) == 0) {
return entry->value;
}
entry = entry->next;
}
return NULL;
}
static char *
__strdup(const char *s, arena_t *arena)
{
size_t slen = strlen(s);
char *result = arena_alloc(arena, slen + 1);
if (result == NULL) {
return NULL;
}
memcpy(result, s, slen + 1);
return result;
}
|