Nilorea Library
C utilities for networking, threading, graphics
Loading...
Searching...
No Matches
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.
#define HASH_DOUBLE   2
 value of double type inside the hash node
#define HASH_INT   1
 compatibility with existing rot func
#define HASH_INT_TYPE   int64_t
 type of a HASH_INT in 64 bits
#define HASH_PTR   8
 value of pointer type inside the hash node
#define HASH_STRING   4
 value of char * type inside the hash node
#define HASH_TRIE   256
 TRIE tree using hash key string.
#define HASH_UNKNOWN   16
 value of unknow type inside the hash node
#define HASH_VAL(node, type)
 Cast a HASH_NODE element.
#define hash_val(node, type)
 Cast a HASH_NODE element.
#define HT_FOREACH(__ITEM_, __HASH_, ...)
 ForEach macro helper.
#define ht_foreach(__ITEM_, __HASH_)
 ForEach macro helper (classic / old).
#define HT_FOREACH_R(__ITEM_, __HASH_, __ITERATOR, ...)
 ForEach macro helper.
#define ht_foreach_r(__ITEM_, __HASH_, __ITERATOR_)
 ForEach macro helper, reentrant (classic / old).
#define MurmurHash(__key, __len, __seed, __out)
 Murmur hash macro helper 64 bits.

Typedefs

typedef size_t HASH_VALUE
 type of a HASH_VALUE

Functions

int destroy_ht (HASH_TABLE **table)
 destroy a hash table and free all resources
int empty_ht (HASH_TABLE *table)
 empty a hash table, freeing all nodes
HASH_TABLE * ht_duplicate (HASH_TABLE *table)
 duplicate a hash table
LIST * ht_get_completion_list (HASH_TABLE *table, const char *keybud, size_t max_results)
 get a list of key completions matching the given prefix
int ht_get_double (HASH_TABLE *table, const char *key, double *val)
 get a double value from the hash table by key
int ht_get_int (HASH_TABLE *table, const char *key, int64_t *val)
 get an integer value from the hash table by key
HASH_NODE * ht_get_node (HASH_TABLE *table, const char *key)
 get the HASH_NODE associated with the given key
HASH_NODE * ht_get_node_ex (HASH_TABLE *table, HASH_VALUE hash_value)
 get a HASH_NODE by numeric hash value
size_t ht_get_optimal_size (HASH_TABLE *table)
 compute the optimal size for the hash table
int ht_get_ptr (HASH_TABLE *table, const char *key, void **val)
 get a pointer value from the hash table by key
int ht_get_ptr_ex (HASH_TABLE *table, HASH_VALUE hash_value, void **val)
 get a pointer value by numeric hash value
int ht_get_string (HASH_TABLE *table, const char *key, char **val)
 get a string value from the hash table by key
int ht_get_table_collision_percentage (HASH_TABLE *table)
 get the collision percentage of the hash table
char * ht_node_type (const HASH_NODE *node)
 return the type of a hash node as a string
int ht_optimize (HASH_TABLE **table)
 optimize a hash table by resizing to the optimal size
void ht_print (HASH_TABLE *table)
 print the contents of a hash table
int ht_put_double (HASH_TABLE *table, const char *key, double value)
 put a double value into the hash table
int ht_put_int (HASH_TABLE *table, const char *key, int64_t value)
 put an integer value into the hash table
int ht_put_ptr (HASH_TABLE *table, const char *key, void *ptr, void(*destructor)(void *ptr), void *(*duplicator)(void *ptr))
 put a pointer value into the hash table with destructor and duplicator
int ht_put_ptr_ex (HASH_TABLE *table, HASH_VALUE hash_value, void *val, void(*destructor)(void *ptr), void *(*duplicator)(void *ptr))
 put a pointer value by numeric hash value
int ht_put_string (HASH_TABLE *table, const char *key, char *string)
 put a string value (duplicated) into the hash table
int ht_put_string_ptr (HASH_TABLE *table, const char *key, char *string)
 put a string pointer into the hash table without copying
int ht_remove (HASH_TABLE *table, const char *key)
 remove a node from the hash table by key
int ht_remove_ex (HASH_TABLE *table, HASH_VALUE hash_value)
 remove a node by numeric hash value
int ht_resize (HASH_TABLE **table, size_t size)
 resize a hash table to the given size
LIST * ht_search (HASH_TABLE *table, int(*node_is_matching)(HASH_NODE *node))
 search the hash table for nodes matching a predicate
