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 * Free bits in a bit array 173 * 174 * This marks the number of bits (@p num_bits) starting from @p offset 175 * as no longer allocated. 176 * 177 * @param bitarray Bitarray struct 178 * @param num_bits Number of bits to free 179 * @param offset Starting bit position to free 180 * 181 * @retval 0 Free is successful 182 * @retval -EINVAL Invalid argument (e.g. try to free more bits than 183 * the bitarray has, trying to free 0 bits, etc.) 184 * @retval -EFAULT The bits in the indicated region are not all allocated. 185 */ 186 int sys_bitarray_free(sys_bitarray_t *bitarray, size_t num_bits, 187 size_t offset); 188 189 /** 190 * Test if bits in a region is all set. 191 * 192 * This tests if the number of bits (@p num_bits) in region starting 193 * from @p offset are all set. 194 * 195 * @param bitarray Bitarray struct 196 * @param num_bits Number of bits to test 197 * @param offset Starting bit position to test 198 * 199 * @retval true All bits are set. 200 * @retval false Not all bits are set. 201 */ 202 bool sys_bitarray_is_region_set(sys_bitarray_t *bitarray, size_t num_bits, 203 size_t offset); 204 205 /** 206 * Test if bits in a region is all cleared. 207 * 208 * This tests if the number of bits (@p num_bits) in region starting 209 * from @p offset are all cleared. 210 * 211 * @param bitarray Bitarray struct 212 * @param num_bits Number of bits to test 213 * @param offset Starting bit position to test 214 * 215 * @retval true All bits are cleared. 216 * @retval false Not all bits are cleared. 217 */ 218 bool sys_bitarray_is_region_cleared(sys_bitarray_t *bitarray, size_t num_bits, 219 size_t offset); 220 221 /** 222 * Set all bits in a region. 223 * 224 * This sets the number of bits (@p num_bits) in region starting 225 * from @p offset. 226 * 227 * @param bitarray Bitarray struct 228 * @param num_bits Number of bits to test 229 * @param offset Starting bit position to test 230 * 231 * @retval 0 Operation successful 232 * @retval -EINVAL Invalid argument (e.g. bit to set exceeds 233 * the number of bits in bit array, etc.) 234 */ 235 int sys_bitarray_set_region(sys_bitarray_t *bitarray, size_t num_bits, 236 size_t offset); 237 238 /** 239 * Test if all bits in a region are cleared/set and set/clear them 240 * in a single atomic operation 241 * 242 * This checks if all the bits (@p num_bits) in region starting 243 * from @p offset are in required state. If even one bit is not, 244 * -EEXIST is returned. If the whole region is set/cleared 245 * it is set to opposite state. The check and set is performed as a single 246 * atomic operation. 247 * 248 * @param bitarray Bitarray struct 249 * @param num_bits Number of bits to test and set 250 * @param offset Starting bit position to test and set 251 * @param to_set if true the region will be set if all bits are cleared 252 * if false the region will be cleard if all bits are set 253 * 254 * @retval 0 Operation successful 255 * @retval -EINVAL Invalid argument (e.g. bit to set exceeds 256 * the number of bits in bit array, etc.) 257 * @retval -EEXIST at least one bit in the region is set/cleared, 258 * operation cancelled 259 */ 260 int sys_bitarray_test_and_set_region(sys_bitarray_t *bitarray, size_t num_bits, 261 size_t offset, bool to_set); 262 263 /** 264 * Clear all bits in a region. 265 * 266 * This clears the number of bits (@p num_bits) in region starting 267 * from @p offset. 268 * 269 * @param bitarray Bitarray struct 270 * @param num_bits Number of bits to test 271 * @param offset Starting bit position to test 272 * 273 * @retval 0 Operation successful 274 * @retval -EINVAL Invalid argument (e.g. bit to set exceeds 275 * the number of bits in bit array, etc.) 276 */ 277 int sys_bitarray_clear_region(sys_bitarray_t *bitarray, size_t num_bits, 278 size_t offset); 279 280 /** 281 * @} 282 */ 283 284 #ifdef __cplusplus 285 } 286 #endif 287 288 #endif /* ZEPHYR_INCLUDE_SYS_BITARRAY_H_ */ 289
