Nilorea Library
C utilities for networking, threading, graphics
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
65 typedef size_t HASH_VALUE ;
66
68 union HASH_DATA
69 {
71 int ival ;
73 double fval ;
75 void *ptr ;
77 char *string ;
78 };
79
80
82 typedef struct HASH_NODE
83 {
85 char *key ;
87 char key_id ;
89 HASH_VALUE hash_value ;
91 int type ;
93 union HASH_DATA data ;
95 void (*destroy_func)( void *ptr );
97 int is_leaf ;
99 int need_rehash ;
101 struct HASH_NODE **children ;
103 size_t alphabet_length ;
104 } HASH_NODE ;
105
106
108 typedef struct HASH_TABLE
109 {
111 size_t size;
113 size_t nb_keys ;
115 size_t seed ;
117 LIST **hash_table;
119 HASH_NODE *root ;
121 size_t alphabet_length ;
123 size_t alphabet_offset ;
125 unsigned int mode ;
127 HASH_NODE *(*ht_get_node)( struct HASH_TABLE *table, const char *key );
129 int (*ht_put_int)( struct HASH_TABLE *table, const char *key, int val );
131 int (*ht_put_double)( struct HASH_TABLE *table, const char *key, double val );
133 int (*ht_put_ptr)( struct HASH_TABLE *table, const char *key, void *ptr, void (*destructor)( void *ptr ) );
135 int (*ht_put_string)( struct HASH_TABLE *table, const char *key, char *val );
137 int (*ht_put_string_ptr)( struct HASH_TABLE *table, const char *key, char *val );
139 int (*ht_get_int)( struct HASH_TABLE *table, const char *key, int *val );
141 int (*ht_get_double)( struct HASH_TABLE *table, const char *key, double *val );
143 int (*ht_get_ptr)( struct HASH_TABLE *table, const char *key, void **val );
145 int (*ht_get_string)( struct HASH_TABLE *table, const char *key, char **val );
147 int (*ht_remove)( struct HASH_TABLE *table, const char *key );
149 LIST *(*ht_search)( struct HASH_TABLE *table, int (*node_is_matching)( HASH_NODE *node ) );
151 int (*empty_ht)( struct HASH_TABLE *table );
153 int (*destroy_ht)( struct HASH_TABLE **table );
155 void (*ht_print)( struct HASH_TABLE *table );
156 } HASH_TABLE ;
157
159#define hash_val( node , type )\
160 ( (node && node -> ptr) ? ( (type *)( ( (HASH_NODE *)node -> ptr )-> data . ptr) ) : NULL )
161
163#define ht_foreach( __ITEM_ , __HASH_ ) \
164 if( !__HASH_ ) \
165 { \
166 n_log( LOG_ERR , "Error in ht_foreach, %s is NULL" , #__HASH_ ); \
167 } \
168 else if( __HASH_ -> mode != HASH_CLASSIC ) \
169 { \
170 n_log( LOG_ERR , "Error in ht_foreach( %s , %s ) unsupportted mode %d" , #__ITEM_ , #__HASH_ , __HASH_ -> mode ); \
171 } \
172 else \
173 for( size_t __hash_it = 0 ; __hash_it < __HASH_ -> size ; __hash_it ++ ) \
174 for( LIST_NODE *__ITEM_ = __HASH_ -> hash_table[ __hash_it ] -> start ; __ITEM_ != NULL; __ITEM_ = __ITEM_ -> next )
175
177#define ht_foreach_r( __ITEM_ , __HASH_ , __ITERATOR_ ) \
178 if( !__HASH_ ) \
179 { \
180 n_log( LOG_ERR , "Error in ht_foreach, %s is NULL" , #__HASH_ ); \
181 } \
182 else if( __HASH_ -> mode != HASH_CLASSIC ) \
183 { \
184 n_log( LOG_ERR , "Error in ht_foreach, %d is an unsupported mode" , __HASH_ -> mode ); \
185 } \
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 { \
199 if( !__HASH_ ) \
200 { \
201 n_log( LOG_ERR , "Error in ht_foreach, %s is NULL" , #__HASH_ ); \
202 } \
203 else \
204 { \
205 if( __HASH_ -> mode == HASH_CLASSIC ) \
206 { \
207 int CONCAT(__ht_node_trie_func_macro_break_flag_classic,__LINE__) = 0 ; \
208 for( size_t __hash_it = 0 ; __hash_it < __HASH_ -> size ; __hash_it ++ ) \
209 { \
210 for( LIST_NODE *__ht_list_node = __HASH_ -> hash_table[ __hash_it ] -> start ; __ht_list_node != NULL; __ht_list_node = __ht_list_node -> next ) \
211 { \
212 HASH_NODE *__ITEM_ = (HASH_NODE *)__ht_list_node -> ptr ; \
213 CONCAT(__ht_node_trie_func_macro_break_flag_classic,__LINE__) = 1 ; \
214 __VA_ARGS__ \
215 CONCAT(__ht_node_trie_func_macro_break_flag_classic,__LINE__) = 0 ; \
216 } \
217 if( CONCAT(__ht_node_trie_func_macro_break_flag_classic,__LINE__) == 1 ) \
218 break ; \
219 } \
220 } \
221 else if( __HASH_ -> mode == HASH_TRIE ) \
222 { \
223 int CONCAT(__ht_node_trie_func_macro,__LINE__)( HASH_NODE *__ITEM_ ) \
224 { \
225 if( !__ITEM_ ) return TRUE ; \
226 int CONCAT(__ht_node_trie_func_macro_break_flag,__LINE__) = 1 ; \
227 if( __ITEM_ -> is_leaf ) \
228 { \
229 do \
230 { \
231 __VA_ARGS__ \
232 CONCAT(__ht_node_trie_func_macro_break_flag,__LINE__) = 0 ; \
233 }while ( 0 ); \
234 } \
235 if( CONCAT(__ht_node_trie_func_macro_break_flag,__LINE__) == 1 ) return FALSE ; \
236 for( size_t it = 0 ; it < __ITEM_ -> alphabet_length ; it++ ) \
237 { \
238 if( CONCAT(__ht_node_trie_func_macro,__LINE__)( __ITEM_ -> children[ it ] ) == FALSE ) \
239 return FALSE ; \
240 } \
241 return TRUE ; \
242 } \
243 CONCAT(__ht_node_trie_func_macro,__LINE__)( __HASH_ -> root ); \
244 } \
245 else \
246 { \
247 n_log( LOG_ERR , "Error in ht_foreach, %d is an unsupported mode" , __HASH_ -> mode ); \
248 break ; \
249 } \
250 } \
251 }while( 0 ); \
252 }
253
255#define HT_FOREACH_R( __ITEM_ , __HASH_ , __ITERATOR , ... ) \
256 { \
257 do \
258 { \
259 if( !__HASH_ ) \
260 { \
261 n_log( LOG_ERR , "Error in ht_foreach, %s is NULL" , #__HASH_ ); \
262 } \
263 else \
264 { \
265 if( __HASH_ -> mode == HASH_CLASSIC ) \
266 { \
267 int CONCAT(__ht_node_trie_func_macro_break_flag_classic,__LINE__) = 0 ; \
268 for( size_t __ITERATOR = 0 ; __ITERATOR < __HASH_ -> size ; __ITERATOR ++ ) \
269 { \
270 for( LIST_NODE *__ht_list_node = __HASH_ -> hash_table[ __ITERATOR ] -> start ; __ht_list_node != NULL; __ht_list_node = __ht_list_node -> next ) \
271 { \
272 HASH_NODE *__ITEM_ = (HASH_NODE *)__ht_list_node -> ptr ; \
273 CONCAT(__ht_node_trie_func_macro_break_flag_classic,__LINE__) = 1 ; \
274 __VA_ARGS__ \
275 CONCAT(__ht_node_trie_func_macro_break_flag_classic,__LINE__) = 0 ; \
276 } \
277 if( CONCAT(__ht_node_trie_func_macro_break_flag_classic,__LINE__) == 1 ) \
278 break ; \
279 } \
280 } \
281 else if( __HASH_ -> mode == HASH_TRIE ) \
282 { \
283 int CONCAT(__ht_node_trie_func_macro,__LINE__)( HASH_NODE *__ITEM_ ) \
284 { \
285 if( !__ITEM_ ) return TRUE ; \
286 int CONCAT(__ht_node_trie_func_macro_break_flag,__LINE__) = 1 ; \
287 if( __ITEM_ -> is_leaf ) \
288 { \
289 do \
290 { \
291 __VA_ARGS__ \
292 CONCAT(__ht_node_trie_func_macro_break_flag,__LINE__) = 0 ; \
293 }while ( 0 ); \
294 } \
295 if( CONCAT(__ht_node_trie_func_macro_break_flag,__LINE__) == 1 ) return FALSE ; \
296 for( size_t it = 0 ; it < __ITEM_ -> alphabet_length ; it++ ) \
297 { \
298 if( CONCAT(__ht_node_trie_func_macro,__LINE__)( __ITEM_ -> children[ it ] ) == FALSE ) \
299 return FALSE ; \
300 } \
301 return TRUE ; \
302 } \
303 CONCAT(__ht_node_trie_func_macro,__LINE__)( __HASH_ -> root ); \
304 } \
305 else \
306 { \
307 n_log( LOG_ERR , "Error in ht_foreach, %d is an unsupported mode" , __HASH_ -> mode ); \
308 break ; \
309 } \
310 } \
311 }while( 0 ); \
312 }
313
314 void MurmurHash3_x86_32 ( const void * key, int len, uint32_t seed, void * out );
315 void MurmurHash3_x86_128 ( const void * key, int len, uint32_t seed, void * out );
316 void MurmurHash3_x64_128 ( const void * key, const size_t len, const uint64_t seed, void * out );
317#ifdef ENV_32BITS
319#define MurmurHash( __key , __len , __seed , __out ) MurmurHash3_x86_128( __key, __len, __seed, __out )
320#else
322#define MurmurHash( __key , __len , __seed , __out ) MurmurHash3_x64_128( __key, __len, __seed, __out )
323#endif
324
325
326
327 char *ht_node_type( HASH_NODE *node );
328 HASH_NODE *ht_get_node( HASH_TABLE *table, const char *key );
329
330 HASH_TABLE *new_ht( size_t size );
331 HASH_TABLE *new_ht_trie( size_t alphabet_size, size_t alphabet_offset );
332
333 int ht_get_double( HASH_TABLE *table, const char *key, double *val );
334 int ht_get_int( HASH_TABLE *table, const char *key, int *val );
335 int ht_get_ptr( HASH_TABLE *table, const char *key, void **val );
336 int ht_get_string( HASH_TABLE *table, const char *key, char **val );
337 int ht_put_double( HASH_TABLE *table, const char *key, double value );
338 int ht_put_int( HASH_TABLE *table, const char *key, int value );
339 int ht_put_ptr( HASH_TABLE *table, const char *key, void *ptr, void (*destructor)(void *ptr ) );
340 int ht_put_string( HASH_TABLE *table, const char *key, char *string );
341 int ht_put_string_ptr( HASH_TABLE *table, const char *key, char *string );
342 int ht_remove( HASH_TABLE *table, const char *key );
343 void ht_print( HASH_TABLE *table );
344 LIST *ht_search( HASH_TABLE *table, int (*node_is_matching)( HASH_NODE *node ) );
345 int empty_ht( HASH_TABLE *table );
346 int destroy_ht( HASH_TABLE **table );
347
348 HASH_NODE *ht_get_node_ex( HASH_TABLE *table, HASH_VALUE hash_value );
349 int ht_put_ptr_ex( HASH_TABLE *table, HASH_VALUE hash_value, void *val, void (*destructor)( void *ptr ) );
350 int ht_get_ptr_ex( HASH_TABLE *table, HASH_VALUE hash_value, void **val );
351 int ht_remove_ex( HASH_TABLE *table, HASH_VALUE hash_value );
352
353 LIST *ht_get_completion_list( HASH_TABLE *table, const char *keybud, size_t max_results );
354
355 int is_prime( int nb );
356 int next_prime( int nb );
357
358 int ht_get_table_collision_percentage( HASH_TABLE *table );
359 int ht_get_optimal_size( HASH_TABLE *table );
360 int ht_resize( HASH_TABLE **table, size_t size );
361 int ht_optimize( HASH_TABLE **table );
362
367#ifdef __cplusplus
368}
369#endif
370
371#endif // header guard
372
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:103
HASH_NODE::need_rehash
int need_rehash
flag to mark a node for rehash
Definition: n_hash.h:99
HASH_NODE::key_id
char key_id
key id of the node if any
Definition: n_hash.h:87
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:145
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:135
HASH_NODE::key
char * key
string key of the node if any, else NULL
Definition: n_hash.h:85
HASH_NODE::is_leaf
int is_leaf
HASH_TRIE mode: does it have a value.
Definition: n_hash.h:97
HASH_TABLE::root
HASH_NODE * root
HASH_TRIE mode: Start of tree.
Definition: n_hash.h:119
HASH_DATA::ptr
void * ptr
pointer type
Definition: n_hash.h:75
HASH_NODE::data
union HASH_DATA data
data inside the node
Definition: n_hash.h:93
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:143
HASH_NODE::type
int type
type of the node
Definition: n_hash.h:91
HASH_TABLE::empty_ht
int(* empty_ht)(struct HASH_TABLE *table)
empty a hash table.
Definition: n_hash.h:151
HASH_TABLE::hash_table
LIST ** hash_table
HASH_CLASSIC mode: preallocated hash table.
Definition: n_hash.h:117
HASH_TABLE::ht_put_int
int(* ht_put_int)(struct HASH_TABLE *table, const char *key, int val)
put an integer
Definition: n_hash.h:129
HASH_TABLE::alphabet_offset
size_t alphabet_offset
HASH_TRIE mode: offset to deduce to individual key digits.
Definition: n_hash.h:123
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:141
HASH_TABLE::alphabet_length
size_t alphabet_length
HASH_TRIE mode: size of the alphabet.
Definition: n_hash.h:121
HASH_TABLE::mode
unsigned int mode
hashing mode, murmurhash and classic HASH_MURMUR, or HASH_TRIE
Definition: n_hash.h:125
HASH_TABLE::seed
size_t seed
table's seed
Definition: n_hash.h:115
HASH_TABLE::destroy_ht
int(* destroy_ht)(struct HASH_TABLE **table)
destroy a hash table
Definition: n_hash.h:153
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:137
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:147
HASH_TABLE::ht_print
void(* ht_print)(struct HASH_TABLE *table)
print table
Definition: n_hash.h:155
HASH_DATA::string
char * string
char *type
Definition: n_hash.h:77
HASH_DATA::ival
int ival
integral type
Definition: n_hash.h:71
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:131
HASH_NODE::children
struct HASH_NODE ** children
HASH_TRIE mode: pointers to children.
Definition: n_hash.h:101
HASH_NODE::hash_value
HASH_VALUE hash_value
numeric key of the node if any, else < 0
Definition: n_hash.h:89
HASH_DATA::fval
double fval
double type
Definition: n_hash.h:73
HASH_TABLE::size
size_t size
size of the hash table
Definition: n_hash.h:111
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:133
HASH_TABLE::nb_keys
size_t nb_keys
total number of used keys in the table
Definition: n_hash.h:113
HASH_NODE::destroy_func
void(* destroy_func)(void *ptr)
destroy_func
Definition: n_hash.h:95
HASH_TABLE::ht_get_int
int(* ht_get_int)(struct HASH_TABLE *table, const char *key, int *val)
get an int from a key's node
Definition: n_hash.h:139
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:2282
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:2526
ht_get_int
int ht_get_int(HASH_TABLE *table, const char *key, int *val)
get node at 'key' from 'table'
Definition: n_hash.c:2266
ht_node_type
char * ht_node_type(HASH_NODE *node)
get the type of a node , text version
Definition: n_hash.c:1422
ht_search
LIST * ht_search(HASH_TABLE *table, int(*node_is_matching)(HASH_NODE *node))
seach table for matching nodes
Definition: n_hash.c:2422
destroy_ht
int destroy_ht(HASH_TABLE **table)
empty a table and destroy it
Definition: n_hash.c:2448
ht_remove
int ht_remove(HASH_TABLE *table, const char *key)
remove and delete node at key in table
Definition: n_hash.c:2394
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:2462
MurmurHash3_x86_32
void MurmurHash3_x86_32(const void *key, int len, uint32_t seed, void *out)
MurmurHash3 was written by Austin Appleby, and is placed in the public domain.
Definition: n_hash.c:1047
new_ht
HASH_TABLE * new_ht(size_t size)
Create a hash table with the given size.
Definition: n_hash.c:2167
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:2738
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:2250
next_prime
int next_prime(int nb)
compute next prime number after nb
Definition: n_hash.c:2715
empty_ht
int empty_ht(HASH_TABLE *table)
empty a table
Definition: n_hash.c:2435
is_prime
int is_prime(int nb)
test if number is a prime number or not
Definition: n_hash.c:2690
ht_print
void ht_print(HASH_TABLE *table)
print contents of table
Definition: n_hash.c:2407
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:2630
HASH_VALUE
size_t HASH_VALUE
type of a HASH_VALUE
Definition: n_hash.h:65
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:2314
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:2298
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:2363
MurmurHash3_x86_128
void MurmurHash3_x86_128(const void *key, int len, uint32_t seed, void *out)
MurmurHash3 was written by Austin Appleby, and is placed in the public domain.
Definition: n_hash.c:1117
ht_resize
int ht_resize(HASH_TABLE **table, size_t size)
rehash table according to size (HASH_CLASSIC mode only)
Definition: n_hash.c:2785
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:1294
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:2582
ht_get_node
HASH_NODE * ht_get_node(HASH_TABLE *table, const char *key)
get node at 'key' from 'table'
Definition: n_hash.c:2234
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:2123
ht_put_int
int ht_put_int(HASH_TABLE *table, const char *key, int value)
put an integral value with given key in the targeted hash table
Definition: n_hash.c:2330
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:2347
ht_optimize
int ht_optimize(HASH_TABLE **table)
try an automatic optimization of the table
Definition: n_hash.c:2881
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:2379
ht_get_optimal_size
int 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:2765
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:2496
HASH_NODE
structure of a hash table node
Definition: n_hash.h:83
HASH_TABLE
structure of a hash table
Definition: n_hash.h:109
HASH_DATA
union of the possibles data values of a node
Definition: n_hash.h:69
LIST
Structure of a generic LIST container.
Definition: n_list.h:45
n_common.h
Common headers and low-level hugly functions & define.
n_list.h
List structures and definitions.