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.Fd #define _WANT_FREEBSD_BITSET 168.Sh DESCRIPTION 169The 170.Nm 171family of macros provide a flexible and efficient bitset implementation if the 172maximum size of the set is known at compilation. 173Throughout this manual page, the name 174.Fa SETSIZE 175refers to the size of the bitset in bits. 176Individual bits in bitsets are referenced with indices zero through 177.Fa SETSIZE - 1 . 178One example use of 179.In sys/bitset.h 180is 181.In sys/cpuset.h . 182.Pp 183These macros are meant to be used in the kernel and are visible if 184.Dv _KERNEL is defined when 185.In sys/_bitset.h 186or 187.In sys/bitset.h 188are included in a program. 189Userland programs must define 190.Dv _WANT_FREEBSD_BITSET 191before including these files to make the macros visible. 192.Pp 193The 194.Fn BITSET_DEFINE 195macro defines a bitset struct 196.Fa STRUCTNAME 197with room to represent 198.Fa SETSIZE 199bits. 200.Pp 201The 202.Fn BITSET_T_INITIALIZER 203macro allows one to initialize a bitset struct with a compile time literal 204value. 205.Pp 206The 207.Fn BITSET_FSET 208macro generates a compile time literal, usable by 209.Fn BITSET_T_INITIALIZER , 210representing a full bitset (all bits set). 211For examples of 212.Fn BITSET_T_INITIALIZER 213and 214.Fn BITSET_FSET 215usage, see the 216.Sx BITSET_T_INITIALIZER EXAMPLE 217section. 218The 219.Fa N_WORDS 220parameter to 221.Fn BITSET_FSET 222should be: 223.Bd -literal -offset indent 224__bitset_words(SETSIZE) 225.Ed 226.Pp 227The 228.Fn BIT_CLR 229macro clears bit 230.Fa bit 231in the bitset pointed to by 232.Fa bitset . 233The 234.Fn BIT_CLR_ATOMIC 235macro is identical, but the bit is cleared atomically. 236The 237.Fn BIT_TEST_CLR_ATOMIC 238macro atomically clears the bit and returns whether it was set. 239.Pp 240The 241.Fn BIT_COPY 242macro copies the contents of the bitset 243.Fa from 244to the bitset 245.Fa to . 246.Fn BIT_COPY_STORE_REL 247is similar, but copies component machine words from 248.Fa from 249and writes them to 250.Fa to 251with atomic store with release semantics. 252(That is, if 253.Fa to 254is composed of multiple machine words, 255.Fn BIT_COPY_STORE_REL 256performs multiple individually atomic operations.) 257.Pp 258The 259.Fn BIT_SET 260macro sets bit 261.Fa bit 262in the bitset pointed to by 263.Fa bitset . 264The 265.Fn BIT_SET_ATOMIC 266macro is identical, but the bit is set atomically. 267The 268.Fn BIT_SET_ATOMIC_ACQ 269macro sets the bit with acquire semantics. 270The 271.Fn BIT_TEST_SET_ATOMIC 272macro atomically sets the bit and returns whether it was set. 273.Pp 274The 275.Fn BIT_ZERO 276macro clears all bits in 277.Fa bitset . 278.Pp 279The 280.Fn BIT_FILL 281macro sets all bits in 282.Fa bitset . 283.Pp 284The 285.Fn BIT_SETOF 286macro clears all bits in 287.Fa bitset 288before setting only bit 289.Fa bit . 290.Pp 291The 292.Fn BIT_EMPTY 293macro returns 294.Dv true 295if 296.Fa bitset 297is empty. 298.Pp 299The 300.Fn BIT_ISFULLSET 301macro returns 302.Dv true 303if 304.Fa bitset 305is full (all bits set). 306.Pp 307The 308.Fn BIT_FFS 309macro returns the 1-index of the first (lowest) set bit in 310.Fa bitset , 311or zero if 312.Fa bitset 313is empty. 314Like with 315.Xr ffs 3 , 316to use the non-zero result of 317.Fn BIT_FFS 318as a 319.Fa bit 320index parameter to any other 321.Nm 322macro, you must subtract one from the result. 323.Pp 324The 325.Fn BIT_FFS_AT 326macro returns the 1-index of the first (lowest) set bit in 327.Fa bitset , 328which is greater than the given 1-indexed 329.Fa start , 330or zero if no bits in 331.Fa bitset 332greater than 333.Fa start 334are set. 335.Pp 336The 337.Fn BIT_FLS 338macro returns the 1-index of the last (highest) set bit in 339.Fa bitset , 340or zero if 341.Fa bitset 342is empty. 343Like with 344.Xr fls 3 , 345to use the non-zero result of 346.Fn BIT_FLS 347as a 348.Fa bit 349index parameter to any other 350.Nm 351macro, you must subtract one from the result. 352.Pp 353The 354.Fn BIT_FOREACH_ISSET 355macro can be used to iterate over all set bits in 356.Fa bitset . 357The index variable 358.Fa bit 359must have been declared with type 360.Ft int , 361and upon each iteration 362.Fa bit 363is set to the index of successive set bits. 364The value of 365.Fa bit 366after the loop terminates is undefined. 367Similarly, 368.Fn BIT_FOREACH_ISCLR 369iterates over all clear bits in 370.Fa bitset . 371In the loop body, the currently indexed bit may be set or cleared. 372However, setting or clearing bits other than the currently indexed 373bit does not guarantee that they will or will not be returned in 374subsequent iterations of the same loop. 375.Pp 376The 377.Fn BIT_COUNT 378macro returns the total number of set bits in 379.Fa bitset . 380.Pp 381The 382.Fn BIT_SUBSET 383macro returns 384.Dv true 385if 386.Fa needle 387is a subset of 388.Fa haystack . 389.Pp 390The 391.Fn BIT_OVERLAP 392macro returns 393.Dv true 394if 395.Fa bitset1 396and 397.Fa bitset2 398have any common bits. 399(That is, if 400.Fa bitset1 401AND 402.Fa bitset2 403is not the empty set.) 404.Pp 405The 406.Fn BIT_CMP 407macro returns 408.Dv true 409if 410.Fa bitset1 411is NOT equal to 412.Fa bitset2 . 413.Pp 414The 415.Fn BIT_OR 416macro sets bits present in 417.Fa src 418in 419.Fa dst . 420(It is the 421.Nm 422equivalent of the scalar: 423.Fa dst 424|= 425.Fa src . ) 426.Fn BIT_OR_ATOMIC 427is similar, but sets bits in the component machine words in 428.Fa dst 429atomically. 430(That is, if 431.Fa dst 432is composed of multiple machine words, 433.Fn BIT_OR_ATOMIC 434performs multiple individually atomic operations.) 435.Pp 436The 437.Fn BIT_OR2 438macro computes 439.Fa src1 440bitwise or 441.Fa src2 442and assigns the result to 443.Fa dst . 444(It is the 445.Nm 446equivalent of the scalar: 447.Fa dst 448= 449.Fa src1 450| 451.Fa src2 . ) 452.Pp 453The 454.Fn BIT_AND 455macro clears bits absent from 456.Fa src 457from 458.Fa dst . 459(It is the 460.Nm 461equivalent of the scalar: 462.Fa dst 463&= 464.Fa src . ) 465.Fn BIT_AND_ATOMIC 466is similar, with the same atomic semantics as 467.Fn BIT_OR_ATOMIC . 468.Pp 469The 470.Fn BIT_AND2 471macro computes 472.Fa src1 473bitwise and 474.Fa src2 475and assigns the result to 476.Fa dst . 477(It is the 478.Nm 479equivalent of the scalar: 480.Fa dst 481= 482.Fa src1 483& 484.Fa src2 . ) 485.Pp 486The 487.Fn BIT_ANDNOT 488macro clears bits set in 489.Fa src 490from 491.Fa dst . 492(It is the 493.Nm 494equivalent of the scalar: 495.Fa dst 496&= 497.Fa ~ src . ) 498.Pp 499The 500.Fn BIT_ANDNOT2 501macro computes 502.Fa src1 503bitwise and not 504.Fa src2 505and assigns the result to 506.Fa dst . 507(It is the 508.Nm 509equivalent of the scalar: 510.Fa dst 511= 512.Fa src1 513& ~ 514.Fa src2 . ) 515.Pp 516The 517.Fn BIT_XOR 518macro toggles bits set in 519.Fa src 520in 521.Fa dst . 522(It is the 523.Nm 524equivalent of the scalar: 525.Fa dst 526^= 527.Fa src . ) 528.Pp 529The 530.Fn BIT_XOR2 531macro computes 532.Fa src1 533bitwise exclusive or 534.Fa src2 535and assigns the result to 536.Fa dst . 537(It is the 538.Nm 539equivalent of the scalar: 540.Fa dst 541= 542.Fa src1 543^ 544.Fa src2 . ) 545.Sh BITSET_T_INITIALIZER EXAMPLE 546.Bd -literal 547BITSET_DEFINE(_myset, MYSETSIZE); 548 549struct _myset myset; 550 551/* Initialize myset to filled (all bits set) */ 552myset = BITSET_T_INITIALIZER(BITSET_FSET(__bitset_words(MYSETSIZE))); 553 554/* Initialize myset to only the lowest bit set */ 555myset = BITSET_T_INITIALIZER(0x1); 556.Ed 557.Sh SEE ALSO 558.Xr bitstring 3 , 559.Xr cpuset 9 560.Sh HISTORY 561The 562.Nm 563macros first appeared in 564.Fx 10.0 565in January 2014. 566They were MFCed to 567.Fx 9.3 , 568released in July 2014. 569.Pp 570This manual page first appeared in 571.Fx 11.0 . 572.Sh AUTHORS 573.An -nosplit 574The 575.Nm 576macros were generalized and pulled out of 577.In sys/cpuset.h 578as 579.In sys/_bitset.h 580and 581.In sys/bitset.h 582by 583.An Attilio Rao Aq Mt attilio@FreeBSD.org . 584This manual page was written by 585.An Conrad Meyer Aq Mt cem@FreeBSD.org . 586.Sh CAVEATS 587The 588.Fa SETSIZE 589argument to all of these macros must match the value given to 590.Fn BITSET_DEFINE . 591.Pp 592Unlike every other reference to individual set members, which are zero-indexed, 593.Fn BIT_FFS , 594.Fn BIT_FFS_AT 595and 596.Fn BIT_FLS 597return a one-indexed result (or zero if the set is empty). 598.Pp 599In order to use the macros defined in 600.In sys/bitset.h 601and 602.In sys/_bitset.h 603in userland programs, 604.Dv _WANT_FREEBSD_BITSET 605has to be defined before including the header files. 606This requirements exists to prevent a name space pollution due to macros defined in 607.Nm 608in programs that include 609.In sys/cpuset.h 610or 611.In sched.h . 612