Nilorea Library
C utilities for networking, threading, graphics
Loading...
Searching...
No Matches
n_hash.h
Go to the documentation of this file.
1
9#ifndef NILOREA_HASH_HEADER_GUARD
10#define NILOREA_HASH_HEADER_GUARD
11
12#ifdef __cplusplus
13extern "C" {
14#endif
15
21#if defined(__linux__) || defined(_AIX) || defined(__sun)
22#include <arpa/inet.h>
23#include <string.h>
24#else
25#include <string.h>
26#endif
27
28#include <stdint.h>
29
30#include "n_common.h"
31#include "n_list.h"
32
33// #if defined(_MSC_VER)
34// #include <stdlib.h>
36// #define ROTL32(x,y) _rotl(x,y)
38// #define ROTL64(x,y) _rotl64(x,y)
40// #define BIG_CONSTANT(x) (x)
41// #else
43// #define ROTL32(x,y) rotl32(x,y)
45// #define ROTL64(x,y) rotl64(x,y)
47// #define BIG_CONSTANT(x) (x##LLU)
48// #endif /* if defined MSVC ... */
49
51#define HASH_INT 1
53#define HASH_DOUBLE 2
55#define HASH_STRING 4
57#define HASH_PTR 8
59#define HASH_UNKNOWN 16
61#define HASH_CLASSIC 128
63#define HASH_TRIE 256
64
65#ifdef ENV_32BITS
67#define MurmurHash(__key, __len, __seed, __out) MurmurHash3_x86_128(__key, __len, __seed, __out)
69#define HASH_INT_TYPE int32_t
70#else
72#define MurmurHash(__key, __len, __seed, __out) MurmurHash3_x64_128(__key, __len, __seed, __out)
74#define HASH_INT_TYPE int64_t
75#endif
76
78typedef size_t HASH_VALUE;
79
81union HASH_DATA {
83 HASH_INT_TYPE ival;
85 double fval;
87 void* ptr;
89 char* string;
90};
91
93typedef struct HASH_NODE {
95 char* key;
97 char key_id;
99 HASH_VALUE hash_value;
101 int type;
103 union HASH_DATA data;
105 void (*destroy_func)(void* ptr);
107 int is_leaf;
109 int need_rehash;
111 struct HASH_NODE** children;
113 size_t alphabet_length;
114} HASH_NODE;
115
117typedef struct HASH_TABLE {
119 size_t size;
121 size_t nb_keys;
123 size_t seed;
125 LIST** hash_table;
127 HASH_NODE* root;
129 size_t alphabet_length;
131 size_t alphabet_offset;
133 unsigned int mode;
135 HASH_NODE* (*ht_get_node)(struct HASH_TABLE* table, const char* key);
137 int (*ht_put_int)(struct HASH_TABLE* table, const char* key, HASH_INT_TYPE val);
139 int (*ht_put_double)(struct HASH_TABLE* table, const char* key, double val);
141 int (*ht_put_ptr)(struct HASH_TABLE* table, const char* key, void* ptr, void (*destructor)(void* ptr));
143 int (*ht_put_string)(struct HASH_TABLE* table, const char* key, char* val);
145 int (*ht_put_string_ptr)(struct HASH_TABLE* table, const char* key, char* val);
147 int (*ht_get_int)(struct HASH_TABLE* table, const char* key, HASH_INT_TYPE* val);
149 int (*ht_get_double)(struct HASH_TABLE* table, const char* key, double* val);
151 int (*ht_get_ptr)(struct HASH_TABLE* table, const char* key, void** val);
153 int (*ht_get_string)(struct HASH_TABLE* table, const char* key, char** val);
155 int (*ht_remove)(struct HASH_TABLE* table, const char* key);
157 LIST* (*ht_search)(struct HASH_TABLE* table, int (*node_is_matching)(HASH_NODE* node));
159 int (*empty_ht)(struct HASH_TABLE* table);
161 int (*destroy_ht)(struct HASH_TABLE** table);
163 void (*ht_print)(struct HASH_TABLE* table);
164} HASH_TABLE;
165
167#define hash_val(node, type) \
168 ((node && node->ptr) ? ((type*)(((HASH_NODE*)node->ptr)->data.ptr)) : NULL)
169
171#define ht_foreach(__ITEM_, __HASH_) \
172 if (!__HASH_) { \
173 n_log(LOG_ERR, "Error in ht_foreach, %s is NULL", #__HASH_); \
174 } else if (__HASH_->mode != HASH_CLASSIC) { \
175 n_log(LOG_ERR, "Error in ht_foreach( %s , %s ) unsupportted mode %d", #__ITEM_, #__HASH_, __HASH_->mode); \
176 } else \
177 for (size_t __hash_it = 0; __hash_it < __HASH_->size; __hash_it++) \
178 for (LIST_NODE* __ITEM_ = __HASH_->hash_table[__hash_it]->start; __ITEM_ != NULL; __ITEM_ = __ITEM_->next)
179
181#define ht_foreach_r(__ITEM_, __HASH_, __ITERATOR_) \
182 if (!__HASH_) { \
183 n_log(LOG_ERR, "Error in ht_foreach, %s is NULL", #__HASH_); \
184 } else if (__HASH_->mode != HASH_CLASSIC) { \
185 n_log(LOG_ERR, "Error in ht_foreach, %d is an unsupported mode", __HASH_->mode); \
186 } else \
187 for (size_t __ITERATOR_ = 0; __ITERATOR_ < __HASH_->size; __ITERATOR_++) \
188 for (LIST_NODE* __ITEM_ = __HASH_->hash_table[__ITERATOR_]->start; __ITEM_ != NULL; __ITEM_ = __ITEM_->next)
189
191#define HASH_VAL(node, type) \
192 ((node && node->data.ptr) ? ((type*)node->data.ptr) : NULL)
193
195#define HT_FOREACH(__ITEM_, __HASH_, ...) \
196 { \
197 do { \
198 if (!__HASH_) { \
199 n_log(LOG_ERR, "Error in ht_foreach, %s is NULL", #__HASH_); \
200 } else { \
201 if (__HASH_->mode == HASH_CLASSIC) { \
202 int CONCAT(__ht_node_trie_func_macro_break_flag_classic, __LINE__) = 0; \
203 for (size_t __hash_it = 0; __hash_it < __HASH_->size; __hash_it++) { \
204 for (LIST_NODE* __ht_list_node = __HASH_->hash_table[__hash_it]->start; __ht_list_node != NULL; __ht_list_node = __ht_list_node->next) { \
205 HASH_NODE* __ITEM_ = (HASH_NODE*)__ht_list_node->ptr; \
206 CONCAT(__ht_node_trie_func_macro_break_flag_classic, __LINE__) = 1; \
207 __VA_ARGS__ \
208 CONCAT(__ht_node_trie_func_macro_break_flag_classic, __LINE__) = 0; \
209 } \
210 if (CONCAT(__ht_node_trie_func_macro_break_flag_classic, __LINE__) == 1) \
211 break; \
212 } \
213 } else if (__HASH_->mode == HASH_TRIE) { \
214 int CONCAT(__ht_node_trie_func_macro, __LINE__)(HASH_NODE * __ITEM_) { \
215 if (!__ITEM_) return TRUE; \
216 int CONCAT(__ht_node_trie_func_macro_break_flag, __LINE__) = 1; \
217 if (__ITEM_->is_leaf) { \
218 do { \
219 __VA_ARGS__ \
220 CONCAT(__ht_node_trie_func_macro_break_flag, __LINE__) = 0; \
221 } while (0); \
222 } \
223 if (CONCAT(__ht_node_trie_func_macro_break_flag, __LINE__) == 1) return FALSE; \
224 for (size_t CONCAT(__ht_node_trie_func_it, __LINE__) = 0; CONCAT(__ht_node_trie_func_it, __LINE__) < __ITEM_->alphabet_length; CONCAT(__ht_node_trie_func_it, __LINE__)++) { \
225 if (CONCAT(__ht_node_trie_func_macro, __LINE__)(__ITEM_->children[CONCAT(__ht_node_trie_func_it, __LINE__)]) == FALSE) \
226 return FALSE; \
227 } \
228 return TRUE; \
229 } \
230 CONCAT(__ht_node_trie_func_macro, __LINE__) \
231 (__HASH_->root); \
232 } else { \
233 n_log(LOG_ERR, "Error in ht_foreach, %d is an unsupported mode", __HASH_->mode); \
234 break; \
235 } \
236 } \
237 } while (0); \
238 }
239
241#define HT_FOREACH_R(__ITEM_, __HASH_, __ITERATOR, ...) \
242 { \
243 do { \
244 if (!__HASH_) { \
245 n_log(LOG_ERR, "Error in ht_foreach, %s is NULL", #__HASH_); \
246 } else { \
247 if (__HASH_->mode == HASH_CLASSIC) { \
248 int CONCAT(__ht_node_trie_func_macro_break_flag_classic, __LINE__) = 0; \
249 LIST_NODE* CONCAT(__ht_list_node_r, __LINE__) = NULL; \
250 for (size_t __ITERATOR = 0; __ITERATOR < __HASH_->size; __ITERATOR++) { \
251 for (CONCAT(__ht_list_node_r, __LINE__) = __HASH_->hash_table[__ITERATOR]->start; CONCAT(__ht_list_node_r, __LINE__) != NULL; CONCAT(__ht_list_node_r, __LINE__) = CONCAT(__ht_list_node_r, __LINE__)->next) { \
252 HASH_NODE* __ITEM_ = (HASH_NODE*)CONCAT(__ht_list_node_r, __LINE__)->ptr; \
253 CONCAT(__ht_node_trie_func_macro_break_flag_classic, __LINE__) = 1; \
254 __VA_ARGS__ \
255 CONCAT(__ht_node_trie_func_macro_break_flag_classic, __LINE__) = 0; \
256 } \
257 if (CONCAT(__ht_node_trie_func_macro_break_flag_classic, __LINE__) == 1) \
258 break; \
259 } \
260 } else if (__HASH_->mode == HASH_TRIE) { \
261 int CONCAT(__ht_node_trie_func_macro, __LINE__)(HASH_NODE * __ITEM_) { \
262 if (!__ITEM_) return TRUE; \
263 int CONCAT(__ht_node_trie_func_macro_break_flag, __LINE__) = 1; \
264 if (__ITEM_->is_leaf) { \
265 do { \
266 __VA_ARGS__ \
267 CONCAT(__ht_node_trie_func_macro_break_flag, __LINE__) = 0; \
268 } while (0); \
269 } \
270 if (CONCAT(__ht_node_trie_func_macro_break_flag, __LINE__) == 1) return FALSE; \
271 for (size_t it = 0; it < __ITEM_->alphabet_length; it++) { \
272 if (CONCAT(__ht_node_trie_func_macro, __LINE__)(__ITEM_->children[it]) == FALSE) \
273 return FALSE; \
274 } \
275 return TRUE; \
276 } \
277 CONCAT(__ht_node_trie_func_macro, __LINE__) \
278 (__HASH_->root); \
279 } else { \
280 n_log(LOG_ERR, "Error in ht_foreach, %d is an unsupported mode", __HASH_->mode); \
281 break; \
282 } \
283 } \
284 } while (0); \
285 }
286
287void MurmurHash3_x86_32(const void* key, const size_t len, const uint32_t seed, void* out);
288// void MurmurHash3_x86_128(const void* key, int len, uint32_t seed, void* out);
289void MurmurHash3_x86_128(const void* key, const size_t len, const uint32_t seed, void* out);
290void MurmurHash3_x64_128(const void* key, const size_t len, const uint64_t seed, void* out);
291
292char* ht_node_type(HASH_NODE* node);
293HASH_NODE* ht_get_node(HASH_TABLE* table, const char* key);
294
295HASH_TABLE* new_ht(size_t size);
296HASH_TABLE* new_ht_trie(size_t alphabet_size, size_t alphabet_offset);
297
298int ht_get_double(HASH_TABLE* table, const char* key, double* val);
299int ht_get_int(HASH_TABLE* table, const char* key, HASH_INT_TYPE* val);
300int ht_get_ptr(HASH_TABLE* table, const char* key, void** val);
301int ht_get_string(HASH_TABLE* table, const char* key, char** val);
302int ht_put_double(HASH_TABLE* table, const char* key, double value);
303int ht_put_int(HASH_TABLE* table, const char* key, HASH_INT_TYPE value);
304int ht_put_ptr(HASH_TABLE* table, const char* key, void* ptr, void (*destructor)(void* ptr));
305int ht_put_string(HASH_TABLE* table, const char* key, char* string);
306int ht_put_string_ptr(HASH_TABLE* table, const char* key, char* string);
307int ht_remove(HASH_TABLE* table, const char* key);
308void ht_print(HASH_TABLE* table);
309LIST* ht_search(HASH_TABLE* table, int (*node_is_matching)(HASH_NODE* node));
310int empty_ht(HASH_TABLE* table);
311int destroy_ht(HASH_TABLE** table);
312
313HASH_NODE* ht_get_node_ex(HASH_TABLE* table, HASH_VALUE hash_value);
314int ht_put_ptr_ex(HASH_TABLE* table, HASH_VALUE hash_value, void* val, void (*destructor)(void* ptr));
315int ht_get_ptr_ex(HASH_TABLE* table, HASH_VALUE hash_value, void** val);
316int ht_remove_ex(HASH_TABLE* table, HASH_VALUE hash_value);
317
318LIST* ht_get_completion_list(HASH_TABLE* table, const char* keybud, size_t max_results);
319
320int is_prime(size_t nb);
321size_t next_prime(size_t nb);
322
323int ht_get_table_collision_percentage(HASH_TABLE* table);
324size_t ht_get_optimal_size(HASH_TABLE* table);
325int ht_resize(HASH_TABLE** table, size_t size);
326int ht_optimize(HASH_TABLE** table);
327
332#ifdef __cplusplus
333}
334#endif
335
336#endif // header guard
key
char * key
Definition ex_network_ssl.c:18
HASH_TABLE::ht_put_int
int(* ht_put_int)(struct HASH_TABLE *table, const char *key, int64_t val)
put an integer
Definition n_hash.h:137
HASH_NODE::alphabet_length
size_t alphabet_length
HASH_TRIE mode: size of alphabet and so size of children allocated array.
Definition n_hash.h:113
HASH_NODE::need_rehash
int need_rehash
flag to mark a node for rehash
Definition n_hash.h:109
HASH_NODE::key_id
char key_id
key id of the node if any
Definition n_hash.h:97
HASH_TABLE::ht_get_string
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:153
HASH_TABLE::ht_put_string
int(* ht_put_string)(struct HASH_TABLE *table, const char *key, char *val)
put an char *string
Definition n_hash.h:143
HASH_NODE::key
char * key
string key of the node if any, else NULL
Definition n_hash.h:95
HASH_DATA::ival
int64_t ival
integral type
Definition n_hash.h:83
HASH_NODE::is_leaf
int is_leaf
HASH_TRIE mode: does it have a value.
Definition n_hash.h:107
HASH_TABLE::root
HASH_NODE * root
HASH_TRIE mode: Start of tree.
Definition n_hash.h:127
HASH_DATA::ptr
void * ptr
pointer type
Definition n_hash.h:87
HASH_NODE::data
union HASH_DATA data
data inside the node
Definition n_hash.h:103
HASH_TABLE::ht_get_ptr
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:151
HASH_NODE::type
int type
type of the node
Definition n_hash.h:101
HASH_TABLE::empty_ht
int(* empty_ht)(struct HASH_TABLE *table)
empty a hash table.
Definition n_hash.h:159
HASH_TABLE::hash_table
LIST ** hash_table
HASH_CLASSIC mode: preallocated hash table.
Definition n_hash.h:125
HASH_TABLE::alphabet_offset
size_t alphabet_offset
HASH_TRIE mode: offset to deduce to individual key digits.
Definition n_hash.h:131
HASH_TABLE::ht_get_double
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:149
HASH_TABLE::alphabet_length
size_t alphabet_length
HASH_TRIE mode: size of the alphabet.
Definition n_hash.h:129
HASH_TABLE::mode
unsigned int mode
hashing mode, murmurhash and classic HASH_MURMUR, or HASH_TRIE
Definition n_hash.h:133
HASH_TABLE::seed
size_t seed
table's seed
Definition n_hash.h:123
HASH_TABLE::destroy_ht
int(* destroy_ht)(struct HASH_TABLE **table)
destroy a hash table
Definition n_hash.h:161
HASH_TABLE::ht_put_string_ptr
int(* ht_put_string_ptr)(struct HASH_TABLE *table, const char *key, char *val)
put an char *string pointer
Definition n_hash.h:145
HASH_TABLE::ht_remove
int(* ht_remove)(struct HASH_TABLE *table, const char *key)
remove given's key node from the table
Definition n_hash.h:155
HASH_TABLE::ht_print
void(* ht_print)(struct HASH_TABLE *table)
print table
Definition n_hash.h:163
HASH_DATA::string
char * string
char *type
Definition n_hash.h:89
HASH_TABLE::ht_put_double
int(* ht_put_double)(struct HASH_TABLE *table, const char *key, double val)
put a double
Definition n_hash.h:139
HASH_NODE::children
struct HASH_NODE ** children
HASH_TRIE mode: pointers to children.
Definition n_hash.h:111
HASH_NODE::hash_value
HASH_VALUE hash_value
numeric key of the node if any, else < 0
Definition n_hash.h:99
HASH_DATA::fval
double fval
double type
Definition n_hash.h:85
HASH_TABLE::size
size_t size
size of the hash table
Definition n_hash.h:119
HASH_TABLE::ht_put_ptr
int(* ht_put_ptr)(struct HASH_TABLE *table, const char *key, void *ptr, void(*destructor)(void *ptr))
put a a pointer
Definition n_hash.h:141
HASH_TABLE::ht_get_int
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:147
HASH_TABLE::nb_keys
size_t nb_keys
total number of used keys in the table
Definition n_hash.h:121
HASH_NODE::destroy_func
void(* destroy_func)(void *ptr)
destroy_func
Definition n_hash.h:105
ht_get_ptr
int ht_get_ptr(HASH_TABLE *table, const char *key, void **val)
get pointer at 'key' from 'table'
Definition n_hash.c:2015
ht_put_ptr_ex
int ht_put_ptr_ex(HASH_TABLE *table, HASH_VALUE hash_value, void *val, void(*destructor)(void *ptr))
put a pointer value with given key in the targeted hash table (HASH_CLASSIC only)
Definition n_hash.c:2213
ht_node_type
char * ht_node_type(HASH_NODE *node)
get the type of a node , text version
Definition n_hash.c:1249
ht_search
LIST * ht_search(HASH_TABLE *table, int(*node_is_matching)(HASH_NODE *node))
seach table for matching nodes
Definition n_hash.c:2128
destroy_ht
int destroy_ht(HASH_TABLE **table)
empty a table and destroy it
Definition n_hash.c:2148
ht_remove
int ht_remove(HASH_TABLE *table, const char *key)
remove and delete node at key in table
Definition n_hash.c:2106
ht_get_node_ex
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:2159
new_ht
HASH_TABLE * new_ht(size_t size)
Create a hash table with the given size.
Definition n_hash.c:1916
ht_get_table_collision_percentage
int ht_get_table_collision_percentage(HASH_TABLE *table)
get table collision percentage (HASH_CLASSIC mode only)
Definition n_hash.c:2388
ht_get_double
int ht_get_double(HASH_TABLE *table, const char *key, double *val)
get double at 'key' from 'table'
Definition n_hash.c:1989
empty_ht
int empty_ht(HASH_TABLE *table)
empty a table
Definition n_hash.c:2138
ht_print
void ht_print(HASH_TABLE *table)
print contents of table
Definition n_hash.c:2116
ht_get_completion_list
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:2303
HASH_VALUE
size_t HASH_VALUE
type of a HASH_VALUE
Definition n_hash.h:78
ht_put_double
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:2041
ht_get_optimal_size
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:2410
ht_get_string
int ht_get_string(HASH_TABLE *table, const char *key, char **val)
get string at 'key' from 'table'
Definition n_hash.c:2028
is_prime
int is_prime(size_t nb)
test if number is a prime number or not
Definition n_hash.c:2349
HASH_INT_TYPE
#define HASH_INT_TYPE
type of a HASH_INT in 64 bits
Definition n_hash.h:74
next_prime
size_t next_prime(size_t nb)
compute next prime number after nb
Definition n_hash.c:2371
ht_put_string
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:2081
ht_resize
int ht_resize(HASH_TABLE **table, size_t size)
rehash table according to size (HASH_CLASSIC mode only)
Definition n_hash.c:2425
MurmurHash3_x86_128
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:959
MurmurHash3_x64_128
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:1127
ht_remove_ex
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:2262
ht_get_int
int ht_get_int(HASH_TABLE *table, const char *key, int64_t *val)
get node at 'key' from 'table'
Definition n_hash.c:2002
ht_get_node
HASH_NODE * ht_get_node(HASH_TABLE *table, const char *key)
get node at 'key' from 'table'
Definition n_hash.c:1976
new_ht_trie
HASH_TABLE * new_ht_trie(size_t alphabet_size, 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:1870
ht_put_ptr
int ht_put_ptr(HASH_TABLE *table, const char *key, void *ptr, void(*destructor)(void *ptr))
put a pointer to the string value with given key in the targeted hash table
Definition n_hash.c:2068
ht_put_int
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:2054
ht_optimize
int ht_optimize(HASH_TABLE **table)
try an automatic optimization of the table
Definition n_hash.c:2500
MurmurHash3_x86_32
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:901
ht_put_string_ptr
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:2094
ht_get_ptr_ex
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:2187
HASH_NODE
structure of a hash table node
Definition n_hash.h:93
HASH_TABLE
structure of a hash table
Definition n_hash.h:117
HASH_DATA
union of the possibles data values of a node
Definition n_hash.h:81
LIST
Structure of a generic LIST container.
Definition n_list.h:40
n_common.h
Common headers and low-level functions & define.
n_list.h
List structures and definitions.