Zephyr API Documentation  3.6.99
A Scalable Open Source RTOS
Loading...
Searching...
No Matches

Hashmap (Hash Table) API. More...

Modules

 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)   SYS_HASHMAP_DEFAULT_DEFINE(_name)
 Declare a Hashmap.
 
#define SYS_HASHMAP_DEFINE_STATIC(_name)   SYS_HASHMAP_DEFAULT_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)), \
}
#define NHPOT(x)
Compute next highest power of two.
Definition: util.h:719
#define DIV_ROUND_UP(n, d)
Divide and round up.
Definition: util.h:336
Size of off_t must be equal or less than size of size_t
Definition: retained_mem.h:28
__UINT8_TYPE__ uint8_t
Definition: stdint.h:88

Initializer for sys_hashmap_config.

This macro helps to initialize a structure of type sys_hashmap_config.

Parameters
_max_sizeMaximum number of entries
_load_factorMaximum 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)    SYS_HASHMAP_DEFAULT_DEFINE(_name)

#include <zephyr/sys/hash_map.h>

Declare a Hashmap.

Declare a Hashmap with default parameters.

Parameters
_nameName 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), \
}
Generic Hashmap API.
Definition: hash_map_api.h:168
Generic Hashmap configuration.
Definition: hash_map_api.h:197
Generic Hashmap data.
Definition: hash_map_api.h:225
Generic Hashmap.
Definition: hash_map.h:124
sys_hash_func32_t hash_func
Hash function.
Definition: hash_map.h:132
const struct sys_hashmap_api * api
Hashmap API.
Definition: hash_map.h:126

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
_nameName of the Hashmap.
_apiAPI pointer of type sys_hashmap_api.
_config_typeVariant of sys_hashmap_config.
_data_typeVariant of sys_hashmap_data.
_hash_funcHash function pointer of type sys_hash_func32_t.
_alloc_funcAllocator function pointer of type sys_hashmap_allocator_t.
...Variant-specific details for _config_type.

◆ SYS_HASHMAP_DEFINE_STATIC

#define SYS_HASHMAP_DEFINE_STATIC (   _name)    SYS_HASHMAP_DEFAULT_DEFINE_STATIC(_name)

#include <zephyr/sys/hash_map.h>

Declare a Hashmap statically.

Declare a Hashmap statically with default parameters.

Parameters
_nameName 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
_nameName of the Hashmap.
_apiAPI pointer of type sys_hashmap_api.
_config_typeVariant of sys_hashmap_config.
_data_typeVariant of sys_hashmap_data.
_hash_funcHash function pointer of type sys_hash_func32_t.
_alloc_funcAllocator 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
ptrPreviously allocated memory region or NULL to make a new vallocation.
new_sizethe 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
keyKey corresponding to value
valueValue corresponding to key
cookieUser-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
mapHashmap to clear
cbCallback to call for each entry
cookieUser-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
mapHashmap to search through
keyKey with which to search map
valueLocation to store a potential value associated with key or NULL
Return values
trueif map contains a value associated with key.
falseif 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
mapHashmap to insert into
keyKey to associate with value
valueValue to associate with key
old_valueLocation to store the value previously associated with key or NULL
Return values
0if value was inserted for an existing key, in which case old_value will contain the previous value
1if a new entry was inserted for the key - value pair
-ENOMEMif 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
mapHashmap to iterate over.
itIterator 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
mapHashmap to remove from
keyKey to remove from map
valueLocation to store a potential value associated with key or NULL
Return values
trueif map was modified as a result of this operation.
falseif 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
mapHashmap to clear
cbCallback to call for each entry
cookieUser-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
mapHashmap to search through
keyKey with which to search map
Return values
trueif map contains a value associated with key.
falseif 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

◆ 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
mapHashmap to iterate over
cbCallback to call for each entry
cookieUser-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
mapHashmap to search through
keyKey with which to search map
valueLocation to store a potential value associated with key or NULL
Return values
trueif map contains a value associated with key.
falseif 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
mapHashmap to insert into
keyKey to associate with value
valueValue to associate with key
old_valueLocation to store the value previously associated with key or NULL
Return values
0if value was inserted for an existing key, in which case old_value will contain the previous value
1if a new entry was inserted for the key - value pair
-ENOMEMif memory allocation failed
-ENOSPCif 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
mapHashmap to query
Return values
trueif map is empty.
falseif 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
itHashmap 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
mapHashmap 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
mapHashmap 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
mapHashmap to remove from
keyKey to remove from map
valueLocation to store a potential value associated with key or NULL
Return values
trueif map was modified as a result of this operation.
falseif 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
mapHashmap to examine
growtrue if an entry is to be added. false if an entry has been removed
num_reservedthe number of reserved entries
[out]new_num_bucketsvariable 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
mapHashmap to search through
Returns
the number of entries contained within map.