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