Nilorea Library

- Main Page
- Modules
- Data Structures
- Files

- File List
- Globals

All Data Structures Files Functions Variables Typedefs Macros Groups
n_hash.c
Go to the documentation of this file.
1
8 #include "n_hash.h"
9
10
11 #ifndef MSVC
12
19 static uint32_t rotl32 ( uint32_t x, int8_t r )
20 {
21 return (x << r) | (x >> (32 - r));
22 } /* rotl32(...) */
23
24 #endif
25
34 FORCE_INLINE uint32_t getblock( const uint32_t *p , int i )
35 {
36 uint32_t var ;
37 memcpy( &var , p+i , sizeof( uint32_t ) );
38 #if __BYTE_ORDER == __LITTLE_ENDIAN
39 var = htonl( var );
40 #endif
41 return var ;
42 } /* get_block(...) */
43
44
45
51 FORCE_INLINE uint32_t fmix32 ( uint32_t h )
52 {
53 h ^= h >> 16;
54 h *= 0x85ebca6b;
55 h ^= h >> 13;
56 h *= 0xc2b2ae35;
57 h ^= h >> 16;
58
59 return h;
60 } /* fmix32(...) */
61
67 FORCE_INLINE uint64_t fmix64 ( uint64_t k )
68 {
69 k ^= k >> 33;
70 k *= BIG_CONSTANT(0xff51afd7ed558ccd);
71 k ^= k >> 33;
72 k *= BIG_CONSTANT(0xc4ceb9fe1a85ec53);
73 k ^= k >> 33;
74
75 return k;
76 } /* fmix64(...) */
77
78
79
92 void MurmurHash3_x86_32 ( const void * key, int len, uint32_t seed, void * out )
93 {
94 const uint8_t * data = (const uint8_t*)key;
95 const int nblocks = len / 4;
96
97 uint32_t h1 = seed;
98
99 uint32_t c1 = 0xcc9e2d51;
100 uint32_t c2 = 0x1b873593;
101
102 /* body */
103 const uint32_t * blocks = (const uint32_t *)(data + nblocks*4);
104
105 for(int i = -nblocks; i; i++)
106 {
107 uint32_t k1 = getblock(blocks,i);
108
109 k1 *= c1;
110 k1 = ROTL32(k1,15);
111 k1 *= c2;
112
113 h1 ^= k1;
114 h1 = ROTL32(h1,13);
115 h1 = h1*5+0xe6546b64;
116 }
117
118 /* tail */
119 const uint8_t * tail = (const uint8_t*)(data + nblocks*4);
120
121 uint32_t k1 = 0;
122
123 switch(len & 3)
124 {
125 case 3: k1 ^= tail[2] << 16;
126 case 2: k1 ^= tail[1] << 8;
127 case 1: k1 ^= tail[0];
128 k1 *= c1; k1 = ROTL32(k1,15); k1 *= c2; h1 ^= k1;
129 };
130
131 /* finalization */
132 h1 ^= len;
133 h1 = fmix32(h1);
134 *(uint32_t*)out = h1;
135 } /* MurmurHash3_x86_32(...) */
136
137
138
151 void MurmurHash3_x86_128 ( const void * key, const int len, uint32_t seed, void * out )
152 {
153 const uint8_t * data = (const uint8_t*)key;
154 const int nblocks = len / 16;
155
156 uint32_t h1 = seed;
157 uint32_t h2 = seed;
158 uint32_t h3 = seed;
159 uint32_t h4 = seed;
160
161 uint32_t c1 = 0x239b961b;
162 uint32_t c2 = 0xab0e9789;
163 uint32_t c3 = 0x38b34ae5;
164 uint32_t c4 = 0xa1e38b93;
165
166 /* body */
167 const uint32_t * blocks = (const uint32_t *)(data + nblocks*16);
168
169 for(int i = -nblocks; i; i++)
170 {
171 uint32_t k1 = getblock(blocks,i*4+0);
172 uint32_t k2 = getblock(blocks,i*4+1);
173 uint32_t k3 = getblock(blocks,i*4+2);
174 uint32_t k4 = getblock(blocks,i*4+3);
175
176 k1 *= c1; k1 = ROTL32(k1,15); k1 *= c2; h1 ^= k1;
177 h1 = ROTL32(h1,19); h1 += h2; h1 = h1*5+0x561ccd1b;
178
179 k2 *= c2; k2 = ROTL32(k2,16); k2 *= c3; h2 ^= k2;
180 h2 = ROTL32(h2,17); h2 += h3; h2 = h2*5+0x0bcaa747;
181
182 k3 *= c3; k3 = ROTL32(k3,17); k3 *= c4; h3 ^= k3;
183 h3 = ROTL32(h3,15); h3 += h4; h3 = h3*5+0x96cd1c35;
184
185 k4 *= c4; k4 = ROTL32(k4,18); k4 *= c1; h4 ^= k4;
186 h4 = ROTL32(h4,13); h4 += h1; h4 = h4*5+0x32ac3b17;
187 }
188
189 /* tail */
190 const uint8_t * tail = (const uint8_t*)(data + nblocks*16);
191
192 uint32_t k1 = 0;
193 uint32_t k2 = 0;
194 uint32_t k3 = 0;
195 uint32_t k4 = 0;
196
197 switch(len & 15)
198 {
199 case 15: k4 ^= tail[14] << 16;
200 case 14: k4 ^= tail[13] << 8;
201 case 13: k4 ^= tail[12] << 0;
202 k4 *= c4; k4 = ROTL32(k4,18); k4 *= c1; h4 ^= k4;
203
204 case 12: k3 ^= tail[11] << 24;
205 case 11: k3 ^= tail[10] << 16;
206 case 10: k3 ^= tail[ 9] << 8;
207 case 9: k3 ^= tail[ 8] << 0;
208 k3 *= c3; k3 = ROTL32(k3,17); k3 *= c4; h3 ^= k3;
209
210 case 8: k2 ^= tail[ 7] << 24;
211 case 7: k2 ^= tail[ 6] << 16;
212 case 6: k2 ^= tail[ 5] << 8;
213 case 5: k2 ^= tail[ 4] << 0;
214 k2 *= c2; k2 = ROTL32(k2,16); k2 *= c3; h2 ^= k2;
215
216 case 4: k1 ^= tail[ 3] << 24;
217 case 3: k1 ^= tail[ 2] << 16;
218 case 2: k1 ^= tail[ 1] << 8;
219 case 1: k1 ^= tail[ 0] << 0;
220 k1 *= c1; k1 = ROTL32(k1,15); k1 *= c2; h1 ^= k1;
221 };
222 /* finalization */
223 h1 ^= len; h2 ^= len; h3 ^= len; h4 ^= len;
224
225 h1 += h2; h1 += h3; h1 += h4;
226 h2 += h1; h3 += h1; h4 += h1;
227
228 h1 = fmix32(h1);
229 h2 = fmix32(h2);
230 h3 = fmix32(h3);
231 h4 = fmix32(h4);
232
233 h1 += h2; h1 += h3; h1 += h4;
234 h2 += h1; h3 += h1; h4 += h1;
235
236 ((uint32_t*)out)[0] = h1;
237 ((uint32_t*)out)[1] = h2;
238 ((uint32_t*)out)[2] = h3;
239 ((uint32_t*)out)[3] = h4;
240 } /* MurmurHash3_x86_32(...) */
241
242
243
249 char *ht_node_type( HASH_NODE *node )
250 {
251 static char *HASH_TYPE_STR[ 5 ] = { "HASH_INT" , "HASH_DOUBLE" , "HASH_STRING" , "HASH_PTR" , "HASH_UNKNOWN" };
252
253 _assert( node , return NULL );
254
255 if( node -> type >= 0 && node -> type < HASH_UNKNOWN )
256 return HASH_TYPE_STR[ node -> type ];
257
258 return NULL ;
259 } /* ht_node_type(...) */
260
261
262
268 HASH_TABLE *new_ht( int size )
269 {
270 HASH_TABLE *table = NULL ;
271
272 if( size < 1 )
273 {
274 n_log( LOG_ERR , "Invalide size %d for new_ht()" , size );
275 return NULL ;
276 }
277 Malloc( table , HASH_TABLE , 1 );
278 _assert( table , n_log( LOG_ERR , "Error allocating HASH_TABLE *table" );return NULL );
279
280 table -> size = size ;
281 table -> nb_keys = 0 ;
282 table -> hash_table = (LIST **)calloc( size , sizeof( LIST *) );
283 _assert( table -> hash_table , n_log( LOG_ERR , "Can't allocate table -> hash_table !" );Free( table );return NULL );
284
285 for( int it = 0 ; it < size ; it ++ )
286 {
287 table -> hash_table[ it ] = new_generic_list( -1 );
288 }
289 return table ;
290 } /* new_ht */
291
292
293
301 int ht_put_int( HASH_TABLE *table , char * key , int val )
302 {
303 uint32_t hash_value = 0 ;
304 unsigned int index = 0;
305
306 HASH_NODE *new_hash_node = NULL ;
307 HASH_NODE *node_ptr = NULL ;
308
309 _assert( table , return FALSE );
310 _assert( key , return FALSE );
311
312 MurmurHash3_x86_32( key , strlen( key ) , 42 , &hash_value );
313 index= (hash_value)%(table->size) ;
314
315 /* we have some nodes here. Let's check if the key already exists */
316 list_foreach( list_node , table -> hash_table[ index ] )
317 {
318 node_ptr = (HASH_NODE *)list_node -> ptr ;
319 /* if we found the same key we just replace the value and return */
320 if( !strcmp( key , node_ptr -> key ) )
321 {
322 /* let's check the key isn't already assigned with another data type */
323 if( node_ptr -> type == HASH_INT )
324 {
325 node_ptr -> data . ival = val ;
326 return TRUE ;
327 }
328 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 ) );
329 return FALSE ; /* key registered with another data type */
330 }
331 }
332
333 Malloc( new_hash_node , HASH_NODE , 1 );
334 _assert( new_hash_node , n_log( LOG_ERR , "Could not allocate new_hash_node" ); return FALSE );
335
336 new_hash_node -> key = strdup( key );
337 new_hash_node -> data. ival = val ;
338 new_hash_node -> type = HASH_INT ;
339
340 table -> nb_keys ++ ;
341
342 return list_push( table -> hash_table[ index ] , new_hash_node , NULL );
343 } /*ht_put_int() */
344
345
346
354 int ht_put_double( HASH_TABLE *table , char * key , double val )
355 {
356 uint32_t hash_value = 0 ;
357 unsigned int index = 0;
358
359 HASH_NODE *new_hash_node = NULL ;
360 HASH_NODE *node_ptr = NULL ;
361
362 _assert( table , return FALSE );
363 _assert( key , return FALSE );
364
365 MurmurHash3_x86_32( key , strlen( key ) , 42 , &hash_value );
366 index= (hash_value)%(table->size) ;
367
368 /* we have some nodes here. Let's check if the key already exists */
369 list_foreach( list_node , table -> hash_table[ index ] )
370 {
371 node_ptr = (HASH_NODE *)list_node -> ptr ;
372 /* if we found the same key we just replace the value and return */
373 if( !strcmp( key , node_ptr -> key ) )
374 {
375 /* let's check the key isn't already assigned with another data type */
376 if( node_ptr -> type == HASH_DOUBLE )
377 {
378 node_ptr -> data . fval = val ;
379 return TRUE ;
380 }
381 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 ) );
382 return FALSE ; /* key registered with another data type */
383 }
384 }
385
386 Malloc( new_hash_node , HASH_NODE , 1 );
387 _assert( new_hash_node , n_log( LOG_ERR , "Could not allocate new_hash_node" ); return FALSE );
388
389 new_hash_node -> key = strdup( key );
390 new_hash_node -> data. fval = val ;
391 new_hash_node -> type = HASH_DOUBLE ;
392
393 table -> nb_keys ++ ;
394
395 return list_push( table -> hash_table[ index ] , new_hash_node , NULL );
396 } /*ht_put_double()*/
397
398
399
408 int ht_put_ptr( HASH_TABLE *table , char *key , void *val , void (*destructor)(void *ptr ) )
409 {
410 uint32_t hash_value = 0 ;
411 unsigned int index = 0;
412
413 HASH_NODE *new_hash_node = NULL ;
414 HASH_NODE *node_ptr = NULL ;
415
416 _assert( table , return FALSE );
417 _assert( key , return FALSE );
418
419 MurmurHash3_x86_32( key , strlen( key ) , 42 , &hash_value );
420 index= (hash_value)%(table->size) ;
421
422 /* we have some nodes here. Let's check if the key already exists */
423 list_foreach( list_node , table -> hash_table[ index ] )
424 {
425 node_ptr = (HASH_NODE *)list_node -> ptr ;
426 /* if we found the same key we just replace the value and return */
427 if( !strcmp( key , node_ptr -> key ) )
428 {
429 /* let's check the key isn't already assigned with another data type */
430 if( node_ptr -> type == HASH_PTR )
431 {
432 if( list_node -> destroy_func )
433 {
434 list_node -> destroy_func( node_ptr -> data . ptr );
435 node_ptr -> data . ptr = val ;
436 list_node -> destroy_func = destructor ;
437 }
438 return TRUE ;
439 }
440 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 ) );
441 return FALSE ; /* key registered with another data type */
442 }
443 }
444
445 Malloc( new_hash_node , HASH_NODE , 1 );
446 _assert( new_hash_node , n_log( LOG_ERR , "Could not allocate new_hash_node" ); return FALSE );
447
448 new_hash_node -> key = strdup( key );
449 new_hash_node -> data . ptr = val ;
450 new_hash_node -> type = HASH_PTR ;
451
452 table -> nb_keys ++ ;
453
454 return list_push( table -> hash_table[ index ] , new_hash_node , NULL );
455 }/* ht_put_ptr() */
456
457
458
466 int ht_put_string( HASH_TABLE *table , char *key , char *val )
467 {
468 uint32_t hash_value = 0 ;
469 unsigned int index = 0;
470
471 HASH_NODE *new_hash_node = NULL ;
472 HASH_NODE *node_ptr = NULL ;
473
474 _assert( table , return FALSE );
475 _assert( key , return FALSE );
476
477 MurmurHash3_x86_32( key , strlen( key ) , 42 , &hash_value );
478 index= (hash_value)%(table->size) ;
479
480 /* we have some nodes here. Let's check if the key already exists */
481 list_foreach( list_node , table -> hash_table[ index ] )
482 {
483 node_ptr = (HASH_NODE *)list_node -> ptr ;
484 /* if we found the same key we just replace the value and return */
485 if( !strcmp( key , node_ptr -> key ) )
486 {
487 /* let's check the key isn't already assigned with another data type */
488 if( node_ptr -> type == HASH_STRING )
489 {
490 Free( node_ptr -> data . string );
491 node_ptr -> data . string = strdup( val );
492 return TRUE ;
493 }
494 n_log( LOG_ERR , "Can't add key[\"%s\"] with type HASH_STRING, key already exist with type %s" , node_ptr -> key , ht_node_type( node_ptr ) );
495 return FALSE ; /* key registered with another data type */
496 }
497 }
498
499 Malloc( new_hash_node , HASH_NODE , 1 );
500 _assert( new_hash_node , n_log( LOG_ERR , "Could not allocate new_hash_node" ); return FALSE );
501
502 new_hash_node -> key = strdup( key );
503 new_hash_node -> data . string = strdup( val );
504 new_hash_node -> type = HASH_STRING ;
505
506 table -> nb_keys ++ ;
507
508 return list_push( table -> hash_table[ index ] , new_hash_node , free );
509 } /*ht_put_string */
510
511
512
519 HASH_NODE *ht_get_node( HASH_TABLE *table , char *key )
520 {
521 uint32_t hash_value = 0 ;
522 unsigned int index = 0;
523
524 HASH_NODE *node_ptr = NULL ;
525
526 _assert( table , return FALSE );
527 _assert( key , return FALSE );
528
529 MurmurHash3_x86_32( key , strlen( key ) , 42 , &hash_value );
530 index= (hash_value)%(table->size) ;
531
532 if( !table -> hash_table[ index ] -> start )
533 return NULL ;
534
535 list_foreach( list_node , table -> hash_table[ index ] )
536 {
537 node_ptr = (HASH_NODE *)list_node -> ptr ;
538 if( !strcmp( key , node_ptr -> key ) )
539 {
540 table -> nb_keys -- ;
541 return node_ptr ;
542 }
543 }
544 return NULL ;
545 } /* ht_get_node() */
546
547
548
556 int ht_get_int( HASH_TABLE *table , char *key , int *val )
557 {
558 _assert( table , return FALSE );
559 _assert( key , return FALSE );
560
561 HASH_NODE *node = ht_get_node( table , key );
562
563 if( !node ) return FALSE ;
564
565 if( node -> type != HASH_INT )
566 {
567 n_log( LOG_ERR , "Can't get key[\"%s\"] of type HASH_INT, key is type %s" , key , ht_node_type( node ) );
568 return FALSE ;
569 }
570
571 (*val) = node -> data . ival ;
572
573 return TRUE ;
574 } /* ht_get_int() */
575
576
577
585 int ht_get_double( HASH_TABLE *table , char * key , double *val )
586 {
587 _assert( table , return FALSE );
588 _assert( key , return FALSE );
589
590 HASH_NODE *node = ht_get_node( table , key );
591
592 if( !node ) return FALSE ;
593
594 if( node -> type != HASH_DOUBLE )
595 {
596 n_log( LOG_ERR , "Can't get key[\"%s\"] of type HASH_DOUBLE, key is type %s" , key , ht_node_type( node ) );
597 return FALSE ;
598 }
599
600 (*val) = node -> data . fval ;
601
602 return TRUE ;
603 } /* ht_get_double()*/
604
605
606
614 int ht_get_ptr( HASH_TABLE *table , char * key , void **val )
615 {
616 _assert( table , return FALSE );
617 _assert( key , return FALSE );
618
619 HASH_NODE *node = ht_get_node( table , key );
620 if( !node ) return FALSE ;
621
622 if( node -> type != HASH_PTR )
623 {
624 n_log( LOG_ERR , "Can't get key[\"%s\"] of type HASH_PTR, key is type %s" , key , ht_node_type( node ) );
625 return FALSE ;
626 }
627
628 (*val) = node -> data . ptr ;
629
630 return TRUE ;
631 } /* ht_get_ptr() */
632
633
641 int ht_get_string( HASH_TABLE *table , char * key , char **val )
642 {
643 _assert( table , return FALSE );
644 _assert( key , return FALSE );
645
646 HASH_NODE *node = ht_get_node( table , key );
647 if( !node ) return FALSE ;
648
649 if( node -> type != HASH_STRING )
650 {
651 n_log( LOG_ERR , "Can't get key[\"%s\"] of type HASH_STRING, key is type %s" , key , ht_node_type( node ) );
652 return FALSE ;
653 }
654
655 (*val) = node -> data . string ;
656
657 return TRUE ;
658 } /* ht_get_string() */
659
660
661
668 int ht_remove( HASH_TABLE *table , char *key )
669 {
670 uint32_t hash_value = 0 ;
671 unsigned int index = 0;
672
673 HASH_NODE *node_ptr = NULL ;
674 LIST_NODE *node_to_kill = NULL ;
675
676 _assert( table , return FALSE );
677 _assert( key , return FALSE );
678
679 MurmurHash3_x86_32( key , strlen( key ) , 42 , &hash_value );
680 index= (hash_value)%(table->size) ;
681
682 if( !table -> hash_table[ index ] -> start )
683 {
684 n_log( LOG_ERR , "Can't remove key[\"%s\"], table is empty" , key );
685 return FALSE ;
686 }
687
688 list_foreach( list_node , table -> hash_table[ index ] )
689 {
690 node_ptr = (HASH_NODE *)list_node -> ptr ;
691 /* if we found the same */
692 if( !strcmp( key , node_ptr -> key ) )
693 {
694 node_to_kill = list_node ;
695 break ;
696 }
697 }
698 if( node_to_kill )
699 {
700 void (*destructor)( void *ptr ) = node_to_kill -> destroy_func ;
701 node_ptr = remove_list_node( table -> hash_table[ index ] , node_to_kill , HASH_NODE );
702 Free( node_ptr -> key );
703 if( node_ptr -> type == HASH_STRING )
704 {
705 Free( node_ptr -> data . string );
706 }
707 if( node_ptr -> type == HASH_PTR )
708 {
709 if( destructor )
710 {
711 destructor( node_ptr -> data . ptr );
712 }
713 else
714 {
715 Free( node_ptr -> data . ptr );
716 }
717 }
718 Free( node_ptr );
719
720 table -> nb_keys -- ;
721
722 return TRUE ;
723 }
724 n_log( LOG_ERR , "Can't delete key[\"%s\"]: inexisting key" , key );
725 return FALSE ;
726 }/* ht_remove() */
727
728
734 int empty_ht( HASH_TABLE *table )
735 {
736 HASH_NODE *hash_node = NULL ;
737
738 _assert( table , return FALSE );
739
740 for( int index = 0 ; index < table -> size ; index ++ )
741 {
742 while( table -> hash_table[ index ] -> start )
743 {
744 void (*destructor)( void *ptr ) = table -> hash_table[ index ] -> start -> destroy_func ;
745 hash_node = remove_list_node( table -> hash_table[ index ] , table -> hash_table[ index ] -> start , HASH_NODE );
746 Free( hash_node -> key );
747 if( hash_node -> type == HASH_STRING )
748 {
749 Free( hash_node -> data . string );
750 }
751 if( hash_node -> type == HASH_PTR )
752 {
753 if( destructor )
754 {
755 destructor( hash_node -> data . ptr );
756 }
757 else
758 {
759 Free( hash_node -> data . ptr );
760 }
761 }
762 Free( hash_node );
763 }
764 }
765 table -> nb_keys = 0 ;
766 return TRUE ;
767 } /* empty_ht */
768
769
770
776 int destroy_ht( HASH_TABLE **table )
777 {
778 _assert( (*table) , n_log( LOG_ERR , "Can't destroy table: already NULL" ); return FALSE );
779
780 if( (*table )-> hash_table )
781 {
782 empty_ht( (*table) );
783
784 for( int it = 0 ; it < (*table) -> size ; it ++ )
785 {
786 if( (*table) -> hash_table[ it ] )
787 list_destroy( &(*table) -> hash_table[ it ] );
788 }
789 Free( (*table )->hash_table );
790 }
791 Free( (*table ) );
792 return TRUE ;
793 } /* destroy_ht */
794
795
796
797