Line data Source code
1 0 : /* 2 : * Copyright (c) 2022 Meta 3 : * 4 : * SPDX-License-Identifier: Apache-2.0 5 : */ 6 : 7 : #ifndef ZEPHYR_INCLUDE_SYS_HASHMAP_API_H_ 8 : #define ZEPHYR_INCLUDE_SYS_HASHMAP_API_H_ 9 : 10 : #include <stdbool.h> 11 : #include <stddef.h> 12 : #include <stdint.h> 13 : 14 : #include <zephyr/sys/hash_function.h> 15 : #include <zephyr/sys/util.h> 16 : 17 : #ifdef __cplusplus 18 : extern "C" { 19 : #endif 20 : 21 : /** 22 : * @file 23 : * @defgroup hashmap_apis Hashmap 24 : * @ingroup datastructure_apis 25 : * 26 : * @brief Hashmap (Hash Table) API 27 : * 28 : * Hashmaps (a.k.a Hash Tables) sacrifice space for speed. All operations 29 : * on a Hashmap (insert, delete, search) are O(1) complexity (on average). 30 : * 31 : * @defgroup hashmap_implementations Hashmap Implementations 32 : * @ingroup hashmap_apis 33 : * 34 : * @addtogroup hashmap_apis 35 : * @{ 36 : */ 37 : 38 : /** 39 : * @brief Generic Hashmap iterator interface 40 : * 41 : * @note @a next should not be used without first checking 42 : * @ref sys_hashmap_iterator_has_next 43 : */ 44 1 : struct sys_hashmap_iterator { 45 : /** Pointer to the associated Hashmap */ 46 1 : const struct sys_hashmap *map; 47 : /** Modify the iterator in-place to point to the next Hashmap entry */ 48 1 : void (*next)(struct sys_hashmap_iterator *it); 49 : /** Implementation-specific iterator state */ 50 1 : void *state; 51 : /** Key associated with the current entry */ 52 1 : uint64_t key; 53 : /** Value associated with the current entry */ 54 1 : uint64_t value; 55 : /** Number of entries in the map */ 56 1 : const size_t size; 57 : /** Number of entries already iterated */ 58 1 : size_t pos; 59 : }; 60 : 61 : /** 62 : * @brief Check if a Hashmap iterator has a next entry 63 : * 64 : * @param it Hashmap iterator 65 : * @return true if there is a next entry 66 : * @return false if there is no next entry 67 : */ 68 1 : static inline bool sys_hashmap_iterator_has_next(const struct sys_hashmap_iterator *it) 69 : { 70 : return it->pos < it->size; 71 : } 72 : 73 : /** 74 : * @brief Allocator interface for @ref sys_hashmap 75 : * 76 : * The Hashmap allocator can be any allocator that behaves similarly to `realloc()` with the 77 : * additional specification that the allocator behaves like `free()` when @p new_size is zero. 78 : * 79 : * @param ptr Previously allocated memory region or `NULL` to make a new vallocation. 80 : * @param new_size the new size of the allocation, in bytes. 81 : * 82 : * @see <a href="https://en.cppreference.com/w/c/memory/realloc">realloc</a> 83 : */ 84 1 : typedef void *(*sys_hashmap_allocator_t)(void *ptr, size_t new_size); 85 : 86 : /** 87 : * @brief In-place iterator constructor for @ref sys_hashmap 88 : * 89 : * Construct an iterator, @p it, for @p map. 90 : * 91 : * @param map Hashmap to iterate over. 92 : * @param it Iterator to initialize. 93 : */ 94 1 : typedef void (*sys_hashmap_iterator_t)(const struct sys_hashmap *map, 95 : struct sys_hashmap_iterator *it); 96 : 97 : /** 98 : * @brief Callback interface for @ref sys_hashmap 99 : * 100 : * This callback is used by some Hashmap methods. 101 : * 102 : * @param key Key corresponding to @p value 103 : * @param value Value corresponding to @p key 104 : * @param cookie User-specified variable 105 : */ 106 1 : typedef void (*sys_hashmap_callback_t)(uint64_t key, uint64_t value, void *cookie); 107 : 108 : /** 109 : * @brief Clear all entries contained in a @ref sys_hashmap 110 : * 111 : * @note If the values in a particular Hashmap are 112 : * 113 : * @param map Hashmap to clear 114 : * @param cb Callback to call for each entry 115 : * @param cookie User-specified variable 116 : */ 117 1 : typedef void (*sys_hashmap_clear_t)(struct sys_hashmap *map, sys_hashmap_callback_t cb, 118 : void *cookie); 119 : 120 : /** 121 : * @brief Insert a new entry into a @ref sys_hashmap 122 : * 123 : * Insert a new @p key - @p value pair into @p map. 124 : * 125 : * @param map Hashmap to insert into 126 : * @param key Key to associate with @p value 127 : * @param value Value to associate with @p key 128 : * @param old_value Location to store the value previously associated with @p key or `NULL` 129 : * @retval 0 if @p value was inserted for an existing key, in which case @p old_value will contain 130 : * the previous value 131 : * @retval 1 if a new entry was inserted for the @p key - @p value pair 132 : * @retval -ENOMEM if memory allocation failed 133 : */ 134 1 : typedef int (*sys_hashmap_insert_t)(struct sys_hashmap *map, uint64_t key, uint64_t value, 135 : uint64_t *old_value); 136 : 137 : /** 138 : * @brief Remove an entry from a @ref sys_hashmap 139 : * 140 : * Erase the entry associated with key @p key, if one exists. 141 : * 142 : * @param map Hashmap to remove from 143 : * @param key Key to remove from @p map 144 : * @param value Location to store a potential value associated with @p key or `NULL` 145 : * 146 : * @retval true if @p map was modified as a result of this operation. 147 : * @retval false if @p map does not contain a value associated with @p key. 148 : */ 149 1 : typedef bool (*sys_hashmap_remove_t)(struct sys_hashmap *map, uint64_t key, uint64_t *value); 150 : 151 : /** 152 : * @brief Get a value from a @ref sys_hashmap 153 : * 154 : * Look-up the @ref uint64_t associated with @p key, if one exists. 155 : * 156 : * @param map Hashmap to search through 157 : * @param key Key with which to search @p map 158 : * @param value Location to store a potential value associated with @p key or `NULL` 159 : * 160 : * @retval true if @p map contains a value associated with @p key. 161 : * @retval false if @p map does not contain a value associated with @p key. 162 : */ 163 1 : typedef bool (*sys_hashmap_get_t)(const struct sys_hashmap *map, uint64_t key, uint64_t *value); 164 : 165 : /** 166 : * @brief Generic Hashmap API 167 : */ 168 1 : struct sys_hashmap_api { 169 : /** Iterator constructor (in-place) */ 170 1 : sys_hashmap_iterator_t iter; 171 : /** Clear the hash table, freeing all resources */ 172 1 : sys_hashmap_clear_t clear; 173 : /** Insert a key-value pair into the Hashmap */ 174 1 : sys_hashmap_insert_t insert; 175 : /** Remove a key-value pair from the Hashmap */ 176 1 : sys_hashmap_remove_t remove; 177 : /** Retrieve the value associated with a given key from the Hashmap */ 178 1 : sys_hashmap_get_t get; 179 : }; 180 : 181 : /** 182 : * @brief Generic Hashmap configuration 183 : * 184 : * When there is a known limit imposed on the number of entries in the Hashmap, 185 : * users should specify that via @a max_size. When the Hashmap should have 186 : * no artificial limitation in size (and be bounded only by the provided 187 : * allocator), users should specify `SIZE_MAX` here. 188 : * 189 : * The @a load_factor is defined as the size of the Hashmap divided by the 190 : * number of buckets. In this case, the size of the Hashmap is defined as 191 : * the number of valid entries plus the number of invalidated entries. 192 : * 193 : * The @a initial_n_buckets is defined as the number of buckets to allocate 194 : * when moving from size 0 to size 1 such that the maximum @a load_factor 195 : * property is preserved. 196 : */ 197 1 : struct sys_hashmap_config { 198 : /** Maximum number of entries */ 199 1 : size_t max_size; 200 : /** Maximum load factor expressed in hundredths */ 201 1 : uint8_t load_factor; 202 : /** Initial number of buckets to allocate */ 203 1 : uint8_t initial_n_buckets; 204 : }; 205 : 206 : /** 207 : * @brief Initializer for @p sys_hashmap_config 208 : * 209 : * This macro helps to initialize a structure of type @p sys_hashmap_config. 210 : * 211 : * @param _max_size Maximum number of entries 212 : * @param _load_factor Maximum load factor of expressed in hundredths 213 : */ 214 1 : #define SYS_HASHMAP_CONFIG(_max_size, _load_factor) \ 215 : { \ 216 : .max_size = (size_t)_max_size, .load_factor = (uint8_t)_load_factor, \ 217 : .initial_n_buckets = NHPOT(DIV_ROUND_UP(100, _load_factor)), \ 218 : } 219 : 220 : /** 221 : * @brief Generic Hashmap data 222 : * 223 : * @note When @a size is zero, @a buckets should be `NULL`. 224 : */ 225 1 : struct sys_hashmap_data { 226 : /** Pointer for implementation-specific Hashmap storage */ 227 1 : void *buckets; 228 : /** The number of buckets currently allocated */ 229 1 : size_t n_buckets; 230 : /** The number of entries currently in the Hashmap */ 231 1 : size_t size; 232 : }; 233 : 234 : /** @} */ 235 : 236 : #ifdef __cplusplus 237 : } 238 : #endif 239 : 240 : #endif /* ZEPHYR_INCLUDE_SYS_HASHMAP_API_H_ */
