Nilorea Library
C utilities for networking, threading, graphics
Loading...
Searching...
No Matches
Data Structures | Macros | Typedefs | Functions
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
 
#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)    ((node && node->ptr) ? ((type*)(((HASH_NODE*)node->ptr)->data.ptr)) : NULL)
 Cast a HASH_NODE element.
 
#define HASH_VAL(node, type)    ((node && node->data.ptr) ? ((type*)node->data.ptr) : NULL)
 Cast a HASH_NODE element.
 
#define ht_foreach(__ITEM_, __HASH_)
 ForEach macro helper (classic / old)
 
#define HT_FOREACH(__ITEM_, __HASH_, ...)
 ForEach macro helper.
 
#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)   MurmurHash3_x64_128(__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)
 empty a table and destroy it
 
int empty_ht (HASH_TABLE *table)
 empty a table
 
LIST * ht_get_completion_list (HASH_TABLE *table, const char *keybud, size_t max_results)
 get next matching keys in table tree
 
int ht_get_double (HASH_TABLE *table, const char *key, double *val)
 get double at 'key' from 'table'
 
int ht_get_int (HASH_TABLE *table, const char *key, int64_t *val)
 
HASH_NODE * ht_get_node (HASH_TABLE *table, const char *key)
 get node at 'key' from 'table'
 
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)
 
size_t 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)
 
int ht_get_ptr (HASH_TABLE *table, const char *key, void **val)
 get pointer at 'key' from 'table'
 
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.
 
int ht_get_string (HASH_TABLE *table, const char *key, char **val)
 get string at 'key' from 'table'
 
int ht_get_table_collision_percentage (HASH_TABLE *table)
 get table collision percentage (HASH_CLASSIC mode only)
 
char * ht_node_type (HASH_NODE *node)
 get the type of a node , text version
 
int ht_optimize (HASH_TABLE **table)
 try an automatic optimization of the table
 
void ht_print (HASH_TABLE *table)
 print contents of table
 
int ht_put_double (HASH_TABLE *table, const char *key, double value)
 put a double value with given key in the targeted hash table
 
int ht_put_int (HASH_TABLE *table, const char *key, int64_t value)
 
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
 
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)
 
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
 
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
 
int ht_remove (HASH_TABLE *table, const char *key)
 remove and delete node at key in table
 
int ht_remove_ex (HASH_TABLE *table, HASH_VALUE hash_value)
 Remove a key from a hash table (HASH_CLASSIC only)
 
int ht_resize (HASH_TABLE **table, size_t size)
 rehash table according to size (HASH_CLASSIC mode only)
 
LIST * ht_search (HASH_TABLE *table, int(*node_is_matching)(HASH_NODE *node))
 seach table for matching nodes
 
int is_prime (size_t nb)
 
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.
 
void MurmurHash3_x86_128 (const void *key, const size_t len, const uint32_t seed, void *out)
 MurmurHash3 was written by Austin Appleby, and is placed in the public domain.
 
void MurmurHash3_x86_32 (const void *key, const size_t len, const uint32_t seed, void *out)
 MurmurHash3 was written by Austin Appleby, and is placed in the public domain.
 
HASH_TABLE * new_ht (size_t size)
 Create a hash table with the given size.
 
HASH_TABLE * new_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
 
size_t next_prime (size_t nb)
 

Detailed Description

Data Structure Documentation

◆ HASH_DATA

union HASH_DATA

union of the possibles data values of a node

Definition at line 78 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 90 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(* destroy_func )(void *ptr)
 destroy_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
 

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

Referenced by _ht_depth_first_search(), _ht_new_node(), _ht_new_node_trie(), _ht_node_destroy(), and _ht_search_trie_helper().

◆ children

struct HASH_NODE** HASH_NODE::children

HASH_TRIE mode: pointers to children.

Definition at line 108 of file n_hash.h.

Referenced by _ht_check_trie_divergence(), _ht_depth_first_search(), _ht_get_node_trie(), _ht_is_leaf_node_trie(), _ht_new_node(), _ht_new_node_trie(), _ht_node_destroy(), _ht_print_trie_helper(), _ht_put_double_trie(), _ht_put_ptr_trie(), _ht_put_string_ptr_trie(), _ht_put_string_trie(), _ht_remove_trie(), _ht_search_trie_helper(), and ht_get_completion_list().