int is_prime (size_t nb)
 check if a number is prime
void MurmurHash3_x64_128 (const void *key, const size_t len, const uint64_t seed, void *out)
 compute a 128-bit MurmurHash3 hash for x64
void MurmurHash3_x86_128 (const void *key, const size_t len, const uint32_t seed, void *out)
 compute a 128-bit MurmurHash3 hash for x86
void MurmurHash3_x86_32 (const void *key, const size_t len, const uint32_t seed, void *out)
 compute a 32-bit MurmurHash3 hash
HASH_TABLE * new_ht (size_t size)
 create a new classic hash table of the given size
HASH_TABLE * new_ht_trie (size_t alphabet_size, size_t alphabet_offset)
 create a new trie hash table with the given alphabet size and offset
size_t next_prime (size_t nb)
 return the next prime number greater than or equal to nb

Detailed Description


Data Structure Documentation

◆ HASH_DATA

union HASH_DATA

union of the possibles data values of a node

Definition at line 100 of file n_hash.h.

Collaboration diagram for HASH_DATA:
Data Fields
double fval double type
int64_t 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 112 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.
struct HASH_NODE ** children HASH_TRIE mode: pointers to children.
union HASH_DATA data data inside the node
void(*)(void *ptr) destroy_func destroy_func
void *(*)(void *ptr) duplicate_func duplicator_func
HASH_VALUE hash_value numeric key of the node if any, else < 0
int is_leaf HASH_TRIE mode: does it have a value.
char * key string key of the node if any, else NULL
char key_id key id of the node if any
int need_rehash flag to mark a node for rehash
int type type of the node

◆ HASH_TABLE

struct HASH_TABLE

structure of a hash table

Examples
ex_gui_dictionary.c, ex_hash.c, ex_network_ssl.c, and ex_network_ssl_hardened.c.

Definition at line 138 of file n_hash.h.

Collaboration diagram for HASH_TABLE:
Data Fields
size_t alphabet_length HASH_TRIE mode: size of the alphabet.
size_t alphabet_offset HASH_TRIE mode: offset to deduce to individual key digits.
int(*)(struct HASH_TABLE **table) destroy_ht destroy a hash table
int(*)(struct HASH_TABLE *table) empty_ht empty a hash table.

char *strings are also freed

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

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 80 of file n_hash.h.

Referenced by ht_duplicate(), ht_get_completion_list(), ht_get_node_ex(), ht_get_optimal_size(), ht_get_ptr_ex(), ht_get_table_collision_percentage(), ht_optimize(), ht_put_ptr_ex(), ht_remove_ex(), ht_resize(), and new_ht().

◆ HASH_DOUBLE

#define HASH_DOUBLE   2

value of double type inside the hash node

Definition at line 72 of file n_hash.h.

Referenced by _ht_get_double(), _ht_get_double_trie(), _ht_new_double_node(), _ht_print_trie_helper(), _ht_put_double(), _ht_put_double_trie(), ht_duplicate(), and ht_node_type().

◆ 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 70 of file n_hash.h.

Referenced by _ht_get_int(), _ht_get_int_trie(), _ht_new_int_node(), _ht_print_trie_helper(), _ht_put_int(), _ht_put_int_trie(), ht_duplicate(), and ht_node_type().

◆ HASH_INT_TYPE

#define HASH_INT_TYPE   int64_t

type of a HASH_INT in 64 bits

Examples
ex_hash.c.

Definition at line 93 of file n_hash.h.

Referenced by _ht_get_int(), _ht_get_int_trie(), _ht_new_int_node(), _ht_put_int(), _ht_put_int_trie(), ht_get_int(), ht_put_int(), and main().

◆ HASH_PTR

#define HASH_PTR   8

◆ HASH_STRING

◆ HASH_TRIE

#define HASH_TRIE   256

TRIE tree using hash key string.

Definition at line 82 of file n_hash.h.

Referenced by ht_get_completion_list(), and new_ht_trie().

◆ HASH_UNKNOWN

#define HASH_UNKNOWN   16

value of unknow type inside the hash node

Definition at line 78 of file n_hash.h.

◆ HASH_VAL

#define HASH_VAL ( node,
type )
Value:
((node && node->data.ptr) ? ((type*)node->data.ptr) : NULL)
static void type(N_GUI_CTX *gui, const char *s)
Type a whole string into whatever has focus.

Cast a HASH_NODE element.

