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 ,
65 .Nm BIT_COPY_STORE_REL
66 .Nd bitset manipulation macros
71 .Fn BITSET_DEFINE "STRUCTNAME" "const SETSIZE"
72 .Fn BITSET_T_INITIALIZER "ARRAY_CONTENTS"
73 .Fn BITSET_FSET "N_WORDS"
75 .Fn BIT_CLR "const SETSIZE" "size_t bit" "struct STRUCTNAME *bitset"
76 .Fn BIT_COPY "const SETSIZE" "struct STRUCTNAME *from" "struct STRUCTNAME *to"
78 .Fn BIT_ISSET "const SETSIZE" "size_t bit" "struct STRUCTNAME *bitset"
79 .Fn BIT_SET "const SETSIZE" "size_t bit" "struct STRUCTNAME *bitset"
80 .Fn BIT_ZERO "const SETSIZE" "struct STRUCTNAME *bitset"
81 .Fn BIT_FILL "const SETSIZE" "struct STRUCTNAME *bitset"
82 .Fn BIT_SETOF "const SETSIZE" "size_t bit" "struct STRUCTNAME *bitset"
84 .Fn BIT_EMPTY "const SETSIZE" "struct STRUCTNAME *bitset"
86 .Fn BIT_ISFULLSET "const SETSIZE" "struct STRUCTNAME *bitset"
88 .Fn BIT_FFS "const SETSIZE" "struct STRUCTNAME *bitset"
90 .Fn BIT_FFS_AT "const SETSIZE" "struct STRUCTNAME *bitset" "long start"
92 .Fn BIT_FLS "const SETSIZE" "struct STRUCTNAME *bitset"
94 .Fn BIT_COUNT "const SETSIZE" "struct STRUCTNAME *bitset"
98 .Fa "const SETSIZE" "struct STRUCTNAME *haystack" "struct STRUCTNAME *needle"
102 .Fa "const SETSIZE" "struct STRUCTNAME *bitset1" "struct STRUCTNAME *bitset2"
106 .Fa "const SETSIZE" "struct STRUCTNAME *bitset1" "struct STRUCTNAME *bitset2"
108 .Fn BIT_OR "const SETSIZE" "struct STRUCTNAME *dst" "struct STRUCTNAME *src"
111 .Fa "struct STRUCTNAME *dst"
112 .Fa "struct STRUCTNAME *src1"
113 .Fa "struct STRUCTNAME *src2"
115 .Fn BIT_AND "const SETSIZE" "struct STRUCTNAME *dst" "struct STRUCTNAME *src"
118 .Fa "struct STRUCTNAME *dst"
119 .Fa "struct STRUCTNAME *src1"
120 .Fa "struct STRUCTNAME *src2"
122 .Fn BIT_ANDNOT "const SETSIZE" "struct STRUCTNAME *dst" "struct STRUCTNAME *src"
125 .Fa "struct STRUCTNAME *dst"
126 .Fa "struct STRUCTNAME *src1"
127 .Fa "struct STRUCTNAME *src2"
129 .Fn BIT_XOR "const SETSIZE" "struct STRUCTNAME *dst" "struct STRUCTNAME *src"
132 .Fa "struct STRUCTNAME *dst"
133 .Fa "struct STRUCTNAME *src1"
134 .Fa "struct STRUCTNAME *src2"
137 .Fn BIT_CLR_ATOMIC "const SETSIZE" "size_t bit" "struct STRUCTNAME *bitset"
138 .Fn BIT_SET_ATOMIC "const SETSIZE" "size_t bit" "struct STRUCTNAME *bitset"
139 .Fn BIT_SET_ATOMIC_ACQ "const SETSIZE" "size_t bit" "struct STRUCTNAME *bitset"
142 .Fa "const SETSIZE" "struct STRUCTNAME *dst" "struct STRUCTNAME *src"
145 .Fa "const SETSIZE" "struct STRUCTNAME *dst" "struct STRUCTNAME *src"
147 .Fo BIT_COPY_STORE_REL
148 .Fa "const SETSIZE" "struct STRUCTNAME *from" "struct STRUCTNAME *to"
153 family of macros provide a flexible and efficient bitset implementation if the
154 maximum size of the set is known at compilation.
155 Throughout this manual page, the name
157 refers to the size of the bitset in bits.
158 Individual bits in bitsets are referenced with indices zero through
167 macro defines a bitset struct
169 with room to represent
174 .Fn BITSET_T_INITIALIZER
175 macro allows one to initialize a bitset struct with a compile time literal
180 macro generates a compile time literal, usable by
181 .Fn BITSET_T_INITIALIZER ,
182 representing a full bitset (all bits set).
184 .Fn BITSET_T_INITIALIZER
188 .Sx BITSET_T_INITIALIZER EXAMPLE
195 .Bd -literal -offset indent
196 __bitset_words(SETSIZE)
203 in the bitset pointed to by
207 macro is identical, but the bit is cleared atomically.
211 macro copies the contents of the bitset
215 .Fn BIT_COPY_STORE_REL
216 is similar, but copies component machine words from
220 with atomic store with release semantics.
223 is composed of multiple machine words,
224 .Fn BIT_COPY_STORE_REL
225 performs multiple individually atomic operations.)
231 in the bitset pointed to by
235 macro is identical, but the bit is set atomically.
237 .Fn BIT_SET_ATOMIC_ACQ
238 macro sets the bit with acquire semantics.
242 macro clears all bits in
247 macro sets all bits in
252 macro clears all bits in
254 before setting only bit
271 is full (all bits set).
275 macro returns the 1-index of the first (lowest) set bit in
282 to use the non-zero result of
286 index parameter to any other
288 macro, you must subtract one from the result.
292 macro returns the 1-index of the first (lowest) set bit in
294 which is greater than the given 1-indexed
296 or zero if no bits in
304 macro returns the 1-index of the last (highest) set bit in
311 to use the non-zero result of
315 index parameter to any other
317 macro, you must subtract one from the result.
321 macro returns the total number of set bits in
341 have any common bits.
346 is not the empty set.)
359 macro sets bits present in
365 equivalent of the scalar:
370 is similar, but sets bits in the component machine words in
375 is composed of multiple machine words,
377 performs multiple individually atomic operations.)
385 and assigns the result to
389 equivalent of the scalar:
398 macro clears bits absent from
404 equivalent of the scalar:
409 is similar, with the same atomic semantics as
418 and assigns the result to
422 equivalent of the scalar:
431 macro clears bits set in
437 equivalent of the scalar:
448 and assigns the result to
452 equivalent of the scalar:
461 macro toggles bits set in
467 equivalent of the scalar:
478 and assigns the result to
482 equivalent of the scalar:
488 .Sh BITSET_T_INITIALIZER EXAMPLE
490 BITSET_DEFINE(_myset, MYSETSIZE);
494 /* Initialize myset to filled (all bits set) */
495 myset = BITSET_T_INITIALIZER(BITSET_FSET(__bitset_words(MYSETSIZE)));
497 /* Initialize myset to only the lowest bit set */
498 myset = BITSET_T_INITIALIZER(0x1);
506 macros first appeared in
511 released in July 2014.
513 This manual page first appeared in
519 macros were generalized and pulled out of
526 .An Attilio Rao Aq Mt attilio@FreeBSD.org .
527 This manual page was written by
528 .An Conrad Meyer Aq Mt cem@FreeBSD.org .
532 argument to all of these macros must match the value given to
535 Unlike every other reference to individual set members, which are zero-indexed,
540 return a one-indexed result (or zero if the set is empty).