X-Git-Url: https://codewiz.org/gitweb?a=blobdiff_plain;f=bertos%2Fstruct%2Fbitarray.h;h=791d46767ccc5012378640154108b79fa5aaa1d4;hb=78d223e73e58bdd267f59994a52c618b4eb277fa;hp=76899c50ba3843987ed48c4179f8a8dec8a7857c;hpb=d26ef6386f8936886450c186dd22c30c6079a8a1;p=bertos.git diff --git a/bertos/struct/bitarray.h b/bertos/struct/bitarray.h index 76899c50..791d4676 100644 --- a/bertos/struct/bitarray.h +++ b/bertos/struct/bitarray.h @@ -45,92 +45,189 @@ #include +typedef struct BitArray +{ + size_t size; /// Size in bytes of the bitarray + size_t bitarray_len; /// Number of bits used + uint8_t *array; /// Pointer to memory occupied by the bitarray +} BitArray; -#define ALLOC_BITARRAY(name, size) uint8_t name[DIV_ROUNDUP((size), 8)] -#define BIT_ARRAY_SIZE(name) (sizeof((name)) * 8) +/** + * Convenience macro to create a memory area for the BitArray. + * \param name Name of the variable. + * \param size Number of bits requested. It will be rounded to the nearest + * byte + */ +#define BITARRAY_ALLOC(name, size) uint8_t name[DIV_ROUNDUP((size), 8)] -INLINE void bitarray_set(int idx, uint8_t *bit_array, size_t len) +/** + * Set one bit into the bit array. + * \param bitx BitArray context + * \param idx The bit to set + */ +INLINE void bitarray_set(BitArray *bitx, int idx) { - ASSERT((size_t)idx <= len); + ASSERT((size_t)idx <= bitx->bitarray_len); + int page = idx / 8; uint8_t bit = idx % 8; - bit_array[page] |= BV(bit); + bitx->array[page] |= BV(bit); } -INLINE void bitarray_clear(int idx, uint8_t *bit_array, size_t len) +/** + * Clear one bit in the bit array. + * \param bitx BitArray context + * \param idx The bit to clear + */ +INLINE void bitarray_clear(BitArray *bitx, int idx) { - ASSERT((size_t)idx <= len); + ASSERT((size_t)idx <= bitx->bitarray_len); + int page = idx / 8; uint8_t bit = idx % 8; - bit_array[page] &= ~BV(bit); + bitx->array[page] &= ~BV(bit); } -INLINE void bitarray_setOffset(int idx, int offset, uint8_t *bit_array, size_t len) +/** + * Set a range of bits. + * + * The range starts from \a idx (inclusive) and spans \a offset bits. + * + * \param bitx BitArray context + * \param idx Starting bit + * \param offset Number of bit to set + */ +INLINE void bitarray_setRange(BitArray *bitx, int idx, int offset) { - ASSERT((size_t)idx <= len); + ASSERT((size_t)idx <= bitx->bitarray_len); for (int i = idx; i < offset + idx; i++) - bitarray_set(i, bit_array, len); + bitarray_set(bitx, i); } - -INLINE void bitarray_clearOffset(int idx, int offset, uint8_t *bit_array, size_t len) +/** + * Clear a range of bits. + * + * The range starts from \a idx (inclusive) and spans \a offset bits. + * + * \param bitx BitArray context + * \param idx Starting bit + * \param offset Number of bits to clear + */ +INLINE void bitarray_clearRange(BitArray *bitx, int idx, int offset) { - ASSERT((size_t)idx <= len); + ASSERT((size_t)idx <= bitx->bitarray_len); for (int i = idx; i < offset + idx; i++) - bitarray_clear(i, bit_array, len); + bitarray_clear(bitx, i); } -INLINE bool bitarray_check(int idx, uint8_t *bit_array, size_t len) +/** + * Test a bit. + * + * \param bitx BitArray context + * \param idx Bit to test + * \return True if bit is set, false otherwise. + */ +INLINE bool bitarray_test(BitArray *bitx, int idx) { - ASSERT((size_t)idx <= len); + ASSERT((size_t)idx <= bitx->bitarray_len); int page = idx / 8; uint8_t bit = idx % 8; - return (bit_array[page] & BV(bit)); + return (bitx->array[page] & BV(bit)); } -INLINE bool bitarray_full(uint8_t *bit_array, size_t len) +/** + * Check if the bitarray is full + * + * Only \a bitarray_len bits are tested. + * + * \param bitx BitArray to test + * \return True if \a bitx is full, false otherwise + */ +INLINE bool bitarray_isFull(BitArray *bitx) { - int count = len; - for (size_t page = 0; page <= len / 8; page++) + // test full bytes except the last one + for (size_t page = 0; page <= bitx->size - 2; page++) { - if (count < 8) - { - for (size_t i = page * 8; i <= len; i++) - if (!bitarray_check(i, bit_array, len)) - return 0; - count--; - } - else - { - if (!(bit_array[page] == 0xff)) - return 0; - } - count -= 8; + if (!(bitx->array[page] == 0xff)) + return 0; } + // test the last byte using the correct bitmask + uint8_t mask = BV(bitx->bitarray_len >> 3) - 1; + if (!(bitx->array[bitx->size - 1] & mask)) + return 0; return 1; } +/* + * Ugly!.. reformat it. + */ +/** + * Test if a range of bit is full. + * + * \param bitx BitArray context + * \param idx Starting bit + * \param offset Number of bits to test + * \return True if range is full, false otherwise + */ +INLINE bool bitarray_isRangeFull(BitArray *bitx, int idx, int offset) +{ + ASSERT((size_t)(idx + offset) <= bitx->bitarray_len); + + for (int i = idx; i <= idx + offset; i++) + if (!bitarray_test(bitx, i)) + return 0; + + return 1; +} -INLINE void bitarray_dump(uint8_t *bit_array, size_t len) +/* + * Ugly!.. reformat it. + */ +/** + * Test if a range of bit is empty. + * + * \param bitx BitArray context + * \param idx Starting bit + * \param offset Number of bits to test + * \return True if range is empty, false otherwise + */ +INLINE bool bitarray_isRangeEmpty(BitArray *bitx, int idx, int offset) { - kprintf("bitarray size[%zu]bits\n", len); + ASSERT((size_t)(idx + offset) <= bitx->bitarray_len); + + for (int i = idx; i <= idx + offset; i++) + if (bitarray_test(bitx, i)) + return 0; + + return 1; +} + +/** + * Print on debug serial a BitArray. + * \note This module does not use the logging module, so you + * can't decide the logging level. + * \param bitx BitArray to be printed. + */ +INLINE void bitarray_dump(BitArray *bitx) +{ + kprintf("bitarray size[%zu]bits on [%zu]bytes\n", bitx->bitarray_len, bitx->size); int i = 0; int j = 0; - int count = len; + int count = bitx->bitarray_len; while (count--) { - kprintf("%d", bitarray_check(i++, bit_array, len)); + kprintf("%d", bitarray_test(bitx, i++)); if (j == 7) { - kprintf("..%02x [%d]\n", bit_array[(i / 8) - 1], i); + kprintf("..%02x [%d]\n", bitx->array[(i / 8) - 1], i); j = 0; continue; } @@ -138,9 +235,35 @@ INLINE void bitarray_dump(uint8_t *bit_array, size_t len) } if (j != 0) - kprintf("..%02x [%d]\n", bit_array[i / 8], i); + kprintf("..%02x [%d]\n", bitx->array[i / 8], i); +} + +int bitarray_firstSetBit(BitArray *bitx); + +/** + * Init a BitArray. + * + * The BitArray uses an external array for storage. You can use the macro + * BITARRAY_ALLOC to declare an appropriate memory size. Example usage: + * \code + * BITARRAY_ALLOC(bits_mem, 17); + * BitArray bits; + * bitarray_init(&bits, 17, bits_mem, sizeof(bits_mem)) + * \endcode + * + * \param bitx BitArray context + * \param bitarray_len Number of bits in the BitArray + * \param array Memory area for the BitArray + * \param size Size (in bytes) of the memory area \a array + */ +INLINE void bitarray_init(BitArray *bitx, size_t bitarray_len, uint8_t *array, size_t size) +{ + bitx->size = size; + bitx->array = array; + bitx->bitarray_len = bitarray_len; } + int bitarray_testSetup(void); int bitarray_testRun(void); int bitarray_testTearDown(void);