Hashmap (Hash Table) API More...

Topics
	Hash Functions


	Hashmap Implementations

Data Structures
struct	sys_hashmap
	Generic Hashmap. More...

struct	sys_hashmap_iterator
	Generic Hashmap iterator interface. More...

struct	sys_hashmap_api
	Generic Hashmap API. More...

struct	sys_hashmap_config
	Generic Hashmap configuration. More...

struct	sys_hashmap_data
	Generic Hashmap data. More...

Macros
#define	SYS_HASHMAP_DEFINE_ADVANCED(_name, _api, _config_type, _data_type, _hash_func, _alloc_func, ...)
	Declare a Hashmap (advanced)

#define	SYS_HASHMAP_DEFINE_STATIC_ADVANCED(_name, _api, _config_type, _data_type, _hash_func, _alloc_func, ...)
	Declare a Hashmap statically (advanced)

#define	SYS_HASHMAP_DEFINE(_name)
	Declare a Hashmap.

#define	SYS_HASHMAP_DEFINE_STATIC(_name)
	Declare a Hashmap statically.

#define	SYS_HASHMAP_DEFAULT_ALLOCATOR sys_hashmap_default_allocator
	The default Hashmap allocator.

#define	SYS_HASHMAP_DEFAULT_LOAD_FACTOR 75
	The default Hashmap load factor (in hundredths)

#define	SYS_HASHMAP_CONFIG(_max_size, _load_factor)
	Initializer for `sys_hashmap_config`.

Typedefs
typedef void (	sys_hashmap_allocator_t) (void *ptr, size_t new_size)
	Allocator interface for sys_hashmap.

typedef void(*	sys_hashmap_iterator_t) (const struct sys_hashmap map, struct sys_hashmap_iterator it)
	In-place iterator constructor for sys_hashmap.

typedef void(*	sys_hashmap_callback_t) (uint64_t key, uint64_t value, void *cookie)
	Callback interface for sys_hashmap.

typedef void(*	sys_hashmap_clear_t) (struct sys_hashmap map, sys_hashmap_callback_t cb, void cookie)
	Clear all entries contained in a sys_hashmap.

typedef int(*	sys_hashmap_insert_t) (struct sys_hashmap map, uint64_t key, uint64_t value, uint64_t old_value)
	Insert a new entry into a sys_hashmap.

typedef bool(*	sys_hashmap_remove_t) (struct sys_hashmap map, uint64_t key, uint64_t value)
	Remove an entry from a sys_hashmap.

typedef bool(*	sys_hashmap_get_t) (const struct sys_hashmap map, uint64_t key, uint64_t value)
	Get a value from a sys_hashmap.

Functions
static void *	sys_hashmap_default_allocator (void *ptr, size_t size)

static void	sys_hashmap_foreach (const struct sys_hashmap map, sys_hashmap_callback_t cb, void cookie)
	Iterate over all values contained in a sys_hashmap.

static void	sys_hashmap_clear (struct sys_hashmap map, sys_hashmap_callback_t cb, void cookie)
	Clear all entries contained in a sys_hashmap.

static int	sys_hashmap_insert (struct sys_hashmap map, uint64_t key, uint64_t value, uint64_t old_value)
	Insert a new entry into a sys_hashmap.

static bool	sys_hashmap_remove (struct sys_hashmap map, uint64_t key, uint64_t value)
	Remove an entry from a sys_hashmap.

static bool	sys_hashmap_get (const struct sys_hashmap map, uint64_t key, uint64_t value)
	Get a value from a sys_hashmap.

static bool	sys_hashmap_contains_key (const struct sys_hashmap *map, uint64_t key)
	Check if `map` contains a value associated with `key`.

static size_t	sys_hashmap_size (const struct sys_hashmap *map)
	Query the number of entries contained within `map`.

static bool	sys_hashmap_is_empty (const struct sys_hashmap *map)
	Check if `map` is empty.

static uint8_t	sys_hashmap_load_factor (const struct sys_hashmap *map)
	Query the load factor of `map`.

