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

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.

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 (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)
	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))
	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)
	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 792 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 819 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 823 of file n_hash.c.

◆ ROTL32

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

32 bit rotate left

Definition at line 790 of file n_hash.c.

◆ ROTL64

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

64 bit rotate left

Definition at line 788 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 1806 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 662 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 1785 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 646 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 123 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 768 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(), key, 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 1658 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 564 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 1630 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 536 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 1266 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 503 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 1687 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 620 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 1714 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 592 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 66 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 1357 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 1335 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	(	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 1299 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 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, 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
	)

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

References __n_assert, _ht_new_node(), HASH_NODE::data, HASH_NODE::destroy_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,
		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 1379 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(), 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 1404 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.

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_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 1827 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 711 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 677 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 1484 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 303 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, 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 1450 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 254 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_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
	)

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 1519 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(), 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
	)

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 460 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, 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 1558 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 1594 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_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 411 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, 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 351 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, 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 1740 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 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, 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_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 1843 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 748 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 728 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 863 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 878 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 840 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 852 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()