◆ data

union HASH_DATA HASH_NODE::data

data inside the node

Definition at line 100 of file n_hash.h.

Referenced by _ht_get_double(), _ht_get_double_trie(), _ht_get_ptr(), _ht_get_ptr_trie(), _ht_get_string(), _ht_get_string_trie(), _ht_new_double_node(), _ht_new_node(), _ht_new_node_trie(), _ht_new_ptr_node(), _ht_new_string_node(), _ht_new_string_ptr_node(), _ht_node_destroy(), _ht_print_trie_helper(), _ht_put_double(), _ht_put_double_trie(), _ht_put_ptr(), _ht_put_ptr_trie(), _ht_put_string(), _ht_put_string_ptr(), _ht_put_string_ptr_trie(), _ht_put_string_trie(), _n_nodup_log(), _n_nodup_log_indexed(), check_n_log_dup(), check_n_log_dup_indexed(), dump_nodup_log(), ht_get_ptr_ex(), and ht_put_ptr_ex().

◆ destroy_func

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

destroy_func

Definition at line 102 of file n_hash.h.

Referenced by _ht_new_node(), _ht_new_node_trie(), _ht_new_ptr_node(), _ht_node_destroy(), _ht_put_ptr(), _ht_put_ptr_trie(), and ht_put_ptr_ex().

◆ hash_value

HASH_VALUE HASH_NODE::hash_value

numeric key of the node if any, else < 0

Definition at line 96 of file n_hash.h.

Referenced by _ht_new_node(), _ht_new_node_trie(), _ht_put_double(), _ht_put_ptr(), _ht_put_string(), _ht_put_string_ptr(), ht_get_node_ex(), ht_put_ptr_ex(), ht_remove_ex(), and ht_resize().

◆ is_leaf

int HASH_NODE::is_leaf

HASH_TRIE mode: does it have a value.

Definition at line 104 of file n_hash.h.

Referenced by _ht_depth_first_search(), _ht_get_double_trie(), _ht_get_ptr_trie(), _ht_get_string_trie(), _ht_is_leaf_node_trie(), _ht_new_node(), _ht_new_node_trie(), _ht_print_trie_helper(), _ht_put_double_trie(), _ht_put_ptr_trie(), _ht_put_string_ptr_trie(), _ht_put_string_trie(), and _ht_search_trie_helper().

◆ key

char* HASH_NODE::key

string key of the node if any, else NULL

Examples
ex_hash.c.

Definition at line 92 of file n_hash.h.

Referenced by _ht_depth_first_search(), _ht_get_node(), _ht_new_node(), _ht_new_node_trie(), _ht_node_destroy(), _ht_print_trie_helper(), _ht_put_double(), _ht_put_double_trie(), _ht_put_ptr(), _ht_put_ptr_trie(), _ht_put_string(), _ht_put_string_ptr(), _ht_put_string_ptr_trie(), _ht_put_string_trie(), _ht_remove(), _ht_search(), _ht_search_trie_helper(), ht_get_completion_list(), and ht_put_ptr_ex().

◆ key_id

char HASH_NODE::key_id

key id of the node if any

Definition at line 94 of file n_hash.h.

Referenced by _ht_new_node(), and _ht_new_node_trie().

◆ need_rehash

int HASH_NODE::need_rehash

flag to mark a node for rehash

Definition at line 106 of file n_hash.h.

Referenced by _ht_new_node(), _ht_new_node_trie(), and ht_resize().

◆ type

int HASH_NODE::type

type of the node

Definition at line 98 of file n_hash.h.

Referenced by _ht_get_double(), _ht_get_double_trie(), _ht_get_ptr(), _ht_get_ptr_trie(), _ht_get_string(), _ht_get_string_trie(), _ht_new_double_node(), _ht_new_ptr_node(), _ht_new_string_node(), _ht_new_string_ptr_node(), _ht_node_destroy(), _ht_print_trie_helper(), _ht_put_double(), _ht_put_double_trie(), _ht_put_ptr(), _ht_put_ptr_trie(), _ht_put_string(), _ht_put_string_ptr(), _ht_put_string_ptr_trie(), _ht_put_string_trie(), ht_get_ptr_ex(), ht_node_type(), and ht_put_ptr_ex().

