Nilorea Library
C utilities for networking, threading, graphics
HASH TABLES: classic or trie tree hash_tables

Data Structures

union  HASH_DATA
 union of the possibles data values of a node More...
 
struct  HASH_NODE
 structure of a hash table node More...
 
struct  HASH_TABLE
 structure of a hash table More...
 

Macros

#define HASH_CLASSIC   128
 Murmur hash using hash key string, hash key numeric value, index table with lists of elements. More...
 
#define HASH_DOUBLE   2
 value of double type inside the hash node More...
 
#define HASH_INT   1
 compatibility with existing rot func More...
 
#define HASH_PTR   8
 value of pointer type inside the hash node More...
 
#define HASH_STRING   4
 value of char * type inside the hash node More...
 
#define HASH_TRIE   256
 TRIE tree using hash key string. More...
 
#define HASH_UNKNOWN   16
 value of unknow type inside the hash node More...
 
#define hash_val(node, type)    ( (node && node -> ptr) ? ( (type *)( ( (HASH_NODE *)node -> ptr )-> data . ptr) ) : NULL )
 Cast a HASH_NODE element. More...
 
#define HASH_VAL(node, type)    ( (node && node -> data . ptr) ? ( (type *)node -> data . ptr ) : NULL )
 Cast a HASH_NODE element. More...
 
#define ht_foreach(__ITEM_, __HASH_)
 ForEach macro helper (classic / old) More...
 
#define HT_FOREACH(__ITEM_, __HASH_, ...)
 ForEach macro helper. More...
 
#define HT_FOREACH_R(__ITEM_, __HASH_, __ITERATOR, ...)
 ForEach macro helper. More...
 
#define ht_foreach_r(__ITEM_, __HASH_, __ITERATOR_)
 ForEach macro helper, reentrant (classic / old)
More...
 
#define MurmurHash(__key, __len, __seed, __out)   MurmurHash3_x64_128( __key, __len, __seed, __out )
 Murmur hash macro helper 64 bits. More...
 

Typedefs

typedef size_t HASH_VALUE
 type of a HASH_VALUE More...
 

Functions

int destroy_ht (HASH_TABLE **table)
 empty a table and destroy it More...
 
int empty_ht (HASH_TABLE *table)
 empty a table More...
 
LISTht_get_completion_list (HASH_TABLE *table, const char *keybud, size_t max_results)
 get next matching keys in table tree More...
 
int ht_get_double (HASH_TABLE *table, const char *key, double *val)
 get double at 'key' from 'table' More...
 
int ht_get_int (HASH_TABLE *table, const char *key, int *val)
 get node at 'key' from 'table' More...
 
HASH_NODEht_get_node (HASH_TABLE *table, const char *key)
 get node at 'key' from 'table' More...
 
HASH_NODEht_get_node_ex (HASH_TABLE *table, HASH_VALUE hash_value)
 return the associated key's node inside the hash_table (HASH_CLASSIC only) More...
 
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_CLASSIC mode only) More...
 
int ht_get_ptr (HASH_TABLE *table, const char *key, void **val)
 get pointer at 'key' from 'table' More...
 
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. More...
 
int ht_get_string (HASH_TABLE *table, const char *key, char **val)
 get string at 'key' from 'table' More...
 
int ht_get_table_collision_percentage (HASH_TABLE *table)
 get table collision percentage (HASH_CLASSIC mode only) More...
 
char * ht_node_type (HASH_NODE *node)
 get the type of a node , text version More...
 
int ht_optimize (HASH_TABLE **table)
 try an automatic optimization of the table More...
 
void ht_print (HASH_TABLE *table)
 print contents of table More...
 
int ht_put_double (HASH_TABLE *table, const char *key, double value)
 put a double value with given key in the targeted hash table More...
 
int ht_put_int (HASH_TABLE *table, const char *key, int value)
 put an integral value with given key in the targeted hash table More...
 
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 More...
 
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) More...
 
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 More...
 
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 More...
 
int ht_remove (HASH_TABLE *table, const char *key)
 remove and delete node at key in table More...
 
int ht_remove_ex (HASH_TABLE *table, HASH_VALUE hash_value)
 Remove a key from a hash table (HASH_CLASSIC only) More...
 
int ht_resize (HASH_TABLE **table, size_t size)
 rehash table according to size (HASH_CLASSIC mode only) More...
 
