From fe41aaf717fe7ce96884f95774de9529dc3bd196 Mon Sep 17 00:00:00 2001 From: Nicolas Schodet Date: Fri, 14 Sep 2012 15:31:29 +0200 Subject: cesar/lib: add new bitqueue tool, refs #3340 --- cesar/lib/bitqueue.h | 155 +++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 155 insertions(+) create mode 100644 cesar/lib/bitqueue.h (limited to 'cesar/lib/bitqueue.h') 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 + * + * <<>> + * + * }}} */ +/** + * \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 */ -- cgit v1.2.3