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