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$ 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_ */ 254