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 ,
60 .Nm BIT_SET_ATOMIC_ACQ ,
63 .Nm BIT_COPY_STORE_REL
64 .Nd bitset manipulation macros
69 .Fn BITSET_DEFINE "STRUCTNAME" "const SETSIZE"
70 .Fn BITSET_T_INITIALIZER "ARRAY_CONTENTS"
71 .Fn BITSET_FSET "N_WORDS"
73 .Fn BIT_CLR "const SETSIZE" "size_t bit" "struct STRUCTNAME *bitset"
74 .Fn BIT_COPY "const SETSIZE" "struct STRUCTNAME *from" "struct STRUCTNAME *to"
76 .Fn BIT_ISSET "const SETSIZE" "size_t bit" "struct STRUCTNAME *bitset"
77 .Fn BIT_SET "const SETSIZE" "size_t bit" "struct STRUCTNAME *bitset"
78 .Fn BIT_ZERO "const SETSIZE" "struct STRUCTNAME *bitset"
79 .Fn BIT_FILL "const SETSIZE" "struct STRUCTNAME *bitset"
80 .Fn BIT_SETOF "const SETSIZE" "size_t bit" "struct STRUCTNAME *bitset"
82 .Fn BIT_EMPTY "const SETSIZE" "struct STRUCTNAME *bitset"
84 .Fn BIT_ISFULLSET "const SETSIZE" "struct STRUCTNAME *bitset"
86 .Fn BIT_FFS "const SETSIZE" "struct STRUCTNAME *bitset"
88 .Fn BIT_COUNT "const SETSIZE" "struct STRUCTNAME *bitset"
92 .Fa "const SETSIZE" "struct STRUCTNAME *haystack" "struct STRUCTNAME *needle"
96 .Fa "const SETSIZE" "struct STRUCTNAME *bitset1" "struct STRUCTNAME *bitset2"
100 .Fa "const SETSIZE" "struct STRUCTNAME *bitset1" "struct STRUCTNAME *bitset2"
102 .Fn BIT_OR "const SETSIZE" "struct STRUCTNAME *dst" "struct STRUCTNAME *src"
105 .Fa "struct STRUCTNAME *dst"
106 .Fa "struct STRUCTNAME *src1"
107 .Fa "struct STRUCTNAME *src2"
109 .Fn BIT_AND "const SETSIZE" "struct STRUCTNAME *dst" "struct STRUCTNAME *src"
112 .Fa "struct STRUCTNAME *dst"
113 .Fa "struct STRUCTNAME *src1"
114 .Fa "struct STRUCTNAME *src2"
116 .Fn BIT_NAND "const SETSIZE" "struct STRUCTNAME *dst" "struct STRUCTNAME *src"
119 .Fa "struct STRUCTNAME *dst"
120 .Fa "struct STRUCTNAME *src1"
121 .Fa "struct STRUCTNAME *src2"
123 .Fn BIT_XOR "const SETSIZE" "struct STRUCTNAME *dst" "struct STRUCTNAME *src"
126 .Fa "struct STRUCTNAME *dst"
127 .Fa "struct STRUCTNAME *src1"
128 .Fa "struct STRUCTNAME *src2"
131 .Fn BIT_CLR_ATOMIC "const SETSIZE" "size_t bit" "struct STRUCTNAME *bitset"
132 .Fn BIT_SET_ATOMIC "const SETSIZE" "size_t bit" "struct STRUCTNAME *bitset"
133 .Fn BIT_SET_ATOMIC_ACQ "const SETSIZE" "size_t bit" "struct STRUCTNAME *bitset"
136 .Fa "const SETSIZE" "struct STRUCTNAME *dst" "struct STRUCTNAME *src"
139 .Fa "const SETSIZE" "struct STRUCTNAME *dst" "struct STRUCTNAME *src"
141 .Fo BIT_COPY_STORE_REL
142 .Fa "const SETSIZE" "struct STRUCTNAME *from" "struct STRUCTNAME *to"
147 family of macros provide a flexible and efficient bitset implementation if the
148 maximum size of the set is known at compilation.
149 Throughout this manual page, the name
151 refers to the size of the bitset in bits.
152 Individual bits in bitsets are referenced with indices zero through
161 macro defines a bitset struct
163 with room to represent
168 .Fn BITSET_T_INITIALIZER
169 macro allows one to initialize a bitset struct with a compile time literal
174 macro generates a compile time literal, usable by
175 .Fn BITSET_T_INITIALIZER ,
176 representing a full bitset (all bits set).
178 .Fn BITSET_T_INITIALIZER
182 .Sx BITSET_T_INITIALIZER EXAMPLE
189 .Bd -literal -offset indent
190 __bitset_words(SETSIZE)
197 in the bitset pointed to by
201 macro is identical, but the bit is cleared atomically.
205 macro copies the contents of the bitset
209 .Fn BIT_COPY_STORE_REL
210 is similar, but copies component machine words from
214 with atomic store with release semantics.
217 is composed of multiple machine words,
218 .Fn BIT_COPY_STORE_REL
219 performs multiple individually atomic operations.)
225 in the bitset pointed to by
229 macro is identical, but the bit is set atomically.
231 .Fn BIT_SET_ATOMIC_ACQ
232 macro sets the bit with acquire semantics.
236 macro clears all bits in
241 macro sets all bits in
246 macro clears all bits in
248 before setting only bit
265 is full (all bits set).
269 macro returns the 1-index of the first (lowest) set bit in
276 to use the non-zero result of
280 index parameter to any other
282 macro, you must subtract one from the result.
286 macro returns the total number of set bits in
306 have any common bits.
311 is not the empty set.)
324 macro sets bits present in
330 equivalent of the scalar:
335 is similar, but sets bits in the component machine words in
340 is composed of multiple machine words,
342 performs multiple individually atomic operations.)
350 and assigns the result to
354 equivalent of the scalar:
363 macro clears bits absent from
369 equivalent of the scalar:
374 is similar, with the same atomic semantics as
383 and assigns the result to
387 equivalent of the scalar:
396 macro clears bits set in
402 equivalent of the scalar:
413 and assigns the result to
417 equivalent of the scalar:
426 macro toggles bits set in
432 equivalent of the scalar:
443 and assigns the result to
447 equivalent of the scalar:
453 .Sh BITSET_T_INITIALIZER EXAMPLE
455 BITSET_DEFINE(_myset, MYSETSIZE);
459 /* Initialize myset to filled (all bits set) */
460 myset = BITSET_T_INITIALIZER(BITSET_FSET(__bitset_words(MYSETSIZE)));
462 /* Initialize myset to only the lowest bit set */
463 myset = BITSET_T_INITIALIZER(0x1);
471 macros first appeared in
476 released in July 2014.
478 This manual page first appeared in
484 macros were generalized and pulled out of
491 .An Attilio Rao Aq Mt attilio@FreeBSD.org .
492 This manual page was written by
493 .An Conrad Meyer Aq Mt cem@FreeBSD.org .
497 argument to all of these macros must match the value given to
500 Unlike every other reference to individual set members, which are zero-indexed,
502 returns a one-indexed result (or zero if the set is empty).