39#if defined(__GLIBC__) && (__GLIBC__ > 2 || (__GLIBC__ == 2 && __GLIBC_MINOR__ >= 25))
40#include <sys/random.h>
41#define N_HASH_HAVE_GETRANDOM 1
68 new_hash_node->
key = NULL;
101 for (
size_t it = 0;
key[it]; it++) {
104 n_log(
LOG_ERR,
"Invalid value %zu for charater at position %zu of %s, set to 0", index, it,
key);
162 size_t last_index = 0;
170 for (
size_t it = 0; node &&
key[it] !=
'\0'; it++) {
173 n_log(
LOG_ERR,
"Invalid value %zu for charater at position %zu of %s, set to 0", index, it,
key);
180 if (it2 != (
unsigned)index && node->
children[it2]) {
203 size_t len = strlen(
key);
206 char* longest_prefix = NULL;
207 Malloc(longest_prefix,
char, len + 1);
209 memcpy(longest_prefix,
key, len);
211 longest_prefix[len] =
'\0';
215 if (branch_index > 0 && branch_index != SIZE_MAX) {
217 longest_prefix[branch_index - 1] =
'\0';
220 Realloc(longest_prefix,
char, branch_index + 1);
222 return longest_prefix;
244 if (!longest_prefix) {
248 if (longest_prefix[0] ==
'\0') {
249 Free(longest_prefix);
254 for (it = 0; longest_prefix[it] !=
'\0'; it++) {
257 n_log(
LOG_ERR,
"Invalid value %zu for charater at position %zu of %s, set to 0", index, it,
key);
260 if (node->
children[index] != NULL) {
265 Free(longest_prefix);
271 for (;
key[it] !=
'\0'; it++) {
274 n_log(
LOG_ERR,
"Invalid value %zu for charater at position %zu of %s, set to 0", index, it,
key);
284 Free(longest_prefix);
304 for (
size_t it = 0;
key[it] !=
'\0'; it++) {
307 n_log(
LOG_ERR,
"Invalid value %zu for charater at position %zu of %s, set to 0", index, it,
key);
311 if (node->
children[index] == NULL) {
359 for (
size_t it = 0;
key[it] !=
'\0'; it++) {
362 n_log(
LOG_ERR,
"Invalid value %zu for charater at position %zu of %s, set to 0", index, it,
key);
365 if (node->
children[index] == NULL) {
414 for (
size_t it = 0;
key[it] !=
'\0'; it++) {
417 n_log(
LOG_ERR,
"Invalid value %zu for charater at position %zu of %s, set to 0", index, it,
key);
420 if (node->
children[index] == NULL) {
481 for (
size_t it = 0;
key[it] !=
'\0'; it++) {
484 n_log(
LOG_ERR,
"Invalid value %zu for charater at position %zu of %s, set to 0", index, it,
key);
487 if (node->
children[index] == NULL) {
538 for (
size_t it = 0;
key[it] !=
'\0'; it++) {
541 n_log(
LOG_ERR,
"Invalid value %zu for character at position %zu of %s, set to 0", index, it,
key);
544 if (node->
children[index] == NULL) {
597 if (
key[0] !=
'\0') {
599 for (
size_t it = 0;
key[it] !=
'\0'; it++) {
602 n_log(
LOG_DEBUG,
"Invalid value %zu for charater at index %zu of %s, set to 0", index, it,
key);
605 if (node->
children[index] == NULL) {
627 if (strlen(
key) == 0)
655 if (strlen(
key) == 0)
683 if (strlen(
key) == 0)
711 if (strlen(
key) == 0)
770 printf(
"key: %s, val: ", node->
key);
771 switch (node->
type) {
773 printf(
"int: %ld", (
long)node->
data.
ival);
776 printf(
"double: %f", node->
data.
fval);
779 printf(
"ptr: %p", node->
data.
ptr);
785 printf(
"unknwow type %d", node->
type);
821 if (node_is_matching(node) == TRUE) {
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)
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)
889#elif defined(__i386) || defined(__x86_64) || defined(__alpha) || defined(__vax)
891#define BYTESWAP32(x) (x)
892#define BYTESWAP64(x) (x)
894#elif defined(__GNUC__) || defined(__clang__)
896#if __has_builtin(__builtin_bswap32)
897#define BYTESWAP32(x) __builtin_bswap32(x)
899#if __has_builtin(__builtin_bswap64)
900#define BYTESWAP64(x) __builtin_bswap64(x)
907#define BYTESWAP32(x) ((((x) & 0xFF) << 24) | (((x) >> 24) & 0xFF) | (((x) & 0x0000FF00) << 8) | (((x) & 0x00FF0000) >> 8))
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))
930 memcpy(&result, (
const uint8_t*)p + i * 4,
sizeof(result));
942 memcpy(&result, (
const uint8_t*)p + i * 8,
sizeof(result));
990 const uint8_t* data = (
const uint8_t*)
key;
991 const size_t nblocks = len / 4;
994 const uint32_t c1 = 0xcc9e2d51;
995 const uint32_t c2 = 0x1b873593;
997 const uint32_t* blocks = (
const uint32_t*)data;
999 for (
size_t i = 0; i < nblocks; i++) {
1007 h1 = h1 * 5 + 0xe6546b64;
1010 const uint8_t* tail = data + nblocks * 4;
1014 k1 ^= (uint32_t)tail[2] << 16;
1017 k1 ^= (uint32_t)tail[1] << 8;
1020 k1 ^= (uint32_t)tail[0];
1030 h1 ^= (uint32_t)len;
1032 *(uint32_t*)out = h1;
1048 const uint8_t* data = (
const uint8_t*)
key;
1049 const size_t nblocks = len / 16;
1056 const uint32_t c1 = 0x239b961b;
1057 const uint32_t c2 = 0xab0e9789;
1058 const uint32_t c3 = 0x38b34ae5;
1059 const uint32_t c4 = 0xa1e38b93;
1061 const uint32_t* blocks = (
const uint32_t*)data;
1063 for (
size_t i = 0; i < nblocks; i++) {
1075 h1 = h1 * 5 + 0x561ccd1b;
1083 h2 = h2 * 5 + 0x0bcaa747;
1091 h3 = h3 * 5 + 0x96cd1c35;
1099 h4 = h4 * 5 + 0x32ac3b17;
1103 const uint8_t* tail = data + nblocks * 16;
1105 uint32_t k1 = 0, k2 = 0, k3 = 0, k4 = 0;
1109 k4 ^= (uint32_t)tail[14] << 16;
1112 k4 ^= (uint32_t)tail[13] << 8;
1115 k4 ^= (uint32_t)tail[12];
1123 k3 ^= (uint32_t)tail[11] << 24;
1126 k3 ^= (uint32_t)tail[10] << 16;
1129 k3 ^= (uint32_t)tail[9] << 8;
1132 k3 ^= (uint32_t)tail[8];
1140 k2 ^= (uint32_t)tail[7] << 24;
1143 k2 ^= (uint32_t)tail[6] << 16;
1146 k2 ^= (uint32_t)tail[5] << 8;
1149 k2 ^= (uint32_t)tail[4];
1157 k1 ^= (uint32_t)tail[3] << 24;
1160 k1 ^= (uint32_t)tail[2] << 16;
1163 k1 ^= (uint32_t)tail[1] << 8;
1166 k1 ^= (uint32_t)tail[0];
1177 h1 ^= (uint32_t)len;
1178 h2 ^= (uint32_t)len;
1179 h3 ^= (uint32_t)len;
1180 h4 ^= (uint32_t)len;
1197 ((uint32_t*)out)[0] = h1;
1198 ((uint32_t*)out)[1] = h2;
1199 ((uint32_t*)out)[2] = h3;
1200 ((uint32_t*)out)[3] = h4;
1216 const uint8_t* data = (
const uint8_t*)
key;
1217 const size_t nblocks = len / 16;
1222 const uint64_t c1 = 0x87c37b91114253d5ULL;
1223 const uint64_t c2 = 0x4cf5ad432745937fULL;
1226 const uint64_t* blocks = (
const uint64_t*)data;
1227 for (
size_t i = 0; i < nblocks; i++) {
1238 h1 = h1 * 5 + 0x52dce729;
1247 h2 = h2 * 5 + 0x38495ab5;
1251 const uint8_t* tail = data + nblocks * 16;
1258 k2 ^= ((uint64_t)tail[14]) << 48;
1261 k2 ^= ((uint64_t)tail[13]) << 40;
1264 k2 ^= ((uint64_t)tail[12]) << 32;
1267 k2 ^= ((uint64_t)tail[11]) << 24;
1270 k2 ^= ((uint64_t)tail[10]) << 16;
1273 k2 ^= ((uint64_t)tail[9]) << 8;
1276 k2 ^= ((uint64_t)tail[8]);
1284 k1 ^= ((uint64_t)tail[7]) << 56;
1287 k1 ^= ((uint64_t)tail[6]) << 48;
1290 k1 ^= ((uint64_t)tail[5]) << 40;
1293 k1 ^= ((uint64_t)tail[4]) << 32;
1296 k1 ^= ((uint64_t)tail[3]) << 24;
1299 k1 ^= ((uint64_t)tail[2]) << 16;
1302 k1 ^= ((uint64_t)tail[1]) << 8;
1305 k1 ^= ((uint64_t)tail[0]);
1328 ((uint64_t*)out)[0] = h1;
1329 ((uint64_t*)out)[1] = h2;
1340 switch (node->
type) {
1344 return "HASH_DOUBLE";
1346 return "HASH_STRING";
1350 return "HASH_UNKNOWN";
1382 uint8_t digest[16] = {0};
1386 memcpy(&value, digest,
sizeof(value));
1408 index = (hash_value) % (table->
size);
1415 if (!strcmp(
key, node_ptr->
key)) {
1436 if (strlen(
key) == 0)
1443 new_hash_node->
key = strdup(
key);
1444 new_hash_node->
key_id =
'\0';
1447 new_hash_node->
data.
ptr = NULL;
1454 return new_hash_node;
1470 if (new_hash_node) {
1474 n_log(
LOG_ERR,
"Could not get a new node in table %p with key %s", table,
key);
1476 return new_hash_node;
1492 if (new_hash_node) {
1496 n_log(
LOG_ERR,
"Could not get a new node in table %p with key %s", table,
key);
1498 return new_hash_node;
1514 if (new_hash_node) {
1521 n_log(
LOG_ERR,
"Could not get a new node in table %p with key %s", table,
key);
1523 return new_hash_node;
1539 if (new_hash_node) {
1543 n_log(
LOG_ERR,
"Could not get a new node in table %p with key %s", table,
key);
1545 return new_hash_node;
1563 if (new_hash_node) {
1564 new_hash_node->
data.
ptr = value;
1569 n_log(
LOG_ERR,
"Could not get a new node in table %p with key %s", table,
key);
1571 return new_hash_node;
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));
1596 int retcode = FALSE;
1601 if (retcode == TRUE) {
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));
1630 int retcode = FALSE;
1635 if (retcode == TRUE) {
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));
1674 int retcode = FALSE;
1679 if (retcode == TRUE) {
1702 char* new_str = NULL;
1704 new_str = strdup(
string);
1706 n_log(
LOG_ERR,
"could not strdup char *string at %p, didn't overwrite %s",
string,
key);
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));
1718 int retcode = FALSE;
1723 if (retcode == TRUE) {
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));
1754 int retcode = FALSE;
1759 if (retcode == TRUE) {
1776 if (strlen(
key) == 0)
1805 if (strlen(
key) == 0)
1833 if (strlen(
key) == 0)
1860 if (strlen(
key) == 0)
1892 if (strlen(
key) == 0)
1896 index = (hash_value) % (table->
size);
1906 if (!strcmp(
key, node_ptr->
key)) {
1907 node_to_kill = list_node;
1932 for (index = 0; index < table->
size; index++) {
1950 if ((*table)->hash_table) {
1954 for (it = 0; it < (*table)->size; it++) {
1955 if ((*table)->hash_table[it])
1958 Free((*table)->hash_table);
1974 printf(
"key:%s node:%s\n", ht_node->
key, ht_node->
key);
1994 if (node_is_matching(hnode) == TRUE) {
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);
2068#if defined(__windows__)
2069 got = BCryptGenRandom(NULL, (PUCHAR)&k, (ULONG)
sizeof(k), BCRYPT_USE_SYSTEM_PREFERRED_RNG) == 0;
2071#ifdef N_HASH_HAVE_GETRANDOM
2072 got = getrandom(&k,
sizeof(k), GRND_NONBLOCK) == (ssize_t)
sizeof(k);
2078 int fd = open(
"/dev/urandom", O_RDONLY);
2080 got = read(fd, &k,
sizeof(k)) == (ssize_t)
sizeof(k);
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;
2095 x += 0x9E3779B97F4A7C15ULL;
2096 x = (x ^ (x >> 30)) * 0xBF58476D1CE4E5B9ULL;
2097 x = (x ^ (x >> 27)) * 0x94D049BB133111EBULL;
2098 return x ^ (x >> 31);
2135 for (it = 0; it < size; 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++) {
2272 return table->
ht_put_ptr(table,
key, ptr, destructor, duplicator);
2331 return table->
ht_search(table, node_is_matching);
2351 return (*table)->destroy_ht(table);
2364 size_t index = (hash_value) % (table->
size);
2420 index = (hash_value) % (table->
size);
2432 n_log(
LOG_ERR,
"Can't free previous key[\"%s\"] with type HASH_PTR , no hash node destroy func", node_ptr->
key);
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));
2447 new_hash_node->
key = NULL;
2449 new_hash_node->
data.
ptr = val;
2473 index = (hash_value) % (table->
size);
2475 n_log(
LOG_ERR,
"Can't remove key[\"%zu\"], table is empty", hash_value);
2483 node_to_kill = list_node;
2495 n_log(
LOG_ERR,
"Can't delete key[\"%zu\"]: inexisting key", hash_value);
2514 if (
list_push(results, strdup(keybud), &free) == TRUE) {
2521 char new_keybud[3] =
"";
2523 list_push(results, strdup(new_keybud), &free);
2530 if (strncasecmp(keybud, hnode->
key, strlen(keybud)) == 0) {
2531 char*
key = strdup(hnode->
key);
2533 n_log(
LOG_ERR,
"not enough space in list or memory error, key %s not pushed !",
key);
2543 if (results && results->
nb_items < 1)
2555 if (nb <= 1)
return FALSE;
2556 if (nb <= 3)
return TRUE;
2559 if ((nb % 2 == 0) || (nb % 3 == 0))
2563 for (
size_t it = 5; it * it <= nb; it = it + 6) {
2564 if ((nb % it == 0) || (nb % (it + 2) == 0))
2598 if (table->
size == 0)
return FALSE;
2600 size_t nb_collisionned_lists = 0;
2602 for (
size_t hash_it = 0; hash_it < table->
size; hash_it++) {
2604 nb_collisionned_lists++;
2607 size_t collision_percentage = (100 * nb_collisionned_lists) / table->
size;
2608 return (
int)collision_percentage;
2623 size_t optimum_size = (size_t)((
double)table->
nb_keys * 1.3);
2624 if (
is_prime(optimum_size) != TRUE)
2626 return optimum_size;
2642 n_log(
LOG_ERR,
"invalid size %zu for hash table %p", size, (
void*)(*table));
2654 if (size > (*table)->size) {
2655 if (
Realloc((*table)->hash_table,
LIST*, size) == FALSE) {
2658 for (
size_t it = (*table)->size; it < size; it++) {
2660 if (!(*table)->hash_table[it]) {
2661 n_log(
LOG_ERR,
"Can't allocate table -> hash_table[ %zu ] !", it);
2663 for (
size_t it_delete = (*table)->size; it_delete < it; it_delete++) {
2668 Realloc((*table)->hash_table,
LIST*, (*table)->size);
2673 for (
size_t it = 0; it < size; it++) {
2674 if ((*table)->hash_table[it]) {
2675 while ((*table)->hash_table[it]->start) {
2682 size_t index = (hash_node->
hash_value) % (size);
2689 for (
size_t it = 0; it < (*table)->size; it++) {
2690 if ((*table)->hash_table[it]) {
2691 while ((*table)->hash_table[it]->start) {
2698 size_t index = (hash_node->
hash_value) % (size);
2704 for (
size_t it = size; it < (*table)->size; it++) {
2713 (*table)->size = size;
2731 if (optimal_size == FALSE) {
2736 if (collision_percentage == FALSE)
2739 int resize_result =
ht_resize(table, optimal_size);
2740 if (resize_result == FALSE) {
2745 if (collision_percentage == FALSE) {
2767 if (!duplicated_table) {
2768 n_log(
LOG_ERR,
"couldn't allocate duplicated table of %zu elements", table->
size);
2774 int has_succeeded = TRUE;
2775 switch (hash_node->
type) {
2786 if (!duplicated_ptr) {
2787 n_log(
LOG_ERR,
"duplicate_func returned NULL for key [%s]", hash_node->
key);
2788 has_succeeded = FALSE;
2802 n_log(
LOG_ERR,
"unknown node type %d for key [%s], skipping", hash_node->
type, hash_node->
key);
2806 if (has_succeeded == FALSE) {
2807 n_log(
LOG_ERR,
"problem when trying to duplicate value in %p, duplication cancelled", table);
2813 return duplicated_table;
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.
#define FALL_THROUGH
set windows if true
#define Malloc(__ptr, __struct, __size)
Malloc Handler to get errors and set to 0.
#define __n_assert(__ptr, __ret)
macro to assert things
#define FORCE_INLINE
FORCE_INLINE portable macro.
#define Realloc(__ptr, __struct, __size)
Realloc Handler to get errors.
#define Free(__ptr)
Free Handler to get errors.
int(* ht_put_int)(struct HASH_TABLE *table, const char *key, int64_t val)
put an integer
size_t alphabet_length
HASH_TRIE mode: size of alphabet and so size of children allocated array.
int need_rehash
flag to mark a node for rehash
HASH_NODE *(* ht_get_node)(struct HASH_TABLE *table, const char *key)
get HASH_NODE at 'key' from table
char key_id
key id of the node if any
int(* ht_get_string)(struct HASH_TABLE *table, const char *key, char **val)
get a char *string from a key's node
int(* ht_put_string)(struct HASH_TABLE *table, const char *key, char *val)
put an char *string
char * key
string key of the node if any, else NULL
int64_t ival
integral type
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
int is_leaf
HASH_TRIE mode: does it have a value.
HASH_NODE * root
HASH_TRIE mode: Start of tree.
union HASH_DATA data
data inside the node
int(* ht_get_ptr)(struct HASH_TABLE *table, const char *key, void **val)
get a pointer from a key's node
int(* empty_ht)(struct HASH_TABLE *table)
empty a hash table.
LIST ** hash_table
HASH_CLASSIC mode: preallocated hash table.
size_t alphabet_offset
HASH_TRIE mode: offset to deduce to individual key digits.
int(* ht_get_double)(struct HASH_TABLE *table, const char *key, double *val)
get a double from a key's node
size_t alphabet_length
HASH_TRIE mode: size of the alphabet.
void *(* duplicate_func)(void *ptr)
duplicator_func
unsigned int mode
hashing mode, murmurhash and classic HASH_MURMUR, or HASH_TRIE
int(* destroy_ht)(struct HASH_TABLE **table)
destroy a hash table
int(* ht_put_string_ptr)(struct HASH_TABLE *table, const char *key, char *val)
put an char *string pointer
int(* ht_remove)(struct HASH_TABLE *table, const char *key)
remove given's key node from the table
void(* ht_print)(struct HASH_TABLE *table)
print table
int(* ht_put_double)(struct HASH_TABLE *table, const char *key, double val)
put a double
struct HASH_NODE ** children
HASH_TRIE mode: pointers to children.
HASH_VALUE hash_value
numeric key of the node if any, else < 0
size_t size
size of the hash table
int(* ht_get_int)(struct HASH_TABLE *table, const char *key, int64_t *val)
get an int from a key's node
size_t nb_keys
total number of used keys in the table
LIST *(* ht_search)(struct HASH_TABLE *table, int(*node_is_matching)(HASH_NODE *node))
search elements given an expression
void(* destroy_func)(void *ptr)
destroy_func
int ht_get_ptr(HASH_TABLE *table, const char *key, void **val)
get pointer at 'key' from 'table'
#define ht_foreach(__ITEM_, __HASH_)
ForEach macro helper (classic / old).
LIST * ht_search(HASH_TABLE *table, int(*node_is_matching)(HASH_NODE *node))
seach table for matching nodes
HASH_TABLE * ht_duplicate(HASH_TABLE *table)
duplicate a hash table (all pointers should have a duplicator func set)
int destroy_ht(HASH_TABLE **table)
empty a table and destroy it
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)
int ht_remove(HASH_TABLE *table, const char *key)
remove and delete node at key in table
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)
#define HASH_PTR
value of pointer type inside the hash node
HASH_TABLE * new_ht(size_t size)
Create a hash table with the given size.
#define MurmurHash(__key, __len, __seed, __out)
Murmur hash macro helper 64 bits.
int ht_get_table_collision_percentage(HASH_TABLE *table)
get table collision percentage (HASH_CLASSIC mode only)
int ht_get_double(HASH_TABLE *table, const char *key, double *val)
get double at 'key' from 'table'
#define HASH_DOUBLE
value of double type inside the hash node
int empty_ht(HASH_TABLE *table)
empty a table
#define HASH_STRING
value of char * type inside the hash node
void ht_print(HASH_TABLE *table)
print contents of table
LIST * ht_get_completion_list(HASH_TABLE *table, const char *keybud, size_t max_results)
get next matching keys in table tree
size_t HASH_VALUE
type of a HASH_VALUE
int ht_put_double(HASH_TABLE *table, const char *key, double value)
put a double value with given key in the targeted hash table
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...
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
int ht_get_string(HASH_TABLE *table, const char *key, char **val)
get string at 'key' from 'table'
int is_prime(size_t nb)
test if number is a prime number or not
#define HASH_INT_TYPE
type of a HASH_INT in 64 bits
size_t next_prime(size_t nb)
compute next prime number after nb
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
int ht_resize(HASH_TABLE **table, size_t size)
rehash table according to size (HASH_CLASSIC mode only)
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.
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.
int ht_remove_ex(HASH_TABLE *table, HASH_VALUE hash_value)
Remove a key from a hash table (HASH_CLASSIC only).
#define HASH_CLASSIC
Murmur hash using hash key string, hash key numeric value, index table with lists of elements.
int ht_get_int(HASH_TABLE *table, const char *key, int64_t *val)
get node at 'key' from 'table'
HASH_NODE * ht_get_node(HASH_TABLE *table, const char *key)
get node at 'key' from 'table'
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
#define HASH_TRIE
TRIE tree using hash key string.
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
int ht_optimize(HASH_TABLE **table)
try an automatic optimization of the table (HASH_CLASSIC mode only)
char * ht_node_type(const HASH_NODE *node)
get the type of a node , text version
#define HASH_INT
compatibility with existing rot func
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.
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
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.
structure of a hash table node
structure of a hash table
size_t nb_max_items
Maximum number of items in the list.
struct LIST_NODE * prev
pointer to the previous node
LIST_NODE * start
pointer to the start of the list
size_t nb_items
number of item currently in the list
struct LIST_NODE * next
pointer to the next node
int list_push(LIST *list, void *ptr, void(*destructor)(void *ptr))
Add a pointer to the end of the list.
#define list_foreach(__ITEM_, __LIST_)
ForEach macro helper, safe for node removal during iteration.
#define remove_list_node(__LIST_, __NODE_, __TYPE_)
Remove macro helper for void pointer casting.
LIST_NODE * list_node_shift(LIST *list)
Get a LIST_NODE pointer from the start of the list.
int list_destroy(LIST **list)
Empty and Free a list container.
LIST * new_generic_list(size_t max_items)
Initialiaze a generic list container to max_items pointers.
#define MAX_LIST_ITEMS
flag to pass to new_generic_list for the maximum possible number of item in a list
int list_node_push(LIST *list, LIST_NODE *node)
Add a filled node to the end of the list.
Structure of a generic LIST container.
Structure of a generic list node.
#define n_log(__LEVEL__,...)
Logging function wrapper to get line and func.
#define LOG_DEBUG
debug-level messages
#define LOG_ERR
error conditions
Common headers and low-level functions & define.
HASH_NODE * _ht_new_node(const HASH_TABLE *table, const char *key)
node creation, HASH_CLASSIC mode
void _ht_node_destroy(void *node)
destroy a HASH_NODE by first calling the HASH_NODE destructor
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
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.
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
int _destroy_ht(HASH_TABLE **table)
Free and set the table to NULL.
int _ht_get_double(HASH_TABLE *table, const char *key, double *val)
Retrieve a double value in the hash table, at the given key.
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.
HASH_NODE * _ht_new_double_node(HASH_TABLE *table, const char *key, double value)
node creation, HASH_CLASSIC mode
int _ht_put_double(HASH_TABLE *table, const char *key, double value)
put a double value with given key in the targeted hash table
static uint64_t _ht_table_counter
HASH_NODE * _ht_new_string_ptr_node(HASH_TABLE *table, const char *key, char *value)
node creation, HASH_CLASSIC mode, pointer to string value
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)
uint32_t getblock32(const uint32_t *p, const size_t i)
Block read - modified from murmur's author, ajusted byte endianess.
int _ht_get_ptr(HASH_TABLE *table, const char *key, void **val)
Retrieve a pointer value in the hash table, at the given key.
HASH_NODE * _ht_new_node_trie(HASH_TABLE *table, const char key)
node creation, HASH_CLASSIC mode
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
HASH_NODE * _ht_new_int_node(HASH_TABLE *table, const char *key, int64_t value)
node creation, HASH_CLASSIC mode
uint32_t fmix32(uint32_t h)
Finalization mix - force all bits of a hash block to avalanche (from murmur's author).
static void _ht_key_init(void)
static uint64_t _ht_mix(uint64_t x)
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
void _ht_print_trie(HASH_TABLE *table)
Generic print func call for trie trees.
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.
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)
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)
void _ht_print_trie_helper(HASH_TABLE *table, HASH_NODE *node)
Recursive function to print trie tree's keys and values.
HASH_NODE * _ht_get_node_trie(HASH_TABLE *table, const char *key)
retrieve a HASH_NODE at key from table
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)
HASH_NODE * _ht_new_string_node(HASH_TABLE *table, const char *key, const char *value)
node creation, HASH_CLASSIC mode, strdup of value
static pthread_once_t _ht_key_once
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)
void _ht_print(HASH_TABLE *table)
Generic print func call for classic hash tables.
char * _ht_find_longest_prefix_trie(HASH_TABLE *table, const char *key)
find the longest prefix string that is not the current key
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.
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.
int _empty_ht(HASH_TABLE *table)
Empty a hash table (CLASSIC mode).
#define BIG_CONSTANT(x)
max unsigned long long
int _ht_is_leaf_node_trie(HASH_TABLE *table, const char *key)
Search a key and tell if it's holding a value (leaf).
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)
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.
size_t _ht_check_trie_divergence(HASH_TABLE *table, const char *key)
check and return branching index in key if any
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)
HASH_NODE * _ht_get_node(HASH_TABLE *table, const char *key)
return the associated key's node inside the hash_table
#define BYTESWAP64(x)
32 bits bytes swap
#define BYTESWAP32(x)
32 bits bytes swap
int _destroy_ht_trie(HASH_TABLE **table)
Free and set the table to NULL (TRIE mode).
int _empty_ht_trie(HASH_TABLE *table)
Empty a TRIE hash table.
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.
int _ht_remove(HASH_TABLE *table, const char *key)
Remove a key from a hash table.
uint64_t getblock64(const uint64_t *p, const size_t i)
Block read - modified from murmur's author, ajusted byte endianess.
static uint64_t _ht_process_key
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)
int _ht_remove_trie(HASH_TABLE *table, const char *key)
Remove a key from a trie table and destroy the node.
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.
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.
static pthread_mutex_t _ht_counter_lock
#define ROTL64(x, r)
64 bit rotate left
uint64_t fmix64(uint64_t k)
Finalization mix - force all bits of a hash block to avalanche (from murmur's author).
#define ROTL32(x, r)
32 bit rotate left
static size_t _ht_new_seed(void)
Hash functions and table.
N_STR and string function declaration.