1 /*
2 * Copyright (c) 2022 Meta
3 *
4 * SPDX-License-Identifier: Apache-2.0
5 */
6
7 /**
8 * @file
9 * @brief Hashmap (Hash Table) API
10 *
11 * Hashmaps (a.k.a Hash Tables) sacrifice space for speed. All operations
12 * on a Hashmap (insert, delete, search) are O(1) complexity (on average).
13 */
14
15 #ifndef ZEPHYR_INCLUDE_SYS_HASH_MAP_H_
16 #define ZEPHYR_INCLUDE_SYS_HASH_MAP_H_
17
18 #include <stdbool.h>
19 #include <stddef.h>
20 #include <stdint.h>
21
22 #include <zephyr/kernel.h>
23 #include <zephyr/sys/hash_map_api.h>
24 #include <zephyr/sys/hash_map_cxx.h>
25 #include <zephyr/sys/hash_map_oa_lp.h>
26 #include <zephyr/sys/hash_map_sc.h>
27
28 #ifdef __cplusplus
29 extern "C" {
30 #endif
31
32 /**
33 * @ingroup hashmap_apis
34 * @{
35 */
36
37 /**
38 * @brief Declare a Hashmap (advanced)
39 *
40 * Declare a Hashmap with control over advanced parameters.
41 *
42 * @note The allocator @p _alloc is used for allocating internal Hashmap
43 * entries and does not interact with any user-provided keys or values.
44 *
45 * @param _name Name of the Hashmap.
46 * @param _api API pointer of type @ref sys_hashmap_api.
47 * @param _config_type Variant of @ref sys_hashmap_config.
48 * @param _data_type Variant of @ref sys_hashmap_data.
49 * @param _hash_func Hash function pointer of type @ref sys_hash_func32_t.
50 * @param _alloc_func Allocator function pointer of type @ref sys_hashmap_allocator_t.
51 * @param ... Variant-specific details for @p _config_type.
52 */
53 #define SYS_HASHMAP_DEFINE_ADVANCED(_name, _api, _config_type, _data_type, _hash_func, \
54 _alloc_func, ...) \
55 const struct _config_type _name##_config = __VA_ARGS__; \
56 struct _data_type _name##_data; \
57 struct sys_hashmap _name = { \
58 .api = (const struct sys_hashmap_api *)(_api), \
59 .config = (const struct sys_hashmap_config *)&_name##_config, \
60 .data = (struct sys_hashmap_data *)&_name##_data, \
61 .hash_func = (_hash_func), \
62 .alloc_func = (_alloc_func), \
63 }
64
65 /**
66 * @brief Declare a Hashmap (advanced)
67 *
68 * Declare a Hashmap with control over advanced parameters.
69 *
70 * @note The allocator @p _alloc is used for allocating internal Hashmap
71 * entries and does not interact with any user-provided keys or values.
72 *
73 * @param _name Name of the Hashmap.
74 * @param _api API pointer of type @ref sys_hashmap_api.
75 * @param _config_type Variant of @ref sys_hashmap_config.
76 * @param _data_type Variant of @ref sys_hashmap_data.
77 * @param _hash_func Hash function pointer of type @ref sys_hash_func32_t.
78 * @param _alloc_func Allocator function pointer of type @ref sys_hashmap_allocator_t.
79 * @param ... Variant-specific details for @p _config_type.
80 */
81 #define SYS_HASHMAP_DEFINE_STATIC_ADVANCED(_name, _api, _config_type, _data_type, _hash_func, \
82 _alloc_func, ...) \
83 static const struct _config_type _name##_config = __VA_ARGS__; \
84 static struct _data_type _name##_data; \
85 static struct sys_hashmap _name = { \
86 .api = (const struct sys_hashmap_api *)(_api), \
87 .config = (const struct sys_hashmap_config *)&_name##_config, \
88 .data = (struct sys_hashmap_data *)&_name##_data, \
89 .hash_func = (_hash_func), \
90 .alloc_func = (_alloc_func), \
91 }
92
93 /**
94 * @brief Declare a Hashmap
95 *
96 * Declare a Hashmap with default parameters.
97 *
98 * @param _name Name of the Hashmap.
99 */
100 #define SYS_HASHMAP_DEFINE(_name) SYS_HASHMAP_DEFAULT_DEFINE(_name)
101
102 /**
103 * @brief Declare a Hashmap statically
104 *
105 * Declare a Hashmap statically with default parameters.
106 *
107 * @param _name Name of the Hashmap.
108 */
109 #define SYS_HASHMAP_DEFINE_STATIC(_name) SYS_HASHMAP_DEFAULT_DEFINE_STATIC(_name)
110
111 /*
112 * A safe wrapper for realloc(), invariant of which libc provides it.
113 */
sys_hashmap_default_allocator(void * ptr,size_t size)114 static inline void *sys_hashmap_default_allocator(void *ptr, size_t size)
115 {
116 if (size == 0) {
117 free(ptr);
118 return NULL;
119 }
120
121 return realloc(ptr, size);
122 }
123
124 #define SYS_HASHMAP_DEFAULT_ALLOCATOR sys_hashmap_default_allocator
125
126 /** @brief The default Hashmap load factor (in hundredths) */
127 #define SYS_HASHMAP_DEFAULT_LOAD_FACTOR 75
128
129 /** @brief Generic Hashmap */
130 struct sys_hashmap {
131 const struct sys_hashmap_api *api;
132 const struct sys_hashmap_config *config;
133 struct sys_hashmap_data *data;
134 sys_hash_func32_t hash_func;
135 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 */
sys_hashmap_foreach(const struct sys_hashmap * map,sys_hashmap_callback_t cb,void * cookie)145 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 */
sys_hashmap_clear(struct sys_hashmap * map,sys_hashmap_callback_t cb,void * cookie)165 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 */
sys_hashmap_insert(struct sys_hashmap * map,uint64_t key,uint64_t value,uint64_t * old_value)186 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 */
sys_hashmap_remove(struct sys_hashmap * map,uint64_t key,uint64_t * value)204 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 */
sys_hashmap_get(const struct sys_hashmap * map,uint64_t key,uint64_t * value)221 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 */
sys_hashmap_contains_key(const struct sys_hashmap * map,uint64_t key)235 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 */
sys_hashmap_size(const struct sys_hashmap * map)247 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 */
sys_hashmap_is_empty(const struct sys_hashmap * map)260 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 */
sys_hashmap_load_factor(const struct sys_hashmap * map)275 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 */
sys_hashmap_num_buckets(const struct sys_hashmap * map)290 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 */
sys_hashmap_should_rehash(const struct sys_hashmap * map,bool grow,size_t num_reserved,size_t * new_num_buckets)316 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_ */
367
