summaryrefslogtreecommitdiff
path: root/cesar/lib/bitqueue.h
diff options
context:
space:
mode:
authorNicolas Schodet2012-09-14 15:31:29 +0200
committerNicolas Schodet2012-12-03 16:35:18 +0100
commitfe41aaf717fe7ce96884f95774de9529dc3bd196 (patch)
tree98488b8f8a8b09142d6fa84dd20d5ef808b44a5e /cesar/lib/bitqueue.h
parent4678a06a0e230e6661b53fbd8dbb7550ad66ae53 (diff)
cesar/lib: add new bitqueue tool, refs #3340
Diffstat (limited to 'cesar/lib/bitqueue.h')
-rw-r--r--cesar/lib/bitqueue.h155
1 files changed, 155 insertions, 0 deletions
diff --git a/cesar/lib/bitqueue.h b/cesar/lib/bitqueue.h
new file mode 100644
index 0000000000..b43f9413ff
--- /dev/null
+++ b/cesar/lib/bitqueue.h
@@ -0,0 +1,155 @@
+#ifndef bitqueue_h
+#define bitqueue_h
+/* Cesar project {{{
+ *
+ * Copyright (C) 2012 Spidcom
+ *
+ * <<<Licence>>>
+ *
+ * }}} */
+/**
+ * \file bitqueue.h
+ * \brief Handle a round robin queue using a bit mask.
+ * \ingroup lib
+ *
+ * A bitqueue can be used to find the next active entry in a set, using round
+ * robin. The queue is implemented as a bit mask where every bit set
+ * represents an active entry.
+ *
+ * The bit mask is composed of an array of 32 bit words. Index 0 is in the
+ * LSB of the first word. The last bit can not be used (more exactly, it can
+ * never be used as the start index).
+ *
+ * No effort is done to support configuration where the number of entry is not
+ * one less of a multiple of 32, but this should not be a problem as long as
+ * the unused bits are always zero.
+ */
+
+/** Compute bitqueue size for a number of entries. This handles the last bit
+ * which can not be used. */
+#define BITQUEUE_SIZE(entries_nb) CEIL_DIV((entries_nb) + 1, 32)
+
+/**
+ * Initialise an empty bitqueue.
+ * \param bitqueue bitqueue array
+ * \param bitqueue_size number of word in bitqueue
+ */
+extern inline void
+bitqueue_init (u32 *bitqueue, uint bitqueue_size)
+{
+ uint i;
+ for (i = 0; i < bitqueue_size; i++)
+ bitqueue[i] = 0;
+}
+
+/**
+ * Update a bitqueue entry.
+ * \param bitqueue bitqueue array
+ * \param index index of bit to update in bitqueue
+ * \param value non-zero to set, zero to reset the bit
+ *
+ * No bound checking is done, this must be handled by caller.
+ */
+extern inline void
+bitqueue_update (u32 *bitqueue, uint index, uint value)
+{
+ uint wmask = 1 << (index % 32);
+ if (value)
+ bitqueue[index / 32] |= wmask;
+ else
+ bitqueue[index / 32] &= ~wmask;
+}
+
+/**
+ * Set a bitqueue entry.
+ * \param bitqueue bitqueue array
+ * \param index index of bit to set in bitqueue
+ *
+ * No bound checking is done, this must be handled by caller.
+ */
+extern inline void
+bitqueue_set (u32 *bitqueue, uint index)
+{
+ uint wmask = 1 << (index % 32);
+ bitqueue[index / 32] |= wmask;
+}
+
+/**
+ * Reset a bitqueue entry.
+ * \param bitqueue bitqueue array
+ * \param index index of bit to reset in bitqueue
+ *
+ * No bound checking is done, this must be handled by caller.
+ */
+extern inline void
+bitqueue_reset (u32 *bitqueue, uint index)
+{
+ uint wmask = 1 << (index % 32);
+ bitqueue[index / 32] &= ~wmask;
+}
+
+/**
+ * Find next set bit in a bitqueue.
+ * \param bitqueue bitqueue array
+ * \param bitqueue_size number of word in bitqueue
+ * \param start start bit
+ * \return the index of the set bit in the queue after the start bit, or -1
+ * if no bit set
+ */
+extern inline int
+bitqueue_find_next (const u32 *bitqueue, uint bitqueue_size, uint start)
+{
+ uint wi, startbi, stopwi, attwi;
+ u32 w;
+ bool again;
+ /* Check parameters. */
+ dbg_claim (bitqueue && start < bitqueue_size * 32 - 1);
+ /* Word index and bit start index. Here is the limitation about the last
+ * bit which can not be used as a start bit. */
+ start++;
+ wi = start / 32;
+ startbi = start % 32;
+ /* Stop word, the word after the current one at the second iteration
+ * because the start word should be examined two time (MSB first, then LSB
+ * if no other word is set). */
+ stopwi = wi + 1;
+ /* Attention needed word index, loop as fast as possible until reached. */
+ attwi = bitqueue_size;
+ /* Load the first word, mask out previous bits. */
+ w = bitqueue[wi] >> startbi;
+ /* Start with the first loop. */
+ again = true;
+ while (1)
+ {
+ if (w)
+ {
+ /* Something is found, find the bit index and overall index. */
+ uint bi;
+ for (bi = startbi; !(w & 1); bi++)
+ w >>= 1;
+ return wi * 32 + bi;
+ }
+ else
+ {
+ /* Nothing found continue with next word. */
+ wi++;
+ startbi = 0;
+ if (wi == attwi)
+ {
+ /* If end of queue reached, loop again. */
+ if (again)
+ {
+ wi = 0;
+ attwi = stopwi;
+ again = false;
+ }
+ else
+ break;
+ }
+ w = bitqueue[wi];
+ }
+ }
+ return -1;
+}
+
+#endif /* bitqueue_h */