| /* |
| * Copyright (c) 2022 Meta |
| * |
| * SPDX-License-Identifier: Apache-2.0 |
| */ |
| |
| /** |
| * @file |
| * @brief 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). |
| */ |
| |
| #ifndef ZEPHYR_INCLUDE_SYS_HASHMAP_API_H_ |
| #define ZEPHYR_INCLUDE_SYS_HASHMAP_API_H_ |
| |
| #include <stdbool.h> |
| #include <stddef.h> |
| #include <stdint.h> |
| |
| #include <zephyr/sys/hash_function.h> |
| #include <zephyr/sys/util.h> |
| |
| #ifdef __cplusplus |
| extern "C" { |
| #endif |
| |
| /** |
| * @defgroup hashmap_apis Hashmap |
| * @ingroup datastructure_apis |
| * @{ |
| */ |
| |
| /** |
| * @brief Generic Hashmap iterator interface |
| * |
| * @note @a next should not be used without first checking |
| * @ref sys_hashmap_iterator_has_next |
| * |
| * @param map Pointer to the associated Hashmap |
| * @param next Modify the iterator in-place to point to the next Hashmap entry |
| * @param state Implementation-specific iterator state |
| * @param key Key associated with the current entry |
| * @param value Value associated with the current entry |
| * @param size Number of entries in the map |
| * @param pos Number of entries already iterated |
| */ |
| struct sys_hashmap_iterator { |
| const struct sys_hashmap *map; |
| void (*next)(struct sys_hashmap_iterator *it); |
| void *state; |
| uint64_t key; |
| uint64_t value; |
| const size_t size; |
| size_t pos; |
| }; |
| |
| /** |
| * @brief Check if a Hashmap iterator has a next entry |
| * |
| * @param it Hashmap iterator |
| * @return true if there is a next entry |
| * @return false if there is no next entry |
| */ |
| static inline bool sys_hashmap_iterator_has_next(const struct sys_hashmap_iterator *it) |
| { |
| return it->pos < it->size; |
| } |
| |
| /** |
| * @brief Allocator interface for @ref 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 @p new_size is zero. |
| * |
| * @param ptr Previously allocated memory region or `NULL` to make a new vallocation. |
| * @param new_size the new size of the allocation, in bytes. |
| * |
| * @see <a href="https://en.cppreference.com/w/c/memory/realloc">realloc</a> |
| */ |
| typedef void *(*sys_hashmap_allocator_t)(void *ptr, size_t new_size); |
| |
| /** |
| * @brief In-place iterator constructor for @ref sys_hashmap |
| * |
| * Construct an iterator, @p it, for @p map. |
| * |
| * @param map Hashmap to iterate over. |
| * @param it Iterator to initialize. |
| */ |
| typedef void (*sys_hashmap_iterator_t)(const struct sys_hashmap *map, |
| struct sys_hashmap_iterator *it); |
| |
| /** |
| * @brief Callback interface for @ref sys_hashmap |
| * |
| * This callback is used by some Hashmap methods. |
| * |
| * @param key Key corresponding to @p value |
| * @param value Value corresponding to @p key |
| * @param cookie User-specified variable |
| */ |
| typedef void (*sys_hashmap_callback_t)(uint64_t key, uint64_t value, void *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 |
| */ |
| typedef void (*sys_hashmap_clear_t)(struct sys_hashmap *map, sys_hashmap_callback_t cb, |
| void *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 |
| */ |
| typedef int (*sys_hashmap_insert_t)(struct sys_hashmap *map, uint64_t key, uint64_t value, |
| uint64_t *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. |
| */ |
| typedef bool (*sys_hashmap_remove_t)(struct sys_hashmap *map, uint64_t key, uint64_t *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. |
| */ |
| typedef bool (*sys_hashmap_get_t)(const struct sys_hashmap *map, uint64_t key, uint64_t *value); |
| |
| /** |
| * @brief Generic Hashmap API |
| * |
| * @param iter Iterator constructor (in-place) |
| * @param next Forward-incrementer for iterator |
| * @param clear Clear the hash table, freeing all resources |
| * @param insert Insert a key-value pair into the Hashmap |
| * @param remove Remove a key-value pair from the Hashmap |
| * @param get Retrieve a the value associated with a given key from the Hashmap |
| */ |
| struct sys_hashmap_api { |
| sys_hashmap_iterator_t iter; |
| sys_hashmap_clear_t clear; |
| sys_hashmap_insert_t insert; |
| sys_hashmap_remove_t remove; |
| sys_hashmap_get_t get; |
| }; |
| |
| /** |
| * @brief Generic Hashmap configuration |
| * |
| * When there is a known limit imposed on the number of entries in the Hashmap, |
| * users should specify that via @a max_size. When the Hashmap should have |
| * no artificial limitation in size (and be bounded only by the provided |
| * allocator), users should specify `SIZE_MAX` here. |
| * |
| * The @a load_factor is defined as the size of the Hashmap divided by the |
| * number of buckets. In this case, the size of the Hashmap is defined as |
| * the number of valid entries plus the number of invalidated entries. |
| * |
| * The @a initial_n_buckets is defined as the number of buckets to allocate |
| * when moving from size 0 to size 1 such that the maximum @a load_factor |
| * property is preserved. |
| * |
| * @param max_size Maximum number of entries |
| * @param load_factor Maximum load factor of expressed in hundredths |
| * @param initial_n_buckets Initial number of buckets to allocate |
| */ |
| struct sys_hashmap_config { |
| size_t max_size; |
| uint8_t load_factor; |
| uint8_t initial_n_buckets; |
| }; |
| |
| /** |
| * @brief Initializer for @p sys_hashmap_config |
| * |
| * This macro helps to initialize a structure of type @p sys_hashmap_config. |
| * |
| * @param _max_size Maximum number of entries |
| * @param _load_factor Maximum load factor of expressed in hundredths |
| */ |
| #define SYS_HASHMAP_CONFIG(_max_size, _load_factor) \ |
| { \ |
| .max_size = (size_t)_max_size, .load_factor = (uint8_t)_load_factor, \ |
| .initial_n_buckets = NHPOT(DIV_ROUND_UP(100, _load_factor)), \ |
| } |
| |
| /** |
| * @brief Generic Hashmap data |
| * |
| * @note When @a size is zero, @a buckets should be `NULL`. |
| * |
| * @param buckets Pointer for implementation-specific Hashmap storage |
| * @param n_buckets The number of buckets currently allocated |
| * @param size The number of entries currently in the Hashmap |
| */ |
| struct sys_hashmap_data { |
| void *buckets; |
| size_t n_buckets; |
| size_t size; |
| }; |
| |
| /** @} */ |
| |
| #ifdef __cplusplus |
| } |
| #endif |
| |
| #endif /* ZEPHYR_INCLUDE_SYS_HASHMAP_API_H_ */ |