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