hash_function.h File Reference

#include <stddef.h>
#include <stdint.h>
#include <zephyr/sys/__assert.h>
#include <zephyr/sys/util_macro.h>

Go to the source code of this file.

Typedefs
typedef uint32_t(*	sys_hash_func32_t) (const void *str, size_t n)
	32-bit Hash function interface More...

Functions
static uint32_t	sys_hash32_identity (const void *str, size_t n)
	The naive identity hash function. More...
uint32_t	sys_hash32_djb2 (const void *str, size_t n)
	Daniel J. Bernstein's hash function. More...
uint32_t	sys_hash32_murmur3 (const void *str, size_t n)
	Murmur3 hash function. More...
static uint32_t	sys_hash32 (const void *str, size_t n)
	System default 32-bit hash function. More...

Typedef Documentation

sys_hash_func32_t

typedef uint32_t(* sys_hash_func32_t) (const void *str, size_t n)

32-bit Hash function interface

Hash functions are used to map data from an arbitrarily large space to a (typically smaller) fixed-size space. For a given input, a hash function will consistently generate the same, semi-unique numerical value. Even for marginally different data, a good hash function will distribute the entropy almost evenly over all bits in the hashed value when combined with modulo arithmetic over a finite-sized numeric field.

Parameters

str	a string of input data
n	the number of bytes in str

Returns

the numeric hash associated with str

Function Documentation

sys_hash32()

static uint32_t sys_hash32 ( const void *  str, size_t  n  )

inlinestatic

System default 32-bit hash function.

Parameters

str	a string of input data
n	the number of bytes in str

Returns

the numeric hash associated with str

sys_hash32_djb2()

uint32_t sys_hash32_djb2	(	const void *	str,
		size_t	n
	)

Daniel J. Bernstein's hash function.

Some notes:

• normally, this hash function is used on NUL-terminated strings
• it has been modified to support arbitrary sequences of bytes
• it has been modified to use XOR rather than addition

Parameters

str	a string of input data
n	the number of bytes in str

Returns

the numeric hash associated with str

Note

enable with CONFIG_SYS_HASH_FUNC32_DJB2

See also

https://theartincode.stanis.me/008-djb2/

sys_hash32_identity()

static uint32_t sys_hash32_identity ( const void *  str, size_t  n  )

inlinestatic

The naive identity hash function.

This hash function requires that n is equal to the size of a primitive type, such as [u]int8_t, [u]int16_t, [u]int32_t, [u]int64_t, float, double, or void *, and that the alignment of str agrees with that of the respective native type.

Note

The identity hash function is used for testing sys_hashmap.

Parameters

str	a string of input data
n	the number of bytes in str

Returns

the numeric hash associated with str

sys_hash32_murmur3()

uint32_t sys_hash32_murmur3	(	const void *	str,
		size_t	n
	)

Murmur3 hash function.

Parameters

str	a string of input data
n	the number of bytes in str

Returns

the numeric hash associated with str

Note

enable with CONFIG_SYS_HASH_FUNC32_MURMUR3

See also

https://en.wikipedia.org/wiki/MurmurHash