lib: bitfield: new macros for bit processing

New macros have been added for the following -
1. to efficiently iterate and execute functions on already set bits
2. to check if a bit is in use
3. to check if a bitfield has been initialized (this is to safetly
handle cases where the bitfield is freed and re-allocated).
4. to check if two bitfields have the same bits set

Signed-off-by: Anuradha Karuppiah <anuradhak@cumulusnetworks.com>

1 files changed, 42 insertions, 1 deletions

diff --git a/lib/bitfield.h b/lib/bitfield.h
index 72980165f9..244938933b 100644
--- a/lib/bitfield.h
+++ b/lib/bitfield.h
@@ -58,7 +58,7 @@ typedef unsigned int word_t;
  * @n: The current word number that is being used.
  * @m: total number of words in 'data'
  */
-#define bitfield_t struct { word_t *data; size_t n, m; }
+typedef struct {word_t *data; size_t n, m; } bitfield_t;
 
 /**
  * Initialize the bits.
@@ -97,6 +97,16 @@ typedef unsigned int word_t;
 #define bf_release_index(v, id)                                                \
 	(v).data[bf_index(id)] &= ~(1 << (bf_offset(id)))
 
+/* check if an id is in use */
+#define bf_test_index(v, id)                                                \
+	((v).data[bf_index(id)] & (1 << (bf_offset(id))))
+
+/* check if the bit field has been setup */
+#define bf_is_inited(v) ((v).data)
+
+/* compare two bitmaps of the same length */
+#define bf_cmp(v1, v2) (memcmp((v1).data, (v2).data, ((v1).m * sizeof(word_t))))
+
 /*
  * return 0th index back to bitfield
  */
@@ -146,6 +156,37 @@ typedef unsigned int word_t;
 		(b) += (w * WORD_SIZE);                                        \
 	} while (0)
 
+static inline unsigned int bf_find_next_set_bit(bitfield_t v,
+		word_t start_index)
+{
+	int start_bit;
+	unsigned long i, offset;
+
+	start_bit = start_index & (WORD_SIZE - 1);
+
+	for (i = bf_index(start_index); i < v.m; ++i) {
+		if (v.data[i] == 0) {
+			/* if the whole word is empty move to the next */
+			start_bit = 0;
+			continue;
+		}
+		/* scan one word for set bits */
+		for (offset = start_bit; offset < WORD_SIZE; ++offset) {
+			if ((v.data[i] >> offset) & 1)
+				return ((i * WORD_SIZE) + offset);
+		}
+		/* move to the next word */
+		start_bit = 0;
+	}
+	return WORD_MAX;
+}
+
+/* iterate through all the set bits */
+#define bf_for_each_set_bit(v, b, max)                 \
+	for ((b) = bf_find_next_set_bit((v), 0);           \
+			(b) < max;                                 \
+			(b) = bf_find_next_set_bit((v), (b) + 1))
+
 /*
  * Free the allocated memory for data
  * @v: an instance of bitfield_t struct.