Line data Source code
1 : // SPDX-License-Identifier: GPL-2.0-or-later
2 : /* Bitfields
3 : * Copyright (C) 2016 Cumulus Networks, Inc.
4 : */
5 : /**
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.
11 : *
12 : * An example:
13 : * #include "bitfield.h"
14 : *
15 : * bitfield_t bitfield;
16 : *
17 : * bf_init(bitfield, 32);
18 : * ...
19 : * bf_assign_index(bitfield, id1);
20 : * bf_assign_index(bitfield, id2);
21 : * ...
22 : * bf_release_index(bitfield, id1);
23 : */
24 :
25 : #ifndef _BITFIELD_H
26 : #define _BITFIELD_H
27 :
28 : #include <stdio.h>
29 : #include <string.h>
30 : #include <stdlib.h>
31 :
32 : #ifdef __cplusplus
33 : extern "C" {
34 : #endif
35 :
36 : typedef unsigned int word_t;
37 : #define WORD_MAX 0xFFFFFFFF
38 : #define WORD_SIZE (sizeof(word_t) * 8)
39 :
40 : /**
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'
45 : */
46 : typedef struct {word_t *data; size_t n, m; } bitfield_t;
47 :
48 : DECLARE_MTYPE(BITFIELD);
49 :
50 : /**
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.
55 : */
56 : #define bf_init(v, N) \
57 : do { \
58 : (v).n = 0; \
59 : (v).m = ((N) / WORD_SIZE + 1); \
60 : (v).data = (word_t *)XCALLOC(MTYPE_BITFIELD, \
61 : ((v).m * sizeof(word_t))); \
62 : } while (0)
63 :
64 : /**
65 : * allocate and assign an id from bitfield v.
66 : */
67 : #define bf_assign_index(v, id) \
68 : do { \
69 : bf_find_bit(v, id); \
70 : bf_set_bit(v, id); \
71 : } while (0)
72 :
73 : /*
74 : * allocate and assign 0th bit in the bitfiled.
75 : */
76 : #define bf_assign_zero_index(v) \
77 : do { \
78 : int id = 0; \
79 : bf_assign_index(v, id); \
80 : } while (0)
81 :
82 : /*
83 : * return an id to bitfield v
84 : */
85 : #define bf_release_index(v, id) \
86 : (v).data[bf_index(id)] &= ~(1 << (bf_offset(id)))
87 :
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))))
91 :
92 : /* check if the bit field has been setup */
93 : #define bf_is_inited(v) ((v).data)
94 :
95 : /* compare two bitmaps of the same length */
96 : #define bf_cmp(v1, v2) (memcmp((v1).data, (v2).data, ((v1).m * sizeof(word_t))))
97 :
98 : /*
99 : * return 0th index back to bitfield
100 : */
101 : #define bf_release_zero_index(v) bf_release_index(v, 0)
102 :
103 : #define bf_index(b) ((b) / WORD_SIZE)
104 : #define bf_offset(b) ((b) % WORD_SIZE)
105 :
106 : /**
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.
109 : */
110 : #define bf_set_bit(v, b) \
111 : do { \
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) { \
116 : (v).m = (v).m + 1; \
117 : (v).data = XREALLOC(MTYPE_BITFIELD, (v).data, \
118 : (v).m * sizeof(word_t)); \
119 : } \
120 : } while (0)
121 :
122 : /* Find a clear bit in v and assign it to b. */
123 : #define bf_find_bit(v, b) \
124 : do { \
125 : word_t word = 0; \
126 : unsigned int w, sh; \
127 : for (w = 0; w <= (v).n; w++) { \
128 : if ((word = (v).data[w]) != WORD_MAX) \
129 : break; \
130 : } \
131 : (b) = ((word & 0xFFFF) == 0xFFFF) << 4; \
132 : word >>= (b); \
133 : sh = ((word & 0xFF) == 0xFF) << 3; \
134 : word >>= sh; \
135 : (b) |= sh; \
136 : sh = ((word & 0xF) == 0xF) << 2; \
137 : word >>= sh; \
138 : (b) |= sh; \
139 : sh = ((word & 0x3) == 0x3) << 1; \
140 : word >>= sh; \
141 : (b) |= sh; \
142 : sh = ((word & 0x1) == 0x1) << 0; \
143 : word >>= sh; \
144 : (b) |= sh; \
145 : (b) += (w * WORD_SIZE); \
146 : } while (0)
147 :
148 : /*
149 : * Find a clear bit in v and return it
150 : * Start looking in the word containing bit position start_index.
151 : * If necessary, wrap around after bit position max_index.
152 : */
153 : static inline unsigned int
154 0 : bf_find_next_clear_bit_wrap(bitfield_t *v, word_t start_index, word_t max_index)
155 : {
156 0 : int start_bit;
157 0 : unsigned long i, offset, scanbits, wordcount_max, index_max;
158 :
159 0 : if (start_index > max_index)
160 0 : start_index = 0;
161 :
162 0 : start_bit = start_index & (WORD_SIZE - 1);
163 0 : wordcount_max = bf_index(max_index) + 1;
164 :
165 0 : scanbits = WORD_SIZE;
166 0 : for (i = bf_index(start_index); i < v->m; ++i) {
167 0 : if (v->data[i] == WORD_MAX) {
168 : /* if the whole word is full move to the next */
169 0 : start_bit = 0;
170 0 : continue;
171 : }
172 : /* scan one word for clear bits */
173 0 : if ((i == v->m - 1) && (v->m >= wordcount_max))
174 : /* max index could be only part of word */
175 0 : scanbits = (max_index % WORD_SIZE) + 1;
176 0 : for (offset = start_bit; offset < scanbits; ++offset) {
177 0 : if (!((v->data[i] >> offset) & 1))
178 0 : return ((i * WORD_SIZE) + offset);
179 : }
180 : /* move to the next word */
181 : start_bit = 0;
182 : }
183 :
184 0 : if (v->m < wordcount_max) {
185 : /*
186 : * We can expand bitfield, so no need to wrap.
187 : * Return the index of the first bit of the next word.
188 : * Assumption is that caller will call bf_set_bit which
189 : * will allocate additional space.
190 : */
191 0 : v->m += 1;
192 0 : v->data = (word_t *)XREALLOC(MTYPE_BITFIELD, v->data,
193 : v->m * sizeof(word_t));
194 0 : v->data[v->m - 1] = 0;
195 0 : return v->m * WORD_SIZE;
196 : }
197 :
198 : /*
199 : * start looking for a clear bit at the start of the bitfield and
200 : * stop when we reach start_index
201 : */
202 0 : scanbits = WORD_SIZE;
203 0 : index_max = bf_index(start_index - 1);
204 0 : for (i = 0; i <= index_max; ++i) {
205 0 : if (i == index_max)
206 0 : scanbits = ((start_index - 1) % WORD_SIZE) + 1;
207 0 : for (offset = start_bit; offset < scanbits; ++offset) {
208 0 : if (!((v->data[i] >> offset) & 1))
209 0 : return ((i * WORD_SIZE) + offset);
210 : }
211 : /* move to the next word */
212 0 : start_bit = 0;
213 : }
214 :
215 : return WORD_MAX;
216 : }
217 :
218 0 : static inline unsigned int bf_find_next_set_bit(bitfield_t v,
219 : word_t start_index)
220 : {
221 0 : int start_bit;
222 0 : unsigned long i, offset;
223 :
224 0 : start_bit = start_index & (WORD_SIZE - 1);
225 :
226 0 : for (i = bf_index(start_index); i < v.m; ++i) {
227 0 : if (v.data[i] == 0) {
228 : /* if the whole word is empty move to the next */
229 0 : start_bit = 0;
230 0 : continue;
231 : }
232 : /* scan one word for set bits */
233 0 : for (offset = start_bit; offset < WORD_SIZE; ++offset) {
234 0 : if ((v.data[i] >> offset) & 1)
235 0 : return ((i * WORD_SIZE) + offset);
236 : }
237 : /* move to the next word */
238 : start_bit = 0;
239 : }
240 : return WORD_MAX;
241 : }
242 :
243 : /* iterate through all the set bits */
244 : #define bf_for_each_set_bit(v, b, max) \
245 : for ((b) = bf_find_next_set_bit((v), 0); \
246 : (b) < max; \
247 : (b) = bf_find_next_set_bit((v), (b) + 1))
248 :
249 : /*
250 : * Free the allocated memory for data
251 : * @v: an instance of bitfield_t struct.
252 : */
253 : #define bf_free(v) \
254 : do { \
255 : XFREE(MTYPE_BITFIELD, (v).data); \
256 : (v).data = NULL; \
257 : } while (0)
258 :
259 0 : static inline bitfield_t bf_copy(bitfield_t src)
260 : {
261 0 : bitfield_t dst;
262 :
263 0 : assert(bf_is_inited(src));
264 0 : bf_init(dst, WORD_SIZE * (src.m - 1));
265 0 : for (size_t i = 0; i < src.m; i++)
266 0 : dst.data[i] = src.data[i];
267 0 : dst.n = src.n;
268 0 : return dst;
269 : }
270 :
271 :
272 : #ifdef __cplusplus
273 : }
274 : #endif
275 :
276 : #endif
|
