#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 */