n_hash.h File Reference

Hash functions and table. More...

#include <string.h>
#include <stdint.h>
#include "n_common.h"
#include "n_list.h"

Include dependency graph for n_hash.h:

This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Data Structures
union	HASH_DATA
	union of the possibles data values of a node More...
struct	HASH_NODE
	structure of a hash table node More...
struct	HASH_TABLE
	structure of a hash table More...

Macros
#define	HASH_CLASSIC   128
	Murmur hash using hash key string, hash key numeric value, index table with lists of elements.
#define	HASH_DOUBLE   2
	value of double type inside the hash node
#define	HASH_INT   1
	compatibility with existing rot func
#define	HASH_INT_TYPE   int64_t
	type of a HASH_INT in 64 bits
#define	HASH_PTR   8
	value of pointer type inside the hash node
#define	HASH_STRING   4
	value of char * type inside the hash node
#define	HASH_TRIE   256
	TRIE tree using hash key string.
#define	HASH_UNKNOWN   16
	value of unknow type inside the hash node
#define	hash_val(node, type)    ((node && node->ptr) ? ((type*)(((HASH_NODE*)node->ptr)->data.ptr)) : NULL)
	Cast a HASH_NODE element.
#define	HASH_VAL(node, type)    ((node && node->data.ptr) ? ((type*)node->data.ptr) : NULL)
	Cast a HASH_NODE element.
#define	ht_foreach(__ITEM_, __HASH_)
	ForEach macro helper (classic / old)
#define	HT_FOREACH(__ITEM_, __HASH_, ...)
	ForEach macro helper.
#define	HT_FOREACH_R(__ITEM_, __HASH_, __ITERATOR, ...)
	ForEach macro helper.
#define	ht_foreach_r(__ITEM_, __HASH_, __ITERATOR_)
	ForEach macro helper, reentrant (classic / old)
#define	MurmurHash(__key, __len, __seed, __out)   MurmurHash3_x64_128(__key, __len, __seed, __out)
	Murmur hash macro helper 64 bits.

Typedefs
typedef size_t	HASH_VALUE
	type of a HASH_VALUE

Functions
int	destroy_ht (HASH_TABLE **table)
	destroy a hash table and free all resources
int	empty_ht (HASH_TABLE *table)
	empty a hash table, freeing all nodes
HASH_TABLE *	ht_duplicate (HASH_TABLE *table)
	duplicate a hash table
LIST *	ht_get_completion_list (HASH_TABLE *table, const char *keybud, size_t max_results)
	get a list of key completions matching the given prefix
int	ht_get_double (HASH_TABLE *table, const char *key, double *val)
	get a double value from the hash table by key
int	ht_get_int (HASH_TABLE *table, const char *key, int64_t *val)
	get an integer value from the hash table by key
HASH_NODE *	ht_get_node (HASH_TABLE *table, const char *key)
	get the HASH_NODE associated with the given key
HASH_NODE *	ht_get_node_ex (HASH_TABLE *table, HASH_VALUE hash_value)
	get a HASH_NODE by numeric hash value
size_t	ht_get_optimal_size (HASH_TABLE *table)
	compute the optimal size for the hash table
int	ht_get_ptr (HASH_TABLE *table, const char *key, void **val)
	get a pointer value from the hash table by key
int	ht_get_ptr_ex (HASH_TABLE *table, HASH_VALUE hash_value, void **val)
	get a pointer value by numeric hash value
int	ht_get_string (HASH_TABLE *table, const char *key, char **val)
	get a string value from the hash table by key
int	ht_get_table_collision_percentage (HASH_TABLE *table)
	get the collision percentage of the hash table
char *	ht_node_type (const HASH_NODE *node)
	return the type of a hash node as a string
int	ht_optimize (HASH_TABLE **table)
	optimize a hash table by resizing to the optimal size
void	ht_print (HASH_TABLE *table)
	print the contents of a hash table
int	ht_put_double (HASH_TABLE *table, const char *key, double value)
	put a double value into the hash table
int	ht_put_int (HASH_TABLE *table, const char *key, int64_t value)
	put an integer value into the 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 into the hash table with destructor and duplicator
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 by numeric hash value
int	ht_put_string (HASH_TABLE *table, const char *key, char *string)
	put a string value (duplicated) into the hash table
int	ht_put_string_ptr (HASH_TABLE *table, const char *key, char *string)
	put a string pointer into the hash table without copying
int	ht_remove (HASH_TABLE *table, const char *key)
	remove a node from the hash table by key
int	ht_remove_ex (HASH_TABLE *table, HASH_VALUE hash_value)
	remove a node by numeric hash value
int	ht_resize (HASH_TABLE **table, size_t size)
	resize a hash table to the given size
LIST *	ht_search (HASH_TABLE *table, int(*node_is_matching)(HASH_NODE *node))
	search the hash table for nodes matching a predicate
int	is_prime (size_t nb)
	check if a number is prime
void	MurmurHash3_x64_128 (const void *key, const size_t len, const uint64_t seed, void *out)
	compute a 128-bit MurmurHash3 hash for x64
void	MurmurHash3_x86_128 (const void *key, const size_t len, const uint32_t seed, void *out)
	compute a 128-bit MurmurHash3 hash for x86
void	MurmurHash3_x86_32 (const void *key, const size_t len, const uint32_t seed, void *out)
	compute a 32-bit MurmurHash3 hash
HASH_TABLE *	new_ht (size_t size)
	create a new classic hash table of the given size
HASH_TABLE *	new_ht_trie (size_t alphabet_size, size_t alphabet_offset)
	create a new trie hash table with the given alphabet size and offset
size_t	next_prime (size_t nb)
	return the next prime number greater than or equal to nb

Detailed Description

Hash functions and table.

Author

Castagnier Mickael

Version

2.0

Date

16/03/2015

Definition in file n_hash.h.