Line data Source code
1 0 : /*
2 : * Copyright (c) 2021 Intel Corporation
3 : *
4 : * SPDX-License-Identifier: Apache-2.0
5 : */
6 :
7 : #ifndef ZEPHYR_INCLUDE_SYS_BITARRAY_H_
8 : #define ZEPHYR_INCLUDE_SYS_BITARRAY_H_
9 :
10 : #ifdef __cplusplus
11 : extern "C" {
12 : #endif
13 :
14 : #include <stddef.h>
15 : #include <stdint.h>
16 :
17 : #include <zephyr/kernel.h>
18 : #include <zephyr/sys/util.h>
19 :
20 : /**
21 : * @file
22 : *
23 : * @defgroup bitarray_apis Bit array
24 : * @ingroup datastructure_apis
25 : *
26 : * @brief Store and manipulate bits in a bit array.
27 : *
28 : * @{
29 : */
30 :
31 : /** @cond INTERNAL_HIDDEN */
32 : struct sys_bitarray {
33 : /* Number of bits */
34 : uint32_t num_bits;
35 :
36 : /* Number of bundles */
37 : uint32_t num_bundles;
38 :
39 : /* Bundle of bits */
40 : uint32_t *bundles;
41 :
42 : /* Spinlock guarding access to this bit array */
43 : struct k_spinlock lock;
44 : };
45 : /** @endcond */
46 :
47 : /** Bitarray structure */
48 1 : typedef struct sys_bitarray sys_bitarray_t;
49 :
50 : /**
51 : * @brief Create a bitarray object.
52 : *
53 : * @param name Name of the bitarray object.
54 : * @param total_bits Total number of bits in this bitarray object.
55 : * @param sba_mod Modifier to the bitarray variables.
56 : */
57 : #define _SYS_BITARRAY_DEFINE(name, total_bits, sba_mod) \
58 : sba_mod uint32_t _sys_bitarray_bundles_##name \
59 : [DIV_ROUND_UP(DIV_ROUND_UP(total_bits, 8), \
60 : sizeof(uint32_t))] = {0}; \
61 : sba_mod sys_bitarray_t name = { \
62 : .num_bits = (total_bits), \
63 : .num_bundles = DIV_ROUND_UP( \
64 : DIV_ROUND_UP(total_bits, 8), sizeof(uint32_t)), \
65 : .bundles = _sys_bitarray_bundles_##name, \
66 : }
67 :
68 : /**
69 : * @brief Create a bitarray object.
70 : *
71 : * @param name Name of the bitarray object.
72 : * @param total_bits Total number of bits in this bitarray object.
73 : */
74 1 : #define SYS_BITARRAY_DEFINE(name, total_bits) \
75 : _SYS_BITARRAY_DEFINE(name, total_bits,)
76 :
77 : /**
78 : * @brief Create a static bitarray object.
79 : *
80 : * @param name Name of the bitarray object.
81 : * @param total_bits Total number of bits in this bitarray object.
82 : */
83 1 : #define SYS_BITARRAY_DEFINE_STATIC(name, total_bits) \
84 : _SYS_BITARRAY_DEFINE(name, total_bits, static)
85 :
86 : /**
87 : * Set a bit in a bit array
88 : *
89 : * @param[in] bitarray Bitarray struct
90 : * @param[in] bit The bit to be set
91 : *
92 : * @retval 0 Operation successful
93 : * @retval -EINVAL Invalid argument (e.g. bit to set exceeds
94 : * the number of bits in bit array, etc.)
95 : */
96 1 : int sys_bitarray_set_bit(sys_bitarray_t *bitarray, size_t bit);
97 :
98 : /**
99 : * Clear a bit in a bit array
100 : *
101 : * @param[in] bitarray Bitarray struct
102 : * @param[in] bit The bit to be cleared
103 : *
104 : * @retval 0 Operation successful
105 : * @retval -EINVAL Invalid argument (e.g. bit to clear exceeds
106 : * the number of bits in bit array, etc.)
107 : */
108 1 : int sys_bitarray_clear_bit(sys_bitarray_t *bitarray, size_t bit);
109 :
110 : /**
111 : * Test whether a bit is set or not
112 : *
113 : * @param[in] bitarray Bitarray struct
114 : * @param[in] bit The bit to be tested
115 : * @param[out] val The value of the bit (0 or 1)
116 : *
117 : * @retval 0 Operation successful
118 : * @retval -EINVAL Invalid argument (e.g. bit to test exceeds
119 : * the number of bits in bit array, etc.)
120 : */
121 1 : int sys_bitarray_test_bit(sys_bitarray_t *bitarray, size_t bit, int *val);
122 :
123 : /**
124 : * Test the bit and set it
125 : *
126 : * @param[in] bitarray Bitarray struct
127 : * @param[in] bit The bit to be tested and set
128 : * @param[out] prev_val Previous value of the bit (0 or 1)
129 : *
130 : * @retval 0 Operation successful
131 : * @retval -EINVAL Invalid argument (e.g. bit to test exceeds
132 : * the number of bits in bit array, etc.)
133 : */
134 1 : int sys_bitarray_test_and_set_bit(sys_bitarray_t *bitarray, size_t bit, int *prev_val);
135 :
136 : /**
137 : * Test the bit and clear it
138 : *
139 : * @param[in] bitarray Bitarray struct
140 : * @param[in] bit The bit to be tested and cleared
141 : * @param[out] prev_val Previous value of the bit (0 or 1)
142 : *
143 : * @retval 0 Operation successful
144 : * @retval -EINVAL Invalid argument (e.g. bit to test exceeds
145 : * the number of bits in bit array, etc.)
146 : */
147 1 : int sys_bitarray_test_and_clear_bit(sys_bitarray_t *bitarray, size_t bit, int *prev_val);
148 :
149 : /**
150 : * Allocate bits in a bit array
151 : *
152 : * This finds a number of bits (@p num_bits) in a contiguous of
153 : * previously unallocated region. If such a region exists, the bits are
154 : * marked as allocated and the offset to the start of this region is
155 : * returned via @p offset.
156 : *
157 : * @param[in] bitarray Bitarray struct
158 : * @param[in] num_bits Number of bits to allocate
159 : * @param[out] offset Offset to the start of allocated region if
160 : * successful
161 : *
162 : * @retval 0 Allocation successful
163 : * @retval -EINVAL Invalid argument (e.g. allocating more bits than
164 : * the bitarray has, trying to allocate 0 bits, etc.)
165 : * @retval -ENOSPC No contiguous region big enough to accommodate
166 : * the allocation
167 : */
168 1 : int sys_bitarray_alloc(sys_bitarray_t *bitarray, size_t num_bits,
169 : size_t *offset);
170 :
171 : /**
172 : * Calculates the bit-wise XOR of two bitarrays in a region.
173 : * The result is stored in the first bitarray passed in (@p dst).
174 : * Both bitarrays must be of the same size.
175 : *
176 : * @param dst Bitarray struct
177 : * @param other Bitarray struct
178 : * @param num_bits Number of bits in the region, must be larger than 0
179 : * @param offset Starting bit location
180 : *
181 : * @retval 0 Operation successful
182 : * @retval -EINVAL Invalid argument (e.g. out-of-bounds access, mismatching bitarrays, trying to xor
183 : * 0 bits, etc.)
184 : */
185 1 : int sys_bitarray_xor(sys_bitarray_t *dst, sys_bitarray_t *other, size_t num_bits, size_t offset);
186 :
187 : /**
188 : * Find nth bit set in region
189 : *
190 : * This counts the number of bits set (@p count) in a
191 : * region (@p offset, @p num_bits) and returns the index (@p found_at)
192 : * of the nth set bit, if it exists, as long with a zero return value.
193 : *
194 : * If it does not exist, @p found_at is not updated and the method returns
195 : *
196 : * @param[in] bitarray Bitarray struct
197 : * @param[in] n Nth bit set to look for
198 : * @param[in] num_bits Number of bits to check, must be larger than 0
199 : * @param[in] offset Starting bit position
200 : * @param[out] found_at Index of the nth bit set, if found
201 : *
202 : * @retval 0 Operation successful
203 : * @retval 1 Nth bit set was not found in region
204 : * @retval -EINVAL Invalid argument (e.g. out-of-bounds access, trying to count 0 bits, etc.)
205 : */
206 1 : int sys_bitarray_find_nth_set(sys_bitarray_t *bitarray, size_t n, size_t num_bits, size_t offset,
207 : size_t *found_at);
208 :
209 : /**
210 : * Count bits set in a bit array region
211 : *
212 : * This counts the number of bits set (@p count) in a
213 : * region (@p offset, @p num_bits).
214 : *
215 : * @param[in] bitarray Bitarray struct
216 : * @param[in] num_bits Number of bits to check, must be larger than 0
217 : * @param[in] offset Starting bit position
218 : * @param[out] count Number of bits set in the region if successful
219 : *
220 : * @retval 0 Operation successful
221 : * @retval -EINVAL Invalid argument (e.g. out-of-bounds access, trying to count 0 bits, etc.)
222 : */
223 1 : int sys_bitarray_popcount_region(sys_bitarray_t *bitarray, size_t num_bits, size_t offset,
224 : size_t *count);
225 :
226 : /**
227 : * Free bits in a bit array
228 : *
229 : * This marks the number of bits (@p num_bits) starting from @p offset
230 : * as no longer allocated.
231 : *
232 : * @param bitarray Bitarray struct
233 : * @param num_bits Number of bits to free
234 : * @param offset Starting bit position to free
235 : *
236 : * @retval 0 Free is successful
237 : * @retval -EINVAL Invalid argument (e.g. try to free more bits than
238 : * the bitarray has, trying to free 0 bits, etc.)
239 : * @retval -EFAULT The bits in the indicated region are not all allocated.
240 : */
241 1 : int sys_bitarray_free(sys_bitarray_t *bitarray, size_t num_bits,
242 : size_t offset);
243 :
244 : /**
245 : * Test if bits in a region is all set.
246 : *
247 : * This tests if the number of bits (@p num_bits) in region starting
248 : * from @p offset are all set.
249 : *
250 : * @param bitarray Bitarray struct
251 : * @param num_bits Number of bits to test
252 : * @param offset Starting bit position to test
253 : *
254 : * @retval true All bits are set.
255 : * @retval false Not all bits are set.
256 : */
257 1 : bool sys_bitarray_is_region_set(sys_bitarray_t *bitarray, size_t num_bits,
258 : size_t offset);
259 :
260 : /**
261 : * Test if bits in a region is all cleared.
262 : *
263 : * This tests if the number of bits (@p num_bits) in region starting
264 : * from @p offset are all cleared.
265 : *
266 : * @param bitarray Bitarray struct
267 : * @param num_bits Number of bits to test
268 : * @param offset Starting bit position to test
269 : *
270 : * @retval true All bits are cleared.
271 : * @retval false Not all bits are cleared.
272 : */
273 1 : bool sys_bitarray_is_region_cleared(sys_bitarray_t *bitarray, size_t num_bits,
274 : size_t offset);
275 :
276 : /**
277 : * Set all bits in a region.
278 : *
279 : * This sets the number of bits (@p num_bits) in region starting
280 : * from @p offset.
281 : *
282 : * @param bitarray Bitarray struct
283 : * @param num_bits Number of bits to test
284 : * @param offset Starting bit position to test
285 : *
286 : * @retval 0 Operation successful
287 : * @retval -EINVAL Invalid argument (e.g. bit to set exceeds
288 : * the number of bits in bit array, etc.)
289 : */
290 1 : int sys_bitarray_set_region(sys_bitarray_t *bitarray, size_t num_bits,
291 : size_t offset);
292 :
293 : /**
294 : * Test if all bits in a region are cleared/set and set/clear them
295 : * in a single atomic operation
296 : *
297 : * This checks if all the bits (@p num_bits) in region starting
298 : * from @p offset are in required state. If even one bit is not,
299 : * -EEXIST is returned. If the whole region is set/cleared
300 : * it is set to opposite state. The check and set is performed as a single
301 : * atomic operation.
302 : *
303 : * @param bitarray Bitarray struct
304 : * @param num_bits Number of bits to test and set
305 : * @param offset Starting bit position to test and set
306 : * @param to_set if true the region will be set if all bits are cleared
307 : * if false the region will be cleard if all bits are set
308 : *
309 : * @retval 0 Operation successful
310 : * @retval -EINVAL Invalid argument (e.g. bit to set exceeds
311 : * the number of bits in bit array, etc.)
312 : * @retval -EEXIST at least one bit in the region is set/cleared,
313 : * operation cancelled
314 : */
315 1 : int sys_bitarray_test_and_set_region(sys_bitarray_t *bitarray, size_t num_bits,
316 : size_t offset, bool to_set);
317 :
318 : /**
319 : * Clear all bits in a region.
320 : *
321 : * This clears the number of bits (@p num_bits) in region starting
322 : * from @p offset.
323 : *
324 : * @param bitarray Bitarray struct
325 : * @param num_bits Number of bits to test
326 : * @param offset Starting bit position to test
327 : *
328 : * @retval 0 Operation successful
329 : * @retval -EINVAL Invalid argument (e.g. bit to set exceeds
330 : * the number of bits in bit array, etc.)
331 : */
332 1 : int sys_bitarray_clear_region(sys_bitarray_t *bitarray, size_t num_bits,
333 : size_t offset);
334 :
335 : /**
336 : * @}
337 : */
338 :
339 : #ifdef __cplusplus
340 : }
341 : #endif
342 :
343 : #endif /* ZEPHYR_INCLUDE_SYS_BITARRAY_H_ */
|
