Hashmap

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.