]>
git.proxmox.com Git - mirror_frr.git/blob - lib/bitfield.h
1 // SPDX-License-Identifier: GPL-2.0-or-later
3 * Copyright (C) 2016 Cumulus Networks, Inc.
6 * A simple bit array implementation to allocate and free IDs. An example
7 * of its usage is in allocating link state IDs for OSPFv3 as OSPFv3 has
8 * removed all address semantics from LS ID. Another usage can be in
9 * allocating IDs for BGP neighbors (and dynamic update groups) for
10 * efficient storage of adj-rib-out.
13 * #include "bitfield.h"
15 * bitfield_t bitfield;
17 * bf_init(bitfield, 32);
19 * bf_assign_index(bitfield, id1);
20 * bf_assign_index(bitfield, id2);
22 * bf_release_index(bitfield, id1);
36 typedef unsigned int word_t
;
37 #define WORD_MAX 0xFFFFFFFF
38 #define WORD_SIZE (sizeof(word_t) * 8)
41 * The bitfield structure.
42 * @data: the bits to manage.
43 * @n: The current word number that is being used.
44 * @m: total number of words in 'data'
46 typedef struct {word_t
*data
; size_t n
, m
; } bitfield_t
;
48 DECLARE_MTYPE(BITFIELD
);
51 * Initialize the bits.
52 * @v: an instance of bitfield_t struct.
53 * @N: number of bits to start with, which equates to how many
54 * IDs can be allocated.
56 #define bf_init(v, N) \
59 (v).m = ((N) / WORD_SIZE + 1); \
60 (v).data = (word_t *)XCALLOC(MTYPE_BITFIELD, \
61 ((v).m * sizeof(word_t))); \
65 * allocate and assign an id from bitfield v.
67 #define bf_assign_index(v, id) \
74 * allocate and assign 0th bit in the bitfiled.
76 #define bf_assign_zero_index(v) \
79 bf_assign_index(v, id); \
83 * return an id to bitfield v
85 #define bf_release_index(v, id) \
86 (v).data[bf_index(id)] &= ~(1 << (bf_offset(id)))
88 /* check if an id is in use */
89 #define bf_test_index(v, id) \
90 ((v).data[bf_index(id)] & (1 << (bf_offset(id))))
92 /* check if the bit field has been setup */
93 #define bf_is_inited(v) ((v).data)
95 /* compare two bitmaps of the same length */
96 #define bf_cmp(v1, v2) (memcmp((v1).data, (v2).data, ((v1).m * sizeof(word_t))))
99 * return 0th index back to bitfield
101 #define bf_release_zero_index(v) bf_release_index(v, 0)
103 #define bf_index(b) ((b) / WORD_SIZE)
104 #define bf_offset(b) ((b) % WORD_SIZE)
107 * Set a bit in the array. If it fills up that word and we are
108 * out of words, extend it by one more word.
110 #define bf_set_bit(v, b) \
112 size_t w = bf_index(b); \
113 (v).data[w] |= 1 << (bf_offset(b)); \
114 (v).n += ((v).data[w] == WORD_MAX); \
115 if ((v).n == (v).m) { \
117 (v).data = realloc((v).data, (v).m * sizeof(word_t)); \
121 /* Find a clear bit in v and assign it to b. */
122 #define bf_find_bit(v, b) \
125 unsigned int w, sh; \
126 for (w = 0; w <= (v).n; w++) { \
127 if ((word = (v).data[w]) != WORD_MAX) \
130 (b) = ((word & 0xFFFF) == 0xFFFF) << 4; \
132 sh = ((word & 0xFF) == 0xFF) << 3; \
135 sh = ((word & 0xF) == 0xF) << 2; \
138 sh = ((word & 0x3) == 0x3) << 1; \
141 sh = ((word & 0x1) == 0x1) << 0; \
144 (b) += (w * WORD_SIZE); \
148 * Find a clear bit in v and return it
149 * Start looking in the word containing bit position start_index.
150 * If necessary, wrap around after bit position max_index.
152 static inline unsigned int
153 bf_find_next_clear_bit_wrap(bitfield_t
*v
, word_t start_index
, word_t max_index
)
156 unsigned long i
, offset
, scanbits
, wordcount_max
, index_max
;
158 if (start_index
> max_index
)
161 start_bit
= start_index
& (WORD_SIZE
- 1);
162 wordcount_max
= bf_index(max_index
) + 1;
164 scanbits
= WORD_SIZE
;
165 for (i
= bf_index(start_index
); i
< v
->m
; ++i
) {
166 if (v
->data
[i
] == WORD_MAX
) {
167 /* if the whole word is full move to the next */
171 /* scan one word for clear bits */
172 if ((i
== v
->m
- 1) && (v
->m
>= wordcount_max
))
173 /* max index could be only part of word */
174 scanbits
= (max_index
% WORD_SIZE
) + 1;
175 for (offset
= start_bit
; offset
< scanbits
; ++offset
) {
176 if (!((v
->data
[i
] >> offset
) & 1))
177 return ((i
* WORD_SIZE
) + offset
);
179 /* move to the next word */
183 if (v
->m
< wordcount_max
) {
185 * We can expand bitfield, so no need to wrap.
186 * Return the index of the first bit of the next word.
187 * Assumption is that caller will call bf_set_bit which
188 * will allocate additional space.
191 v
->data
= (word_t
*)realloc(v
->data
, v
->m
* sizeof(word_t
));
192 v
->data
[v
->m
- 1] = 0;
193 return v
->m
* WORD_SIZE
;
197 * start looking for a clear bit at the start of the bitfield and
198 * stop when we reach start_index
200 scanbits
= WORD_SIZE
;
201 index_max
= bf_index(start_index
- 1);
202 for (i
= 0; i
<= index_max
; ++i
) {
204 scanbits
= ((start_index
- 1) % WORD_SIZE
) + 1;
205 for (offset
= start_bit
; offset
< scanbits
; ++offset
) {
206 if (!((v
->data
[i
] >> offset
) & 1))
207 return ((i
* WORD_SIZE
) + offset
);
209 /* move to the next word */
216 static inline unsigned int bf_find_next_set_bit(bitfield_t v
,
220 unsigned long i
, offset
;
222 start_bit
= start_index
& (WORD_SIZE
- 1);
224 for (i
= bf_index(start_index
); i
< v
.m
; ++i
) {
225 if (v
.data
[i
] == 0) {
226 /* if the whole word is empty move to the next */
230 /* scan one word for set bits */
231 for (offset
= start_bit
; offset
< WORD_SIZE
; ++offset
) {
232 if ((v
.data
[i
] >> offset
) & 1)
233 return ((i
* WORD_SIZE
) + offset
);
235 /* move to the next word */
241 /* iterate through all the set bits */
242 #define bf_for_each_set_bit(v, b, max) \
243 for ((b) = bf_find_next_set_bit((v), 0); \
245 (b) = bf_find_next_set_bit((v), (b) + 1))
248 * Free the allocated memory for data
249 * @v: an instance of bitfield_t struct.
253 XFREE(MTYPE_BITFIELD, (v).data); \
257 static inline bitfield_t
bf_copy(bitfield_t src
)
261 assert(bf_is_inited(src
));
262 bf_init(dst
, WORD_SIZE
* (src
.m
- 1));
263 for (size_t i
= 0; i
< src
.m
; i
++)
264 dst
.data
[i
] = src
.data
[i
];