Definition at line 212 of file n_hash.h.

◆ hash_val

#define hash_val ( node,
type )
Value:
((node && node->ptr) ? ((type*)(((HASH_NODE*)node->ptr)->data.ptr)) : NULL)
structure of a hash table node
Definition n_hash.h:112

Cast a HASH_NODE element.

Definition at line 188 of file n_hash.h.

Referenced by netw_pool_broadcast().

◆ 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; \
__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 CONCAT(__ht_node_trie_func_it, __LINE__) = 0; CONCAT(__ht_node_trie_func_it, __LINE__) < __ITEM_->alphabet_length; CONCAT(__ht_node_trie_func_it, __LINE__)++) { \
if (CONCAT(__ht_node_trie_func_macro, __LINE__)(__ITEM_->children[CONCAT(__ht_node_trie_func_it, __LINE__)]) == 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:456
#define HASH_CLASSIC
Murmur hash using hash key string, hash key numeric value, index table with lists of elements.
Definition n_hash.h:80
#define HASH_TRIE
TRIE tree using hash key string.
Definition n_hash.h:82
struct LIST_NODE * next
pointer to the next node
Definition n_list.h:52
Structure of a generic list node.
Definition n_list.h:44
#define LOG_ERR
error conditions
Definition n_log.h:100

ForEach macro helper.

Examples
ex_gui_network.c, ex_hash.c, ex_network_ssl.c, and ex_network_ssl_hardened.c.

Definition at line 216 of file n_hash.h.

Referenced by handle_request(), main(), main(), and refresh_clients_list().

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

ForEach macro helper (classic / old).

Definition at line 192 of file n_hash.h.

Referenced by _ht_print(), _ht_search(), ht_duplicate(), ht_get_completion_list(), ht_resize(), and netw_pool_broadcast().

◆ 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; \
LIST_NODE* CONCAT(__ht_list_node_r, __LINE__) = NULL; \
for (size_t __ITERATOR = 0; __ITERATOR < __HASH_->size; __ITERATOR++) { \
for (CONCAT(__ht_list_node_r, __LINE__) = __HASH_->hash_table[__ITERATOR]->start; CONCAT(__ht_list_node_r, __LINE__) != NULL; CONCAT(__ht_list_node_r, __LINE__) = CONCAT(__ht_list_node_r, __LINE__)->next) { \
HASH_NODE* __ITEM_ = (HASH_NODE*)CONCAT(__ht_list_node_r, __LINE__)->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); \
}

ForEach macro helper.

Examples
ex_hash.c.

Definition at line 262 of file n_hash.h.

Referenced by main().

◆ 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 202 of file n_hash.h.

◆ MurmurHash

#define MurmurHash ( __key,
__len,
__seed,
__out )
Value:
MurmurHash3_x64_128(__key, __len, __seed, __out)
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:1215

Murmur hash macro helper 64 bits.

Definition at line 91 of file n_hash.h.

Referenced by _ht_hash_value().

Typedef Documentation

◆ HASH_VALUE

typedef size_t HASH_VALUE

type of a HASH_VALUE

Definition at line 97 of file n_hash.h.

Function Documentation

◆ destroy_ht()

int destroy_ht ( HASH_TABLE ** table)

destroy a hash table and free all resources

destroy a hash table and free all resources

Parameters
tabletargeted hash table
Returns
TRUE or FALSE

Definition at line 2349 of file n_hash.c.

References __n_assert.

Referenced by close_nodup_log(), destroy_config_file_section(), handle_request(), ht_duplicate(), main(), main(), n_gui_destroy_ctx(), and netw_destroy_pool().

Here is the caller graph for this function:

◆ empty_ht()

int empty_ht ( HASH_TABLE * table)

empty a hash table, freeing all nodes

empty a hash table, freeing all nodes

Parameters
tabletargeted hash table
Returns
TRUE or FALSE

Definition at line 2339 of file n_hash.c.

References __n_assert, and HASH_TABLE::empty_ht.

Referenced by empty_nodup_table(), and main().

Here is the caller graph for this function:

◆ ht_duplicate()

HASH_TABLE * ht_duplicate ( HASH_TABLE * table)

duplicate a hash table

duplicate a hash table

Parameters
tablethe HASH_TABLE *table to duplicate
Returns
NULL or and allocated duplicated HASH_TABLE

Definition at line 2757 of file n_hash.c.

References __n_assert, HASH_NODE::data, HASH_NODE::destroy_func, destroy_ht(), HASH_NODE::duplicate_func, HASH_DATA::fval, HASH_CLASSIC, HASH_DOUBLE, HASH_INT, HASH_PTR, HASH_STRING, ht_foreach, ht_put_double(), ht_put_int(), ht_put_ptr(), ht_put_string(), HASH_DATA::ival, HASH_NODE::key, LOG_ERR, HASH_TABLE::mode, n_log, new_ht(), HASH_DATA::ptr, HASH_TABLE::size, HASH_DATA::string, and HASH_NODE::type.

Referenced by main().

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 a list of key completions matching the given prefix

get a list of key completions matching the given prefix

Parameters
tabletargeted hash table
keybudstarting characters of the keys we want
max_resultsmaximum number of matching keys in list. From UNLIMITED_LIST_ITEMS (0) to MAX_LIST_ITEMS (SIZE_MAX).
Returns
NULL or a LIST *list of matching HASH_NODE *nodes

Definition at line 2506 of file n_hash.c.

References __n_assert, _ht_depth_first_search(), _ht_get_node_trie(), HASH_TABLE::alphabet_length, HASH_TABLE::alphabet_offset, HASH_NODE::children, Free, HASH_CLASSIC, HASH_TRIE, ht_foreach, HASH_NODE::key, key, list_destroy(), list_push(), LOG_ERR, max_results, HASH_TABLE::mode, n_log, LIST::nb_items, new_generic_list(), and HASH_TABLE::root.

Referenced by main(), and update_completion().

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

◆ ht_get_double()

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

get a double value from the hash table by key

get a double value from the hash table by key

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 2189 of file n_hash.c.

References __n_assert, HASH_TABLE::ht_get_double, and key.

Referenced by main().

Here is the caller graph for this function:

◆ ht_get_int()

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

get an integer value from the hash table by key

get an integer value from the hash table by key

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 2202 of file n_hash.c.

References __n_assert, HASH_INT_TYPE, HASH_TABLE::ht_get_int, and key.

Referenced by main().

Here is the caller graph for this function:

◆ ht_get_node()

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

get the HASH_NODE associated with the given key

get the HASH_NODE associated with the given key

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

Definition at line 2176 of file n_hash.c.

References __n_assert, HASH_TABLE::ht_get_node, and key.

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

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 )

