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