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