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