Nilorea Library
C utilities for networking, threading, graphics
Loading...
Searching...
No Matches
n_hash.h
Go to the documentation of this file.
1
8#ifndef NILOREA_HASH_HEADER_GUARD
9#define NILOREA_HASH_HEADER_GUARD
10
11#ifdef __cplusplus
12extern "C" {
13#endif
14
20#if defined(__linux__) || defined(_AIX) || defined(__sun)
21#include <arpa/inet.h>
22#include <string.h>
23#else
24#include <string.h>
25#endif
26
27#include <stdint.h>
28
29#include "n_common.h"
30#include "n_list.h"
31
32// #if defined(_MSC_VER)
33// #include <stdlib.h>
35// #define ROTL32(x,y) _rotl(x,y)
37// #define ROTL64(x,y) _rotl64(x,y)
39// #define BIG_CONSTANT(x) (x)
40// #else
42// #define ROTL32(x,y) rotl32(x,y)
44// #define ROTL64(x,y) rotl64(x,y)
46// #define BIG_CONSTANT(x) (x##LLU)
47// #endif /* if defined MSVC ... */
48
50#define HASH_INT 1
52#define HASH_DOUBLE 2
54#define HASH_STRING 4
56#define HASH_PTR 8
58#define HASH_UNKNOWN 16
60#define HASH_CLASSIC 128
62#define HASH_TRIE 256
63
64#ifdef ENV_32BITS
66#define MurmurHash(__key, __len, __seed, __out) MurmurHash3_x86_128(__key, __len, __seed, __out)
67#define HASH_INT_TYPE int32_t
68#else
70#define MurmurHash(__key, __len, __seed, __out) MurmurHash3_x64_128(__key, __len, __seed, __out)
71#define HASH_INT_TYPE int64_t
72#endif
73
75typedef size_t HASH_VALUE;
76
78union HASH_DATA {
80 HASH_INT_TYPE ival;
82 double fval;
84 void* ptr;
86 char* string;
87};
88
90typedef struct HASH_NODE {
92 char* key;
94 char key_id;
96 HASH_VALUE hash_value;
98 int type;
100 union HASH_DATA data;
102 void (*destroy_func)(void* ptr);
104 int is_leaf;
106 int need_rehash;
108 struct HASH_NODE** children;
110 size_t alphabet_length;
111} HASH_NODE;
112
114typedef struct HASH_TABLE {
116 size_t size;
118 size_t nb_keys;
120 size_t seed;
122 LIST** hash_table;
124 HASH_NODE* root;
126 size_t alphabet_length;
128 size_t alphabet_offset;
130 unsigned int mode;
132 HASH_NODE* (*ht_get_node)(struct HASH_TABLE* table, const char* key);
134 int (*ht_put_int)(struct HASH_TABLE* table, const char* key, HASH_INT_TYPE val);
136 int (*ht_put_double)(struct HASH_TABLE* table, const char* key, double val);
138 int (*ht_put_ptr)(struct HASH_TABLE* table, const char* key, void* ptr, void (*destructor)(void* ptr));
140 int (*ht_put_string)(struct HASH_TABLE* table, const char* key, char* val);
142 int (*ht_put_string_ptr)(struct HASH_TABLE* table, const char* key, char* val);
144 int (*ht_get_int)(struct HASH_TABLE* table, const char* key, HASH_INT_TYPE* val);
146 int (*ht_get_double)(struct HASH_TABLE* table, const char* key, double* val);
148 int (*ht_get_ptr)(struct HASH_TABLE* table, const char* key, void** val);
150 int (*ht_get_string)(struct HASH_TABLE* table, const char* key, char** val);
152 int (*ht_remove)(struct HASH_TABLE* table, const char* key);
154 LIST* (*ht_search)(struct HASH_TABLE* table, int (*node_is_matching)(HASH_NODE* node));
156 int (*empty_ht)(struct HASH_TABLE* table);
158 int (*destroy_ht)(struct HASH_TABLE** table);
160 void (*ht_print)(struct HASH_TABLE* table);
161} HASH_TABLE;
162
164#define hash_val(node, type) \
165 ((node && node->ptr) ? ((type*)(((HASH_NODE*)node->ptr)->data.ptr)) : NULL)
166
168#define ht_foreach(__ITEM_, __HASH_) \
169 if (!__HASH_) { \
170 n_log(LOG_ERR, "Error in ht_foreach, %s is NULL", #__HASH_); \
171 } else if (__HASH_->mode != HASH_CLASSIC) { \
172 n_log(LOG_ERR, "Error in ht_foreach( %s , %s ) unsupportted mode %d", #__ITEM_, #__HASH_, __HASH_->mode); \
173 } else \
174 for (size_t __hash_it = 0; __hash_it < __HASH_->size; __hash_it++) \
175 for (LIST_NODE* __ITEM_ = __HASH_->hash_table[__hash_it]->start; __ITEM_ != NULL; __ITEM_ = __ITEM_->next)
176
178#define ht_foreach_r(__ITEM_, __HASH_, __ITERATOR_) \
179 if (!__HASH_) { \
180 n_log(LOG_ERR, "Error in ht_foreach, %s is NULL", #__HASH_); \
181 } else if (__HASH_->mode != HASH_CLASSIC) { \
182 n_log(LOG_ERR, "Error in ht_foreach, %d is an unsupported mode", __HASH_->mode); \
183 } else \
184 for (size_t __ITERATOR_ = 0; __ITERATOR_ < __HASH_->size; __ITERATOR_++) \
185 for (LIST_NODE* __ITEM_ = __HASH_->hash_table[__ITERATOR_]->start; __ITEM_ != NULL; __ITEM_ = __ITEM_->next)
186
188#define HASH_VAL(node, type) \
189 ((node && node->data.ptr) ? ((type*)node->data.ptr) : NULL)
190
192#define HT_FOREACH(__ITEM_, __HASH_, ...) \
193 { \
194 do { \
195 if (!__HASH_) { \
196 n_log(LOG_ERR, "Error in ht_foreach, %s is NULL", #__HASH_); \
197 } else { \
198 if (__HASH_->mode == HASH_CLASSIC) { \
199 int CONCAT(__ht_node_trie_func_macro_break_flag_classic, __LINE__) = 0; \
200 for (size_t __hash_it = 0; __hash_it < __HASH_->size; __hash_it++) { \
201 for (LIST_NODE* __ht_list_node = __HASH_->hash_table[__hash_it]->start; __ht_list_node != NULL; __ht_list_node = __ht_list_node->next) { \
202 HASH_NODE* __ITEM_ = (HASH_NODE*)__ht_list_node->ptr; \
203 CONCAT(__ht_node_trie_func_macro_break_flag_classic, __LINE__) = 1; \
204 __VA_ARGS__ \
205 CONCAT(__ht_node_trie_func_macro_break_flag_classic, __LINE__) = 0; \
206 } \
207 if (CONCAT(__ht_node_trie_func_macro_break_flag_classic, __LINE__) == 1) \
208 break; \
209 } \
210 } else if (__HASH_->mode == HASH_TRIE) { \
211 int CONCAT(__ht_node_trie_func_macro, __LINE__)(HASH_NODE * __ITEM_) { \
212 if (!__ITEM_) return TRUE; \
213 int CONCAT(__ht_node_trie_func_macro_break_flag, __LINE__) = 1; \
214 if (__ITEM_->is_leaf) { \
215 do { \
216 __VA_ARGS__ \
217 CONCAT(__ht_node_trie_func_macro_break_flag, __LINE__) = 0; \
218 } while (0); \
219 } \
220 if (CONCAT(__ht_node_trie_func_macro_break_flag, __LINE__) == 1) return FALSE; \
221 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__)++) { \
222 if (CONCAT(__ht_node_trie_func_macro, __LINE__)(__ITEM_->children[CONCAT(__ht_node_trie_func_it, __LINE__)]) == FALSE) \
223 return FALSE; \
224 } \
225 return TRUE; \
226 } \
227 CONCAT(__ht_node_trie_func_macro, __LINE__) \
228 (__HASH_->root); \
229 } else { \
230 n_log(LOG_ERR, "Error in ht_foreach, %d is an unsupported mode", __HASH_->mode); \
231 break; \
232 } \
233 } \
234 } while (0); \
235 }
236
238#define HT_FOREACH_R(__ITEM_, __HASH_, __ITERATOR, ...) \
239 { \
240 do { \
241 if (!__HASH_) { \
242 n_log(LOG_ERR, "Error in ht_foreach, %s is NULL", #__HASH_); \
243 } else { \
244 if (__HASH_->mode == HASH_CLASSIC) { \
245 int CONCAT(__ht_node_trie_func_macro_break_flag_classic, __LINE__) = 0; \
246 LIST_NODE* CONCAT(__ht_list_node_r, __LINE__) = NULL; \
247 for (size_t __ITERATOR = 0; __ITERATOR < __HASH_->size; __ITERATOR++) { \
248 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) { \
249 HASH_NODE* __ITEM_ = (HASH_NODE*)CONCAT(__ht_list_node_r, __LINE__)->ptr; \
250 CONCAT(__ht_node_trie_func_macro_break_flag_classic, __LINE__) = 1; \
251 __VA_ARGS__ \
252 CONCAT(__ht_node_trie_func_macro_break_flag_classic, __LINE__) = 0; \
253 } \
254 if (CONCAT(__ht_node_trie_func_macro_break_flag_classic, __LINE__) == 1) \
255 break; \
256 } \
257 } else if (__HASH_->mode == HASH_TRIE) { \
258 int CONCAT(__ht_node_trie_func_macro, __LINE__)(HASH_NODE * __ITEM_) { \
259 if (!__ITEM_) return TRUE; \
260 int CONCAT(__ht_node_trie_func_macro_break_flag, __LINE__) = 1; \
261 if (__ITEM_->is_leaf) { \
262 do { \
263 __VA_ARGS__ \
264 CONCAT(__ht_node_trie_func_macro_break_flag, __LINE__) = 0; \
265 } while (0); \
266 } \
267 if (CONCAT(__ht_node_trie_func_macro_break_flag, __LINE__) == 1) return FALSE; \
268 for (size_t it = 0; it < __ITEM_->alphabet_length; it++) { \
269 if (CONCAT(__ht_node_trie_func_macro, __LINE__)(__ITEM_->children[it]) == FALSE) \
270 return FALSE; \
271 } \
272 return TRUE; \
273 } \
274 CONCAT(__ht_node_trie_func_macro, __LINE__) \
275 (__HASH_->root); \
276 } else { \
277 n_log(LOG_ERR, "Error in ht_foreach, %d is an unsupported mode", __HASH_->mode); \
278 break; \
279 } \
280 } \
281 } while (0); \
282 }
283
284void MurmurHash3_x86_32(const void* key, const size_t len, const uint32_t seed, void* out);
285// void MurmurHash3_x86_128(const void* key, int len, uint32_t seed, void* out);
286void MurmurHash3_x86_128(const void* key, const size_t len, const uint32_t seed, void* out);
287void MurmurHash3_x64_128(const void* key, const size_t len, const uint64_t seed, void* out);
288
289char* ht_node_type(HASH_NODE* node);
290HASH_NODE* ht_get_node(HASH_TABLE* table, const char* key);
291
292HASH_TABLE* new_ht(size_t size);
293HASH_TABLE* new_ht_trie(size_t alphabet_size, size_t alphabet_offset);
294
295int ht_get_double(HASH_TABLE* table, const char* key, double* val);
296int ht_get_int(HASH_TABLE* table, const char* key, HASH_INT_TYPE* val);
297int ht_get_ptr(HASH_TABLE* table, const char* key, void** val);
298int ht_get_string(HASH_TABLE* table, const char* key, char** val);
299int ht_put_double(HASH_TABLE* table, const char* key, double value);
300int ht_put_int(HASH_TABLE* table, const char* key, HASH_INT_TYPE value);
301int ht_put_ptr(HASH_TABLE* table, const char* key, void* ptr, void (*destructor)(void* ptr));
302int ht_put_string(HASH_TABLE* table, const char* key, char* string);
303int ht_put_string_ptr(HASH_TABLE* table, const char* key, char* string);
304int ht_remove(HASH_TABLE* table, const char* key);
305void ht_print(HASH_TABLE* table);
306LIST* ht_search(HASH_TABLE* table, int (*node_is_matching)(HASH_NODE* node));
307int empty_ht(HASH_TABLE* table);
308int destroy_ht(HASH_TABLE** table);
309
310HASH_NODE* ht_get_node_ex(HASH_TABLE* table, HASH_VALUE hash_value);
311int ht_put_ptr_ex(HASH_TABLE* table, HASH_VALUE hash_value, void* val, void (*destructor)(void* ptr));
312int ht_get_ptr_ex(HASH_TABLE* table, HASH_VALUE hash_value, void** val);
313int ht_remove_ex(HASH_TABLE* table, HASH_VALUE hash_value);
314
315LIST* ht_get_completion_list(HASH_TABLE* table, const char* keybud, size_t max_results);
316
317int is_prime(size_t nb);
318size_t next_prime(size_t nb);
319
320int ht_get_table_collision_percentage(HASH_TABLE* table);
321size_t ht_get_optimal_size(HASH_TABLE* table);
322int ht_resize(HASH_TABLE** table, size_t size);
323int ht_optimize(HASH_TABLE** table);
324
329#ifdef __cplusplus
330}
331#endif
332
333#endif // header guard
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:134
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:110
HASH_NODE::need_rehash
int need_rehash
flag to mark a node for rehash
Definition n_hash.h:106
HASH_NODE::key_id
char key_id
key id of the node if any
Definition n_hash.h:94
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:150
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:140
HASH_NODE::key
char * key
string key of the node if any, else NULL
Definition n_hash.h:92
HASH_DATA::ival
int64_t ival
integral type
Definition n_hash.h:80
HASH_NODE::is_leaf
int is_leaf
HASH_TRIE mode: does it have a value.
Definition n_hash.h:104
HASH_TABLE::root
HASH_NODE * root
HASH_TRIE mode: Start of tree.
Definition n_hash.h:124
HASH_DATA::ptr
void * ptr
pointer type
Definition n_hash.h:84
HASH_NODE::data
union HASH_DATA data
data inside the node
Definition n_hash.h:100
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:148
HASH_NODE::type
int type
type of the node
Definition n_hash.h:98
HASH_TABLE::empty_ht
int(* empty_ht)(struct HASH_TABLE *table)
empty a hash table.
Definition n_hash.h:156
HASH_TABLE::hash_table
LIST ** hash_table
HASH_CLASSIC mode: preallocated hash table.
Definition n_hash.h:122
HASH_TABLE::alphabet_offset
size_t alphabet_offset
HASH_TRIE mode: offset to deduce to individual key digits.
Definition n_hash.h:128
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:146
HASH_TABLE::alphabet_length
size_t alphabet_length
HASH_TRIE mode: size of the alphabet.
Definition n_hash.h:126
HASH_TABLE::mode
unsigned int mode
hashing mode, murmurhash and classic HASH_MURMUR, or HASH_TRIE
Definition n_hash.h:130
HASH_TABLE::seed
size_t seed
table's seed
Definition n_hash.h:120
HASH_TABLE::destroy_ht
int(* destroy_ht)(struct HASH_TABLE **table)
destroy a hash table
Definition n_hash.h:158
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:142
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:152
HASH_TABLE::ht_print
void(* ht_print)(struct HASH_TABLE *table)
print table
Definition n_hash.h:160
HASH_DATA::string
char * string
char *type
Definition n_hash.h:86
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:136
HASH_NODE::children
struct HASH_NODE ** children
HASH_TRIE mode: pointers to children.
Definition n_hash.h:108
HASH_NODE::hash_value
HASH_VALUE hash_value
numeric key of the node if any, else < 0
Definition n_hash.h:96
HASH_DATA::fval
double fval
double type
Definition n_hash.h:82
HASH_TABLE::size
size_t size
size of the hash table
Definition n_hash.h:116
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:138
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:144
HASH_TABLE::nb_keys
size_t nb_keys
total number of used keys in the table
Definition n_hash.h:118
HASH_NODE::destroy_func
void(* destroy_func)(void *ptr)
destroy_func
Definition n_hash.h:102
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:2047
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:2245
ht_node_type
char * ht_node_type(HASH_NODE *node)
get the type of a node , text version
Definition n_hash.c:1271
ht_search
LIST * ht_search(HASH_TABLE *table, int(*node_is_matching)(HASH_NODE *node))
seach table for matching nodes
Definition n_hash.c:2160
destroy_ht
int destroy_ht(HASH_TABLE **table)
empty a table and destroy it
Definition n_hash.c:2180
ht_remove
int ht_remove(HASH_TABLE *table, const char *key)
remove and delete node at key in table
Definition n_hash.c:2138
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:2191
new_ht
HASH_TABLE * new_ht(size_t size)
Create a hash table with the given size.
Definition n_hash.c:1948
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:2420
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:2021
empty_ht
int empty_ht(HASH_TABLE *table)
empty a table
Definition n_hash.c:2170
ht_print
void ht_print(HASH_TABLE *table)
print contents of table
Definition n_hash.c:2148
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:2335
HASH_VALUE
size_t HASH_VALUE
type of a HASH_VALUE
Definition n_hash.h:75
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:2073
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:2442
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:2060
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:2113
ht_resize
int ht_resize(HASH_TABLE **table, size_t size)
rehash table according to size (HASH_CLASSIC mode only)
Definition n_hash.c:2457
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:981
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:1149
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:2294
ht_get_node
HASH_NODE * ht_get_node(HASH_TABLE *table, const char *key)
get node at 'key' from 'table'
Definition n_hash.c:2008
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:1902
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:2100
ht_optimize
int ht_optimize(HASH_TABLE **table)
try an automatic optimization of the table
Definition n_hash.c:2532
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:923
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:2126
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:2219
HASH_NODE
structure of a hash table node
Definition n_hash.h:90
HASH_TABLE
structure of a hash table
Definition n_hash.h:114
HASH_DATA
union of the possibles data values of a node
Definition n_hash.h:78
LIST
Structure of a generic LIST container.
Definition n_list.h:39
n_common.h
Common headers and low-level functions & define.
n_list.h
List structures and definitions.