LISTht_search (HASH_TABLE *table, int(*node_is_matching)(HASH_NODE *node))
 seach table for matching nodes More...
 
int is_prime (int nb)
 test if number is a prime number or not More...
 
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. More...
 
void MurmurHash3_x86_128 (const void *key, int len, uint32_t seed, void *out)
 MurmurHash3 was written by Austin Appleby, and is placed in the public domain. More...
 
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. More...
 
HASH_TABLEnew_ht (size_t size)
 Create a hash table with the given size. More...
 
HASH_TABLEnew_ht_trie (size_t alphabet_size, size_t alphabet_offset)
 create a TRIE hash table with the alphabet_size, each key value beeing decreased by alphabet_offset More...
 
int next_prime (int nb)
 compute next prime number after nb More...
 

Detailed Description


Data Structure Documentation

◆ HASH_DATA

union HASH_DATA

union of the possibles data values of a node

Definition at line 68 of file n_hash.h.

+ Collaboration diagram for HASH_DATA:
Data Fields
double fval double type
int ival integral type
void * ptr pointer type
char * string char *type

◆ HASH_NODE

struct HASH_NODE

structure of a hash table node

Examples
ex_hash.c.

Definition at line 82 of file n_hash.h.

+ Collaboration diagram for HASH_NODE:

Data Fields

size_t alphabet_length
 HASH_TRIE mode: size of alphabet and so size of children allocated array. More...
 
struct HASH_NODE ** children
 HASH_TRIE mode: pointers to children. More...
 
union HASH_DATA data
 data inside the node More...
 
void(* destroy_func )(void *ptr)
 destroy_func More...
 
HASH_VALUE hash_value
 numeric key of the node if any, else < 0 More...
 
int is_leaf
 HASH_TRIE mode: does it have a value. More...
 
char * key
 string key of the node if any, else NULL More...
 
char key_id
 key id of the node if any More...
 
int need_rehash
 flag to mark a node for rehash More...
 
int type
 type of the node More...
 

Field Documentation

◆ alphabet_length

size_t HASH_NODE::alphabet_length

HASH_TRIE mode: size of alphabet and so size of children allocated array.

Definition at line 103 of file n_hash.h.

◆ children

struct HASH_NODE** HASH_NODE::children

HASH_TRIE mode: pointers to children.

Definition at line 101 of file n_hash.h.

Referenced by _ht_check_trie_divergence().

◆ data

union HASH_DATA HASH_NODE::data

data inside the node

Definition at line 93 of file n_hash.h.

◆ destroy_func

void(* HASH_NODE::destroy_func) (void *ptr)

destroy_func

Definition at line 95 of file n_hash.h.

◆ hash_value

HASH_VALUE HASH_NODE::hash_value

numeric key of the node if any, else < 0

Definition at line 89 of file n_hash.h.

◆ is_leaf

int HASH_NODE::is_leaf

HASH_TRIE mode: does it have a value.

Definition at line 97 of file n_hash.h.

◆ key

char* HASH_NODE::key

string key of the node if any, else NULL

Definition at line 85 of file n_hash.h.

◆ key_id

char HASH_NODE::key_id

key id of the node if any

Definition at line 87 of file n_hash.h.

◆ need_rehash

int HASH_NODE::need_rehash

flag to mark a node for rehash

Definition at line 99 of file n_hash.h.

◆ type

int HASH_NODE::type

type of the node

Definition at line 91 of file n_hash.h.

◆ HASH_TABLE

struct HASH_TABLE

structure of a hash table

Examples
ex_gui_dictionary.c, and ex_hash.c.

Definition at line 108 of file n_hash.h.

+ Collaboration diagram for HASH_TABLE:

Data Fields

size_t alphabet_length
 HASH_TRIE mode: size of the alphabet. More...
 
size_t alphabet_offset
 HASH_TRIE mode: offset to deduce to individual key digits. More...
 
int(* destroy_ht )(struct HASH_TABLE **table)
 destroy a hash table More...
 
int(* empty_ht )(struct HASH_TABLE *table)
 empty a hash table. More...
 
LIST ** hash_table
 HASH_CLASSIC mode: preallocated hash table. More...
 
int(* ht_get_double )(struct HASH_TABLE *table, const char *key, double *val)
 get a double from a key's node More...
 
int(* ht_get_int )(struct HASH_TABLE *table, const char *key, int *val)
 get an int from a key's node More...
 
HASH_NODE *(* ht_get_node )(struct HASH_TABLE *table, const char *key)
 get HASH_NODE at 'key' from table More...
 