get a HASH_NODE by numeric hash value

get a HASH_NODE by numeric hash value

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

Definition at line 2360 of file n_hash.c.

References __n_assert, HASH_CLASSIC, HASH_TABLE::hash_table, HASH_NODE::hash_value, list_foreach, HASH_TABLE::mode, HASH_TABLE::size, and LIST::start.

Referenced by ht_get_ptr_ex().

Here is the caller graph for this function:

◆ ht_get_optimal_size()

size_t ht_get_optimal_size ( HASH_TABLE * table)

compute the optimal size for the hash table

compute the optimal size for the hash table

Parameters
tabletargeted table
Returns
0 or optimal table size

Definition at line 2616 of file n_hash.c.

References __n_assert, HASH_CLASSIC, is_prime(), LOG_ERR, HASH_TABLE::mode, n_log, HASH_TABLE::nb_keys, and next_prime().

Referenced by ht_optimize(), and main().

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 a pointer value from the hash table by key

get a pointer value from the hash table by key

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 2215 of file n_hash.c.

References __n_assert, HASH_TABLE::ht_get_ptr, and key.

Referenced by get_config_section_value(), get_nb_config_file_sections_entries(), load_config_file(), main(), main(), n_gui_get_widget(), netw_pool_add(), and update_definitions().

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 )

get a pointer value by numeric hash value

get a pointer value by numeric hash value

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 2385 of file n_hash.c.

References __n_assert, HASH_NODE::data, HASH_CLASSIC, HASH_PTR, ht_get_node_ex(), ht_node_type(), LOG_ERR, HASH_TABLE::mode, n_log, HASH_DATA::ptr, and HASH_NODE::type.

Here is the call graph for this function:

◆ ht_get_string()

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

get a string value from the hash table by key

get a string value from the hash table by key

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 2228 of file n_hash.c.

References __n_assert, HASH_TABLE::ht_get_string, and key.

Referenced by main(), and n_str_template_expand().

Here is the caller graph for this function:

◆ ht_get_table_collision_percentage()

int ht_get_table_collision_percentage ( HASH_TABLE * table)

