Line data Source code
1 : /* Bitfields
2 : * Copyright (C) 2016 Cumulus Networks, Inc.
3 : *
4 : * This file is part of Quagga.
5 : *
6 : * Quagga is free software; you can redistribute it and/or modify it
7 : * under the terms of the GNU General Public License as published by the
8 : * Free Software Foundation; either version 2, or (at your option) any
9 : * later version.
10 : *
11 : * Quagga is distributed in the hope that it will be useful, but
12 : * WITHOUT ANY WARRANTY; without even the implied warranty of
13 : * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
14 : * General Public License for more details.
15 : *
16 : * You should have received a copy of the GNU General Public License along
17 : * with this program; see the file COPYING; if not, write to the Free Software
18 : * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
19 : */
20 : /**
21 : * A simple bit array implementation to allocate and free IDs. An example
22 : * of its usage is in allocating link state IDs for OSPFv3 as OSPFv3 has
23 : * removed all address semantics from LS ID. Another usage can be in
24 : * allocating IDs for BGP neighbors (and dynamic update groups) for
25 : * efficient storage of adj-rib-out.
26 : *
27 : * An example:
28 : * #include "bitfield.h"
29 : *
30 : * bitfield_t bitfield;
31 : *
32 : * bf_init(bitfield, 32);
33 : * ...
34 : * bf_assign_index(bitfield, id1);
35 : * bf_assign_index(bitfield, id2);
36 : * ...
37 : * bf_release_index(bitfield, id1);
38 : */
39 :
40 : #ifndef _BITFIELD_H
41 : #define _BITFIELD_H
42 :
43 : #include <stdio.h>
44 : #include <string.h>
45 : #include <stdlib.h>
46 :
47 : #ifdef __cplusplus
48 : extern "C" {
49 : #endif
50 :
51 : typedef unsigned int word_t;
52 : #define WORD_MAX 0xFFFFFFFF
53 : #define WORD_SIZE (sizeof(word_t) * 8)
54 :
55 : /**
56 : * The bitfield structure.
57 : * @data: the bits to manage.
58 : * @n: The current word number that is being used.
59 : * @m: total number of words in 'data'
60 : */
61 : typedef struct {word_t *data; size_t n, m; } bitfield_t;
62 :
63 : DECLARE_MTYPE(BITFIELD);
64 :
65 : /**
66 : * Initialize the bits.
67 : * @v: an instance of bitfield_t struct.
68 : * @N: number of bits to start with, which equates to how many
69 : * IDs can be allocated.
70 : */
71 : #define bf_init(v, N) \
72 : do { \
73 : (v).n = 0; \
74 : (v).m = ((N) / WORD_SIZE + 1); \
75 : (v).data = XCALLOC(MTYPE_BITFIELD, ((v).m * sizeof(word_t))); \
76 : } while (0)
77 :
78 : /**
79 : * allocate and assign an id from bitfield v.
80 : */
81 : #define bf_assign_index(v, id) \
82 : do { \
83 : bf_find_bit(v, id); \
84 : bf_set_bit(v, id); \
85 : } while (0)
86 :
87 : /*
88 : * allocate and assign 0th bit in the bitfiled.
89 : */
90 : #define bf_assign_zero_index(v) \
91 : do { \
92 : int id = 0; \
93 : bf_assign_index(v, id); \
94 : } while (0)
95 :
96 : /*
97 : * return an id to bitfield v
98 : */
99 : #define bf_release_index(v, id) \
100 : (v).data[bf_index(id)] &= ~(1 << (bf_offset(id)))
101 :
102 : /* check if an id is in use */
103 : #define bf_test_index(v, id) \
104 : ((v).data[bf_index(id)] & (1 << (bf_offset(id))))
105 :
106 : /* check if the bit field has been setup */
107 : #define bf_is_inited(v) ((v).data)
108 :
109 : /* compare two bitmaps of the same length */
110 : #define bf_cmp(v1, v2) (memcmp((v1).data, (v2).data, ((v1).m * sizeof(word_t))))
111 :
112 : /*
113 : * return 0th index back to bitfield
114 : */
115 : #define bf_release_zero_index(v) bf_release_index(v, 0)
116 :
117 : #define bf_index(b) ((b) / WORD_SIZE)
118 : #define bf_offset(b) ((b) % WORD_SIZE)
119 :
120 : /**
121 : * Set a bit in the array. If it fills up that word and we are
122 : * out of words, extend it by one more word.
123 : */
124 : #define bf_set_bit(v, b) \
125 : do { \
126 : size_t w = bf_index(b); \
127 : (v).data[w] |= 1 << (bf_offset(b)); \
128 : (v).n += ((v).data[w] == WORD_MAX); \
129 : if ((v).n == (v).m) { \
130 : (v).m = (v).m + 1; \
131 : (v).data = realloc((v).data, (v).m * sizeof(word_t)); \
132 : } \
133 : } while (0)
134 :
135 : /* Find a clear bit in v and assign it to b. */
136 : #define bf_find_bit(v, b) \
137 : do { \
138 : word_t word = 0; \
139 : unsigned int w, sh; \
140 : for (w = 0; w <= (v).n; w++) { \
141 : if ((word = (v).data[w]) != WORD_MAX) \
142 : break; \
143 : } \
144 : (b) = ((word & 0xFFFF) == 0xFFFF) << 4; \
145 : word >>= (b); \
146 : sh = ((word & 0xFF) == 0xFF) << 3; \
147 : word >>= sh; \
148 : (b) |= sh; \
149 : sh = ((word & 0xF) == 0xF) << 2; \
150 : word >>= sh; \
151 : (b) |= sh; \
152 : sh = ((word & 0x3) == 0x3) << 1; \
153 : word >>= sh; \
154 : (b) |= sh; \
155 : sh = ((word & 0x1) == 0x1) << 0; \
156 : word >>= sh; \
157 : (b) |= sh; \
158 : (b) += (w * WORD_SIZE); \
159 : } while (0)
160 :
161 : /*
162 : * Find a clear bit in v and return it
163 : * Start looking in the word containing bit position start_index.
164 : * If necessary, wrap around after bit position max_index.
165 : */
166 : static inline unsigned int
167 0 : bf_find_next_clear_bit_wrap(bitfield_t *v, word_t start_index, word_t max_index)
168 : {
169 0 : int start_bit;
170 0 : unsigned long i, offset, scanbits, wordcount_max, index_max;
171 :
172 0 : if (start_index > max_index)
173 0 : start_index = 0;
174 :
175 0 : start_bit = start_index & (WORD_SIZE - 1);
176 0 : wordcount_max = bf_index(max_index) + 1;
177 :
178 0 : scanbits = WORD_SIZE;
179 0 : for (i = bf_index(start_index); i < v->m; ++i) {
180 0 : if (v->data[i] == WORD_MAX) {
181 : /* if the whole word is full move to the next */
182 0 : start_bit = 0;
183 0 : continue;
184 : }
185 : /* scan one word for clear bits */
186 0 : if ((i == v->m - 1) && (v->m >= wordcount_max))
187 : /* max index could be only part of word */
188 0 : scanbits = (max_index % WORD_SIZE) + 1;
189 0 : for (offset = start_bit; offset < scanbits; ++offset) {
190 0 : if (!((v->data[i] >> offset) & 1))
191 0 : return ((i * WORD_SIZE) + offset);
192 : }
193 : /* move to the next word */
194 : start_bit = 0;
195 : }
196 :
197 0 : if (v->m < wordcount_max) {
198 : /*
199 : * We can expand bitfield, so no need to wrap.
200 : * Return the index of the first bit of the next word.
201 : * Assumption is that caller will call bf_set_bit which
202 : * will allocate additional space.
203 : */
204 0 : v->m += 1;
205 0 : v->data = (word_t *)realloc(v->data, v->m * sizeof(word_t));
206 0 : v->data[v->m - 1] = 0;
207 0 : return v->m * WORD_SIZE;
208 : }
209 :
210 : /*
211 : * start looking for a clear bit at the start of the bitfield and
212 : * stop when we reach start_index
213 : */
214 0 : scanbits = WORD_SIZE;
215 0 : index_max = bf_index(start_index - 1);
216 0 : for (i = 0; i <= index_max; ++i) {
217 0 : if (i == index_max)
218 0 : scanbits = ((start_index - 1) % WORD_SIZE) + 1;
219 0 : for (offset = start_bit; offset < scanbits; ++offset) {
220 0 : if (!((v->data[i] >> offset) & 1))
221 0 : return ((i * WORD_SIZE) + offset);
222 : }
223 : /* move to the next word */
224 0 : start_bit = 0;
225 : }
226 :
227 : return WORD_MAX;
228 : }
229 :
230 0 : static inline unsigned int bf_find_next_set_bit(bitfield_t v,
231 : word_t start_index)
232 : {
233 0 : int start_bit;
234 0 : unsigned long i, offset;
235 :
236 0 : start_bit = start_index & (WORD_SIZE - 1);
237 :
238 0 : for (i = bf_index(start_index); i < v.m; ++i) {
239 0 : if (v.data[i] == 0) {
240 : /* if the whole word is empty move to the next */
241 0 : start_bit = 0;
242 0 : continue;
243 : }
244 : /* scan one word for set bits */
245 0 : for (offset = start_bit; offset < WORD_SIZE; ++offset) {
246 0 : if ((v.data[i] >> offset) & 1)
247 0 : return ((i * WORD_SIZE) + offset);
248 : }
249 : /* move to the next word */
250 : start_bit = 0;
251 : }
252 : return WORD_MAX;
253 : }
254 :
255 : /* iterate through all the set bits */
256 : #define bf_for_each_set_bit(v, b, max) \
257 : for ((b) = bf_find_next_set_bit((v), 0); \
258 : (b) < max; \
259 : (b) = bf_find_next_set_bit((v), (b) + 1))
260 :
261 : /*
262 : * Free the allocated memory for data
263 : * @v: an instance of bitfield_t struct.
264 : */
265 : #define bf_free(v) \
266 : do { \
267 : XFREE(MTYPE_BITFIELD, (v).data); \
268 : (v).data = NULL; \
269 : } while (0)
270 :
271 : #ifdef __cplusplus
272 : }
273 : #endif
274 :
275 : #endif
|