int(* ht_get_ptr )(struct HASH_TABLE *table, const char *key, void **val)
 get a pointer from a key's node More...
 
int(* ht_get_string )(struct HASH_TABLE *table, const char *key, char **val)
 get a char *string from a key's node More...
 
void(* ht_print )(struct HASH_TABLE *table)
 print table More...
 
int(* ht_put_double )(struct HASH_TABLE *table, const char *key, double val)
 put a double More...
 
int(* ht_put_int )(struct HASH_TABLE *table, const char *key, int val)
 put an integer More...
 
int(* ht_put_ptr )(struct HASH_TABLE *table, const char *key, void *ptr, void(*destructor)(void *ptr))
 put a a pointer More...
 
int(* ht_put_string )(struct HASH_TABLE *table, const char *key, char *val)
 put an char *string More...
 
int(* ht_put_string_ptr )(struct HASH_TABLE *table, const char *key, char *val)
 put an char *string pointer More...
 
int(* ht_remove )(struct HASH_TABLE *table, const char *key)
 remove given's key node from the table More...
 
LIST *(* ht_search )(struct HASH_TABLE *table, int(*node_is_matching)(HASH_NODE *node))
 search elements given an expression More...
 
unsigned int mode
 hashing mode, murmurhash and classic HASH_MURMUR, or HASH_TRIE More...
 
size_t nb_keys
 total number of used keys in the table More...
 
HASH_NODEroot
 HASH_TRIE mode: Start of tree. More...
 
size_t seed
 table's seed More...
 
size_t size
 size of the hash table More...
 

Field Documentation

◆ alphabet_length

size_t HASH_TABLE::alphabet_length

HASH_TRIE mode: size of the alphabet.

Definition at line 121 of file n_hash.h.

◆ alphabet_offset

size_t HASH_TABLE::alphabet_offset

HASH_TRIE mode: offset to deduce to individual key digits.

Definition at line 123 of file n_hash.h.

◆ destroy_ht

int(* HASH_TABLE::destroy_ht) (struct HASH_TABLE **table)

destroy a hash table

Definition at line 153 of file n_hash.h.

◆ empty_ht

int(* HASH_TABLE::empty_ht) (struct HASH_TABLE *table)

empty a hash table.

char *strings are also freed

Definition at line 151 of file n_hash.h.

◆ hash_table

LIST** HASH_TABLE::hash_table

HASH_CLASSIC mode: preallocated hash table.

Definition at line 117 of file n_hash.h.

◆ ht_get_double

int(* HASH_TABLE::ht_get_double) (struct HASH_TABLE *table, const char *key, double *val)

get a double from a key's node

Definition at line 141 of file n_hash.h.

Referenced by ht_get_double().

◆ ht_get_int

int(* HASH_TABLE::ht_get_int) (struct HASH_TABLE *table, const char *key, int *val)

get an int from a key's node

Definition at line 139 of file n_hash.h.

Referenced by ht_get_int().

◆ ht_get_node

HASH_NODE *(* HASH_TABLE::ht_get_node) (struct HASH_TABLE *table, const char *key)

get HASH_NODE at 'key' from table

Definition at line 127 of file n_hash.h.

Referenced by ht_get_node().

◆ ht_get_ptr

int(* HASH_TABLE::ht_get_ptr) (struct HASH_TABLE *table, const char *key, void **val)

get a pointer from a key's node

Definition at line 143 of file n_hash.h.

◆ ht_get_string

int(* HASH_TABLE::ht_get_string) (struct HASH_TABLE *table, const char *key, char **val)

get a char *string from a key's node

Definition at line 145 of file n_hash.h.

Referenced by ht_get_string().

◆ ht_print

void(* HASH_TABLE::ht_print) (struct HASH_TABLE *table)

print table

Definition at line 155 of file n_hash.h.

Referenced by ht_print().

◆ ht_put_double

int(* HASH_TABLE::ht_put_double) (struct HASH_TABLE *table, const char *key, double val)

put a double

Definition at line 131 of file n_hash.h.

Referenced by ht_put_double().

◆ ht_put_int

int(* HASH_TABLE::ht_put_int) (struct HASH_TABLE *table, const char *key, int val)

put an integer

Definition at line 129 of file n_hash.h.

Referenced by ht_put_int().

◆ ht_put_ptr

