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
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)
	Retrieve an integral value in the hash table, at the given key.

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

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)
	node creation, HASH_CLASSIC mode

HASH_NODE *	_ht_new_node (const 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), void (duplicator)(void ptr))
	node creation, HASH_CLASSIC mode, pointer to string value

HASH_NODE *	_ht_new_string_node (HASH_TABLE table, const char key, const 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)
	put an integral value with given key in the targeted hash table [CLASSIC HASH TABLE)

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

int	_ht_put_ptr (HASH_TABLE table, const char key, void ptr, void(destructor)(void ptr), void (duplicator)(void ptr))
	put a pointer value 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), void (duplicator)(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

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

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

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

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

HASH_TABLE *	ht_duplicate (HASH_TABLE *table)
	duplicate a hash table (all pointers should have a duplicator func set)

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)
	get node at 'key' from 'table'

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 (const HASH_NODE *node)
	get the type of a node , text version

int	ht_optimize (HASH_TABLE **table)
	try an automatic optimization of the table (HASH_CLASSIC mode only)

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)
	put an integral value with given key in the targeted hash table

int	ht_put_ptr (HASH_TABLE table, const char key, void ptr, void(destructor)(void ptr), void (duplicator)(void ptr))
	put an arbitrary pointer 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), void (duplicator)(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)
	test if number is a prime number or not

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)
	compute next prime number after 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 859 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 886 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 890 of file n_hash.c.

◆ ROTL32

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

32 bit rotate left

Definition at line 857 of file n_hash.c.

◆ ROTL64

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

64 bit rotate left

Definition at line 855 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 1889 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 729 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 1870 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 713 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()

size_t _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 143 of file n_hash.c.

References __n_assert, HASH_TABLE::alphabet_length, HASH_TABLE::alphabet_offset, HASH_NODE::children, key, 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 835 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 178 of file n_hash.c.

References __n_assert, _ht_check_trie_divergence(), key, Malloc, 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 1743 of file n_hash.c.

References __n_assert, _ht_get_node(), HASH_NODE::data, HASH_DATA::fval, HASH_DOUBLE, ht_node_type(), key, 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 631 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, key, 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
	)

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

References __n_assert, _ht_get_node(), HASH_NODE::data, HASH_INT, ht_node_type(), HASH_DATA::ival, key, 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_int_trie()

int _ht_get_int_trie	(	HASH_TABLE *	table,
		const char *	key,
		int64_t *	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 603 of file n_hash.c.

References __n_assert, _ht_get_node_trie(), HASH_NODE::data, HASH_INT, ht_node_type(), HASH_NODE::is_leaf, HASH_DATA::ival, key, 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_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 1339 of file n_hash.c.

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

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

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

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

References __n_assert, _ht_get_node(), HASH_NODE::data, HASH_PTR, ht_node_type(), key, 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 687 of file n_hash.c.

References __n_assert, _ht_get_node_trie(), HASH_NODE::data, HASH_PTR, ht_node_type(), HASH_NODE::is_leaf, key, 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 1799 of file n_hash.c.

References __n_assert, _ht_get_node(), HASH_NODE::data, HASH_STRING, ht_node_type(), key, 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 659 of file n_hash.c.

References __n_assert, _ht_get_node_trie(), HASH_NODE::data, HASH_STRING, ht_node_type(), HASH_NODE::is_leaf, key, 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 84 of file n_hash.c.

References __n_assert, HASH_TABLE::alphabet_length, HASH_TABLE::alphabet_offset, HASH_NODE::children, HASH_NODE::is_leaf, key, 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 1428 of file n_hash.c.

References __n_assert, _ht_new_node(), HASH_NODE::data, HASH_DATA::fval, HASH_DOUBLE, key, 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
	)

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

References __n_assert, _ht_new_node(), HASH_NODE::data, HASH_INT, HASH_DATA::ival, key, LOG_ERR, n_log, and HASH_NODE::type.

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	(	const 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 1370 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, key, 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_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 50 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, key, 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_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,
		void ()(void *ptr)	duplicator
	)

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
duplicator	function pointer to a duplicator of value type (or NULL)

