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_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