static size_t	sys_hashmap_num_buckets (const struct sys_hashmap *map)
	Query the number of buckets used in `map`.

static bool	sys_hashmap_should_rehash (const struct sys_hashmap map, bool grow, size_t num_reserved, size_t new_num_buckets)
	Decide whether the Hashmap should be resized.

static bool	sys_hashmap_iterator_has_next (const struct sys_hashmap_iterator *it)
	Check if a Hashmap iterator has a next entry.

Detailed Description

Hashmap (Hash Table) API

Hashmaps (a.k.a Hash Tables) sacrifice space for speed. All operations on a Hashmap (insert, delete, search) are O(1) complexity (on average).

Macro Definition Documentation

◆ SYS_HASHMAP_CONFIG

#define SYS_HASHMAP_CONFIG	(		_max_size,
			_load_factor )

#include <zephyr/sys/hash_map_api.h>

Value:

        {                                                                                          \
                .max_size = (size_t)_max_size, .load_factor = (uint8_t)_load_factor,               \
                .initial_n_buckets = NHPOT(DIV_ROUND_UP(100, _load_factor)),                   \
        }

Initializer for sys_hashmap_config.

This macro helps to initialize a structure of type sys_hashmap_config.

Parameters

_max_size	Maximum number of entries
_load_factor	Maximum load factor of expressed in hundredths

◆ SYS_HASHMAP_DEFAULT_ALLOCATOR

#define SYS_HASHMAP_DEFAULT_ALLOCATOR sys_hashmap_default_allocator

#include <zephyr/sys/hash_map.h>

The default Hashmap allocator.

◆ SYS_HASHMAP_DEFAULT_LOAD_FACTOR

#define SYS_HASHMAP_DEFAULT_LOAD_FACTOR 75

#include <zephyr/sys/hash_map.h>

The default Hashmap load factor (in hundredths)

◆ SYS_HASHMAP_DEFINE

#define SYS_HASHMAP_DEFINE ( _name )

#include <zephyr/sys/hash_map.h>

Value:

SYS_HASHMAP_DEFAULT_DEFINE(_name)

Declare a Hashmap.

Declare a Hashmap with default parameters.

Parameters

_name Name of the Hashmap.

◆ SYS_HASHMAP_DEFINE_ADVANCED

#define SYS_HASHMAP_DEFINE_ADVANCED	(	_name,
		_api,
		_config_type,
		_data_type,
		_hash_func,
		_alloc_func,
		... )

#include <zephyr/sys/hash_map.h>

Value:

        const struct _config_type _name##_config = __VA_ARGS__;                                    \
        struct _data_type _name##_data;                                                            \
        struct sys_hashmap _name = {                                                               \
                .api = (const struct sys_hashmap_api *)(_api),                                     \
                .config = (const struct sys_hashmap_config *)&_name##_config,                      \
                .data = (struct sys_hashmap_data *)&_name##_data,                                  \
                .hash_func = (_hash_func),                                                         \
                .alloc_func = (_alloc_func),                                                       \
        }

Declare a Hashmap (advanced)

Declare a Hashmap with control over advanced parameters.

Note: The allocator _alloc is used for allocating internal Hashmap entries and does not interact with any user-provided keys or values.

Parameters

_name	Name of the Hashmap.
_api	API pointer of type sys_hashmap_api.
_config_type	Variant of sys_hashmap_config.
_data_type	Variant of sys_hashmap_data.
_hash_func	Hash function pointer of type sys_hash_func32_t.
_alloc_func	Allocator function pointer of type sys_hashmap_allocator_t.
...	Variant-specific details for `_config_type`.

◆ SYS_HASHMAP_DEFINE_STATIC

#define SYS_HASHMAP_DEFINE_STATIC ( _name )

#include <zephyr/sys/hash_map.h>

Value:

SYS_HASHMAP_DEFAULT_DEFINE_STATIC(_name)

Declare a Hashmap statically.

Declare a Hashmap statically with default parameters.

Parameters

_name Name of the Hashmap.

◆ SYS_HASHMAP_DEFINE_STATIC_ADVANCED

