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 ,
55 .Nm BIT_SET_ATOMIC_ACQ ,
58 .Nm BIT_COPY_STORE_REL
59 .Nd bitset manipulation macros
64 .Fn BITSET_DEFINE "STRUCTNAME" "const SETSIZE"
65 .Fn BITSET_T_INITIALIZER "ARRAY_CONTENTS"
66 .Fn BITSET_FSET "N_WORDS"
68 .Fn BIT_CLR "const SETSIZE" "size_t bit" "struct STRUCTNAME *bitset"
69 .Fn BIT_COPY "const SETSIZE" "struct STRUCTNAME *from" "struct STRUCTNAME *to"
71 .Fn BIT_ISSET "const SETSIZE" "size_t bit" "struct STRUCTNAME *bitset"
72 .Fn BIT_SET "const SETSIZE" "size_t bit" "struct STRUCTNAME *bitset"
73 .Fn BIT_ZERO "const SETSIZE" "struct STRUCTNAME *bitset"
74 .Fn BIT_FILL "const SETSIZE" "struct STRUCTNAME *bitset"
75 .Fn BIT_SETOF "const SETSIZE" "size_t bit" "struct STRUCTNAME *bitset"
77 .Fn BIT_EMPTY "const SETSIZE" "struct STRUCTNAME *bitset"
79 .Fn BIT_ISFULLSET "const SETSIZE" "struct STRUCTNAME *bitset"
81 .Fn BIT_FFS "const SETSIZE" "struct STRUCTNAME *bitset"
83 .Fn BIT_COUNT "const SETSIZE" "struct STRUCTNAME *bitset"
87 .Fa "const SETSIZE" "struct STRUCTNAME *haystack" "struct STRUCTNAME *needle"
91 .Fa "const SETSIZE" "struct STRUCTNAME *bitset1" "struct STRUCTNAME *bitset2"
95 .Fa "const SETSIZE" "struct STRUCTNAME *bitset1" "struct STRUCTNAME *bitset2"
97 .Fn BIT_OR "const SETSIZE" "struct STRUCTNAME *dst" "struct STRUCTNAME *src"
98 .Fn BIT_AND "const SETSIZE" "struct STRUCTNAME *dst" "struct STRUCTNAME *src"
99 .Fn BIT_NAND "const SETSIZE" "struct STRUCTNAME *dst" "struct STRUCTNAME *src"
101 .Fn BIT_CLR_ATOMIC "const SETSIZE" "size_t bit" "struct STRUCTNAME *bitset"
102 .Fn BIT_SET_ATOMIC "const SETSIZE" "size_t bit" "struct STRUCTNAME *bitset"
103 .Fn BIT_SET_ATOMIC_ACQ "const SETSIZE" "size_t bit" "struct STRUCTNAME *bitset"
106 .Fa "const SETSIZE" "struct STRUCTNAME *dst" "struct STRUCTNAME *src"
109 .Fa "const SETSIZE" "struct STRUCTNAME *dst" "struct STRUCTNAME *src"
111 .Fo BIT_COPY_STORE_REL
112 .Fa "const SETSIZE" "struct STRUCTNAME *from" "struct STRUCTNAME *to"
117 family of macros provide a flexible and efficient bitset implementation if the
118 maximum size of the set is known at compilation.
119 Throughout this manual page, the name
121 refers to the size of the bitset in bits.
122 Individual bits in bitsets are referenced with indices zero through
131 macro defines a bitset struct
133 with room to represent
138 .Fn BITSET_T_INITIALIZER
139 macro allows one to initialize a bitset struct with a compile time literal
144 macro generates a compile time literal, usable by
145 .Fn BITSET_T_INITIALIZER ,
146 representing a full bitset (all bits set).
148 .Fn BITSET_T_INITIALIZER
152 .Sx BITSET_T_INITIALIZER EXAMPLE
159 .Bd -literal -offset indent
160 __bitset_words(SETSIZE)
167 in the bitset pointed to by
171 macro is identical, but the bit is cleared atomically.
175 macro copies the contents of the bitset
179 .Fn BIT_COPY_STORE_REL
180 is similar, but copies component machine words from
184 with atomic store with release semantics.
187 is composed of multiple machine words,
188 .Fn BIT_COPY_STORE_REL
189 performs multiple individually atomic operations.)
195 in the bitset pointed to by
199 macro is identical, but the bit is set atomically.
201 .Fn BIT_SET_ATOMIC_ACQ
202 macro sets the bit with acquire semantics.
206 macro clears all bits in
211 macro sets all bits in
216 macro clears all bits in
218 before setting only bit
235 is full (all bits set).
239 macro returns the 1-index of the first (lowest) set bit in
246 to use the non-zero result of
250 index parameter to any other
252 macro, you must subtract one from the result.
256 macro returns the total number of set bits in
276 have any common bits.
281 is not the empty set.)
294 macro sets bits present in
300 equivalent of the scalar:
305 is similar, but sets bits in the component machine words in
310 is composed of multiple machine words,
312 performs multiple individually atomic operations.)
316 macro clears bits absent from
322 equivalent of the scalar:
327 is similar, with the same atomic semantics as
332 macro clears bits set in
338 equivalent of the scalar:
342 .Sh BITSET_T_INITIALIZER EXAMPLE
344 BITSET_DEFINE(_myset, MYSETSIZE);
348 /* Initialize myset to filled (all bits set) */
349 myset = BITSET_T_INITIALIZER(BITSET_FSET(__bitset_words(MYSETSIZE)));
351 /* Initialize myset to only the lowest bit set */
352 myset = BITSET_T_INITIALIZER(0x1);
360 macros first appeared in
365 released in July 2014.
367 This manual page first appeared in
373 macros were generalized and pulled out of
380 .An Attilio Rao Aq Mt attilio@FreeBSD.org .
381 This manual page was written by
382 .An Conrad Meyer Aq Mt cem@FreeBSD.org .
386 argument to all of these macros must match the value given to
389 Unlike every other reference to individual set members, which are zero-indexed,
391 returns a one-indexed result (or zero if the set is empty).