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