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