int(* HASH_TABLE::ht_put_ptr) (struct HASH_TABLE *table, const char *key, void *ptr, void(*destructor)(void *ptr))

put a a pointer

Definition at line 133 of file n_hash.h.

Referenced by ht_put_ptr().

◆ ht_put_string

int(* HASH_TABLE::ht_put_string) (struct HASH_TABLE *table, const char *key, char *val)

put an char *string

Definition at line 135 of file n_hash.h.

Referenced by ht_put_string().

◆ ht_put_string_ptr

int(* HASH_TABLE::ht_put_string_ptr) (struct HASH_TABLE *table, const char *key, char *val)

put an char *string pointer

Definition at line 137 of file n_hash.h.

Referenced by ht_put_string_ptr().

◆ ht_remove

int(* HASH_TABLE::ht_remove) (struct HASH_TABLE *table, const char *key)

remove given's key node from the table

Definition at line 147 of file n_hash.h.

Referenced by ht_remove().

◆ ht_search

LIST *(* HASH_TABLE::ht_search) (struct HASH_TABLE *table, int(*node_is_matching)(HASH_NODE *node))

search elements given an expression

Definition at line 149 of file n_hash.h.

◆ mode

unsigned int HASH_TABLE::mode

hashing mode, murmurhash and classic HASH_MURMUR, or HASH_TRIE

Definition at line 125 of file n_hash.h.

◆ nb_keys

size_t HASH_TABLE::nb_keys

total number of used keys in the table

Definition at line 113 of file n_hash.h.

◆ root

HASH_NODE* HASH_TABLE::root

HASH_TRIE mode: Start of tree.

Definition at line 119 of file n_hash.h.

◆ seed

size_t HASH_TABLE::seed

table's seed

Definition at line 115 of file n_hash.h.

◆ size

size_t HASH_TABLE::size

size of the hash table

Definition at line 111 of file n_hash.h.

Referenced by _ht_get_node(), _ht_remove(), ht_get_node_ex(), ht_put_ptr_ex(), and ht_remove_ex().

Macro Definition Documentation

◆ HASH_CLASSIC

#define HASH_CLASSIC   128

Murmur hash using hash key string, hash key numeric value, index table with lists of elements.

Definition at line 60 of file n_hash.h.

◆ HASH_DOUBLE

#define HASH_DOUBLE   2

value of double type inside the hash node

Definition at line 52 of file n_hash.h.

◆ HASH_INT

#define HASH_INT   1

compatibility with existing rot func

compatibility with existing rot func

compatibility with existing func

missing ROTL fix 32bit

missing ROTL fix 64bit

missing ROTL constant

value of integral type inside the hash node

Definition at line 50 of file n_hash.h.

◆ HASH_PTR

#define HASH_PTR   8

value of pointer type inside the hash node

Definition at line 56 of file n_hash.h.

◆ HASH_STRING

#define HASH_STRING   4

value of char * type inside the hash node

Definition at line 54 of file n_hash.h.

◆ HASH_TRIE

#define HASH_TRIE   256

TRIE tree using hash key string.

Definition at line 62 of file n_hash.h.

◆ HASH_UNKNOWN

#define HASH_UNKNOWN   16

value of unknow type inside the hash node

Definition at line 58 of file n_hash.h.

◆ hash_val

#define hash_val (   node,
  type 
)     ( (node && node -> ptr) ? ( (type *)( ( (HASH_NODE *)node -> ptr )-> data . ptr) ) : NULL )

Cast a HASH_NODE element.

Definition at line 159 of file n_hash.h.

◆ HASH_VAL

#define HASH_VAL (   node,
  type 
)     ( (node && node -> data . ptr) ? ( (type *)node -> data . ptr ) : NULL )

Cast a HASH_NODE element.

Definition at line 191 of file n_hash.h.

◆ ht_foreach

#define ht_foreach (   __ITEM_,
  __HASH_ 
)
Value:
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 HASH_CLASSIC
Murmur hash using hash key string, hash key numeric value, index table with lists of elements.
Definition: n_hash.h:60
Structure of a generic list node.
Definition: n_list.h:27
#define LOG_ERR
error conditions
Definition: n_log.h:58

ForEach macro helper (classic / old)

Definition at line 163 of file n_hash.h.

◆ HT_FOREACH