◆ HASH_TABLE

struct HASH_TABLE

structure of a hash table

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

Definition at line 114 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(* destroy_ht )(struct HASH_TABLE **table)
 destroy a hash table
 
int(* empty_ht )(struct HASH_TABLE *table)
 empty a hash table.
 
LIST ** hash_table
 HASH_CLASSIC mode: preallocated hash table.
 
int(* ht_get_double )(struct HASH_TABLE *table, const char *key, double *val)
 get a double from a key's node
 
int(* ht_get_int )(struct HASH_TABLE *table, const char *key, int64_t *val)
 get an int from a key's node
 
HASH_NODE *(* ht_get_node )(struct HASH_TABLE *table, const char *key)
 get HASH_NODE at 'key' from table
 
int(* ht_get_ptr )(struct HASH_TABLE *table, const char *key, void **val)
 get a pointer from a key's node
 
int(* ht_get_string )(struct HASH_TABLE *table, const char *key, char **val)
 get a char *string from a key's node
 
void(* ht_print )(struct HASH_TABLE *table)
 print table
 
int(* ht_put_double )(struct HASH_TABLE *table, const char *key, double val)
 put a double
 
int(* ht_put_int )(struct HASH_TABLE *table, const char *key, int64_t val)
 put an integer
 
int(* ht_put_ptr )(struct HASH_TABLE *table, const char *key, void *ptr, void(*destructor)(void *ptr))
 put a a pointer
 
int(* ht_put_string )(struct HASH_TABLE *table, const char *key, char *val)
 put an char *string
 
int(* ht_put_string_ptr )(struct HASH_TABLE *table, const char *key, char *val)
 put an char *string pointer
 
int(* ht_remove )(struct HASH_TABLE *table, const char *key)
 remove given's key node from the table
 
LIST *(* ht_search )(struct HASH_TABLE *table, int(*node_is_matching)(HASH_NODE *node))
 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
 

Field Documentation

◆ alphabet_length

size_t HASH_TABLE::alphabet_length

HASH_TRIE mode: size of the alphabet.

Definition at line 126 of file n_hash.h.

Referenced by _ht_check_trie_divergence(), _ht_get_node_trie(), _ht_is_leaf_node_trie(), _ht_new_node_trie(), _ht_print_trie_helper(), _ht_put_double_trie(), _ht_put_ptr_trie(), _ht_put_string_ptr_trie(), _ht_put_string_trie(), _ht_remove_trie(), ht_get_completion_list(), and new_ht_trie().

◆ alphabet_offset

size_t HASH_TABLE::alphabet_offset

HASH_TRIE mode: offset to deduce to individual key digits.

Definition at line 128 of file n_hash.h.

Referenced by _ht_check_trie_divergence(), _ht_get_node_trie(), _ht_is_leaf_node_trie(), _ht_put_double_trie(), _ht_put_ptr_trie(), _ht_put_string_ptr_trie(), _ht_put_string_trie(), _ht_remove_trie(), ht_get_completion_list(), and new_ht_trie().

◆ destroy_ht

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

destroy a hash table

Definition at line 158 of file n_hash.h.

Referenced by new_ht(), and new_ht_trie().

◆ empty_ht

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

empty a hash table.

char *strings are also freed

Definition at line 156 of file n_hash.h.

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

◆ hash_table

LIST** HASH_TABLE::hash_table

HASH_CLASSIC mode: preallocated hash table.

Definition at line 122 of file n_hash.h.

Referenced by _empty_ht(), _ht_get_node(), _ht_print(), _ht_put_double(), _ht_put_ptr(), _ht_put_string(), _ht_put_string_ptr(), _ht_remove(), dump_nodup_log(), ht_get_node_ex(), ht_get_table_collision_percentage(), ht_put_ptr_ex(), ht_remove_ex(), new_ht(), and new_ht_trie().

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

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

◆ ht_get_int

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

get an int from a key's node

Definition at line 144 of file n_hash.h.

