n_hash.h

Go to the documentation of this file.

 
#ifndef NILOREA_HASH_HEADER_GUARD
#define NILOREA_HASH_HEADER_GUARD
 
#ifdef __cplusplus
extern "C" {
#endif
 
#if defined( __linux__ ) || defined( _AIX ) || defined( __sun )
#include <arpa/inet.h>
#include <string.h>
#else
#include <string.h>
#endif
 
#include <stdint.h>
 
#include "n_common.h"
#include "n_list.h"
 
                //#if defined(_MSC_VER)
                //#include <stdlib.h>
                //#define ROTL32(x,y)     _rotl(x,y)
                //#define ROTL64(x,y)     _rotl64(x,y)
                //#define BIG_CONSTANT(x) (x)
                //#else
                //#define ROTL32(x,y)     rotl32(x,y)
                //#define ROTL64(x,y)     rotl64(x,y)
                //#define BIG_CONSTANT(x) (x##LLU)
                //#endif /* if defined MSVC ... */
 
#define HASH_INT        1
#define HASH_DOUBLE     2
#define HASH_STRING     4
#define HASH_PTR        8
#define HASH_UNKNOWN    16
#define HASH_CLASSIC    128
#define HASH_TRIE       256
 
                typedef size_t HASH_VALUE ;
 
                union HASH_DATA
                {
                                int    ival ;
                                double fval ;
                                void   *ptr ;
                                char   *string ;
                };
 
                typedef struct HASH_NODE
                {
                                char *key ;
                                char key_id ;
                                HASH_VALUE hash_value ;
                                int type ;
                                union HASH_DATA data ;
                                void (*destroy_func)( void *ptr );
                                int is_leaf ;
                                int need_rehash ;
                                struct HASH_NODE **children ;
                                size_t alphabet_length ;
                } HASH_NODE ;
 
 
                typedef struct HASH_TABLE
                {
        size_t size;
        size_t nb_keys ;
        size_t seed ;
        LIST **hash_table;
        HASH_NODE *root ;
        size_t alphabet_length ;
        size_t alphabet_offset ;
        unsigned int mode ;
        HASH_NODE *(*ht_get_node)( struct HASH_TABLE *table, const char *key );
        int (*ht_put_int)( struct HASH_TABLE *table, const char *key, int val );
        int (*ht_put_double)( struct HASH_TABLE *table, const char *key, double val );
        int (*ht_put_ptr)( struct HASH_TABLE *table, const char *key, void  *ptr, void (*destructor)( void *ptr ) );
        int (*ht_put_string)( struct HASH_TABLE *table, const char *key, char  *val );
        int (*ht_put_string_ptr)( struct HASH_TABLE *table, const char *key, char  *val );
        int (*ht_get_int)( struct HASH_TABLE *table, const char *key, int *val );
        int (*ht_get_double)( struct HASH_TABLE *table, const char *key, double *val );
        int (*ht_get_ptr)( struct HASH_TABLE *table, const char *key, void  **val );
        int (*ht_get_string)( struct HASH_TABLE *table, const char *key, char  **val );
        int (*ht_remove)( struct HASH_TABLE *table, const char *key );
        LIST *(*ht_search)( struct HASH_TABLE *table, int (*node_is_matching)( HASH_NODE *node ) );
        int (*empty_ht)( struct HASH_TABLE *table );
        int (*destroy_ht)( struct HASH_TABLE **table );
        void (*ht_print)( struct HASH_TABLE *table );
    } HASH_TABLE ;
 
#define hash_val( node , type )\
    ( (node && node -> ptr) ? ( (type *)( ( (HASH_NODE *)node -> ptr )-> data . ptr) ) : NULL )
 
#define ht_foreach( __ITEM_ , __HASH_  ) \
    if( !__HASH_ ) \
    { \
        n_log( LOG_ERR , "Error in ht_foreach, %s is NULL" , #__HASH_ ); \
    } \
    else if( __HASH_ -> mode != HASH_CLASSIC ) \
    { \
        n_log( LOG_ERR , "Error in ht_foreach( %s , %s ) unsupportted mode %d" , #__ITEM_ , #__HASH_  , __HASH_ -> mode ); \
    } \
    else \
    for( size_t __hash_it = 0 ; __hash_it < __HASH_ -> size ; __hash_it ++ ) \
    for( LIST_NODE *__ITEM_ = __HASH_ -> hash_table[ __hash_it ] -> start ; __ITEM_ != NULL; __ITEM_ = __ITEM_ -> next )
 
#define ht_foreach_r( __ITEM_ , __HASH_ , __ITERATOR_ ) \
    if( !__HASH_ ) \
    { \
        n_log( LOG_ERR , "Error in ht_foreach, %s is NULL" , #__HASH_ ); \
    } \
    else if( __HASH_ -> mode != HASH_CLASSIC ) \
    { \
        n_log( LOG_ERR , "Error in ht_foreach, %d is an unsupported mode" , __HASH_ -> mode ); \
    } \
    else \
    for( size_t __ITERATOR_ = 0 ; __ITERATOR_ < __HASH_ -> size ; __ITERATOR_ ++ ) \
    for( LIST_NODE *__ITEM_ = __HASH_ -> hash_table[ __ITERATOR_ ] -> start ; __ITEM_ != NULL; __ITEM_ = __ITEM_ -> next )
 
#define HASH_VAL( node , type )\
    ( (node && node -> data . ptr) ? ( (type *)node -> data . ptr ) : NULL )
 
#define HT_FOREACH( __ITEM_ , __HASH_ , ... ) \
    { \
        do \
        { \
            if( !__HASH_ ) \
            { \
                n_log( LOG_ERR , "Error in ht_foreach, %s is NULL" , #__HASH_ ); \
            } \
            else \
            { \
                if( __HASH_ -> mode == HASH_CLASSIC ) \
                { \
                    int CONCAT(__ht_node_trie_func_macro_break_flag_classic,__LINE__) = 0 ; \
                    for( size_t __hash_it = 0 ; __hash_it < __HASH_ -> size ; __hash_it ++ ) \
                    { \
                        for( LIST_NODE *__ht_list_node = __HASH_ -> hash_table[ __hash_it ] -> start ; __ht_list_node != NULL; __ht_list_node = __ht_list_node -> next ) \
                        { \
                            HASH_NODE *__ITEM_ = (HASH_NODE *)__ht_list_node -> ptr ; \
                            CONCAT(__ht_node_trie_func_macro_break_flag_classic,__LINE__) = 1 ; \
                            __VA_ARGS__ \
                            CONCAT(__ht_node_trie_func_macro_break_flag_classic,__LINE__) = 0 ; \
                        } \
                        if( CONCAT(__ht_node_trie_func_macro_break_flag_classic,__LINE__) == 1 ) \
                        break ; \
                    } \
                } \
                else if( __HASH_ -> mode == HASH_TRIE ) \
                { \
                    int CONCAT(__ht_node_trie_func_macro,__LINE__)( HASH_NODE *__ITEM_ ) \
                    { \
                        if( !__ITEM_ ) return TRUE ; \
                        int CONCAT(__ht_node_trie_func_macro_break_flag,__LINE__) = 1 ; \
                        if( __ITEM_ -> is_leaf ) \
                        { \
                            do \
                            { \
                                __VA_ARGS__  \
                                CONCAT(__ht_node_trie_func_macro_break_flag,__LINE__) = 0 ; \
                            }while ( 0 ); \
                        } \
                        if( CONCAT(__ht_node_trie_func_macro_break_flag,__LINE__) == 1 ) return FALSE ; \
                        for( size_t it = 0 ; it < __ITEM_ -> alphabet_length ; it++ ) \
                        { \
                            if( CONCAT(__ht_node_trie_func_macro,__LINE__)( __ITEM_ -> children[ it ] ) == FALSE )  \
                            return FALSE ; \
                        } \
                        return TRUE ; \
                    } \
                    CONCAT(__ht_node_trie_func_macro,__LINE__)( __HASH_ -> root ); \
                } \
                else \
                { \
                    n_log( LOG_ERR , "Error in ht_foreach, %d is an unsupported mode" , __HASH_ -> mode ); \
                    break ; \
                } \
            } \
        }while( 0 ); \
    }
 
#define HT_FOREACH_R( __ITEM_ , __HASH_ , __ITERATOR , ... ) \
    { \
        do \
        { \
            if( !__HASH_ ) \
            { \
                n_log( LOG_ERR , "Error in ht_foreach, %s is NULL" , #__HASH_ ); \
            } \
            else \
            { \
                if( __HASH_ -> mode == HASH_CLASSIC ) \
                { \
                    int CONCAT(__ht_node_trie_func_macro_break_flag_classic,__LINE__) = 0 ; \
                    for( size_t __ITERATOR = 0 ; __ITERATOR < __HASH_ -> size ; __ITERATOR ++ ) \
                    { \
                        for( LIST_NODE *__ht_list_node = __HASH_ -> hash_table[ __ITERATOR ] -> start ; __ht_list_node != NULL; __ht_list_node = __ht_list_node -> next ) \
                        { \
                            HASH_NODE *__ITEM_ = (HASH_NODE *)__ht_list_node -> ptr ; \
                            CONCAT(__ht_node_trie_func_macro_break_flag_classic,__LINE__) = 1 ; \
                            __VA_ARGS__ \
                            CONCAT(__ht_node_trie_func_macro_break_flag_classic,__LINE__) = 0 ; \
                        } \
                        if( CONCAT(__ht_node_trie_func_macro_break_flag_classic,__LINE__) == 1 ) \
                        break ; \
                    } \
                } \
                else if( __HASH_ -> mode == HASH_TRIE ) \
                { \
                    int CONCAT(__ht_node_trie_func_macro,__LINE__)( HASH_NODE *__ITEM_ ) \
                    { \
                        if( !__ITEM_ ) return TRUE ; \
                        int CONCAT(__ht_node_trie_func_macro_break_flag,__LINE__) = 1 ; \
                        if( __ITEM_ -> is_leaf ) \
                        { \
                            do \
                            { \
                                __VA_ARGS__  \
                                CONCAT(__ht_node_trie_func_macro_break_flag,__LINE__) = 0 ; \
                            }while ( 0 ); \
                        } \
                        if( CONCAT(__ht_node_trie_func_macro_break_flag,__LINE__) == 1 ) return FALSE ; \
                        for( size_t it = 0 ; it < __ITEM_ -> alphabet_length ; it++ ) \
                        { \
                            if( CONCAT(__ht_node_trie_func_macro,__LINE__)( __ITEM_ -> children[ it ] ) == FALSE )  \
                            return FALSE ; \
                        } \
                        return TRUE ; \
                    } \
                    CONCAT(__ht_node_trie_func_macro,__LINE__)( __HASH_ -> root ); \
                } \
                else \
                { \
                    n_log( LOG_ERR , "Error in ht_foreach, %d is an unsupported mode" , __HASH_ -> mode ); \
                    break ; \
                } \
            } \
        }while( 0 ); \
    }
 
    void MurmurHash3_x86_32  ( const void * key, int len, uint32_t seed, void * out );
    void MurmurHash3_x86_128 ( const void * key, int len, uint32_t seed, void * out );
    void MurmurHash3_x64_128 ( const void * key, const size_t len, const uint64_t seed, void * out );
#ifdef ENV_32BITS
#define MurmurHash( __key , __len , __seed , __out ) MurmurHash3_x86_128( __key, __len, __seed, __out )
#else
#define MurmurHash( __key , __len , __seed , __out ) MurmurHash3_x64_128( __key, __len, __seed, __out )
#endif
 
 
 
    char *ht_node_type( HASH_NODE *node );
    HASH_NODE *ht_get_node( HASH_TABLE *table, const char *key );
 
    HASH_TABLE *new_ht( size_t size );
    HASH_TABLE *new_ht_trie( size_t alphabet_size, size_t alphabet_offset );
 
    int ht_get_double( HASH_TABLE *table, const char *key, double *val );
    int ht_get_int( HASH_TABLE *table, const char *key, int *val );
    int ht_get_ptr( HASH_TABLE *table, const char *key, void  **val );
    int ht_get_string( HASH_TABLE *table, const char *key, char  **val );
    int ht_put_double( HASH_TABLE *table, const char *key, double value );
    int ht_put_int( HASH_TABLE *table, const char *key, int value );
    int ht_put_ptr( HASH_TABLE *table, const char *key, void  *ptr, void (*destructor)(void *ptr ) );
    int ht_put_string( HASH_TABLE *table, const char *key, char *string );
    int ht_put_string_ptr( HASH_TABLE *table, const char *key, char *string );
    int ht_remove( HASH_TABLE *table, const char *key );
    void ht_print( HASH_TABLE *table );
    LIST *ht_search( HASH_TABLE *table, int (*node_is_matching)( HASH_NODE *node ) );
    int empty_ht( HASH_TABLE *table );
    int destroy_ht( HASH_TABLE **table );
 
    HASH_NODE *ht_get_node_ex( HASH_TABLE *table, HASH_VALUE hash_value );
    int ht_put_ptr_ex( HASH_TABLE *table, HASH_VALUE hash_value, void  *val, void (*destructor)( void *ptr ) );
    int ht_get_ptr_ex( HASH_TABLE *table, HASH_VALUE hash_value, void  **val );
    int ht_remove_ex( HASH_TABLE *table, HASH_VALUE hash_value );
 
    LIST *ht_get_completion_list( HASH_TABLE *table, const char *keybud, size_t max_results );
 
    int is_prime( int nb );
    int next_prime( int nb );
 
    int ht_get_table_collision_percentage( HASH_TABLE *table );
    int ht_get_optimal_size( HASH_TABLE *table );
    int ht_resize( HASH_TABLE **table, size_t size );
    int ht_optimize( HASH_TABLE **table );
 
#ifdef __cplusplus
}
#endif
 
#endif // header guard