#define HT_FOREACH (   __ITEM_,
  __HASH_,
  ... 
)
Value:
{ \
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 ; \
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 \
{ \
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 CONCAT(a, b)
Concatenate two macro.
Definition: n_common.h:450
#define HASH_TRIE
TRIE tree using hash key string.
Definition: n_hash.h:62
structure of a hash table node
Definition: n_hash.h:83

ForEach macro helper.

Examples
ex_hash.c.

Definition at line 195 of file n_hash.h.

◆ HT_FOREACH_R

#define HT_FOREACH_R (   __ITEM_,
  __HASH_,
  __ITERATOR,
  ... 
)
Value:
{ \
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 ; \
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 \
{ \
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 ); \
}

ForEach macro helper.

Examples
ex_hash.c.

Definition at line 255 of file n_hash.h.

◆ ht_foreach_r

#define ht_foreach_r (   __ITEM_,
  __HASH_,
  __ITERATOR_ 
)
Value:
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 )

ForEach macro helper, reentrant (classic / old)

Definition at line 177 of file n_hash.h.

◆ MurmurHash

#define MurmurHash (   __key,
  __len,
  __seed,
  __out 
)    MurmurHash3_x64_128( __key, __len, __seed, __out )

Murmur hash macro helper 64 bits.

Definition at line 322 of file n_hash.h.

Typedef Documentation

◆ HASH_VALUE

typedef size_t HASH_VALUE

type of a HASH_VALUE

Definition at line 65 of file n_hash.h.

Function Documentation

◆ destroy_ht()

int destroy_ht ( HASH_TABLE **  table)

empty a table and destroy it

Parameters
tabletargeted hash table
Returns
TRUE or FALSE

Definition at line 2448 of file n_hash.c.

References __n_assert.

Referenced by close_nodup_log(), destroy_config_file_section(), netw_destroy_pool(), new_ht(), and new_ht_trie().

+ Here is the caller graph for this function:

◆ empty_ht()

int empty_ht ( HASH_TABLE table)

empty a table

Parameters
tabletargeted hash table
Returns
TRUE or FALSE

Definition at line 2435 of file n_hash.c.

References __n_assert, and empty_ht().

Referenced by empty_ht(), empty_nodup_table(), new_ht(), and new_ht_trie().

+ Here is the call graph for this function:
+ Here is the caller graph for this function:

◆ 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

Parameters
tabletargeted hash table
keybudstarting characters of the keys we want
max_resultsmaximum number of matching keys in list
Returns
NULL or a LIST *list of matching HASH_NODE *nodes

Definition at line 2630 of file n_hash.c.

References __n_assert, _ht_depth_first_search(), _ht_get_node_trie(), HASH_CLASSIC, HASH_TRIE, ht_search(), list_destroy(), list_push(), LOG_ERR, n_log, and new_generic_list().

+ Here is the call graph for this function:

◆ ht_get_double()

int ht_get_double ( HASH_TABLE table,
const char *  key,
double *  val 
)

get double at 'key' from 'table'

Parameters
tabletargeted table
keykey to retrieve
valpointer to double storage
Returns
TRUE if found, else FALSE. 'val' value is preserved if no key is matching.

Definition at line 2250 of file n_hash.c.

References __n_assert, and ht_get_double.

Referenced by new_ht(), and new_ht_trie().

+ Here is the caller graph for this function:

◆ ht_get_int()

int ht_get_int ( HASH_TABLE table,
const char *  key,
int *  val 
)

get node at 'key' from 'table'

Parameters
tabletargeted table
keykey to retrieve
valpointer to int storage
Returns
TRUE if found, else FALSE. 'val' value is preserved if no key is matching.

Definition at line 2266 of file n_hash.c.

References __n_assert, and ht_get_int.

Referenced by new_ht(), and new_ht_trie().

+ Here is the caller graph for this function:

◆ ht_get_node()

HASH_NODE * ht_get_node ( HASH_TABLE table,
const char *  key 
)

get node at 'key' from 'table'

Parameters
tabletargeted table
keykey to retrieve
Returns
NULL or the matching HASH_NODE *node

Definition at line 2234 of file n_hash.c.

References __n_assert, and ht_get_node.

Referenced by _n_nodup_log(), _n_nodup_log_indexed(), check_n_log_dup(), check_n_log_dup_indexed(), and new_ht().

+ Here is the caller graph for this function:

◆ 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)

Parameters
tableTargeted hash table
hash_valueAssociated hash_value
Returns
The found node, or NULL

Definition at line 2462 of file n_hash.c.

References __n_assert, HASH_CLASSIC, list_foreach, and size.

