X-Git-Url: https://codewiz.org/gitweb?a=blobdiff_plain;f=bertos%2Fstruct%2Fbitarray.h;h=791d46767ccc5012378640154108b79fa5aaa1d4;hb=9a9f21e5cfc92ab7eddb27d4996923a9e5100513;hp=3bbaa8d19cf277b96037f0da96ee4eb4fb76c33a;hpb=f56cf80247f6fbe18ddd34357ee306107fffeca0;p=bertos.git

diff --git a/bertos/struct/bitarray.h b/bertos/struct/bitarray.h
index 3bbaa8d1..791d4676 100644
--- a/bertos/struct/bitarray.h
+++ b/bertos/struct/bitarray.h
@@ -47,14 +47,24 @@
 
 typedef struct BitArray
 {
-	size_t size;
-	size_t bitarray_len;
-	uint8_t *array;
+	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)]
 
+/**
+ * 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 <= bitx->bitarray_len);
@@ -65,6 +75,11 @@ INLINE void bitarray_set(BitArray *bitx, int idx)
 	bitx->array[page] |= BV(bit);
 }
 
+/**
+ * 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 <= bitx->bitarray_len);
@@ -75,7 +90,16 @@ INLINE void bitarray_clear(BitArray *bitx, int idx)
 	bitx->array[page] &= ~BV(bit);
 }
 
-INLINE void bitarray_setOffset(BitArray *bitx, int idx, int offset)
+/**
+ * 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 <= bitx->bitarray_len);
 
@@ -83,8 +107,16 @@ INLINE void bitarray_setOffset(BitArray *bitx, int idx, int offset)
 		bitarray_set(bitx, i);
 }
 
-
-INLINE void bitarray_clearOffset(BitArray *bitx, int idx, int offset)
+/**
+ * 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 <= bitx->bitarray_len);
 
@@ -92,7 +124,14 @@ INLINE void bitarray_clearOffset(BitArray *bitx, int idx, int offset)
 		bitarray_clear(bitx, i);
 }
 
-INLINE bool bitarray_check(BitArray *bitx, int idx)
+/**
+ * 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 <= bitx->bitarray_len);
 	int page = idx / 8;
@@ -101,28 +140,26 @@ INLINE bool bitarray_check(BitArray *bitx, int idx)
 	return (bitx->array[page] & BV(bit));
 }
 
-/*
- * Ugly!.. reformat it.
+/**
+ * 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_full(BitArray *bitx)
+INLINE bool bitarray_isFull(BitArray *bitx)
 {
-	int count = bitx->size;
-	for (size_t page = 0; page <= bitx->size / 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 <= bitx->bitarray_len; i++)
-				if (!bitarray_check(bitx, i))
-					return 0;
-				count--;
-		}
-		else
-		{
-			if (!(bitx->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;
 }
@@ -130,12 +167,20 @@ INLINE bool bitarray_full(BitArray *bitx)
 /*
  * Ugly!.. reformat it.
  */
-INLINE bool bitarray_blockFull(BitArray *bitx, int idx, int offset)
+/**
+ * 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_check(bitx, i))
+		if (!bitarray_test(bitx, i))
 			return 0;
 
 	return 1;
@@ -144,18 +189,31 @@ INLINE bool bitarray_blockFull(BitArray *bitx, int idx, int offset)
 /*
  * Ugly!.. reformat it.
  */
-INLINE bool bitarray_blockEmpty(BitArray *bitx, int idx, int offset)
+/**
+ * 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)
 {
 	ASSERT((size_t)(idx + offset) <= bitx->bitarray_len);
 
 	for (int i = idx; i <= idx + offset; i++)
-		if (bitarray_check(bitx, 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);
@@ -166,7 +224,7 @@ INLINE void bitarray_dump(BitArray *bitx)
 
 	while (count--)
 	{
-		kprintf("%d", bitarray_check(bitx, i++));
+		kprintf("%d", bitarray_test(bitx, i++));
 		if (j == 7)
 		{
 			kprintf("..%02x [%d]\n", bitx->array[(i / 8) - 1], i);
@@ -180,7 +238,25 @@ INLINE void bitarray_dump(BitArray *bitx)
 		kprintf("..%02x [%d]\n", bitx->array[i / 8], i);
 }
 
-INLINE void init_bitarray(BitArray *bitx, size_t bitarray_len, uint8_t *array, size_t size)
+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;