Line data Source code
1 0 : /*
2 : * Copyright (c) 2022 Meta
3 : *
4 : * SPDX-License-Identifier: Apache-2.0
5 : */
6 :
7 : /**
8 : * @file
9 : * @addtogroup hashmap_apis
10 : * @{
11 : */
12 :
13 : #ifndef ZEPHYR_INCLUDE_SYS_HASH_MAP_H_
14 : #define ZEPHYR_INCLUDE_SYS_HASH_MAP_H_
15 :
16 : #include <stdbool.h>
17 : #include <stddef.h>
18 : #include <stdint.h>
19 : #include <stdlib.h>
20 :
21 : #include <zephyr/kernel.h>
22 : #include <zephyr/sys/hash_map_api.h>
23 : #include <zephyr/sys/hash_map_cxx.h>
24 : #include <zephyr/sys/hash_map_oa_lp.h>
25 : #include <zephyr/sys/hash_map_sc.h>
26 :
27 : #ifdef __cplusplus
28 : extern "C" {
29 : #endif
30 :
31 : /**
32 : * @brief Declare a Hashmap (advanced)
33 : *
34 : * Declare a Hashmap with control over advanced parameters.
35 : *
36 : * @note The allocator @p _alloc is used for allocating internal Hashmap
37 : * entries and does not interact with any user-provided keys or values.
38 : *
39 : * @param _name Name of the Hashmap.
40 : * @param _api API pointer of type @ref sys_hashmap_api.
41 : * @param _config_type Variant of @ref sys_hashmap_config.
42 : * @param _data_type Variant of @ref sys_hashmap_data.
43 : * @param _hash_func Hash function pointer of type @ref sys_hash_func32_t.
44 : * @param _alloc_func Allocator function pointer of type @ref sys_hashmap_allocator_t.
45 : * @param ... Variant-specific details for @p _config_type.
46 : */
47 : #define SYS_HASHMAP_DEFINE_ADVANCED(_name, _api, _config_type, _data_type, _hash_func, \
48 1 : _alloc_func, ...) \
49 : const struct _config_type _name##_config = __VA_ARGS__; \
50 : struct _data_type _name##_data; \
51 : struct sys_hashmap _name = { \
52 : .api = (const struct sys_hashmap_api *)(_api), \
53 : .config = (const struct sys_hashmap_config *)&_name##_config, \
54 : .data = (struct sys_hashmap_data *)&_name##_data, \
55 : .hash_func = (_hash_func), \
56 : .alloc_func = (_alloc_func), \
57 : }
58 :
59 : /**
60 : * @brief Declare a Hashmap statically (advanced)
61 : *
62 : * Declare a Hashmap statically with control over advanced parameters.
63 : *
64 : * @note The allocator @p _alloc is used for allocating internal Hashmap
65 : * entries and does not interact with any user-provided keys or values.
66 : *
67 : * @param _name Name of the Hashmap.
68 : * @param _api API pointer of type @ref sys_hashmap_api.
69 : * @param _config_type Variant of @ref sys_hashmap_config.
70 : * @param _data_type Variant of @ref sys_hashmap_data.
71 : * @param _hash_func Hash function pointer of type @ref sys_hash_func32_t.
72 : * @param _alloc_func Allocator function pointer of type @ref sys_hashmap_allocator_t.
73 : * @param ... Variant-specific details for @p _config_type.
74 : */
75 : #define SYS_HASHMAP_DEFINE_STATIC_ADVANCED(_name, _api, _config_type, _data_type, _hash_func, \
76 1 : _alloc_func, ...) \
77 : static const struct _config_type _name##_config = __VA_ARGS__; \
78 : static struct _data_type _name##_data; \
79 : static struct sys_hashmap _name = { \
80 : .api = (const struct sys_hashmap_api *)(_api), \
81 : .config = (const struct sys_hashmap_config *)&_name##_config, \
82 : .data = (struct sys_hashmap_data *)&_name##_data, \
83 : .hash_func = (_hash_func), \
84 : .alloc_func = (_alloc_func), \
85 : }
86 :
87 : /**
88 : * @brief Declare a Hashmap
89 : *
90 : * Declare a Hashmap with default parameters.
91 : *
92 : * @param _name Name of the Hashmap.
93 : */
94 1 : #define SYS_HASHMAP_DEFINE(_name) SYS_HASHMAP_DEFAULT_DEFINE(_name)
95 :
96 : /**
97 : * @brief Declare a Hashmap statically
98 : *
99 : * Declare a Hashmap statically with default parameters.
100 : *
101 : * @param _name Name of the Hashmap.
102 : */
103 1 : #define SYS_HASHMAP_DEFINE_STATIC(_name) SYS_HASHMAP_DEFAULT_DEFINE_STATIC(_name)
104 :
105 : /*
106 : * A safe wrapper for realloc(), invariant of which libc provides it.
107 : */
108 0 : static inline void *sys_hashmap_default_allocator(void *ptr, size_t size)
109 : {
110 : if (size == 0) {
111 : free(ptr);
112 : return NULL;
113 : }
114 :
115 : return realloc(ptr, size);
116 : }
117 :
118 : /** @brief The default Hashmap allocator */
119 1 : #define SYS_HASHMAP_DEFAULT_ALLOCATOR sys_hashmap_default_allocator
120 :
121 : /** @brief The default Hashmap load factor (in hundredths) */
122 1 : #define SYS_HASHMAP_DEFAULT_LOAD_FACTOR 75
123 :
124 : /** @brief Generic Hashmap */
125 1 : struct sys_hashmap {
126 : /** Hashmap API */
127 1 : const struct sys_hashmap_api *api;
128 : /** Hashmap configuration */
129 1 : const struct sys_hashmap_config *config;
130 : /** Hashmap data */
131 1 : struct sys_hashmap_data *data;
132 : /** Hash function */
133 1 : sys_hash_func32_t hash_func;
134 : /** Allocator */
135 1 : sys_hashmap_allocator_t alloc_func;
136 : };
137 :
138 : /**
139 : * @brief Iterate over all values contained in a @ref sys_hashmap
140 : *
141 : * @param map Hashmap to iterate over
142 : * @param cb Callback to call for each entry
143 : * @param cookie User-specified variable
144 : */
145 1 : static inline void sys_hashmap_foreach(const struct sys_hashmap *map, sys_hashmap_callback_t cb,
146 : void *cookie)
147 : {
148 : struct sys_hashmap_iterator it = {0};
149 :
150 : for (map->api->iter(map, &it); sys_hashmap_iterator_has_next(&it);) {
151 : it.next(&it);
152 : cb(it.key, it.value, cookie);
153 : }
154 : }
155 :
156 : /**
157 : * @brief Clear all entries contained in a @ref sys_hashmap
158 : *
159 : * @note If the values in a particular Hashmap are
160 : *
161 : * @param map Hashmap to clear
162 : * @param cb Callback to call for each entry
163 : * @param cookie User-specified variable
164 : */
165 1 : static inline void sys_hashmap_clear(struct sys_hashmap *map, sys_hashmap_callback_t cb,
166 : void *cookie)
167 : {
168 : map->api->clear(map, cb, cookie);
169 : }
170 :
171 : /**
172 : * @brief Insert a new entry into a @ref sys_hashmap
173 : *
174 : * Insert a new @p key - @p value pair into @p map.
175 : *
176 : * @param map Hashmap to insert into
177 : * @param key Key to associate with @p value
178 : * @param value Value to associate with @p key
179 : * @param old_value Location to store the value previously associated with @p key or `NULL`
180 : * @retval 0 if @p value was inserted for an existing key, in which case @p old_value will contain
181 : * the previous value
182 : * @retval 1 if a new entry was inserted for the @p key - @p value pair
183 : * @retval -ENOMEM if memory allocation failed
184 : * @retval -ENOSPC if the size limit has been reached
185 : */
186 1 : static inline int sys_hashmap_insert(struct sys_hashmap *map, uint64_t key, uint64_t value,
187 : uint64_t *old_value)
188 : {
189 : return map->api->insert(map, key, value, old_value);
190 : }
191 :
192 : /**
193 : * @brief Remove an entry from a @ref sys_hashmap
194 : *
195 : * Erase the entry associated with key @p key, if one exists.
196 : *
197 : * @param map Hashmap to remove from
198 : * @param key Key to remove from @p map
199 : * @param value Location to store a potential value associated with @p key or `NULL`
200 : *
201 : * @retval true if @p map was modified as a result of this operation.
202 : * @retval false if @p map does not contain a value associated with @p key.
203 : */
204 1 : static inline bool sys_hashmap_remove(struct sys_hashmap *map, uint64_t key, uint64_t *value)
205 : {
206 : return map->api->remove(map, key, value);
207 : }
208 :
209 : /**
210 : * @brief Get a value from a @ref sys_hashmap
211 : *
212 : * Look-up the @ref uint64_t associated with @p key, if one exists.
213 : *
214 : * @param map Hashmap to search through
215 : * @param key Key with which to search @p map
216 : * @param value Location to store a potential value associated with @p key or `NULL`
217 : *
218 : * @retval true if @p map contains a value associated with @p key.
219 : * @retval false if @p map does not contain a value associated with @p key.
220 : */
221 1 : static inline bool sys_hashmap_get(const struct sys_hashmap *map, uint64_t key, uint64_t *value)
222 : {
223 : return map->api->get(map, key, value);
224 : }
225 :
226 : /**
227 : * @brief Check if @p map contains a value associated with @p key
228 : *
229 : * @param map Hashmap to search through
230 : * @param key Key with which to search @p map
231 : *
232 : * @retval true if @p map contains a value associated with @p key.
233 : * @retval false if @p map does not contain a value associated with @p key.
234 : */
235 1 : static inline bool sys_hashmap_contains_key(const struct sys_hashmap *map, uint64_t key)
236 : {
237 : return sys_hashmap_get(map, key, NULL);
238 : }
239 :
240 : /**
241 : * @brief Query the number of entries contained within @p map
242 : *
243 : * @param map Hashmap to search through
244 : *
245 : * @return the number of entries contained within @p map.
246 : */
247 1 : static inline size_t sys_hashmap_size(const struct sys_hashmap *map)
248 : {
249 : return map->data->size;
250 : }
251 :
252 : /**
253 : * @brief Check if @p map is empty
254 : *
255 : * @param map Hashmap to query
256 : *
257 : * @retval true if @p map is empty.
258 : * @retval false if @p map is not empty.
259 : */
260 1 : static inline bool sys_hashmap_is_empty(const struct sys_hashmap *map)
261 : {
262 : return map->data->size == 0;
263 : }
264 :
265 : /**
266 : * @brief Query the load factor of @p map
267 : *
268 : * @note To convert the load factor to a floating-point value use
269 : * `sys_hash_load_factor(map) / 100.0f`.
270 : *
271 : * @param map Hashmap to query
272 : *
273 : * @return Load factor of @p map expressed in hundredths.
274 : */
275 1 : static inline uint8_t sys_hashmap_load_factor(const struct sys_hashmap *map)
276 : {
277 : if (map->data->n_buckets == 0) {
278 : return 0;
279 : }
280 :
281 : return (map->data->size * 100) / map->data->n_buckets;
282 : }
283 :
284 : /**
285 : * @brief Query the number of buckets used in @p map
286 : *
287 : * @param map Hashmap to query
288 : * @return Number of buckets used in @p map
289 : */
290 1 : static inline size_t sys_hashmap_num_buckets(const struct sys_hashmap *map)
291 : {
292 : return map->data->n_buckets;
293 : }
294 :
295 : /**
296 : * @brief Decide whether the Hashmap should be resized
297 : *
298 : * This is a simple opportunistic method that implementations
299 : * can choose to use. It will grow and shrink the Hashmap by a factor
300 : * of 2 when insertion / removal would exceed / fall into the specified
301 : * load factor.
302 : *
303 : * @note Users should call this prior to inserting a new key-value pair and after removing a
304 : * key-value pair.
305 : *
306 : * @note The number of reserved entries is implementation-defined, but it is only considered
307 : * as part of the load factor when growing the hash table.
308 : *
309 : * @param map Hashmap to examine
310 : * @param grow true if an entry is to be added. false if an entry has been removed
311 : * @param num_reserved the number of reserved entries
312 : * @param[out] new_num_buckets variable Hashmap size
313 : * @return true if the Hashmap should be rehashed
314 : * @return false if the Hashmap should not be rehashed
315 : */
316 1 : static inline bool sys_hashmap_should_rehash(const struct sys_hashmap *map, bool grow,
317 : size_t num_reserved, size_t *new_num_buckets)
318 : {
319 : size_t size;
320 : bool should_grow;
321 : size_t n_buckets;
322 : bool should_shrink;
323 : const bool shrink = !grow;
324 : struct sys_hashmap_oa_lp_data *const data = (struct sys_hashmap_oa_lp_data *)map->data;
325 : const struct sys_hashmap_config *const config = map->config;
326 :
327 : /* All branchless calculations, so very cache-friendly */
328 :
329 : /* calculate new size */
330 : size = data->size;
331 : size += grow;
332 : /* maximum size imposed by the implementation */
333 : __ASSERT_NO_MSG(size < SIZE_MAX / 100);
334 :
335 : /* calculate new number of buckets */
336 : n_buckets = data->n_buckets;
337 : /* initial number of buckets */
338 : n_buckets += grow * (size == 1) * config->initial_n_buckets;
339 : /* grow at a rate of 2x */
340 : n_buckets <<= grow * (size != 1);
341 : /* shrink at a rate of 2x */
342 : n_buckets >>= shrink;
343 :
344 : /* shrink to zero if empty */
345 : n_buckets *= (size != 0);
346 :
347 : __ASSERT_NO_MSG(new_num_buckets != NULL);
348 : __ASSERT_NO_MSG(new_num_buckets != &data->n_buckets);
349 : *new_num_buckets = n_buckets;
350 :
351 : should_grow =
352 : grow && (data->n_buckets == 0 ||
353 : (size + num_reserved) * 100 / data->n_buckets > map->config->load_factor);
354 : should_shrink =
355 : shrink && (n_buckets == 0 || (size * 100) / n_buckets <= map->config->load_factor);
356 :
357 : return should_grow || should_shrink;
358 : }
359 :
360 : /** @} */
361 :
362 : #ifdef __cplusplus
363 : }
364 : #endif
365 :
366 : #endif /* ZEPHYR_INCLUDE_SYS_HASH_MAP_H_ */
|
