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