Zephyr Project API 3.7.0
A Scalable Open Source RTOS
Loading...
Searching...
No Matches
hash_map.h
Go to the documentation of this file.
1/*
2 * Copyright (c) 2022 Meta
3 *
4 * SPDX-License-Identifier: Apache-2.0
5 */
6
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>
26
27#ifdef __cplusplus
28extern "C" {
29#endif
30
47#define SYS_HASHMAP_DEFINE_ADVANCED(_name, _api, _config_type, _data_type, _hash_func, \
48 _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
75#define SYS_HASHMAP_DEFINE_STATIC_ADVANCED(_name, _api, _config_type, _data_type, _hash_func, \
76 _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
94#define SYS_HASHMAP_DEFINE(_name) SYS_HASHMAP_DEFAULT_DEFINE(_name)
95
103#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 */
108static 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
119#define SYS_HASHMAP_DEFAULT_ALLOCATOR sys_hashmap_default_allocator
120
122#define SYS_HASHMAP_DEFAULT_LOAD_FACTOR 75
123
137
145static 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
166 void *cookie)
167{
168 map->api->clear(map, cb, cookie);
169}
170
187 uint64_t *old_value)
188{
189 return map->api->insert(map, key, value, old_value);
190}
191
205{
206 return map->api->remove(map, key, value);
207}
208
221static 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
235static 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
247static inline size_t sys_hashmap_size(const struct sys_hashmap *map)
248{
249 return map->data->size;
250}
251
260static inline bool sys_hashmap_is_empty(const struct sys_hashmap *map)
261{
262 return map->data->size == 0;
263}
264
275static 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
290static inline size_t sys_hashmap_num_buckets(const struct sys_hashmap *map)
291{
292 return map->data->n_buckets;
293}
294
316static 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
362#ifdef __cplusplus
363}
364#endif
365
366#endif /* ZEPHYR_INCLUDE_SYS_HASH_MAP_H_ */
uint32_t(* sys_hash_func32_t)(const void *str, size_t n)
32-bit Hash function interface
Definition hash_function.h:41
static bool sys_hashmap_iterator_has_next(const struct sys_hashmap_iterator *it)
Check if a Hashmap iterator has a next entry.
Definition hash_map_api.h:68
static bool sys_hashmap_remove(struct sys_hashmap *map, uint64_t key, uint64_t *value)
Remove an entry from a sys_hashmap.
Definition hash_map.h:204
static int sys_hashmap_insert(struct sys_hashmap *map, uint64_t key, uint64_t value, uint64_t *old_value)
Insert a new entry into a sys_hashmap.
Definition hash_map.h:186
static uint8_t sys_hashmap_load_factor(const struct sys_hashmap *map)
Query the load factor of map.
Definition hash_map.h:275
static size_t sys_hashmap_size(const struct sys_hashmap *map)
Query the number of entries contained within map.
Definition hash_map.h:247
static bool sys_hashmap_get(const struct sys_hashmap *map, uint64_t key, uint64_t *value)
Get a value from a sys_hashmap.
Definition hash_map.h:221
static bool sys_hashmap_is_empty(const struct sys_hashmap *map)
Check if map is empty.
Definition hash_map.h:260
void(* sys_hashmap_callback_t)(uint64_t key, uint64_t value, void *cookie)
Callback interface for sys_hashmap.
Definition hash_map_api.h:106
static size_t sys_hashmap_num_buckets(const struct sys_hashmap *map)
Query the number of buckets used in map.
Definition hash_map.h:290
void *(* sys_hashmap_allocator_t)(void *ptr, size_t new_size)
Allocator interface for sys_hashmap.
Definition hash_map_api.h:84
static bool sys_hashmap_contains_key(const struct sys_hashmap *map, uint64_t key)
Check if map contains a value associated with key.
Definition hash_map.h:235
static void * sys_hashmap_default_allocator(void *ptr, size_t size)
Definition hash_map.h:108
static void sys_hashmap_clear(struct sys_hashmap *map, sys_hashmap_callback_t cb, void *cookie)
Clear all entries contained in a sys_hashmap.
Definition hash_map.h:165
static void sys_hashmap_foreach(const struct sys_hashmap *map, sys_hashmap_callback_t cb, void *cookie)
Iterate over all values contained in a sys_hashmap.
Definition hash_map.h:145
static bool sys_hashmap_should_rehash(const struct sys_hashmap *map, bool grow, size_t num_reserved, size_t *new_num_buckets)
Decide whether the Hashmap should be resized.
Definition hash_map.h:316
C++ Hashmap.
Open-Addressing / Linear Probe Hashmap Implementation.
Separate Chaining Hashmap Implementation.
Public kernel APIs.
void * ptr
Definition printk.c:177
static k_spinlock_key_t key
Definition spinlock_error_case.c:15
__UINT64_TYPE__ uint64_t
Definition stdint.h:91
#define SIZE_MAX
Definition stdint.h:70
__UINT8_TYPE__ uint8_t
Definition stdint.h:88
void * realloc(void *ptr, size_t size)
void free(void *ptr)
Generic Hashmap API.
Definition hash_map_api.h:168
sys_hashmap_iterator_t iter
Iterator constructor (in-place)
Definition hash_map_api.h:170
sys_hashmap_remove_t remove
Remove a key-value pair from the Hashmap.
Definition hash_map_api.h:176
sys_hashmap_clear_t clear
Clear the hash table, freeing all resources.
Definition hash_map_api.h:172
sys_hashmap_insert_t insert
Insert a key-value pair into the Hashmap.
Definition hash_map_api.h:174
sys_hashmap_get_t get
Retrieve the value associated with a given key from the Hashmap.
Definition hash_map_api.h:178
Generic Hashmap configuration.
Definition hash_map_api.h:197
uint8_t initial_n_buckets
Initial number of buckets to allocate.
Definition hash_map_api.h:203
uint8_t load_factor
Maximum load factor expressed in hundredths.
Definition hash_map_api.h:201
Generic Hashmap data.
Definition hash_map_api.h:225
size_t n_buckets
The number of buckets currently allocated.
Definition hash_map_api.h:229
size_t size
The number of entries currently in the Hashmap.
Definition hash_map_api.h:231
Generic Hashmap iterator interface.
Definition hash_map_api.h:44
const struct sys_hashmap * map
Pointer to the associated Hashmap.
Definition hash_map_api.h:46
const size_t size
Number of entries in the map.
Definition hash_map_api.h:56
uint64_t key
Key associated with the current entry.
Definition hash_map_api.h:52
void(* next)(struct sys_hashmap_iterator *it)
Modify the iterator in-place to point to the next Hashmap entry.
Definition hash_map_api.h:48
uint64_t value
Value associated with the current entry.
Definition hash_map_api.h:54
Definition hash_map_oa_lp.h:27
Generic Hashmap.
Definition hash_map.h:125
struct sys_hashmap_data * data
Hashmap data.
Definition hash_map.h:131
sys_hash_func32_t hash_func
Hash function.
Definition hash_map.h:133
const struct sys_hashmap_api * api
Hashmap API.
Definition hash_map.h:127
sys_hashmap_allocator_t alloc_func
Allocator.
Definition hash_map.h:135
const struct sys_hashmap_config * config
Hashmap configuration.
Definition hash_map.h:129
static fdata_t data[2]
Definition test_fifo_contexts.c:15