Returns: NULL or a new HASH_NODE *

Definition at line 1499 of file n_hash.c.

References __n_assert, _ht_new_node(), HASH_NODE::data, HASH_NODE::destroy_func, HASH_NODE::duplicate_func, HASH_PTR, key, 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,
		const 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 1450 of file n_hash.c.

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

Referenced by _ht_put_string().

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

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

Referenced by _ht_put_string_ptr().

Here is the call graph for this function:

Here is the caller 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 108 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_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 1910 of file n_hash.c.

References __n_assert, HASH_TABLE::hash_table, ht_foreach, and HASH_NODE::key.

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 778 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 744 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 1557 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(), key, 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 332 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, FreeNoLog, HASH_DATA::fval, HASH_DOUBLE, HASH_NODE::is_leaf, key, 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
	)

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

References __n_assert, _ht_get_node(), _ht_new_int_node(), _ht_node_destroy(), HASH_NODE::data, HASH_INT, HASH_TABLE::hash_table, HASH_NODE::hash_value, ht_node_type(), HASH_DATA::ival, key, 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_int_trie()

int _ht_put_int_trie	(	HASH_TABLE *	table,
		const char *	key,
		int64_t	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 277 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, FreeNoLog, HASH_INT, HASH_NODE::is_leaf, HASH_DATA::ival, key, 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_ptr()

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

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
duplicator	Pointer to the ptr type duplicator function. Leave to NULL if there isn't

Returns: TRUE or FALSE

Definition at line 1593 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_NODE::duplicate_func, HASH_PTR, HASH_TABLE::hash_table, HASH_NODE::hash_value, ht_node_type(), key, 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,
		void ()(void *ptr)	duplicator
	)

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
duplicator	the duplicate func for ptr or NULL

Returns: TRUE or FALSE

Definition at line 511 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_NODE::destroy_func, HASH_NODE::duplicate_func, FreeNoLog, HASH_PTR, HASH_NODE::is_leaf, key, 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 1635 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(), key, 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 1679 of file n_hash.c.

References __n_assert, _ht_get_node(), _ht_new_string_ptr_node(), _ht_node_destroy(), HASH_NODE::data, Free, HASH_STRING, HASH_TABLE::hash_table, HASH_NODE::hash_value, ht_node_type(), key, 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 454 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, FreeNoLog, HASH_STRING, HASH_NODE::is_leaf, key, 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 387 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, FreeNoLog, HASH_STRING, HASH_NODE::is_leaf, key, 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 1825 of file n_hash.c.

References __n_assert, _ht_node_destroy(), HASH_TABLE::hash_table, key, 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 210 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, key, LOG_ERR, n_log, HASH_TABLE::nb_keys, and HASH_TABLE::root.

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

References __n_assert, ht_foreach, HASH_NODE::key, list_destroy(), list_push(), MAX_LIST_ITEMS, LIST::nb_items, 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 815 of file n_hash.c.

References __n_assert, _ht_search_trie_helper(), list_destroy(), MAX_LIST_ITEMS, LIST::nb_items, new_generic_list(), 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 795 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:

◆ fmix32()

uint32_t fmix32 ( uint32_t h )

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

Parameters

h value

Returns: mixed value

Definition at line 930 of file n_hash.c.

Referenced by MurmurHash3_x86_128(), and MurmurHash3_x86_32().

Here is the caller graph for this function:

◆ fmix64()

uint64_t fmix64 ( uint64_t k )

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

Parameters

k value

Returns: mixed value

Definition at line 945 of file n_hash.c.

References BIG_CONSTANT.

Referenced by MurmurHash3_x64_128().

Here is the caller graph for this function:

◆ getblock32()

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

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

Parameters

p	value
i	position

Returns: value at position inside block

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

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

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

Parameters

p	value
i	position

Returns: value at position inside block

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