Hash functions and table. More...

#include "nilorea/n_common.h"
#include "nilorea/n_log.h"
#include "nilorea/n_hash.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 More...

#define	BYTESWAP32(x)
	32 bits bytes swap More...

#define	BYTESWAP64(x)
	32 bits bytes swap More...

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

HASH_NODE *	_ht_new_int_node (HASH_TABLE table, const char key, int value)
	node creation, HASH_CLASSIC mode More...

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

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

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

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

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

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

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

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

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

int	_ht_put_double (HASH_TABLE table, const char key, double value)
	put a double value with given key in the targeted hash table More...

int	_ht_put_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) More...

int	_ht_put_int (HASH_TABLE table, const char key, int value)
	put an integral value with given key in the targeted hash table [CLASSIC HASH TABLE) More...

int	_ht_put_int_trie (HASH_TABLE table, const char key, int value)
	put an integral value with given key in the targeted hash table [TRIE HASH TABLE) More...

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

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) More...

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) More...

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) More...

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) More...

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) More...

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

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

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

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

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

int	destroy_ht (HASH_TABLE **table)
	empty a table and destroy it More...

int	empty_ht (HASH_TABLE *table)
	empty a table More...

static FORCE_INLINE uint32_t	fmix32 (uint32_t h)
	Finalization mix - force all bits of a hash block to avalanche (from murmur's author) More...

static FORCE_INLINE uint64_t	fmix64 (uint64_t k)
	Finalization mix - force all bits of a hash block to avalanche (from murmur's author) More...

static FORCE_INLINE uint32_t	getblock32 (const uint32_t *p, const size_t i)
	Block read - modified from murmur's author, ajusted byte endianess More...

static FORCE_INLINE uint64_t	getblock64 (const uint64_t *p, const size_t i)
	Block read - modified from murmur's author, ajusted byte endianess. More...

LIST *	ht_get_completion_list (HASH_TABLE table, const char keybud, size_t max_results)
	get next matching keys in table tree More...

int	ht_get_double (HASH_TABLE table, const char key, double *val)
	get double at 'key' from 'table' More...

int	ht_get_int (HASH_TABLE table, const char key, int *val)
	get node at 'key' from 'table' More...

HASH_NODE *	ht_get_node (HASH_TABLE table, const char key)
	get node at 'key' from 'table' More...

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) More...

int	ht_get_optimal_size (HASH_TABLE *table)
	get optimal array size based on nb=(number_of_key*1.3) && if( !isprime(nb) )nb=nextprime(nb) (HASH_CLASSIC mode only) More...

int	ht_get_ptr (HASH_TABLE table, const char key, void **val)
	get pointer at 'key' from 'table' More...

int	ht_get_ptr_ex (HASH_TABLE table, HASH_VALUE hash_value, void *val)
	Retrieve a pointer value in the hash table, at the given key. More...

int	ht_get_string (HASH_TABLE table, const char key, char **val)
	get string at 'key' from 'table' More...

int	ht_get_table_collision_percentage (HASH_TABLE *table)
	get table collision percentage (HASH_CLASSIC mode only) More...

char *	ht_node_type (HASH_NODE *node)
	get the type of a node , text version More...

int	ht_optimize (HASH_TABLE **table)
	try an automatic optimization of the table More...

void	ht_print (HASH_TABLE *table)
	print contents of table More...

int	ht_put_double (HASH_TABLE table, const char key, double value)
	put a double value with given key in the targeted hash table More...

int	ht_put_int (HASH_TABLE table, const char key, int value)
	put an integral value with given key in the targeted hash table More...

int	ht_put_ptr (HASH_TABLE table, const char key, void ptr, void(destructor)(void *ptr))
	put a pointer to the string value with given key in the targeted hash table More...

int	ht_put_ptr_ex (HASH_TABLE table, HASH_VALUE hash_value, void val, void(destructor)(void ptr))
	put a pointer value with given key in the targeted hash table (HASH_CLASSIC only) More...

int	ht_put_string (HASH_TABLE table, const char key, char *string)
	put a string value (copy/dup) with given key in the targeted hash table More...

int	ht_put_string_ptr (HASH_TABLE table, const char key, char *string)
	put a string value (pointer) with given key in the targeted hash table More...

int	ht_remove (HASH_TABLE table, const char key)
	remove and delete node at key in table More...

int	ht_remove_ex (HASH_TABLE *table, HASH_VALUE hash_value)
	Remove a key from a hash table (HASH_CLASSIC only) More...

int	ht_resize (HASH_TABLE **table, size_t size)
	rehash table according to size (HASH_CLASSIC mode only) More...

LIST *	ht_search (HASH_TABLE table, int(node_is_matching)(HASH_NODE *node))
	seach table for matching nodes More...

int	is_prime (int nb)
	test if number is a prime number or not More...

void	MurmurHash3_x64_128 (const void key, const size_t len, const uint64_t seed, void out)
	MurmurHash3 was written by Austin Appleby, and is placed in the public domain. More...

void	MurmurHash3_x86_128 (const void key, const int len, uint32_t seed, void out)
	MurmurHash3 was written by Austin Appleby, and is placed in the public domain. More...

void	MurmurHash3_x86_32 (const void key, int len, uint32_t seed, void out)
	MurmurHash3 was written by Austin Appleby, and is placed in the public domain. More...

HASH_TABLE *	new_ht (size_t size)
	Create a hash table with the given size. More...

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

int	next_prime (int nb)
	compute next prime number after nb More...

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

◆ BYTESWAP32

#define BYTESWAP32 ( x )

Value:

                                ((((x)&0xFF)<<24) \
                                |(((x)>>24)&0xFF) \
                                |(((x)&0x0000FF00)<<8)    \
                                |(((x)&0x00FF0000)>>8)    )

32 bits bytes swap

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

◆ ROTL32

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

32 bit rotate left

Definition at line 927 of file n_hash.c.

◆ ROTL64

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

64 bit rotate left

Definition at line 925 of file n_hash.c.

Function Documentation

◆ _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 2041 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 766 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 2013 of file n_hash.c.

References __n_assert, _ht_node_destroy(), and remove_list_node.

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

References __n_assert, _ht_new_node_trie(), and _ht_node_destroy().

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: TRUE or FALSE

Definition at line 508 of file n_hash.c.

References __n_assert, HASH_NODE::children, LOG_ERR, and n_log.

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

References __n_assert, _ht_depth_first_search(), and list_push().

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

References __n_assert, _ht_get_node(), HASH_DOUBLE, ht_node_type(), 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:

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

References __n_assert, _ht_get_node_trie(), HASH_DOUBLE, ht_node_type(), 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:

◆ _ht_get_int()

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

Retrieve an integral 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 integer

Returns: TRUE or FALSE.

Definition at line 1833 of file n_hash.c.

References __n_assert, _ht_get_node(), HASH_INT, ht_node_type(), 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:

◆ _ht_get_int_trie()

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

Retrieve an integral 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 integer

Returns: TRUE or FALSE.

Definition at line 380 of file n_hash.c.

References __n_assert, _ht_get_node_trie(), HASH_INT, ht_node_type(), 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:

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

References __n_assert, list_foreach, MurmurHash, and HASH_TABLE::size.

Referenced by _ht_get_double(), _ht_get_int(), _ht_get_ptr(), _ht_get_string(), _ht_put_double(), _ht_put_int(), _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 338 of file n_hash.c.

References __n_assert, LOG_DEBUG, and n_log.

Referenced by _ht_get_double_trie(), _ht_get_int_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 1898 of file n_hash.c.

References __n_assert, _ht_get_node(), HASH_PTR, ht_node_type(), 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:

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

References __n_assert, _ht_get_node_trie(), HASH_PTR, ht_node_type(), 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:

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

References __n_assert, _ht_get_node(), HASH_STRING, ht_node_type(), 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:

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

References __n_assert, _ht_get_node_trie(), HASH_STRING, ht_node_type(), 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:

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

References __n_assert, LOG_ERR, and n_log.

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

References __n_assert, _ht_new_node(), and HASH_DOUBLE.

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,
		int	value
	)

