Nilorea Library
C utilities for networking, threading, graphics
Loading...
Searching...
No Matches
n_hash.c
Go to the documentation of this file.
1
8#include "nilorea/n_common.h"
9#include "nilorea/n_log.h"
10#include "nilorea/n_hash.h"
11#include "nilorea/n_str.h"
12
13#include <pthread.h>
14#include <string.h>
15#include <strings.h>
16
17#ifdef __windows__
18#include <winsock.h>
19#else
20#include <arpa/inet.h>
21#endif
22
23/************ TRIE TREE TABLES ************/
24
32HASH_NODE *_ht_new_node_trie( HASH_TABLE *table, const char key )
33{
34 __n_assert( table, return NULL );
35
36 HASH_NODE *new_hash_node = NULL ;
37 Malloc( new_hash_node, HASH_NODE, 1 );
38 __n_assert( new_hash_node, n_log( LOG_ERR, "Could not allocate new_hash_node" ); return NULL );
39 new_hash_node -> key = NULL ;
40 new_hash_node -> hash_value = 0 ;
41 new_hash_node -> data. ptr = NULL ;
42 new_hash_node -> destroy_func = NULL ;
43 new_hash_node -> children = NULL ;
44 new_hash_node -> is_leaf = 0 ;
45 new_hash_node -> need_rehash = 0 ;
46 new_hash_node -> alphabet_length = table -> alphabet_length ;
47
48 Malloc( new_hash_node -> children, HASH_NODE *, table -> alphabet_length );
49 __n_assert( new_hash_node -> children, n_log( LOG_ERR, "Could not allocate new_hash_node" ); Free( new_hash_node ); return NULL );
50
51 /* n_log( LOG_DEBUG , "node: %d %c table: alpha: %d / offset %d" , key , key , table -> alphabet_length , table -> alphabet_offset ); */
52
53 for( size_t it = 0 ; it < table -> alphabet_length ; it++ )
54 {
55 new_hash_node -> children[ it ] = NULL;
56 }
57 new_hash_node -> is_leaf = 0 ;
58 new_hash_node -> key_id = key ;
59 return new_hash_node;
60} /* _ht_new_node_trie(...) */
61
62
72int _ht_put_int_trie( HASH_TABLE *table, const char *key, int value )
73{
74 __n_assert( table, return FALSE );
75 __n_assert( key, return FALSE );
76
77 HASH_NODE *node = table -> root ;
78
79 for( size_t it = 0 ; key[ it ] != '\0' ; it++ )
80 {
81 size_t index = (size_t)key[ it ] - table -> alphabet_offset ;
82 if( index >= table -> alphabet_length )
83 {
84 n_log( LOG_ERR, "Invalid value %d for charater at position %d of %s, set to 0", index, it, key );
85 index = 0 ;
86 }
87 /* n_log( LOG_DEBUG , "index:%d" , index ); */
88 if( node -> children[ index ] == NULL )
89 {
90 /* create a node */
91 node -> children[ index ] = _ht_new_node_trie( table, key[ it ] );
92 __n_assert( node -> children[ index ], return FALSE );
93 }
94 else
95 {
96 /* nothing to do since node is existing */
97 }
98 /* go down a level, to the child referenced by index */
99 node = node -> children[ index ];
100 }
101 /* At the end of the key, mark this node as the leaf node */
102 node -> is_leaf = 1;
103 /* Put the key */
104 node -> key = strdup( key );
105 /* Put the value */
106 node -> data . ival = value ;
107 node -> type = HASH_INT ;
108
109 table -> nb_keys ++ ;
110
111 return TRUE;
112} /* _ht_put_int_trie(...) */
113
114
115
125int _ht_put_double_trie( HASH_TABLE *table, const char *key, double value )
126{
127 __n_assert( table, return FALSE );
128 __n_assert( key, return FALSE );
129
130 HASH_NODE *node = table -> root ;
131
132 for( size_t it = 0 ; key[ it ] != '\0' ; it++ )
133 {
134 size_t index = (size_t)key[ it ] - table -> alphabet_offset ;
135 if( index >= table -> alphabet_length )
136 {
137 n_log( LOG_ERR, "Invalid value %d for charater at position %d of %s, set to 0", index, it, key );
138 index = 0 ;
139 }
140 if( node -> children[ index ] == NULL )
141 {
142 /* create a node */
143 node -> children[ index ] = _ht_new_node_trie( table, key[ it ] );
144 __n_assert( node -> children[ index ], return FALSE );
145 }
146 else
147 {
148 /* nothing to do since node is existing */
149 }
150 /* go down a level, to the child referenced by index */
151 node = node -> children[ index ];
152 }
153 /* At the end of the key, mark this node as the leaf node */
154 node -> is_leaf = 1;
155 /* Put the key */
156 node -> key = strdup( key );
157 /* Put the value */
158 node -> data . fval = value ;
159 node -> type = HASH_DOUBLE ;
160
161 table -> nb_keys ++ ;
162
163 return TRUE;
164} /* _ht_put_double_trie(...) */
165
166
167
177int _ht_put_string_trie( HASH_TABLE *table, const char *key, char *string )
178{
179 __n_assert( table, return FALSE );
180 __n_assert( key, return FALSE );
181
182 HASH_NODE *node = table -> root ;
183
184 for( size_t it = 0 ; key[ it ] != '\0' ; it++ )
185 {
186 size_t index = (size_t)key[ it ] - table -> alphabet_offset ;
187 if( index >= table -> alphabet_length )
188 {
189 n_log( LOG_ERR, "Invalid value %d for charater at position %d of %s, set to 0", index, it, key );
190 index = 0 ;
191 }
192 if( node -> children[ index ] == NULL )
193 {
194 /* create a node */
195 node -> children[ index ] = _ht_new_node_trie( table, key[ it ] );
196 __n_assert( node -> children[ index ], return FALSE );
197 }
198 else
199 {
200 /* nothing to do since node is existing */
201 }
202 /* go down a level, to the child referenced by index */
203 node = node -> children[ index ];
204 }
205 /* At the end of the key, mark this node as the leaf node */
206 node -> is_leaf = 1;
207 /* Put the key */
208 node -> key = strdup( key );
209 /* Put the value */
210 if( string )
211 node -> data . string = strdup( string );
212 else
213 node -> data . string = NULL ;
214
215 node -> type = HASH_STRING ;
216
217 table -> nb_keys ++ ;
218
219 return TRUE;
220} /* _ht_put_string_trie(...) */
221
222
223
233int _ht_put_string_ptr_trie( HASH_TABLE *table, const char *key, char *string )
234{
235 __n_assert( table, return FALSE );
236 __n_assert( key, return FALSE );
237
238 HASH_NODE *node = table -> root ;
239
240 for( size_t it = 0 ; key[ it ] != '\0' ; it++ )
241 {
242 size_t index = (size_t)key[ it ] - table -> alphabet_offset ;
243 if( index >= table -> alphabet_length )
244 {
245 n_log( LOG_ERR, "Invalid value %d for charater at position %d of %s, set to 0", index, it, key );
246 index = 0 ;
247 }
248 if( node -> children[ index ] == NULL )
249 {
250 /* create a node */
251 node -> children[ index ] = _ht_new_node_trie( table, key[ it ] );
252 __n_assert( node -> children[ index ], return FALSE );
253 }
254 else
255 {
256 /* nothing to do since node is existing */
257 }
258 /* go down a level, to the child referenced by index */
259 node = node -> children[ index ];
260 }
261 /* At the end of the key, mark this node as the leaf node */
262 node -> is_leaf = 1;
263 /* Put the key */
264 node -> key = strdup( key );
265 /* Put the string */
266 node -> data . string = string ;
267 node -> type = HASH_STRING ;
268
269 table -> nb_keys ++ ;
270
271 return TRUE;
272} /* _ht_put_string_ptr_trie(...) */
273
274
275
286int _ht_put_ptr_trie( HASH_TABLE *table, const char *key, void *ptr, void (*destructor)(void *ptr ) )
287{
288 __n_assert( table, return FALSE );
289 __n_assert( key, return FALSE );
290
291 HASH_NODE *node = table -> root ;
292
293 for( size_t it = 0 ; key[ it ] != '\0' ; it++ )
294 {
295 size_t index = ( (size_t)(key[ it ] - table -> alphabet_offset) ) % table -> alphabet_length;
296 if( index >= table -> alphabet_length )
297 {
298 n_log( LOG_ERR, "Invalid value %u for charater at position %d of %s, set to 0", index, it, key );
299 index = 0 ;
300 }
301 if( node -> children[ index ] == NULL )
302 {
303 /* create a node */
304 node -> children[ index ] = _ht_new_node_trie( table, key[ it ] );
305 __n_assert( node -> children[ index ], return FALSE );
306 }
307 else
308 {
309 /* nothing to do since node is existing */
310 }
311 /* go down a level, to the child referenced by index */
312 node = node -> children[ index ];
313 }
314 /* At the end of the key, mark this node as the leaf node */
315 node -> is_leaf = 1;
316 /* Put the key */
317 node -> key = strdup( key );
318 /* Put the value */
319 node -> data . ptr = ptr ;
320 if( destructor )
321 node -> destroy_func = destructor ;
322 node -> type = HASH_PTR ;
323
324 table -> nb_keys ++ ;
325
326 return TRUE;
327} /* _ht_put_ptr_trie(...) */
328
329
330
339HASH_NODE *_ht_get_node_trie( HASH_TABLE *table, const char *key )
340{
341 __n_assert( table, return NULL );
342 __n_assert( key, return NULL );
343
344 HASH_NODE *node = NULL ;
345
346 if( key[ 0 ] != '\0' )
347 {
348 node = table -> root;
349 for( size_t it = 0 ; key[ it ] != '\0' ; it++ )
350 {
351 size_t index = (size_t)key[ it ] - table -> alphabet_offset ;
352 if( index >= table -> alphabet_length )
353 {
354 n_log( LOG_DEBUG, "Invalid value %d for charater at index %d of %s, set to 0", index, it, key );
355 return NULL;
356 }
357 if( node -> children[ index ] == NULL )
358 {
359 /* not found */
360 return NULL;
361 }
362 node = node -> children[ index ];
363 }
364 }
365 else
366 {
367 node = NULL ;
368 }
369 return node ;
370} /* _ht_get_node_trie(...) */
371
372
373
381int _ht_get_int_trie( HASH_TABLE *table, const char *key, int *val )
382{
383 __n_assert( table, return FALSE );
384 __n_assert( key, return FALSE );
385 if( strlen( key ) == 0 )
386 return FALSE ;
387
388 HASH_NODE *node = _ht_get_node_trie( table, key );
389
390 if( !node || !node -> is_leaf )
391 return FALSE ;
392
393 if( node -> type != HASH_INT )
394 {
395 n_log( LOG_ERR, "Can't get key[\"%s\"] of type HASH_INT, key is type %s", key, ht_node_type( node ) );
396 return FALSE ;
397 }
398
399 (*val) = node -> data . ival ;
400
401 return TRUE ;
402} /* _ht_get_int_trie() */
403
404
405
413int _ht_get_double_trie( HASH_TABLE *table, const char *key, double *val )
414{
415 __n_assert( table, return FALSE );
416 __n_assert( key, return FALSE );
417 if( strlen( key ) == 0 )
418 return FALSE ;
419
420 HASH_NODE *node = _ht_get_node_trie( table, key );
421
422 if( !node || !node -> is_leaf )
423 return FALSE ;
424
425 if( node -> type != HASH_DOUBLE )
426 {
427 n_log( LOG_ERR, "Can't get key[\"%s\"] of type HASH_INT, key is type %s", key, ht_node_type( node ) );
428 return FALSE ;
429 }
430
431 (*val) = node -> data . fval ;
432
433 return TRUE ;
434} /* _ht_get_double_trie() */
435
436
437
445int _ht_get_string_trie( HASH_TABLE *table, const char *key, char **val )
446{
447 __n_assert( table, return FALSE );
448 __n_assert( key, return FALSE );
449 if( strlen( key ) == 0 )
450 return FALSE ;
451
452 HASH_NODE *node = _ht_get_node_trie( table, key );
453
454 if( !node || !node -> is_leaf )
455 return FALSE ;
456
457 if( node -> type != HASH_STRING )
458 {
459 n_log( LOG_ERR, "Can't get key[\"%s\"] of type HASH_INT, key is type %s", key, ht_node_type( node ) );
460 return FALSE ;
461 }
462
463 (*val) = node -> data . string ;
464
465 return TRUE ;
466} /* _ht_get_string_trie() */
467
468
476int _ht_get_ptr_trie( HASH_TABLE *table, const char *key, void **val )
477{
478 __n_assert( table, return FALSE );
479 __n_assert( key, return FALSE );
480 if( strlen( key ) == 0 )
481 return FALSE ;
482
483 HASH_NODE *node = _ht_get_node_trie( table, key );
484
485 if( !node || !node -> is_leaf )
486 return FALSE ;
487
488 if( node -> type != HASH_PTR )
489 {
490 n_log( LOG_ERR, "Can't get key[\"%s\"] of type HASH_PTR , key is type %s", key, ht_node_type( node ) );
491 return FALSE ;
492 }
493
494 (*val) = node -> data . ptr ;
495
496 return TRUE ;
497} /* _ht_get_ptr_trie() */
498
499
500
509int _ht_check_trie_divergence( HASH_TABLE *table, const char *key )
510{
511 __n_assert( table, return FALSE );
512 __n_assert( key, return FALSE );
513
514
515 HASH_NODE* node = table -> root;
516
517 int last_index = 0;
518 for( size_t it = 0 ; key[ it ] != '\0' ; it ++ )
519 {
520 size_t index = (size_t)key[ it ] - table -> alphabet_offset ;
521 if( index >= table -> alphabet_length )
522 {
523 n_log( LOG_ERR, "Invalid value %d for charater at position %d of %s, set to 0", index, it, key );
524 index = 0 ;
525 }
526 if( node -> children[ index ] )
527 {
528 /* child check */
529 for( size_t it2 = 0 ; it2 < table -> alphabet_length ; it2++ )
530 {
531 if( it2 != (unsigned)index && node -> children[ it2 ] )
532 {
533 /* child found, update branch index */
534 last_index = it + 1;
535 break;
536 }
537 }
538 /* Go to the next child in the sequence */
539 node = node->children[ index ];
540 }
541 }
542 return last_index;
543} /* _ht_check_trie_divergence(...) */
544
545
546
555char* _ht_find_longest_prefix_trie( HASH_TABLE *table, const char *key )
556{
557 __n_assert( table, return NULL );
558 __n_assert( key, return NULL );
559
560 int len = strlen( key );
561
562 /* start with full key and backtrack to search for divergences */
563 char *longest_prefix = NULL ;
564 Malloc( longest_prefix, char, len + 1 );
565 memcpy( longest_prefix, key, len );
566
567 /* check branching from the root */
568 int branch_index = _ht_check_trie_divergence( table, longest_prefix ) - 1 ;
569 if(branch_index >= 0 )
570 {
571 /* there is branching, update the position to the longest match and update the longest prefix by the branch index length */
572 longest_prefix[ branch_index ] = '\0';
573 Realloc( longest_prefix, char, (branch_index + 1) );
574 if( !longest_prefix )
575 {
576 n_log( LOG_ERR, "reallocation error, stopping find longest prefix" );
577 return NULL ;
578 }
579 __n_assert( longest_prefix, return NULL );
580 }
581 return longest_prefix;
582} /* _ht_find_longest_prefix_trie(...) */
583
584
585
594int _ht_is_leaf_node_trie( HASH_TABLE *table, const char *key )
595{
596 __n_assert( table, return -1 );
597
598 /* checks if the prefix match of key and root is a leaf node */
599 HASH_NODE* node = table -> root;
600 for( size_t it = 0 ; key[ it ] ; it++ )
601 {
602 size_t index = (size_t)key[ it ] - table -> alphabet_offset ;
603 if( index >= table -> alphabet_length )
604 {
605 n_log( LOG_ERR, "Invalid value %d for charater at position %d of %s, set to 0", index, it, key );
606 index = 0 ;
607 }
608 if( node -> children[ index ] )
609 {
610 node = node -> children[ index ];
611 }
612 }
613 return node -> is_leaf ;
614} /* _ht_is_leaf_node_trie(...) */
615
616
617
624void _ht_node_destroy( void *node )
625{
626 HASH_NODE *node_ptr = (HASH_NODE *)node ;
627 __n_assert( node_ptr, return );
628 if( node_ptr -> type == HASH_STRING )
629 {
630 Free( node_ptr -> data . string );
631 }
632 if( node_ptr -> type == HASH_PTR )
633 {
634 if( node_ptr -> destroy_func && node_ptr -> data . ptr )
635 {
636 node_ptr -> destroy_func( node_ptr -> data . ptr );
637 }
638 /* No free by default. must be passed as a destroy_func
639 else
640 {
641 Free( node_ptr -> data . ptr );
642 }
643 */
644 }
645 FreeNoLog( node_ptr -> key );
646 if( node_ptr -> alphabet_length > 0 )
647 {
648 for( size_t it = 0 ; it < node_ptr -> alphabet_length ; it ++ )
649 {
650 if( node_ptr -> children[ it ] )
651 {
652 _ht_node_destroy( node_ptr -> children[ it ] );
653 }
654 }
655 Free( node_ptr -> children );
656 }
657 Free( node_ptr )
658} /* _ht_node_destroy */
659
660
661
670int _ht_remove_trie( HASH_TABLE *table, const char *key )
671{
672 __n_assert( table, return FALSE );
673 __n_assert( table -> root, return FALSE );
674 __n_assert( key, return FALSE );
675
676 /* stop if matching node not a leaf node */
677 if( !_ht_is_leaf_node_trie( table, key ) )
678 {
679 return FALSE ;
680 }
681
682 HASH_NODE *node = table -> root ;
683 /* find the longest prefix string that is not the current key */
684 char *longest_prefix = _ht_find_longest_prefix_trie( table, key );
685 if( longest_prefix && longest_prefix[ 0 ] == '\0' )
686 {
687 Free( longest_prefix );
688 return FALSE ;
689 }
690 /* keep track of position in the tree */
691 size_t it = 0 ;
692 for( it = 0 ; longest_prefix[ it ] != '\0'; it++ )
693 {
694 size_t index = (size_t)longest_prefix[ it ] - table -> alphabet_offset ;
695 if( index >= table -> alphabet_length )
696 {
697 n_log( LOG_ERR, "Invalid value %d for charater at position %d of %s, set to 0", index, it, key );
698 index = 0 ;
699 }
700 if( node -> children[ index ] != NULL )
701 {
702 /* common prefix, keep moving */
703 node = node -> children[ index ];
704 }
705 else
706 {
707 /* not found */
708 Free( longest_prefix );
709 return FALSE ;
710 }
711 }
712 /* deepest common node between the two strings */
713 /* deleting the sequence corresponding to key */
714 for( ; key[ it ] != '\0' ; it++ )
715 {
716 size_t index = (size_t)key[ it ] - table -> alphabet_offset ;
717 if( index >= table -> alphabet_length )
718 {
719 n_log( LOG_ERR, "Invalid value %d for charater at position %d of %s, set to 0", index, it, key );
720 index = 0 ;
721 }
722 if( node -> children[ index] )
723 {
724 /* delete the remaining sequence */
725 HASH_NODE* node_to_kill = node -> children[ index ];
726 node -> children[ index ] = NULL;
727 _ht_node_destroy( node_to_kill );
728 }
729 }
730 Free( longest_prefix );
731
732 table -> nb_keys -- ;
733
734 return TRUE ;
735} /* _ht_remove_trie(...) */
736
737
738
746int _empty_ht_trie( HASH_TABLE *table )
747{
748 __n_assert( table, return FALSE );
749
750 _ht_node_destroy( table -> root );
751
752 table -> root = _ht_new_node_trie( table, '\0' );
753
754 table -> nb_keys = 0 ;
755 return TRUE ;
756} /* _empty_ht_trie */
757
758
759
767int _destroy_ht_trie( HASH_TABLE **table )
768{
769 __n_assert( table&&(*table), n_log( LOG_ERR, "Can't destroy table: already NULL" ); return FALSE );
770
771 _ht_node_destroy( (*table) -> root );
772
773 Free( (*table ) );
774
775 return TRUE ;
776} /* _destroy_ht_trie */
777
778
779
787void _ht_print_trie_helper( HASH_TABLE *table, HASH_NODE *node )
788{
789 if( !node )
790 return ;
791
792 if( node -> is_leaf )
793 {
794 printf( "key: %s, val: ", node -> key );
795 switch( node -> type )
796 {
797 case HASH_INT:
798 printf( "int: %d", node -> data . ival );
799 break;
800 case HASH_DOUBLE:
801 printf( "double: %f", node -> data . fval );
802 break;
803 case HASH_PTR:
804 printf( "ptr: %p", node -> data . ptr );
805 break;
806 case HASH_STRING:
807 printf( "%s", node -> data . string );
808 break;
809 default:
810 printf( "unknwow type %d", node -> type );
811 break;
812 }
813 printf( "\n" );
814 }
815 for( size_t it = 0 ; it < table -> alphabet_length ; it++ )
816 {
817 _ht_print_trie_helper( table, node -> children[ it ] );
818 }
819} /* _ht_print_trie_helper(...) */
820
821
822
827void _ht_print_trie( HASH_TABLE *table )
828{
829 __n_assert( table, return );
830 __n_assert( table -> root, return );
831
832 HASH_NODE *node = table -> root ;
833
834 _ht_print_trie_helper( table, node );
835
836 return ;
837} /* _ht_print_trie(...) */
838
839
848void _ht_search_trie_helper( LIST *results, HASH_NODE *node, int (*node_is_matching)( HASH_NODE *node ) )
849{
850 if( !node )
851 return ;
852
853 if( node -> is_leaf )
854 {
855 if( node_is_matching( node ) == TRUE )
856 {
857 list_push( results, strdup( node -> key ), &free );
858 }
859 }
860 for( size_t it = 0 ; it < node -> alphabet_length ; it++ )
861 {
862 _ht_search_trie_helper( results, node -> children[ it ], node_is_matching );
863 }
864}
865
866
875LIST *_ht_search_trie( HASH_TABLE *table, int (*node_is_matching)( HASH_NODE *node ) )
876{
877 __n_assert( table, return NULL );
878
879 LIST *results = new_generic_list( 0 );
880 __n_assert( results, return NULL );
881
882 _ht_search_trie_helper( results, table -> root, node_is_matching );
883
884 if( results -> nb_items < 1 )
885 list_destroy( &results );
886
887 return results ;
888} /* _ht_search_trie(...) */
889
890
891
900int _ht_depth_first_search( HASH_NODE *node, LIST *results )
901{
902 __n_assert( results, return FALSE );
903
904 if( !node )
905 return FALSE ;
906
907 for( size_t it = 0; it < node -> alphabet_length ; it++ )
908 {
909 _ht_depth_first_search( node -> children[ it ], results );
910 }
911 if( node -> is_leaf )
912 {
913 if( results -> nb_items < results -> nb_max_items )
914 {
915 return list_push( results, strdup( node -> key ), &free );
916 }
917 return TRUE ;
918 }
919 return TRUE ;
920} /* _ht_depth_first_search(...) */
921
922
923
924/************ CLASSIC HASH TABLE ************/
926#define ROTL64(x, r) (((x) << (r)) | ((x) >> (64 - (r))))
928#define ROTL32(x, r) (((x) << (r)) | ((x) >> (32 - (r))))
930#define BIG_CONSTANT(x) (x##LLU)
931
932/* NO-OP for little-endian platforms */
933#if defined(__BYTE_ORDER__) && defined(__ORDER_LITTLE_ENDIAN__)
934# if __BYTE_ORDER__ == __ORDER_LITTLE_ENDIAN__
935# define BYTESWAP32(x) (x)
936# define BYTESWAP64(x) (x)
937# endif
938/* if __BYTE_ORDER__ is not predefined (like FreeBSD), use arch */
939#elif defined(__i386) || defined(__x86_64) \
940 || defined(__alpha) || defined(__vax)
941
942# define BYTESWAP32(x) (x)
943# define BYTESWAP64(x) (x)
944/* use __builtin_bswap32 if available */
945#elif defined(__GNUC__) || defined(__clang__)
946# ifdef __has_builtin
947# if __has_builtin(__builtin_bswap32)
948# define BYTESWAP32(x) __builtin_bswap32(x)
949# endif // __has_builtin(__builtin_bswap32)
950# if __has_builtin(__builtin_bswap64)
951# define BYTESWAP64(x) __builtin_bswap64(x)
952# endif // __has_builtin(__builtin_bswap64)
953# endif // __has_builtin
954#endif // defined(__GNUC__) || defined(__clang__)
955/* last resort (big-endian w/o __builtin_bswap) */
956#ifndef BYTESWAP32
958# define BYTESWAP32(x) ((((x)&0xFF)<<24) \
959 |(((x)>>24)&0xFF) \
960 |(((x)&0x0000FF00)<<8) \
961 |(((x)&0x00FF0000)>>8) )
962#endif
963#ifndef BYTESWAP64
965# define BYTESWAP64(x) \
966 (((uint64_t)(x) << 56) | \
967 (((uint64_t)(x) << 40) & 0X00FF000000000000ULL) | \
968 (((uint64_t)(x) << 24) & 0X0000FF0000000000ULL) | \
969 (((uint64_t)(x) << 8) & 0X000000FF00000000ULL) | \
970 (((uint64_t)(x) >> 8) & 0X00000000FF000000ULL) | \
971 (((uint64_t)(x) >> 24) & 0X0000000000FF0000ULL) | \
972 (((uint64_t)(x) >> 40) & 0X000000000000FF00ULL) | \
973 ((uint64_t)(x) >> 56))
974#endif
975
976
977
984FORCE_INLINE uint32_t getblock32(const uint32_t *p, const size_t i) {
985 return BYTESWAP32(p[i]);
986}
987
994FORCE_INLINE uint64_t getblock64(const uint64_t * p, const size_t i) {
995 return BYTESWAP64(p[i]);
996}
997
998
999
1005FORCE_INLINE uint32_t fmix32 ( uint32_t h )
1006{
1007 h ^= h >> 16;
1008 h *= 0x85ebca6b;
1009 h ^= h >> 13;
1010 h *= 0xc2b2ae35;
1011 h ^= h >> 16;
1012
1013 return h;
1014} /* fmix32(...) */
1015
1016
1017
1023FORCE_INLINE uint64_t fmix64 ( uint64_t k )
1024{
1025 k ^= k >> 33;
1026 k *= BIG_CONSTANT(0xff51afd7ed558ccd);
1027 k ^= k >> 33;
1028 k *= BIG_CONSTANT(0xc4ceb9fe1a85ec53);
1029 k ^= k >> 33;
1030
1031 return k;
1032}
1033
1034
1035
1048void MurmurHash3_x86_32( const void * key, int len, uint32_t seed, void * out )
1049{
1050 const uint8_t * data = (const uint8_t*)key;
1051 const int nblocks = len / 4;
1052
1053 uint32_t h1 = seed;
1054
1055 uint32_t c1 = 0xcc9e2d51;
1056 uint32_t c2 = 0x1b873593;
1057
1058 /* body */
1059 const uint32_t * blocks = (const uint32_t *)(data + nblocks*4);
1060
1061 int i = 0 ;
1062 for(i = -nblocks; i; i++)
1063 {
1064 uint32_t k1 = getblock32(blocks,i);
1065
1066 k1 *= c1;
1067 k1 = ROTL32(k1,15);
1068 k1 *= c2;
1069
1070 h1 ^= k1;
1071 h1 = ROTL32(h1,13);
1072 h1 = h1*5+0xe6546b64;
1073 }
1074
1075 /* tail */
1076 const uint8_t * tail = (const uint8_t*)(data + nblocks*4);
1077
1078 uint32_t k1 = 0;
1079
1080 switch(len & 3)
1081 {
1082 case 3:
1083 k1 ^= tail[2] << 16;
1084 FALL_THROUGH ;
1085 case 2:
1086 k1 ^= tail[1] << 8;
1087 FALL_THROUGH ;
1088 case 1:
1089 k1 ^= tail[0];
1090 k1 *= c1;
1091 k1 = ROTL32(k1,15);
1092 k1 *= c2;
1093 h1 ^= k1;
1094 default:
1095 break ;
1096 };
1097
1098 /* finalization */
1099 h1 ^= len;
1100 h1 = fmix32(h1);
1101 *(uint32_t*)out = h1;
1102} /* MurmurHash3_x86_32(...) */
1103
1104
1105
1118void MurmurHash3_x86_128( const void * key, const int len, uint32_t seed, void * out )
1119{
1120 const uint8_t * data = (const uint8_t*)key;
1121 const int nblocks = len / 16;
1122
1123 uint32_t h1 = seed;
1124 uint32_t h2 = seed;
1125 uint32_t h3 = seed;
1126 uint32_t h4 = seed;
1127
1128 uint32_t c1 = 0x239b961b;
1129 uint32_t c2 = 0xab0e9789;
1130 uint32_t c3 = 0x38b34ae5;
1131 uint32_t c4 = 0xa1e38b93;
1132
1133 /* body */
1134 const uint32_t * blocks = (const uint32_t *)(data + nblocks*16);
1135
1136 int i = 0 ;
1137 for( i = -nblocks ; i; i++)
1138 {
1139 uint32_t k1 = getblock32(blocks,i*4+0);
1140 uint32_t k2 = getblock32(blocks,i*4+1);
1141 uint32_t k3 = getblock32(blocks,i*4+2);
1142 uint32_t k4 = getblock32(blocks,i*4+3);
1143
1144 k1 *= c1;
1145 k1 = ROTL32(k1,15);
1146 k1 *= c2;
1147 h1 ^= k1;
1148 h1 = ROTL32(h1,19);
1149 h1 += h2;
1150 h1 = h1*5+0x561ccd1b;
1151
1152 k2 *= c2;
1153 k2 = ROTL32(k2,16);
1154 k2 *= c3;
1155 h2 ^= k2;
1156 h2 = ROTL32(h2,17);
1157 h2 += h3;
1158 h2 = h2*5+0x0bcaa747;
1159
1160 k3 *= c3;
1161 k3 = ROTL32(k3,17);
1162 k3 *= c4;
1163 h3 ^= k3;
1164 h3 = ROTL32(h3,15);
1165 h3 += h4;
1166 h3 = h3*5+0x96cd1c35;
1167
1168 k4 *= c4;
1169 k4 = ROTL32(k4,18);
1170 k4 *= c1;
1171 h4 ^= k4;
1172 h4 = ROTL32(h4,13);
1173 h4 += h1;
1174 h4 = h4*5+0x32ac3b17;
1175 }
1176
1177 /* tail */
1178 const uint8_t * tail = (const uint8_t*)(data + nblocks*16);
1179
1180 uint32_t k1 = 0;
1181 uint32_t k2 = 0;
1182 uint32_t k3 = 0;
1183 uint32_t k4 = 0;
1184
1185 switch(len & 15)
1186 {
1187 case 15:
1188 k4 ^= tail[14] << 16;
1189 FALL_THROUGH ;
1190 case 14:
1191 k4 ^= tail[13] << 8;
1192 FALL_THROUGH ;
1193 case 13:
1194 k4 ^= tail[12] << 0;
1195 k4 *= c4;
1196 k4 = ROTL32(k4,18);
1197 k4 *= c1;
1198 h4 ^= k4;
1199 FALL_THROUGH ;
1200 case 12:
1201 k3 ^= tail[11] << 24;
1202 FALL_THROUGH ;
1203 case 11:
1204 k3 ^= tail[10] << 16;
1205 FALL_THROUGH ;
1206 case 10:
1207 k3 ^= tail[ 9] << 8;
1208 FALL_THROUGH ;
1209 case 9:
1210 k3 ^= tail[ 8] << 0;
1211 k3 *= c3;
1212 k3 = ROTL32(k3,17);
1213 k3 *= c4;
1214 h3 ^= k3;
1215 FALL_THROUGH ;
1216 case 8:
1217 k2 ^= tail[ 7] << 24;
1218 FALL_THROUGH ;
1219 case 7:
1220 k2 ^= tail[ 6] << 16;
1221 FALL_THROUGH ;
1222 case 6:
1223 k2 ^= tail[ 5] << 8;
1224 FALL_THROUGH ;
1225 case 5:
1226 k2 ^= tail[ 4] << 0;
1227 k2 *= c2;
1228 k2 = ROTL32(k2,16);
1229 k2 *= c3;
1230 h2 ^= k2;
1231 FALL_THROUGH ;
1232 case 4:
1233 k1 ^= tail[ 3] << 24;
1234 FALL_THROUGH ;
1235 case 3:
1236 k1 ^= tail[ 2] << 16;
1237 FALL_THROUGH ;
1238 case 2:
1239 k1 ^= tail[ 1] << 8;
1240 FALL_THROUGH ;
1241 case 1:
1242 k1 ^= tail[ 0] << 0;
1243 k1 *= c1;
1244 k1 = ROTL32(k1,15);
1245 k1 *= c2;
1246 h1 ^= k1;
1247 default:
1248 break ;
1249 };
1250 /* finalization */
1251 h1 ^= len;
1252 h2 ^= len;
1253 h3 ^= len;
1254 h4 ^= len;
1255
1256 h1 += h2;
1257 h1 += h3;
1258 h1 += h4;
1259 h2 += h1;
1260 h3 += h1;
1261 h4 += h1;
1262
1263 h1 = fmix32(h1);
1264 h2 = fmix32(h2);
1265 h3 = fmix32(h3);
1266 h4 = fmix32(h4);
1267
1268 h1 += h2;
1269 h1 += h3;
1270 h1 += h4;
1271 h2 += h1;
1272 h3 += h1;
1273 h4 += h1;
1274
1275 ((uint32_t*)out)[0] = h1;
1276 ((uint32_t*)out)[1] = h2;
1277 ((uint32_t*)out)[2] = h3;
1278 ((uint32_t*)out)[3] = h4;
1279} /* MurmurHash3_x86_128(...) */
1280
1281
1282
1295void MurmurHash3_x64_128( const void * key, const size_t len, const uint64_t seed, void * out )
1296{
1297 const uint8_t * data = (const uint8_t*)key;
1298 const size_t nblocks = len / 16;
1299
1300 uint64_t h1 = seed;
1301 uint64_t h2 = seed;
1302
1303 const uint64_t c1 = BIG_CONSTANT(0x87c37b91114253d5);
1304 const uint64_t c2 = BIG_CONSTANT(0x4cf5ad432745937f);
1305
1306 const uint64_t * blocks = (const uint64_t *)(data);
1307 const uint8_t * tail = (const uint8_t*)(data + nblocks*16);
1308 uint64_t k1 = 0;
1309 uint64_t k2 = 0;
1310
1311 /* body */
1312 for(size_t i = 0; i < nblocks; i++)
1313 {
1314 k1 = getblock64(blocks,i*2+0);
1315 k2 = getblock64(blocks,i*2+1);
1316
1317 k1 *= c1;
1318 k1 = ROTL64(k1,31);
1319 k1 *= c2;
1320 h1 ^= k1;
1321
1322 h1 = ROTL64(h1,27);
1323 h1 += h2;
1324 h1 = h1*5+0x52dce729;
1325
1326 k2 *= c2;
1327 k2 = ROTL64(k2,33);
1328 k2 *= c1;
1329 h2 ^= k2;
1330
1331 h2 = ROTL64(h2,31);
1332 h2 += h1;
1333 h2 = h2*5+0x38495ab5;
1334 }
1335
1336 /* tail */
1337 switch(len & 15)
1338 {
1339 case 15:
1340 k2 ^= ((uint64_t)tail[14]) << 48;
1341 FALL_THROUGH ;
1342 case 14:
1343 k2 ^= ((uint64_t)tail[13]) << 40;
1344 FALL_THROUGH ;
1345 case 13:
1346 k2 ^= ((uint64_t)tail[12]) << 32;
1347 FALL_THROUGH ;
1348 case 12:
1349 k2 ^= ((uint64_t)tail[11]) << 24;
1350 FALL_THROUGH ;
1351 case 11:
1352 k2 ^= ((uint64_t)tail[10]) << 16;
1353 FALL_THROUGH ;
1354 case 10:
1355 k2 ^= ((uint64_t)tail[ 9]) << 8;
1356 FALL_THROUGH ;
1357 case 9:
1358 k2 ^= ((uint64_t)tail[ 8]) << 0;
1359 k2 *= c2;
1360 k2 = ROTL64(k2,33);
1361 k2 *= c1;
1362 h2 ^= k2;
1363 FALL_THROUGH ;
1364
1365 case 8:
1366 k1 ^= ((uint64_t)tail[ 7]) << 56;
1367 FALL_THROUGH ;
1368 case 7:
1369 k1 ^= ((uint64_t)tail[ 6]) << 48;
1370 FALL_THROUGH ;
1371 case 6:
1372 k1 ^= ((uint64_t)tail[ 5]) << 40;
1373 FALL_THROUGH ;
1374 case 5:
1375 k1 ^= ((uint64_t)tail[ 4]) << 32;
1376 FALL_THROUGH ;
1377 case 4:
1378 k1 ^= ((uint64_t)tail[ 3]) << 24;
1379 FALL_THROUGH ;
1380 case 3:
1381 k1 ^= ((uint64_t)tail[ 2]) << 16;
1382 FALL_THROUGH ;
1383 case 2:
1384 k1 ^= ((uint64_t)tail[ 1]) << 8;
1385 FALL_THROUGH ;
1386 case 1:
1387 k1 ^= ((uint64_t)tail[ 0]) << 0;
1388 k1 *= c1;
1389 k1 = ROTL64(k1,31);
1390 k1 *= c2;
1391 h1 ^= k1;
1392 FALL_THROUGH ;
1393 default:
1394 break;
1395 };
1396
1397 /* finalization */
1398
1399 h1 ^= len;
1400 h2 ^= len;
1401
1402 h1 += h2;
1403 h2 += h1;
1404
1405 h1 = fmix64(h1);
1406 h2 = fmix64(h2);
1407
1408 h1 += h2;
1409 h2 += h1;
1410
1411 ((uint64_t*)out)[0] = h2;
1412 ((uint64_t*)out)[1] = h1;
1413
1414} /* MurmurHash3_x64_128()*/
1415
1416
1417
1423char *ht_node_type( HASH_NODE *node )
1424{
1425 static char *HASH_TYPE_STR[ 5 ] = { "HASH_INT", "HASH_DOUBLE", "HASH_STRING", "HASH_PTR", "HASH_UNKNOWN" };
1426
1427 __n_assert( node, return NULL );
1428
1429 if( node -> type >= 0 && node -> type < HASH_UNKNOWN )
1430 return HASH_TYPE_STR[ node -> type ];
1431
1432 return NULL ;
1433} /* ht_node_type(...) */
1434
1435
1442HASH_NODE *_ht_get_node( HASH_TABLE *table, const char *key )
1443{
1444 HASH_VALUE hash_value[ 2 ] = { 0 , 0 };
1445 size_t index = 0;
1446
1447 HASH_NODE *node_ptr = NULL ;
1448
1449 __n_assert( table, return NULL );
1450 __n_assert( key, return NULL );
1451
1452 if( key[ 0 ] == '\0' )
1453 return NULL ;
1454
1455 MurmurHash( key, strlen( key ), table -> seed, &hash_value );
1456 index= (hash_value[ 0 ])%(table->size);
1457
1458 if( ! table -> hash_table[ index ] -> start )
1459 return NULL ;
1460
1461 list_foreach( list_node, table -> hash_table[ index ] )
1462 {
1463 node_ptr = (HASH_NODE *)list_node -> ptr ;
1464 if( !strcmp( key, node_ptr -> key ) )
1465 {
1466 return node_ptr ;
1467 }
1468 }
1469 return NULL ;
1470} /* _ht_get_node() */
1471
1472
1473
1480HASH_NODE *_ht_new_node( HASH_TABLE *table, const char *key )
1481{
1482 __n_assert( table, return NULL );
1483 __n_assert( key, return NULL );
1484
1485 HASH_NODE *new_hash_node = NULL ;
1486
1487 HASH_VALUE hash_value[ 2 ] = { 0 , 0 };
1488
1489 if( strlen( key ) == 0 )
1490 return NULL ;
1491
1492 MurmurHash( key, strlen( key ), table -> seed, &hash_value );
1493
1494 Malloc( new_hash_node, HASH_NODE, 1 );
1495 __n_assert( new_hash_node, n_log( LOG_ERR, "Could not allocate new_hash_node" ); return NULL );
1496 new_hash_node -> key = strdup( key );
1497 new_hash_node -> key_id = '\0' ;
1498 __n_assert( new_hash_node -> key, n_log( LOG_ERR, "Could not allocate new_hash_node->key" ); Free( new_hash_node ); return NULL );
1499 new_hash_node -> hash_value = hash_value[ 0 ] ;
1500 new_hash_node -> data. ptr = NULL ;
1501 new_hash_node -> destroy_func = NULL ;
1502 new_hash_node -> children = NULL ;
1503 new_hash_node -> is_leaf = 0 ;
1504 new_hash_node -> need_rehash = 0 ;
1505 new_hash_node -> alphabet_length = 0 ;
1506
1507 return new_hash_node ;
1508} /* _ht_new_node */
1509
1510
1511
1519HASH_NODE *_ht_new_int_node( HASH_TABLE *table, const char *key, int value )
1520{
1521 __n_assert( table, return NULL );
1522 __n_assert( key, return NULL );
1523
1524 HASH_NODE *new_hash_node = NULL ;
1525 new_hash_node = _ht_new_node( table, key );
1526 new_hash_node -> data . ival = value ;
1527 new_hash_node -> type = HASH_INT ;
1528 return new_hash_node ;
1529} /* _ht_new_int_node */
1530
1531
1532
1540HASH_NODE *_ht_new_double_node( HASH_TABLE *table, const char *key, double value )
1541{
1542 __n_assert( table, return NULL );
1543 __n_assert( key, return NULL );
1544
1545 HASH_NODE *new_hash_node = NULL ;
1546 new_hash_node = _ht_new_node( table, key );
1547 new_hash_node -> data . fval = value ;
1548 new_hash_node -> type = HASH_DOUBLE ;
1549 return new_hash_node ;
1550} /* _ht_new_double_node */
1551
1552
1553
1561HASH_NODE *_ht_new_string_node( HASH_TABLE *table, const char *key, char *value )
1562{
1563 __n_assert( table, return NULL );
1564 __n_assert( key, return NULL );
1565
1566 HASH_NODE *new_hash_node = NULL ;
1567 new_hash_node = _ht_new_node( table, key );
1568 if( value )
1569 new_hash_node -> data . string = strdup( value );
1570 else
1571 new_hash_node -> data . string = NULL ;
1572 new_hash_node -> type = HASH_STRING ;
1573 return new_hash_node ;
1574}
1575
1576
1577
1585HASH_NODE *_ht_new_string_ptr_node( HASH_TABLE *table, const char *key, char *value )
1586{
1587 __n_assert( table, return NULL );
1588 __n_assert( key, return NULL );
1589
1590 HASH_NODE *new_hash_node = NULL ;
1591 new_hash_node = _ht_new_node( table, key );
1592 new_hash_node -> data . string = value ;
1593 new_hash_node -> type = HASH_STRING ;
1594 return new_hash_node ;
1595}
1596
1597
1598
1607HASH_NODE *_ht_new_ptr_node( HASH_TABLE *table, const char *key, void *value, void (*destructor)(void *ptr ) )
1608{
1609 __n_assert( table, return NULL );
1610 __n_assert( key, return NULL );
1611
1612 HASH_NODE *new_hash_node = NULL ;
1613 new_hash_node = _ht_new_node( table, key );
1614 new_hash_node -> data . ptr = value ;
1615 new_hash_node -> destroy_func = destructor ;
1616 new_hash_node -> type = HASH_PTR ;
1617 return new_hash_node ;
1618}
1619
1620
1621
1631int _ht_put_int( HASH_TABLE *table, const char *key, int value )
1632{
1633 HASH_NODE *node_ptr = NULL ;
1634
1635 __n_assert( table, return FALSE );
1636 __n_assert( key, return FALSE );
1637
1638 if( ( node_ptr = _ht_get_node( table, key ) ) )
1639 {
1640 if( node_ptr -> type == HASH_INT )
1641 {
1642 node_ptr -> data . ival = value ;
1643 return TRUE ;
1644 }
1645 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 ) );
1646 return FALSE ; /* key registered with another data type */
1647 }
1648
1649 node_ptr = _ht_new_int_node( table, key, value );
1650
1651 size_t index = ( node_ptr -> hash_value )%( table -> size );
1652 int retcode = list_push( table -> hash_table[ index ], node_ptr, &_ht_node_destroy );
1653 if( retcode == TRUE )
1654 {
1655 table -> nb_keys ++ ;
1656 }
1657 return retcode ;
1658} /*_ht_put_int() */
1659
1660
1661
1669int _ht_put_double( HASH_TABLE *table, const char *key, double value )
1670{
1671 HASH_NODE *node_ptr = NULL ;
1672
1673 __n_assert( table, return FALSE );
1674 __n_assert( key, return FALSE );
1675
1676 if( ( node_ptr = _ht_get_node( table, key ) ) )
1677 {
1678 if( node_ptr -> type == HASH_DOUBLE )
1679 {
1680 node_ptr -> data . fval = value ;
1681 return TRUE ;
1682 }
1683 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 ) );
1684 return FALSE ; /* key registered with another data type */
1685 }
1686
1687 node_ptr = _ht_new_double_node( table, key, value );
1688
1689 HASH_VALUE index = ( node_ptr -> hash_value )%( table -> size );
1690 int retcode = list_push( table -> hash_table[ index ], node_ptr, &_ht_node_destroy );
1691 if( retcode == TRUE )
1692 {
1693 table -> nb_keys ++ ;
1694 }
1695 return retcode ;
1696} /*_ht_put_double()*/
1697
1698
1699
1708int _ht_put_ptr( HASH_TABLE *table, const char *key, void *ptr, void (*destructor)(void *ptr ) )
1709{
1710 HASH_NODE *node_ptr = NULL ;
1711
1712 __n_assert( table, return FALSE );
1713 __n_assert( key, return FALSE );
1714
1715 if( ( node_ptr = _ht_get_node( table, key ) ) )
1716 {
1717 /* let's check the key isn't already assigned with another data type */
1718 if( node_ptr -> type == HASH_PTR )
1719 {
1720 if( node_ptr -> destroy_func )
1721 {
1722 node_ptr -> destroy_func( node_ptr -> data . ptr );
1723 node_ptr -> data . ptr = ptr ;
1724 node_ptr -> destroy_func = destructor ;
1725 }
1726 return TRUE ;
1727 }
1728 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 ) );
1729 return FALSE ; /* key registered with another data type */
1730 }
1731
1732 node_ptr = _ht_new_ptr_node( table, key, ptr, destructor );
1733
1734 HASH_VALUE index = ( node_ptr -> hash_value )%( table -> size );
1735 int retcode = list_push( table -> hash_table[ index ], node_ptr, &_ht_node_destroy );
1736 if( retcode == TRUE )
1737 {
1738 table -> nb_keys ++ ;
1739 }
1740 return retcode ;
1741}/* _ht_put_ptr() */
1742
1743
1744
1752int _ht_put_string( HASH_TABLE *table, const char *key, char *string )
1753{
1754 HASH_NODE *node_ptr = NULL ;
1755
1756 __n_assert( table, return FALSE );
1757 __n_assert( key, return FALSE );
1758
1759 if( ( node_ptr = _ht_get_node( table, key ) ) )
1760 {
1761 /* let's check the key isn't already assigned with another data type */
1762 if( node_ptr -> type == HASH_STRING )
1763 {
1764 Free( node_ptr -> data . string );
1765 node_ptr -> data . string = strdup( string );
1766 return TRUE ;
1767 }
1768 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 ) );
1769 return FALSE ; /* key registered with another data type */
1770 }
1771
1772 node_ptr = _ht_new_string_node( table, key, string );
1773
1774 HASH_VALUE index = ( node_ptr -> hash_value )%( table -> size );
1775 int retcode = list_push( table -> hash_table[ index ], node_ptr, &_ht_node_destroy );
1776 if( retcode == TRUE )
1777 {
1778 table -> nb_keys ++ ;
1779 }
1780 return retcode ;
1781} /*_ht_put_string */
1782
1783
1784
1792int _ht_put_string_ptr( HASH_TABLE *table, const char *key, char *string )
1793{
1794 HASH_NODE *node_ptr = NULL ;
1795
1796 __n_assert( table, return FALSE );
1797 __n_assert( key, return FALSE );
1798
1799 if( ( node_ptr = _ht_get_node( table, key ) ) )
1800 {
1801 /* let's check the key isn't already assigned with another data type */
1802 if( node_ptr -> type == HASH_STRING )
1803 {
1804 Free( node_ptr -> data . string );
1805 node_ptr -> data . string = string ;
1806 return TRUE ;
1807 }
1808 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 ) );
1809 return FALSE ; /* key registered with another data type */
1810 }
1811
1812 node_ptr = _ht_new_string_node( table, key, string );
1813
1814 HASH_VALUE index = ( node_ptr -> hash_value )%( table -> size );
1815 int retcode = list_push( table -> hash_table[ index ], node_ptr, &_ht_node_destroy );
1816 if( retcode == TRUE )
1817 {
1818 table -> nb_keys ++ ;
1819 }
1820 return retcode ;
1821} /*_ht_put_string_ptr */
1822
1823
1824
1825
1826
1834int _ht_get_int( HASH_TABLE *table, const char *key, int *val )
1835{
1836 __n_assert( table, return FALSE );
1837 __n_assert( key, return FALSE );
1838 if( strlen( key ) == 0 )
1839 return FALSE ;
1840
1841 HASH_NODE *node = _ht_get_node( table, key );
1842
1843 if( !node )
1844 return FALSE ;
1845
1846 if( node -> type != HASH_INT )
1847 {
1848 n_log( LOG_ERR, "Can't get key[\"%s\"] of type HASH_INT, key is type %s", key, ht_node_type( node ) );
1849 return FALSE ;
1850 }
1851
1852 (*val) = node -> data . ival ;
1853
1854 return TRUE ;
1855} /* _ht_get_int() */
1856
1857
1858
1866int _ht_get_double( HASH_TABLE *table, const char *key, double *val )
1867{
1868 __n_assert( table, return FALSE );
1869 __n_assert( key, return FALSE );
1870
1871 if( strlen( key ) == 0 )
1872 return FALSE ;
1873
1874 HASH_NODE *node = _ht_get_node( table, key );
1875
1876 if( !node )
1877 return FALSE ;
1878
1879 if( node -> type != HASH_DOUBLE )
1880 {
1881 n_log( LOG_ERR, "Can't get key[\"%s\"] of type HASH_DOUBLE, key is type %s", key, ht_node_type( node ) );
1882 return FALSE ;
1883 }
1884
1885 (*val) = node -> data . fval ;
1886
1887 return TRUE ;
1888} /* _ht_get_double()*/
1889
1890
1891
1899int _ht_get_ptr( HASH_TABLE *table, const char *key, void **val )
1900{
1901 __n_assert( table, return FALSE );
1902 __n_assert( key, return FALSE );
1903 if( strlen( key ) == 0 )
1904 return FALSE ;
1905
1906 HASH_NODE *node = _ht_get_node( table, key );
1907 if( !node )
1908 return FALSE ;
1909
1910 if( node -> type != HASH_PTR )
1911 {
1912 n_log( LOG_ERR, "Can't get key[\"%s\"] of type HASH_PTR, key is type %s", key, ht_node_type( node ) );
1913 return FALSE ;
1914 }
1915
1916 (*val) = node -> data . ptr ;
1917
1918 return TRUE ;
1919} /* _ht_get_ptr() */
1920
1921
1922
1930int _ht_get_string( HASH_TABLE *table, const char *key, char **val )
1931{
1932 __n_assert( table, return FALSE );
1933 __n_assert( key, return FALSE );
1934 if( strlen( key ) == 0 )
1935 return FALSE ;
1936
1937 HASH_NODE *node = _ht_get_node( table, key );
1938 if( !node )
1939 return FALSE ;
1940
1941 if( node -> type != HASH_STRING )
1942 {
1943 n_log( LOG_ERR, "Can't get key[\"%s\"] of type HASH_STRING, key is type %s", key, ht_node_type( node ) );
1944 return FALSE ;
1945 }
1946
1947 (*val) = node -> data . string ;
1948
1949 return TRUE ;
1950} /* _ht_get_string() */
1951
1952
1953
1960int _ht_remove( HASH_TABLE *table, const char *key )
1961{
1962 HASH_VALUE hash_value[ 2 ] = { 0 , 0 };
1963 size_t index = 0;
1964
1965 HASH_NODE *node_ptr = NULL ;
1966 LIST_NODE *node_to_kill = NULL ;
1967
1968 __n_assert( table, return FALSE );
1969 __n_assert( key, return FALSE );
1970 if( strlen( key ) == 0 )
1971 return FALSE ;
1972
1973 MurmurHash( key, strlen( key ), table -> seed, &hash_value );
1974 index= (hash_value[ 0 ])%(table->size) ;
1975
1976 if( !table -> hash_table[ index ] -> start )
1977 {
1978 n_log( LOG_ERR, "Can't remove key[\"%s\"], table is empty", key );
1979 return FALSE ;
1980 }
1981
1982 list_foreach( list_node, table -> hash_table[ index ] )
1983 {
1984 node_ptr = (HASH_NODE *)list_node -> ptr ;
1985 /* if we found the same */
1986 if( !strcmp( key, node_ptr -> key ) )
1987 {
1988 node_to_kill = list_node ;
1989 break ;
1990 }
1991 }
1992 if( node_to_kill )
1993 {
1994 node_ptr = remove_list_node( table -> hash_table[ index ], node_to_kill, HASH_NODE );
1995 _ht_node_destroy( node_ptr );
1996
1997 table -> nb_keys -- ;
1998
1999 return TRUE ;
2000 }
2001 n_log( LOG_ERR, "Can't delete key[\"%s\"]: inexisting key", key );
2002 return FALSE ;
2003}/* ht_remove() */
2004
2005
2006
2014int _empty_ht( HASH_TABLE *table )
2015{
2016 HASH_NODE *hash_node = NULL ;
2017
2018 __n_assert( table, return FALSE );
2019
2020 HASH_VALUE index = 0 ;
2021 for( index = 0 ; index < table -> size ; index ++ )
2022 {
2023 while( table -> hash_table[ index ] && table -> hash_table[ index ] -> start )
2024 {
2025 hash_node = remove_list_node( table -> hash_table[ index ], table -> hash_table[ index ] -> start, HASH_NODE );
2026 _ht_node_destroy( hash_node );
2027 }
2028 }
2029 table -> nb_keys = 0 ;
2030 return TRUE ;
2031} /* empty_ht */
2032
2033
2034
2042int _destroy_ht( HASH_TABLE **table )
2043{
2044 __n_assert( table&&(*table), n_log( LOG_ERR, "Can't destroy table: already NULL" ); return FALSE );
2045
2046 if( (*table )-> hash_table )
2047 {
2048 //empty_ht( (*table) );
2049
2050 HASH_VALUE it = 0 ;
2051 for( it = 0 ; it < (*table) -> size ; it ++ )
2052 {
2053 if( (*table) -> hash_table[ it ] )
2054 list_destroy( &(*table) -> hash_table[ it ] );
2055 }
2056 Free( (*table )->hash_table );
2057 }
2058 Free( (*table ) );
2059 return TRUE ;
2060} /* _destroy_ht */
2061
2062
2069void _ht_print( HASH_TABLE *table )
2070{
2071 __n_assert( table, return );
2072 __n_assert( table -> hash_table, return );
2073 ht_foreach( node, table )
2074 {
2075 printf( "key:%s node:%s\n", ((HASH_NODE *)node ->ptr)->key, ((HASH_NODE *)node ->ptr)->key );
2076 }
2077
2078 return ;
2079} /* _ht_print(...) */
2080
2081
2090LIST *_ht_search( HASH_TABLE *table, int (*node_is_matching)( HASH_NODE *node ) )
2091{
2092 __n_assert( table, return NULL );
2093
2094 LIST *results = new_generic_list( 0 );
2095 __n_assert( results, return NULL );
2096
2097 ht_foreach( node, table )
2098 {
2099 HASH_NODE *hnode = (HASH_NODE *)node -> ptr;
2100 if( node_is_matching( hnode ) == TRUE )
2101 {
2102 list_push( results, strdup( hnode -> key ), &free );
2103 }
2104 }
2105
2106 if( results -> nb_items < 1 )
2107 list_destroy( &results );
2108
2109 return results ;
2110} /* _ht_search(...) */
2111
2112
2113
2114/************ HASH_TABLES FUNCTION POINTERS AND COMMON TABLE TYPE FUNCS ************/
2115
2116
2117
2124HASH_TABLE *new_ht_trie( size_t alphabet_length, size_t alphabet_offset )
2125{
2126 HASH_TABLE *table = NULL ;
2127
2128 Malloc( table, HASH_TABLE, 1 );
2129 __n_assert( table, n_log( LOG_ERR, "Error allocating HASH_TABLE *table" ); return NULL );
2130
2131 table -> size = 0 ;
2132 table -> seed = 0 ;
2133 table -> nb_keys = 0 ;
2134 errno = 0 ;
2135 table -> hash_table = NULL ;
2136
2137 table -> ht_put_int = _ht_put_int_trie ;
2138 table -> ht_put_double = _ht_put_double_trie ;
2139 table -> ht_put_ptr = _ht_put_ptr_trie ;
2140 table -> ht_put_string = _ht_put_string_trie ;
2141 table -> ht_put_string_ptr = _ht_put_string_ptr_trie ;
2142 table -> ht_get_int = _ht_get_int_trie ;
2143 table -> ht_get_double = _ht_get_double_trie ;
2144 table -> ht_get_string = _ht_get_string_trie ;
2145 table -> ht_get_ptr = _ht_get_ptr_trie ;
2146 table -> ht_remove = _ht_remove_trie ;
2147 table -> ht_search = _ht_search_trie ;
2148 table -> empty_ht = _empty_ht_trie ;
2149 table -> destroy_ht = _destroy_ht_trie ;
2150 table -> ht_print = _ht_print_trie ;
2151
2152 table -> alphabet_length = alphabet_length ;
2153 table -> alphabet_offset = alphabet_offset ;
2154
2155 table -> root = _ht_new_node_trie( table, '\0' );
2156 table -> mode = HASH_TRIE ;
2157
2158 return table ;
2159} /* new_ht_trie */
2160
2161
2162
2168HASH_TABLE *new_ht( size_t size )
2169{
2170 HASH_TABLE *table = NULL ;
2171
2172 if( size < 1 )
2173 {
2174 n_log( LOG_ERR, "Invalide size %d for new_ht()", size );
2175 return NULL ;
2176 }
2177 Malloc( table, HASH_TABLE, 1 );
2178 __n_assert( table, n_log( LOG_ERR, "Error allocating HASH_TABLE *table" ); return NULL );
2179
2180 table -> size = size ;
2181 table -> seed = (uint32_t)rand()%100000 ;
2182 table -> nb_keys = 0 ;
2183 errno = 0 ;
2184 Malloc( table -> hash_table, LIST *, size );
2185 // table -> hash_table = (LIST **)calloc( size, sizeof( LIST *) );
2186 __n_assert( table -> hash_table, n_log( LOG_ERR, "Can't allocate table -> hash_table with size %d !", size ); Free( table ); return NULL );
2187
2188 size_t it = 0 ;
2189 for( it = 0 ; it < size ; it ++ )
2190 {
2191 table -> hash_table[ it ] = new_generic_list( 0 );
2192 // if no valid table then unroll previsouly created slots
2193 if( !table -> hash_table[ it ] )
2194 {
2195 n_log( LOG_ERR, "Can't allocate table -> hash_table[ %d ] !", it );
2196 size_t it_delete = 0 ;
2197 for( it_delete = 0 ; it_delete < it ; it_delete ++ )
2198 {
2199 list_destroy( &table -> hash_table[ it_delete ] );
2200 }
2201 Free( table -> hash_table );
2202 Free( table );
2203 return NULL ;
2204 }
2205 }
2206 table -> mode = HASH_CLASSIC ;
2207
2208 table -> ht_put_int = _ht_put_int ;
2209 table -> ht_put_double = _ht_put_double ;
2210 table -> ht_put_ptr = _ht_put_ptr ;
2211 table -> ht_put_string = _ht_put_string ;
2212 table -> ht_put_string_ptr = _ht_put_string_ptr ;
2213 table -> ht_get_int = _ht_get_int ;
2214 table -> ht_get_double = _ht_get_double ;
2215 table -> ht_get_string = _ht_get_string ;
2216 table -> ht_get_ptr = _ht_get_ptr ;
2217 table -> ht_get_node = _ht_get_node;
2218 table -> ht_remove = _ht_remove ;
2219 table -> ht_search = _ht_search ;
2220 table -> empty_ht = _empty_ht ;
2221 table -> destroy_ht = _destroy_ht ;
2222 table -> ht_print = _ht_print ;
2223
2224 return table ;
2225} /* new_ht(...) */
2226
2227
2228
2235HASH_NODE *ht_get_node( HASH_TABLE *table, const char *key )
2236{
2237 __n_assert( table, return FALSE );
2238 __n_assert( key, return FALSE );
2239 return table->ht_get_node( table, key );
2240} /*ht_get_node(...) */
2241
2242
2243
2251int ht_get_double( HASH_TABLE *table, const char *key, double *val )
2252{
2253 __n_assert( table, return FALSE );
2254 __n_assert( key, return FALSE );
2255 return table->ht_get_double( table, key, val );
2256} /* ht_get_double(...) */
2257
2258
2259
2267int ht_get_int( HASH_TABLE *table, const char *key, int *val )
2268{
2269 __n_assert( table, return FALSE );
2270 __n_assert( key, return FALSE );
2271 return table->ht_get_int( table, key, val );
2272} /* ht_get_int(...) */
2273
2274
2275
2283int ht_get_ptr( HASH_TABLE *table, const char *key, void **val )
2284{
2285 __n_assert( table, return FALSE );
2286 __n_assert( key, return FALSE );
2287 return table -> ht_get_ptr( table, key, &(*val) );
2288} /* ht_get_ptr(...) */
2289
2290
2291
2299int ht_get_string( HASH_TABLE *table, const char *key, char **val )
2300{
2301 __n_assert( table, return FALSE );
2302 __n_assert( key, return FALSE );
2303 return table->ht_get_string( table, key, val );
2304} /* ht_get_string(...) */
2305
2306
2307
2315int ht_put_double( HASH_TABLE *table, const char *key, double value )
2316{
2317 __n_assert( table, return FALSE );
2318 __n_assert( key, return FALSE );
2319 return table->ht_put_double( table, key, value );
2320} /* ht_put_double(...) */
2321
2322
2323
2331int ht_put_int( HASH_TABLE *table, const char *key, int value )
2332{
2333 __n_assert( table, return FALSE );
2334 __n_assert( key, return FALSE );
2335 return table->ht_put_int( table, key, value );
2336} /* ht_put_int(...) */
2337
2338
2339
2348int ht_put_ptr( HASH_TABLE *table, const char *key, void *ptr, void (*destructor)(void *ptr ) )
2349{
2350 __n_assert( table, return FALSE );
2351 __n_assert( key, return FALSE );
2352 return table->ht_put_ptr( table, key, ptr, destructor );
2353} /* ht_put_ptr(...) */
2354
2355
2356
2364int ht_put_string( HASH_TABLE *table, const char *key, char *string )
2365{
2366 __n_assert( table, return FALSE );
2367 __n_assert( key, return FALSE );
2368 return table->ht_put_string( table, key, string );
2369} /* ht_put_string(...) */
2370
2371
2372
2380int ht_put_string_ptr( HASH_TABLE *table, const char *key, char *string )
2381{
2382 __n_assert( table, return FALSE );
2383 __n_assert( key, return FALSE );
2384 return table->ht_put_string_ptr( table, key, string );
2385} /* ht_put_string_ptr(...) */
2386
2387
2388
2395int ht_remove( HASH_TABLE *table, const char *key )
2396{
2397 __n_assert( table, return FALSE );
2398 __n_assert( key, return FALSE );
2399 return table->ht_remove( table, key );
2400} /* ht_remove(...) */
2401
2402
2403
2408void ht_print( HASH_TABLE *table )
2409{
2410 __n_assert( table, return );
2411 table->ht_print( table );
2412 return ;
2413} /* ht_print(...) */
2414
2415
2416
2423LIST *ht_search( HASH_TABLE *table, int (*node_is_matching)( HASH_NODE *node ) )
2424{
2425 __n_assert( table, return FALSE );
2426 return table -> ht_search( table, node_is_matching );
2427} /* ht_search(...) */
2428
2429
2430
2436int empty_ht( HASH_TABLE *table )
2437{
2438 __n_assert( table, return FALSE );
2439 return table -> empty_ht( table );
2440} /* empty_ht(...) */
2441
2442
2443
2449int destroy_ht( HASH_TABLE **table )
2450{
2451 __n_assert( (*table), return FALSE );
2452 return (*table)->destroy_ht( table );
2453} /* destroy_ht(...) */
2454
2455
2456
2463HASH_NODE *ht_get_node_ex( HASH_TABLE *table, HASH_VALUE hash_value )
2464{
2465 __n_assert( table, return NULL );
2466 __n_assert( table -> mode == HASH_CLASSIC, return NULL );
2467
2468 size_t index = 0;
2469 HASH_NODE *node_ptr = NULL ;
2470
2471 index= (hash_value)%(table->size) ;
2472 if( !table -> hash_table[ index ] -> start )
2473 {
2474 return NULL ;
2475 }
2476
2477 list_foreach( list_node, table -> hash_table[ index ] )
2478 {
2479 node_ptr = (HASH_NODE *)list_node -> ptr ;
2480 if( hash_value == node_ptr -> hash_value )
2481 {
2482 return node_ptr ;
2483 }
2484 }
2485 return NULL ;
2486} /* ht_get_node_ex() */
2487
2488
2489
2497int ht_get_ptr_ex( HASH_TABLE *table, HASH_VALUE hash_value, void **val )
2498{
2499 __n_assert( table, return FALSE );
2500 __n_assert( table -> mode == HASH_CLASSIC, return FALSE );
2501
2502 HASH_NODE *node = ht_get_node_ex( table, hash_value );
2503 if( !node )
2504 return FALSE ;
2505
2506 if( node -> type != HASH_PTR )
2507 {
2508 n_log( LOG_ERR, "Can't get key[\"%lld\"] of type HASH_PTR, key is type %s", hash_value, ht_node_type( node ) );
2509 return FALSE ;
2510 }
2511
2512 (*val) = node -> data . ptr ;
2513
2514 return TRUE ;
2515} /* ht_get_ptr_ex() */
2516
2517
2518
2527int ht_put_ptr_ex( HASH_TABLE *table, HASH_VALUE hash_value, void *val, void (*destructor)( void *ptr ) )
2528{
2529 __n_assert( table, return FALSE );
2530 __n_assert( table -> mode == HASH_CLASSIC, return FALSE );
2531
2532 size_t index = 0;
2533 HASH_NODE *new_hash_node = NULL ;
2534 HASH_NODE *node_ptr = NULL ;
2535
2536 index = (hash_value)%(table->size) ;
2537
2538 /* we have some nodes here. Let's check if the key already exists */
2539 list_foreach( list_node, table -> hash_table[ index ] )
2540 {
2541 node_ptr = (HASH_NODE *)list_node -> ptr ;
2542 /* if we found the same key we just replace the value and return */
2543 if( hash_value == node_ptr -> hash_value )
2544 {
2545 /* let's check the key isn't already assigned with another data type */
2546 if( node_ptr -> type == HASH_PTR )
2547 {
2548 if( list_node -> destroy_func )
2549 {
2550 list_node -> destroy_func( node_ptr -> data . ptr );
2551 node_ptr -> data . ptr = val ;
2552 list_node -> destroy_func = destructor ;
2553 }
2554 return TRUE ;
2555 }
2556 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 ) );
2557 return FALSE ; /* key registered with another data type */
2558 }
2559 }
2560
2561 Malloc( new_hash_node, HASH_NODE, 1 );
2562 __n_assert( new_hash_node, n_log( LOG_ERR, "Could not allocate new_hash_node" ); return FALSE );
2563
2564 new_hash_node -> key = NULL ;
2565 new_hash_node -> hash_value = hash_value ;
2566 new_hash_node -> data . ptr = val ;
2567 new_hash_node -> type = HASH_PTR ;
2568 new_hash_node -> destroy_func = destructor ;
2569
2570 table -> nb_keys ++ ;
2571
2572 return list_push( table -> hash_table[ index ], new_hash_node, &_ht_node_destroy );
2573}/* ht_put_ptr_ex() */
2574
2575
2576
2583int ht_remove_ex( HASH_TABLE *table, HASH_VALUE hash_value )
2584{
2585 __n_assert( table, return FALSE );
2586 __n_assert( table -> mode == HASH_CLASSIC, return FALSE );
2587
2588 size_t index = 0;
2589 HASH_NODE *node_ptr = NULL ;
2590 LIST_NODE *node_to_kill = NULL ;
2591
2592 index= (hash_value)%(table->size) ;
2593 if( !table -> hash_table[ index ] -> start )
2594 {
2595 n_log( LOG_ERR, "Can't remove key[\"%d\"], table is empty", hash_value );
2596 return FALSE ;
2597 }
2598
2599 list_foreach( list_node, table -> hash_table[ index ] )
2600 {
2601 node_ptr = (HASH_NODE *)list_node -> ptr ;
2602 /* if we found the same */
2603 if( hash_value == node_ptr -> hash_value )
2604 {
2605 node_to_kill = list_node ;
2606 break ;
2607 }
2608 }
2609 if( node_to_kill )
2610 {
2611 node_ptr = remove_list_node( table -> hash_table[ index ], node_to_kill, HASH_NODE );
2612 _ht_node_destroy( node_ptr );
2613
2614 table -> nb_keys -- ;
2615
2616 return TRUE ;
2617 }
2618 n_log( LOG_ERR, "Can't delete key[\"%d\"]: inexisting key", hash_value );
2619 return FALSE ;
2620}/* ht_remove_ex() */
2621
2622
2623
2631LIST *ht_get_completion_list( HASH_TABLE *table, const char *keybud, size_t max_results )
2632{
2633 __n_assert( table, return NULL );
2634 __n_assert( keybud, return NULL );
2635
2636 LIST *results = NULL ;
2637 if( table -> mode == HASH_TRIE )
2638 {
2639 int found = FALSE ;
2640 results = new_generic_list( max_results );
2641 HASH_NODE* node = _ht_get_node_trie( table, keybud );
2642 if( node )
2643 {
2644 if( list_push( results, strdup( keybud ), &free ) == TRUE )
2645 {
2646 found = TRUE ;
2647 _ht_depth_first_search( node, results );
2648 }
2649 }
2650 else
2651 {
2652 node = table -> root ;
2653 for( size_t it = 0 ; it < table -> alphabet_length ; it++ )
2654 {
2655 if( node -> children[ it ] )
2656 {
2657 char keybud[ 3 ] = "" ;
2658 keybud[ 0 ] = it + table -> alphabet_offset ;
2659 list_push( results , strdup( keybud ), &free );
2660 found = TRUE ;
2661 }
2662 }
2663 }
2664 if( found == FALSE )
2665 list_destroy( &results );
2666 }
2667 else if( table -> mode == HASH_CLASSIC )
2668 {
2669 int matching_nodes( HASH_NODE *node)
2670 {
2671 if( strncasecmp( keybud, node -> key, strlen( keybud ) ) == 0 )
2672 return TRUE ;
2673 return FALSE ;
2674 }
2675 results = ht_search( table, &matching_nodes );
2676 }
2677 else
2678 {
2679 n_log( LOG_ERR, "unsupported mode %d", table -> mode );
2680 return NULL ;
2681 }
2682 return results ;
2683} /* ht_get_completion_list(...) */
2684
2685
2691int is_prime( int nb )
2692{
2693 /* quick test for first primes */
2694 if( nb <= 1 ) return FALSE ;
2695 if( nb <= 3 ) return TRUE ;
2696
2697 /* skip middle five numbers in below loop */
2698 if( (nb%2 == 0) || (nb%3 == 0) )
2699 return FALSE ;
2700
2701 /* looping */
2702 for( int it = 5 ; it*it <= nb ; it = it + 6 )
2703 {
2704 if( (nb%it == 0) || (nb%( it + 2 ) == 0) )
2705 return FALSE ;
2706 }
2707 return TRUE ;
2708} /* is_prime() */
2709
2710
2716int next_prime( int nb )
2717{
2718 if( nb <= 1 )
2719 return 2 ;
2720
2721 int next_prime = nb;
2722 do
2723 {
2724 next_prime++;
2725 }
2726 while( is_prime( next_prime ) == FALSE );
2727
2728 return next_prime;
2729} /* next_prime() */
2730
2731
2732
2733
2739int ht_get_table_collision_percentage( HASH_TABLE *table )
2740{
2741 __n_assert( table, return FALSE );
2742 __n_assert( table -> mode == HASH_CLASSIC, return FALSE );
2743
2744 if( table -> size == 0 ) return FALSE ;
2745
2746 int nb_collisionned_lists = 0 ;
2747
2748 for( size_t hash_it = 0 ; hash_it < table -> size ; hash_it ++ )
2749 {
2750 if( table -> hash_table[ hash_it ] && table -> hash_table[ hash_it ] -> nb_items > 1 )
2751 {
2752 nb_collisionned_lists ++ ;
2753 }
2754 }
2755 int collision_percentage = ( 100 * nb_collisionned_lists ) / table -> size ;
2756 return collision_percentage ;
2757} /* ht_get_table_collision_percentage() */
2758
2759
2760
2766int ht_get_optimal_size( HASH_TABLE *table )
2767{
2768 __n_assert( table, return FALSE );
2769
2770 int optimum_size = (double)table -> nb_keys * 1.3 ;
2771 if( is_prime( optimum_size ) != TRUE )
2772 optimum_size = next_prime( optimum_size );
2773
2774 return optimum_size ;
2775} /* ht_get_optimal_size() */
2776
2777
2778
2779
2786int ht_resize( HASH_TABLE **table, size_t size )
2787{
2788 __n_assert( (*table), return FALSE );
2789
2790 if( size < 1 )
2791 {
2792 n_log( LOG_ERR, "invalid size %d for hash table %p", size, (*table) );
2793 return FALSE ;
2794 }
2795 HT_FOREACH( node, (*table), { node -> need_rehash = 1 ; } );
2796
2797 if( size > (*table) -> size )
2798 {
2799 Realloc( (*table) -> hash_table, LIST *, size );
2800 if( !(*table) -> hash_table )
2801 {
2802 n_log( LOG_ERR,"Realloc did not augment the size the table !" );
2803 }
2804 else
2805 {
2806 for( size_t it = (*table) -> size ; it < size ; it ++ )
2807 {
2808 (*table) -> hash_table[ it ] = new_generic_list( 0 );
2809 // if no valid table then unroll previsouly created slots
2810 if( !(*table) -> hash_table[ it ] )
2811 {
2812 n_log( LOG_ERR, "Can't allocate table -> hash_table[ %d ] !", it );
2813 for( size_t it_delete = 0 ; it_delete < it ; it_delete ++ )
2814 {
2815 list_destroy( &(*table) -> hash_table[ it_delete ] );
2816 }
2817 Free( (*table) -> hash_table );
2818 Free( (*table) );
2819 return FALSE ;
2820 }
2821 }
2822 for( size_t it = 0 ; it < size ; it ++ )
2823 {
2824 if( ( (*table) -> hash_table[ it ] ) )
2825 {
2826 while( (*table) -> hash_table[ it ] -> start )
2827 {
2828 HASH_NODE *hash_node = (HASH_NODE *)(*table) -> hash_table[ it ] -> start -> ptr ;
2829 if( hash_node -> need_rehash == 0 )
2830 break ;
2831 hash_node -> need_rehash = 0 ;
2832 LIST_NODE *node = list_node_shift( (*table) -> hash_table[ it ] );
2833 node -> next = node -> prev = NULL ;
2834 size_t index= (hash_node -> hash_value)%(size);
2835 list_node_push( (*table) -> hash_table[ index ], node );
2836 }
2837 }
2838 }
2839 }
2840 }
2841 else
2842 {
2843 for( size_t it = 0 ; it < (*table) -> size ; it ++ )
2844 {
2845 if( ( (*table) -> hash_table[ it ] ) )
2846 {
2847 while( (*table) -> hash_table[ it ] -> start )
2848 {
2849 HASH_NODE *hash_node = (HASH_NODE *)(*table) -> hash_table[ it ] -> start -> ptr ;
2850 if( hash_node -> need_rehash == 0 )
2851 break ;
2852 hash_node -> need_rehash = 0 ;
2853 LIST_NODE *node = list_node_shift( (*table) -> hash_table[ it ] );
2854 node -> next = node -> prev = NULL ;
2855 size_t index= (hash_node -> hash_value)%(size);
2856 list_node_push( (*table) -> hash_table[ index ], node );
2857 }
2858 }
2859 }
2860 for( size_t it = size ; it < (*table) -> size ; it ++ )
2861 {
2862 list_destroy( &(*table) -> hash_table[ it ] );
2863 }
2864 Realloc( (*table) -> hash_table, LIST *, size );
2865 if( !(*table) -> hash_table )
2866 {
2867 n_log( LOG_ERR,"Realloc did not reduce the resize the table !" );
2868 }
2869 }
2870 (*table) -> size = size ;
2871
2872 return TRUE ;
2873} /* ht_resize() */
2874
2875
2876
2882int ht_optimize( HASH_TABLE **table )
2883{
2884 __n_assert( (*table), return FALSE );
2885
2886 size_t optimal_size = ht_get_optimal_size( (*table) );
2887 if( optimal_size == FALSE )
2888 {
2889 return FALSE;
2890 }
2891
2892 int collision_percentage = ht_get_table_collision_percentage( (*table) );
2893 if( collision_percentage == FALSE )
2894 return FALSE ;
2895
2896 int resize_result = ht_resize( &(*table), optimal_size );
2897 if( resize_result == FALSE )
2898 {
2899 return FALSE ;
2900 }
2901
2902 collision_percentage = ht_get_table_collision_percentage( (*table) );
2903 if( collision_percentage == FALSE )
2904 {
2905 return FALSE ;
2906 }
2907
2908 return TRUE ;
2909}/* ht_optimize() */
2910
FreeNoLog
#define FreeNoLog(__ptr)
Free Handler without log.
Definition n_common.h:276
FALL_THROUGH
#define FALL_THROUGH
fall through macro for switch cases, avoid warning at compilation
Definition n_common.h:56
Malloc
#define Malloc(__ptr, __struct, __size)
Malloc Handler to get errors and set to 0.
Definition n_common.h:191
__n_assert
#define __n_assert(__ptr, __ret)
macro to assert things
Definition n_common.h:284
FORCE_INLINE
#define FORCE_INLINE
FORCE_INLINE portable macro.
Definition n_common.h:149
Realloc
#define Realloc(__ptr, __struct, __size)
Realloc Handler to get errors.
Definition n_common.h:225
Free
#define Free(__ptr)
Free Handler to get errors.
Definition n_common.h:264
HASH_TABLE::ht_get_node
HASH_NODE *(* ht_get_node)(struct HASH_TABLE *table, const char *key)
get HASH_NODE at 'key' from table
Definition n_hash.h:126
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:144
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:134
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: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:140
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:136
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:146
HASH_TABLE::ht_print
void(* ht_print)(struct HASH_TABLE *table)
print table
Definition n_hash.h:154
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:130
HASH_NODE::children
struct HASH_NODE ** children
HASH_TRIE mode: pointers to children.
Definition n_hash.h:100
HASH_TABLE::size
size_t size
size of the hash table
Definition n_hash.h:110
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:132
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:138
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:2283
ht_foreach
#define ht_foreach(__ITEM_, __HASH_)
ForEach macro helper (classic / old)
Definition n_hash.h:162
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:2527
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:2267
ht_node_type
char * ht_node_type(HASH_NODE *node)
get the type of a node , text version
Definition n_hash.c:1423
ht_search
LIST * ht_search(HASH_TABLE *table, int(*node_is_matching)(HASH_NODE *node))
seach table for matching nodes
Definition n_hash.c:2423
destroy_ht
int destroy_ht(HASH_TABLE **table)
empty a table and destroy it
Definition n_hash.c:2449
ht_remove
int ht_remove(HASH_TABLE *table, const char *key)
remove and delete node at key in table
Definition n_hash.c:2395
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:2463
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:1048
HASH_PTR
#define HASH_PTR
value of pointer type inside the hash node
Definition n_hash.h:56
new_ht
HASH_TABLE * new_ht(size_t size)
Create a hash table with the given size.
Definition n_hash.c:2168
MurmurHash
#define MurmurHash(__key, __len, __seed, __out)
Murmur hash macro helper 64 bits.
Definition n_hash.h:321
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:2739
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:2251
next_prime
int next_prime(int nb)
compute next prime number after nb
Definition n_hash.c:2716
HASH_DOUBLE
#define HASH_DOUBLE
value of double type inside the hash node
Definition n_hash.h:52
empty_ht
int empty_ht(HASH_TABLE *table)
empty a table
Definition n_hash.c:2436
is_prime
int is_prime(int nb)
test if number is a prime number or not
Definition n_hash.c:2691
HASH_STRING
#define HASH_STRING
value of char * type inside the hash node
Definition n_hash.h:54
ht_print
void ht_print(HASH_TABLE *table)
print contents of table
Definition n_hash.c:2408
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:2631
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:2315
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:2299
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:2364
MurmurHash3_x86_128
void MurmurHash3_x86_128(const void *key, const int len, uint32_t seed, void *out)
MurmurHash3 was written by Austin Appleby, and is placed in the public domain.
Definition n_hash.c:1118
ht_resize
int ht_resize(HASH_TABLE **table, size_t size)
rehash table according to size (HASH_CLASSIC mode only)
Definition n_hash.c:2786
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:1295
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:2583
HASH_CLASSIC
#define HASH_CLASSIC
Murmur hash using hash key string, hash key numeric value, index table with lists of elements.
Definition n_hash.h:60
ht_get_node
HASH_NODE * ht_get_node(HASH_TABLE *table, const char *key)
get node at 'key' from 'table'
Definition n_hash.c:2235
new_ht_trie
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:2124
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:2331
HASH_TRIE
#define HASH_TRIE
TRIE tree using hash key string.
Definition n_hash.h:62
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:2348
ht_optimize
int ht_optimize(HASH_TABLE **table)
try an automatic optimization of the table
Definition n_hash.c:2882
HASH_INT
#define HASH_INT
compatibility with existing rot func
Definition n_hash.h:50
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:2380
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:2766
HT_FOREACH
#define HT_FOREACH(__ITEM_, __HASH_,...)
ForEach macro helper.
Definition n_hash.h:194
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:2497
HASH_UNKNOWN
#define HASH_UNKNOWN
value of unknow type inside the hash node
Definition n_hash.h:58
HASH_NODE
structure of a hash table node
Definition n_hash.h:82
HASH_TABLE
structure of a hash table
Definition n_hash.h:108
remove_list_node
#define remove_list_node(__LIST_,__NODE_, __TYPE_)
Remove macro helper for void pointer casting.
Definition n_list.h:83
list_push
int list_push(LIST *list, void *ptr, void(*destructor)(void *ptr))
Add a pointer to the end of the list.
Definition n_list.c:244
list_foreach
#define list_foreach(__ITEM_, __LIST_)
ForEach macro helper.
Definition n_list.h:70
list_node_shift
LIST_NODE * list_node_shift(LIST *list)
Get a LIST_NODE pointer from the start of the list.
Definition n_list.c:179
list_destroy
int list_destroy(LIST **list)
Empty and Free a list container.
Definition n_list.c:605
new_generic_list
LIST * new_generic_list(int max_items)
Initialiaze a generic list container to max_items pointers.
Definition n_list.c:20
list_node_push
int list_node_push(LIST *list, LIST_NODE *node)
Add a filled node to the end of the list.
Definition n_list.c:120
LIST
Structure of a generic LIST container.
Definition n_list.h:45
LIST_NODE
Structure of a generic list node.
Definition n_list.h:27
n_log
#define n_log(__LEVEL__,...)
Logging function wrapper to get line and func.
Definition n_log.h:74
LOG_DEBUG
#define LOG_DEBUG
debug-level messages
Definition n_log.h:66
LOG_ERR
#define LOG_ERR
error conditions
Definition n_log.h:58
n_common.h
Common headers and low-level hugly functions & define.
_ht_node_destroy
void _ht_node_destroy(void *node)
destroy a HASH_NODE by first calling the HASH_NODE destructor
Definition n_hash.c:624
fmix64
FORCE_INLINE 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:1023
_destroy_ht
int _destroy_ht(HASH_TABLE **table)
Free and set the table to NULL.
Definition n_hash.c:2042
_ht_get_double
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:1866
_ht_new_double_node
HASH_NODE * _ht_new_double_node(HASH_TABLE *table, const char *key, double value)
node creation, HASH_CLASSIC mode
Definition n_hash.c:1540
_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:1669
getblock32
FORCE_INLINE 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:984
_ht_put_int_trie
int _ht_put_int_trie(HASH_TABLE *table, const char *key, int value)
put an integral value with given key in the targeted hash table [TRIE HASH TABLE)
Definition n_hash.c:72
_ht_new_string_ptr_node
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:1585
_ht_put_string_trie
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:177
_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 [CLASSIC HASH TABLE)
Definition n_hash.c:1631
_ht_get_ptr
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:1899
_ht_new_node_trie
HASH_NODE * _ht_new_node_trie(HASH_TABLE *table, const char key)
node creation, HASH_CLASSIC mode
Definition n_hash.c:32
_ht_depth_first_search
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:900
_ht_print_trie
void _ht_print_trie(HASH_TABLE *table)
Generic print func call for trie trees.
Definition n_hash.c:827
_ht_get_string_trie
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:445
getblock64
FORCE_INLINE 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:994
_ht_print_trie_helper
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:787
_ht_check_trie_divergence
int _ht_check_trie_divergence(HASH_TABLE *table, const char *key)
check and return branching index in key if any
Definition n_hash.c:509
_ht_new_int_node
HASH_NODE * _ht_new_int_node(HASH_TABLE *table, const char *key, int value)
node creation, HASH_CLASSIC mode
Definition n_hash.c:1519
_ht_get_node_trie
HASH_NODE * _ht_get_node_trie(HASH_TABLE *table, const char *key)
retrieve a HASH_NODE at key from table
Definition n_hash.c:339
_ht_put_string
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:1752
_ht_new_ptr_node
HASH_NODE * _ht_new_ptr_node(HASH_TABLE *table, const char *key, void *value, void(*destructor)(void *ptr))
node creation, HASH_CLASSIC mode, pointer to string value
Definition n_hash.c:1607
_ht_put_string_ptr_trie
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:233
_ht_put_ptr
int _ht_put_ptr(HASH_TABLE *table, const char *key, void *ptr, void(*destructor)(void *ptr))
put a pointer value with given key in the targeted hash table
Definition n_hash.c:1708
_ht_print
void _ht_print(HASH_TABLE *table)
Generic print func call for classic hash tables.
Definition n_hash.c:2069
_ht_new_node
HASH_NODE * _ht_new_node(HASH_TABLE *table, const char *key)
node creation, HASH_CLASSIC mode
Definition n_hash.c:1480
_ht_find_longest_prefix_trie
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:555
fmix32
FORCE_INLINE 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:1005
_ht_get_ptr_trie
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:476
_ht_get_string
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:1930
_empty_ht
int _empty_ht(HASH_TABLE *table)
Empty a hash table (CLASSIC mode)
Definition n_hash.c:2014
BIG_CONSTANT
#define BIG_CONSTANT(x)
max unsigned long long
Definition n_hash.c:930
_ht_is_leaf_node_trie
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:594
_ht_put_string_ptr
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:1792
_ht_search_trie
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:875
_ht_put_double_trie
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:125
_ht_get_node
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:1442
BYTESWAP64
#define BYTESWAP64(x)
32 bits bytes swap
Definition n_hash.c:965
BYTESWAP32
#define BYTESWAP32(x)
32 bits bytes swap
Definition n_hash.c:958
_destroy_ht_trie
int _destroy_ht_trie(HASH_TABLE **table)
Free and set the table to NULL (TRIE mode)
Definition n_hash.c:767
_ht_put_ptr_trie
int _ht_put_ptr_trie(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 [TRIE HASH TABLE)
Definition n_hash.c:286
_empty_ht_trie
int _empty_ht_trie(HASH_TABLE *table)
Empty a TRIE hash table.
Definition n_hash.c:746
_ht_get_double_trie
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:413
_ht_remove
int _ht_remove(HASH_TABLE *table, const char *key)
Remove a key from a hash table.
Definition n_hash.c:1960
_ht_get_int
int _ht_get_int(HASH_TABLE *table, const char *key, int *val)
Retrieve an integral value in the hash table, at the given key.
Definition n_hash.c:1834
_ht_remove_trie
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:670
_ht_get_int_trie
int _ht_get_int_trie(HASH_TABLE *table, const char *key, int *val)
Retrieve an integral value in the hash table, at the given key.
Definition n_hash.c:381
_ht_search
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:2090
_ht_new_string_node
HASH_NODE * _ht_new_string_node(HASH_TABLE *table, const char *key, char *value)
node creation, HASH_CLASSIC mode, strdup of value
Definition n_hash.c:1561
_ht_search_trie_helper
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:848
ROTL64
#define ROTL64(x, r)
64 bit rotate left
Definition n_hash.c:926
ROTL32
#define ROTL32(x, r)
32 bit rotate left
Definition n_hash.c:928
n_hash.h
Hash functions and table.
n_log.h
Generic log system.
n_str.h
N_STR and string function declaration.