Line data Source code
1 0 : /*
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 1 : struct sys_hashmap_iterator {
45 : /** Pointer to the associated Hashmap */
46 1 : const struct sys_hashmap *map;
47 : /** Modify the iterator in-place to point to the next Hashmap entry */
48 1 : void (*next)(struct sys_hashmap_iterator *it);
49 : /** Implementation-specific iterator state */
50 1 : void *state;
51 : /** Key associated with the current entry */
52 1 : uint64_t key;
53 : /** Value associated with the current entry */
54 1 : uint64_t value;
55 : /** Number of entries in the map */
56 1 : const size_t size;
57 : /** Number of entries already iterated */
58 1 : 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 : */
68 1 : 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 1 : 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 1 : 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 1 : 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 1 : 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 1 : 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 1 : 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 1 : 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 1 : struct sys_hashmap_api {
169 : /** Iterator constructor (in-place) */
170 1 : sys_hashmap_iterator_t iter;
171 : /** Clear the hash table, freeing all resources */
172 1 : sys_hashmap_clear_t clear;
173 : /** Insert a key-value pair into the Hashmap */
174 1 : sys_hashmap_insert_t insert;
175 : /** Remove a key-value pair from the Hashmap */
176 1 : sys_hashmap_remove_t remove;
177 : /** Retrieve the value associated with a given key from the Hashmap */
178 1 : 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 1 : struct sys_hashmap_config {
198 : /** Maximum number of entries */
199 1 : size_t max_size;
200 : /** Maximum load factor expressed in hundredths */
201 1 : uint8_t load_factor;
202 : /** Initial number of buckets to allocate */
203 1 : 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 1 : #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 1 : struct sys_hashmap_data {
226 : /** Pointer for implementation-specific Hashmap storage */
227 1 : void *buckets;
228 : /** The number of buckets currently allocated */
229 1 : size_t n_buckets;
230 : /** The number of entries currently in the Hashmap */
231 1 : size_t size;
232 : };
233 :
234 : /** @} */
235 :
236 : #ifdef __cplusplus
237 : }
238 : #endif
239 :
240 : #endif /* ZEPHYR_INCLUDE_SYS_HASHMAP_API_H_ */
|
