FreeBSD/Linux Kernel Cross Reference
sys/sys/bitstring.h
1 /*-
2 * Copyright (c) 1989, 1993
3 * The Regents of the University of California. All rights reserved.
4 *
5 * This code is derived from software contributed to Berkeley by
6 * Paul Vixie.
7 *
8 * Redistribution and use in source and binary forms, with or without
9 * modification, are permitted provided that the following conditions
10 * are met:
11 * 1. Redistributions of source code must retain the above copyright
12 * notice, this list of conditions and the following disclaimer.
13 * 2. Redistributions in binary form must reproduce the above copyright
14 * notice, this list of conditions and the following disclaimer in the
15 * documentation and/or other materials provided with the distribution.
16 * 4. Neither the name of the University nor the names of its contributors
17 * may be used to endorse or promote products derived from this software
18 * without specific prior written permission.
19 *
20 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
21 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
22 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
23 * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
24 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
25 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
26 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
27 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
28 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
29 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
30 * SUCH DAMAGE.
31 *
32 * Copyright (c) 2014 Spectra Logic Corporation
33 * All rights reserved.
34 *
35 * Redistribution and use in source and binary forms, with or without
36 * modification, are permitted provided that the following conditions
37 * are met:
38 * 1. Redistributions of source code must retain the above copyright
39 * notice, this list of conditions, and the following disclaimer,
40 * without modification.
41 * 2. Redistributions in binary form must reproduce at minimum a disclaimer
42 * substantially similar to the "NO WARRANTY" disclaimer below
43 * ("Disclaimer") and any redistribution must be conditioned upon
44 * including a substantially similar Disclaimer requirement for further
45 * binary redistribution.
46 *
47 * NO WARRANTY
48 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
49 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
50 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTIBILITY AND FITNESS FOR
51 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
52 * HOLDERS OR CONTRIBUTORS BE LIABLE FOR SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
53 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
54 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
55 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
56 * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING
57 * IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
58 * POSSIBILITY OF SUCH DAMAGES.
59 *
60 * $FreeBSD: releng/11.0/sys/sys/bitstring.h 302180 2016-06-24 21:44:46Z asomers $
61 */
62 #ifndef _SYS_BITSTRING_H_
63 #define _SYS_BITSTRING_H_
64
65 #ifdef _KERNEL
66 #include <sys/libkern.h>
67 #include <sys/malloc.h>
68 #endif
69
70 #include <sys/types.h>
71
72 typedef unsigned long bitstr_t;
73
74 /*---------------------- Private Implementation Details ----------------------*/
75 #define _BITSTR_MASK (~0UL)
76 #define _BITSTR_BITS (sizeof(bitstr_t) * 8)
77
78 #ifdef roundup2
79 #define _bit_roundup2 roundup2
80 #else
81 #define _bit_roundup2(x, y) (((x)+((y)-1))&(~((y)-1))) /* if y is powers of two */
82 #endif
83
84 /* bitstr_t in bit string containing the bit. */
85 static inline int
86 _bit_idx(int _bit)
87 {
88 return (_bit / _BITSTR_BITS);
89 }
90
91 /* bit number within bitstr_t at _bit_idx(_bit). */
92 static inline int
93 _bit_offset(int _bit)
94 {
95 return (_bit % _BITSTR_BITS);
96 }
97
98 /* Mask for the bit within its long. */
99 static inline bitstr_t
100 _bit_mask(int _bit)
101 {
102 return (1UL << _bit_offset(_bit));
103 }
104
105 static inline bitstr_t
106 _bit_make_mask(int _start, int _stop)
107 {
108 return ((_BITSTR_MASK << _bit_offset(_start)) &
109 (_BITSTR_MASK >> (_BITSTR_BITS - _bit_offset(_stop) - 1)));
110 }
111
112 /*----------------------------- Public Interface -----------------------------*/
113 /* Number of bytes allocated for a bit string of nbits bits */
114 #define bitstr_size(_nbits) (_bit_roundup2(_nbits, _BITSTR_BITS) / 8)
115
116 /* Allocate a bit string initialized with no bits set. */
117 #ifdef _KERNEL
118 static inline bitstr_t *
119 bit_alloc(int _nbits, struct malloc_type *type, int flags)
120 {
121 return ((bitstr_t *)malloc(bitstr_size(_nbits), type, flags | M_ZERO));
122 }
123 #else
124 static inline bitstr_t *
125 bit_alloc(int _nbits)
126 {
127 return ((bitstr_t *)calloc(bitstr_size(_nbits), 1));
128 }
129 #endif
130
131 /* Allocate a bit string on the stack */
132 #define bit_decl(name, nbits) \
133 ((name)[bitstr_size(nbits) / sizeof(bitstr_t)])
134
135 /* Is bit N of bit string set? */
136 static inline int
137 bit_test(const bitstr_t *_bitstr, int _bit)
138 {
139 return ((_bitstr[_bit_idx(_bit)] & _bit_mask(_bit)) != 0);
140 }
141
142 /* Set bit N of bit string. */
143 static inline void
144 bit_set(bitstr_t *_bitstr, int _bit)
145 {
146 _bitstr[_bit_idx(_bit)] |= _bit_mask(_bit);
147 }
148
149 /* clear bit N of bit string name */
150 static inline void
151 bit_clear(bitstr_t *_bitstr, int _bit)
152 {
153 _bitstr[_bit_idx(_bit)] &= ~_bit_mask(_bit);
154 }
155
156 /* Set bits start ... stop inclusive in bit string. */
157 static inline void
158 bit_nset(bitstr_t *_bitstr, int _start, int _stop)
159 {
160 bitstr_t *_stopbitstr;
161
162 _stopbitstr = _bitstr + _bit_idx(_stop);
163 _bitstr += _bit_idx(_start);
164
165 if (_bitstr == _stopbitstr) {
166 *_bitstr |= _bit_make_mask(_start, _stop);
167 } else {
168 *_bitstr |= _bit_make_mask(_start, _BITSTR_BITS - 1);
169 while (++_bitstr < _stopbitstr)
170 *_bitstr = _BITSTR_MASK;
171 *_stopbitstr |= _bit_make_mask(0, _stop);
172 }
173 }
174
175 /* Clear bits start ... stop inclusive in bit string. */
176 static inline void
177 bit_nclear(bitstr_t *_bitstr, int _start, int _stop)
178 {
179 bitstr_t *_stopbitstr;
180
181 _stopbitstr = _bitstr + _bit_idx(_stop);
182 _bitstr += _bit_idx(_start);
183
184 if (_bitstr == _stopbitstr) {
185 *_bitstr &= ~_bit_make_mask(_start, _stop);
186 } else {
187 *_bitstr &= ~_bit_make_mask(_start, _BITSTR_BITS - 1);
188 while (++_bitstr < _stopbitstr)
189 *_bitstr = 0;
190 *_stopbitstr &= ~_bit_make_mask(0, _stop);
191 }
192 }
193
194 /* Find the first bit set in bit string at or after bit start. */
195 static inline void
196 bit_ffs_at(bitstr_t *_bitstr, int _start, int _nbits, int *_result)
197 {
198 bitstr_t *_curbitstr;
199 bitstr_t *_stopbitstr;
200 bitstr_t _test;
201 int _value, _offset;
202
203 if (_nbits > 0) {
204 _curbitstr = _bitstr + _bit_idx(_start);
205 _stopbitstr = _bitstr + _bit_idx(_nbits - 1);
206
207 _test = *_curbitstr;
208 if (_bit_offset(_start) != 0)
209 _test &= _bit_make_mask(_start, _BITSTR_BITS - 1);
210 while (_test == 0 && _curbitstr < _stopbitstr)
211 _test = *(++_curbitstr);
212
213 _offset = ffsl(_test);
214 _value = ((_curbitstr - _bitstr) * _BITSTR_BITS) + _offset - 1;
215 if (_offset == 0 || _value >= _nbits)
216 _value = -1;
217 } else {
218 _value = -1;
219 }
220 *_result = _value;
221 }
222
223 /* Find the first bit clear in bit string at or after bit start. */
224 static inline void
225 bit_ffc_at(bitstr_t *_bitstr, int _start, int _nbits, int *_result)
226 {
227 bitstr_t *_curbitstr;
228 bitstr_t *_stopbitstr;
229 bitstr_t _test;
230 int _value, _offset;
231
232 if (_nbits > 0) {
233 _curbitstr = _bitstr + _bit_idx(_start);
234 _stopbitstr = _bitstr + _bit_idx(_nbits - 1);
235
236 _test = *_curbitstr;
237 if (_bit_offset(_start) != 0)
238 _test |= _bit_make_mask(0, _start - 1);
239 while (_test == _BITSTR_MASK && _curbitstr < _stopbitstr)
240 _test = *(++_curbitstr);
241
242 _offset = ffsl(~_test);
243 _value = ((_curbitstr - _bitstr) * _BITSTR_BITS) + _offset - 1;
244 if (_offset == 0 || _value >= _nbits)
245 _value = -1;
246 } else {
247 _value = -1;
248 }
249 *_result = _value;
250 }
251
252 /* Find the first bit set in bit string. */
253 static inline void
254 bit_ffs(bitstr_t *_bitstr, int _nbits, int *_result)
255 {
256 bit_ffs_at(_bitstr, /*start*/0, _nbits, _result);
257 }
258
259 /* Find the first bit clear in bit string. */
260 static inline void
261 bit_ffc(bitstr_t *_bitstr, int _nbits, int *_result)
262 {
263 bit_ffc_at(_bitstr, /*start*/0, _nbits, _result);
264 }
265
266 /* Count the number of bits set in a bitstr of size _nbits at or after _start */
267 static inline void
268 bit_count(bitstr_t *_bitstr, int _start, int _nbits, int *_result)
269 {
270 bitstr_t *_curbitstr, mask;
271 int _value = 0, curbitstr_len;
272
273 if (_start >= _nbits)
274 goto out;
275
276 _curbitstr = _bitstr + _bit_idx(_start);
277 _nbits -= _BITSTR_BITS * _bit_idx(_start);
278 _start -= _BITSTR_BITS * _bit_idx(_start);
279
280 if (_start > 0) {
281 curbitstr_len = (int)_BITSTR_BITS < _nbits ?
282 (int)_BITSTR_BITS : _nbits;
283 mask = _bit_make_mask(_start, _bit_offset(curbitstr_len - 1));
284 _value += __bitcountl(*_curbitstr & mask);
285 _curbitstr++;
286 _nbits -= _BITSTR_BITS;
287 }
288 while (_nbits >= (int)_BITSTR_BITS) {
289 _value += __bitcountl(*_curbitstr);
290 _curbitstr++;
291 _nbits -= _BITSTR_BITS;
292 }
293 if (_nbits > 0) {
294 mask = _bit_make_mask(0, _bit_offset(_nbits - 1));
295 _value += __bitcountl(*_curbitstr & mask);
296 }
297
298 out:
299 *_result = _value;
300 }
301
302 #endif /* _SYS_BITSTRING_H_ */
Cache object: 9b113d2336851a7916465d37c0165897
|