FreeBSD/Linux Kernel Cross Reference
sys/sys/bitstring.h
1 /*-
2 * SPDX-License-Identifier: BSD-3-Clause
3 *
4 * Copyright (c) 1989, 1993
5 * The Regents of the University of California. All rights reserved.
6 *
7 * This code is derived from software contributed to Berkeley by
8 * Paul Vixie.
9 *
10 * Redistribution and use in source and binary forms, with or without
11 * modification, are permitted provided that the following conditions
12 * are met:
13 * 1. Redistributions of source code must retain the above copyright
14 * notice, this list of conditions and the following disclaimer.
15 * 2. Redistributions in binary form must reproduce the above copyright
16 * notice, this list of conditions and the following disclaimer in the
17 * documentation and/or other materials provided with the distribution.
18 * 3. Neither the name of the University nor the names of its contributors
19 * may be used to endorse or promote products derived from this software
20 * without specific prior written permission.
21 *
22 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
23 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
24 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
25 * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
26 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
27 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
28 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
29 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
30 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
31 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
32 * SUCH DAMAGE.
33 *
34 * Copyright (c) 2014 Spectra Logic Corporation
35 * All rights reserved.
36 *
37 * Redistribution and use in source and binary forms, with or without
38 * modification, are permitted provided that the following conditions
39 * are met:
40 * 1. Redistributions of source code must retain the above copyright
41 * notice, this list of conditions, and the following disclaimer,
42 * without modification.
43 * 2. Redistributions in binary form must reproduce at minimum a disclaimer
44 * substantially similar to the "NO WARRANTY" disclaimer below
45 * ("Disclaimer") and any redistribution must be conditioned upon
46 * including a substantially similar Disclaimer requirement for further
47 * binary redistribution.
48 *
49 * NO WARRANTY
50 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
51 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
52 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTIBILITY AND FITNESS FOR
53 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
54 * HOLDERS OR CONTRIBUTORS BE LIABLE FOR SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
55 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
56 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
57 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
58 * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING
59 * IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
60 * POSSIBILITY OF SUCH DAMAGES.
61 *
62 * $FreeBSD$
63 */
64 #ifndef _SYS_BITSTRING_H_
65 #define _SYS_BITSTRING_H_
66
67 #ifdef _KERNEL
68 #include <sys/libkern.h>
69 #include <sys/malloc.h>
70 #endif
71
72 #include <sys/types.h>
73
74 typedef unsigned long bitstr_t;
75
76 /*---------------------- Private Implementation Details ----------------------*/
77 #define _BITSTR_MASK (~0UL)
78 #define _BITSTR_BITS (sizeof(bitstr_t) * 8)
79
80 #ifdef roundup2
81 #define _bit_roundup2 roundup2
82 #else
83 #define _bit_roundup2(x, y) (((x)+((y)-1))&(~((y)-1))) /* if y is powers of two */
84 #endif
85
86 /* bitstr_t in bit string containing the bit. */
87 static inline int
88 _bit_idx(int _bit)
89 {
90 return (_bit / _BITSTR_BITS);
91 }
92
93 /* bit number within bitstr_t at _bit_idx(_bit). */
94 static inline int
95 _bit_offset(int _bit)
96 {
97 return (_bit % _BITSTR_BITS);
98 }
99
100 /* Mask for the bit within its long. */
101 static inline bitstr_t
102 _bit_mask(int _bit)
103 {
104 return (1UL << _bit_offset(_bit));
105 }
106
107 static inline bitstr_t
108 _bit_make_mask(int _start, int _stop)
109 {
110 return ((_BITSTR_MASK << _bit_offset(_start)) &
111 (_BITSTR_MASK >> (_BITSTR_BITS - _bit_offset(_stop) - 1)));
112 }
113
114 /*----------------------------- Public Interface -----------------------------*/
115 /* Number of bytes allocated for a bit string of nbits bits */
116 #define bitstr_size(_nbits) (_bit_roundup2(_nbits, _BITSTR_BITS) / 8)
117
118 /* Allocate a bit string initialized with no bits set. */
119 #ifdef _KERNEL
120 static inline bitstr_t *
121 bit_alloc(int _nbits, struct malloc_type *type, int flags)
122 {
123 return ((bitstr_t *)malloc(bitstr_size(_nbits), type, flags | M_ZERO));
124 }
125 #else
126 static inline bitstr_t *
127 bit_alloc(int _nbits)
128 {
129 return ((bitstr_t *)calloc(bitstr_size(_nbits), 1));
130 }
131 #endif
132
133 /* Allocate a bit string on the stack */
134 #define bit_decl(name, nbits) \
135 ((name)[bitstr_size(nbits) / sizeof(bitstr_t)])
136
137 /* Is bit N of bit string set? */
138 static inline int
139 bit_test(const bitstr_t *_bitstr, int _bit)
140 {
141 return ((_bitstr[_bit_idx(_bit)] & _bit_mask(_bit)) != 0);
142 }
143
144 /* Set bit N of bit string. */
145 static inline void
146 bit_set(bitstr_t *_bitstr, int _bit)
147 {
148 _bitstr[_bit_idx(_bit)] |= _bit_mask(_bit);
149 }
150
151 /* clear bit N of bit string name */
152 static inline void
153 bit_clear(bitstr_t *_bitstr, int _bit)
154 {
155 _bitstr[_bit_idx(_bit)] &= ~_bit_mask(_bit);
156 }
157
158 /* Are bits in [start ... stop] in bit string all 0 or all 1? */
159 static inline int
160 bit_ntest(const bitstr_t *_bitstr, int _start, int _stop, int _match)
161 {
162 const bitstr_t *_stopbitstr;
163 bitstr_t _mask;
164
165 _mask = (_match == 0) ? 0 : _BITSTR_MASK;
166 _stopbitstr = _bitstr + _bit_idx(_stop);
167 _bitstr += _bit_idx(_start);
168
169 if (_bitstr == _stopbitstr)
170 return (0 == ((*_bitstr ^ _mask) &
171 _bit_make_mask(_start, _stop)));
172 if (_bit_offset(_start) != 0 &&
173 0 != ((*_bitstr++ ^ _mask) &
174 _bit_make_mask(_start, _BITSTR_BITS - 1)))
175 return (0);
176 if (_bit_offset(_stop) == _BITSTR_BITS - 1)
177 ++_stopbitstr;
178 while (_bitstr < _stopbitstr) {
179 if (*_bitstr++ != _mask)
180 return (0);
181 }
182 return (_bit_offset(_stop) == _BITSTR_BITS - 1 ||
183 0 == ((*_stopbitstr ^ _mask) & _bit_make_mask(0, _stop)));
184 }
185
186 /* Set bits start ... stop inclusive in bit string. */
187 static inline void
188 bit_nset(bitstr_t *_bitstr, int _start, int _stop)
189 {
190 bitstr_t *_stopbitstr;
191
192 _stopbitstr = _bitstr + _bit_idx(_stop);
193 _bitstr += _bit_idx(_start);
194
195 if (_bitstr == _stopbitstr) {
196 *_bitstr |= _bit_make_mask(_start, _stop);
197 } else {
198 if (_bit_offset(_start) != 0)
199 *_bitstr++ |= _bit_make_mask(_start, _BITSTR_BITS - 1);
200 if (_bit_offset(_stop) == _BITSTR_BITS - 1)
201 ++_stopbitstr;
202 while (_bitstr < _stopbitstr)
203 *_bitstr++ = _BITSTR_MASK;
204 if (_bit_offset(_stop) != _BITSTR_BITS - 1)
205 *_stopbitstr |= _bit_make_mask(0, _stop);
206 }
207 }
208
209 /* Clear bits start ... stop inclusive in bit string. */
210 static inline void
211 bit_nclear(bitstr_t *_bitstr, int _start, int _stop)
212 {
213 bitstr_t *_stopbitstr;
214
215 _stopbitstr = _bitstr + _bit_idx(_stop);
216 _bitstr += _bit_idx(_start);
217
218 if (_bitstr == _stopbitstr) {
219 *_bitstr &= ~_bit_make_mask(_start, _stop);
220 } else {
221 if (_bit_offset(_start) != 0)
222 *_bitstr++ &= ~_bit_make_mask(_start, _BITSTR_BITS - 1);
223 if (_bit_offset(_stop) == _BITSTR_BITS - 1)
224 ++_stopbitstr;
225 while (_bitstr < _stopbitstr)
226 *_bitstr++ = 0;
227 if (_bit_offset(_stop) != _BITSTR_BITS - 1)
228 *_stopbitstr &= ~_bit_make_mask(0, _stop);
229 }
230 }
231
232 /* Find the first '_match'-bit in bit string at or after bit start. */
233 static inline void
234 bit_ff_at(bitstr_t *_bitstr, int _start, int _nbits, int _match,
235 int *_result)
236 {
237 bitstr_t *_curbitstr;
238 bitstr_t *_stopbitstr;
239 bitstr_t _mask;
240 bitstr_t _test;
241 int _value;
242
243 if (_start >= _nbits || _nbits <= 0) {
244 *_result = -1;
245 return;
246 }
247
248 _curbitstr = _bitstr + _bit_idx(_start);
249 _stopbitstr = _bitstr + _bit_idx(_nbits - 1);
250 _mask = _match ? 0 : _BITSTR_MASK;
251
252 _test = _mask ^ *_curbitstr;
253 if (_bit_offset(_start) != 0)
254 _test &= _bit_make_mask(_start, _BITSTR_BITS - 1);
255 while (_test == 0 && _curbitstr < _stopbitstr)
256 _test = _mask ^ *(++_curbitstr);
257
258 _value = ((_curbitstr - _bitstr) * _BITSTR_BITS) + ffsl(_test) - 1;
259 if (_test == 0 ||
260 (_bit_offset(_nbits) != 0 && _value >= _nbits))
261 _value = -1;
262 *_result = _value;
263 }
264
265 /* Find the first bit set in bit string at or after bit start. */
266 static inline void
267 bit_ffs_at(bitstr_t *_bitstr, int _start, int _nbits, int *_result)
268 {
269 bit_ff_at(_bitstr, _start, _nbits, 1, _result);
270 }
271
272 /* Find the first bit clear in bit string at or after bit start. */
273 static inline void
274 bit_ffc_at(bitstr_t *_bitstr, int _start, int _nbits, int *_result)
275 {
276 bit_ff_at(_bitstr, _start, _nbits, 0, _result);
277 }
278
279 /* Find the first bit set in bit string. */
280 static inline void
281 bit_ffs(bitstr_t *_bitstr, int _nbits, int *_result)
282 {
283 bit_ffs_at(_bitstr, /*start*/0, _nbits, _result);
284 }
285
286 /* Find the first bit clear in bit string. */
287 static inline void
288 bit_ffc(bitstr_t *_bitstr, int _nbits, int *_result)
289 {
290 bit_ffc_at(_bitstr, /*start*/0, _nbits, _result);
291 }
292
293 /* Find contiguous sequence of at least size '_match'-bits at or after start */
294 static inline void
295 bit_ff_area_at(bitstr_t *_bitstr, int _start, int _nbits, int _size,
296 int _match, int *_result)
297 {
298 bitstr_t *_curbitstr, _mask, _test;
299 int _value, _last, _shft, _maxshft;
300
301 if (_start + _size > _nbits || _nbits <= 0) {
302 *_result = -1;
303 return;
304 }
305
306 _mask = _match ? _BITSTR_MASK : 0;
307 _maxshft = _bit_idx(_size - 1) == 0 ? _size : (int)_BITSTR_BITS;
308 _value = _start;
309 _curbitstr = _bitstr + _bit_idx(_start);
310 _test = ~(_BITSTR_MASK << _bit_offset(_start));
311 for (_last = _size - 1, _test |= _mask ^ *_curbitstr;
312 !(_bit_idx(_last) == 0 &&
313 (_test & _bit_make_mask(0, _last)) == 0);
314 _last -= _BITSTR_BITS, _test = _mask ^ *++_curbitstr) {
315 if (_test == 0)
316 continue;
317 /* Shrink-left every 0-area in _test by maxshft-1 bits. */
318 for (_shft = _maxshft; _shft > 1 && (_test & (_test + 1)) != 0;
319 _shft = (_shft + 1) / 2)
320 _test |= _test >> _shft / 2;
321 /* Find the start of the first 0-area in _test. */
322 _last = ffsl(~(_test >> 1));
323 _value = (_curbitstr - _bitstr) * _BITSTR_BITS + _last;
324 /* If there's insufficient space left, give up. */
325 if (_value + _size > _nbits) {
326 _value = -1;
327 break;
328 }
329 _last += _size - 1;
330 /* If a solution is contained in _test, success! */
331 if (_bit_idx(_last) == 0)
332 break;
333 /* A solution here needs bits from the next word. */
334 }
335 *_result = _value;
336 }
337
338 /* Find contiguous sequence of at least size set bits at or after start */
339 static inline void
340 bit_ffs_area_at(bitstr_t *_bitstr, int _start, int _nbits, int _size,
341 int *_result)
342 {
343 bit_ff_area_at(_bitstr, _start, _nbits, _size, 1, _result);
344 }
345
346 /* Find contiguous sequence of at least size cleared bits at or after start */
347 static inline void
348 bit_ffc_area_at(bitstr_t *_bitstr, int _start, int _nbits, int _size,
349 int *_result)
350 {
351 bit_ff_area_at(_bitstr, _start, _nbits, _size, 0, _result);
352 }
353
354 /* Find contiguous sequence of at least size set bits in bit string */
355 static inline void
356 bit_ffs_area(bitstr_t *_bitstr, int _nbits, int _size, int *_result)
357 {
358 bit_ffs_area_at(_bitstr, /*start*/0, _nbits, _size, _result);
359 }
360
361 /* Find contiguous sequence of at least size cleared bits in bit string */
362 static inline void
363 bit_ffc_area(bitstr_t *_bitstr, int _nbits, int _size, int *_result)
364 {
365 bit_ffc_area_at(_bitstr, /*start*/0, _nbits, _size, _result);
366 }
367
368 /* Count the number of bits set in a bitstr of size _nbits at or after _start */
369 static inline void
370 bit_count(bitstr_t *_bitstr, int _start, int _nbits, int *_result)
371 {
372 bitstr_t *_curbitstr, mask;
373 int _value = 0, curbitstr_len;
374
375 if (_start >= _nbits)
376 goto out;
377
378 _curbitstr = _bitstr + _bit_idx(_start);
379 _nbits -= _BITSTR_BITS * _bit_idx(_start);
380 _start -= _BITSTR_BITS * _bit_idx(_start);
381
382 if (_start > 0) {
383 curbitstr_len = (int)_BITSTR_BITS < _nbits ?
384 (int)_BITSTR_BITS : _nbits;
385 mask = _bit_make_mask(_start, _bit_offset(curbitstr_len - 1));
386 _value += __bitcountl(*_curbitstr & mask);
387 _curbitstr++;
388 _nbits -= _BITSTR_BITS;
389 }
390 while (_nbits >= (int)_BITSTR_BITS) {
391 _value += __bitcountl(*_curbitstr);
392 _curbitstr++;
393 _nbits -= _BITSTR_BITS;
394 }
395 if (_nbits > 0) {
396 mask = _bit_make_mask(0, _bit_offset(_nbits - 1));
397 _value += __bitcountl(*_curbitstr & mask);
398 }
399
400 out:
401 *_result = _value;
402 }
403
404 /* Traverse all set bits, assigning each location in turn to iter */
405 #define bit_foreach_at(_bitstr, _start, _nbits, _iter) \
406 for (bit_ffs_at((_bitstr), (_start), (_nbits), &(_iter)); \
407 (_iter) != -1; \
408 bit_ffs_at((_bitstr), (_iter) + 1, (_nbits), &(_iter)))
409 #define bit_foreach(_bitstr, _nbits, _iter) \
410 bit_foreach_at(_bitstr, /*start*/0, _nbits, _iter)
411
412 /* Traverse all unset bits, assigning each location in turn to iter */
413 #define bit_foreach_unset_at(_bitstr, _start, _nbits, _iter) \
414 for (bit_ffc_at((_bitstr), (_start), (_nbits), &(_iter)); \
415 (_iter) != -1; \
416 bit_ffc_at((_bitstr), (_iter) + 1, (_nbits), &(_iter)))
417 #define bit_foreach_unset(_bitstr, _nbits, _iter) \
418 bit_foreach_unset_at(_bitstr, /*start*/0, _nbits, _iter)
419
420 #endif /* _SYS_BITSTRING_H_ */
Cache object: 7fb2b49372fe2cef50cd5642193d01cb
|