Referenced by ht_get_ptr_ex().

+ Here is the caller graph for this function:

◆ 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_CLASSIC mode only)

Parameters
tabletargeted table
Returns
FALSE or optimal table size

Definition at line 2765 of file n_hash.c.

References __n_assert, is_prime(), and next_prime().

Referenced by ht_optimize().

+ Here is the call graph for this function:
+ Here is the caller graph for this function:

◆ ht_get_ptr()

int ht_get_ptr ( HASH_TABLE table,
const char *  key,
void **  val 
)

get pointer at 'key' from 'table'

Parameters
tabletargeted table
keykey to retrieve
valpointer to pointer storage
Returns
TRUE if found, else FALSE. 'val' value is preserved if no key is matching.

Definition at line 2282 of file n_hash.c.

References __n_assert, and ht_get_ptr().

Referenced by get_config_section_value(), get_nb_config_file_sections_entries(), ht_get_ptr(), load_config_file(), netw_pool_add(), new_ht(), and new_ht_trie().

+ Here is the call graph for this function:
+ Here is the caller graph for this function:

◆ 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.

Leave val untouched if key is not found. (HASH_CLASSIC only)

Parameters
tableTargeted hash table
hash_valuekey pre computed numeric hash value
valA pointer to an empty pointer store
Returns
TRUE or FALSE.

Definition at line 2496 of file n_hash.c.

References __n_assert, HASH_CLASSIC, HASH_PTR, ht_get_node_ex(), ht_node_type(), LOG_ERR, and n_log.

+ Here is the call graph for this function:

◆ ht_get_string()

int ht_get_string ( HASH_TABLE table,
const char *  key,
char **  val 
)

get string at 'key' from 'table'

Parameters
tabletargeted table
keykey to retrieve
valpointer to string storage
Returns
TRUE if found, else FALSE. 'val' value is preserved if no key is matching.

Definition at line 2298 of file n_hash.c.

References __n_assert, and ht_get_string.

Referenced by new_ht(), and new_ht_trie().

+ Here is the caller graph for this function:

◆ ht_get_table_collision_percentage()

int ht_get_table_collision_percentage ( HASH_TABLE table)

get table collision percentage (HASH_CLASSIC mode only)

Parameters
tabletargeted table
Returns
table collision percentage or FALSE

Definition at line 2738 of file n_hash.c.

References __n_assert, and HASH_CLASSIC.

Referenced by ht_optimize().

+ Here is the caller graph for this function:

◆ ht_node_type()

char * ht_node_type ( HASH_NODE node)

get the type of a node , text version

Parameters
nodenode to check
Returns
NULL or the associated node type

Definition at line 1422 of file n_hash.c.

References __n_assert, and HASH_UNKNOWN.

Referenced by _ht_get_double(), _ht_get_double_trie(), _ht_get_int(), _ht_get_int_trie(), _ht_get_ptr(), _ht_get_ptr_trie(), _ht_get_string(), _ht_get_string_trie(), _ht_put_double(), _ht_put_int(), _ht_put_ptr(), _ht_put_string(), _ht_put_string_ptr(), ht_get_ptr_ex(), and ht_put_ptr_ex().

+ Here is the caller graph for this function:

◆ ht_optimize()

int ht_optimize ( HASH_TABLE **  table)

try an automatic optimization of the table

Parameters
tabletargeted table
Returns
TRUE or FALSE and set table to NULL

Definition at line 2881 of file n_hash.c.

References __n_assert, ht_get_optimal_size(), ht_get_table_collision_percentage(), and ht_resize().

+ Here is the call graph for this function:

◆ ht_print()

void ht_print ( HASH_TABLE table)

print contents of table

Parameters
tabletargeted hash table

Definition at line 2407 of file n_hash.c.

References __n_assert, and ht_print.

Referenced by new_ht(), and new_ht_trie().

+ Here is the caller graph for this function:

◆ 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

Parameters
tabletargeted table
keykey to retrieve
valuedouble value to put
Returns
TRUE or FALSE

Definition at line 2314 of file n_hash.c.

References __n_assert, and ht_put_double.

Referenced by new_ht(), and new_ht_trie().

+ Here is the caller graph for this function:

◆ 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

Parameters
tabletargeted hash table
keyassociated value's key
valueintegral value to put
Returns
TRUE or FALSE

Definition at line 2330 of file n_hash.c.

References __n_assert, and ht_put_int.

