FreeBSD/Linux Kernel Cross Reference
sys/sys/bitset.h
1 /*-
2 * SPDX-License-Identifier: BSD-2-Clause-FreeBSD
3 *
4 * Copyright (c) 2008, Jeffrey Roberson <jeff@freebsd.org>
5 * All rights reserved.
6 *
7 * Copyright (c) 2008 Nokia Corporation
8 * All rights reserved.
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 unmodified, this list of conditions, and the following
15 * disclaimer.
16 * 2. Redistributions in binary form must reproduce the above copyright
17 * notice, this list of conditions and the following disclaimer in the
18 * documentation and/or other materials provided with the distribution.
19 *
20 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
21 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
22 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
23 * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
24 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
25 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
26 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
27 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
28 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
29 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
30 *
31 * $FreeBSD$
32 */
33
34 #ifndef _SYS_BITSET_H_
35 #define _SYS_BITSET_H_
36
37 #define __bitset_mask(_s, n) \
38 (1UL << ((__bitset_words((_s)) == 1) ? \
39 (__size_t)(n) : ((n) % _BITSET_BITS)))
40
41 #define __bitset_word(_s, n) \
42 ((__bitset_words((_s)) == 1) ? 0 : ((n) / _BITSET_BITS))
43
44 #define BIT_CLR(_s, n, p) \
45 ((p)->__bits[__bitset_word(_s, n)] &= ~__bitset_mask((_s), (n)))
46
47 #define BIT_COPY(_s, f, t) (void)(*(t) = *(f))
48
49 #define BIT_ISSET(_s, n, p) \
50 ((((p)->__bits[__bitset_word(_s, n)] & __bitset_mask((_s), (n))) != 0))
51
52 #define BIT_SET(_s, n, p) \
53 ((p)->__bits[__bitset_word(_s, n)] |= __bitset_mask((_s), (n)))
54
55 #define BIT_ZERO(_s, p) do { \
56 __size_t __i; \
57 for (__i = 0; __i < __bitset_words((_s)); __i++) \
58 (p)->__bits[__i] = 0L; \
59 } while (0)
60
61 #define BIT_FILL(_s, p) do { \
62 __size_t __i; \
63 for (__i = 0; __i < __bitset_words((_s)); __i++) \
64 (p)->__bits[__i] = -1L; \
65 } while (0)
66
67 #define BIT_SETOF(_s, n, p) do { \
68 BIT_ZERO(_s, p); \
69 (p)->__bits[__bitset_word(_s, n)] = __bitset_mask((_s), (n)); \
70 } while (0)
71
72 /* Is p empty. */
73 #define BIT_EMPTY(_s, p) __extension__ ({ \
74 __size_t __i; \
75 for (__i = 0; __i < __bitset_words((_s)); __i++) \
76 if ((p)->__bits[__i]) \
77 break; \
78 __i == __bitset_words((_s)); \
79 })
80
81 /* Is p full set. */
82 #define BIT_ISFULLSET(_s, p) __extension__ ({ \
83 __size_t __i; \
84 for (__i = 0; __i < __bitset_words((_s)); __i++) \
85 if ((p)->__bits[__i] != (long)-1) \
86 break; \
87 __i == __bitset_words((_s)); \
88 })
89
90 /* Is c a subset of p. */
91 #define BIT_SUBSET(_s, p, c) __extension__ ({ \
92 __size_t __i; \
93 for (__i = 0; __i < __bitset_words((_s)); __i++) \
94 if (((c)->__bits[__i] & \
95 (p)->__bits[__i]) != \
96 (c)->__bits[__i]) \
97 break; \
98 __i == __bitset_words((_s)); \
99 })
100
101 /* Are there any common bits between b & c? */
102 #define BIT_OVERLAP(_s, p, c) __extension__ ({ \
103 __size_t __i; \
104 for (__i = 0; __i < __bitset_words((_s)); __i++) \
105 if (((c)->__bits[__i] & \
106 (p)->__bits[__i]) != 0) \
107 break; \
108 __i != __bitset_words((_s)); \
109 })
110
111 /* Compare two sets, returns 0 if equal 1 otherwise. */
112 #define BIT_CMP(_s, p, c) __extension__ ({ \
113 __size_t __i; \
114 for (__i = 0; __i < __bitset_words((_s)); __i++) \
115 if (((c)->__bits[__i] != \
116 (p)->__bits[__i])) \
117 break; \
118 __i != __bitset_words((_s)); \
119 })
120
121 #define BIT_OR(_s, d, s) do { \
122 __size_t __i; \
123 for (__i = 0; __i < __bitset_words((_s)); __i++) \
124 (d)->__bits[__i] |= (s)->__bits[__i]; \
125 } while (0)
126
127 #define BIT_OR2(_s, d, s1, s2) do { \
128 __size_t __i; \
129 for (__i = 0; __i < __bitset_words((_s)); __i++) \
130 (d)->__bits[__i] = (s1)->__bits[__i] | (s2)->__bits[__i];\
131 } while (0)
132
133 #define BIT_AND(_s, d, s) do { \
134 __size_t __i; \
135 for (__i = 0; __i < __bitset_words((_s)); __i++) \
136 (d)->__bits[__i] &= (s)->__bits[__i]; \
137 } while (0)
138
139 #define BIT_AND2(_s, d, s1, s2) do { \
140 __size_t __i; \
141 for (__i = 0; __i < __bitset_words((_s)); __i++) \
142 (d)->__bits[__i] = (s1)->__bits[__i] & (s2)->__bits[__i];\
143 } while (0)
144
145 #define BIT_NAND(_s, d, s) do { \
146 __size_t __i; \
147 for (__i = 0; __i < __bitset_words((_s)); __i++) \
148 (d)->__bits[__i] &= ~(s)->__bits[__i]; \
149 } while (0)
150
151 #define BIT_NAND2(_s, d, s1, s2) do { \
152 __size_t __i; \
153 for (__i = 0; __i < __bitset_words((_s)); __i++) \
154 (d)->__bits[__i] = (s1)->__bits[__i] & ~(s2)->__bits[__i];\
155 } while (0)
156
157 #define BIT_XOR(_s, d, s) do { \
158 __size_t __i; \
159 for (__i = 0; __i < __bitset_words((_s)); __i++) \
160 (d)->__bits[__i] ^= (s)->__bits[__i]; \
161 } while (0)
162
163 #define BIT_XOR2(_s, d, s1, s2) do { \
164 __size_t __i; \
165 for (__i = 0; __i < __bitset_words((_s)); __i++) \
166 (d)->__bits[__i] = (s1)->__bits[__i] ^ (s2)->__bits[__i];\
167 } while (0)
168
169 #define BIT_CLR_ATOMIC(_s, n, p) \
170 atomic_clear_long(&(p)->__bits[__bitset_word(_s, n)], \
171 __bitset_mask((_s), n))
172
173 #define BIT_SET_ATOMIC(_s, n, p) \
174 atomic_set_long(&(p)->__bits[__bitset_word(_s, n)], \
175 __bitset_mask((_s), n))
176
177 #define BIT_SET_ATOMIC_ACQ(_s, n, p) \
178 atomic_set_acq_long(&(p)->__bits[__bitset_word(_s, n)], \
179 __bitset_mask((_s), n))
180
181 /* Convenience functions catering special cases. */
182 #define BIT_AND_ATOMIC(_s, d, s) do { \
183 __size_t __i; \
184 for (__i = 0; __i < __bitset_words((_s)); __i++) \
185 atomic_clear_long(&(d)->__bits[__i], \
186 ~(s)->__bits[__i]); \
187 } while (0)
188
189 #define BIT_OR_ATOMIC(_s, d, s) do { \
190 __size_t __i; \
191 for (__i = 0; __i < __bitset_words((_s)); __i++) \
192 atomic_set_long(&(d)->__bits[__i], \
193 (s)->__bits[__i]); \
194 } while (0)
195
196 #define BIT_COPY_STORE_REL(_s, f, t) do { \
197 __size_t __i; \
198 for (__i = 0; __i < __bitset_words((_s)); __i++) \
199 atomic_store_rel_long(&(t)->__bits[__i], \
200 (f)->__bits[__i]); \
201 } while (0)
202
203 #define BIT_FFS(_s, p) __extension__ ({ \
204 __size_t __i; \
205 int __bit; \
206 \
207 __bit = 0; \
208 for (__i = 0; __i < __bitset_words((_s)); __i++) { \
209 if ((p)->__bits[__i] != 0) { \
210 __bit = ffsl((p)->__bits[__i]); \
211 __bit += __i * _BITSET_BITS; \
212 break; \
213 } \
214 } \
215 __bit; \
216 })
217
218 #define BIT_FLS(_s, p) __extension__ ({ \
219 __size_t __i; \
220 int __bit; \
221 \
222 __bit = 0; \
223 for (__i = __bitset_words((_s)); __i > 0; __i--) { \
224 if ((p)->__bits[__i - 1] != 0) { \
225 __bit = flsl((p)->__bits[__i - 1]); \
226 __bit += (__i - 1) * _BITSET_BITS; \
227 break; \
228 } \
229 } \
230 __bit; \
231 })
232
233 #define BIT_COUNT(_s, p) __extension__ ({ \
234 __size_t __i; \
235 int __count; \
236 \
237 __count = 0; \
238 for (__i = 0; __i < __bitset_words((_s)); __i++) \
239 __count += __bitcountl((p)->__bits[__i]); \
240 __count; \
241 })
242
243 #define BITSET_T_INITIALIZER(x) \
244 { .__bits = { x } }
245
246 #define BITSET_FSET(n) \
247 [ 0 ... ((n) - 1) ] = (-1L)
248
249 /*
250 * Dynamically allocate a bitset.
251 */
252 #define BITSET_ALLOC(_s, mt, mf) \
253 malloc(__bitset_words(_s) * sizeof(long), mt, (mf))
254
255 #endif /* !_SYS_BITSET_H_ */
Cache object: f917a8656776355250b1386169764470
|