#define SYS_HASHMAP_DEFINE_STATIC_ADVANCED	(	_name,
		_api,
		_config_type,
		_data_type,
		_hash_func,
		_alloc_func,
		... )

#include <zephyr/sys/hash_map.h>

Value:

        static const struct _config_type _name##_config = __VA_ARGS__;                             \
        static struct _data_type _name##_data;                                                     \
        static struct sys_hashmap _name = {                                                        \
                .api = (const struct sys_hashmap_api *)(_api),                                     \
                .config = (const struct sys_hashmap_config *)&_name##_config,                      \
                .data = (struct sys_hashmap_data *)&_name##_data,                                  \
                .hash_func = (_hash_func),                                                         \
                .alloc_func = (_alloc_func),                                                       \
        }

Declare a Hashmap statically (advanced)

Declare a Hashmap statically with control over advanced parameters.

Note: The allocator _alloc is used for allocating internal Hashmap entries and does not interact with any user-provided keys or values.

Parameters

_name	Name of the Hashmap.
_api	API pointer of type sys_hashmap_api.
_config_type	Variant of sys_hashmap_config.
_data_type	Variant of sys_hashmap_data.
_hash_func	Hash function pointer of type sys_hash_func32_t.
_alloc_func	Allocator function pointer of type sys_hashmap_allocator_t.
...	Variant-specific details for `_config_type`.

Typedef Documentation

◆ sys_hashmap_allocator_t

typedef void *(* sys_hashmap_allocator_t) (void *ptr, size_t new_size)

#include <zephyr/sys/hash_map_api.h>

Allocator interface for sys_hashmap.

The Hashmap allocator can be any allocator that behaves similarly to realloc() with the additional specification that the allocator behaves like free() when new_size is zero.

Parameters

ptr	Previously allocated memory region or `NULL` to make a new vallocation.
new_size	the new size of the allocation, in bytes.

See also: realloc

◆ sys_hashmap_callback_t

typedef void(* sys_hashmap_callback_t) (uint64_t key, uint64_t value, void *cookie)

#include <zephyr/sys/hash_map_api.h>

Callback interface for sys_hashmap.

This callback is used by some Hashmap methods.

Parameters

key	Key corresponding to `value`
value	Value corresponding to `key`
cookie	User-specified variable

◆ sys_hashmap_clear_t

typedef void(* sys_hashmap_clear_t) (struct sys_hashmap *map, sys_hashmap_callback_t cb, void *cookie)

#include <zephyr/sys/hash_map_api.h>

Clear all entries contained in a sys_hashmap.

Note: If the values in a particular Hashmap are

Parameters

map	Hashmap to clear
cb	Callback to call for each entry
cookie	User-specified variable

◆ sys_hashmap_get_t

typedef bool(* sys_hashmap_get_t) (const struct sys_hashmap *map, uint64_t key, uint64_t *value)

#include <zephyr/sys/hash_map_api.h>

Get a value from a sys_hashmap.

Look-up the uint64_t associated with key, if one exists.

Parameters

map	Hashmap to search through
key	Key with which to search `map`
value	Location to store a potential value associated with `key` or `NULL`

Return values

true	if `map` contains a value associated with `key`.
false	if `map` does not contain a value associated with `key`.

◆ sys_hashmap_insert_t

typedef int(* sys_hashmap_insert_t) (struct sys_hashmap *map, uint64_t key, uint64_t value, uint64_t *old_value)

#include <zephyr/sys/hash_map_api.h>

Insert a new entry into a sys_hashmap.

Insert a new key - value pair into map.

Parameters

map	Hashmap to insert into
key	Key to associate with `value`
value	Value to associate with `key`
old_value	Location to store the value previously associated with `key` or `NULL`

Return values

0	if `value` was inserted for an existing key, in which case `old_value` will contain the previous value
1	if a new entry was inserted for the `key` - `value` pair
-ENOMEM	if memory allocation failed

◆ sys_hashmap_iterator_t

typedef void(* sys_hashmap_iterator_t) (const struct sys_hashmap *map, struct sys_hashmap_iterator *it)

