1 /*- 2 * Copyright (c) 2008, Jeffrey Roberson <[email protected]> 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_AND(_s, d, s) do { \ 126 __size_t __i; \ 127 for (__i = 0; __i < __bitset_words((_s)); __i++) \ 128 (d)->__bits[__i] &= (s)->__bits[__i]; \ 129 } while (0) 130 131 #define BIT_NAND(_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_CLR_ATOMIC(_s, n, p) \ 138 atomic_clear_long(&(p)->__bits[__bitset_word(_s, n)], \ 139 __bitset_mask((_s), n)) 140 141 #define BIT_SET_ATOMIC(_s, n, p) \ 142 atomic_set_long(&(p)->__bits[__bitset_word(_s, n)], \ 143 __bitset_mask((_s), n)) 144 145 #define BIT_SET_ATOMIC_ACQ(_s, n, p) \ 146 atomic_set_acq_long(&(p)->__bits[__bitset_word(_s, n)], \ 147 __bitset_mask((_s), n)) 148 149 /* Convenience functions catering special cases. */ 150 #define BIT_AND_ATOMIC(_s, d, s) do { \ 151 __size_t __i; \ 152 for (__i = 0; __i < __bitset_words((_s)); __i++) \ 153 atomic_clear_long(&(d)->__bits[__i], \ 154 ~(s)->__bits[__i]); \ 155 } while (0) 156 157 #define BIT_OR_ATOMIC(_s, d, s) do { \ 158 __size_t __i; \ 159 for (__i = 0; __i < __bitset_words((_s)); __i++) \ 160 atomic_set_long(&(d)->__bits[__i], \ 161 (s)->__bits[__i]); \ 162 } while (0) 163 164 #define BIT_COPY_STORE_REL(_s, f, t) do { \ 165 __size_t __i; \ 166 for (__i = 0; __i < __bitset_words((_s)); __i++) \ 167 atomic_store_rel_long(&(t)->__bits[__i], \ 168 (f)->__bits[__i]); \ 169 } while (0) 170 171 #define BIT_FFS(_s, p) __extension__ ({ \ 172 __size_t __i; \ 173 int __bit; \ 174 \ 175 __bit = 0; \ 176 for (__i = 0; __i < __bitset_words((_s)); __i++) { \ 177 if ((p)->__bits[__i] != 0) { \ 178 __bit = ffsl((p)->__bits[__i]); \ 179 __bit += __i * _BITSET_BITS; \ 180 break; \ 181 } \ 182 } \ 183 __bit; \ 184 }) 185 186 #define BIT_COUNT(_s, p) __extension__ ({ \ 187 __size_t __i; \ 188 int __count; \ 189 \ 190 __count = 0; \ 191 for (__i = 0; __i < __bitset_words((_s)); __i++) \ 192 __count += __bitcountl((p)->__bits[__i]); \ 193 __count; \ 194 }) 195 196 #define BITSET_T_INITIALIZER(x) \ 197 { .__bits = { x } } 198 199 #define BITSET_FSET(n) \ 200 [ 0 ... ((n) - 1) ] = (-1L) 201 202 /* 203 * Dynamically allocate a bitset. 204 */ 205 #define BITSET_ALLOC(_s, mt, mf) \ 206 malloc(__bitset_words(_s) * sizeof(long), mt, (mf)) 207 208 #endif /* !_SYS_BITSET_H_ */ 209