#include <cpu/types.h>
+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;
}
}
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);