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