Referenced by new_ht(), and new_ht_trie().

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

Referenced by ht_get_node(), and new_ht().

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

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

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

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

◆ ht_print

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

print table

Definition at line 160 of file n_hash.h.

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

◆ ht_put_double

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

put a double

Definition at line 136 of file n_hash.h.

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

◆ ht_put_int

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

put an integer

Definition at line 134 of file n_hash.h.

Referenced by new_ht(), and new_ht_trie().

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

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

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

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

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

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

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

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

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

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

◆ mode

unsigned int HASH_TABLE::mode

hashing mode, murmurhash and classic HASH_MURMUR, or HASH_TRIE

Definition at line 130 of file n_hash.h.

Referenced by ht_get_completion_list(), ht_get_node_ex(), ht_get_ptr_ex(), ht_get_table_collision_percentage(), ht_put_ptr_ex(), ht_remove_ex(), new_ht(), and new_ht_trie().

◆ nb_keys

size_t HASH_TABLE::nb_keys

total number of used keys in the table

Definition at line 118 of file n_hash.h.

Referenced by _empty_ht(), _empty_ht_trie(), _ht_put_double(), _ht_put_double_trie(), _ht_put_ptr(), _ht_put_ptr_trie(), _ht_put_string(), _ht_put_string_ptr(), _ht_put_string_ptr_trie(), _ht_put_string_trie(), _ht_remove(), _ht_remove_trie(), ht_get_optimal_size(), ht_put_ptr_ex(), ht_remove_ex(), netw_pool_nbclients(), new_ht(), and new_ht_trie().

◆ root

HASH_NODE* HASH_TABLE::root

HASH_TRIE mode: Start of tree.

Definition at line 124 of file n_hash.h.

Referenced by _empty_ht_trie(), _ht_check_trie_divergence(), _ht_get_node_trie(), _ht_is_leaf_node_trie(), _ht_print_trie(), _ht_put_double_trie(), _ht_put_ptr_trie(), _ht_put_string_ptr_trie(), _ht_put_string_trie(), _ht_remove_trie(), _ht_search_trie(), ht_get_completion_list(), and new_ht_trie().

◆ seed

size_t HASH_TABLE::seed

table's seed

Definition at line 120 of file n_hash.h.

Referenced by _ht_get_node(), _ht_new_node(), _ht_remove(), new_ht(), and new_ht_trie().

◆ size

size_t HASH_TABLE::size

size of the hash table

Examples
ex_hash.c.

Definition at line 116 of file n_hash.h.

Referenced by _empty_ht(), _ht_get_node(), _ht_put_double(), _ht_put_ptr(), _ht_put_string(), _ht_put_string_ptr(), _ht_remove(), dump_nodup_log(), ht_get_node_ex(), ht_get_table_collision_percentage(), ht_put_ptr_ex(), ht_remove_ex(), new_ht(), and new_ht_trie().

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_INT_TYPE

#define HASH_INT_TYPE   int64_t

Definition at line 71 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 164 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 188 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)
HASH_CLASSIC
#define HASH_CLASSIC
Murmur hash using hash key string, hash key numeric value, index table with lists of elements.
Definition n_hash.h:60
LIST_NODE
Structure of a generic list node.
Definition n_list.h:24
LOG_ERR
#define LOG_ERR
error conditions
Definition n_log.h:56

ForEach macro helper (classic / old)

Definition at line 168 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; \
__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); \
}
CONCAT
#define CONCAT(a, b)
Concatenate two macro.
Definition n_common.h:437
HASH_TRIE
#define HASH_TRIE
TRIE tree using hash key string.
Definition n_hash.h:62
HASH_NODE
structure of a hash table node
Definition n_hash.h:90

ForEach macro helper.

Examples
ex_hash.c, and ex_network_ssl.c.

Definition at line 192 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; \
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 238 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 178 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 70 of file n_hash.h.

Typedef Documentation

◆ HASH_VALUE

typedef size_t HASH_VALUE

type of a HASH_VALUE

Definition at line 75 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 2180 of file n_hash.c.

References __n_assert.

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

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

References __n_assert, and empty_ht.

Referenced by empty_nodup_table().

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

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

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

References __n_assert, and ht_get_double.

◆ ht_get_int()

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

Definition at line 2034 of file n_hash.c.

◆ 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 2008 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(), 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 
)

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

References __n_assert, HASH_CLASSIC, hash_table, HASH_NODE::hash_value, list_foreach, mode, 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)

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
0 or optimal table size

Definition at line 2442 of file n_hash.c.

References __n_assert, and nb_keys.

Referenced by ht_optimize().

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

References __n_assert, and ht_get_ptr.

Referenced by get_config_section_value(), get_nb_config_file_sections_entries(), load_config_file(), and netw_pool_add().

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

References __n_assert, HASH_NODE::data, HASH_CLASSIC, HASH_PTR, ht_get_node_ex(), ht_node_type(), LOG_ERR, 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 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 2060 of file n_hash.c.

References __n_assert, and ht_get_string.

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

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

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

References __n_assert, HASH_UNKNOWN, and HASH_NODE::type.

Referenced by _ht_get_double(), _ht_get_double_trie(), _ht_get_ptr(), _ht_get_ptr_trie(), _ht_get_string(), _ht_get_string_trie(), _ht_put_double(), _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 2532 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 2148 of file n_hash.c.

References __n_assert, and ht_print.

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

References __n_assert, and ht_put_double.

◆ ht_put_int()

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

Definition at line 2086 of file n_hash.c.

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

References __n_assert, and ht_put_ptr.

Referenced by load_config_file(), 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(*)(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 2245 of file n_hash.c.

References __n_assert, _ht_node_destroy(), HASH_NODE::data, HASH_NODE::destroy_func, HASH_CLASSIC, HASH_PTR, hash_table, HASH_NODE::hash_value, ht_node_type(), HASH_NODE::key, list_foreach, list_push(), LOG_ERR, Malloc, mode, n_log, nb_keys, HASH_DATA::ptr, 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 (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 2113 of file n_hash.c.

References __n_assert, and ht_put_string.

Referenced by _n_nodup_log(), _n_nodup_log_indexed(), 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 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 2126 of file n_hash.c.

References __n_assert, and ht_put_string_ptr.

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

References __n_assert, and ht_remove.

Referenced by 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 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 2294 of file n_hash.c.

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

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

References __n_assert, Free, 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, LIST_NODE::next, LIST_NODE::prev, 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 2160 of file n_hash.c.

References __n_assert, and ht_search.

◆ is_prime()

int is_prime ( size_t  nb)

Definition at line 2381 of file n_hash.c.

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

References FALL_THROUGH, and ROTL64.

◆ MurmurHash3_x86_128()

void MurmurHash3_x86_128 ( const void *  key,
const size_t  len,
const 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 981 of file n_hash.c.

References FALL_THROUGH, and ROTL32.

◆ MurmurHash3_x86_32()

void MurmurHash3_x86_32 ( const void *  key,
const size_t  len,
const 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 923 of file n_hash.c.

References FALL_THROUGH, and ROTL32.

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

References __n_assert, _destroy_ht(), _empty_ht(), _ht_get_double(), _ht_get_node(), _ht_get_ptr(), _ht_get_string(), _ht_print(), _ht_put_double(), _ht_put_ptr(), _ht_put_string(), _ht_put_string_ptr(), _ht_remove(), _ht_search(), destroy_ht, empty_ht, Free, HASH_CLASSIC, hash_table, 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, MAX_LIST_ITEMS, mode, n_log, nb_keys, seed, and size.

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

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

References __n_assert, _destroy_ht_trie(), _empty_ht_trie(), _ht_get_double_trie(), _ht_get_ptr_trie(), _ht_get_string_trie(), _ht_new_node_trie(), _ht_print_trie(), _ht_put_double_trie(), _ht_put_ptr_trie(), _ht_put_string_ptr_trie(), _ht_put_string_trie(), _ht_remove_trie(), _ht_search_trie(), alphabet_length, alphabet_offset, destroy_ht, empty_ht, Free, hash_table, 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, mode, n_log, nb_keys, root, seed, and size.

+ Here is the call graph for this function:

◆ next_prime()

size_t next_prime ( size_t  nb)

Definition at line 2403 of file n_hash.c.