get the collision percentage of the hash table

get the collision percentage of the hash table

Parameters
tabletargeted table
Returns
table collision percentage or FALSE

Definition at line 2592 of file n_hash.c.

References __n_assert, HASH_CLASSIC, HASH_TABLE::hash_table, LOG_ERR, HASH_TABLE::mode, n_log, LIST::nb_items, and HASH_TABLE::size.

Referenced by ht_optimize(), and main().

Here is the caller graph for this function:

◆ ht_node_type()

char * ht_node_type ( const HASH_NODE * node)

return the type of a hash node as a string

return the type of a hash node as a string

Parameters
nodenode to check
Returns
"HASH_INT", "HASH_DOUBLE", "HASH_STRING", "HASH_PTR", "HASH_UNKNOWN", "NULL_NODE"

Definition at line 1337 of file n_hash.c.

References __n_assert, HASH_DOUBLE, HASH_INT, HASH_PTR, HASH_STRING, and HASH_NODE::type.

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)

optimize a hash table by resizing to the optimal size

optimize a hash table by resizing to the optimal size

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

Definition at line 2723 of file n_hash.c.

References __n_assert, HASH_CLASSIC, ht_get_optimal_size(), ht_get_table_collision_percentage(), ht_resize(), LOG_ERR, and n_log.

Referenced by main().

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

◆ ht_print()

void ht_print ( HASH_TABLE * table)

print the contents of a hash table

print the contents of a hash table

Parameters
tabletargeted hash table

Definition at line 2317 of file n_hash.c.

References __n_assert, and HASH_TABLE::ht_print.

◆ ht_put_double()

int ht_put_double ( HASH_TABLE * table,
const char * key,
double value )

put a double value into the hash table

put a double value into the hash table

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

Definition at line 2241 of file n_hash.c.

References __n_assert, HASH_TABLE::ht_put_double, and key.

Referenced by ht_duplicate(), and main().

Here is the caller graph for this function:

◆ ht_put_int()

int ht_put_int ( HASH_TABLE * table,
const char * key,
int64_t value )

put an integer value into the hash table

put an integer value into the hash table

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

Definition at line 2254 of file n_hash.c.

References __n_assert, HASH_INT_TYPE, HASH_TABLE::ht_put_int, and key.

Referenced by ht_duplicate(), and main().

Here is the caller graph for this function:

◆ ht_put_ptr()

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

put a pointer value into the hash table with destructor and duplicator

put a pointer value into the hash table with destructor and duplicator

Parameters
tabletargeted hash table
keykey of the entry
ptrpointer value to put
destructorPointer to the ptr type destructor function. Leave to NULL if there isn't
duplicatorPointer to the ptr type duplicator function. Leave to NULL if there isn't
Returns
TRUE or FALSE

Definition at line 2269 of file n_hash.c.

References __n_assert, HASH_TABLE::ht_put_ptr, and key.

Referenced by _register_widget(), ht_duplicate(), load_config_file(), main(), main(), and netw_pool_add().

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(* destructor )(void *ptr),
void *(* duplicator )(void *ptr) )

put a pointer value by numeric hash value

put a pointer value by numeric hash value

Parameters
tabletargeted hash table
hash_valueprecomputed hash value for the key
valpointer value to put
destructorPointer to the ptr type destructor function. Leave to NULL if there isn't
duplicatorPointer to the ptr type duplicator function. Leave to NULL if there isn't
Returns
TRUE or FALSE

Definition at line 2412 of file n_hash.c.

References __n_assert, _ht_node_destroy(), HASH_NODE::data, HASH_NODE::destroy_func, HASH_NODE::duplicate_func, HASH_CLASSIC, HASH_PTR, HASH_TABLE::hash_table, HASH_NODE::hash_value, ht_node_type(), HASH_NODE::key, list_foreach, list_push(), LOG_ERR, Malloc, HASH_TABLE::mode, n_log, HASH_TABLE::nb_keys, HASH_DATA::ptr, HASH_TABLE::size, and HASH_NODE::type.

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 (duplicated) into the hash table

put a string value (duplicated) into the hash table

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

Definition at line 2282 of file n_hash.c.

References __n_assert, HASH_TABLE::ht_put_string, and key.

Referenced by _n_nodup_log(), _n_nodup_log_indexed(), ht_duplicate(), main(), and netw_parse_post_data().

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 pointer into the hash table without copying

put a string pointer into the hash table without copying

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

