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_ISSET 260macro returns 261.Dv true 262if the bit 263.Fa bit 264in the bitset pointed to by 265.Fa bitset 266is set. 267.Pp 268The 269.Fn BIT_SET 270macro sets bit 271.Fa bit 272in the bitset pointed to by 273.Fa bitset . 274The 275.Fn BIT_SET_ATOMIC 276macro is identical, but the bit is set atomically. 277The 278.Fn BIT_SET_ATOMIC_ACQ 279macro sets the bit with acquire semantics. 280The 281.Fn BIT_TEST_SET_ATOMIC 282macro atomically sets the bit and returns whether it was set. 283.Pp 284The 285.Fn BIT_ZERO 286macro clears all bits in 287.Fa bitset . 288.Pp 289The 290.Fn BIT_FILL 291macro sets all bits in 292.Fa bitset . 293.Pp 294The 295.Fn BIT_SETOF 296macro clears all bits in 297.Fa bitset 298before setting only bit 299.Fa bit . 300.Pp 301The 302.Fn BIT_EMPTY 303macro returns 304.Dv true 305if 306.Fa bitset 307is empty. 308.Pp 309The 310.Fn BIT_ISFULLSET 311macro returns 312.Dv true 313if 314.Fa bitset 315is full (all bits set). 316.Pp 317The 318.Fn BIT_FFS 319macro returns the 1-index of the first (lowest) set bit in 320.Fa bitset , 321or zero if 322.Fa bitset 323is empty. 324Like with 325.Xr ffs 3 , 326to use the non-zero result of 327.Fn BIT_FFS 328as a 329.Fa bit 330index parameter to any other 331.Nm 332macro, you must subtract one from the result. 333.Pp 334The 335.Fn BIT_FFS_AT 336macro returns the 1-index of the first (lowest) set bit in 337.Fa bitset , 338which is greater than the given 1-indexed 339.Fa start , 340or zero if no bits in 341.Fa bitset 342greater than 343.Fa start 344are set. 345.Pp 346The 347.Fn BIT_FLS 348macro returns the 1-index of the last (highest) set bit in 349.Fa bitset , 350or zero if 351.Fa bitset 352is empty. 353Like with 354.Xr fls 3 , 355to use the non-zero result of 356.Fn BIT_FLS 357as a 358.Fa bit 359index parameter to any other 360.Nm 361macro, you must subtract one from the result. 362.Pp 363The 364.Fn BIT_FOREACH_ISSET 365macro can be used to iterate over all set bits in 366.Fa bitset . 367The index variable 368.Fa bit 369must have been declared with type 370.Ft int , 371and upon each iteration 372.Fa bit 373is set to the index of successive set bits. 374The value of 375.Fa bit 376after the loop terminates is undefined. 377Similarly, 378.Fn BIT_FOREACH_ISCLR 379iterates over all clear bits in 380.Fa bitset . 381In the loop body, the currently indexed bit may be set or cleared. 382However, setting or clearing bits other than the currently indexed 383bit does not guarantee that they will or will not be returned in 384subsequent iterations of the same loop. 385.Pp 386The 387.Fn BIT_COUNT 388macro returns the total number of set bits in 389.Fa bitset . 390.Pp 391The 392.Fn BIT_SUBSET 393macro returns 394.Dv true 395if 396.Fa needle 397is a subset of 398.Fa haystack . 399.Pp 400The 401.Fn BIT_OVERLAP 402macro returns 403.Dv true 404if 405.Fa bitset1 406and 407.Fa bitset2 408have any common bits. 409(That is, if 410.Fa bitset1 411AND 412.Fa bitset2 413is not the empty set.) 414.Pp 415The 416.Fn BIT_CMP 417macro returns 418.Dv true 419if 420.Fa bitset1 421is NOT equal to 422.Fa bitset2 . 423.Pp 424The 425.Fn BIT_OR 426macro sets bits present in 427.Fa src 428in 429.Fa dst . 430(It is the 431.Nm 432equivalent of the scalar: 433.Fa dst 434|= 435.Fa src . ) 436.Fn BIT_OR_ATOMIC 437is similar, but sets bits in the component machine words in 438.Fa dst 439atomically. 440(That is, if 441.Fa dst 442is composed of multiple machine words, 443.Fn BIT_OR_ATOMIC 444performs multiple individually atomic operations.) 445.Pp 446The 447.Fn BIT_OR2 448macro computes 449.Fa src1 450bitwise or 451.Fa src2 452and assigns the result to 453.Fa dst . 454(It is the 455.Nm 456equivalent of the scalar: 457.Fa dst 458= 459.Fa src1 460| 461.Fa src2 . ) 462.Pp 463The 464.Fn BIT_AND 465macro clears bits absent from 466.Fa src 467from 468.Fa dst . 469(It is the 470.Nm 471equivalent of the scalar: 472.Fa dst 473&= 474.Fa src . ) 475.Fn BIT_AND_ATOMIC 476is similar, with the same atomic semantics as 477.Fn BIT_OR_ATOMIC . 478.Pp 479The 480.Fn BIT_AND2 481macro computes 482.Fa src1 483bitwise and 484.Fa src2 485and assigns the result to 486.Fa dst . 487(It is the 488.Nm 489equivalent of the scalar: 490.Fa dst 491= 492.Fa src1 493& 494.Fa src2 . ) 495.Pp 496The 497.Fn BIT_ANDNOT 498macro clears bits set in 499.Fa src 500from 501.Fa dst . 502(It is the 503.Nm 504equivalent of the scalar: 505.Fa dst 506&= 507.Fa ~ src . ) 508.Pp 509The 510.Fn BIT_ANDNOT2 511macro computes 512.Fa src1 513bitwise and not 514.Fa src2 515and assigns the result to 516.Fa dst . 517(It is the 518.Nm 519equivalent of the scalar: 520.Fa dst 521= 522.Fa src1 523& ~ 524.Fa src2 . ) 525.Pp 526The 527.Fn BIT_XOR 528macro toggles bits set in 529.Fa src 530in 531.Fa dst . 532(It is the 533.Nm 534equivalent of the scalar: 535.Fa dst 536^= 537.Fa src . ) 538.Pp 539The 540.Fn BIT_XOR2 541macro computes 542.Fa src1 543bitwise exclusive or 544.Fa src2 545and assigns the result to 546.Fa dst . 547(It is the 548.Nm 549equivalent of the scalar: 550.Fa dst 551= 552.Fa src1 553^ 554.Fa src2 . ) 555.Sh BITSET_T_INITIALIZER EXAMPLE 556.Bd -literal 557BITSET_DEFINE(_myset, MYSETSIZE); 558 559struct _myset myset; 560 561/* Initialize myset to filled (all bits set) */ 562myset = BITSET_T_INITIALIZER(BITSET_FSET(__bitset_words(MYSETSIZE))); 563 564/* Initialize myset to only the lowest bit set */ 565myset = BITSET_T_INITIALIZER(0x1); 566.Ed 567.Sh SEE ALSO 568.Xr bitstring 3 , 569.Xr cpuset 9 570.Sh HISTORY 571The 572.Nm 573macros first appeared in 574.Fx 10.0 575in January 2014. 576They were MFCed to 577.Fx 9.3 , 578released in July 2014. 579.Pp 580This manual page first appeared in 581.Fx 11.0 . 582.Sh AUTHORS 583.An -nosplit 584The 585.Nm 586macros were generalized and pulled out of 587.In sys/cpuset.h 588as 589.In sys/_bitset.h 590and 591.In sys/bitset.h 592by 593.An Attilio Rao Aq Mt attilio@FreeBSD.org . 594This manual page was written by 595.An Conrad Meyer Aq Mt cem@FreeBSD.org . 596.Sh CAVEATS 597The 598.Fa SETSIZE 599argument to all of these macros must match the value given to 600.Fn BITSET_DEFINE . 601.Pp 602Unlike every other reference to individual set members, which are zero-indexed, 603.Fn BIT_FFS , 604.Fn BIT_FFS_AT 605and 606.Fn BIT_FLS 607return a one-indexed result (or zero if the set is empty). 608.Pp 609In order to use the macros defined in 610.In sys/bitset.h 611and 612.In sys/_bitset.h 613in userland programs, 614.Dv _WANT_FREEBSD_BITSET 615has to be defined before including the header files. 616This requirements exists to prevent a name space pollution due to macros defined in 617.Nm 618in programs that include 619.In sys/cpuset.h 620or 621.In sched.h . 622