summaryrefslogtreecommitdiff
path: root/cesar/lib/bitqueue.h
blob: b43f9413ffdda430025337197d86e9ce675cf66d (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
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 */