node creation, HASH_CLASSIC mode

Parameters

table	targeted table
key	key of new node
value	int value of key

Returns: NULL or a new HASH_NODE *

Definition at line 1518 of file n_hash.c.

References __n_assert, _ht_new_node(), and HASH_INT.

Referenced by _ht_put_int().

Here is the call graph for this function:

Here is the caller graph for this function:

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

References __n_assert, Free, LOG_ERR, Malloc, MurmurHash, and n_log.

Referenced by _ht_new_double_node(), _ht_new_int_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 31 of file n_hash.c.

References __n_assert, Free, LOG_ERR, Malloc, and n_log.

Referenced by _empty_ht_trie(), _ht_put_double_trie(), _ht_put_int_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 1606 of file n_hash.c.

References __n_assert, _ht_new_node(), and HASH_PTR.

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

References __n_assert, _ht_new_node(), and HASH_STRING.

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

References __n_assert, _ht_new_node(), and HASH_STRING.

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

References __n_assert, _ht_node_destroy(), Free, FreeNoLog, HASH_PTR, and HASH_STRING.

Referenced by _destroy_ht_trie(), _empty_ht(), _empty_ht_trie(), _ht_node_destroy(), _ht_put_double(), _ht_put_int(), _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 2068 of file n_hash.c.