Referenced by new_ht(), and new_ht_trie().

+ Here is the caller graph for this function:

◆ ht_put_ptr()

int ht_put_ptr ( HASH_TABLE table,
const char *  key,
void *  ptr,
void(*)(void *ptr)  destructor 
)

put a pointer to the string value with given key in the targeted hash table

Parameters
tabletargeted hash table
keyassociated value's key
ptrpointer value to put
destructorthe destructor func for ptr or NULL
Returns
TRUE or FALSE

Definition at line 2347 of file n_hash.c.

References __n_assert, and ht_put_ptr.

Referenced by load_config_file(), netw_pool_add(), new_ht(), and new_ht_trie().

+ Here is the caller graph for this function:

◆ ht_put_ptr_ex()

int ht_put_ptr_ex ( HASH_TABLE table,
HASH_VALUE  hash_value,
void *  val,
void(*)(void *ptr)  destructor 
)

put a pointer value with given key in the targeted hash table (HASH_CLASSIC only)

Parameters
tableTargeted hash table
hash_valuenumerical hash key
valpointer value to put
destructorPointer to the ptr type destructor function. Leave to NULL if there isn't
Returns
TRUE or FALSE

Definition at line 2526 of file n_hash.c.

References __n_assert, _ht_node_destroy(), HASH_CLASSIC, HASH_PTR, ht_node_type(), list_foreach, list_push(), LOG_ERR, Malloc, n_log, and size.

+ Here is the call graph for this function:

◆ 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

Parameters
tabletargeted hash table
keyassociated value's key
stringstring value to put (copy)
Returns
TRUE or FALSE

Definition at line 2363 of file n_hash.c.

References __n_assert, and ht_put_string.

Referenced by _n_nodup_log(), _n_nodup_log_indexed(), new_ht(), and new_ht_trie().

+ Here is the caller graph for this function:

◆ 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

Parameters
tabletargeted hash table
keyassociated value's key
stringstring value to put (pointer)
Returns
TRUE or FALSE

Definition at line 2379 of file n_hash.c.

References __n_assert, and ht_put_string_ptr.

Referenced by new_ht(), and new_ht_trie().

+ Here is the caller graph for this function:

◆ ht_remove()

int ht_remove ( HASH_TABLE table,
const char *  key 
)

remove and delete node at key in table

Parameters
tabletargeted hash table
keykey of node to destroy
Returns
TRUE or FALSE

Definition at line 2394 of file n_hash.c.

References __n_assert, and ht_remove.

Referenced by netw_pool_remove(), new_ht(), and new_ht_trie().

+ Here is the caller graph for this function:

◆ ht_remove_ex()

int ht_remove_ex ( HASH_TABLE table,
HASH_VALUE  hash_value 
)

Remove a key from a hash table (HASH_CLASSIC only)

Parameters
tableTargeted hash table
hash_valuekey pre computed numeric hash value
Returns
TRUE or FALSE.

Definition at line 2582 of file n_hash.c.

References __n_assert, _ht_node_destroy(), HASH_CLASSIC, list_foreach, LOG_ERR, n_log, remove_list_node, and size.

+ Here is the call graph for this function:

◆ ht_resize()

int ht_resize ( HASH_TABLE **  table,
size_t  size 
)

rehash table according to size (HASH_CLASSIC mode only)

Parameters
tabletargeted table
sizenew hash table size
Returns
TRUE or FALSE

Definition at line 2785 of file n_hash.c.

References __n_assert, Free, HT_FOREACH, list_destroy(), list_node_push(), list_node_shift(), LOG_ERR, n_log, new_generic_list(), and Realloc.

Referenced by ht_optimize().

+ Here is the call graph for this function:
+ Here is the caller graph for this function:

◆ ht_search()

LIST * ht_search ( HASH_TABLE table,
int(*)(HASH_NODE *node)  node_is_matching 
)

seach table for matching nodes

Parameters
tabletargeted hash table
node_is_matchingmatching function
Returns
NULL or a LIST *list of HASH_NODE *nodes

Definition at line 2422 of file n_hash.c.

References __n_assert, and ht_search().

Referenced by ht_get_completion_list(), ht_search(), new_ht(), and new_ht_trie().

+ Here is the call graph for this function:
+ Here is the caller graph for this function:

◆ is_prime()

int is_prime ( int  nb)

test if number is a prime number or not

Parameters
nbnumber to test
Returns
TRUE or FALSE

