Nilorea Library
C utilities for networking, threading, graphics
Loading...
Searching...
No Matches
n_hash.c
Go to the documentation of this file.
1/*
2 * Nilorea Library
3 * Copyright (C) 2005-2026 Castagnier Mickael
4 *
5 * Licensed under the Apache License, Version 2.0 (the "License");
6 * you may not use this file except in compliance with the License.
7 * You may obtain a copy of the License at
8 *
9 * http://www.apache.org/licenses/LICENSE-2.0
10 *
11 * Unless required by applicable law or agreed to in writing, software
12 * distributed under the License is distributed on an "AS IS" BASIS,
13 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or
14 * implied. See the License for the specific language governing
15 * permissions and limitations under the License.
16 *
17 * SPDX-License-Identifier: Apache-2.0
18 */
19
27
28#include "nilorea/n_common.h"
29#include "nilorea/n_log.h"
30#include "nilorea/n_hash.h"
31#include "nilorea/n_str.h"
32
33#include <fcntl.h>
34#include <pthread.h>
35#include <string.h>
36#include <strings.h>
37#include <time.h>
38#include <unistd.h>
39#if defined(__GLIBC__) && (__GLIBC__ > 2 || (__GLIBC__ == 2 && __GLIBC_MINOR__ >= 25))
40#include <sys/random.h>
41#define N_HASH_HAVE_GETRANDOM 1
42#endif
43
44#ifdef __windows__
45#include <winsock.h>
46/* n_windows.h comes first: bcrypt.h uses LONG/ULONG without defining them;
47 * link with -lbcrypt (in the Windows CLIBS) */
48#include "nilorea/n_windows.h"
49#include <bcrypt.h>
50#else
51#include <arpa/inet.h>
52#endif
53
54/* Trie tree tables */
55
63 __n_assert(table, return NULL);
64
65 HASH_NODE* new_hash_node = NULL;
66 Malloc(new_hash_node, HASH_NODE, 1);
67 __n_assert(new_hash_node, n_log(LOG_ERR, "Could not allocate new_hash_node"); return NULL);
68 new_hash_node->key = NULL;
69 new_hash_node->hash_value = 0;
70 new_hash_node->data.ptr = NULL;
71 new_hash_node->destroy_func = NULL;
72 new_hash_node->children = NULL;
73 new_hash_node->is_leaf = 0;
74 new_hash_node->need_rehash = 0;
75 new_hash_node->alphabet_length = table->alphabet_length;
76
77 Malloc(new_hash_node->children, HASH_NODE*, table->alphabet_length);
78 __n_assert(new_hash_node->children, n_log(LOG_ERR, "Could not allocate new_hash_node"); Free(new_hash_node); return NULL);
79
80 /* n_log( LOG_DEBUG , "node: %d %c table: alpha: %d / offset %d" , key , key , table -> alphabet_length , table -> alphabet_offset ); */
81
82 for (size_t it = 0; it < table->alphabet_length; it++) {
83 new_hash_node->children[it] = NULL;
84 }
85 new_hash_node->is_leaf = 0;
86 new_hash_node->key_id = key;
87 return new_hash_node;
88} /* _ht_new_node_trie(...) */
89
96int _ht_is_leaf_node_trie(HASH_TABLE* table, const char* key) {
97 __n_assert(table, return -1);
98
99 /* checks if the prefix match of key and root is a leaf node */
100 HASH_NODE* node = table->root;
101 for (size_t it = 0; key[it]; it++) {
102 size_t index = (size_t)key[it] - table->alphabet_offset;
103 if (index >= table->alphabet_length) {
104 n_log(LOG_ERR, "Invalid value %zu for charater at position %zu of %s, set to 0", index, it, key);
105 index = 0;
106 }
107 if (node->children[index]) {
108 node = node->children[index];
109 } else {
110 return 0;
111 }
112 }
113 return node->is_leaf;
114} /* _ht_is_leaf_node_trie(...) */
115
120void _ht_node_destroy(void* node) {
121 HASH_NODE* node_ptr = (HASH_NODE*)node;
122 __n_assert(node_ptr, return);
123 if (node_ptr->type == HASH_STRING) {
124 Free(node_ptr->data.string);
125 }
126 if (node_ptr->type == HASH_PTR) {
127 if (node_ptr->destroy_func && node_ptr->data.ptr) {
128 node_ptr->destroy_func(node_ptr->data.ptr);
129 }
130 /* No free by default. must be passed as a destroy_func
131 else
132 {
133 Free( node_ptr -> data . ptr );
134 }
135 */
136 }
137 FreeNoLog(node_ptr->key);
138 if (node_ptr->alphabet_length > 0) {
139 for (size_t it = 0; it < node_ptr->alphabet_length; it++) {
140 if (node_ptr->children[it]) {
141 _ht_node_destroy(node_ptr->children[it]);
142 }
143 }
144 Free(node_ptr->children);
145 }
146 Free(node_ptr);
147} /* _ht_node_destroy */
148
155size_t _ht_check_trie_divergence(HASH_TABLE* table, const char* key) {
156 __n_assert(table, return SIZE_MAX);
157 __n_assert(key, return SIZE_MAX);
158 __n_assert(table->root, return SIZE_MAX);
159
160 HASH_NODE* node = table->root;
161
162 size_t last_index = 0;
163 /* `node` is non-null on entry (table->root checked above) and only ever
164 * gets reassigned from `node->children[index]` after that slot was
165 * verified non-null. We still gate the loop on `node` so the static
166 * analyzer narrows `node` to non-null at every dereference inside the
167 * body, older clang static analyzers (the one in Ubuntu's clang-tools
168 * package, used by CI) don't track that constraint through the
169 * children[] reassignment, even though it holds. */
170 for (size_t it = 0; node && key[it] != '\0'; it++) {
171 size_t index = (size_t)key[it] - table->alphabet_offset;
172 if (index >= table->alphabet_length) {
173 n_log(LOG_ERR, "Invalid value %zu for charater at position %zu of %s, set to 0", index, it, key);
174 index = 0;
175 }
176 HASH_NODE* child = node->children[index];
177 if (child) {
178 /* child check */
179 for (size_t it2 = 0; it2 < table->alphabet_length; it2++) {
180 if (it2 != (unsigned)index && node->children[it2]) {
181 /* child found, update branch index */
182 last_index = it + 1;
183 break;
184 }
185 }
186 /* Go to the next child in the sequence */
187 node = child;
188 }
189 }
190 return last_index;
191} /* _ht_check_trie_divergence(...) */
192
199char* _ht_find_longest_prefix_trie(HASH_TABLE* table, const char* key) {
200 __n_assert(table, return NULL);
201 __n_assert(key, return NULL);
202
203 size_t len = strlen(key);
204
205 /* start with full key and backtrack to search for divergences */
206 char* longest_prefix = NULL;
207 Malloc(longest_prefix, char, len + 1);
208 __n_assert(longest_prefix, return NULL);
209 memcpy(longest_prefix, key, len);
210 /* memcpy does not add a null terminator; set it explicitly */
211 longest_prefix[len] = '\0';
212
213 /* check branching from the root */
214 size_t branch_index = _ht_check_trie_divergence(table, longest_prefix);
215 if (branch_index > 0 && branch_index != SIZE_MAX) {
216 /* truncate to the branch point */
217 longest_prefix[branch_index - 1] = '\0';
218 /* shrink the allocation; Realloc preserves the original pointer on
219 failure so the caller still gets a valid terminated string */
220 Realloc(longest_prefix, char, branch_index + 1);
221 }
222 return longest_prefix;
223} /* _ht_find_longest_prefix_trie(...) */
224
231int _ht_remove_trie(HASH_TABLE* table, const char* key) {
232 __n_assert(table, return FALSE);
233 __n_assert(table->root, return FALSE);
234 __n_assert(key, return FALSE);
235
236 /* stop if matching node not a leaf node */
237 if (!_ht_is_leaf_node_trie(table, key)) {
238 return FALSE;
239 }
240
241 HASH_NODE* node = table->root;
242 /* find the longest prefix string that is not the current key */
243 char* longest_prefix = _ht_find_longest_prefix_trie(table, key);
244 if (!longest_prefix) {
245 n_log(LOG_ERR, "couldn't find longest prefix for key %s", key);
246 return FALSE;
247 }
248 if (longest_prefix[0] == '\0') {
249 Free(longest_prefix);
250 return FALSE;
251 }
252 /* keep track of position in the tree */
253 size_t it = 0;
254 for (it = 0; longest_prefix[it] != '\0'; it++) {
255 size_t index = (size_t)longest_prefix[it] - table->alphabet_offset;
256 if (index >= table->alphabet_length) {
257 n_log(LOG_ERR, "Invalid value %zu for charater at position %zu of %s, set to 0", index, it, key);
258 index = 0;
259 }
260 if (node->children[index] != NULL) {
261 /* common prefix, keep moving */
262 node = node->children[index];
263 } else {
264 /* not found */
265 Free(longest_prefix);
266 return FALSE;
267 }
268 }
269 /* deepest common node between the two strings */
270 /* deleting the sequence corresponding to key */
271 for (; key[it] != '\0'; it++) {
272 size_t index = (size_t)key[it] - table->alphabet_offset;
273 if (index >= table->alphabet_length) {
274 n_log(LOG_ERR, "Invalid value %zu for charater at position %zu of %s, set to 0", index, it, key);
275 index = 0;
276 }
277 if (node->children[index]) {
278 /* delete the remaining sequence */
279 HASH_NODE* node_to_kill = node->children[index];
280 node->children[index] = NULL;
281 _ht_node_destroy(node_to_kill);
282 }
283 }
284 Free(longest_prefix);
285
286 table->nb_keys--;
287
288 return TRUE;
289} /* _ht_remove_trie(...) */
290
298int _ht_put_int_trie(HASH_TABLE* table, const char* key, HASH_INT_TYPE value) {
299 __n_assert(table, return FALSE);
300 __n_assert(key, return FALSE);
301
302 HASH_NODE* node = table->root;
303
304 for (size_t it = 0; key[it] != '\0'; it++) {
305 size_t index = (size_t)key[it] - table->alphabet_offset;
306 if (index >= table->alphabet_length) {
307 n_log(LOG_ERR, "Invalid value %zu for charater at position %zu of %s, set to 0", index, it, key);
308 index = 0;
309 }
310 /* n_log( LOG_DEBUG , "index:%d" , index ); */
311 if (node->children[index] == NULL) {
312 /* create a node */
313 node->children[index] = _ht_new_node_trie(table, key[it]);
314 __n_assert(node->children[index], return FALSE);
315 } else {
316 /* nothing to do since node is existing */
317 }
318 /* go down a level, to the child referenced by index */
319 node = node->children[index];
320 }
321 /* At the end of the key, mark this node as the leaf node */
322 int was_leaf = node->is_leaf;
323 if (was_leaf) {
324 FreeNoLog(node->key);
325 }
326 node->is_leaf = 1;
327 /* Put the key */
328 node->key = strdup(key);
329 if (!node->key) {
330 n_log(LOG_ERR, "strdup failure for key [%s]", key);
331 table->nb_keys++; /* compensate for upcoming remove */
332 _ht_remove_trie(table, key);
333 return FALSE;
334 }
335 /* Put the value */
336 node->data.ival = value;
337 node->type = HASH_INT;
338
339 if (!was_leaf) {
340 table->nb_keys++;
341 }
342
343 return TRUE;
344} /* _ht_put_int_trie(...) */
345
353int _ht_put_double_trie(HASH_TABLE* table, const char* key, double value) {
354 __n_assert(table, return FALSE);
355 __n_assert(key, return FALSE);
356
357 HASH_NODE* node = table->root;
358
359 for (size_t it = 0; key[it] != '\0'; it++) {
360 size_t index = (size_t)key[it] - table->alphabet_offset;
361 if (index >= table->alphabet_length) {
362 n_log(LOG_ERR, "Invalid value %zu for charater at position %zu of %s, set to 0", index, it, key);
363 index = 0;
364 }
365 if (node->children[index] == NULL) {
366 /* create a node */
367 node->children[index] = _ht_new_node_trie(table, key[it]);
368 __n_assert(node->children[index], return FALSE);
369 } else {
370 /* nothing to do since node is existing */
371 }
372 /* go down a level, to the child referenced by index */
373 node = node->children[index];
374 }
375 /* At the end of the key, mark this node as the leaf node */
376 int was_leaf = node->is_leaf;
377 if (was_leaf) {
378 FreeNoLog(node->key);
379 }
380 node->is_leaf = 1;
381 /* Put the key */
382 node->key = strdup(key);
383 if (!node->key) {
384 n_log(LOG_ERR, "strdup failure for key [%s]", key);
385 table->nb_keys++; /* compensate for upcoming remove */
386 _ht_remove_trie(table, key);
387 return FALSE;
388 }
389 /* Put the value */
390 node->data.fval = value;
391 node->type = HASH_DOUBLE;
392
393 if (!was_leaf) {
394 table->nb_keys++;
395 }
396
397 return TRUE;
398} /* _ht_put_double_trie(...) */
399
407// cppcheck-suppress constParameterCallback ; callback signature must match typedef
408int _ht_put_string_trie(HASH_TABLE* table, const char* key, char* string) {
409 __n_assert(table, return FALSE);
410 __n_assert(key, return FALSE);
411
412 HASH_NODE* node = table->root;
413
414 for (size_t it = 0; key[it] != '\0'; it++) {
415 size_t index = (size_t)key[it] - table->alphabet_offset;
416 if (index >= table->alphabet_length) {
417 n_log(LOG_ERR, "Invalid value %zu for charater at position %zu of %s, set to 0", index, it, key);
418 index = 0;
419 }
420 if (node->children[index] == NULL) {
421 /* create a node */
422 node->children[index] = _ht_new_node_trie(table, key[it]);
423 __n_assert(node->children[index], return FALSE);
424 } else {
425 /* nothing to do since node is existing */
426 }
427 /* go down a level, to the child referenced by index */
428 node = node->children[index];
429 }
430 /* At the end of the key, mark this node as the leaf node */
431 int was_leaf = node->is_leaf;
432 if (was_leaf) {
433 FreeNoLog(node->key);
434 FreeNoLog(node->data.string);
435 }
436 node->is_leaf = 1;
437 /* Put the key */
438 node->key = strdup(key);
439 if (!node->key) {
440 n_log(LOG_ERR, "strdup failure for key [%s]", key);
441 table->nb_keys++; /* compensate for upcoming remove */
442 _ht_remove_trie(table, key);
443 return FALSE;
444 }
445 /* Put the value */
446 if (string) {
447 node->data.string = strdup(string);
448 if (!node->data.string) {
449 n_log(LOG_ERR, "strdup failure for value at key [%s]", key);
450 Free(node->key);
451 table->nb_keys++; /* compensate for upcoming remove */
452 _ht_remove_trie(table, key);
453 return FALSE;
454 }
455 } else {
456 node->data.string = NULL;
457 }
458
459 node->type = HASH_STRING;
460
461 if (!was_leaf) {
462 table->nb_keys++;
463 }
464
465 return TRUE;
466} /* _ht_put_string_trie(...) */
467
475int _ht_put_string_ptr_trie(HASH_TABLE* table, const char* key, char* string) {
476 __n_assert(table, return FALSE);
477 __n_assert(key, return FALSE);
478
479 HASH_NODE* node = table->root;
480
481 for (size_t it = 0; key[it] != '\0'; it++) {
482 size_t index = (size_t)key[it] - table->alphabet_offset;
483 if (index >= table->alphabet_length) {
484 n_log(LOG_ERR, "Invalid value %zu for charater at position %zu of %s, set to 0", index, it, key);
485 index = 0;
486 }
487 if (node->children[index] == NULL) {
488 /* create a node */
489 node->children[index] = _ht_new_node_trie(table, key[it]);
490 __n_assert(node->children[index], return FALSE);
491 } else {
492 /* nothing to do since node is existing */
493 }
494 /* go down a level, to the child referenced by index */
495 node = node->children[index];
496 }
497 /* At the end of the key, mark this node as the leaf node */
498 int was_leaf = node->is_leaf;
499 if (was_leaf) {
500 FreeNoLog(node->key);
501 FreeNoLog(node->data.string);
502 }
503 node->is_leaf = 1;
504 /* Put the key - string pointer variant does not strdup the value, but key must be duplicated */
505 node->key = strdup(key);
506 if (!node->key) {
507 n_log(LOG_ERR, "strdup failure for key [%s]", key);
508 table->nb_keys++; /* compensate for upcoming remove */
509 _ht_remove_trie(table, key);
510 return FALSE;
511 }
512 /* Put the string pointer (not a copy - caller owns the string) */
513 node->data.string = string;
514 node->type = HASH_STRING;
515
516 if (!was_leaf) {
517 table->nb_keys++;
518 }
519
520 return TRUE;
521} /* _ht_put_string_ptr_trie(...) */
522
532int _ht_put_ptr_trie(HASH_TABLE* table, const char* key, void* ptr, void (*destructor)(void* ptr), void* (*duplicator)(void* ptr)) {
533 __n_assert(table, return FALSE);
534 __n_assert(key, return FALSE);
535
536 HASH_NODE* node = table->root;
537
538 for (size_t it = 0; key[it] != '\0'; it++) {
539 size_t index = (size_t)key[it] - table->alphabet_offset;
540 if (index >= table->alphabet_length) {
541 n_log(LOG_ERR, "Invalid value %zu for character at position %zu of %s, set to 0", index, it, key);
542 index = 0;
543 }
544 if (node->children[index] == NULL) {
545 /* create a node */
546 node->children[index] = _ht_new_node_trie(table, key[it]);
547 __n_assert(node->children[index], return FALSE);
548 } else {
549 /* nothing to do since node is existing */
550 }
551 /* go down a level, to the child referenced by index */
552 node = node->children[index];
553 }
554 /* At the end of the key, mark this node as the leaf node */
555 int was_leaf = node->is_leaf;
556 if (was_leaf) {
557 FreeNoLog(node->key);
558 /* free old value if a destructor was set */
559 if (node->destroy_func && node->data.ptr) {
560 node->destroy_func(node->data.ptr);
561 }
562 }
563 node->is_leaf = 1;
564 /* Put the key */
565 node->key = strdup(key);
566 if (!node->key) {
567 n_log(LOG_ERR, "strdup failure for key [%s]", key);
568 table->nb_keys++; /* compensate for upcoming remove */
569 _ht_remove_trie(table, key);
570 return FALSE;
571 }
572 /* Put the value */
573 node->data.ptr = ptr;
574 node->destroy_func = destructor;
575 node->duplicate_func = duplicator;
576 node->type = HASH_PTR;
577
578 if (!was_leaf) {
579 table->nb_keys++;
580 }
581
582 return TRUE;
583} /* _ht_put_ptr_trie(...) */
584
592 __n_assert(table, return NULL);
593 __n_assert(key, return NULL);
594
595 HASH_NODE* node = NULL;
596
597 if (key[0] != '\0') {
598 node = table->root;
599 for (size_t it = 0; key[it] != '\0'; it++) {
600 size_t index = (size_t)key[it] - table->alphabet_offset;
601 if (index >= table->alphabet_length) {
602 n_log(LOG_DEBUG, "Invalid value %zu for charater at index %zu of %s, set to 0", index, it, key);
603 return NULL;
604 }
605 if (node->children[index] == NULL) {
606 /* not found */
607 return NULL;
608 }
609 node = node->children[index];
610 }
611 } else {
612 node = NULL;
613 }
614 return node;
615} /* _ht_get_node_trie(...) */
616
624int _ht_get_int_trie(HASH_TABLE* table, const char* key, HASH_INT_TYPE* val) {
625 __n_assert(table, return FALSE);
626 __n_assert(key, return FALSE);
627 if (strlen(key) == 0)
628 return FALSE;
629
630 HASH_NODE* node = _ht_get_node_trie(table, key);
631
632 if (!node || !node->is_leaf)
633 return FALSE;
634
635 if (node->type != HASH_INT) {
636 n_log(LOG_ERR, "Can't get key[\"%s\"] of type HASH_INT, key is type %s", key, ht_node_type(node));
637 return FALSE;
638 }
639
640 (*val) = node->data.ival;
641
642 return TRUE;
643} /* _ht_get_int_trie() */
644
652int _ht_get_double_trie(HASH_TABLE* table, const char* key, double* val) {
653 __n_assert(table, return FALSE);
654 __n_assert(key, return FALSE);
655 if (strlen(key) == 0)
656 return FALSE;
657
658 HASH_NODE* node = _ht_get_node_trie(table, key);
659
660 if (!node || !node->is_leaf)
661 return FALSE;
662
663 if (node->type != HASH_DOUBLE) {
664 n_log(LOG_ERR, "Can't get key[\"%s\"] of type HASH_DOUBLE, key is type %s", key, ht_node_type(node));
665 return FALSE;
666 }
667
668 (*val) = node->data.fval;
669
670 return TRUE;
671} /* _ht_get_double_trie() */
672
680int _ht_get_string_trie(HASH_TABLE* table, const char* key, char** val) {
681 __n_assert(table, return FALSE);
682 __n_assert(key, return FALSE);
683 if (strlen(key) == 0)
684 return FALSE;
685
686 HASH_NODE* node = _ht_get_node_trie(table, key);
687
688 if (!node || !node->is_leaf)
689 return FALSE;
690
691 if (node->type != HASH_STRING) {
692 n_log(LOG_ERR, "Can't get key[\"%s\"] of type HASH_STRING, key is type %s", key, ht_node_type(node));
693 return FALSE;
694 }
695
696 (*val) = node->data.string;
697
698 return TRUE;
699} /* _ht_get_string_trie() */
700
708int _ht_get_ptr_trie(HASH_TABLE* table, const char* key, void** val) {
709 __n_assert(table, return FALSE);
710 __n_assert(key, return FALSE);
711 if (strlen(key) == 0)
712 return FALSE;
713
714 HASH_NODE* node = _ht_get_node_trie(table, key);
715
716 if (!node || !node->is_leaf)
717 return FALSE;
718
719 if (node->type != HASH_PTR) {
720 n_log(LOG_ERR, "Can't get key[\"%s\"] of type HASH_PTR , key is type %s", key, ht_node_type(node));
721 return FALSE;
722 }
723
724 (*val) = node->data.ptr;
725
726 return TRUE;
727} /* _ht_get_ptr_trie() */
728
735 __n_assert(table, return FALSE);
736
737 _ht_node_destroy(table->root);
738
739 table->root = _ht_new_node_trie(table, '\0');
740
741 table->nb_keys = 0;
742 return TRUE;
743} /* _empty_ht_trie */
744
751 __n_assert(table && (*table), n_log(LOG_ERR, "Can't destroy table: already NULL"); return FALSE);
752
753 _ht_node_destroy((*table)->root);
754
755 Free((*table));
756
757 return TRUE;
758} /* _destroy_ht_trie */
759
766 if (!node)
767 return;
768
769 if (node->is_leaf) {
770 printf("key: %s, val: ", node->key);
771 switch (node->type) {
772 case HASH_INT:
773 printf("int: %ld", (long)node->data.ival);
774 break;
775 case HASH_DOUBLE:
776 printf("double: %f", node->data.fval);
777 break;
778 case HASH_PTR:
779 printf("ptr: %p", node->data.ptr);
780 break;
781 case HASH_STRING:
782 printf("%s", node->data.string);
783 break;
784 default:
785 printf("unknwow type %d", node->type);
786 break;
787 }
788 printf("\n");
789 }
790 for (size_t it = 0; it < table->alphabet_length; it++) {
791 _ht_print_trie_helper(table, node->children[it]);
792 }
793} /* _ht_print_trie_helper(...) */
794
800 __n_assert(table, return);
801 __n_assert(table->root, return);
802
803 HASH_NODE* node = table->root;
804
805 _ht_print_trie_helper(table, node);
806
807 return;
808} /* _ht_print_trie(...) */
809
816void _ht_search_trie_helper(LIST* results, HASH_NODE* node, int (*node_is_matching)(HASH_NODE* node)) {
817 if (!node)
818 return;
819
820 if (node->is_leaf) {
821 if (node_is_matching(node) == TRUE) {
822 list_push(results, strdup(node->key), &free);
823 }
824 }
825 for (size_t it = 0; it < node->alphabet_length; it++) {
826 _ht_search_trie_helper(results, node->children[it], node_is_matching);
827 }
828}
829
836LIST* _ht_search_trie(HASH_TABLE* table, int (*node_is_matching)(HASH_NODE* node)) {
837 __n_assert(table, return NULL);
838
840 __n_assert(results, return NULL);
841
842 _ht_search_trie_helper(results, table->root, node_is_matching);
843
844 if (results->nb_items < 1)
845 list_destroy(&results);
846
847 return results;
848} /* _ht_search_trie(...) */
849
857 __n_assert(results, return FALSE);
858
859 if (!node)
860 return FALSE;
861
862 for (size_t it = 0; it < node->alphabet_length; it++) {
863 _ht_depth_first_search(node->children[it], results);
864 }
865 if (node->is_leaf) {
866 if (results->nb_items < results->nb_max_items) {
867 return list_push(results, strdup(node->key), &free);
868 }
869 return TRUE;
870 }
871 return TRUE;
872} /* _ht_depth_first_search(...) */
873
874/* Classic hash table */
876#define ROTL64(x, r) (((x) << (r)) | ((x) >> (64 - (r))))
878#define ROTL32(x, r) (((x) << (r)) | ((x) >> (32 - (r))))
880#define BIG_CONSTANT(x) (x##LLU)
881
882/* NO-OP for little-endian platforms */
883#if defined(__BYTE_ORDER__) && defined(__ORDER_LITTLE_ENDIAN__)
884#if __BYTE_ORDER__ == __ORDER_LITTLE_ENDIAN__
885#define BYTESWAP32(x) (x)
886#define BYTESWAP64(x) (x)
887#endif
888/* if __BYTE_ORDER__ is not predefined (like FreeBSD), use arch */
889#elif defined(__i386) || defined(__x86_64) || defined(__alpha) || defined(__vax)
890
891#define BYTESWAP32(x) (x)
892#define BYTESWAP64(x) (x)
893/* use __builtin_bswap32 if available */
894#elif defined(__GNUC__) || defined(__clang__)
895#ifdef __has_builtin
896#if __has_builtin(__builtin_bswap32)
897#define BYTESWAP32(x) __builtin_bswap32(x)
898#endif // __has_builtin(__builtin_bswap32)
899#if __has_builtin(__builtin_bswap64)
900#define BYTESWAP64(x) __builtin_bswap64(x)
901#endif // __has_builtin(__builtin_bswap64)
902#endif // __has_builtin
903#endif // defined(__GNUC__) || defined(__clang__)
904/* last resort (big-endian w/o __builtin_bswap) */
905#ifndef BYTESWAP32
907#define BYTESWAP32(x) ((((x) & 0xFF) << 24) | (((x) >> 24) & 0xFF) | (((x) & 0x0000FF00) << 8) | (((x) & 0x00FF0000) >> 8))
908#endif
909#ifndef BYTESWAP64
911#define BYTESWAP64(x) \
912 (((uint64_t)(x) << 56) | \
913 (((uint64_t)(x) << 40) & 0X00FF000000000000ULL) | \
914 (((uint64_t)(x) << 24) & 0X0000FF0000000000ULL) | \
915 (((uint64_t)(x) << 8) & 0X000000FF00000000ULL) | \
916 (((uint64_t)(x) >> 8) & 0X00000000FF000000ULL) | \
917 (((uint64_t)(x) >> 24) & 0X0000000000FF0000ULL) | \
918 (((uint64_t)(x) >> 40) & 0X000000000000FF00ULL) | \
919 ((uint64_t)(x) >> 56))
920#endif
921
928FORCE_INLINE uint32_t getblock32(const uint32_t* p, const size_t i) {
929 uint32_t result;
930 memcpy(&result, (const uint8_t*)p + i * 4, sizeof(result));
931 return BYTESWAP32(result);
932}
933
940FORCE_INLINE uint64_t getblock64(const uint64_t* p, const size_t i) {
941 uint64_t result;
942 memcpy(&result, (const uint8_t*)p + i * 8, sizeof(result));
943 return BYTESWAP64(result);
944}
945
951FORCE_INLINE uint32_t fmix32(uint32_t h) {
952 h ^= h >> 16;
953 h *= 0x85ebca6b;
954 h ^= h >> 13;
955 h *= 0xc2b2ae35;
956 h ^= h >> 16;
957
958 return h;
959} /* fmix32(...) */
960
966FORCE_INLINE uint64_t fmix64(uint64_t k) {
967 k ^= k >> 33;
968 k *= BIG_CONSTANT(0xff51afd7ed558ccd);
969 k ^= k >> 33;
970 k *= BIG_CONSTANT(0xc4ceb9fe1a85ec53);
971 k ^= k >> 33;
972
973 return k;
974}
975
988// Safe forward-indexing version
989void MurmurHash3_x86_32(const void* key, const size_t len, const uint32_t seed, void* out) {
990 const uint8_t* data = (const uint8_t*)key;
991 const size_t nblocks = len / 4;
992
993 uint32_t h1 = seed;
994 const uint32_t c1 = 0xcc9e2d51;
995 const uint32_t c2 = 0x1b873593;
996
997 const uint32_t* blocks = (const uint32_t*)data;
998
999 for (size_t i = 0; i < nblocks; i++) {
1000 uint32_t k1 = getblock32(blocks, i);
1001 k1 *= c1;
1002 k1 = ROTL32(k1, 15);
1003 k1 *= c2;
1004
1005 h1 ^= k1;
1006 h1 = ROTL32(h1, 13);
1007 h1 = h1 * 5 + 0xe6546b64;
1008 }
1009
1010 const uint8_t* tail = data + nblocks * 4;
1011 uint32_t k1 = 0;
1012 switch (len & 3) {
1013 case 3:
1014 k1 ^= (uint32_t)tail[2] << 16; /* fall through */
1016 case 2:
1017 k1 ^= (uint32_t)tail[1] << 8; /* fall through */
1019 case 1:
1020 k1 ^= (uint32_t)tail[0];
1021 k1 *= c1;
1022 k1 = ROTL32(k1, 15);
1023 k1 *= c2;
1024 h1 ^= k1;
1025 break;
1026 default:
1027 break;
1028 }
1029
1030 h1 ^= (uint32_t)len;
1031 h1 = fmix32(h1);
1032 *(uint32_t*)out = h1;
1033} /* MurmurHash3_x86_32 */
1034
1047void MurmurHash3_x86_128(const void* key, const size_t len, const uint32_t seed, void* out) {
1048 const uint8_t* data = (const uint8_t*)key;
1049 const size_t nblocks = len / 16;
1050
1051 uint32_t h1 = seed;
1052 uint32_t h2 = seed;
1053 uint32_t h3 = seed;
1054 uint32_t h4 = seed;
1055
1056 const uint32_t c1 = 0x239b961b;
1057 const uint32_t c2 = 0xab0e9789;
1058 const uint32_t c3 = 0x38b34ae5;
1059 const uint32_t c4 = 0xa1e38b93;
1060
1061 const uint32_t* blocks = (const uint32_t*)data;
1062
1063 for (size_t i = 0; i < nblocks; i++) {
1064 uint32_t k1 = getblock32(blocks, i * 4 + 0);
1065 uint32_t k2 = getblock32(blocks, i * 4 + 1);
1066 uint32_t k3 = getblock32(blocks, i * 4 + 2);
1067 uint32_t k4 = getblock32(blocks, i * 4 + 3);
1068
1069 k1 *= c1;
1070 k1 = ROTL32(k1, 15);
1071 k1 *= c2;
1072 h1 ^= k1;
1073 h1 = ROTL32(h1, 19);
1074 h1 += h2;
1075 h1 = h1 * 5 + 0x561ccd1b;
1076
1077 k2 *= c2;
1078 k2 = ROTL32(k2, 16);
1079 k2 *= c3;
1080 h2 ^= k2;
1081 h2 = ROTL32(h2, 17);
1082 h2 += h3;
1083 h2 = h2 * 5 + 0x0bcaa747;
1084
1085 k3 *= c3;
1086 k3 = ROTL32(k3, 17);
1087 k3 *= c4;
1088 h3 ^= k3;
1089 h3 = ROTL32(h3, 15);
1090 h3 += h4;
1091 h3 = h3 * 5 + 0x96cd1c35;
1092
1093 k4 *= c4;
1094 k4 = ROTL32(k4, 18);
1095 k4 *= c1;
1096 h4 ^= k4;
1097 h4 = ROTL32(h4, 13);
1098 h4 += h1;
1099 h4 = h4 * 5 + 0x32ac3b17;
1100 }
1101
1102 // tail
1103 const uint8_t* tail = data + nblocks * 16;
1104
1105 uint32_t k1 = 0, k2 = 0, k3 = 0, k4 = 0;
1106
1107 switch (len & 15) {
1108 case 15:
1109 k4 ^= (uint32_t)tail[14] << 16; /* fall through */
1111 case 14:
1112 k4 ^= (uint32_t)tail[13] << 8; /* fall through */
1114 case 13:
1115 k4 ^= (uint32_t)tail[12];
1116 k4 *= c4;
1117 k4 = ROTL32(k4, 18);
1118 k4 *= c1;
1119 h4 ^= k4;
1120 /* fall through */
1122 case 12:
1123 k3 ^= (uint32_t)tail[11] << 24; /* fall through */
1125 case 11:
1126 k3 ^= (uint32_t)tail[10] << 16; /* fall through */
1128 case 10:
1129 k3 ^= (uint32_t)tail[9] << 8; /* fall through */
1131 case 9:
1132 k3 ^= (uint32_t)tail[8];
1133 k3 *= c3;
1134 k3 = ROTL32(k3, 17);
1135 k3 *= c4;
1136 h3 ^= k3;
1137 /* fall through */
1139 case 8:
1140 k2 ^= (uint32_t)tail[7] << 24; /* fall through */
1142 case 7:
1143 k2 ^= (uint32_t)tail[6] << 16; /* fall through */
1145 case 6:
1146 k2 ^= (uint32_t)tail[5] << 8; /* fall through */
1148 case 5:
1149 k2 ^= (uint32_t)tail[4];
1150 k2 *= c2;
1151 k2 = ROTL32(k2, 16);
1152 k2 *= c3;
1153 h2 ^= k2;
1154 /* fall through */
1156 case 4:
1157 k1 ^= (uint32_t)tail[3] << 24; /* fall through */
1159 case 3:
1160 k1 ^= (uint32_t)tail[2] << 16; /* fall through */
1162 case 2:
1163 k1 ^= (uint32_t)tail[1] << 8; /* fall through */
1165 case 1:
1166 k1 ^= (uint32_t)tail[0];
1167 k1 *= c1;
1168 k1 = ROTL32(k1, 15);
1169 k1 *= c2;
1170 h1 ^= k1;
1171 break;
1172 default:
1173 break;
1174 }
1175
1176 // finalization
1177 h1 ^= (uint32_t)len;
1178 h2 ^= (uint32_t)len;
1179 h3 ^= (uint32_t)len;
1180 h4 ^= (uint32_t)len;
1181
1182 h1 += h2 + h3 + h4;
1183 h2 += h1;
1184 h3 += h1;
1185 h4 += h1;
1186
1187 h1 = fmix32(h1);
1188 h2 = fmix32(h2);
1189 h3 = fmix32(h3);
1190 h4 = fmix32(h4);
1191
1192 h1 += h2 + h3 + h4;
1193 h2 += h1;
1194 h3 += h1;
1195 h4 += h1;
1196
1197 ((uint32_t*)out)[0] = h1;
1198 ((uint32_t*)out)[1] = h2;
1199 ((uint32_t*)out)[2] = h3;
1200 ((uint32_t*)out)[3] = h4;
1201} /* MurmurHash3_x86_128(...) */
1202
1215void MurmurHash3_x64_128(const void* key, const size_t len, const uint64_t seed, void* out) {
1216 const uint8_t* data = (const uint8_t*)key;
1217 const size_t nblocks = len / 16;
1218
1219 uint64_t h1 = seed;
1220 uint64_t h2 = seed;
1221
1222 const uint64_t c1 = 0x87c37b91114253d5ULL;
1223 const uint64_t c2 = 0x4cf5ad432745937fULL;
1224
1225 // Body
1226 const uint64_t* blocks = (const uint64_t*)data;
1227 for (size_t i = 0; i < nblocks; i++) {
1228 uint64_t k1 = getblock64(blocks, i * 2 + 0);
1229 uint64_t k2 = getblock64(blocks, i * 2 + 1);
1230
1231 k1 *= c1;
1232 k1 = ROTL64(k1, 31);
1233 k1 *= c2;
1234 h1 ^= k1;
1235
1236 h1 = ROTL64(h1, 27);
1237 h1 += h2;
1238 h1 = h1 * 5 + 0x52dce729;
1239
1240 k2 *= c2;
1241 k2 = ROTL64(k2, 33);
1242 k2 *= c1;
1243 h2 ^= k2;
1244
1245 h2 = ROTL64(h2, 31);
1246 h2 += h1;
1247 h2 = h2 * 5 + 0x38495ab5;
1248 }
1249
1250 // Tail
1251 const uint8_t* tail = data + nblocks * 16;
1252
1253 uint64_t k1 = 0;
1254 uint64_t k2 = 0;
1255
1256 switch (len & 15) {
1257 case 15:
1258 k2 ^= ((uint64_t)tail[14]) << 48; /* fall through */
1260 case 14:
1261 k2 ^= ((uint64_t)tail[13]) << 40; /* fall through */
1263 case 13:
1264 k2 ^= ((uint64_t)tail[12]) << 32; /* fall through */
1266 case 12:
1267 k2 ^= ((uint64_t)tail[11]) << 24; /* fall through */
1269 case 11:
1270 k2 ^= ((uint64_t)tail[10]) << 16; /* fall through */
1272 case 10:
1273 k2 ^= ((uint64_t)tail[9]) << 8; /* fall through */
1275 case 9:
1276 k2 ^= ((uint64_t)tail[8]);
1277 k2 *= c2;
1278 k2 = ROTL64(k2, 33);
1279 k2 *= c1;
1280 h2 ^= k2;
1281 /* fall through */
1283 case 8:
1284 k1 ^= ((uint64_t)tail[7]) << 56; /* fall through */
1286 case 7:
1287 k1 ^= ((uint64_t)tail[6]) << 48; /* fall through */
1289 case 6:
1290 k1 ^= ((uint64_t)tail[5]) << 40; /* fall through */
1292 case 5:
1293 k1 ^= ((uint64_t)tail[4]) << 32; /* fall through */
1295 case 4:
1296 k1 ^= ((uint64_t)tail[3]) << 24; /* fall through */
1298 case 3:
1299 k1 ^= ((uint64_t)tail[2]) << 16; /* fall through */
1301 case 2:
1302 k1 ^= ((uint64_t)tail[1]) << 8; /* fall through */
1304 case 1:
1305 k1 ^= ((uint64_t)tail[0]);
1306 k1 *= c1;
1307 k1 = ROTL64(k1, 31);
1308 k1 *= c2;
1309 h1 ^= k1;
1310 break;
1311 default:
1312 break;
1313 }
1314
1315 // Finalization
1316 h1 ^= len;
1317 h2 ^= len;
1318
1319 h1 += h2;
1320 h2 += h1;
1321
1322 h1 = fmix64(h1);
1323 h2 = fmix64(h2);
1324
1325 h1 += h2;
1326 h2 += h1;
1327
1328 ((uint64_t*)out)[0] = h1;
1329 ((uint64_t*)out)[1] = h2;
1330} /* MurmurHash3_x64_128()*/
1331
1337char* ht_node_type(const HASH_NODE* node) {
1338 __n_assert(node, return "NULL_NODE");
1339
1340 switch (node->type) {
1341 case HASH_INT:
1342 return "HASH_INT";
1343 case HASH_DOUBLE:
1344 return "HASH_DOUBLE";
1345 case HASH_STRING:
1346 return "HASH_STRING";
1347 case HASH_PTR:
1348 return "HASH_PTR";
1349 default:
1350 return "HASH_UNKNOWN";
1351 }
1352} /* ht_node_type(...) */
1353
1381static HASH_VALUE _ht_hash_value(const HASH_TABLE* table, const char* key, size_t key_len) {
1382 uint8_t digest[16] = {0};
1383 HASH_VALUE value = 0;
1384
1385 MurmurHash(key, key_len, table->seed, digest);
1386 memcpy(&value, digest, sizeof(value));
1387
1388 return value;
1389} /* _ht_hash_value */
1390
1397HASH_NODE* _ht_get_node(HASH_TABLE* table, const char* key) {
1398 HASH_VALUE hash_value = 0;
1399 size_t index = 0;
1400
1401 __n_assert(table, return NULL);
1402 __n_assert(key, return NULL);
1403
1404 if (key[0] == '\0')
1405 return NULL;
1406
1407 hash_value = _ht_hash_value(table, key, strlen(key));
1408 index = (hash_value) % (table->size);
1409
1410 if (!table->hash_table[index]->start)
1411 return NULL;
1412
1413 list_foreach(list_node, table->hash_table[index]) {
1414 HASH_NODE* node_ptr = (HASH_NODE*)list_node->ptr;
1415 if (!strcmp(key, node_ptr->key)) {
1416 return node_ptr;
1417 }
1418 }
1419 return NULL;
1420} /* _ht_get_node() */
1421
1428HASH_NODE* _ht_new_node(const HASH_TABLE* table, const char* key) {
1429 __n_assert(table, return NULL);
1430 __n_assert(key, return NULL);
1431
1432 HASH_NODE* new_hash_node = NULL;
1433
1434 HASH_VALUE hash_value = 0;
1435
1436 if (strlen(key) == 0)
1437 return NULL;
1438
1439 hash_value = _ht_hash_value(table, key, strlen(key));
1440
1441 Malloc(new_hash_node, HASH_NODE, 1);
1442 __n_assert(new_hash_node, n_log(LOG_ERR, "Could not allocate new_hash_node"); return NULL);
1443 new_hash_node->key = strdup(key);
1444 new_hash_node->key_id = '\0';
1445 __n_assert(new_hash_node->key, n_log(LOG_ERR, "Could not allocate new_hash_node->key"); Free(new_hash_node); return NULL);
1446 new_hash_node->hash_value = hash_value;
1447 new_hash_node->data.ptr = NULL;
1448 new_hash_node->destroy_func = NULL;
1449 new_hash_node->children = NULL;
1450 new_hash_node->is_leaf = 0;
1451 new_hash_node->need_rehash = 0;
1452 new_hash_node->alphabet_length = 0;
1453
1454 return new_hash_node;
1455} /* _ht_new_node */
1456
1465 __n_assert(table, return NULL);
1466 __n_assert(key, return NULL);
1467
1468 HASH_NODE* new_hash_node = NULL;
1469 new_hash_node = _ht_new_node(table, key);
1470 if (new_hash_node) {
1471 new_hash_node->data.ival = value;
1472 new_hash_node->type = HASH_INT;
1473 } else {
1474 n_log(LOG_ERR, "Could not get a new node in table %p with key %s", table, key);
1475 }
1476 return new_hash_node;
1477} /* _ht_new_int_node */
1478
1486HASH_NODE* _ht_new_double_node(HASH_TABLE* table, const char* key, double value) {
1487 __n_assert(table, return NULL);
1488 __n_assert(key, return NULL);
1489
1490 HASH_NODE* new_hash_node = NULL;
1491 new_hash_node = _ht_new_node(table, key);
1492 if (new_hash_node) {
1493 new_hash_node->data.fval = value;
1494 new_hash_node->type = HASH_DOUBLE;
1495 } else {
1496 n_log(LOG_ERR, "Could not get a new node in table %p with key %s", table, key);
1497 }
1498 return new_hash_node;
1499} /* _ht_new_double_node */
1500
1508HASH_NODE* _ht_new_string_node(HASH_TABLE* table, const char* key, const char* value) {
1509 __n_assert(table, return NULL);
1510 __n_assert(key, return NULL);
1511
1512 HASH_NODE* new_hash_node = NULL;
1513 new_hash_node = _ht_new_node(table, key);
1514 if (new_hash_node) {
1515 if (value)
1516 new_hash_node->data.string = strdup(value);
1517 else
1518 new_hash_node->data.string = NULL;
1519 new_hash_node->type = HASH_STRING;
1520 } else {
1521 n_log(LOG_ERR, "Could not get a new node in table %p with key %s", table, key);
1522 }
1523 return new_hash_node;
1524}
1525
1533HASH_NODE* _ht_new_string_ptr_node(HASH_TABLE* table, const char* key, char* value) {
1534 __n_assert(table, return NULL);
1535 __n_assert(key, return NULL);
1536
1537 HASH_NODE* new_hash_node = NULL;
1538 new_hash_node = _ht_new_node(table, key);
1539 if (new_hash_node) {
1540 new_hash_node->data.string = value;
1541 new_hash_node->type = HASH_STRING;
1542 } else {
1543 n_log(LOG_ERR, "Could not get a new node in table %p with key %s", table, key);
1544 }
1545 return new_hash_node;
1546}
1547
1557HASH_NODE* _ht_new_ptr_node(HASH_TABLE* table, const char* key, void* value, void (*destructor)(void* ptr), void* (*duplicator)(void* ptr)) {
1558 __n_assert(table, return NULL);
1559 __n_assert(key, return NULL);
1560
1561 HASH_NODE* new_hash_node = NULL;
1562 new_hash_node = _ht_new_node(table, key);
1563 if (new_hash_node) {
1564 new_hash_node->data.ptr = value;
1565 new_hash_node->destroy_func = destructor;
1566 new_hash_node->duplicate_func = duplicator;
1567 new_hash_node->type = HASH_PTR;
1568 } else {
1569 n_log(LOG_ERR, "Could not get a new node in table %p with key %s", table, key);
1570 }
1571 return new_hash_node;
1572}
1573
1581int _ht_put_int(HASH_TABLE* table, const char* key, HASH_INT_TYPE value) {
1582 HASH_NODE* node_ptr = NULL;
1583
1584 __n_assert(table, return FALSE);
1585 __n_assert(key, return FALSE);
1586
1587 if ((node_ptr = _ht_get_node(table, key))) {
1588 if (node_ptr->type == HASH_INT) {
1589 node_ptr->data.ival = value;
1590 return TRUE;
1591 }
1592 n_log(LOG_ERR, "Can't add key[\"%s\"] with type HASH_INT, key already exist with type %s", node_ptr->key, ht_node_type(node_ptr));
1593 return FALSE; /* key registered with another data type */
1594 }
1595
1596 int retcode = FALSE;
1597 node_ptr = _ht_new_int_node(table, key, value);
1598 if (node_ptr) {
1599 size_t index = (node_ptr->hash_value) % (table->size);
1600 retcode = list_push(table->hash_table[index], node_ptr, &_ht_node_destroy);
1601 if (retcode == TRUE) {
1602 table->nb_keys++;
1603 }
1604 }
1605 return retcode;
1606} /*_ht_put_int() */
1607
1615int _ht_put_double(HASH_TABLE* table, const char* key, double value) {
1616 HASH_NODE* node_ptr = NULL;
1617
1618 __n_assert(table, return FALSE);
1619 __n_assert(key, return FALSE);
1620
1621 if ((node_ptr = _ht_get_node(table, key))) {
1622 if (node_ptr->type == HASH_DOUBLE) {
1623 node_ptr->data.fval = value;
1624 return TRUE;
1625 }
1626 n_log(LOG_ERR, "Can't add key[\"%s\"] with type HASH_DOUBLE, key already exist with type %s", node_ptr->key, ht_node_type(node_ptr));
1627 return FALSE; /* key registered with another data type */
1628 }
1629
1630 int retcode = FALSE;
1631 node_ptr = _ht_new_double_node(table, key, value);
1632 if (node_ptr) {
1633 HASH_VALUE index = (node_ptr->hash_value) % (table->size);
1634 retcode = list_push(table->hash_table[index], node_ptr, &_ht_node_destroy);
1635 if (retcode == TRUE) {
1636 table->nb_keys++;
1637 }
1638 }
1639 return retcode;
1640} /*_ht_put_double()*/
1641
1651int _ht_put_ptr(HASH_TABLE* table, const char* key, void* ptr, void (*destructor)(void* ptr), void* (*duplicator)(void* ptr)) {
1652 HASH_NODE* node_ptr = NULL;
1653
1654 __n_assert(table, return FALSE);
1655 __n_assert(key, return FALSE);
1656
1657 if ((node_ptr = _ht_get_node(table, key))) {
1658 /* let's check the key isn't already assigned with another data type */
1659 if (node_ptr->type == HASH_PTR) {
1660 /* free the old value if a destructor is set */
1661 if (node_ptr->destroy_func && node_ptr->data.ptr) {
1662 node_ptr->destroy_func(node_ptr->data.ptr);
1663 }
1664 /* always update the pointer and function pointers */
1665 node_ptr->data.ptr = ptr;
1666 node_ptr->destroy_func = destructor;
1667 node_ptr->duplicate_func = duplicator;
1668 return TRUE;
1669 }
1670 n_log(LOG_ERR, "Can't add key[\"%s\"] with type HASH_PTR , key already exist with type %s", node_ptr->key, ht_node_type(node_ptr));
1671 return FALSE; /* key registered with another data type */
1672 }
1673
1674 int retcode = FALSE;
1675 node_ptr = _ht_new_ptr_node(table, key, ptr, destructor, duplicator);
1676 if (node_ptr) {
1677 HASH_VALUE index = (node_ptr->hash_value) % (table->size);
1678 retcode = list_push(table->hash_table[index], node_ptr, &_ht_node_destroy);
1679 if (retcode == TRUE) {
1680 table->nb_keys++;
1681 }
1682 }
1683 return retcode;
1684} /* _ht_put_ptr() */
1685
1693int _ht_put_string(HASH_TABLE* table, const char* key, char* string) {
1694 HASH_NODE* node_ptr = NULL;
1695
1696 __n_assert(table, return FALSE);
1697 __n_assert(key, return FALSE);
1698
1699 if ((node_ptr = _ht_get_node(table, key))) {
1700 /* let's check the key isn't already assigned with another data type */
1701 if (node_ptr->type == HASH_STRING) {
1702 char* new_str = NULL;
1703 if (string) {
1704 new_str = strdup(string);
1705 if (!new_str) {
1706 n_log(LOG_ERR, "could not strdup char *string at %p, didn't overwrite %s", string, key);
1707 return FALSE;
1708 }
1709 }
1710 Free(node_ptr->data.string);
1711 node_ptr->data.string = new_str;
1712 return TRUE;
1713 }
1714 n_log(LOG_ERR, "Can't add key[\"%s\"] with type HASH_STRING , key already exist with type %s", node_ptr->key, ht_node_type(node_ptr));
1715 return FALSE; /* key registered with another data type */
1716 }
1717
1718 int retcode = FALSE;
1719 node_ptr = _ht_new_string_node(table, key, string);
1720 if (node_ptr) {
1721 HASH_VALUE index = (node_ptr->hash_value) % (table->size);
1722 retcode = list_push(table->hash_table[index], node_ptr, &_ht_node_destroy);
1723 if (retcode == TRUE) {
1724 table->nb_keys++;
1725 }
1726 }
1727 return retcode;
1728} /*_ht_put_string */
1729
1737int _ht_put_string_ptr(HASH_TABLE* table, const char* key, char* string) {
1738 HASH_NODE* node_ptr = NULL;
1739
1740 __n_assert(table, return FALSE);
1741 __n_assert(key, return FALSE);
1742
1743 if ((node_ptr = _ht_get_node(table, key))) {
1744 /* let's check the key isn't already assigned with another data type */
1745 if (node_ptr->type == HASH_STRING) {
1746 Free(node_ptr->data.string);
1747 node_ptr->data.string = string;
1748 return TRUE;
1749 }
1750 n_log(LOG_ERR, "Can't add key[\"%s\"] with type HASH_STRING , key already exist with type %s", node_ptr->key, ht_node_type(node_ptr));
1751 return FALSE; /* key registered with another data type */
1752 }
1753
1754 int retcode = FALSE;
1755 node_ptr = _ht_new_string_ptr_node(table, key, string);
1756 if (node_ptr) {
1757 HASH_VALUE index = (node_ptr->hash_value) % (table->size);
1758 retcode = list_push(table->hash_table[index], node_ptr, &_ht_node_destroy);
1759 if (retcode == TRUE) {
1760 table->nb_keys++;
1761 }
1762 }
1763 return retcode;
1764} /*_ht_put_string_ptr */
1765
1773int _ht_get_int(HASH_TABLE* table, const char* key, HASH_INT_TYPE* val) {
1774 __n_assert(table, return FALSE);
1775 __n_assert(key, return FALSE);
1776 if (strlen(key) == 0)
1777 return FALSE;
1778
1779 HASH_NODE* node = _ht_get_node(table, key);
1780
1781 if (!node)
1782 return FALSE;
1783
1784 if (node->type != HASH_INT) {
1785 n_log(LOG_ERR, "Can't get key[\"%s\"] of type HASH_INT, key is type %s", key, ht_node_type(node));
1786 return FALSE;
1787 }
1788
1789 (*val) = node->data.ival;
1790
1791 return TRUE;
1792} /* _ht_get_int() */
1793
1801int _ht_get_double(HASH_TABLE* table, const char* key, double* val) {
1802 __n_assert(table, return FALSE);
1803 __n_assert(key, return FALSE);
1804
1805 if (strlen(key) == 0)
1806 return FALSE;
1807
1808 HASH_NODE* node = _ht_get_node(table, key);
1809
1810 if (!node)
1811 return FALSE;
1812
1813 if (node->type != HASH_DOUBLE) {
1814 n_log(LOG_ERR, "Can't get key[\"%s\"] of type HASH_DOUBLE, key is type %s", key, ht_node_type(node));
1815 return FALSE;
1816 }
1817
1818 (*val) = node->data.fval;
1819
1820 return TRUE;
1821} /* _ht_get_double()*/
1822
1830int _ht_get_ptr(HASH_TABLE* table, const char* key, void** val) {
1831 __n_assert(table, return FALSE);
1832 __n_assert(key, return FALSE);
1833 if (strlen(key) == 0)
1834 return FALSE;
1835
1836 HASH_NODE* node = _ht_get_node(table, key);
1837 if (!node)
1838 return FALSE;
1839
1840 if (node->type != HASH_PTR) {
1841 n_log(LOG_ERR, "Can't get key[\"%s\"] of type HASH_PTR, key is type %s", key, ht_node_type(node));
1842 return FALSE;
1843 }
1844
1845 (*val) = node->data.ptr;
1846
1847 return TRUE;
1848} /* _ht_get_ptr() */
1849
1857int _ht_get_string(HASH_TABLE* table, const char* key, char** val) {
1858 __n_assert(table, return FALSE);
1859 __n_assert(key, return FALSE);
1860 if (strlen(key) == 0)
1861 return FALSE;
1862
1863 HASH_NODE* node = _ht_get_node(table, key);
1864 if (!node)
1865 return FALSE;
1866
1867 if (node->type != HASH_STRING) {
1868 n_log(LOG_ERR, "Can't get key[\"%s\"] of type HASH_STRING, key is type %s", key, ht_node_type(node));
1869 return FALSE;
1870 }
1871
1872 (*val) = node->data.string;
1873
1874 return TRUE;
1875} /* _ht_get_string() */
1876
1883int _ht_remove(HASH_TABLE* table, const char* key) {
1884 HASH_VALUE hash_value = 0;
1885 size_t index = 0;
1886
1887 HASH_NODE* node_ptr = NULL;
1888 LIST_NODE* node_to_kill = NULL;
1889
1890 __n_assert(table, return FALSE);
1891 __n_assert(key, return FALSE);
1892 if (strlen(key) == 0)
1893 return FALSE;
1894
1895 hash_value = _ht_hash_value(table, key, strlen(key));
1896 index = (hash_value) % (table->size);
1897
1898 if (!table->hash_table[index]->start) {
1899 n_log(LOG_ERR, "Can't remove key[\"%s\"], table is empty", key);
1900 return FALSE;
1901 }
1902
1903 list_foreach(list_node, table->hash_table[index]) {
1904 node_ptr = (HASH_NODE*)list_node->ptr;
1905 /* if we found the same */
1906 if (!strcmp(key, node_ptr->key)) {
1907 node_to_kill = list_node;
1908 break;
1909 }
1910 }
1911 if (node_to_kill) {
1912 node_ptr = remove_list_node(table->hash_table[index], node_to_kill, HASH_NODE);
1913 _ht_node_destroy(node_ptr);
1914
1915 table->nb_keys--;
1916
1917 return TRUE;
1918 }
1919 n_log(LOG_ERR, "Can't delete key[\"%s\"]: inexisting key", key);
1920 return FALSE;
1921} /* ht_remove() */
1922
1929 __n_assert(table, return FALSE);
1930
1931 HASH_VALUE index = 0;
1932 for (index = 0; index < table->size; index++) {
1933 while (table->hash_table[index] && table->hash_table[index]->start) {
1934 HASH_NODE* hash_node = remove_list_node(table->hash_table[index], table->hash_table[index]->start, HASH_NODE);
1935 _ht_node_destroy(hash_node);
1936 }
1937 }
1938 table->nb_keys = 0;
1939 return TRUE;
1940} /* empty_ht */
1941
1948 __n_assert(table && (*table), n_log(LOG_ERR, "Can't destroy table: already NULL"); return FALSE);
1949
1950 if ((*table)->hash_table) {
1951 // empty_ht( (*table) );
1952
1953 HASH_VALUE it = 0;
1954 for (it = 0; it < (*table)->size; it++) {
1955 if ((*table)->hash_table[it])
1956 list_destroy(&(*table)->hash_table[it]);
1957 }
1958 Free((*table)->hash_table);
1959 }
1960 Free((*table));
1961 return TRUE;
1962} /* _destroy_ht */
1963
1968void _ht_print(HASH_TABLE* table) {
1969 __n_assert(table, return);
1970 __n_assert(table->hash_table, return);
1971 // cppcheck-suppress constVariablePointer ; node is generated by ht_foreach macro
1972 ht_foreach(node, table) {
1973 const HASH_NODE* ht_node = (const HASH_NODE*)node->ptr;
1974 printf("key:%s node:%s\n", ht_node->key, ht_node->key);
1975 }
1976
1977 return;
1978} /* _ht_print(...) */
1979
1986LIST* _ht_search(HASH_TABLE* table, int (*node_is_matching)(HASH_NODE* node)) {
1987 __n_assert(table, return NULL);
1988
1990 __n_assert(results, return NULL);
1991
1992 ht_foreach(node, table) {
1993 HASH_NODE* hnode = (HASH_NODE*)node->ptr;
1994 if (node_is_matching(hnode) == TRUE) {
1995 list_push(results, strdup(hnode->key), &free);
1996 }
1997 }
1998
1999 if (results->nb_items < 1)
2000 list_destroy(&results);
2001
2002 return results;
2003} /* _ht_search(...) */
2004
2005/* Hash tables function pointers and common table type functions */
2006
2013HASH_TABLE* new_ht_trie(size_t alphabet_length, size_t alphabet_offset) {
2014 HASH_TABLE* table = NULL;
2015
2016 Malloc(table, HASH_TABLE, 1);
2017 __n_assert(table, n_log(LOG_ERR, "Error allocating HASH_TABLE *table"); return NULL);
2018
2019 table->size = 0;
2020 table->seed = 0;
2021 table->nb_keys = 0;
2022 errno = 0;
2023 table->hash_table = NULL;
2024
2034 table->ht_remove = _ht_remove_trie;
2035 table->ht_search = _ht_search_trie;
2036 table->empty_ht = _empty_ht_trie;
2038 table->ht_print = _ht_print_trie;
2039
2040 table->alphabet_length = alphabet_length;
2041 table->alphabet_offset = alphabet_offset;
2042
2043 table->root = _ht_new_node_trie(table, '\0');
2044 if (!table->root) {
2045 n_log(LOG_ERR, "Couldn't allocate new_ht_trie with alphabet_length of %zu and alphabet offset of %zu", alphabet_length, alphabet_offset);
2046 Free(table);
2047 return NULL;
2048 }
2049 table->mode = HASH_TRIE;
2050
2051 return table;
2052} /* new_ht_trie */
2053
2054/* Per-process random key for the table seeds, read once from the OS: a
2055 * hash table fed attacker-chosen keys (form fields, headers, cookies) must
2056 * not use a seed the attacker can predict, or colliding keys can be
2057 * precomputed to turn every lookup into a list walk (hash flooding). The
2058 * old seed was rand() % 100000 with rand() never seeded: the same for
2059 * every process. */
2060static uint64_t _ht_process_key = 0;
2061static uint64_t _ht_table_counter = 0;
2062static pthread_once_t _ht_key_once = PTHREAD_ONCE_INIT;
2063static pthread_mutex_t _ht_counter_lock = PTHREAD_MUTEX_INITIALIZER;
2064
2065static void _ht_key_init(void) {
2066 uint64_t k = 0;
2067 int got = 0;
2068#if defined(__windows__)
2069 got = BCryptGenRandom(NULL, (PUCHAR)&k, (ULONG)sizeof(k), BCRYPT_USE_SYSTEM_PREFERRED_RNG) == 0;
2070#else
2071#ifdef N_HASH_HAVE_GETRANDOM
2072 got = getrandom(&k, sizeof(k), GRND_NONBLOCK) == (ssize_t)sizeof(k);
2073#endif
2074 /* cppcheck does not define __GLIBC__, so it never sees the getrandom()
2075 * branch above that can set got */
2076 // cppcheck-suppress knownConditionTrueFalse ; got is set by getrandom() on glibc
2077 if (!got) {
2078 int fd = open("/dev/urandom", O_RDONLY);
2079 if (fd >= 0) {
2080 got = read(fd, &k, sizeof(k)) == (ssize_t)sizeof(k);
2081 close(fd);
2082 }
2083 }
2084#endif
2085 if (!got) {
2086 /* last resort: time and addresses, at least different per run */
2087 uint64_t t = (uint64_t)time(NULL), c = (uint64_t)clock();
2088 k = t * 0x9E3779B97F4A7C15ULL ^ (c << 21) ^ (uint64_t)(uintptr_t)&k ^ (uint64_t)(uintptr_t)&_ht_process_key;
2089 }
2090 _ht_process_key = k;
2091}
2092
2093/* splitmix64: spread a counter into well-mixed 64-bit values. */
2094static uint64_t _ht_mix(uint64_t x) {
2095 x += 0x9E3779B97F4A7C15ULL;
2096 x = (x ^ (x >> 30)) * 0xBF58476D1CE4E5B9ULL;
2097 x = (x ^ (x >> 27)) * 0x94D049BB133111EBULL;
2098 return x ^ (x >> 31);
2099}
2100
2101/* A fresh, unpredictable seed for one table. */
2102static size_t _ht_new_seed(void) {
2103 uint64_t n;
2104 pthread_once(&_ht_key_once, _ht_key_init);
2105 pthread_mutex_lock(&_ht_counter_lock);
2106 n = ++_ht_table_counter;
2107 pthread_mutex_unlock(&_ht_counter_lock);
2108 return (size_t)_ht_mix(_ht_process_key ^ _ht_mix(n));
2109}
2110
2116HASH_TABLE* new_ht(size_t size) {
2117 HASH_TABLE* table = NULL;
2118
2119 if (size < 1) {
2120 n_log(LOG_ERR, "Invalid size %zu for new_ht()", size);
2121 return NULL;
2122 }
2123 Malloc(table, HASH_TABLE, 1);
2124 __n_assert(table, n_log(LOG_ERR, "Error allocating HASH_TABLE *table"); return NULL);
2125
2126 table->size = size;
2127 table->seed = _ht_new_seed();
2128 table->nb_keys = 0;
2129 errno = 0;
2130 Malloc(table->hash_table, LIST*, size);
2131 // table -> hash_table = (LIST **)calloc( size, sizeof( LIST *) );
2132 __n_assert(table->hash_table, n_log(LOG_ERR, "Can't allocate table -> hash_table with size %zu !", size); Free(table); return NULL);
2133
2134 size_t it = 0;
2135 for (it = 0; it < size; it++) {
2137 // if no valid table then unroll previsouly created slots
2138 if (!table->hash_table[it]) {
2139 n_log(LOG_ERR, "Can't allocate table -> hash_table[ %zu ] !", it);
2140 size_t it_delete = 0;
2141 for (it_delete = 0; it_delete < it; it_delete++) {
2142 list_destroy(&table->hash_table[it_delete]);
2143 }
2144 Free(table->hash_table);
2145 Free(table);
2146 return NULL;
2147 }
2148 }
2149 table->mode = HASH_CLASSIC;
2150
2151 table->ht_put_int = _ht_put_int;
2153 table->ht_put_ptr = _ht_put_ptr;
2156 table->ht_get_int = _ht_get_int;
2159 table->ht_get_ptr = _ht_get_ptr;
2160 table->ht_get_node = _ht_get_node;
2161 table->ht_remove = _ht_remove;
2162 table->ht_search = _ht_search;
2163 table->empty_ht = _empty_ht;
2164 table->destroy_ht = _destroy_ht;
2165 table->ht_print = _ht_print;
2166
2167 return table;
2168} /* new_ht(...) */
2169
2176HASH_NODE* ht_get_node(HASH_TABLE* table, const char* key) {
2177 __n_assert(table, return NULL);
2178 __n_assert(key, return NULL);
2179 return table->ht_get_node(table, key);
2180} /*ht_get_node(...) */
2181
2189int ht_get_double(HASH_TABLE* table, const char* key, double* val) {
2190 __n_assert(table, return FALSE);
2191 __n_assert(key, return FALSE);
2192 return table->ht_get_double(table, key, val);
2193} /* ht_get_double(...) */
2194
2202int ht_get_int(HASH_TABLE* table, const char* key, HASH_INT_TYPE* val) {
2203 __n_assert(table, return FALSE);
2204 __n_assert(key, return FALSE);
2205 return table->ht_get_int(table, key, val);
2206} /* ht_get_int(...) */
2207
2215int ht_get_ptr(HASH_TABLE* table, const char* key, void** val) {
2216 __n_assert(table, return FALSE);
2217 __n_assert(key, return FALSE);
2218 return table->ht_get_ptr(table, key, val);
2219} /* ht_get_ptr(...) */
2220
2228int ht_get_string(HASH_TABLE* table, const char* key, char** val) {
2229 __n_assert(table, return FALSE);
2230 __n_assert(key, return FALSE);
2231 return table->ht_get_string(table, key, val);
2232} /* ht_get_string(...) */
2233
2241int ht_put_double(HASH_TABLE* table, const char* key, double value) {
2242 __n_assert(table, return FALSE);
2243 __n_assert(key, return FALSE);
2244 return table->ht_put_double(table, key, value);
2245} /* ht_put_double(...) */
2246
2254int ht_put_int(HASH_TABLE* table, const char* key, HASH_INT_TYPE value) {
2255 __n_assert(table, return FALSE);
2256 __n_assert(key, return FALSE);
2257 return table->ht_put_int(table, key, value);
2258} /* ht_put_int(...) */
2259
2269int ht_put_ptr(HASH_TABLE* table, const char* key, void* ptr, void (*destructor)(void* ptr), void* (*duplicator)(void* ptr)) {
2270 __n_assert(table, return FALSE);
2271 __n_assert(key, return FALSE);
2272 return table->ht_put_ptr(table, key, ptr, destructor, duplicator);
2273} /* ht_put_ptr(...) */
2274
2282int ht_put_string(HASH_TABLE* table, const char* key, char* string) {
2283 __n_assert(table, return FALSE);
2284 __n_assert(key, return FALSE);
2285 return table->ht_put_string(table, key, string);
2286} /* ht_put_string(...) */
2287
2295int ht_put_string_ptr(HASH_TABLE* table, const char* key, char* string) {
2296 __n_assert(table, return FALSE);
2297 __n_assert(key, return FALSE);
2298 return table->ht_put_string_ptr(table, key, string);
2299} /* ht_put_string_ptr(...) */
2300
2307int ht_remove(HASH_TABLE* table, const char* key) {
2308 __n_assert(table, return FALSE);
2309 __n_assert(key, return FALSE);
2310 return table->ht_remove(table, key);
2311} /* ht_remove(...) */
2312
2317void ht_print(HASH_TABLE* table) {
2318 __n_assert(table, return);
2319 table->ht_print(table);
2320 return;
2321} /* ht_print(...) */
2322
2329LIST* ht_search(HASH_TABLE* table, int (*node_is_matching)(HASH_NODE* node)) {
2330 __n_assert(table, return NULL);
2331 return table->ht_search(table, node_is_matching);
2332} /* ht_search(...) */
2333
2340 __n_assert(table, return FALSE);
2341 return table->empty_ht(table);
2342} /* empty_ht(...) */
2343
2350 __n_assert((*table), return FALSE);
2351 return (*table)->destroy_ht(table);
2352} /* destroy_ht(...) */
2353
2361 __n_assert(table, return NULL);
2362 __n_assert(table->mode == HASH_CLASSIC, return NULL);
2363
2364 size_t index = (hash_value) % (table->size);
2365 if (!table->hash_table[index]->start) {
2366 return NULL;
2367 }
2368
2369 list_foreach(list_node, table->hash_table[index]) {
2370 HASH_NODE* node_ptr = (HASH_NODE*)list_node->ptr;
2371 if (hash_value == node_ptr->hash_value) {
2372 return node_ptr;
2373 }
2374 }
2375 return NULL;
2376} /* ht_get_node_ex() */
2377
2385int ht_get_ptr_ex(HASH_TABLE* table, HASH_VALUE hash_value, void** val) {
2386 __n_assert(table, return FALSE);
2387 __n_assert(table->mode == HASH_CLASSIC, return FALSE);
2388
2389 HASH_NODE* node = ht_get_node_ex(table, hash_value);
2390 if (!node)
2391 return FALSE;
2392
2393 if (node->type != HASH_PTR) {
2394 n_log(LOG_ERR, "Can't get key[\"%zu\"] of type HASH_PTR, key is type %s", hash_value, ht_node_type(node));
2395 return FALSE;
2396 }
2397
2398 (*val) = node->data.ptr;
2399
2400 return TRUE;
2401} /* ht_get_ptr_ex() */
2402
2412int ht_put_ptr_ex(HASH_TABLE* table, HASH_VALUE hash_value, void* val, void (*destructor)(void* ptr), void* (*duplicator)(void* ptr)) {
2413 __n_assert(table, return FALSE);
2414 __n_assert(table->mode == HASH_CLASSIC, return FALSE);
2415
2416 size_t index = 0;
2417 HASH_NODE* new_hash_node = NULL;
2418 HASH_NODE* node_ptr = NULL;
2419
2420 index = (hash_value) % (table->size);
2421
2422 /* we have some nodes here. Let's check if the key already exists */
2423 list_foreach(list_node, table->hash_table[index]) {
2424 node_ptr = (HASH_NODE*)list_node->ptr;
2425 /* if we found the same key we just replace the value and return */
2426 if (hash_value == node_ptr->hash_value) {
2427 /* let's check the key isn't already assigned with another data type */
2428 if (node_ptr->type == HASH_PTR) {
2429 if (node_ptr->destroy_func && node_ptr->data.ptr) {
2430 node_ptr->destroy_func(node_ptr->data.ptr);
2431 } else if (!node_ptr->destroy_func && node_ptr->data.ptr) {
2432 n_log(LOG_ERR, "Can't free previous key[\"%s\"] with type HASH_PTR , no hash node destroy func", node_ptr->key);
2433 }
2434 node_ptr->destroy_func = destructor;
2435 node_ptr->duplicate_func = duplicator;
2436 node_ptr->data.ptr = val;
2437 return TRUE;
2438 }
2439 n_log(LOG_ERR, "Can't add key[\"%s\"] with type HASH_PTR , key already exist with type %s", node_ptr->key, ht_node_type(node_ptr));
2440 return FALSE; /* key registered with another data type */
2441 }
2442 }
2443
2444 Malloc(new_hash_node, HASH_NODE, 1);
2445 __n_assert(new_hash_node, n_log(LOG_ERR, "Could not allocate new_hash_node"); return FALSE);
2446
2447 new_hash_node->key = NULL;
2448 new_hash_node->hash_value = hash_value;
2449 new_hash_node->data.ptr = val;
2450 new_hash_node->type = HASH_PTR;
2451 new_hash_node->destroy_func = destructor;
2452 new_hash_node->duplicate_func = duplicator;
2453
2454 table->nb_keys++;
2455
2456 return list_push(table->hash_table[index], new_hash_node, &_ht_node_destroy);
2457} /* ht_put_ptr_ex() */
2458
2465int ht_remove_ex(HASH_TABLE* table, HASH_VALUE hash_value) {
2466 __n_assert(table, return FALSE);
2467 __n_assert(table->mode == HASH_CLASSIC, return FALSE);
2468
2469 size_t index = 0;
2470 HASH_NODE* node_ptr = NULL;
2471 LIST_NODE* node_to_kill = NULL;
2472
2473 index = (hash_value) % (table->size);
2474 if (!table->hash_table[index]->start) {
2475 n_log(LOG_ERR, "Can't remove key[\"%zu\"], table is empty", hash_value);
2476 return FALSE;
2477 }
2478
2479 list_foreach(list_node, table->hash_table[index]) {
2480 node_ptr = (HASH_NODE*)list_node->ptr;
2481 /* if we found the same */
2482 if (hash_value == node_ptr->hash_value) {
2483 node_to_kill = list_node;
2484 break;
2485 }
2486 }
2487 if (node_to_kill) {
2488 node_ptr = remove_list_node(table->hash_table[index], node_to_kill, HASH_NODE);
2489 _ht_node_destroy(node_ptr);
2490
2491 table->nb_keys--;
2492
2493 return TRUE;
2494 }
2495 n_log(LOG_ERR, "Can't delete key[\"%zu\"]: inexisting key", hash_value);
2496 return FALSE;
2497} /* ht_remove_ex() */
2498
2506LIST* ht_get_completion_list(HASH_TABLE* table, const char* keybud, size_t max_results) {
2507 __n_assert(table, return NULL);
2508 __n_assert(keybud, return NULL);
2509
2510 LIST* results = new_generic_list(max_results);
2511 if (table->mode == HASH_TRIE) {
2512 HASH_NODE* node = _ht_get_node_trie(table, keybud);
2513 if (node) {
2514 if (list_push(results, strdup(keybud), &free) == TRUE) {
2515 _ht_depth_first_search(node, results);
2516 }
2517 } else {
2518 node = table->root;
2519 for (size_t it = 0; it < table->alphabet_length; it++) {
2520 if (node->children[it]) {
2521 char new_keybud[3] = "";
2522 new_keybud[0] = (char)(it + table->alphabet_offset);
2523 list_push(results, strdup(new_keybud), &free);
2524 }
2525 }
2526 }
2527 } else if (table->mode == HASH_CLASSIC) {
2528 ht_foreach(node, table) {
2529 HASH_NODE* hnode = (HASH_NODE*)node->ptr;
2530 if (strncasecmp(keybud, hnode->key, strlen(keybud)) == 0) {
2531 char* key = strdup(hnode->key);
2532 if (list_push(results, key, &free) == FALSE) {
2533 n_log(LOG_ERR, "not enough space in list or memory error, key %s not pushed !", key);
2534 Free(key);
2535 }
2536 }
2537 }
2538 } else {
2539 n_log(LOG_ERR, "unsupported mode %d", table->mode);
2540 list_destroy(&results);
2541 return NULL;
2542 }
2543 if (results && results->nb_items < 1)
2544 list_destroy(&results);
2545 return results;
2546} /* ht_get_completion_list(...) */
2547
2553int is_prime(size_t nb) {
2554 /* quick test for first primes */
2555 if (nb <= 1) return FALSE;
2556 if (nb <= 3) return TRUE;
2557
2558 /* skip middle five numbers in below loop */
2559 if ((nb % 2 == 0) || (nb % 3 == 0))
2560 return FALSE;
2561
2562 /* looping */
2563 for (size_t it = 5; it * it <= nb; it = it + 6) {
2564 if ((nb % it == 0) || (nb % (it + 2) == 0))
2565 return FALSE;
2566 }
2567 return TRUE;
2568} /* is_prime() */
2569
2575size_t next_prime(size_t nb) {
2576 if (nb <= 1)
2577 return 2;
2578
2579 size_t next_prime = nb;
2580 do {
2581 next_prime++;
2582 } while (is_prime(next_prime) == FALSE);
2583
2584 return next_prime;
2585} /* next_prime() */
2586
2593 __n_assert(table, return FALSE);
2594 if (table->mode != HASH_CLASSIC) {
2595 n_log(LOG_ERR, "unsupported table->mode (%d instead or %d)", table->mode, HASH_CLASSIC);
2596 return FALSE;
2597 }
2598 if (table->size == 0) return FALSE;
2599
2600 size_t nb_collisionned_lists = 0;
2601
2602 for (size_t hash_it = 0; hash_it < table->size; hash_it++) {
2603 if (table->hash_table[hash_it] && table->hash_table[hash_it]->nb_items > 1) {
2604 nb_collisionned_lists++;
2605 }
2606 }
2607 size_t collision_percentage = (100 * nb_collisionned_lists) / table->size;
2608 return (int)collision_percentage;
2609} /* ht_get_table_collision_percentage() */
2610
2617 __n_assert(table, return 0);
2618 if (table->mode != HASH_CLASSIC) {
2619 n_log(LOG_ERR, "unsupported table->mode (%d instead or %d)", table->mode, HASH_CLASSIC);
2620 return FALSE;
2621 }
2622
2623 size_t optimum_size = (size_t)((double)table->nb_keys * 1.3);
2624 if (is_prime(optimum_size) != TRUE)
2625 optimum_size = next_prime(optimum_size);
2626 return optimum_size;
2627} /* ht_get_optimal_size() */
2628
2635int ht_resize(HASH_TABLE** table, size_t size) {
2636 __n_assert((*table), return FALSE);
2637 if ((*table)->mode != HASH_CLASSIC) {
2638 n_log(LOG_ERR, "unsupported table->mode (%d instead or %d)", (*table)->mode, HASH_CLASSIC);
2639 return FALSE;
2640 }
2641 if (size < 1) {
2642 n_log(LOG_ERR, "invalid size %zu for hash table %p", size, (void*)(*table));
2643 return FALSE;
2644 }
2645 /* mark every existing entry for rehash before resizing.
2646 * Using ht_foreach (plain for-loop macro) instead of HT_FOREACH
2647 * because the body needs no break/continue, and HT_FOREACH's
2648 * GCC nested-function expansion is rejected by clang's parser. */
2649 ht_foreach(it_node, (*table)) {
2650 HASH_NODE* node = (HASH_NODE*)it_node->ptr;
2651 node->need_rehash = 1;
2652 }
2653
2654 if (size > (*table)->size) {
2655 if (Realloc((*table)->hash_table, LIST*, size) == FALSE) {
2656 return FALSE;
2657 }
2658 for (size_t it = (*table)->size; it < size; it++) {
2659 (*table)->hash_table[it] = new_generic_list(MAX_LIST_ITEMS);
2660 if (!(*table)->hash_table[it]) {
2661 n_log(LOG_ERR, "Can't allocate table -> hash_table[ %zu ] !", it);
2662 /* destroy newly added slots and shrink back */
2663 for (size_t it_delete = (*table)->size; it_delete < it; it_delete++) {
2664 list_destroy(&(*table)->hash_table[it_delete]);
2665 }
2666 /* best-effort rollback: shrink back to original size.
2667 Realloc preserves the pointer on failure, which is fine here. */
2668 Realloc((*table)->hash_table, LIST*, (*table)->size);
2669 return FALSE;
2670 }
2671 }
2672 /* rehash all marked nodes into their new positions */
2673 for (size_t it = 0; it < size; it++) {
2674 if ((*table)->hash_table[it]) {
2675 while ((*table)->hash_table[it]->start) {
2676 HASH_NODE* hash_node = (HASH_NODE*)(*table)->hash_table[it]->start->ptr;
2677 if (hash_node->need_rehash == 0)
2678 break;
2679 hash_node->need_rehash = 0;
2680 LIST_NODE* node = list_node_shift((*table)->hash_table[it]);
2681 node->next = node->prev = NULL;
2682 size_t index = (hash_node->hash_value) % (size);
2683 list_node_push((*table)->hash_table[index], node);
2684 }
2685 }
2686 }
2687 } else {
2688 /* rehash nodes that need it into the smaller index space */
2689 for (size_t it = 0; it < (*table)->size; it++) {
2690 if ((*table)->hash_table[it]) {
2691 while ((*table)->hash_table[it]->start) {
2692 HASH_NODE* hash_node = (HASH_NODE*)(*table)->hash_table[it]->start->ptr;
2693 if (hash_node->need_rehash == 0)
2694 break;
2695 hash_node->need_rehash = 0;
2696 LIST_NODE* node = list_node_shift((*table)->hash_table[it]);
2697 node->next = node->prev = NULL;
2698 size_t index = (hash_node->hash_value) % (size);
2699 list_node_push((*table)->hash_table[index], node);
2700 }
2701 }
2702 }
2703 /* destroy trailing slots that are now unused */
2704 for (size_t it = size; it < (*table)->size; it++) {
2705 list_destroy(&(*table)->hash_table[it]);
2706 }
2707 /* shrink the backing array; Realloc preserves the pointer on failure.
2708 Trailing slots have already been list_destroy'd so they are NULL.
2709 (*table)->size is updated below regardless, keeping the table
2710 consistent even if the allocator cannot shrink in-place. */
2711 Realloc((*table)->hash_table, LIST*, size);
2712 }
2713 (*table)->size = size;
2714
2715 return TRUE;
2716} /* ht_resize() */
2717
2724 __n_assert((*table), return FALSE);
2725 if ((*table)->mode != HASH_CLASSIC) {
2726 n_log(LOG_ERR, "unsupported table->mode (%d instead or %d)", (*table)->mode, HASH_CLASSIC);
2727 return FALSE;
2728 }
2729
2730 size_t optimal_size = ht_get_optimal_size((*table));
2731 if (optimal_size == FALSE) {
2732 return FALSE;
2733 }
2734
2735 int collision_percentage = ht_get_table_collision_percentage((*table));
2736 if (collision_percentage == FALSE)
2737 return FALSE;
2738
2739 int resize_result = ht_resize(table, optimal_size);
2740 if (resize_result == FALSE) {
2741 return FALSE;
2742 }
2743
2744 collision_percentage = ht_get_table_collision_percentage((*table));
2745 if (collision_percentage == FALSE) {
2746 return FALSE;
2747 }
2748
2749 return TRUE;
2750} /* ht_optimize() */
2751
2758 __n_assert(table, return NULL);
2759 HASH_TABLE* duplicated_table = NULL;
2760
2761 if (table->mode != HASH_CLASSIC) {
2762 n_log(LOG_ERR, "unsupported mode %d for table %p", table->mode, table);
2763 return NULL;
2764 }
2765
2766 duplicated_table = new_ht(table->size);
2767 if (!duplicated_table) {
2768 n_log(LOG_ERR, "couldn't allocate duplicated table of %zu elements", table->size);
2769 return NULL;
2770 }
2771
2772 ht_foreach(node, table) {
2773 HASH_NODE* hash_node = (HASH_NODE*)node->ptr;
2774 int has_succeeded = TRUE;
2775 switch (hash_node->type) {
2776 case HASH_INT:
2777 has_succeeded = ht_put_int(duplicated_table, hash_node->key, hash_node->data.ival);
2778 break;
2779 case HASH_DOUBLE:
2780 has_succeeded = ht_put_double(duplicated_table, hash_node->key, hash_node->data.fval);
2781 break;
2782 case HASH_PTR: {
2783 if (hash_node->duplicate_func && hash_node->data.ptr) {
2784 /* deep copy: new entry takes ownership with the same funcs */
2785 void* duplicated_ptr = hash_node->duplicate_func(hash_node->data.ptr);
2786 if (!duplicated_ptr) {
2787 n_log(LOG_ERR, "duplicate_func returned NULL for key [%s]", hash_node->key);
2788 has_succeeded = FALSE;
2789 break;
2790 }
2791 has_succeeded = ht_put_ptr(duplicated_table, hash_node->key, duplicated_ptr, hash_node->destroy_func, hash_node->duplicate_func);
2792 } else {
2793 /* shallow copy: pass NULL destroy/duplicate so the duplicate table
2794 does not take ownership; only the source table will free the pointer */
2795 has_succeeded = ht_put_ptr(duplicated_table, hash_node->key, hash_node->data.ptr, NULL, NULL);
2796 }
2797 } break;
2798 case HASH_STRING:
2799 has_succeeded = ht_put_string(duplicated_table, hash_node->key, hash_node->data.string);
2800 break;
2801 default:
2802 n_log(LOG_ERR, "unknown node type %d for key [%s], skipping", hash_node->type, hash_node->key);
2803 break;
2804 }
2805
2806 if (has_succeeded == FALSE) {
2807 n_log(LOG_ERR, "problem when trying to duplicate value in %p, duplication cancelled", table);
2808 destroy_ht(&duplicated_table);
2809 return NULL;
2810 }
2811 }
2812
2813 return duplicated_table;
2814}
static size_t max_results
static int h(void *ctx, const N_ROUTE_MATCH *m)
a handler that does nothing (the test only routes)
volatile char key[227]
TRUE while the key is held.
#define FreeNoLog(__ptr)
Free Handler without log.
Definition n_common.h:272
#define FALL_THROUGH
set windows if true
Definition n_common.h:72
#define Malloc(__ptr, __struct, __size)
Malloc Handler to get errors and set to 0.
Definition n_common.h:204
#define __n_assert(__ptr, __ret)
macro to assert things
Definition n_common.h:279
#define FORCE_INLINE
FORCE_INLINE portable macro.
Definition n_common.h:164
#define Realloc(__ptr, __struct, __size)
Realloc Handler to get errors.
Definition n_common.h:231
#define Free(__ptr)
Free Handler to get errors.
Definition n_common.h:263
int(* ht_put_int)(struct HASH_TABLE *table, const char *key, int64_t val)
put an integer
Definition n_hash.h:158
size_t alphabet_length
HASH_TRIE mode: size of alphabet and so size of children allocated array.
Definition n_hash.h:134
int need_rehash
flag to mark a node for rehash
Definition n_hash.h:130
HASH_NODE *(* ht_get_node)(struct HASH_TABLE *table, const char *key)
get HASH_NODE at 'key' from table
Definition n_hash.h:156
char key_id
key id of the node if any
Definition n_hash.h:116
int(* ht_get_string)(struct HASH_TABLE *table, const char *key, char **val)
get a char *string from a key's node
Definition n_hash.h:174
int(* ht_put_string)(struct HASH_TABLE *table, const char *key, char *val)
put an char *string
Definition n_hash.h:164
char * key
string key of the node if any, else NULL
Definition n_hash.h:114
int64_t ival
integral type
Definition n_hash.h:102
int(* ht_put_ptr)(struct HASH_TABLE *table, const char *key, void *ptr, void(*destructor)(void *ptr), void *(*duplicator)(void *ptr))
put a a pointer
Definition n_hash.h:162
int is_leaf
HASH_TRIE mode: does it have a value.
Definition n_hash.h:128
HASH_NODE * root
HASH_TRIE mode: Start of tree.
Definition n_hash.h:148
void * ptr
pointer type
Definition n_hash.h:106
union HASH_DATA data
data inside the node
Definition n_hash.h:122
int(* ht_get_ptr)(struct HASH_TABLE *table, const char *key, void **val)
get a pointer from a key's node
Definition n_hash.h:172
int type
type of the node
Definition n_hash.h:120
int(* empty_ht)(struct HASH_TABLE *table)
empty a hash table.
Definition n_hash.h:180
LIST ** hash_table
HASH_CLASSIC mode: preallocated hash table.
Definition n_hash.h:146
size_t alphabet_offset
HASH_TRIE mode: offset to deduce to individual key digits.
Definition n_hash.h:152
int(* ht_get_double)(struct HASH_TABLE *table, const char *key, double *val)
get a double from a key's node
Definition n_hash.h:170
size_t alphabet_length
HASH_TRIE mode: size of the alphabet.
Definition n_hash.h:150
void *(* duplicate_func)(void *ptr)
duplicator_func
Definition n_hash.h:126
unsigned int mode
hashing mode, murmurhash and classic HASH_MURMUR, or HASH_TRIE
Definition n_hash.h:154
size_t seed
table's seed
Definition n_hash.h:144
int(* destroy_ht)(struct HASH_TABLE **table)
destroy a hash table
Definition n_hash.h:182
int(* ht_put_string_ptr)(struct HASH_TABLE *table, const char *key, char *val)
put an char *string pointer
Definition n_hash.h:166
int(* ht_remove)(struct HASH_TABLE *table, const char *key)
remove given's key node from the table
Definition n_hash.h:176
void(* ht_print)(struct HASH_TABLE *table)
print table
Definition n_hash.h:184
char * string
char *type
Definition n_hash.h:108
int(* ht_put_double)(struct HASH_TABLE *table, const char *key, double val)
put a double
Definition n_hash.h:160
struct HASH_NODE ** children
HASH_TRIE mode: pointers to children.
Definition n_hash.h:132
HASH_VALUE hash_value
numeric key of the node if any, else < 0
Definition n_hash.h:118
double fval
double type
Definition n_hash.h:104
size_t size
size of the hash table
Definition n_hash.h:140
int(* ht_get_int)(struct HASH_TABLE *table, const char *key, int64_t *val)
get an int from a key's node
Definition n_hash.h:168
size_t nb_keys
total number of used keys in the table
Definition n_hash.h:142
LIST *(* ht_search)(struct HASH_TABLE *table, int(*node_is_matching)(HASH_NODE *node))
search elements given an expression
Definition n_hash.h:178
void(* destroy_func)(void *ptr)
destroy_func
Definition n_hash.h:124
int ht_get_ptr(HASH_TABLE *table, const char *key, void **val)
get pointer at 'key' from 'table'
Definition n_hash.c:2215
#define ht_foreach(__ITEM_, __HASH_)
ForEach macro helper (classic / old).
Definition n_hash.h:192
LIST * ht_search(HASH_TABLE *table, int(*node_is_matching)(HASH_NODE *node))
seach table for matching nodes
Definition n_hash.c:2329
HASH_TABLE * ht_duplicate(HASH_TABLE *table)
duplicate a hash table (all pointers should have a duplicator func set)
Definition n_hash.c:2757
int destroy_ht(HASH_TABLE **table)
empty a table and destroy it
Definition n_hash.c:2349
int ht_put_ptr_ex(HASH_TABLE *table, HASH_VALUE hash_value, void *val, void(*destructor)(void *ptr), void *(*duplicator)(void *ptr))
put a pointer value with given key in the targeted hash table (HASH_CLASSIC only)
Definition n_hash.c:2412
int ht_remove(HASH_TABLE *table, const char *key)
remove and delete node at key in table
Definition n_hash.c:2307
HASH_NODE * ht_get_node_ex(HASH_TABLE *table, HASH_VALUE hash_value)
return the associated key's node inside the hash_table (HASH_CLASSIC only)
Definition n_hash.c:2360
#define HASH_PTR
value of pointer type inside the hash node
Definition n_hash.h:76
HASH_TABLE * new_ht(size_t size)
Create a hash table with the given size.
Definition n_hash.c:2116
#define MurmurHash(__key, __len, __seed, __out)
Murmur hash macro helper 64 bits.
Definition n_hash.h:91
int ht_get_table_collision_percentage(HASH_TABLE *table)
get table collision percentage (HASH_CLASSIC mode only)
Definition n_hash.c:2592
int ht_get_double(HASH_TABLE *table, const char *key, double *val)
get double at 'key' from 'table'
Definition n_hash.c:2189
#define HASH_DOUBLE
value of double type inside the hash node
Definition n_hash.h:72
int empty_ht(HASH_TABLE *table)
empty a table
Definition n_hash.c:2339
#define HASH_STRING
value of char * type inside the hash node
Definition n_hash.h:74
void ht_print(HASH_TABLE *table)
print contents of table
Definition n_hash.c:2317
LIST * ht_get_completion_list(HASH_TABLE *table, const char *keybud, size_t max_results)
get next matching keys in table tree
Definition n_hash.c:2506
size_t HASH_VALUE
type of a HASH_VALUE
Definition n_hash.h:97
int ht_put_double(HASH_TABLE *table, const char *key, double value)
put a double value with given key in the targeted hash table
Definition n_hash.c:2241
size_t ht_get_optimal_size(HASH_TABLE *table)
get optimal array size based on nb=(number_of_key*1.3) && if( !isprime(nb) )nb=nextprime(nb) (HASH_CL...
Definition n_hash.c:2616
int ht_put_ptr(HASH_TABLE *table, const char *key, void *ptr, void(*destructor)(void *ptr), void *(*duplicator)(void *ptr))
put an arbitrary pointer value with given key in the targeted hash table
Definition n_hash.c:2269
int ht_get_string(HASH_TABLE *table, const char *key, char **val)
get string at 'key' from 'table'
Definition n_hash.c:2228
int is_prime(size_t nb)
test if number is a prime number or not
Definition n_hash.c:2553
#define HASH_INT_TYPE
type of a HASH_INT in 64 bits
Definition n_hash.h:93
size_t next_prime(size_t nb)
compute next prime number after nb
Definition n_hash.c:2575
int ht_put_string(HASH_TABLE *table, const char *key, char *string)
put a string value (copy/dup) with given key in the targeted hash table
Definition n_hash.c:2282
int ht_resize(HASH_TABLE **table, size_t size)
rehash table according to size (HASH_CLASSIC mode only)
Definition n_hash.c:2635
void MurmurHash3_x86_128(const void *key, const size_t len, const uint32_t seed, void *out)
MurmurHash3 was written by Austin Appleby, and is placed in the public domain.
Definition n_hash.c:1047
void MurmurHash3_x64_128(const void *key, const size_t len, const uint64_t seed, void *out)
MurmurHash3 was written by Austin Appleby, and is placed in the public domain.
Definition n_hash.c:1215
int ht_remove_ex(HASH_TABLE *table, HASH_VALUE hash_value)
Remove a key from a hash table (HASH_CLASSIC only).
Definition n_hash.c:2465
#define HASH_CLASSIC
Murmur hash using hash key string, hash key numeric value, index table with lists of elements.
Definition n_hash.h:80
int ht_get_int(HASH_TABLE *table, const char *key, int64_t *val)
get node at 'key' from 'table'
Definition n_hash.c:2202
HASH_NODE * ht_get_node(HASH_TABLE *table, const char *key)
get node at 'key' from 'table'
Definition n_hash.c:2176
HASH_TABLE * new_ht_trie(size_t alphabet_length, size_t alphabet_offset)
create a TRIE hash table with the alphabet_size, each key value beeing decreased by alphabet_offset
Definition n_hash.c:2013
#define HASH_TRIE
TRIE tree using hash key string.
Definition n_hash.h:82
int ht_put_int(HASH_TABLE *table, const char *key, int64_t value)
put an integral value with given key in the targeted hash table
Definition n_hash.c:2254
int ht_optimize(HASH_TABLE **table)
try an automatic optimization of the table (HASH_CLASSIC mode only)
Definition n_hash.c:2723
char * ht_node_type(const HASH_NODE *node)
get the type of a node , text version
Definition n_hash.c:1337
#define HASH_INT
compatibility with existing rot func
Definition n_hash.h:70
void MurmurHash3_x86_32(const void *key, const size_t len, const uint32_t seed, void *out)
MurmurHash3 was written by Austin Appleby, and is placed in the public domain.
Definition n_hash.c:989
int ht_put_string_ptr(HASH_TABLE *table, const char *key, char *string)
put a string value (pointer) with given key in the targeted hash table
Definition n_hash.c:2295
int ht_get_ptr_ex(HASH_TABLE *table, HASH_VALUE hash_value, void **val)
Retrieve a pointer value in the hash table, at the given key.
Definition n_hash.c:2385
structure of a hash table node
Definition n_hash.h:112
structure of a hash table
Definition n_hash.h:138
size_t nb_max_items
Maximum number of items in the list.
Definition n_list.h:63
struct LIST_NODE * prev
pointer to the previous node
Definition n_list.h:54
LIST_NODE * start
pointer to the start of the list
Definition n_list.h:66
size_t nb_items
number of item currently in the list
Definition n_list.h:61
struct LIST_NODE * next
pointer to the next node
Definition n_list.h:52
int list_push(LIST *list, void *ptr, void(*destructor)(void *ptr))
Add a pointer to the end of the list.
Definition n_list.c:228
#define list_foreach(__ITEM_, __LIST_)
ForEach macro helper, safe for node removal during iteration.
Definition n_list.h:89
#define remove_list_node(__LIST_, __NODE_, __TYPE_)
Remove macro helper for void pointer casting.
Definition n_list.h:98
LIST_NODE * list_node_shift(LIST *list)
Get a LIST_NODE pointer from the start of the list.
Definition n_list.c:170
int list_destroy(LIST **list)
Empty and Free a list container.
Definition n_list.c:548
LIST * new_generic_list(size_t max_items)
Initialiaze a generic list container to max_items pointers.
Definition n_list.c:37
#define MAX_LIST_ITEMS
flag to pass to new_generic_list for the maximum possible number of item in a list
Definition n_list.h:75
int list_node_push(LIST *list, LIST_NODE *node)
Add a filled node to the end of the list.
Definition n_list.c:117
Structure of a generic LIST container.
Definition n_list.h:59
Structure of a generic list node.
Definition n_list.h:44
#define n_log(__LEVEL__,...)
Logging function wrapper to get line and func.
Definition n_log.h:113
#define LOG_DEBUG
debug-level messages
Definition n_log.h:108
#define LOG_ERR
error conditions
Definition n_log.h:100
Common headers and low-level functions & define.
HASH_NODE * _ht_new_node(const HASH_TABLE *table, const char *key)
node creation, HASH_CLASSIC mode
Definition n_hash.c:1428
void _ht_node_destroy(void *node)
destroy a HASH_NODE by first calling the HASH_NODE destructor
Definition n_hash.c:120
int _ht_put_ptr(HASH_TABLE *table, const char *key, void *ptr, void(*destructor)(void *ptr), void *(*duplicator)(void *ptr))
put a pointer value with given key in the targeted hash table
Definition n_hash.c:1651
int _ht_get_int(HASH_TABLE *table, const char *key, int64_t *val)
Retrieve an integral value in the hash table, at the given key.
Definition n_hash.c:1773
static HASH_VALUE _ht_hash_value(const HASH_TABLE *table, const char *key, size_t key_len)
compute a key's hash value with a correctly sized output buffer
Definition n_hash.c:1381
int _destroy_ht(HASH_TABLE **table)
Free and set the table to NULL.
Definition n_hash.c:1947
int _ht_get_double(HASH_TABLE *table, const char *key, double *val)
Retrieve a double value in the hash table, at the given key.
Definition n_hash.c:1801
int _ht_get_int_trie(HASH_TABLE *table, const char *key, int64_t *val)
Retrieve an integral value in the hash table, at the given key.
Definition n_hash.c:624
HASH_NODE * _ht_new_double_node(HASH_TABLE *table, const char *key, double value)
node creation, HASH_CLASSIC mode
Definition n_hash.c:1486
int _ht_put_double(HASH_TABLE *table, const char *key, double value)
put a double value with given key in the targeted hash table
Definition n_hash.c:1615
static uint64_t _ht_table_counter
Definition n_hash.c:2061
HASH_NODE * _ht_new_string_ptr_node(HASH_TABLE *table, const char *key, char *value)
node creation, HASH_CLASSIC mode, pointer to string value
Definition n_hash.c:1533
int _ht_put_string_trie(HASH_TABLE *table, const char *key, char *string)
put a duplicate of the string value with given key in the targeted hash table [TRIE HASH TABLE)
Definition n_hash.c:408
uint32_t getblock32(const uint32_t *p, const size_t i)
Block read - modified from murmur's author, ajusted byte endianess.
Definition n_hash.c:928
int _ht_get_ptr(HASH_TABLE *table, const char *key, void **val)
Retrieve a pointer value in the hash table, at the given key.
Definition n_hash.c:1830
HASH_NODE * _ht_new_node_trie(HASH_TABLE *table, const char key)
node creation, HASH_CLASSIC mode
Definition n_hash.c:62
int _ht_depth_first_search(HASH_NODE *node, LIST *results)
recursive, helper for ht_get_completion_list, get the list of leaf starting from node
Definition n_hash.c:856
HASH_NODE * _ht_new_int_node(HASH_TABLE *table, const char *key, int64_t value)
node creation, HASH_CLASSIC mode
Definition n_hash.c:1464
uint32_t fmix32(uint32_t h)
Finalization mix - force all bits of a hash block to avalanche (from murmur's author).
Definition n_hash.c:951
static void _ht_key_init(void)
Definition n_hash.c:2065
static uint64_t _ht_mix(uint64_t x)
Definition n_hash.c:2094
HASH_NODE * _ht_new_ptr_node(HASH_TABLE *table, const char *key, void *value, void(*destructor)(void *ptr), void *(*duplicator)(void *ptr))
node creation, HASH_CLASSIC mode, pointer to string value
Definition n_hash.c:1557
void _ht_print_trie(HASH_TABLE *table)
Generic print func call for trie trees.
Definition n_hash.c:799
int _ht_get_string_trie(HASH_TABLE *table, const char *key, char **val)
Retrieve an char *string value in the hash table, at the given key.
Definition n_hash.c:680
int _ht_put_int_trie(HASH_TABLE *table, const char *key, int64_t value)
put an integral value with given key in the targeted hash table [TRIE HASH TABLE)
Definition n_hash.c:298
int _ht_put_ptr_trie(HASH_TABLE *table, const char *key, void *ptr, void(*destructor)(void *ptr), void *(*duplicator)(void *ptr))
put a pointer to the string value with given key in the targeted hash table [TRIE HASH TABLE)
Definition n_hash.c:532
void _ht_print_trie_helper(HASH_TABLE *table, HASH_NODE *node)
Recursive function to print trie tree's keys and values.
Definition n_hash.c:765
HASH_NODE * _ht_get_node_trie(HASH_TABLE *table, const char *key)
retrieve a HASH_NODE at key from table
Definition n_hash.c:591
int _ht_put_string(HASH_TABLE *table, const char *key, char *string)
put a null terminated char *string with given key in the targeted hash table (copy of string)
Definition n_hash.c:1693
HASH_NODE * _ht_new_string_node(HASH_TABLE *table, const char *key, const char *value)
node creation, HASH_CLASSIC mode, strdup of value
Definition n_hash.c:1508
static pthread_once_t _ht_key_once
Definition n_hash.c:2062
int _ht_put_string_ptr_trie(HASH_TABLE *table, const char *key, char *string)
put a pointer to the string value with given key in the targeted hash table [TRIE HASH TABLE)
Definition n_hash.c:475
void _ht_print(HASH_TABLE *table)
Generic print func call for classic hash tables.
Definition n_hash.c:1968
char * _ht_find_longest_prefix_trie(HASH_TABLE *table, const char *key)
find the longest prefix string that is not the current key
Definition n_hash.c:199
int _ht_get_ptr_trie(HASH_TABLE *table, const char *key, void **val)
Retrieve a pointer value in the hash table, at the given key.
Definition n_hash.c:708
int _ht_get_string(HASH_TABLE *table, const char *key, char **val)
Retrieve a char *string value in the hash table, at the given key.
Definition n_hash.c:1857
int _empty_ht(HASH_TABLE *table)
Empty a hash table (CLASSIC mode).
Definition n_hash.c:1928
#define BIG_CONSTANT(x)
max unsigned long long
Definition n_hash.c:880
int _ht_is_leaf_node_trie(HASH_TABLE *table, const char *key)
Search a key and tell if it's holding a value (leaf).
Definition n_hash.c:96
int _ht_put_string_ptr(HASH_TABLE *table, const char *key, char *string)
put a null terminated char *string with given key in the targeted hash table (pointer)
Definition n_hash.c:1737
LIST * _ht_search_trie(HASH_TABLE *table, int(*node_is_matching)(HASH_NODE *node))
Search tree's keys and apply a matching func to put results in the list.
Definition n_hash.c:836
size_t _ht_check_trie_divergence(HASH_TABLE *table, const char *key)
check and return branching index in key if any
Definition n_hash.c:155
int _ht_put_double_trie(HASH_TABLE *table, const char *key, double value)
put a double value with given key in the targeted hash table [TRIE HASH TABLE)
Definition n_hash.c:353
HASH_NODE * _ht_get_node(HASH_TABLE *table, const char *key)
return the associated key's node inside the hash_table
Definition n_hash.c:1397
#define BYTESWAP64(x)
32 bits bytes swap
Definition n_hash.c:911
#define BYTESWAP32(x)
32 bits bytes swap
Definition n_hash.c:907
int _destroy_ht_trie(HASH_TABLE **table)
Free and set the table to NULL (TRIE mode).
Definition n_hash.c:750
int _empty_ht_trie(HASH_TABLE *table)
Empty a TRIE hash table.
Definition n_hash.c:734
int _ht_get_double_trie(HASH_TABLE *table, const char *key, double *val)
Retrieve an double value in the hash table, at the given key.
Definition n_hash.c:652
int _ht_remove(HASH_TABLE *table, const char *key)
Remove a key from a hash table.
Definition n_hash.c:1883
uint64_t getblock64(const uint64_t *p, const size_t i)
Block read - modified from murmur's author, ajusted byte endianess.
Definition n_hash.c:940
static uint64_t _ht_process_key
Definition n_hash.c:2060
int _ht_put_int(HASH_TABLE *table, const char *key, int64_t value)
put an integral value with given key in the targeted hash table [CLASSIC HASH TABLE)
Definition n_hash.c:1581
int _ht_remove_trie(HASH_TABLE *table, const char *key)
Remove a key from a trie table and destroy the node.
Definition n_hash.c:231
LIST * _ht_search(HASH_TABLE *table, int(*node_is_matching)(HASH_NODE *node))
Search hash table's keys and apply a matching func to put results in the list.
Definition n_hash.c:1986
void _ht_search_trie_helper(LIST *results, HASH_NODE *node, int(*node_is_matching)(HASH_NODE *node))
Recursive function to search tree's keys and apply a matching func to put results in the list.
Definition n_hash.c:816
static pthread_mutex_t _ht_counter_lock
Definition n_hash.c:2063
#define ROTL64(x, r)
64 bit rotate left
Definition n_hash.c:876
uint64_t fmix64(uint64_t k)
Finalization mix - force all bits of a hash block to avalanche (from murmur's author).
Definition n_hash.c:966
#define ROTL32(x, r)
32 bit rotate left
Definition n_hash.c:878
static size_t _ht_new_seed(void)
Definition n_hash.c:2102
Hash functions and table.
Generic log system.
N_STR and string function declaration.