#include <zephyr/sys/hash_map_api.h>

In-place iterator constructor for sys_hashmap.

Construct an iterator, it, for map.

Parameters

map	Hashmap to iterate over.
it	Iterator to initialize.

◆ sys_hashmap_remove_t

typedef bool(* sys_hashmap_remove_t) (struct sys_hashmap *map, uint64_t key, uint64_t *value)

#include <zephyr/sys/hash_map_api.h>

Remove an entry from a sys_hashmap.

Erase the entry associated with key key, if one exists.

Parameters

map	Hashmap to remove from
key	Key to remove from `map`
value	Location to store a potential value associated with `key` or `NULL`

Return values

true	if `map` was modified as a result of this operation.
false	if `map` does not contain a value associated with `key`.

Function Documentation

◆ sys_hashmap_clear()

static void sys_hashmap_clear	(	struct sys_hashmap *	map,
		sys_hashmap_callback_t	cb,
		void *	cookie )

inlinestatic

#include <zephyr/sys/hash_map.h>

Clear all entries contained in a sys_hashmap.

Note: If the values in a particular Hashmap are

Parameters

map	Hashmap to clear
cb	Callback to call for each entry
cookie	User-specified variable

◆ sys_hashmap_contains_key()

static bool sys_hashmap_contains_key	(	const struct sys_hashmap *	map,
		uint64_t	key )

inlinestatic

#include <zephyr/sys/hash_map.h>

Check if map contains a value associated with key.

Parameters

map	Hashmap to search through
key	Key with which to search `map`

Return values

true	if `map` contains a value associated with `key`.
false	if `map` does not contain a value associated with `key`.

◆ sys_hashmap_default_allocator()

static void * sys_hashmap_default_allocator	(	void *	ptr,
		size_t	size )

inlinestatic

#include <zephyr/sys/hash_map.h>

◆ sys_hashmap_foreach()

static void sys_hashmap_foreach	(	const struct sys_hashmap *	map,
		sys_hashmap_callback_t	cb,
		void *	cookie )

inlinestatic

#include <zephyr/sys/hash_map.h>

Iterate over all values contained in a sys_hashmap.

Parameters

map	Hashmap to iterate over
cb	Callback to call for each entry
cookie	User-specified variable

◆ sys_hashmap_get()

static bool sys_hashmap_get	(	const struct sys_hashmap *	map,
		uint64_t	key,
		uint64_t *	value )

inlinestatic

#include <zephyr/sys/hash_map.h>

Get a value from a sys_hashmap.

Look-up the uint64_t associated with key, if one exists.

Parameters

map	Hashmap to search through
key	Key with which to search `map`
value	Location to store a potential value associated with `key` or `NULL`

Return values

true	if `map` contains a value associated with `key`.
false	if `map` does not contain a value associated with `key`.

◆ sys_hashmap_insert()

static int sys_hashmap_insert	(	struct sys_hashmap *	map,
		uint64_t	key,
		uint64_t	value,
		uint64_t *	old_value )

inlinestatic

#include <zephyr/sys/hash_map.h>

Insert a new entry into a sys_hashmap.

Insert a new key - value pair into map.

Parameters

map	Hashmap to insert into
key	Key to associate with `value`
value	Value to associate with `key`
old_value	Location to store the value previously associated with `key` or `NULL`

Return values

0	if `value` was inserted for an existing key, in which case `old_value` will contain the previous value
1	if a new entry was inserted for the `key` - `value` pair
-ENOMEM	if memory allocation failed
-ENOSPC	if the size limit has been reached

◆ sys_hashmap_is_empty()

static bool sys_hashmap_is_empty ( const struct sys_hashmap * map )

inlinestatic

#include <zephyr/sys/hash_map.h>

Check if map is empty.

Parameters

map	Hashmap to query

Return values

true	if `map` is empty.
false	if `map` is not empty.

◆ sys_hashmap_iterator_has_next()

static bool sys_hashmap_iterator_has_next ( const struct sys_hashmap_iterator * it )

inlinestatic

#include <zephyr/sys/hash_map_api.h>

