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 . 360.Pp 361The 362.Fn BIT_COUNT 363macro returns the total number of set bits in 364.Fa bitset . 365.Pp 366The 367.Fn BIT_SUBSET 368macro returns 369.Dv true 370if 371.Fa needle 372is a subset of 373.Fa haystack . 374.Pp 375The 376.Fn BIT_OVERLAP 377macro returns 378.Dv true 379if 380.Fa bitset1 381and 382.Fa bitset2 383have any common bits. 384(That is, if 385.Fa bitset1 386AND 387.Fa bitset2 388is not the empty set.) 389.Pp 390The 391.Fn BIT_CMP 392macro returns 393.Dv true 394if 395.Fa bitset1 396is NOT equal to 397.Fa bitset2 . 398.Pp 399The 400.Fn BIT_OR 401macro sets bits present in 402.Fa src 403in 404.Fa dst . 405(It is the 406.Nm 407equivalent of the scalar: 408.Fa dst 409|= 410.Fa src . ) 411.Fn BIT_OR_ATOMIC 412is similar, but sets bits in the component machine words in 413.Fa dst 414atomically. 415(That is, if 416.Fa dst 417is composed of multiple machine words, 418.Fn BIT_OR_ATOMIC 419performs multiple individually atomic operations.) 420.Pp 421The 422.Fn BIT_OR2 423macro computes 424.Fa src1 425bitwise or 426.Fa src2 427and assigns the result to 428.Fa dst . 429(It is the 430.Nm 431equivalent of the scalar: 432.Fa dst 433= 434.Fa src1 435| 436.Fa src2 . ) 437.Pp 438The 439.Fn BIT_AND 440macro clears bits absent from 441.Fa src 442from 443.Fa dst . 444(It is the 445.Nm 446equivalent of the scalar: 447.Fa dst 448&= 449.Fa src . ) 450.Fn BIT_AND_ATOMIC 451is similar, with the same atomic semantics as 452.Fn BIT_OR_ATOMIC . 453.Pp 454The 455.Fn BIT_AND2 456macro computes 457.Fa src1 458bitwise and 459.Fa src2 460and assigns the result to 461.Fa dst . 462(It is the 463.Nm 464equivalent of the scalar: 465.Fa dst 466= 467.Fa src1 468& 469.Fa src2 . ) 470.Pp 471The 472.Fn BIT_ANDNOT 473macro clears bits set in 474.Fa src 475from 476.Fa dst . 477(It is the 478.Nm 479equivalent of the scalar: 480.Fa dst 481&= 482.Fa ~ src . ) 483.Pp 484The 485.Fn BIT_ANDNOT2 486macro computes 487.Fa src1 488bitwise and not 489.Fa src2 490and assigns the result to 491.Fa dst . 492(It is the 493.Nm 494equivalent of the scalar: 495.Fa dst 496= 497.Fa src1 498& ~ 499.Fa src2 . ) 500.Pp 501The 502.Fn BIT_XOR 503macro toggles bits set in 504.Fa src 505in 506.Fa dst . 507(It is the 508.Nm 509equivalent of the scalar: 510.Fa dst 511^= 512.Fa src . ) 513.Pp 514The 515.Fn BIT_XOR2 516macro computes 517.Fa src1 518bitwise exclusive or 519.Fa src2 520and assigns the result to 521.Fa dst . 522(It is the 523.Nm 524equivalent of the scalar: 525.Fa dst 526= 527.Fa src1 528^ 529.Fa src2 . ) 530.Sh BITSET_T_INITIALIZER EXAMPLE 531.Bd -literal 532BITSET_DEFINE(_myset, MYSETSIZE); 533 534struct _myset myset; 535 536/* Initialize myset to filled (all bits set) */ 537myset = BITSET_T_INITIALIZER(BITSET_FSET(__bitset_words(MYSETSIZE))); 538 539/* Initialize myset to only the lowest bit set */ 540myset = BITSET_T_INITIALIZER(0x1); 541.Ed 542.Sh SEE ALSO 543.Xr bitstring 3 , 544.Xr cpuset 9 545.Sh HISTORY 546The 547.Nm 548macros first appeared in 549.Fx 10.0 550in January 2014. 551They were MFCed to 552.Fx 9.3 , 553released in July 2014. 554.Pp 555This manual page first appeared in 556.Fx 11.0 . 557.Sh AUTHORS 558.An -nosplit 559The 560.Nm 561macros were generalized and pulled out of 562.In sys/cpuset.h 563as 564.In sys/_bitset.h 565and 566.In sys/bitset.h 567by 568.An Attilio Rao Aq Mt attilio@FreeBSD.org . 569This manual page was written by 570.An Conrad Meyer Aq Mt cem@FreeBSD.org . 571.Sh CAVEATS 572The 573.Fa SETSIZE 574argument to all of these macros must match the value given to 575.Fn BITSET_DEFINE . 576.Pp 577Unlike every other reference to individual set members, which are zero-indexed, 578.Fn BIT_FFS , 579.Fn BIT_FFS_AT 580and 581.Fn BIT_FLS 582return a one-indexed result (or zero if the set is empty). 583