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 ,
61 .Nm BIT_SET_ATOMIC_ACQ ,
64 .Nm BIT_COPY_STORE_REL
65 .Nd bitset manipulation macros
70 .Fn BITSET_DEFINE "STRUCTNAME" "const SETSIZE"
71 .Fn BITSET_T_INITIALIZER "ARRAY_CONTENTS"
72 .Fn BITSET_FSET "N_WORDS"
74 .Fn BIT_CLR "const SETSIZE" "size_t bit" "struct STRUCTNAME *bitset"
75 .Fn BIT_COPY "const SETSIZE" "struct STRUCTNAME *from" "struct STRUCTNAME *to"
77 .Fn BIT_ISSET "const SETSIZE" "size_t bit" "struct STRUCTNAME *bitset"
78 .Fn BIT_SET "const SETSIZE" "size_t bit" "struct STRUCTNAME *bitset"
79 .Fn BIT_ZERO "const SETSIZE" "struct STRUCTNAME *bitset"
80 .Fn BIT_FILL "const SETSIZE" "struct STRUCTNAME *bitset"
81 .Fn BIT_SETOF "const SETSIZE" "size_t bit" "struct STRUCTNAME *bitset"
83 .Fn BIT_EMPTY "const SETSIZE" "struct STRUCTNAME *bitset"
85 .Fn BIT_ISFULLSET "const SETSIZE" "struct STRUCTNAME *bitset"
87 .Fn BIT_FFS "const SETSIZE" "struct STRUCTNAME *bitset"
89 .Fn BIT_FLS "const SETSIZE" "struct STRUCTNAME *bitset"
91 .Fn BIT_COUNT "const SETSIZE" "struct STRUCTNAME *bitset"
95 .Fa "const SETSIZE" "struct STRUCTNAME *haystack" "struct STRUCTNAME *needle"
99 .Fa "const SETSIZE" "struct STRUCTNAME *bitset1" "struct STRUCTNAME *bitset2"
103 .Fa "const SETSIZE" "struct STRUCTNAME *bitset1" "struct STRUCTNAME *bitset2"
105 .Fn BIT_OR "const SETSIZE" "struct STRUCTNAME *dst" "struct STRUCTNAME *src"
108 .Fa "struct STRUCTNAME *dst"
109 .Fa "struct STRUCTNAME *src1"
110 .Fa "struct STRUCTNAME *src2"
112 .Fn BIT_AND "const SETSIZE" "struct STRUCTNAME *dst" "struct STRUCTNAME *src"
115 .Fa "struct STRUCTNAME *dst"
116 .Fa "struct STRUCTNAME *src1"
117 .Fa "struct STRUCTNAME *src2"
119 .Fn BIT_NAND "const SETSIZE" "struct STRUCTNAME *dst" "struct STRUCTNAME *src"
122 .Fa "struct STRUCTNAME *dst"
123 .Fa "struct STRUCTNAME *src1"
124 .Fa "struct STRUCTNAME *src2"
126 .Fn BIT_XOR "const SETSIZE" "struct STRUCTNAME *dst" "struct STRUCTNAME *src"
129 .Fa "struct STRUCTNAME *dst"
130 .Fa "struct STRUCTNAME *src1"
131 .Fa "struct STRUCTNAME *src2"
134 .Fn BIT_CLR_ATOMIC "const SETSIZE" "size_t bit" "struct STRUCTNAME *bitset"
135 .Fn BIT_SET_ATOMIC "const SETSIZE" "size_t bit" "struct STRUCTNAME *bitset"
136 .Fn BIT_SET_ATOMIC_ACQ "const SETSIZE" "size_t bit" "struct STRUCTNAME *bitset"
139 .Fa "const SETSIZE" "struct STRUCTNAME *dst" "struct STRUCTNAME *src"
142 .Fa "const SETSIZE" "struct STRUCTNAME *dst" "struct STRUCTNAME *src"
144 .Fo BIT_COPY_STORE_REL
145 .Fa "const SETSIZE" "struct STRUCTNAME *from" "struct STRUCTNAME *to"
150 family of macros provide a flexible and efficient bitset implementation if the
151 maximum size of the set is known at compilation.
152 Throughout this manual page, the name
154 refers to the size of the bitset in bits.
155 Individual bits in bitsets are referenced with indices zero through
164 macro defines a bitset struct
166 with room to represent
171 .Fn BITSET_T_INITIALIZER
172 macro allows one to initialize a bitset struct with a compile time literal
177 macro generates a compile time literal, usable by
178 .Fn BITSET_T_INITIALIZER ,
179 representing a full bitset (all bits set).
181 .Fn BITSET_T_INITIALIZER
185 .Sx BITSET_T_INITIALIZER EXAMPLE
192 .Bd -literal -offset indent
193 __bitset_words(SETSIZE)
200 in the bitset pointed to by
204 macro is identical, but the bit is cleared atomically.
208 macro copies the contents of the bitset
212 .Fn BIT_COPY_STORE_REL
213 is similar, but copies component machine words from
217 with atomic store with release semantics.
220 is composed of multiple machine words,
221 .Fn BIT_COPY_STORE_REL
222 performs multiple individually atomic operations.)
228 in the bitset pointed to by
232 macro is identical, but the bit is set atomically.
234 .Fn BIT_SET_ATOMIC_ACQ
235 macro sets the bit with acquire semantics.
239 macro clears all bits in
244 macro sets all bits in
249 macro clears all bits in
251 before setting only bit
268 is full (all bits set).
272 macro returns the 1-index of the first (lowest) set bit in
279 to use the non-zero result of
283 index parameter to any other
285 macro, you must subtract one from the result.
289 macro returns the 1-index of the last (highest) set bit in
296 to use the non-zero result of
300 index parameter to any other
302 macro, you must subtract one from the result.
306 macro returns the total number of set bits in
326 have any common bits.
331 is not the empty set.)
344 macro sets bits present in
350 equivalent of the scalar:
355 is similar, but sets bits in the component machine words in
360 is composed of multiple machine words,
362 performs multiple individually atomic operations.)
370 and assigns the result to
374 equivalent of the scalar:
383 macro clears bits absent from
389 equivalent of the scalar:
394 is similar, with the same atomic semantics as
403 and assigns the result to
407 equivalent of the scalar:
416 macro clears bits set in
422 equivalent of the scalar:
433 and assigns the result to
437 equivalent of the scalar:
446 macro toggles bits set in
452 equivalent of the scalar:
463 and assigns the result to
467 equivalent of the scalar:
473 .Sh BITSET_T_INITIALIZER EXAMPLE
475 BITSET_DEFINE(_myset, MYSETSIZE);
479 /* Initialize myset to filled (all bits set) */
480 myset = BITSET_T_INITIALIZER(BITSET_FSET(__bitset_words(MYSETSIZE)));
482 /* Initialize myset to only the lowest bit set */
483 myset = BITSET_T_INITIALIZER(0x1);
491 macros first appeared in
496 released in July 2014.
498 This manual page first appeared in
504 macros were generalized and pulled out of
511 .An Attilio Rao Aq Mt attilio@FreeBSD.org .
512 This manual page was written by
513 .An Conrad Meyer Aq Mt cem@FreeBSD.org .
517 argument to all of these macros must match the value given to
520 Unlike every other reference to individual set members, which are zero-indexed,
524 return a one-indexed result (or zero if the set is empty).