dde023fb8a
Add missing documentation for SYS_HASHMAP_DEFAULT_ALLOCATOR and sys_hashmap struct. Fixed minor type in SYS_HASHMAP_DEFINE_STATIC_ADVANCED doc. Signed-off-by: Benjamin Cabé <benjamin@zephyrproject.org>
366 lines
12 KiB
C
366 lines
12 KiB
C
/*
|
|
* Copyright (c) 2022 Meta
|
|
*
|
|
* SPDX-License-Identifier: Apache-2.0
|
|
*/
|
|
|
|
/**
|
|
* @file
|
|
* @addtogroup hashmap_apis
|
|
* @{
|
|
*/
|
|
|
|
#ifndef ZEPHYR_INCLUDE_SYS_HASH_MAP_H_
|
|
#define ZEPHYR_INCLUDE_SYS_HASH_MAP_H_
|
|
|
|
#include <stdbool.h>
|
|
#include <stddef.h>
|
|
#include <stdint.h>
|
|
|
|
#include <zephyr/kernel.h>
|
|
#include <zephyr/sys/hash_map_api.h>
|
|
#include <zephyr/sys/hash_map_cxx.h>
|
|
#include <zephyr/sys/hash_map_oa_lp.h>
|
|
#include <zephyr/sys/hash_map_sc.h>
|
|
|
|
#ifdef __cplusplus
|
|
extern "C" {
|
|
#endif
|
|
|
|
/**
|
|
* @brief Declare a Hashmap (advanced)
|
|
*
|
|
* Declare a Hashmap with control over advanced parameters.
|
|
*
|
|
* @note The allocator @p _alloc is used for allocating internal Hashmap
|
|
* entries and does not interact with any user-provided keys or values.
|
|
*
|
|
* @param _name Name of the Hashmap.
|
|
* @param _api API pointer of type @ref sys_hashmap_api.
|
|
* @param _config_type Variant of @ref sys_hashmap_config.
|
|
* @param _data_type Variant of @ref sys_hashmap_data.
|
|
* @param _hash_func Hash function pointer of type @ref sys_hash_func32_t.
|
|
* @param _alloc_func Allocator function pointer of type @ref sys_hashmap_allocator_t.
|
|
* @param ... Variant-specific details for @p _config_type.
|
|
*/
|
|
#define SYS_HASHMAP_DEFINE_ADVANCED(_name, _api, _config_type, _data_type, _hash_func, \
|
|
_alloc_func, ...) \
|
|
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), \
|
|
}
|
|
|
|
/**
|
|
* @brief Declare a Hashmap statically (advanced)
|
|
*
|
|
* Declare a Hashmap statically with control over advanced parameters.
|
|
*
|
|
* @note The allocator @p _alloc is used for allocating internal Hashmap
|
|
* entries and does not interact with any user-provided keys or values.
|
|
*
|
|
* @param _name Name of the Hashmap.
|
|
* @param _api API pointer of type @ref sys_hashmap_api.
|
|
* @param _config_type Variant of @ref sys_hashmap_config.
|
|
* @param _data_type Variant of @ref sys_hashmap_data.
|
|
* @param _hash_func Hash function pointer of type @ref sys_hash_func32_t.
|
|
* @param _alloc_func Allocator function pointer of type @ref sys_hashmap_allocator_t.
|
|
* @param ... Variant-specific details for @p _config_type.
|
|
*/
|
|
#define SYS_HASHMAP_DEFINE_STATIC_ADVANCED(_name, _api, _config_type, _data_type, _hash_func, \
|
|
_alloc_func, ...) \
|
|
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), \
|
|
}
|
|
|
|
/**
|
|
* @brief Declare a Hashmap
|
|
*
|
|
* Declare a Hashmap with default parameters.
|
|
*
|
|
* @param _name Name of the Hashmap.
|
|
*/
|
|
#define SYS_HASHMAP_DEFINE(_name) SYS_HASHMAP_DEFAULT_DEFINE(_name)
|
|
|
|
/**
|
|
* @brief Declare a Hashmap statically
|
|
*
|
|
* Declare a Hashmap statically with default parameters.
|
|
*
|
|
* @param _name Name of the Hashmap.
|
|
*/
|
|
#define SYS_HASHMAP_DEFINE_STATIC(_name) SYS_HASHMAP_DEFAULT_DEFINE_STATIC(_name)
|
|
|
|
/*
|
|
* A safe wrapper for realloc(), invariant of which libc provides it.
|
|
*/
|
|
static inline void *sys_hashmap_default_allocator(void *ptr, size_t size)
|
|
{
|
|
if (size == 0) {
|
|
free(ptr);
|
|
return NULL;
|
|
}
|
|
|
|
return realloc(ptr, size);
|
|
}
|
|
|
|
/** @brief The default Hashmap allocator */
|
|
#define SYS_HASHMAP_DEFAULT_ALLOCATOR sys_hashmap_default_allocator
|
|
|
|
/** @brief The default Hashmap load factor (in hundredths) */
|
|
#define SYS_HASHMAP_DEFAULT_LOAD_FACTOR 75
|
|
|
|
/** @brief Generic Hashmap */
|
|
struct sys_hashmap {
|
|
/** Hashmap API */
|
|
const struct sys_hashmap_api *api;
|
|
/** Hashmap configuration */
|
|
const struct sys_hashmap_config *config;
|
|
/** Hashmap data */
|
|
struct sys_hashmap_data *data;
|
|
/** Hash function */
|
|
sys_hash_func32_t hash_func;
|
|
/** Allocator */
|
|
sys_hashmap_allocator_t alloc_func;
|
|
};
|
|
|
|
/**
|
|
* @brief Iterate over all values contained in a @ref sys_hashmap
|
|
*
|
|
* @param map Hashmap to iterate over
|
|
* @param cb Callback to call for each entry
|
|
* @param cookie User-specified variable
|
|
*/
|
|
static inline void sys_hashmap_foreach(const struct sys_hashmap *map, sys_hashmap_callback_t cb,
|
|
void *cookie)
|
|
{
|
|
struct sys_hashmap_iterator it = {0};
|
|
|
|
for (map->api->iter(map, &it); sys_hashmap_iterator_has_next(&it);) {
|
|
it.next(&it);
|
|
cb(it.key, it.value, cookie);
|
|
}
|
|
}
|
|
|
|
/**
|
|
* @brief Clear all entries contained in a @ref sys_hashmap
|
|
*
|
|
* @note If the values in a particular Hashmap are
|
|
*
|
|
* @param map Hashmap to clear
|
|
* @param cb Callback to call for each entry
|
|
* @param cookie User-specified variable
|
|
*/
|
|
static inline void sys_hashmap_clear(struct sys_hashmap *map, sys_hashmap_callback_t cb,
|
|
void *cookie)
|
|
{
|
|
map->api->clear(map, cb, cookie);
|
|
}
|
|
|
|
/**
|
|
* @brief Insert a new entry into a @ref sys_hashmap
|
|
*
|
|
* Insert a new @p key - @p value pair into @p map.
|
|
*
|
|
* @param map Hashmap to insert into
|
|
* @param key Key to associate with @p value
|
|
* @param value Value to associate with @p key
|
|
* @param old_value Location to store the value previously associated with @p key or `NULL`
|
|
* @retval 0 if @p value was inserted for an existing key, in which case @p old_value will contain
|
|
* the previous value
|
|
* @retval 1 if a new entry was inserted for the @p key - @p value pair
|
|
* @retval -ENOMEM if memory allocation failed
|
|
* @retval -ENOSPC if the size limit has been reached
|
|
*/
|
|
static inline int sys_hashmap_insert(struct sys_hashmap *map, uint64_t key, uint64_t value,
|
|
uint64_t *old_value)
|
|
{
|
|
return map->api->insert(map, key, value, old_value);
|
|
}
|
|
|
|
/**
|
|
* @brief Remove an entry from a @ref sys_hashmap
|
|
*
|
|
* Erase the entry associated with key @p key, if one exists.
|
|
*
|
|
* @param map Hashmap to remove from
|
|
* @param key Key to remove from @p map
|
|
* @param value Location to store a potential value associated with @p key or `NULL`
|
|
*
|
|
* @retval true if @p map was modified as a result of this operation.
|
|
* @retval false if @p map does not contain a value associated with @p key.
|
|
*/
|
|
static inline bool sys_hashmap_remove(struct sys_hashmap *map, uint64_t key, uint64_t *value)
|
|
{
|
|
return map->api->remove(map, key, value);
|
|
}
|
|
|
|
/**
|
|
* @brief Get a value from a @ref sys_hashmap
|
|
*
|
|
* Look-up the @ref uint64_t associated with @p key, if one exists.
|
|
*
|
|
* @param map Hashmap to search through
|
|
* @param key Key with which to search @p map
|
|
* @param value Location to store a potential value associated with @p key or `NULL`
|
|
*
|
|
* @retval true if @p map contains a value associated with @p key.
|
|
* @retval false if @p map does not contain a value associated with @p key.
|
|
*/
|
|
static inline bool sys_hashmap_get(const struct sys_hashmap *map, uint64_t key, uint64_t *value)
|
|
{
|
|
return map->api->get(map, key, value);
|
|
}
|
|
|
|
/**
|
|
* @brief Check if @p map contains a value associated with @p key
|
|
*
|
|
* @param map Hashmap to search through
|
|
* @param key Key with which to search @p map
|
|
*
|
|
* @retval true if @p map contains a value associated with @p key.
|
|
* @retval false if @p map does not contain a value associated with @p key.
|
|
*/
|
|
static inline bool sys_hashmap_contains_key(const struct sys_hashmap *map, uint64_t key)
|
|
{
|
|
return sys_hashmap_get(map, key, NULL);
|
|
}
|
|
|
|
/**
|
|
* @brief Query the number of entries contained within @p map
|
|
*
|
|
* @param map Hashmap to search through
|
|
*
|
|
* @return the number of entries contained within @p map.
|
|
*/
|
|
static inline size_t sys_hashmap_size(const struct sys_hashmap *map)
|
|
{
|
|
return map->data->size;
|
|
}
|
|
|
|
/**
|
|
* @brief Check if @p map is empty
|
|
*
|
|
* @param map Hashmap to query
|
|
*
|
|
* @retval true if @p map is empty.
|
|
* @retval false if @p map is not empty.
|
|
*/
|
|
static inline bool sys_hashmap_is_empty(const struct sys_hashmap *map)
|
|
{
|
|
return map->data->size == 0;
|
|
}
|
|
|
|
/**
|
|
* @brief Query the load factor of @p map
|
|
*
|
|
* @note To convert the load factor to a floating-point value use
|
|
* `sys_hash_load_factor(map) / 100.0f`.
|
|
*
|
|
* @param map Hashmap to query
|
|
*
|
|
* @return Load factor of @p map expressed in hundredths.
|
|
*/
|
|
static inline uint8_t sys_hashmap_load_factor(const struct sys_hashmap *map)
|
|
{
|
|
if (map->data->n_buckets == 0) {
|
|
return 0;
|
|
}
|
|
|
|
return (map->data->size * 100) / map->data->n_buckets;
|
|
}
|
|
|
|
/**
|
|
* @brief Query the number of buckets used in @p map
|
|
*
|
|
* @param map Hashmap to query
|
|
* @return Number of buckets used in @p map
|
|
*/
|
|
static inline size_t sys_hashmap_num_buckets(const struct sys_hashmap *map)
|
|
{
|
|
return map->data->n_buckets;
|
|
}
|
|
|
|
/**
|
|
* @brief 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.
|
|
*
|
|
* @note The number of reserved entries is implementation-defined, but it is only considered
|
|
* as part of the load factor when growing the hash table.
|
|
*
|
|
* @param map Hashmap to examine
|
|
* @param grow true if an entry is to be added. false if an entry has been removed
|
|
* @param num_reserved the number of reserved entries
|
|
* @param[out] new_num_buckets variable Hashmap size
|
|
* @return true if the Hashmap should be rehashed
|
|
* @return false if the Hashmap should not be rehashed
|
|
*/
|
|
static inline bool sys_hashmap_should_rehash(const struct sys_hashmap *map, bool grow,
|
|
size_t num_reserved, size_t *new_num_buckets)
|
|
{
|
|
size_t size;
|
|
bool should_grow;
|
|
size_t n_buckets;
|
|
bool should_shrink;
|
|
const bool shrink = !grow;
|
|
struct sys_hashmap_oa_lp_data *const data = (struct sys_hashmap_oa_lp_data *)map->data;
|
|
const struct sys_hashmap_config *const config = map->config;
|
|
|
|
/* All branchless calculations, so very cache-friendly */
|
|
|
|
/* calculate new size */
|
|
size = data->size;
|
|
size += grow;
|
|
/* maximum size imposed by the implementation */
|
|
__ASSERT_NO_MSG(size < SIZE_MAX / 100);
|
|
|
|
/* calculate new number of buckets */
|
|
n_buckets = data->n_buckets;
|
|
/* initial number of buckets */
|
|
n_buckets += grow * (size == 1) * config->initial_n_buckets;
|
|
/* grow at a rate of 2x */
|
|
n_buckets <<= grow * (size != 1);
|
|
/* shrink at a rate of 2x */
|
|
n_buckets >>= shrink;
|
|
|
|
/* shrink to zero if empty */
|
|
n_buckets *= (size != 0);
|
|
|
|
__ASSERT_NO_MSG(new_num_buckets != NULL);
|
|
__ASSERT_NO_MSG(new_num_buckets != &data->n_buckets);
|
|
*new_num_buckets = n_buckets;
|
|
|
|
should_grow =
|
|
grow && (data->n_buckets == 0 ||
|
|
(size + num_reserved) * 100 / data->n_buckets > map->config->load_factor);
|
|
should_shrink =
|
|
shrink && (n_buckets == 0 || (size * 100) / n_buckets <= map->config->load_factor);
|
|
|
|
return should_grow || should_shrink;
|
|
}
|
|
|
|
/** @} */
|
|
|
|
#ifdef __cplusplus
|
|
}
|
|
#endif
|
|
|
|
#endif /* ZEPHYR_INCLUDE_SYS_HASH_MAP_H_ */
|