1 .\" Copyright (c) 2015 Conrad Meyer <cem@FreeBSD.org>
2 .\" All rights reserved.
4 .\" Redistribution and use in source and binary forms, with or without
5 .\" modification, are permitted provided that the following conditions
7 .\" 1. Redistributions of source code must retain the above copyright
8 .\" notice, this list of conditions and the following disclaimer.
9 .\" 2. Redistributions in binary form must reproduce the above copyright
10 .\" notice, this list of conditions and the following disclaimer in the
11 .\" documentation and/or other materials provided with the distribution.
13 .\" THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS''
14 .\" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
15 .\" TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
16 .\" PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE
17 .\" LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
18 .\" CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
19 .\" SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
20 .\" INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
21 .\" CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
22 .\" ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
23 .\" POSSIBILITY OF SUCH DAMAGE.
34 .Nm BITSET_T_INITIALIZER ,
62 .Nm BIT_SET_ATOMIC_ACQ ,
63 .Nm BIT_TEST_SET_ATOMIC ,
64 .Nm BIT_TEST_CLR_ATOMIC ,
67 .Nm BIT_COPY_STORE_REL
68 .Nd bitset manipulation macros
73 .Fn BITSET_DEFINE "STRUCTNAME" "const SETSIZE"
74 .Fn BITSET_T_INITIALIZER "ARRAY_CONTENTS"
75 .Fn BITSET_FSET "N_WORDS"
77 .Fn BIT_CLR "const SETSIZE" "size_t bit" "struct STRUCTNAME *bitset"
78 .Fn BIT_COPY "const SETSIZE" "struct STRUCTNAME *from" "struct STRUCTNAME *to"
80 .Fn BIT_ISSET "const SETSIZE" "size_t bit" "struct STRUCTNAME *bitset"
81 .Fn BIT_SET "const SETSIZE" "size_t bit" "struct STRUCTNAME *bitset"
82 .Fn BIT_ZERO "const SETSIZE" "struct STRUCTNAME *bitset"
83 .Fn BIT_FILL "const SETSIZE" "struct STRUCTNAME *bitset"
84 .Fn BIT_SETOF "const SETSIZE" "size_t bit" "struct STRUCTNAME *bitset"
86 .Fn BIT_EMPTY "const SETSIZE" "struct STRUCTNAME *bitset"
88 .Fn BIT_ISFULLSET "const SETSIZE" "struct STRUCTNAME *bitset"
90 .Fn BIT_FFS "const SETSIZE" "struct STRUCTNAME *bitset"
92 .Fn BIT_FFS_AT "const SETSIZE" "struct STRUCTNAME *bitset" "long start"
94 .Fn BIT_FLS "const SETSIZE" "struct STRUCTNAME *bitset"
96 .Fn BIT_COUNT "const SETSIZE" "struct STRUCTNAME *bitset"
100 .Fa "const SETSIZE" "struct STRUCTNAME *haystack" "struct STRUCTNAME *needle"
104 .Fa "const SETSIZE" "struct STRUCTNAME *bitset1" "struct STRUCTNAME *bitset2"
108 .Fa "const SETSIZE" "struct STRUCTNAME *bitset1" "struct STRUCTNAME *bitset2"
110 .Fn BIT_OR "const SETSIZE" "struct STRUCTNAME *dst" "struct STRUCTNAME *src"
113 .Fa "struct STRUCTNAME *dst"
114 .Fa "struct STRUCTNAME *src1"
115 .Fa "struct STRUCTNAME *src2"
117 .Fn BIT_AND "const SETSIZE" "struct STRUCTNAME *dst" "struct STRUCTNAME *src"
120 .Fa "struct STRUCTNAME *dst"
121 .Fa "struct STRUCTNAME *src1"
122 .Fa "struct STRUCTNAME *src2"
124 .Fn BIT_ANDNOT "const SETSIZE" "struct STRUCTNAME *dst" "struct STRUCTNAME *src"
127 .Fa "struct STRUCTNAME *dst"
128 .Fa "struct STRUCTNAME *src1"
129 .Fa "struct STRUCTNAME *src2"
131 .Fn BIT_XOR "const SETSIZE" "struct STRUCTNAME *dst" "struct STRUCTNAME *src"
134 .Fa "struct STRUCTNAME *dst"
135 .Fa "struct STRUCTNAME *src1"
136 .Fa "struct STRUCTNAME *src2"
139 .Fn BIT_CLR_ATOMIC "const SETSIZE" "size_t bit" "struct STRUCTNAME *bitset"
140 .Fn BIT_SET_ATOMIC "const SETSIZE" "size_t bit" "struct STRUCTNAME *bitset"
141 .Fn BIT_SET_ATOMIC_ACQ "const SETSIZE" "size_t bit" "struct STRUCTNAME *bitset"
143 .Fn BIT_TEST_SET_ATOMIC "const SETSIZE" "size_t bit" "struct STRUCTNAME *bitset"
145 .Fn BIT_TEST_CLR_ATOMIC "const SETSIZE" "size_t bit" "struct STRUCTNAME *bitset"
148 .Fa "const SETSIZE" "struct STRUCTNAME *dst" "struct STRUCTNAME *src"
151 .Fa "const SETSIZE" "struct STRUCTNAME *dst" "struct STRUCTNAME *src"
153 .Fo BIT_COPY_STORE_REL
154 .Fa "const SETSIZE" "struct STRUCTNAME *from" "struct STRUCTNAME *to"
159 family of macros provide a flexible and efficient bitset implementation if the
160 maximum size of the set is known at compilation.
161 Throughout this manual page, the name
163 refers to the size of the bitset in bits.
164 Individual bits in bitsets are referenced with indices zero through
173 macro defines a bitset struct
175 with room to represent
180 .Fn BITSET_T_INITIALIZER
181 macro allows one to initialize a bitset struct with a compile time literal
186 macro generates a compile time literal, usable by
187 .Fn BITSET_T_INITIALIZER ,
188 representing a full bitset (all bits set).
190 .Fn BITSET_T_INITIALIZER
194 .Sx BITSET_T_INITIALIZER EXAMPLE
201 .Bd -literal -offset indent
202 __bitset_words(SETSIZE)
209 in the bitset pointed to by
213 macro is identical, but the bit is cleared atomically.
215 .Fn BIT_TEST_CLR_ATOMIC
216 macro atomically clears the bit and returns whether it was set.
220 macro copies the contents of the bitset
224 .Fn BIT_COPY_STORE_REL
225 is similar, but copies component machine words from
229 with atomic store with release semantics.
232 is composed of multiple machine words,
233 .Fn BIT_COPY_STORE_REL
234 performs multiple individually atomic operations.)
240 in the bitset pointed to by
244 macro is identical, but the bit is set atomically.
246 .Fn BIT_SET_ATOMIC_ACQ
247 macro sets the bit with acquire semantics.
249 .Fn BIT_TEST_SET_ATOMIC
250 macro atomically sets the bit and returns whether it was set.
254 macro clears all bits in
259 macro sets all bits in
264 macro clears all bits in
266 before setting only bit
283 is full (all bits set).
287 macro returns the 1-index of the first (lowest) set bit in
294 to use the non-zero result of
298 index parameter to any other
300 macro, you must subtract one from the result.
304 macro returns the 1-index of the first (lowest) set bit in
306 which is greater than the given 1-indexed
308 or zero if no bits in
316 macro returns the 1-index of the last (highest) set bit in
323 to use the non-zero result of
327 index parameter to any other
329 macro, you must subtract one from the result.
333 macro returns the total number of set bits in
353 have any common bits.
358 is not the empty set.)
371 macro sets bits present in
377 equivalent of the scalar:
382 is similar, but sets bits in the component machine words in
387 is composed of multiple machine words,
389 performs multiple individually atomic operations.)
397 and assigns the result to
401 equivalent of the scalar:
410 macro clears bits absent from
416 equivalent of the scalar:
421 is similar, with the same atomic semantics as
430 and assigns the result to
434 equivalent of the scalar:
443 macro clears bits set in
449 equivalent of the scalar:
460 and assigns the result to
464 equivalent of the scalar:
473 macro toggles bits set in
479 equivalent of the scalar:
490 and assigns the result to
494 equivalent of the scalar:
500 .Sh BITSET_T_INITIALIZER EXAMPLE
502 BITSET_DEFINE(_myset, MYSETSIZE);
506 /* Initialize myset to filled (all bits set) */
507 myset = BITSET_T_INITIALIZER(BITSET_FSET(__bitset_words(MYSETSIZE)));
509 /* Initialize myset to only the lowest bit set */
510 myset = BITSET_T_INITIALIZER(0x1);
518 macros first appeared in
523 released in July 2014.
525 This manual page first appeared in
531 macros were generalized and pulled out of
538 .An Attilio Rao Aq Mt attilio@FreeBSD.org .
539 This manual page was written by
540 .An Conrad Meyer Aq Mt cem@FreeBSD.org .
544 argument to all of these macros must match the value given to
547 Unlike every other reference to individual set members, which are zero-indexed,
552 return a one-indexed result (or zero if the set is empty).