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