xref: /freebsd/share/man/man9/bitset.9 (revision 3332f1b444d4a73238e9f59cca27bfc95fe936bd)
1.\" Copyright (c) 2015 Conrad Meyer <cem@FreeBSD.org>
2.\" All rights reserved.
3.\"
4.\" Redistribution and use in source and binary forms, with or without
5.\" modification, are permitted provided that the following conditions
6.\" are met:
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.
12.\"
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.
24.\"
25.\" $FreeBSD$
26.\"
27.Dd September 20, 2021
28.Dt BITSET 9
29.Os
30.Sh NAME
31.Nm bitset(9)
32\(em
33.Nm BITSET_DEFINE ,
34.Nm BITSET_T_INITIALIZER ,
35.Nm BITSET_FSET ,
36.Nm BIT_CLR ,
37.Nm BIT_COPY ,
38.Nm BIT_ISSET ,
39.Nm BIT_SET ,
40.Nm BIT_ZERO ,
41.Nm BIT_FILL ,
42.Nm BIT_SETOF ,
43.Nm BIT_EMPTY ,
44.Nm BIT_ISFULLSET ,
45.Nm BIT_FFS ,
46.Nm BIT_FFS_AT ,
47.Nm BIT_FLS ,
48.Nm BIT_FOREACH_ISSET ,
49.Nm BIT_FOREACH_ISCLR ,
50.Nm BIT_COUNT ,
51.Nm BIT_SUBSET ,
52.Nm BIT_OVERLAP ,
53.Nm BIT_CMP ,
54.Nm BIT_OR ,
55.Nm BIT_OR2 ,
56.Nm BIT_AND ,
57.Nm BIT_AND2 ,
58.Nm BIT_ANDNOT ,
59.Nm BIT_ANDNOT2 ,
60.Nm BIT_XOR ,
61.Nm BIT_XOR2 ,
62.Nm BIT_CLR_ATOMIC ,
63.Nm BIT_SET_ATOMIC ,
64.Nm BIT_SET_ATOMIC_ACQ ,
65.Nm BIT_TEST_SET_ATOMIC ,
66.Nm BIT_TEST_CLR_ATOMIC ,
67.Nm BIT_AND_ATOMIC ,
68.Nm BIT_OR_ATOMIC ,
69.Nm BIT_COPY_STORE_REL
70.Nd bitset manipulation macros
71.Sh SYNOPSIS
72.In sys/_bitset.h
73.In sys/bitset.h
74.\"
75.Fn BITSET_DEFINE "STRUCTNAME" "const SETSIZE"
76.Fn BITSET_T_INITIALIZER "ARRAY_CONTENTS"
77.Fn BITSET_FSET "N_WORDS"
78.\"
79.Fn BIT_CLR "const SETSIZE" "size_t bit" "struct STRUCTNAME *bitset"
80.Fn BIT_COPY "const SETSIZE" "struct STRUCTNAME *from" "struct STRUCTNAME *to"
81.Ft bool
82.Fn BIT_ISSET "const SETSIZE" "size_t bit" "struct STRUCTNAME *bitset"
83.Fn BIT_SET "const SETSIZE" "size_t bit" "struct STRUCTNAME *bitset"
84.Fn BIT_ZERO "const SETSIZE" "struct STRUCTNAME *bitset"
85.Fn BIT_FILL "const SETSIZE" "struct STRUCTNAME *bitset"
86.Fn BIT_SETOF "const SETSIZE" "size_t bit" "struct STRUCTNAME *bitset"
87.Ft bool
88.Fn BIT_EMPTY "const SETSIZE" "struct STRUCTNAME *bitset"
89.Ft bool
90.Fn BIT_ISFULLSET "const SETSIZE" "struct STRUCTNAME *bitset"
91.Ft long
92.Fn BIT_FFS "const SETSIZE" "struct STRUCTNAME *bitset"
93.Ft long
94.Fn BIT_FFS_AT "const SETSIZE" "struct STRUCTNAME *bitset" "long start"
95.Ft long
96.Fn BIT_FLS "const SETSIZE" "struct STRUCTNAME *bitset"
97.Fo BIT_FOREACH_ISSET
98.Fa "const SETSIZE"
99.Fa "size_t bit"
100.Fa "const struct STRUCTNAME *bitset"
101.Fc
102.Fo BIT_FOREACH_ISCLR
103.Fa "const SETSIZE"
104.Fa "size_t bit"
105.Fa "const struct STRUCTNAME *bitset"
106.Fc
107.Ft long
108.Fn BIT_COUNT "const SETSIZE" "struct STRUCTNAME *bitset"
109.Ft bool
110.Fo BIT_SUBSET
111.Fa "const SETSIZE" "struct STRUCTNAME *haystack" "struct STRUCTNAME *needle"
112.Fc
113.Ft bool
114.Fo BIT_OVERLAP
115.Fa "const SETSIZE" "struct STRUCTNAME *bitset1" "struct STRUCTNAME *bitset2"
116.Fc
117.Ft bool
118.Fo BIT_CMP
119.Fa "const SETSIZE" "struct STRUCTNAME *bitset1" "struct STRUCTNAME *bitset2"
120.Fc
121.Fn BIT_OR "const SETSIZE" "struct STRUCTNAME *dst" "struct STRUCTNAME *src"
122.Fo BIT_OR2
123.Fa "const SETSIZE"
124.Fa "struct STRUCTNAME *dst"
125.Fa "struct STRUCTNAME *src1"
126.Fa "struct STRUCTNAME *src2"
127.Fc
128.Fn BIT_AND "const SETSIZE" "struct STRUCTNAME *dst" "struct STRUCTNAME *src"
129.Fo BIT_AND2
130.Fa "const SETSIZE"
131.Fa "struct STRUCTNAME *dst"
132.Fa "struct STRUCTNAME *src1"
133.Fa "struct STRUCTNAME *src2"
134.Fc
135.Fn BIT_ANDNOT "const SETSIZE" "struct STRUCTNAME *dst" "struct STRUCTNAME *src"
136.Fo BIT_ANDNOT2
137.Fa "const SETSIZE"
138.Fa "struct STRUCTNAME *dst"
139.Fa "struct STRUCTNAME *src1"
140.Fa "struct STRUCTNAME *src2"
141.Fc
142.Fn BIT_XOR "const SETSIZE" "struct STRUCTNAME *dst" "struct STRUCTNAME *src"
143.Fo BIT_XOR2
144.Fa "const SETSIZE"
145.Fa "struct STRUCTNAME *dst"
146.Fa "struct STRUCTNAME *src1"
147.Fa "struct STRUCTNAME *src2"
148.Fc
149.\"
150.Fn BIT_CLR_ATOMIC "const SETSIZE" "size_t bit" "struct STRUCTNAME *bitset"
151.Fn BIT_SET_ATOMIC "const SETSIZE" "size_t bit" "struct STRUCTNAME *bitset"
152.Fn BIT_SET_ATOMIC_ACQ "const SETSIZE" "size_t bit" "struct STRUCTNAME *bitset"
153.Ft bool
154.Fn BIT_TEST_SET_ATOMIC "const SETSIZE" "size_t bit" "struct STRUCTNAME *bitset"
155.Ft bool
156.Fn BIT_TEST_CLR_ATOMIC "const SETSIZE" "size_t bit" "struct STRUCTNAME *bitset"
157.\"
158.Fo BIT_AND_ATOMIC
159.Fa "const SETSIZE" "struct STRUCTNAME *dst" "struct STRUCTNAME *src"
160.Fc
161.Fo BIT_OR_ATOMIC
162.Fa "const SETSIZE" "struct STRUCTNAME *dst" "struct STRUCTNAME *src"
163.Fc
164.Fo BIT_COPY_STORE_REL
165.Fa "const SETSIZE" "struct STRUCTNAME *from" "struct STRUCTNAME *to"
166.Fc
167.Sh DESCRIPTION
168The
169.Nm
170family of macros provide a flexible and efficient bitset implementation if the
171maximum size of the set is known at compilation.
172Throughout this manual page, the name
173.Fa SETSIZE
174refers to the size of the bitset in bits.
175Individual bits in bitsets are referenced with indices zero through
176.Fa SETSIZE - 1 .
177One example use of
178.In sys/bitset.h
179is
180.In sys/cpuset.h .
181.Pp
182The
183.Fn BITSET_DEFINE
184macro defines a bitset struct
185.Fa STRUCTNAME
186with room to represent
187.Fa SETSIZE
188bits.
189.Pp
190The
191.Fn BITSET_T_INITIALIZER
192macro allows one to initialize a bitset struct with a compile time literal
193value.
194.Pp
195The
196.Fn BITSET_FSET
197macro generates a compile time literal, usable by
198.Fn BITSET_T_INITIALIZER ,
199representing a full bitset (all bits set).
200For examples of
201.Fn BITSET_T_INITIALIZER
202and
203.Fn BITSET_FSET
204usage, see the
205.Sx BITSET_T_INITIALIZER EXAMPLE
206section.
207The
208.Fa N_WORDS
209parameter to
210.Fn BITSET_FSET
211should be:
212.Bd -literal -offset indent
213__bitset_words(SETSIZE)
214.Ed
215.Pp
216The
217.Fn BIT_CLR
218macro clears bit
219.Fa bit
220in the bitset pointed to by
221.Fa bitset .
222The
223.Fn BIT_CLR_ATOMIC
224macro is identical, but the bit is cleared atomically.
225The
226.Fn BIT_TEST_CLR_ATOMIC
227macro atomically clears the bit and returns whether it was set.
228.Pp
229The
230.Fn BIT_COPY
231macro copies the contents of the bitset
232.Fa from
233to the bitset
234.Fa to .
235.Fn BIT_COPY_STORE_REL
236is similar, but copies component machine words from
237.Fa from
238and writes them to
239.Fa to
240with atomic store with release semantics.
241(That is, if
242.Fa to
243is composed of multiple machine words,
244.Fn BIT_COPY_STORE_REL
245performs multiple individually atomic operations.)
246.Pp
247The
248.Fn BIT_SET
249macro sets bit
250.Fa bit
251in the bitset pointed to by
252.Fa bitset .
253The
254.Fn BIT_SET_ATOMIC
255macro is identical, but the bit is set atomically.
256The
257.Fn BIT_SET_ATOMIC_ACQ
258macro sets the bit with acquire semantics.
259The
260.Fn BIT_TEST_SET_ATOMIC
261macro atomically sets the bit and returns whether it was set.
262.Pp
263The
264.Fn BIT_ZERO
265macro clears all bits in
266.Fa bitset .
267.Pp
268The
269.Fn BIT_FILL
270macro sets all bits in
271.Fa bitset .
272.Pp
273The
274.Fn BIT_SETOF
275macro clears all bits in
276.Fa bitset
277before setting only bit
278.Fa bit .
279.Pp
280The
281.Fn BIT_EMPTY
282macro returns
283.Dv true
284if
285.Fa bitset
286is empty.
287.Pp
288The
289.Fn BIT_ISFULLSET
290macro returns
291.Dv true
292if
293.Fa bitset
294is full (all bits set).
295.Pp
296The
297.Fn BIT_FFS
298macro returns the 1-index of the first (lowest) set bit in
299.Fa bitset ,
300or zero if
301.Fa bitset
302is empty.
303Like with
304.Xr ffs 3 ,
305to use the non-zero result of
306.Fn BIT_FFS
307as a
308.Fa bit
309index parameter to any other
310.Nm
311macro, you must subtract one from the result.
312.Pp
313The
314.Fn BIT_FFS_AT
315macro returns the 1-index of the first (lowest) set bit in
316.Fa bitset ,
317which is greater than the given 1-indexed
318.Fa start ,
319or zero if no bits in
320.Fa bitset
321greater than
322.Fa start
323are set.
324.Pp
325The
326.Fn BIT_FLS
327macro returns the 1-index of the last (highest) set bit in
328.Fa bitset ,
329or zero if
330.Fa bitset
331is empty.
332Like with
333.Xr fls 3 ,
334to use the non-zero result of
335.Fn BIT_FLS
336as a
337.Fa bit
338index parameter to any other
339.Nm
340macro, you must subtract one from the result.
341.Pp
342The
343.Fn BIT_FOREACH_ISSET
344macro can be used to iterate over all set bits in
345.Fa bitset .
346The index variable
347.Fa bit
348must have been declared with type
349.Ft int ,
350and upon each iteration
351.Fa bit
352is set to the index of successive set bits.
353The value of
354.Fa bit
355after the loop terminates is undefined.
356Similarly,
357.Fn BIT_FOREACH_ISCLR
358iterates over all clear bits in
359.Fa bitset .
360In the loop body, the currently indexed bit may be set or cleared.
361However, setting or clearing bits other than the currently indexed
362bit does not guarantee that they will or will not be returned in
363subsequent iterations of the same loop.
364.Pp
365The
366.Fn BIT_COUNT
367macro returns the total number of set bits in
368.Fa bitset .
369.Pp
370The
371.Fn BIT_SUBSET
372macro returns
373.Dv true
374if
375.Fa needle
376is a subset of
377.Fa haystack .
378.Pp
379The
380.Fn BIT_OVERLAP
381macro returns
382.Dv true
383if
384.Fa bitset1
385and
386.Fa bitset2
387have any common bits.
388(That is, if
389.Fa bitset1
390AND
391.Fa bitset2
392is not the empty set.)
393.Pp
394The
395.Fn BIT_CMP
396macro returns
397.Dv true
398if
399.Fa bitset1
400is NOT equal to
401.Fa bitset2 .
402.Pp
403The
404.Fn BIT_OR
405macro sets bits present in
406.Fa src
407in
408.Fa dst .
409(It is the
410.Nm
411equivalent of the scalar:
412.Fa dst
413|=
414.Fa src . )
415.Fn BIT_OR_ATOMIC
416is similar, but sets bits in the component machine words in
417.Fa dst
418atomically.
419(That is, if
420.Fa dst
421is composed of multiple machine words,
422.Fn BIT_OR_ATOMIC
423performs multiple individually atomic operations.)
424.Pp
425The
426.Fn BIT_OR2
427macro computes
428.Fa src1
429bitwise or
430.Fa src2
431and assigns the result to
432.Fa dst .
433(It is the
434.Nm
435equivalent of the scalar:
436.Fa dst
437=
438.Fa src1
439|
440.Fa src2 . )
441.Pp
442The
443.Fn BIT_AND
444macro clears bits absent from
445.Fa src
446from
447.Fa dst .
448(It is the
449.Nm
450equivalent of the scalar:
451.Fa dst
452&=
453.Fa src . )
454.Fn BIT_AND_ATOMIC
455is similar, with the same atomic semantics as
456.Fn BIT_OR_ATOMIC .
457.Pp
458The
459.Fn BIT_AND2
460macro computes
461.Fa src1
462bitwise and
463.Fa src2
464and assigns the result to
465.Fa dst .
466(It is the
467.Nm
468equivalent of the scalar:
469.Fa dst
470=
471.Fa src1
472&
473.Fa src2 . )
474.Pp
475The
476.Fn BIT_ANDNOT
477macro clears bits set in
478.Fa src
479from
480.Fa dst .
481(It is the
482.Nm
483equivalent of the scalar:
484.Fa dst
485&=
486.Fa ~ src . )
487.Pp
488The
489.Fn BIT_ANDNOT2
490macro computes
491.Fa src1
492bitwise and not
493.Fa src2
494and assigns the result to
495.Fa dst .
496(It is the
497.Nm
498equivalent of the scalar:
499.Fa dst
500=
501.Fa src1
502& ~
503.Fa src2 . )
504.Pp
505The
506.Fn BIT_XOR
507macro toggles bits set in
508.Fa src
509in
510.Fa dst .
511(It is the
512.Nm
513equivalent of the scalar:
514.Fa dst
515^=
516.Fa src . )
517.Pp
518The
519.Fn BIT_XOR2
520macro computes
521.Fa src1
522bitwise exclusive or
523.Fa src2
524and assigns the result to
525.Fa dst .
526(It is the
527.Nm
528equivalent of the scalar:
529.Fa dst
530=
531.Fa src1
532^
533.Fa src2 . )
534.Sh BITSET_T_INITIALIZER EXAMPLE
535.Bd -literal
536BITSET_DEFINE(_myset, MYSETSIZE);
537
538struct _myset myset;
539
540/* Initialize myset to filled (all bits set) */
541myset = BITSET_T_INITIALIZER(BITSET_FSET(__bitset_words(MYSETSIZE)));
542
543/* Initialize myset to only the lowest bit set */
544myset = BITSET_T_INITIALIZER(0x1);
545.Ed
546.Sh SEE ALSO
547.Xr bitstring 3 ,
548.Xr cpuset 9
549.Sh HISTORY
550The
551.Nm
552macros first appeared in
553.Fx 10.0
554in January 2014.
555They were MFCed to
556.Fx 9.3 ,
557released in July 2014.
558.Pp
559This manual page first appeared in
560.Fx 11.0 .
561.Sh AUTHORS
562.An -nosplit
563The
564.Nm
565macros were generalized and pulled out of
566.In sys/cpuset.h
567as
568.In sys/_bitset.h
569and
570.In sys/bitset.h
571by
572.An Attilio Rao Aq Mt attilio@FreeBSD.org .
573This manual page was written by
574.An Conrad Meyer Aq Mt cem@FreeBSD.org .
575.Sh CAVEATS
576The
577.Fa SETSIZE
578argument to all of these macros must match the value given to
579.Fn BITSET_DEFINE .
580.Pp
581Unlike every other reference to individual set members, which are zero-indexed,
582.Fn BIT_FFS ,
583.Fn BIT_FFS_AT
584and
585.Fn BIT_FLS
586return a one-indexed result (or zero if the set is empty).
587