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