Check if a Hashmap iterator has a next entry.

Parameters

it	Hashmap iterator

Returns: true if there is a next entry; false if there is no next entry

◆ sys_hashmap_load_factor()

static uint8_t sys_hashmap_load_factor ( const struct sys_hashmap * map )

inlinestatic

#include <zephyr/sys/hash_map.h>

Query the load factor of map.

Note: To convert the load factor to a floating-point value use sys_hash_load_factor(map) / 100.0f.

Parameters

map	Hashmap to query

Returns: Load factor of map expressed in hundredths.

◆ sys_hashmap_num_buckets()

static size_t sys_hashmap_num_buckets ( const struct sys_hashmap * map )

inlinestatic

#include <zephyr/sys/hash_map.h>

Query the number of buckets used in map.

Parameters

map	Hashmap to query

Returns: Number of buckets used in map

◆ sys_hashmap_remove()

static bool sys_hashmap_remove	(	struct sys_hashmap *	map,
		uint64_t	key,
		uint64_t *	value )

inlinestatic

#include <zephyr/sys/hash_map.h>

Remove an entry from a sys_hashmap.

Erase the entry associated with key key, if one exists.

Parameters

map	Hashmap to remove from
key	Key to remove from `map`
value	Location to store a potential value associated with `key` or `NULL`

Return values

true	if `map` was modified as a result of this operation.
false	if `map` does not contain a value associated with `key`.

◆ sys_hashmap_should_rehash()

static bool sys_hashmap_should_rehash	(	const struct sys_hashmap *	map,
		bool	grow,
		size_t	num_reserved,
		size_t *	new_num_buckets )

inlinestatic

#include <zephyr/sys/hash_map.h>

Decide whether the Hashmap should be resized.

This is a simple opportunistic method that implementations can choose to use. It will grow and shrink the Hashmap by a factor of 2 when insertion / removal would exceed / fall into the specified load factor.

Note: Users should call this prior to inserting a new key-value pair and after removing a key-value pair.; The number of reserved entries is implementation-defined, but it is only considered as part of the load factor when growing the hash table.

Parameters

	map	Hashmap to examine
	grow	true if an entry is to be added. false if an entry has been removed
	num_reserved	the number of reserved entries
[out]	new_num_buckets	variable Hashmap size

Returns: true if the Hashmap should be rehashed; false if the Hashmap should not be rehashed

◆ sys_hashmap_size()

static size_t sys_hashmap_size ( const struct sys_hashmap * map )

inlinestatic

#include <zephyr/sys/hash_map.h>

Query the number of entries contained within map.

Parameters

map	Hashmap to search through

Returns: the number of entries contained within map.

Topics

Data Structures

Macros

Typedefs

Functions

Detailed Description

Macro Definition Documentation

◆ SYS_HASHMAP_CONFIG

◆ SYS_HASHMAP_DEFAULT_ALLOCATOR

◆ SYS_HASHMAP_DEFAULT_LOAD_FACTOR

◆ SYS_HASHMAP_DEFINE

◆ SYS_HASHMAP_DEFINE_ADVANCED

◆ SYS_HASHMAP_DEFINE_STATIC

◆ SYS_HASHMAP_DEFINE_STATIC_ADVANCED

Typedef Documentation

◆ sys_hashmap_allocator_t

◆ sys_hashmap_callback_t

◆ sys_hashmap_clear_t

◆ sys_hashmap_get_t

◆ sys_hashmap_insert_t

◆ sys_hashmap_iterator_t

◆ sys_hashmap_remove_t

Function Documentation

◆ sys_hashmap_clear()

◆ sys_hashmap_contains_key()

◆ sys_hashmap_default_allocator()

◆ sys_hashmap_foreach()

◆ sys_hashmap_get()

◆ sys_hashmap_insert()

◆ sys_hashmap_is_empty()

◆ sys_hashmap_iterator_has_next()

◆ sys_hashmap_load_factor()

◆ sys_hashmap_num_buckets()

◆ sys_hashmap_remove()

◆ sys_hashmap_should_rehash()

◆ sys_hashmap_size()