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