1 #ifndef SHEREDOM_HASHMAP_H_INCLUDED
2 #define SHEREDOM_HASHMAP_H_INCLUDED
3
4 #include "tag.h"
5 #include "allocator.h"
6
7 #if defined(_MSC_VER)
8 // Workaround a bug in the MSVC runtime where it uses __cplusplus when not
9 // defined.
10 #pragma warning(push, 0)
11 #pragma warning(disable : 4668)
12 #endif
13 #include <stdlib.h>
14 #include <string.h>
15
16 #if (defined(_MSC_VER) && defined(__AVX__)) || \
17 (!defined(_MSC_VER) && defined(__SSE4_2__))
18 #define HASHMAP_SSE42
19 #endif
20
21 #if defined(HASHMAP_SSE42)
22 #include <nmmintrin.h>
23 #endif
24
25 #if defined(_MSC_VER)
26 #pragma warning(pop)
27 #endif
28
29 #if defined(_MSC_VER)
30 #pragma warning(push)
31 /* Stop MSVC complaining about unreferenced functions */
32 #pragma warning(disable : 4505)
33 /* Stop MSVC complaining about not inlining functions */
34 #pragma warning(disable : 4710)
35 /* Stop MSVC complaining about inlining functions! */
36 #pragma warning(disable : 4711)
37 #elif defined(__clang__)
38 #pragma clang diagnostic push
39 #pragma clang diagnostic ignored "-Wunused-function"
40 #endif
41
42 #if defined(_MSC_VER)
43 #define HASHMAP_USED
44 #elif defined(__GNUC__)
45 #define HASHMAP_USED __attribute__((used))
46 #else
47 #define HASHMAP_USED
48 #endif
49
50 /* We need to keep keys and values. */
51 struct hashmap_element_s {
52 const char *key;
53 unsigned key_len;
54 int in_use;
55 TagType data;
56 };
57
58 /* A hashmap has some maximum size and current size, as well as the data to
59 * hold. */
60 struct hashmap_s {
61 unsigned table_size;
62 unsigned size;
63 struct hashmap_element_s *data;
64 za_Allocator* A;
65 };
66
67 #define HASHMAP_MAX_CHAIN_LENGTH (8)
68
69 #if defined(__cplusplus)
70 extern "C" {
71 #endif
72
73 /// @brief Create a hashmap.
74 /// @param initial_size The initial size of the hashmap. Must be a power of two.
75 /// @param out_hashmap The storage for the created hashmap.
76 /// @return On success 0 is returned.
77 ///
78 /// Note that the initial size of the hashmap must be a power of two, and
79 /// creation of the hashmap will fail if this is not the case.
80 static int hashmap_create(za_Allocator* A, const unsigned initial_size,
81 struct hashmap_s *const out_hashmap) HASHMAP_USED;
82
83 /// @brief Put an element into the hashmap.
84 /// @param hashmap The hashmap to insert into.
85 /// @param key The string key to use.
86 /// @param len The length of the string key.
87 /// @param value The value to insert.
88 /// @return On success 0 is returned.
89 ///
90 /// The key string slice is not copied when creating the hashmap entry, and thus
91 /// must remain a valid pointer until the hashmap entry is removed or the
92 /// hashmap is destroyed.
93 static int hashmap_put(struct hashmap_s *const hashmap, const char *const key,
94 const unsigned len, const TagType value) HASHMAP_USED;
95
96 /// @brief Get an element from the hashmap.
97 /// @param hashmap The hashmap to get from.
98 /// @param key The string key to use.
99 /// @param len The length of the string key.
100 /// @return The previously set element, or NULL if none exists.
101 static TagType hashmap_get(const struct hashmap_s *const hashmap,
102 const char *const key,
103 const unsigned len) HASHMAP_USED;
104
105 /// @brief Remove an element from the hashmap.
106 /// @param hashmap The hashmap to remove from.
107 /// @param key The string key to use.
108 /// @param len The length of the string key.
109 /// @return On success 0 is returned.
110 static int hashmap_remove(struct hashmap_s *const hashmap,
111 const char *const key,
112 const unsigned len) HASHMAP_USED;
113
114 /// @brief Remove an element from the hashmap.
115 /// @param hashmap The hashmap to remove from.
116 /// @param key The string key to use.
117 /// @param len The length of the string key.
118 /// @return On success the original stored key pointer is returned, on failure
119 /// NULL is returned.
120 static const char *
121 hashmap_remove_and_return_key(struct hashmap_s *const hashmap,
122 const char *const key,
123 const unsigned len) HASHMAP_USED;
124
125 /// @brief Iterate over all the elements in a hashmap.
126 /// @param hashmap The hashmap to iterate over.
127 /// @param f The function pointer to call on each element.
128 /// @param context The context to pass as the first argument to f.
129 /// @return If the entire hashmap was iterated then 0 is returned. Otherwise if
130 /// the callback function f returned non-zero then non-zero is returned.
131 static int hashmap_iterate(const struct hashmap_s *const hashmap,
132 int (*f)(void *const context, const TagType value),
133 void *const context) HASHMAP_USED;
134
135 /// @brief Iterate over all the elements in a hashmap.
136 /// @param hashmap The hashmap to iterate over.
137 /// @param f The function pointer to call on each element.
138 /// @param context The context to pass as the first argument to f.
139 /// @return If the entire hashmap was iterated then 0 is returned.
140 /// Otherwise if the callback function f returned positive then the positive
141 /// value is returned. If the callback function returns -1, the current item
142 /// is removed and iteration continues.
143 static int hashmap_iterate_pairs(struct hashmap_s *const hashmap,
144 int (*f)(void *const,
145 struct hashmap_element_s *const),
146 void *const context) HASHMAP_USED;
147
148 /// @brief Get the size of the hashmap.
149 /// @param hashmap The hashmap to get the size of.
150 /// @return The size of the hashmap.
151 static unsigned
152 hashmap_num_entries(const struct hashmap_s *const hashmap) HASHMAP_USED;
153
154 /// @brief Destroy the hashmap.
155 /// @param hashmap The hashmap to destroy.
156 static void hashmap_destroy(struct hashmap_s *const hashmap) HASHMAP_USED;
157
158 static unsigned hashmap_crc32_helper(const char *const s,
159 const unsigned len) HASHMAP_USED;
160 static unsigned hashmap_hash_helper_int_helper(const struct hashmap_s *const m,
161 const char *const keystring,
162 const unsigned len) HASHMAP_USED;
163 static int hashmap_match_helper(const struct hashmap_element_s *const element,
164 const char *const key,
165 const unsigned len) HASHMAP_USED;
166 static int hashmap_hash_helper(const struct hashmap_s *const m,
167 const char *const key, const unsigned len,
168 unsigned *const out_index) HASHMAP_USED;
169 static int
170 hashmap_rehash_iterator(void *const new_hash,
171 struct hashmap_element_s *const e) HASHMAP_USED;
172 static int hashmap_rehash_helper(struct hashmap_s *const m) HASHMAP_USED;
173
174 #if defined(__cplusplus)
175 }
176 #endif
177
178 #if defined(__cplusplus)
179 #define HASHMAP_CAST(type, x) static_cast<type>(x)
180 #define HASHMAP_PTR_CAST(type, x) reinterpret_cast<type>(x)
181 #define HASHMAP_NULL NULL
182 #else
183 #define HASHMAP_CAST(type, x) ((type)x)
184 #define HASHMAP_PTR_CAST(type, x) ((type)x)
185 #define HASHMAP_NULL 0
186 #endif
187
hashmap_create(za_Allocator * A,const unsigned initial_size,struct hashmap_s * const out_hashmap)188 int hashmap_create(za_Allocator* A, const unsigned initial_size,
189 struct hashmap_s *const out_hashmap) {
190 out_hashmap->table_size = initial_size;
191 out_hashmap->size = 0;
192 out_hashmap->A = A;
193
194 if (0 == initial_size || 0 != (initial_size & (initial_size - 1))) {
195 return 1;
196 }
197
198 out_hashmap->data =
199 HASHMAP_CAST(struct hashmap_element_s *,
200 calloc(initial_size, sizeof(struct hashmap_element_s)));
201 if (!out_hashmap->data) {
202 return 1;
203 }
204
205 return 0;
206 }
207
hashmap_put(struct hashmap_s * const m,const char * const key,const unsigned len,const TagType value)208 int hashmap_put(struct hashmap_s *const m, const char *const key,
209 const unsigned len, const TagType value) {
210 unsigned int index;
211
212 /* Find a place to put our value. */
213 while (!hashmap_hash_helper(m, key, len, &index)) {
214 if (hashmap_rehash_helper(m)) {
215 return 1;
216 }
217 }
218
219 /* Set the data. */
220 m->data[index].data = value;
221 m->data[index].key = key;
222 m->data[index].key_len = len;
223
224 /* If the hashmap element was not already in use, set that it is being used
225 * and bump our size. */
226 if (0 == m->data[index].in_use) {
227 m->data[index].in_use = 1;
228 m->size++;
229 }
230
231 return 0;
232 }
233
hashmap_get(const struct hashmap_s * const m,const char * const key,const unsigned len)234 TagType hashmap_get(const struct hashmap_s *const m, const char *const key,
235 const unsigned len) {
236 unsigned int curr;
237 unsigned int i;
238
239 /* Find data location */
240 curr = hashmap_hash_helper_int_helper(m, key, len);
241
242 /* Linear probing, if necessary */
243 for (i = 0; i < HASHMAP_MAX_CHAIN_LENGTH; i++) {
244 if (m->data[curr].in_use) {
245 if (hashmap_match_helper(&m->data[curr], key, len)) {
246 return m->data[curr].data;
247 }
248 }
249
250 curr = (curr + 1) % m->table_size;
251 }
252
253 /* Not found */
254 return HASHMAP_NULL;
255 }
256
hashmap_remove(struct hashmap_s * const m,const char * const key,const unsigned len)257 int hashmap_remove(struct hashmap_s *const m, const char *const key,
258 const unsigned len) {
259 unsigned int i;
260 unsigned int curr;
261
262 /* Find key */
263 curr = hashmap_hash_helper_int_helper(m, key, len);
264
265 /* Linear probing, if necessary */
266 for (i = 0; i < HASHMAP_MAX_CHAIN_LENGTH; i++) {
267 if (m->data[curr].in_use) {
268 if (hashmap_match_helper(&m->data[curr], key, len)) {
269 /* Blank out the fields including in_use */
270 memset(&m->data[curr], 0, sizeof(struct hashmap_element_s));
271
272 /* Reduce the size */
273 m->size--;
274
275 return 0;
276 }
277 }
278
279 curr = (curr + 1) % m->table_size;
280 }
281
282 return 1;
283 }
284
hashmap_remove_and_return_key(struct hashmap_s * const m,const char * const key,const unsigned len)285 const char *hashmap_remove_and_return_key(struct hashmap_s *const m,
286 const char *const key,
287 const unsigned len) {
288 unsigned int i;
289 unsigned int curr;
290
291 /* Find key */
292 curr = hashmap_hash_helper_int_helper(m, key, len);
293
294 /* Linear probing, if necessary */
295 for (i = 0; i < HASHMAP_MAX_CHAIN_LENGTH; i++) {
296 if (m->data[curr].in_use) {
297 if (hashmap_match_helper(&m->data[curr], key, len)) {
298 const char *const stored_key = m->data[curr].key;
299
300 /* Blank out the fields */
301 m->data[curr].in_use = 0;
302 m->data[curr].data = HASHMAP_NULL;
303 m->data[curr].key = HASHMAP_NULL;
304
305 /* Reduce the size */
306 m->size--;
307
308 return stored_key;
309 }
310 }
311 curr = (curr + 1) % m->table_size;
312 }
313
314 return HASHMAP_NULL;
315 }
316
hashmap_iterate(const struct hashmap_s * const m,int (* f)(void * const,TagType const),void * const context)317 int hashmap_iterate(const struct hashmap_s *const m,
318 int (*f)(void *const, TagType const), void *const context) {
319 unsigned int i;
320
321 /* Linear probing */
322 for (i = 0; i < m->table_size; i++) {
323 if (m->data[i].in_use) {
324 if (!f(context, m->data[i].data)) {
325 return 1;
326 }
327 }
328 }
329 return 0;
330 }
331
hashmap_iterate_pairs(struct hashmap_s * const hashmap,int (* f)(void * const,struct hashmap_element_s * const),void * const context)332 int hashmap_iterate_pairs(struct hashmap_s *const hashmap,
333 int (*f)(void *const,
334 struct hashmap_element_s *const),
335 void *const context) {
336 unsigned int i;
337 struct hashmap_element_s *p;
338 int r;
339
340 /* Linear probing */
341 for (i = 0; i < hashmap->table_size; i++) {
342 p = &hashmap->data[i];
343 if (p->in_use) {
344 r = f(context, p);
345 switch (r) {
346 case -1: /* remove item */
347 memset(p, 0, sizeof(struct hashmap_element_s));
348 hashmap->size--;
349 break;
350 case 0: /* continue iterating */
351 break;
352 default: /* early exit */
353 return 1;
354 }
355 }
356 }
357 return 0;
358 }
359
hashmap_destroy(struct hashmap_s * const m)360 void hashmap_destroy(struct hashmap_s *const m) {
361 za_Free(m->A, m->data);
362 memset(m, 0, sizeof(struct hashmap_s));
363 }
364
hashmap_num_entries(const struct hashmap_s * const m)365 unsigned hashmap_num_entries(const struct hashmap_s *const m) {
366 return m->size;
367 }
368
hashmap_crc32_helper(const char * const s,const unsigned len)369 unsigned hashmap_crc32_helper(const char *const s, const unsigned len) {
370 unsigned i;
371 unsigned crc32val = 0;
372
373 #if defined(HASHMAP_SSE42)
374 for (i = 0; i < len; i++) {
375 crc32val = _mm_crc32_u8(crc32val, HASHMAP_CAST(unsigned char, s[i]));
376 }
377
378 return crc32val;
379 #else
380 // Using polynomial 0x11EDC6F41 to match SSE 4.2's crc function.
381 static const unsigned crc32_tab[] = {
382 0x00000000U, 0xF26B8303U, 0xE13B70F7U, 0x1350F3F4U, 0xC79A971FU,
383 0x35F1141CU, 0x26A1E7E8U, 0xD4CA64EBU, 0x8AD958CFU, 0x78B2DBCCU,
384 0x6BE22838U, 0x9989AB3BU, 0x4D43CFD0U, 0xBF284CD3U, 0xAC78BF27U,
385 0x5E133C24U, 0x105EC76FU, 0xE235446CU, 0xF165B798U, 0x030E349BU,
386 0xD7C45070U, 0x25AFD373U, 0x36FF2087U, 0xC494A384U, 0x9A879FA0U,
387 0x68EC1CA3U, 0x7BBCEF57U, 0x89D76C54U, 0x5D1D08BFU, 0xAF768BBCU,
388 0xBC267848U, 0x4E4DFB4BU, 0x20BD8EDEU, 0xD2D60DDDU, 0xC186FE29U,
389 0x33ED7D2AU, 0xE72719C1U, 0x154C9AC2U, 0x061C6936U, 0xF477EA35U,
390 0xAA64D611U, 0x580F5512U, 0x4B5FA6E6U, 0xB93425E5U, 0x6DFE410EU,
391 0x9F95C20DU, 0x8CC531F9U, 0x7EAEB2FAU, 0x30E349B1U, 0xC288CAB2U,
392 0xD1D83946U, 0x23B3BA45U, 0xF779DEAEU, 0x05125DADU, 0x1642AE59U,
393 0xE4292D5AU, 0xBA3A117EU, 0x4851927DU, 0x5B016189U, 0xA96AE28AU,
394 0x7DA08661U, 0x8FCB0562U, 0x9C9BF696U, 0x6EF07595U, 0x417B1DBCU,
395 0xB3109EBFU, 0xA0406D4BU, 0x522BEE48U, 0x86E18AA3U, 0x748A09A0U,
396 0x67DAFA54U, 0x95B17957U, 0xCBA24573U, 0x39C9C670U, 0x2A993584U,
397 0xD8F2B687U, 0x0C38D26CU, 0xFE53516FU, 0xED03A29BU, 0x1F682198U,
398 0x5125DAD3U, 0xA34E59D0U, 0xB01EAA24U, 0x42752927U, 0x96BF4DCCU,
399 0x64D4CECFU, 0x77843D3BU, 0x85EFBE38U, 0xDBFC821CU, 0x2997011FU,
400 0x3AC7F2EBU, 0xC8AC71E8U, 0x1C661503U, 0xEE0D9600U, 0xFD5D65F4U,
401 0x0F36E6F7U, 0x61C69362U, 0x93AD1061U, 0x80FDE395U, 0x72966096U,
402 0xA65C047DU, 0x5437877EU, 0x4767748AU, 0xB50CF789U, 0xEB1FCBADU,
403 0x197448AEU, 0x0A24BB5AU, 0xF84F3859U, 0x2C855CB2U, 0xDEEEDFB1U,
404 0xCDBE2C45U, 0x3FD5AF46U, 0x7198540DU, 0x83F3D70EU, 0x90A324FAU,
405 0x62C8A7F9U, 0xB602C312U, 0x44694011U, 0x5739B3E5U, 0xA55230E6U,
406 0xFB410CC2U, 0x092A8FC1U, 0x1A7A7C35U, 0xE811FF36U, 0x3CDB9BDDU,
407 0xCEB018DEU, 0xDDE0EB2AU, 0x2F8B6829U, 0x82F63B78U, 0x709DB87BU,
408 0x63CD4B8FU, 0x91A6C88CU, 0x456CAC67U, 0xB7072F64U, 0xA457DC90U,
409 0x563C5F93U, 0x082F63B7U, 0xFA44E0B4U, 0xE9141340U, 0x1B7F9043U,
410 0xCFB5F4A8U, 0x3DDE77ABU, 0x2E8E845FU, 0xDCE5075CU, 0x92A8FC17U,
411 0x60C37F14U, 0x73938CE0U, 0x81F80FE3U, 0x55326B08U, 0xA759E80BU,
412 0xB4091BFFU, 0x466298FCU, 0x1871A4D8U, 0xEA1A27DBU, 0xF94AD42FU,
413 0x0B21572CU, 0xDFEB33C7U, 0x2D80B0C4U, 0x3ED04330U, 0xCCBBC033U,
414 0xA24BB5A6U, 0x502036A5U, 0x4370C551U, 0xB11B4652U, 0x65D122B9U,
415 0x97BAA1BAU, 0x84EA524EU, 0x7681D14DU, 0x2892ED69U, 0xDAF96E6AU,
416 0xC9A99D9EU, 0x3BC21E9DU, 0xEF087A76U, 0x1D63F975U, 0x0E330A81U,
417 0xFC588982U, 0xB21572C9U, 0x407EF1CAU, 0x532E023EU, 0xA145813DU,
418 0x758FE5D6U, 0x87E466D5U, 0x94B49521U, 0x66DF1622U, 0x38CC2A06U,
419 0xCAA7A905U, 0xD9F75AF1U, 0x2B9CD9F2U, 0xFF56BD19U, 0x0D3D3E1AU,
420 0x1E6DCDEEU, 0xEC064EEDU, 0xC38D26C4U, 0x31E6A5C7U, 0x22B65633U,
421 0xD0DDD530U, 0x0417B1DBU, 0xF67C32D8U, 0xE52CC12CU, 0x1747422FU,
422 0x49547E0BU, 0xBB3FFD08U, 0xA86F0EFCU, 0x5A048DFFU, 0x8ECEE914U,
423 0x7CA56A17U, 0x6FF599E3U, 0x9D9E1AE0U, 0xD3D3E1ABU, 0x21B862A8U,
424 0x32E8915CU, 0xC083125FU, 0x144976B4U, 0xE622F5B7U, 0xF5720643U,
425 0x07198540U, 0x590AB964U, 0xAB613A67U, 0xB831C993U, 0x4A5A4A90U,
426 0x9E902E7BU, 0x6CFBAD78U, 0x7FAB5E8CU, 0x8DC0DD8FU, 0xE330A81AU,
427 0x115B2B19U, 0x020BD8EDU, 0xF0605BEEU, 0x24AA3F05U, 0xD6C1BC06U,
428 0xC5914FF2U, 0x37FACCF1U, 0x69E9F0D5U, 0x9B8273D6U, 0x88D28022U,
429 0x7AB90321U, 0xAE7367CAU, 0x5C18E4C9U, 0x4F48173DU, 0xBD23943EU,
430 0xF36E6F75U, 0x0105EC76U, 0x12551F82U, 0xE03E9C81U, 0x34F4F86AU,
431 0xC69F7B69U, 0xD5CF889DU, 0x27A40B9EU, 0x79B737BAU, 0x8BDCB4B9U,
432 0x988C474DU, 0x6AE7C44EU, 0xBE2DA0A5U, 0x4C4623A6U, 0x5F16D052U,
433 0xAD7D5351U};
434
435 for (i = 0; i < len; i++) {
436 crc32val = crc32_tab[(HASHMAP_CAST(unsigned char, crc32val) ^
437 HASHMAP_CAST(unsigned char, s[i]))] ^
438 (crc32val >> 8);
439 }
440 return crc32val;
441 #endif
442 }
443
hashmap_hash_helper_int_helper(const struct hashmap_s * const m,const char * const keystring,const unsigned len)444 unsigned hashmap_hash_helper_int_helper(const struct hashmap_s *const m,
445 const char *const keystring,
446 const unsigned len) {
447 unsigned key = hashmap_crc32_helper(keystring, len);
448
449 /* Robert Jenkins' 32 bit Mix Function */
450 key += (key << 12);
451 key ^= (key >> 22);
452 key += (key << 4);
453 key ^= (key >> 9);
454 key += (key << 10);
455 key ^= (key >> 2);
456 key += (key << 7);
457 key ^= (key >> 12);
458
459 /* Knuth's Multiplicative Method */
460 key = (key >> 3) * 2654435761;
461
462 return key % m->table_size;
463 }
464
hashmap_match_helper(const struct hashmap_element_s * const element,const char * const key,const unsigned len)465 int hashmap_match_helper(const struct hashmap_element_s *const element,
466 const char *const key, const unsigned len) {
467 return (element->key_len == len) && (0 == memcmp(element->key, key, len));
468 }
469
hashmap_hash_helper(const struct hashmap_s * const m,const char * const key,const unsigned len,unsigned * const out_index)470 int hashmap_hash_helper(const struct hashmap_s *const m, const char *const key,
471 const unsigned len, unsigned *const out_index) {
472 unsigned int start, curr;
473 unsigned int i;
474 int total_in_use;
475
476 /* If full, return immediately */
477 if (m->size >= m->table_size) {
478 return 0;
479 }
480
481 /* Find the best index */
482 curr = start = hashmap_hash_helper_int_helper(m, key, len);
483
484 /* First linear probe to check if we've already insert the element */
485 total_in_use = 0;
486
487 for (i = 0; i < HASHMAP_MAX_CHAIN_LENGTH; i++) {
488 const int in_use = m->data[curr].in_use;
489
490 total_in_use += in_use;
491
492 if (in_use && hashmap_match_helper(&m->data[curr], key, len)) {
493 *out_index = curr;
494 return 1;
495 }
496
497 curr = (curr + 1) % m->table_size;
498 }
499
500 curr = start;
501
502 /* Second linear probe to actually insert our element (only if there was at
503 * least one empty entry) */
504 if (HASHMAP_MAX_CHAIN_LENGTH > total_in_use) {
505 for (i = 0; i < HASHMAP_MAX_CHAIN_LENGTH; i++) {
506 if (!m->data[curr].in_use) {
507 *out_index = curr;
508 return 1;
509 }
510
511 curr = (curr + 1) % m->table_size;
512 }
513 }
514
515 return 0;
516 }
517
hashmap_rehash_iterator(void * const new_hash,struct hashmap_element_s * const e)518 int hashmap_rehash_iterator(void *const new_hash,
519 struct hashmap_element_s *const e) {
520 int temp = hashmap_put(HASHMAP_PTR_CAST(struct hashmap_s *, new_hash), e->key,
521 e->key_len, e->data);
522 if (0 < temp) {
523 return 1;
524 }
525 /* clear old value to avoid stale pointers */
526 return -1;
527 }
528 /*
529 * Doubles the size of the hashmap, and rehashes all the elements
530 */
hashmap_rehash_helper(struct hashmap_s * const m)531 int hashmap_rehash_helper(struct hashmap_s *const m) {
532 /* If this multiplication overflows hashmap_create will fail. */
533 unsigned new_size = 2 * m->table_size;
534
535 struct hashmap_s new_hash;
536
537 int flag = hashmap_create(m->A, new_size, &new_hash);
538
539 if (0 != flag) {
540 return flag;
541 }
542
543 /* copy the old elements to the new table */
544 flag = hashmap_iterate_pairs(m, hashmap_rehash_iterator,
545 HASHMAP_PTR_CAST(void *, &new_hash));
546
547 if (0 != flag) {
548 return flag;
549 }
550
551 hashmap_destroy(m);
552 /* put new hash into old hash structure by copying */
553 memcpy(m, &new_hash, sizeof(struct hashmap_s));
554
555 return 0;
556 }
557
558 #if defined(_MSC_VER)
559 #pragma warning(pop)
560 #elif defined(__clang__)
561 #pragma clang diagnostic pop
562 #endif
563 //--------------------------------------
564
565 // for a name
for_name(za_Allocator * A,struct hashmap_s * m,const ekstring * name)566 Tag *for_name(za_Allocator *A, struct hashmap_s *m, const ekstring *name) {
567 TagType type = hashmap_get(m, name->buf, name->length);
568 if (type != 0) {
569 Tag *t = (Tag *)za_Alloc(A, sizeof(Tag));
570 t->type = type;
571 t->custom_tag_name = (ekstring){NULL, 0, A};
572 return t;
573 } else {
574 return initTagArgs(A, CUSTOM, *name);
575 }
576 }
577
578 // init tags-hashmap
get_tag_map(za_Allocator * AA)579 const struct hashmap_s *get_tag_map(za_Allocator *AA) {
580 struct hashmap_s *data =
581 (struct hashmap_s *)za_Alloc(AA, sizeof(struct hashmap_s));
582 int res = hashmap_create(AA, 1024, data);
583
584 if (res == 0) {
585 #define TAG(name, str) hashmap_put(data, str, strlen(str), (name))
586 TAG(AREA, "area");
587 TAG(BASE, "base");
588 TAG(BASEFONT, "basefont");
589 TAG(BGSOUND, "bgsound");
590 TAG(BR, "br");
591 TAG(COL, "col");
592 TAG(COMMAND, "command");
593 TAG(EMBED, "embed");
594 TAG(FRAME, "frame");
595 TAG(HR, "hr");
596 TAG(IMAGE, "image");
597 TAG(IMG, "img");
598 TAG(INPUT, "input");
599 TAG(ISINDEX, "isindex");
600 TAG(KEYGEN, "keygen");
601 TAG(LINK, "link");
602 TAG(MENUITEM, "menuitem");
603 TAG(META, "meta");
604 TAG(NEXTID, "nextid");
605 TAG(PARAM, "param");
606 TAG(SOURCE, "source");
607 TAG(TRACK, "track");
608 TAG(WBR, "wbr");
609 TAG(A, "a");
610 TAG(ABBR, "bbr");
611 TAG(ADDRESS, "address");
612 TAG(ARTICLE, "article");
613 TAG(ASIDE, "aside");
614 TAG(AUDIO, "audio");
615 TAG(B, "b");
616 TAG(BDI, "di");
617 TAG(BDO, "bdo");
618 TAG(BLOCKQUOTE, "blockquote");
619 TAG(BODY, "body");
620 TAG(BUTTON, "button");
621 TAG(CANVAS, "canvas");
622 TAG(CAPTION, "caption");
623 TAG(CITE, "cite");
624 TAG(CODE, "code");
625 TAG(COLGROUP, "colgroup");
626 TAG(DATA, "data");
627 TAG(DATALIST, "datalist");
628 TAG(DD, "dd");
629 TAG(DEL, "del");
630 TAG(DETAILS, "details");
631 TAG(DFN, "dfn");
632 TAG(DIALOG, "dialog");
633 TAG(DIV, "div");
634 TAG(DL, "dl");
635 TAG(DT, "dt");
636 TAG(EM, "em");
637 TAG(FIELDSET, "fieldset");
638 TAG(FIGCAPTION, "figcaption");
639 TAG(FIGURE, "figure");
640 TAG(FOOTER, "footer");
641 TAG(FORM, "form");
642 TAG(H1, "h1");
643 TAG(H2, "h2");
644 TAG(H3, "h3");
645 TAG(H4, "h4");
646 TAG(H5, "h5");
647 TAG(H6, "h6");
648 TAG(HEAD, "head");
649 TAG(HEADER, "header");
650 TAG(HGROUP, "hgroup");
651 TAG(HTML, "html");
652 TAG(I, "i");
653 TAG(IFRAME, "frame");
654 TAG(INS, "ins");
655 TAG(KBD, "kbd");
656 TAG(LABEL, "label");
657 TAG(LEGEND, "legend");
658 TAG(LI, "li");
659 TAG(MAIN, "main");
660 TAG(MAP, "map");
661 TAG(MARK, "mark");
662 TAG(MATH, "math");
663 TAG(MENU, "menu");
664 TAG(METER, "meter");
665 TAG(NAV, "nav");
666 TAG(NOSCRIPT, "noscript");
667 TAG(OBJECT, "object");
668 TAG(OL, "ol");
669 TAG(OPTGROUP, "optgroup");
670 TAG(OPTION, "option");
671 TAG(OUTPUT, "output");
672 TAG(P, "p");
673 TAG(PICTURE, "picture");
674 TAG(PRE, "pre");
675 TAG(PROGRESS, "progress");
676 TAG(Q, "q");
677 TAG(RB, "rb");
678 TAG(RP, "RP");
679 TAG(RT, "rt");
680 TAG(RTC, "rtc");
681 TAG(RUBY, "ruby");
682 TAG(S, "s");
683 TAG(SAMP, "samp");
684 TAG(SCRIPT, "script");
685 TAG(SECTION, "section");
686 TAG(SELECT, "select");
687 TAG(SLOT, "slot");
688 TAG(SMALL, "small");
689 TAG(SPAN, "span");
690 TAG(STRONG, "strong");
691 TAG(STYLE, "style");
692 TAG(SUB, "sub");
693 TAG(SUMMARY, "summary");
694 TAG(SUP, "sup");
695 TAG(SVG, "svg");
696 TAG(TABLE, "table");
697 TAG(TBODY, "tbody");
698 TAG(TD, "td");
699 TAG(TEMPLATE, "template");
700 TAG(TEXTAREA, "textarea");
701 TAG(TFOOT, "tfoot");
702 TAG(TH, "th");
703 TAG(THEAD, "thead");
704 TAG(TIME, "time");
705 TAG(TITLE, "title");
706 TAG(TR, "tr");
707 TAG(U, "u");
708 TAG(UL, "ul");
709 TAG(VAR, "var");
710 TAG(VIDEO, "video");
711 // TAG(CUSTOM);
712 #undef TAG
713 }
714 return data;
715 }
716
717 #endif
718