Definition at line 2690 of file n_hash.c.

Referenced by ht_get_optimal_size(), and next_prime().

+ Here is the caller graph for this function:

◆ 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.

The author hereby disclaims copyright to this source code. Note - The x86 and x64 versions do not produce the same results, as the algorithms are optimized for their respective platforms. You can still compile and run any of them on any platform, but your performance with the non-native version will be less than optimal.

Parameters
keychar *string as the key
lensize of the key
seedseed value for murmur hash
outgenerated hash

Definition at line 1294 of file n_hash.c.

References BIG_CONSTANT, FALL_THROUGH, fmix64(), getblock64(), and ROTL64.

+ Here is the call graph for this function:

◆ 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.

The author hereby disclaims copyright to this source code. Note - The x86 and x64 versions do not produce the same results, as the algorithms are optimized for their respective platforms. You can still compile and run any of them on any platform, but your performance with the non-native version will be less than optimal.

Parameters
keychar *string as the key
lensize of the key
seedseed value for murmur hash
outgenerated hash

Definition at line 1117 of file n_hash.c.

References FALL_THROUGH, fmix32(), getblock32(), and ROTL32.

+ Here is the call graph for this function:

◆ 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.

The author hereby disclaims copyright to this source code. Note - The x86 and x64 versions do not produce the same results, as the algorithms are optimized for their respective platforms. You can still compile and run any of them on any platform, but your performance with the non-native version will be less than optimal.

Parameters
keychar *string as the key
lensize of the key
seedseed value for murmur hash
outgenerated hash

Definition at line 1047 of file n_hash.c.

References FALL_THROUGH, fmix32(), getblock32(), and ROTL32.

+ Here is the call graph for this function:

◆ new_ht()

HASH_TABLE * new_ht ( size_t  size)

Create a hash table with the given size.

Parameters
sizeSize of the root hash node table
Returns
NULL or the new allocated hash table

Definition at line 2167 of file n_hash.c.

References __n_assert, _destroy_ht(), _empty_ht(), _ht_get_double(), _ht_get_int(), _ht_get_node(), _ht_get_ptr(), _ht_get_string(), _ht_print(), _ht_put_double(), _ht_put_int(), _ht_put_ptr(), _ht_put_string(), _ht_put_string_ptr(), _ht_remove(), _ht_search(), destroy_ht(), empty_ht(), Free, HASH_CLASSIC, ht_get_double(), ht_get_int(), ht_get_node(), ht_get_ptr(), ht_get_string(), ht_print(), ht_put_double(), ht_put_int(), ht_put_ptr(), ht_put_string(), ht_put_string_ptr(), ht_remove(), ht_search(), list_destroy(), LOG_ERR, Malloc, n_log, and new_generic_list().

Referenced by init_nodup_log(), load_config_file(), and netw_new_pool().

+ Here is the call graph for this function:
+ Here is the caller graph for this function:

◆ 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

Parameters
alphabet_lengthof the alphabet
alphabet_offsetoffset of each character in a key (i.e: to have 'a->z' with 'a' starting at zero, offset must be 32.
Returns
NULL or the new allocated hash table

Definition at line 2123 of file n_hash.c.

References __n_assert, _destroy_ht_trie(), _empty_ht_trie(), _ht_get_double_trie(), _ht_get_int_trie(), _ht_get_ptr_trie(), _ht_get_string_trie(), _ht_new_node_trie(), _ht_print_trie(), _ht_put_double_trie(), _ht_put_int_trie(), _ht_put_ptr_trie(), _ht_put_string_ptr_trie(), _ht_put_string_trie(), _ht_remove_trie(), _ht_search_trie(), destroy_ht(), empty_ht(), HASH_TRIE, ht_get_double(), ht_get_int(), ht_get_ptr(), ht_get_string(), ht_print(), ht_put_double(), ht_put_int(), ht_put_ptr(), ht_put_string(), ht_put_string_ptr(), ht_remove(), ht_search(), LOG_ERR, Malloc, and n_log.

+ Here is the call graph for this function:

◆ next_prime()

int next_prime ( int  nb)

compute next prime number after nb

Parameters
nbnumber to test
Returns
next prime number after nb or FALSE

Definition at line 2715 of file n_hash.c.

References is_prime(), and next_prime().

Referenced by ht_get_optimal_size(), and next_prime().

+ Here is the call graph for this function:
+ Here is the caller graph for this function: