Hash functions and table. More...

#include "nilorea/n_common.h"
#include "nilorea/n_log.h"
#include "nilorea/n_hash.h"
#include "nilorea/n_str.h"
#include <pthread.h>
#include <string.h>
#include <strings.h>
#include <arpa/inet.h>

Include dependency graph for n_hash.c:

Go to the source code of this file.

Macros
#define	BIG_CONSTANT(x) (x##LLU)
	max unsigned long long

#define	BYTESWAP32(x) ((((x) & 0xFF) << 24) \| (((x) >> 24) & 0xFF) \| (((x) & 0x0000FF00) << 8) \| (((x) & 0x00FF0000) >> 8))
	32 bits bytes swap

#define	BYTESWAP64(x)
	32 bits bytes swap

#define	ROTL32(x, r) (((x) << (r)) \| ((x) >> (32 - (r))))
	32 bit rotate left

#define	ROTL64(x, r) (((x) << (r)) \| ((x) >> (64 - (r))))
	64 bit rotate left

Functions
static	__attribute__ ((always_inline))

int	_destroy_ht (HASH_TABLE **table)
	Free and set the table to NULL.

int	_destroy_ht_trie (HASH_TABLE **table)
	Free and set the table to NULL (TRIE mode)

int	_empty_ht (HASH_TABLE *table)
	Empty a hash table (CLASSIC mode)

int	_empty_ht_trie (HASH_TABLE *table)
	Empty a TRIE hash table.

size_t	_ht_check_trie_divergence (HASH_TABLE table, const char key)
	check and return branching index in key if any

int	_ht_depth_first_search (HASH_NODE node, LIST results)
	recursive, helper for ht_get_completion_list, get the list of leaf starting from node

char *	_ht_find_longest_prefix_trie (HASH_TABLE table, const char key)
	find the longest prefix string that is not the current key

int	_ht_get_double (HASH_TABLE table, const char key, double *val)
	Retrieve a double value in the hash table, at the given key.

int	_ht_get_double_trie (HASH_TABLE table, const char key, double *val)
	Retrieve an double value in the hash table, at the given key.

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

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

HASH_NODE *	_ht_get_node (HASH_TABLE table, const char key)
	return the associated key's node inside the hash_table

HASH_NODE *	_ht_get_node_trie (HASH_TABLE table, const char key)
	retrieve a HASH_NODE at key from table

int	_ht_get_ptr (HASH_TABLE table, const char key, void **val)
	Retrieve a pointer value in the hash table, at the given key.

int	_ht_get_ptr_trie (HASH_TABLE table, const char key, 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)
	Retrieve a char *string value in the hash table, at the given key.

int	_ht_get_string_trie (HASH_TABLE table, const char key, char **val)
	Retrieve an char *string value in the hash table, at the given key.

int	_ht_is_leaf_node_trie (HASH_TABLE table, const char key)
	Search a key and tell if it's holding a value (leaf)

HASH_NODE *	_ht_new_double_node (HASH_TABLE table, const char key, double value)
	node creation, HASH_CLASSIC mode

HASH_NODE *	_ht_new_int_node (HASH_TABLE table, const char key, int64_t value)

HASH_NODE *	_ht_new_node (HASH_TABLE table, const char key)
	node creation, HASH_CLASSIC mode

HASH_NODE *	_ht_new_node_trie (HASH_TABLE *table, const char key)
	node creation, HASH_CLASSIC mode

HASH_NODE *	_ht_new_ptr_node (HASH_TABLE table, const char key, void value, void(destructor)(void *ptr))
	node creation, HASH_CLASSIC mode, pointer to string value

HASH_NODE *	_ht_new_string_node (HASH_TABLE table, const char key, char *value)
	node creation, HASH_CLASSIC mode, strdup of value

HASH_NODE *	_ht_new_string_ptr_node (HASH_TABLE table, const char key, char *value)
	node creation, HASH_CLASSIC mode, pointer to string value

void	_ht_node_destroy (void *node)
	destroy a HASH_NODE by first calling the HASH_NODE destructor

void	_ht_print (HASH_TABLE *table)
	Generic print func call for classic hash tables.

void	_ht_print_trie (HASH_TABLE *table)
	Generic print func call for trie trees.

void	_ht_print_trie_helper (HASH_TABLE table, HASH_NODE node)
	Recursive function to print trie tree's keys and values.

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_double_trie (HASH_TABLE table, const char key, double value)
	put a double value with given key in the targeted hash table [TRIE HASH TABLE)

int	_ht_put_int (HASH_TABLE table, const char key, int64_t value)

int	_ht_put_int_trie (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 value with given key in the targeted hash table

int	_ht_put_ptr_trie (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 [TRIE HASH TABLE)

int	_ht_put_string (HASH_TABLE table, const char key, char *string)
	put a null terminated char *string with given key in the targeted hash table (copy of string)

int	_ht_put_string_ptr (HASH_TABLE table, const char key, char *string)
	put a null terminated char *string with given key in the targeted hash table (pointer)

int	_ht_put_string_ptr_trie (HASH_TABLE table, const char key, char *string)
	put a pointer to the string value with given key in the targeted hash table [TRIE HASH TABLE)

int	_ht_put_string_trie (HASH_TABLE table, const char key, char *string)
	put a duplicate of the string value with given key in the targeted hash table [TRIE HASH TABLE)

int	_ht_remove (HASH_TABLE table, const char key)
	Remove a key from a hash table.

int	_ht_remove_trie (HASH_TABLE table, const char key)
	Remove a key from a trie table and destroy the node.

LIST *	_ht_search (HASH_TABLE table, int(node_is_matching)(HASH_NODE *node))
	Search hash table's keys and apply a matching func to put results in the list.

LIST *	_ht_search_trie (HASH_TABLE table, int(node_is_matching)(HASH_NODE *node))
	Search tree's keys and apply a matching func to put results in the list.

void	_ht_search_trie_helper (LIST results, HASH_NODE node, int(node_is_matching)(HASH_NODE node))
	Recursive function to search tree's keys and apply a matching func to put results in the list.

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_length, 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

Hash functions and table.

Author: Castagnier Mickael

Version: 2.0

Date: 16/03/2015

Definition in file n_hash.c.

Macro Definition Documentation

◆ BIG_CONSTANT

#define BIG_CONSTANT ( x ) (x##LLU)

max unsigned long long

Definition at line 814 of file n_hash.c.

◆ BYTESWAP32

#define BYTESWAP32 ( x ) ((((x) & 0xFF) << 24) | (((x) >> 24) & 0xFF) | (((x) & 0x0000FF00) << 8) | (((x) & 0x00FF0000) >> 8))

32 bits bytes swap

Definition at line 841 of file n_hash.c.

◆ BYTESWAP64

#define BYTESWAP64 ( x )

Value:

    (((uint64_t)(x) << 56) |                           \
     (((uint64_t)(x) << 40) & 0X00FF000000000000ULL) | \
     (((uint64_t)(x) << 24) & 0X0000FF0000000000ULL) | \
     (((uint64_t)(x) << 8) & 0X000000FF00000000ULL) |  \
     (((uint64_t)(x) >> 8) & 0X00000000FF000000ULL) |  \
     (((uint64_t)(x) >> 24) & 0X0000000000FF0000ULL) | \
     (((uint64_t)(x) >> 40) & 0X000000000000FF00ULL) | \
     ((uint64_t)(x) >> 56))

32 bits bytes swap

Definition at line 845 of file n_hash.c.

◆ ROTL32

#define ROTL32	(	x,
		r
	)	(((x) << (r)) \| ((x) >> (32 - (r))))

32 bit rotate left

Definition at line 812 of file n_hash.c.

◆ ROTL64

#define ROTL64	(	x,
		r
	)	(((x) << (r)) \| ((x) >> (64 - (r))))

64 bit rotate left

Definition at line 810 of file n_hash.c.

Function Documentation

◆ attribute()

static __attribute__ ( (always_inline) )

inlinestatic

Definition at line 862 of file n_hash.c.

◆ _destroy_ht()

int _destroy_ht ( HASH_TABLE ** table )

Free and set the table to NULL.

Parameters

table targeted hash table

Returns: TRUE or FALSE.

Definition at line 1834 of file n_hash.c.

References __n_assert, Free, list_destroy(), LOG_ERR, and n_log.

Referenced by new_ht().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ _destroy_ht_trie()

int _destroy_ht_trie ( HASH_TABLE ** table )

Free and set the table to NULL (TRIE mode)

Parameters

table targeted hash table

Returns: TRUE or FALSE.

Definition at line 676 of file n_hash.c.

References __n_assert, _ht_node_destroy(), Free, LOG_ERR, and n_log.

Referenced by new_ht_trie().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ _empty_ht()

int _empty_ht ( HASH_TABLE * table )

Empty a hash table (CLASSIC mode)

Parameters

table targeted hash table

Returns: TRUE or FALSE.

Definition at line 1811 of file n_hash.c.

References __n_assert, _ht_node_destroy(), HASH_TABLE::hash_table, HASH_TABLE::nb_keys, remove_list_node, HASH_TABLE::size, and LIST::start.

Referenced by new_ht().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ _empty_ht_trie()

int _empty_ht_trie ( HASH_TABLE * table )

Empty a TRIE hash table.

Parameters

table targeted hash table

Returns: TRUE or FALSE.

Definition at line 658 of file n_hash.c.

References __n_assert, _ht_new_node_trie(), _ht_node_destroy(), HASH_TABLE::nb_keys, and HASH_TABLE::root.

Referenced by new_ht_trie().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ _ht_check_trie_divergence()

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

check and return branching index in key if any

Parameters

table	targeted hash table
key	associated value's key

Returns: index of the divergence or SIZE_MAX on error

Definition at line 123 of file n_hash.c.

References __n_assert, HASH_TABLE::alphabet_length, HASH_TABLE::alphabet_offset, HASH_NODE::children, LOG_ERR, n_log, and HASH_TABLE::root.

Referenced by _ht_find_longest_prefix_trie().

Here is the caller graph for this function:

◆ _ht_depth_first_search()

int _ht_depth_first_search	(	HASH_NODE *	node,
		LIST *	results
	)

recursive, helper for ht_get_completion_list, get the list of leaf starting from node

Parameters

node	starting node
results	initialized LIST * for the matching NODES

Returns: TRUE or FALSE

Definition at line 790 of file n_hash.c.

References __n_assert, _ht_depth_first_search(), HASH_NODE::alphabet_length, HASH_NODE::children, HASH_NODE::is_leaf, HASH_NODE::key, list_push(), LIST::nb_items, and LIST::nb_max_items.

Referenced by _ht_depth_first_search(), and ht_get_completion_list().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ _ht_find_longest_prefix_trie()

char * _ht_find_longest_prefix_trie	(	HASH_TABLE *	table,
		const char *	key
	)

find the longest prefix string that is not the current key

Parameters

table	targeted hash table
key	key to search prefix for

Returns: TRUE or FALSE

Definition at line 158 of file n_hash.c.

References __n_assert, _ht_check_trie_divergence(), LOG_ERR, Malloc, n_log, and Realloc.

Referenced by _ht_remove_trie().

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
	)

Retrieve a double value in the hash table, at the given key.

Leave val untouched if key is not found.

Parameters

table	targeted hash table
key	associated value's key
val	A pointer to a destination double

Returns: TRUE or FALSE.

Definition at line 1682 of file n_hash.c.

References __n_assert, _ht_get_node(), HASH_NODE::data, HASH_DATA::fval, HASH_DOUBLE, ht_node_type(), LOG_ERR, n_log, and HASH_NODE::type.

Referenced by new_ht().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ _ht_get_double_trie()

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

Retrieve an double value in the hash table, at the given key.

Leave val untouched if key is not found.

Parameters

table	targeted hash table
key	associated value's key
val	a pointer to a destination double

Returns: TRUE or FALSE.

Definition at line 576 of file n_hash.c.

References __n_assert, _ht_get_node_trie(), HASH_NODE::data, HASH_DATA::fval, HASH_DOUBLE, ht_node_type(), HASH_NODE::is_leaf, LOG_ERR, n_log, and HASH_NODE::type.

Referenced by new_ht_trie().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ _ht_get_int()

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

Definition at line 1654 of file n_hash.c.

◆ _ht_get_int_trie()

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

Definition at line 548 of file n_hash.c.

◆ _ht_get_node()

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

return the associated key's node inside the hash_table

Parameters

table	targeted table
key	Associated value's key

Returns: The found node, or NULL

Definition at line 1288 of file n_hash.c.

References __n_assert, HASH_TABLE::hash_table, HASH_NODE::key, list_foreach, MurmurHash, HASH_TABLE::seed, HASH_TABLE::size, and LIST::start.

Referenced by _ht_get_double(), _ht_get_ptr(), _ht_get_string(), _ht_put_double(), _ht_put_ptr(), _ht_put_string(), _ht_put_string_ptr(), and new_ht().

Here is the caller graph for this function:

◆ _ht_get_node_trie()

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

retrieve a HASH_NODE at key from table

Parameters

table	targeted hash table
key	associated value's key

Returns: a HASH_NODE *node or NULL

Definition at line 515 of file n_hash.c.

References __n_assert, HASH_TABLE::alphabet_length, HASH_TABLE::alphabet_offset, HASH_NODE::children, LOG_DEBUG, n_log, and HASH_TABLE::root.

Referenced by _ht_get_double_trie(), _ht_get_ptr_trie(), _ht_get_string_trie(), and ht_get_completion_list().

Here is the caller graph for this function:

◆ _ht_get_ptr()

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

Retrieve a pointer value in the hash table, at the given key.

Leave val untouched if key is not found.

Parameters

table	targeted hash table
key	associated value's key
val	A pointer to an empty pointer store

Returns: TRUE or FALSE.

Definition at line 1711 of file n_hash.c.

References __n_assert, _ht_get_node(), HASH_NODE::data, HASH_PTR, ht_node_type(), LOG_ERR, n_log, HASH_DATA::ptr, and HASH_NODE::type.

Referenced by new_ht().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ _ht_get_ptr_trie()

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

Retrieve a pointer value in the hash table, at the given key.

Leave val untouched if key is not found.

Parameters

table	targeted hash table
key	associated value's key
val	a pointer to a destination pointer

Returns: TRUE or FALSE.

Definition at line 632 of file n_hash.c.

References __n_assert, _ht_get_node_trie(), HASH_NODE::data, HASH_PTR, ht_node_type(), HASH_NODE::is_leaf, LOG_ERR, n_log, HASH_DATA::ptr, and HASH_NODE::type.

Referenced by new_ht_trie().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ _ht_get_string()

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

Retrieve a char *string value in the hash table, at the given key.

Leave val untouched if key is not found.

Parameters

table	targeted hash table
key	associated value's key
val	A pointer to an empty destination char *string

Returns: TRUE or FALSE.

Definition at line 1738 of file n_hash.c.

References __n_assert, _ht_get_node(), HASH_NODE::data, HASH_STRING, ht_node_type(), LOG_ERR, n_log, HASH_DATA::string, and HASH_NODE::type.

Referenced by new_ht().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ _ht_get_string_trie()

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

Retrieve an char *string value in the hash table, at the given key.

Leave val untouched if key is not found.

Parameters

table	targeted hash table
key	associated value's key
val	a pointer to a destination char *string

Returns: TRUE or FALSE.

Definition at line 604 of file n_hash.c.

References __n_assert, _ht_get_node_trie(), HASH_NODE::data, HASH_STRING, ht_node_type(), HASH_NODE::is_leaf, LOG_ERR, n_log, HASH_DATA::string, and HASH_NODE::type.

Referenced by new_ht_trie().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ _ht_is_leaf_node_trie()

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

Search a key and tell if it's holding a value (leaf)

Parameters

table	targeted hash table
key	key verify

Returns: 1 or 0

Definition at line 66 of file n_hash.c.

References __n_assert, HASH_TABLE::alphabet_length, HASH_TABLE::alphabet_offset, HASH_NODE::children, HASH_NODE::is_leaf, LOG_ERR, n_log, and HASH_TABLE::root.

Referenced by _ht_remove_trie().

Here is the caller graph for this function:

◆ _ht_new_double_node()

HASH_NODE * _ht_new_double_node	(	HASH_TABLE *	table,
		const char *	key,
		double	value
	)

node creation, HASH_CLASSIC mode

Parameters

table	targeted table
key	key of new node
value	double value of key

Returns: NULL or a new HASH_NODE *

Definition at line 1379 of file n_hash.c.

References __n_assert, _ht_new_node(), HASH_NODE::data, HASH_DATA::fval, HASH_DOUBLE, LOG_ERR, n_log, and HASH_NODE::type.

Referenced by _ht_put_double().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ _ht_new_int_node()

HASH_NODE * _ht_new_int_node	(	HASH_TABLE *	table,
		const char *	key,
		int64_t	value
	)

Definition at line 1357 of file n_hash.c.

◆ _ht_new_node()

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

node creation, HASH_CLASSIC mode

Parameters

table	targeted table
key	key of new node

Returns: NULL or a new HASH_NODE *

Definition at line 1321 of file n_hash.c.

References __n_assert, HASH_NODE::alphabet_length, HASH_NODE::children, HASH_NODE::data, HASH_NODE::destroy_func, Free, HASH_NODE::hash_value, HASH_NODE::is_leaf, HASH_NODE::key, HASH_NODE::key_id, LOG_ERR, Malloc, MurmurHash, n_log, HASH_NODE::need_rehash, HASH_DATA::ptr, and HASH_TABLE::seed.

Referenced by _ht_new_double_node(), _ht_new_ptr_node(), _ht_new_string_node(), and _ht_new_string_ptr_node().

Here is the caller graph for this function:

◆ _ht_new_node_trie()

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

node creation, HASH_CLASSIC mode

Parameters

table	targeted table
key	key of new node

Returns: NULL or a new HASH_NODE *

Definition at line 32 of file n_hash.c.

References __n_assert, HASH_NODE::alphabet_length, HASH_TABLE::alphabet_length, HASH_NODE::children, HASH_NODE::data, HASH_NODE::destroy_func, Free, HASH_NODE::hash_value, HASH_NODE::is_leaf, HASH_NODE::key, HASH_NODE::key_id, LOG_ERR, Malloc, n_log, HASH_NODE::need_rehash, and HASH_DATA::ptr.

Referenced by _empty_ht_trie(), _ht_put_double_trie(), _ht_put_ptr_trie(), _ht_put_string_ptr_trie(), _ht_put_string_trie(), and new_ht_trie().

Here is the caller graph for this function:

◆ _ht_new_ptr_node()

HASH_NODE * _ht_new_ptr_node	(	HASH_TABLE *	table,
		const char *	key,
		void *	value,
		void()(void ptr)	destructor
	)

node creation, HASH_CLASSIC mode, pointer to string value

Parameters

table	targeted table
key	key of new node
value	pointer data of key
destructor	function pointer to a destructor of value type

Returns: NULL or a new HASH_NODE *

Definition at line 1449 of file n_hash.c.

References __n_assert, _ht_new_node(), HASH_NODE::data, HASH_NODE::destroy_func, HASH_PTR, LOG_ERR, n_log, HASH_DATA::ptr, and HASH_NODE::type.

Referenced by _ht_put_ptr().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ _ht_new_string_node()

HASH_NODE * _ht_new_string_node	(	HASH_TABLE *	table,
		const char *	key,
		char *	value
	)

node creation, HASH_CLASSIC mode, strdup of value

Parameters

table	targeted table
key	key of new node
value	char *value of key

Returns: NULL or a new HASH_NODE *

Definition at line 1401 of file n_hash.c.

References __n_assert, _ht_new_node(), HASH_NODE::data, HASH_STRING, LOG_ERR, n_log, HASH_DATA::string, and HASH_NODE::type.

Referenced by _ht_put_string(), and _ht_put_string_ptr().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ _ht_new_string_ptr_node()

HASH_NODE * _ht_new_string_ptr_node	(	HASH_TABLE *	table,
		const char *	key,
		char *	value
	)

node creation, HASH_CLASSIC mode, pointer to string value

Parameters

table	targeted table
key	key of new node
value	char *value of key

Returns: NULL or a new HASH_NODE *

Definition at line 1426 of file n_hash.c.

References __n_assert, _ht_new_node(), HASH_NODE::data, HASH_STRING, LOG_ERR, n_log, HASH_DATA::string, and HASH_NODE::type.

Here is the call graph for this function:

◆ _ht_node_destroy()

void _ht_node_destroy ( void * node )

destroy a HASH_NODE by first calling the HASH_NODE destructor

Parameters

node	The node to kill

Definition at line 88 of file n_hash.c.

References __n_assert, _ht_node_destroy(), HASH_NODE::alphabet_length, HASH_NODE::children, HASH_NODE::data, HASH_NODE::destroy_func, Free, FreeNoLog, HASH_PTR, HASH_STRING, HASH_NODE::key, HASH_DATA::ptr, HASH_DATA::string, and HASH_NODE::type.

Referenced by _destroy_ht_trie(), _empty_ht(), _empty_ht_trie(), _ht_node_destroy(), _ht_put_double(), _ht_put_ptr(), _ht_put_string(), _ht_put_string_ptr(), _ht_remove(), _ht_remove_trie(), ht_put_ptr_ex(), and ht_remove_ex().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ _ht_print()

void _ht_print ( HASH_TABLE * table )

Generic print func call for classic hash tables.

Parameters

table targeted hash table

Definition at line 1857 of file n_hash.c.

References __n_assert, HASH_TABLE::hash_table, and ht_foreach.

Referenced by new_ht().

Here is the caller graph for this function:

◆ _ht_print_trie()

void _ht_print_trie ( HASH_TABLE * table )

Generic print func call for trie trees.

Parameters

table targeted hash table

Definition at line 727 of file n_hash.c.

References __n_assert, _ht_print_trie_helper(), and HASH_TABLE::root.

Referenced by new_ht_trie().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ _ht_print_trie_helper()

void _ht_print_trie_helper	(	HASH_TABLE *	table,
		HASH_NODE *	node
	)

Recursive function to print trie tree's keys and values.

Parameters

table	targeted hash table
node	current node

Definition at line 693 of file n_hash.c.

References _ht_print_trie_helper(), HASH_TABLE::alphabet_length, HASH_NODE::children, HASH_NODE::data, HASH_DATA::fval, HASH_DOUBLE, HASH_INT, HASH_PTR, HASH_STRING, HASH_NODE::is_leaf, HASH_DATA::ival, HASH_NODE::key, HASH_DATA::ptr, HASH_DATA::string, and HASH_NODE::type.

Referenced by _ht_print_trie(), and _ht_print_trie_helper().

Here is the call graph for this function:

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

table	targeted hash table
key	associated value's key
value	double value to put

Returns: TRUE or FALSE

Definition at line 1508 of file n_hash.c.

References __n_assert, _ht_get_node(), _ht_new_double_node(), _ht_node_destroy(), HASH_NODE::data, HASH_DATA::fval, HASH_DOUBLE, HASH_TABLE::hash_table, HASH_NODE::hash_value, ht_node_type(), HASH_NODE::key, list_push(), LOG_ERR, n_log, HASH_TABLE::nb_keys, HASH_TABLE::size, and HASH_NODE::type.

Referenced by new_ht().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ _ht_put_double_trie()

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

put a double value with given key in the targeted hash table [TRIE HASH TABLE)

Parameters

table	targeted hash table
key	associated value's key
value	double value to put

Returns: TRUE or FALSE

Definition at line 307 of file n_hash.c.

References __n_assert, _ht_new_node_trie(), _ht_remove_trie(), HASH_TABLE::alphabet_length, HASH_TABLE::alphabet_offset, HASH_NODE::children, HASH_NODE::data, HASH_DATA::fval, HASH_DOUBLE, HASH_NODE::is_leaf, HASH_NODE::key, LOG_ERR, n_log, HASH_TABLE::nb_keys, HASH_TABLE::root, and HASH_NODE::type.

Referenced by new_ht_trie().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ _ht_put_int()

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

Definition at line 1474 of file n_hash.c.

◆ _ht_put_int_trie()

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

Definition at line 256 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 value with given key in the targeted hash table

Parameters

table	targeted hash table
key	Associated value's key
ptr	pointer value to put
destructor	Pointer to the ptr type destructor function. Leave to NULL if there isn't

Returns: TRUE or FALSE

Definition at line 1543 of file n_hash.c.

References __n_assert, _ht_get_node(), _ht_new_ptr_node(), _ht_node_destroy(), HASH_NODE::data, HASH_NODE::destroy_func, HASH_PTR, HASH_TABLE::hash_table, HASH_NODE::hash_value, ht_node_type(), HASH_NODE::key, list_push(), LOG_ERR, n_log, HASH_TABLE::nb_keys, HASH_DATA::ptr, HASH_TABLE::size, and HASH_NODE::type.

Referenced by new_ht().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ _ht_put_ptr_trie()

int _ht_put_ptr_trie	(	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 [TRIE HASH TABLE)

Parameters

table	targeted hash table
key	associated value's key
ptr	pointer value to put
destructor	the destructor func for ptr or NULL

Returns: TRUE or FALSE

Definition at line 470 of file n_hash.c.

References __n_assert, _ht_new_node_trie(), HASH_TABLE::alphabet_length, HASH_TABLE::alphabet_offset, HASH_NODE::children, HASH_NODE::data, HASH_NODE::destroy_func, HASH_PTR, HASH_NODE::is_leaf, HASH_NODE::key, LOG_ERR, n_log, HASH_TABLE::nb_keys, HASH_DATA::ptr, HASH_TABLE::root, and HASH_NODE::type.

Referenced by new_ht_trie().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ _ht_put_string()

int _ht_put_string	(	HASH_TABLE *	table,
		const char *	key,
		char *	string
	)

put a null terminated char *string with given key in the targeted hash table (copy of string)

Parameters

table	targeted hash table
key	Associated value's key
string	string value to put (will be strdup'ed)

Returns: TRUE or FALSE

Definition at line 1582 of file n_hash.c.

References __n_assert, _ht_get_node(), _ht_new_string_node(), _ht_node_destroy(), HASH_NODE::data, Free, HASH_STRING, HASH_TABLE::hash_table, HASH_NODE::hash_value, ht_node_type(), HASH_NODE::key, list_push(), LOG_ERR, n_log, HASH_TABLE::nb_keys, HASH_TABLE::size, HASH_DATA::string, and HASH_NODE::type.

Referenced by new_ht().

Here is the call graph for this function:

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 null terminated char *string with given key in the targeted hash table (pointer)

Parameters

table	targeted hash table
key	Associated value's key
string	The string to put

Returns: TRUE or FALSE

Definition at line 1618 of file n_hash.c.

References __n_assert, _ht_get_node(), _ht_new_string_node(), _ht_node_destroy(), HASH_NODE::data, Free, HASH_STRING, HASH_TABLE::hash_table, HASH_NODE::hash_value, ht_node_type(), HASH_NODE::key, list_push(), LOG_ERR, n_log, HASH_TABLE::nb_keys, HASH_TABLE::size, HASH_DATA::string, and HASH_NODE::type.

Referenced by new_ht().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ _ht_put_string_ptr_trie()

int _ht_put_string_ptr_trie	(	HASH_TABLE *	table,
		const char *	key,
		char *	string
	)

put a pointer to the string value with given key in the targeted hash table [TRIE HASH TABLE)

Parameters

table	targeted hash table
key	associated value's key
string	string value to put (pointer)

Returns: TRUE or FALSE

Definition at line 419 of file n_hash.c.

References __n_assert, _ht_new_node_trie(), _ht_remove_trie(), HASH_TABLE::alphabet_length, HASH_TABLE::alphabet_offset, HASH_NODE::children, HASH_NODE::data, HASH_STRING, HASH_NODE::is_leaf, HASH_NODE::key, LOG_ERR, n_log, HASH_TABLE::nb_keys, HASH_TABLE::root, HASH_DATA::string, and HASH_NODE::type.

Referenced by new_ht_trie().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ _ht_put_string_trie()

int _ht_put_string_trie	(	HASH_TABLE *	table,
		const char *	key,
		char *	string
	)

put a duplicate of the string value with given key in the targeted hash table [TRIE HASH TABLE)

Parameters

table	targeted hash table
key	associated value's key
string	string value to put (copy)

Returns: TRUE or FALSE

Definition at line 357 of file n_hash.c.

References __n_assert, _ht_new_node_trie(), _ht_remove_trie(), HASH_TABLE::alphabet_length, HASH_TABLE::alphabet_offset, HASH_NODE::children, HASH_NODE::data, Free, HASH_STRING, HASH_NODE::is_leaf, HASH_NODE::key, LOG_ERR, n_log, HASH_TABLE::nb_keys, HASH_TABLE::root, HASH_DATA::string, and HASH_NODE::type.

Referenced by new_ht_trie().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ _ht_remove()

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

Remove a key from a hash table.

Parameters

table	targeted hash table
key	Key to remove

Returns: TRUE or FALSE.

Definition at line 1764 of file n_hash.c.

References __n_assert, _ht_node_destroy(), HASH_TABLE::hash_table, HASH_NODE::key, list_foreach, LOG_ERR, MurmurHash, n_log, HASH_TABLE::nb_keys, remove_list_node, HASH_TABLE::seed, HASH_TABLE::size, and LIST::start.

Referenced by new_ht().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ _ht_remove_trie()

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

Remove a key from a trie table and destroy the node.

Parameters

table	targeted tabled
key	the node key to kill

Returns: TRUE or FALSE

Definition at line 191 of file n_hash.c.

References __n_assert, _ht_find_longest_prefix_trie(), _ht_is_leaf_node_trie(), _ht_node_destroy(), HASH_TABLE::alphabet_length, HASH_TABLE::alphabet_offset, HASH_NODE::children, Free, LOG_ERR, n_log, HASH_TABLE::nb_keys, and HASH_TABLE::root.

Referenced by _ht_put_double_trie(), _ht_put_string_ptr_trie(), _ht_put_string_trie(), and new_ht_trie().

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
	)

Search hash table's keys and apply a matching func to put results in the list.

Parameters

table	targeted table
node_is_matching	pointer to a matching function to use

Returns: NULL or a LIST *list of HASH_NODE *elements

Definition at line 1875 of file n_hash.c.

References __n_assert, ht_foreach, HASH_NODE::key, list_destroy(), list_push(), MAX_LIST_ITEMS, and LIST::nb_items.

Referenced by new_ht().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ _ht_search_trie()

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

Search tree's keys and apply a matching func to put results in the list.

Parameters

table	targeted table
node_is_matching	pointer to a matching function to use

Returns: NULL or a LIST *list of HASH_NODE *elements

Definition at line 768 of file n_hash.c.

References __n_assert, _ht_search_trie_helper(), list_destroy(), MAX_LIST_ITEMS, LIST::nb_items, and HASH_TABLE::root.

Referenced by new_ht_trie().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ _ht_search_trie_helper()

void _ht_search_trie_helper	(	LIST *	results,
		HASH_NODE *	node,
		int()(HASH_NODE node)	node_is_matching
	)

Recursive function to search tree's keys and apply a matching func to put results in the list.

Parameters

results	targeted and initialized LIST in which the matching nodes will be put
node	targeted starting trie node
node_is_matching	pointer to a matching function to use

Definition at line 746 of file n_hash.c.

References _ht_search_trie_helper(), HASH_NODE::alphabet_length, HASH_NODE::children, HASH_NODE::is_leaf, HASH_NODE::key, and list_push().

Referenced by _ht_search_trie(), and _ht_search_trie_helper().

Here is the call graph for this function:

Here is the caller graph for this function:

Macros

Functions

Detailed Description

Macro Definition Documentation

◆ BIG_CONSTANT

◆ BYTESWAP32

◆ BYTESWAP64

◆ ROTL32

◆ ROTL64

Function Documentation

◆ __attribute__()

◆ _destroy_ht()

◆ _destroy_ht_trie()

◆ _empty_ht()

◆ _empty_ht_trie()

◆ _ht_check_trie_divergence()

◆ _ht_depth_first_search()

◆ _ht_find_longest_prefix_trie()

◆ _ht_get_double()

◆ _ht_get_double_trie()

◆ _ht_get_int()

◆ _ht_get_int_trie()

◆ _ht_get_node()

◆ _ht_get_node_trie()

◆ _ht_get_ptr()

◆ _ht_get_ptr_trie()

◆ _ht_get_string()

◆ _ht_get_string_trie()

◆ _ht_is_leaf_node_trie()

◆ _ht_new_double_node()

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

◆ _ht_print_trie()

◆ _ht_print_trie_helper()

◆ _ht_put_double()

◆ _ht_put_double_trie()

◆ _ht_put_int()

◆ _ht_put_int_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_search()

◆ _ht_search_trie()

◆ _ht_search_trie_helper()

◆ attribute()