References __n_assert, 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 826 of file n_hash.c.

References __n_assert, and _ht_print_trie_helper().

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

References _ht_print_trie_helper(), HASH_DOUBLE, HASH_INT, HASH_PTR, and HASH_STRING.

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

References __n_assert, _ht_get_node(), _ht_new_double_node(), _ht_node_destroy(), HASH_DOUBLE, ht_node_type(), list_push(), 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:

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

References __n_assert, _ht_new_node_trie(), HASH_DOUBLE, 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:

◆ _ht_put_int()

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

put an integral value with given key in the targeted hash table [CLASSIC HASH TABLE)

Parameters

table	targeted table
key	associated value's key
value	integral value to put

Returns: TRUE or FALSE

Definition at line 1630 of file n_hash.c.

References __n_assert, _ht_get_node(), _ht_new_int_node(), _ht_node_destroy(), HASH_INT, ht_node_type(), list_push(), 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:

◆ _ht_put_int_trie()

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

put an integral value with given key in the targeted hash table [TRIE HASH TABLE)

Parameters

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

Returns: TRUE or FALSE

Definition at line 71 of file n_hash.c.

References __n_assert, _ht_new_node_trie(), HASH_INT, 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:

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

References __n_assert, _ht_get_node(), _ht_new_ptr_node(), _ht_node_destroy(), HASH_PTR, ht_node_type(), list_push(), 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:

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

References __n_assert, _ht_new_node_trie(), HASH_PTR, 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:

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

References __n_assert, _ht_get_node(), _ht_new_string_node(), _ht_node_destroy(), Free, HASH_STRING, ht_node_type(), list_push(), 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:

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

References __n_assert, _ht_get_node(), _ht_new_string_node(), _ht_node_destroy(), Free, HASH_STRING, ht_node_type(), list_push(), 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:

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

References __n_assert, _ht_new_node_trie(), HASH_STRING, 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:

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

References __n_assert, _ht_new_node_trie(), HASH_STRING, 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:

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

References __n_assert, _ht_node_destroy(), list_foreach, LOG_ERR, MurmurHash, n_log, remove_list_node, and HASH_TABLE::size.

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

References __n_assert, _ht_find_longest_prefix_trie(), _ht_is_leaf_node_trie(), _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:

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

References __n_assert, ht_foreach, list_destroy(), list_push(), and new_generic_list().

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

References __n_assert, _ht_search_trie_helper(), list_destroy(), and new_generic_list().

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

References _ht_search_trie_helper(), 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:

◆ fmix32()

static FORCE_INLINE uint32_t fmix32 ( uint32_t h )

static

Finalization mix - force all bits of a hash block to avalanche (from murmur's author)

Parameters

h value

Returns: mixed value

Definition at line 1004 of file n_hash.c.

Referenced by MurmurHash3_x86_128(), and MurmurHash3_x86_32().

Here is the caller graph for this function:

◆ fmix64()

static FORCE_INLINE uint64_t fmix64 ( uint64_t k )

static

Finalization mix - force all bits of a hash block to avalanche (from murmur's author)

Parameters

k value

Returns: mixed value

Definition at line 1022 of file n_hash.c.

References BIG_CONSTANT.

Referenced by MurmurHash3_x64_128().

Here is the caller graph for this function:

◆ getblock32()

static FORCE_INLINE uint32_t getblock32	(	const uint32_t *	p,
		const size_t	i
	)

static

Block read - modified from murmur's author, ajusted byte endianess

Parameters

p	value
i	position

Returns: value at position inside block

Definition at line 983 of file n_hash.c.

References BYTESWAP32.

Referenced by MurmurHash3_x86_128(), and MurmurHash3_x86_32().

Here is the caller graph for this function:

◆ getblock64()

static FORCE_INLINE uint64_t getblock64	(	const uint64_t *	p,
		const size_t	i
	)

static

Block read - modified from murmur's author, ajusted byte endianess.

Parameters

p	value
i	position

Returns: value at position inside block

Definition at line 993 of file n_hash.c.

References BYTESWAP64.

Referenced by MurmurHash3_x64_128().

Here is the caller graph for this function:

Macros

Functions

Detailed Description

Macro Definition Documentation

◆ BIG_CONSTANT

◆ BYTESWAP32

◆ BYTESWAP64

◆ ROTL32

◆ ROTL64

Function Documentation

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

◆ fmix32()

◆ fmix64()

◆ getblock32()

◆ getblock64()