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