Definition at line 2295 of file n_hash.c.

References __n_assert, HASH_TABLE::ht_put_string_ptr, and key.

◆ ht_remove()

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

remove a node from the hash table by key

remove a node from the hash table by key

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

Definition at line 2307 of file n_hash.c.

References __n_assert, HASH_TABLE::ht_remove, and key.

Referenced by main(), and netw_pool_remove().

Here is the caller graph for this function:

◆ ht_remove_ex()

int ht_remove_ex ( HASH_TABLE * table,
HASH_VALUE hash_value )

remove a node by numeric hash value

remove a node by numeric hash value

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

Definition at line 2465 of file n_hash.c.

References __n_assert, _ht_node_destroy(), HASH_CLASSIC, HASH_TABLE::hash_table, HASH_NODE::hash_value, list_foreach, LOG_ERR, HASH_TABLE::mode, n_log, HASH_TABLE::nb_keys, remove_list_node, HASH_TABLE::size, and LIST::start.

Here is the call graph for this function:

◆ ht_resize()

int ht_resize ( HASH_TABLE ** table,
size_t size )

resize a hash table to the given size

resize a hash table to the given size

Parameters
tabletargeted table
sizenew hash table size
Returns
TRUE or FALSE

Definition at line 2635 of file n_hash.c.

References __n_assert, HASH_CLASSIC, HASH_NODE::hash_value, ht_foreach, list_destroy(), list_node_push(), list_node_shift(), LOG_ERR, MAX_LIST_ITEMS, n_log, HASH_NODE::need_rehash, new_generic_list(), LIST_NODE::next, LIST_NODE::prev, and Realloc.

Referenced by ht_optimize(), and main().

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(* node_is_matching )(HASH_NODE *node) )

search the hash table for nodes matching a predicate

search the hash table for nodes matching a predicate

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

Definition at line 2329 of file n_hash.c.

References __n_assert, and HASH_TABLE::ht_search.

Referenced by main().

Here is the caller graph for this function:

◆ is_prime()

int is_prime ( size_t nb)

check if a number is prime

check if a number is prime

Parameters
nbnumber to test
Returns
TRUE or FALSE

Definition at line 2553 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 )

compute a 128-bit MurmurHash3 hash for x64

compute a 128-bit MurmurHash3 hash for x64

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 1215 of file n_hash.c.

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

Referenced by n_disk_cache_path().

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

◆ MurmurHash3_x86_128()

void MurmurHash3_x86_128 ( const void * key,
const size_t len,
const uint32_t seed,
void * out )

compute a 128-bit MurmurHash3 hash for x86

compute a 128-bit MurmurHash3 hash for x86

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(), key, and ROTL32.

Here is the call graph for this function:

◆ MurmurHash3_x86_32()

void MurmurHash3_x86_32 ( const void * key,
const size_t len,
const uint32_t seed,
void * out )

compute a 32-bit MurmurHash3 hash

compute a 32-bit MurmurHash3 hash

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 989 of file n_hash.c.

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

Here is the call graph for this function:

◆ new_ht()

◆ new_ht_trie()

HASH_TABLE * new_ht_trie ( size_t alphabet_length,
size_t alphabet_offset )

create a new trie hash table with the given alphabet size and offset

create a new trie hash table with the given alphabet size and 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 2013 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(), HASH_TABLE::alphabet_length, HASH_TABLE::alphabet_offset, HASH_TABLE::destroy_ht, HASH_TABLE::empty_ht, Free, HASH_TABLE::hash_table, HASH_TRIE, HASH_TABLE::ht_get_double, HASH_TABLE::ht_get_int, HASH_TABLE::ht_get_ptr, HASH_TABLE::ht_get_string, HASH_TABLE::ht_print, HASH_TABLE::ht_put_double, HASH_TABLE::ht_put_int, HASH_TABLE::ht_put_ptr, HASH_TABLE::ht_put_string, HASH_TABLE::ht_put_string_ptr, HASH_TABLE::ht_remove, HASH_TABLE::ht_search, LOG_ERR, Malloc, HASH_TABLE::mode, n_log, HASH_TABLE::nb_keys, HASH_TABLE::root, HASH_TABLE::seed, and HASH_TABLE::size.

Referenced by main(), and main().

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

◆ next_prime()

size_t next_prime ( size_t nb)

return the next prime number greater than or equal to nb

return the next prime number greater than or equal to nb

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

Definition at line 2575 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: