1#include "table.h"
2
3#include <assert.h>
4#include <stdlib.h> /* malloc */
5#include <string.h>
6
7/* fnv-1a */
8static uint32_t
9hash_string(const char *key, int length)
10{
11 const unsigned char *u = (const unsigned char *)key;
12 uint32_t hash = 2166136261u;
13 int i;
14
15 for (i = 0; i < length; ++i)
16 hash = (hash ^ u[i]) * 16777619u;
17 return hash;
18}
19
20/* struct name: global interning table */
21
22static struct Table name_table;
23
24static const struct Name *
25find_name_table(const char *chars, int bytes, uint32_t hash)
26{
27 const struct Table *table;
28 uint32_t index;
29 struct TableEntry *entry;
30 const struct Name *key;
31
32 table = &name_table;
33 if (table->count == 0)
34 return NULL;
35
36 for (index = hash % table->capacity;; index = (index + 1) % table->capacity) {
37 entry = &table->entries[index];
38 key = entry->key;
39 if (key == NULL) {
40 if (entry->value == NULL)
41 return NULL;
42 } else if (key->bytes == bytes && key->hash == hash && memcmp(key->chars, chars, bytes) == 0) {
43 return key;
44 }
45 }
46}
47
48const struct Name *
49alloc_name(const char *begin, const char *end, int make_copy)
50{
51 int bytes;
52 uint32_t hash;
53 const struct Name *name;
54 char *new_str;
55 struct Name *new_name;
56
57 bytes = end != NULL ? (int)(end - begin) : (int)strlen(begin);
58 hash = hash_string(begin, bytes);
59 name = find_name_table(begin, bytes, hash);
60 if (name == NULL) {
61 if (make_copy) {
62 new_str = malloc(bytes);
63 if (new_str == NULL)
64 return NULL;
65 memcpy(new_str, begin, bytes);
66 begin = new_str;
67 }
68 new_name = malloc(sizeof(*new_name));
69 if (new_name == NULL) {
70 if (make_copy)
71 free((void *)begin);
72 } else {
73 new_name->chars = begin;
74 new_name->bytes = bytes;
75 new_name->hash = hash;
76 table_put(&name_table, new_name, new_name);
77 name = new_name;
78 }
79 }
80 return name;
81}
82
83const struct Name *
84alloc_cname(const char *cstr)
85{
86 return alloc_name(cstr, NULL, 0);
87}
88
89int
90equal_name(const struct Name *name1, const struct Name *name2)
91{
92 /* all names are interned, compare by pointer */
93 return name1 == name2;
94}
95
96/* struct table: open-addressing hash table */
97
98static struct TableEntry *
99find_entry(struct TableEntry *entries, int capacity, const struct Name *key)
100{
101 struct TableEntry *tombstone;
102 uint32_t index;
103 struct TableEntry *entry;
104
105 tombstone = NULL;
106 for (index = key->hash % capacity;; index = (index + 1) % capacity) {
107 entry = &entries[index];
108 if (entry->key == NULL) {
109 if (entry->value == NULL)
110 return tombstone != NULL ? tombstone : entry;
111 /* tombstone */
112 if (tombstone == NULL)
113 tombstone = entry;
114 } else if (entry->key == key) {
115 return entry;
116 }
117 }
118}
119
120static void
121adjust_capacity(struct Table *table, int new_capacity)
122{
123 struct TableEntry *new_entries;
124 int i;
125 struct TableEntry *old_entries;
126 int old_capacity;
127 int new_count;
128
129 new_entries = malloc(sizeof(struct TableEntry) * new_capacity);
130 if (new_entries == NULL)
131 return;
132 for (i = 0; i < new_capacity; ++i) {
133 new_entries[i].key = NULL;
134 new_entries[i].value = NULL;
135 }
136
137 old_entries = table->entries;
138 old_capacity = table->capacity;
139 new_count = 0;
140 for (i = 0; i < old_capacity; ++i) {
141 struct TableEntry *entry;
142 struct TableEntry *dest;
143
144 entry = &old_entries[i];
145 if (entry->key == NULL)
146 continue;
147
148 dest = find_entry(new_entries, new_capacity, entry->key);
149 dest->key = entry->key;
150 dest->value = entry->value;
151 ++new_count;
152 }
153
154 free(old_entries);
155 table->entries = new_entries;
156 table->capacity = new_capacity;
157 table->count = table->used = new_count;
158}
159
160struct Table *
161alloc_table(void)
162{
163 struct Table *table = malloc(sizeof(*table));
164 if (table != NULL)
165 table_init(table);
166 return table;
167}
168
169void
170table_init(struct Table *table)
171{
172 assert(table != NULL);
173 table->entries = NULL;
174 table->count = 0;
175 table->used = 0;
176 table->capacity = 0;
177}
178
179void *
180table_get(struct Table *table, const struct Name *key)
181{
182 struct TableEntry *entry;
183
184 assert(table != NULL);
185 if (table->count == 0)
186 return NULL;
187
188 entry = find_entry(table->entries, table->capacity, key);
189 if (entry->key == NULL)
190 return NULL;
191
192 return entry->value;
193}
194
195int
196table_try_get(struct Table *table, const struct Name *key, void **output)
197{
198 struct TableEntry *entry;
199
200 assert(table != NULL);
201 if (table->count == 0)
202 return 0;
203
204 entry = find_entry(table->entries, table->capacity, key);
205 if (entry->key == NULL)
206 return 0;
207
208 if (output != NULL)
209 *output = entry->value;
210 return 1;
211}
212
213int
214table_put(struct Table *table, const struct Name *key, void *value)
215{
216 const int min_capacity = 15;
217 int capacity;
218 struct TableEntry *entry;
219 int is_new_key;
220
221 assert(table != NULL);
222 if (table->used >= table->capacity / 2) {
223 capacity = table->capacity * 2 - 1; /* keep odd */
224 if (capacity < min_capacity)
225 capacity = min_capacity;
226 adjust_capacity(table, capacity);
227 }
228
229 entry = find_entry(table->entries, table->capacity, key);
230 is_new_key = entry->key == NULL;
231 if (is_new_key) {
232 ++table->count;
233 if (entry->value == NULL)
234 ++table->used;
235 }
236
237 entry->key = key;
238 entry->value = value;
239 return is_new_key;
240}
241
242int
243table_delete(struct Table *table, const struct Name *key)
244{
245 struct TableEntry *entry;
246
247 assert(table != NULL);
248 if (table->count == 0)
249 return 0;
250
251 entry = find_entry(table->entries, table->capacity, key);
252 if (entry->key == NULL)
253 return 0;
254
255 --table->count;
256 /* mark as tombstone */
257 entry->key = NULL;
258 entry->value = entry;
259
260 return 1;
261}
262
263int
264table_iterate(const struct Table *table, int iterator, const struct Name **pkey, void **pvalue)
265{
266 int capacity;
267 const struct TableEntry *entry;
268 const struct Name *key;
269
270 assert(table != NULL);
271 capacity = table->capacity;
272 for (; iterator < capacity; ++iterator) {
273 entry = &table->entries[iterator];
274 key = entry->key;
275 if (key != NULL) {
276 if (pkey != NULL)
277 *pkey = key;
278 if (pvalue != NULL)
279 *pvalue = entry->value;
280 return iterator + 1;
281 }
282 }
283 return -1;
284}
