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 August 25, 2020 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_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_AND_ATOMIC , 64.Nm BIT_OR_ATOMIC , 65.Nm BIT_COPY_STORE_REL 66.Nd bitset manipulation macros 67.Sh SYNOPSIS 68.In sys/_bitset.h 69.In sys/bitset.h 70.\" 71.Fn BITSET_DEFINE "STRUCTNAME" "const SETSIZE" 72.Fn BITSET_T_INITIALIZER "ARRAY_CONTENTS" 73.Fn BITSET_FSET "N_WORDS" 74.\" 75.Fn BIT_CLR "const SETSIZE" "size_t bit" "struct STRUCTNAME *bitset" 76.Fn BIT_COPY "const SETSIZE" "struct STRUCTNAME *from" "struct STRUCTNAME *to" 77.Ft bool 78.Fn BIT_ISSET "const SETSIZE" "size_t bit" "struct STRUCTNAME *bitset" 79.Fn BIT_SET "const SETSIZE" "size_t bit" "struct STRUCTNAME *bitset" 80.Fn BIT_ZERO "const SETSIZE" "struct STRUCTNAME *bitset" 81.Fn BIT_FILL "const SETSIZE" "struct STRUCTNAME *bitset" 82.Fn BIT_SETOF "const SETSIZE" "size_t bit" "struct STRUCTNAME *bitset" 83.Ft bool 84.Fn BIT_EMPTY "const SETSIZE" "struct STRUCTNAME *bitset" 85.Ft bool 86.Fn BIT_ISFULLSET "const SETSIZE" "struct STRUCTNAME *bitset" 87.Ft int 88.Fn BIT_FFS "const SETSIZE" "struct STRUCTNAME *bitset" 89.Ft int 90.Fn BIT_FFS_AT "const SETSIZE" "struct STRUCTNAME *bitset" "int start" 91.Ft int 92.Fn BIT_FLS "const SETSIZE" "struct STRUCTNAME *bitset" 93.Ft int 94.Fn BIT_COUNT "const SETSIZE" "struct STRUCTNAME *bitset" 95.\" 96.Ft bool 97.Fo BIT_SUBSET 98.Fa "const SETSIZE" "struct STRUCTNAME *haystack" "struct STRUCTNAME *needle" 99.Fc 100.Ft bool 101.Fo BIT_OVERLAP 102.Fa "const SETSIZE" "struct STRUCTNAME *bitset1" "struct STRUCTNAME *bitset2" 103.Fc 104.Ft bool 105.Fo BIT_CMP 106.Fa "const SETSIZE" "struct STRUCTNAME *bitset1" "struct STRUCTNAME *bitset2" 107.Fc 108.Fn BIT_OR "const SETSIZE" "struct STRUCTNAME *dst" "struct STRUCTNAME *src" 109.Fo BIT_OR2 110.Fa "const SETSIZE" 111.Fa "struct STRUCTNAME *dst" 112.Fa "struct STRUCTNAME *src1" 113.Fa "struct STRUCTNAME *src2" 114.Fc 115.Fn BIT_AND "const SETSIZE" "struct STRUCTNAME *dst" "struct STRUCTNAME *src" 116.Fo BIT_AND2 117.Fa "const SETSIZE" 118.Fa "struct STRUCTNAME *dst" 119.Fa "struct STRUCTNAME *src1" 120.Fa "struct STRUCTNAME *src2" 121.Fc 122.Fn BIT_ANDNOT "const SETSIZE" "struct STRUCTNAME *dst" "struct STRUCTNAME *src" 123.Fo BIT_ANDNOT2 124.Fa "const SETSIZE" 125.Fa "struct STRUCTNAME *dst" 126.Fa "struct STRUCTNAME *src1" 127.Fa "struct STRUCTNAME *src2" 128.Fc 129.Fn BIT_XOR "const SETSIZE" "struct STRUCTNAME *dst" "struct STRUCTNAME *src" 130.Fo BIT_XOR2 131.Fa "const SETSIZE" 132.Fa "struct STRUCTNAME *dst" 133.Fa "struct STRUCTNAME *src1" 134.Fa "struct STRUCTNAME *src2" 135.Fc 136.\" 137.Fn BIT_CLR_ATOMIC "const SETSIZE" "size_t bit" "struct STRUCTNAME *bitset" 138.Fn BIT_SET_ATOMIC "const SETSIZE" "size_t bit" "struct STRUCTNAME *bitset" 139.Fn BIT_SET_ATOMIC_ACQ "const SETSIZE" "size_t bit" "struct STRUCTNAME *bitset" 140.\" 141.Fo BIT_AND_ATOMIC 142.Fa "const SETSIZE" "struct STRUCTNAME *dst" "struct STRUCTNAME *src" 143.Fc 144.Fo BIT_OR_ATOMIC 145.Fa "const SETSIZE" "struct STRUCTNAME *dst" "struct STRUCTNAME *src" 146.Fc 147.Fo BIT_COPY_STORE_REL 148.Fa "const SETSIZE" "struct STRUCTNAME *from" "struct STRUCTNAME *to" 149.Fc 150.Sh DESCRIPTION 151The 152.Nm 153family of macros provide a flexible and efficient bitset implementation if the 154maximum size of the set is known at compilation. 155Throughout this manual page, the name 156.Fa SETSIZE 157refers to the size of the bitset in bits. 158Individual bits in bitsets are referenced with indices zero through 159.Fa SETSIZE - 1 . 160One example use of 161.In sys/bitset.h 162is 163.In sys/cpuset.h . 164.Pp 165The 166.Fn BITSET_DEFINE 167macro defines a bitset struct 168.Fa STRUCTNAME 169with room to represent 170.Fa SETSIZE 171bits. 172.Pp 173The 174.Fn BITSET_T_INITIALIZER 175macro allows one to initialize a bitset struct with a compile time literal 176value. 177.Pp 178The 179.Fn BITSET_FSET 180macro generates a compile time literal, usable by 181.Fn BITSET_T_INITIALIZER , 182representing a full bitset (all bits set). 183For examples of 184.Fn BITSET_T_INITIALIZER 185and 186.Fn BITSET_FSET 187usage, see the 188.Sx BITSET_T_INITIALIZER EXAMPLE 189section. 190The 191.Fa N_WORDS 192parameter to 193.Fn BITSET_FSET 194should be: 195.Bd -literal -offset indent 196__bitset_words(SETSIZE) 197.Ed 198.Pp 199The 200.Fn BIT_CLR 201macro clears bit 202.Fa bit 203in the bitset pointed to by 204.Fa bitset . 205The 206.Fn BIT_CLR_ATOMIC 207macro is identical, but the bit is cleared atomically. 208.Pp 209The 210.Fn BIT_COPY 211macro copies the contents of the bitset 212.Fa from 213to the bitset 214.Fa to . 215.Fn BIT_COPY_STORE_REL 216is similar, but copies component machine words from 217.Fa from 218and writes them to 219.Fa to 220with atomic store with release semantics. 221(That is, if 222.Fa to 223is composed of multiple machine words, 224.Fn BIT_COPY_STORE_REL 225performs multiple individually atomic operations.) 226.Pp 227The 228.Fn BIT_SET 229macro sets bit 230.Fa bit 231in the bitset pointed to by 232.Fa bitset . 233The 234.Fn BIT_SET_ATOMIC 235macro is identical, but the bit is set atomically. 236The 237.Fn BIT_SET_ATOMIC_ACQ 238macro sets the bit with acquire semantics. 239.Pp 240The 241.Fn BIT_ZERO 242macro clears all bits in 243.Fa bitset . 244.Pp 245The 246.Fn BIT_FILL 247macro sets all bits in 248.Fa bitset . 249.Pp 250The 251.Fn BIT_SETOF 252macro clears all bits in 253.Fa bitset 254before setting only bit 255.Fa bit . 256.Pp 257The 258.Fn BIT_EMPTY 259macro returns 260.Dv true 261if 262.Fa bitset 263is empty. 264.Pp 265The 266.Fn BIT_ISFULLSET 267macro returns 268.Dv true 269if 270.Fa bitset 271is full (all bits set). 272.Pp 273The 274.Fn BIT_FFS 275macro returns the 1-index of the first (lowest) set bit in 276.Fa bitset , 277or zero if 278.Fa bitset 279is empty. 280Like with 281.Xr ffs 3 , 282to use the non-zero result of 283.Fn BIT_FFS 284as a 285.Fa bit 286index parameter to any other 287.Nm 288macro, you must subtract one from the result. 289.Pp 290The 291.Fn BIT_FFS_AT 292macro returns the 1-index of the first (lowest) set bit in 293.Fa bitset , 294which is greater than the given 1-indexed 295.Fa start , 296or zero if no bits in 297.Fa bitset 298greater than 299.Fa start 300are set. 301.Pp 302The 303.Fn BIT_FLS 304macro returns the 1-index of the last (highest) set bit in 305.Fa bitset , 306or zero if 307.Fa bitset 308is empty. 309Like with 310.Xr fls 3 , 311to use the non-zero result of 312.Fn BIT_FLS 313as a 314.Fa bit 315index parameter to any other 316.Nm 317macro, you must subtract one from the result. 318.Pp 319The 320.Fn BIT_COUNT 321macro returns the total number of set bits in 322.Fa bitset . 323.Pp 324The 325.Fn BIT_SUBSET 326macro returns 327.Dv true 328if 329.Fa needle 330is a subset of 331.Fa haystack . 332.Pp 333The 334.Fn BIT_OVERLAP 335macro returns 336.Dv true 337if 338.Fa bitset1 339and 340.Fa bitset2 341have any common bits. 342(That is, if 343.Fa bitset1 344AND 345.Fa bitset2 346is not the empty set.) 347.Pp 348The 349.Fn BIT_CMP 350macro returns 351.Dv true 352if 353.Fa bitset1 354is NOT equal to 355.Fa bitset2 . 356.Pp 357The 358.Fn BIT_OR 359macro sets bits present in 360.Fa src 361in 362.Fa dst . 363(It is the 364.Nm 365equivalent of the scalar: 366.Fa dst 367|= 368.Fa src . ) 369.Fn BIT_OR_ATOMIC 370is similar, but sets bits in the component machine words in 371.Fa dst 372atomically. 373(That is, if 374.Fa dst 375is composed of multiple machine words, 376.Fn BIT_OR_ATOMIC 377performs multiple individually atomic operations.) 378.Pp 379The 380.Fn BIT_OR2 381macro computes 382.Fa src1 383bitwise or 384.Fa src2 385and assigns the result to 386.Fa dst . 387(It is the 388.Nm 389equivalent of the scalar: 390.Fa dst 391= 392.Fa src1 393| 394.Fa src2 . ) 395.Pp 396The 397.Fn BIT_AND 398macro clears bits absent from 399.Fa src 400from 401.Fa dst . 402(It is the 403.Nm 404equivalent of the scalar: 405.Fa dst 406&= 407.Fa src . ) 408.Fn BIT_AND_ATOMIC 409is similar, with the same atomic semantics as 410.Fn BIT_OR_ATOMIC . 411.Pp 412The 413.Fn BIT_AND2 414macro computes 415.Fa src1 416bitwise and 417.Fa src2 418and assigns the result to 419.Fa dst . 420(It is the 421.Nm 422equivalent of the scalar: 423.Fa dst 424= 425.Fa src1 426& 427.Fa src2 . ) 428.Pp 429The 430.Fn BIT_ANDNOT 431macro clears bits set in 432.Fa src 433from 434.Fa dst . 435(It is the 436.Nm 437equivalent of the scalar: 438.Fa dst 439&= 440.Fa ~ src . ) 441.Pp 442The 443.Fn BIT_ANDNOT2 444macro computes 445.Fa src1 446bitwise and not 447.Fa src2 448and assigns the result to 449.Fa dst . 450(It is the 451.Nm 452equivalent of the scalar: 453.Fa dst 454= 455.Fa src1 456& ~ 457.Fa src2 . ) 458.Pp 459The 460.Fn BIT_XOR 461macro toggles bits set in 462.Fa src 463in 464.Fa dst . 465(It is the 466.Nm 467equivalent of the scalar: 468.Fa dst 469^= 470.Fa src . ) 471.Pp 472The 473.Fn BIT_XOR2 474macro computes 475.Fa src1 476bitwise exclusive or 477.Fa src2 478and assigns the result to 479.Fa dst . 480(It is the 481.Nm 482equivalent of the scalar: 483.Fa dst 484= 485.Fa src1 486^ 487.Fa src2 . ) 488.Sh BITSET_T_INITIALIZER EXAMPLE 489.Bd -literal 490BITSET_DEFINE(_myset, MYSETSIZE); 491 492struct _myset myset; 493 494/* Initialize myset to filled (all bits set) */ 495myset = BITSET_T_INITIALIZER(BITSET_FSET(__bitset_words(MYSETSIZE))); 496 497/* Initialize myset to only the lowest bit set */ 498myset = BITSET_T_INITIALIZER(0x1); 499.Ed 500.Sh SEE ALSO 501.Xr bitstring 3 , 502.Xr cpuset 9 503.Sh HISTORY 504The 505.Nm 506macros first appeared in 507.Fx 10.0 508in January 2014. 509They were MFCed to 510.Fx 9.3 , 511released in July 2014. 512.Pp 513This manual page first appeared in 514.Fx 11.0 . 515.Sh AUTHORS 516.An -nosplit 517The 518.Nm 519macros were generalized and pulled out of 520.In sys/cpuset.h 521as 522.In sys/_bitset.h 523and 524.In sys/bitset.h 525by 526.An Attilio Rao Aq Mt attilio@FreeBSD.org . 527This manual page was written by 528.An Conrad Meyer Aq Mt cem@FreeBSD.org . 529.Sh CAVEATS 530The 531.Fa SETSIZE 532argument to all of these macros must match the value given to 533.Fn BITSET_DEFINE . 534.Pp 535Unlike every other reference to individual set members, which are zero-indexed, 536.Fn BIT_FFS , 537.Fn BIT_FFS_AT 538and 539.Fn BIT_FLS 540return a one-indexed result (or zero if the set is empty). 541