1 /* 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 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 #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 #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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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_ */ 344
