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 (1L << ((__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_ */ 256