1.\" Copyright (c) 1989, 1991, 1993 2.\" The Regents of the University of California. All rights reserved. 3.\" 4.\" This code is derived from software contributed to Berkeley by 5.\" Paul Vixie. 6.\" Redistribution and use in source and binary forms, with or without 7.\" modification, are permitted provided that the following conditions 8.\" are met: 9.\" 1. Redistributions of source code must retain the above copyright 10.\" notice, this list of conditions and the following disclaimer. 11.\" 2. Redistributions in binary form must reproduce the above copyright 12.\" notice, this list of conditions and the following disclaimer in the 13.\" documentation and/or other materials provided with the distribution. 14.\" 3. Neither the name of the University nor the names of its contributors 15.\" may be used to endorse or promote products derived from this software 16.\" without specific prior written permission. 17.\" 18.\" THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND 19.\" ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 20.\" IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 21.\" ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE 22.\" FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 23.\" DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 24.\" OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 25.\" HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 26.\" LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 27.\" OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 28.\" SUCH DAMAGE. 29.\" 30.\" Copyright (c) 2014,2016 Spectra Logic Corporation 31.\" All rights reserved. 32.\" 33.\" Redistribution and use in source and binary forms, with or without 34.\" modification, are permitted provided that the following conditions 35.\" are met: 36.\" 1. Redistributions of source code must retain the above copyright 37.\" notice, this list of conditions, and the following disclaimer, 38.\" without modification. 39.\" 2. Redistributions in binary form must reproduce at minimum a disclaimer 40.\" substantially similar to the "NO WARRANTY" disclaimer below 41.\" ("Disclaimer") and any redistribution must be conditioned upon 42.\" including a substantially similar Disclaimer requirement for further 43.\" binary redistribution. 44.\" 45.\" NO WARRANTY 46.\" THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 47.\" "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 48.\" LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTIBILITY AND FITNESS FOR 49.\" A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 50.\" HOLDERS OR CONTRIBUTORS BE LIABLE FOR SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 51.\" DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 52.\" OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 53.\" HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, 54.\" STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING 55.\" IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE 56.\" POSSIBILITY OF SUCH DAMAGES. 57.\" 58.Dd November 21, 2023 59.Dt BITSTRING 3 60.Os 61.Sh NAME 62.Nm bit_alloc , 63.Nm bit_clear , 64.Nm bit_count , 65.Nm bit_decl , 66.Nm bit_ffc , 67.Nm bit_ffs , 68.Nm bit_ff_at , 69.Nm bit_ffc_at , 70.Nm bit_ffs_at , 71.Nm bit_ffc_area , 72.Nm bit_ffs_area , 73.Nm bit_ff_area_at , 74.Nm bit_ffc_area_at , 75.Nm bit_ffs_area_at , 76.Nm bit_nclear , 77.Nm bit_nset , 78.Nm bit_ntest , 79.Nm bit_set , 80.Nm bit_test , 81.Nm bitstr_size 82.Nd bit-string manipulation functions and macros 83.Sh SYNOPSIS 84.In bitstring.h 85.Ft bitstr_t * 86.Fn bit_alloc "size_t nbits" 87.Ft void 88.Fn bit_decl "bitstr_t *name" "size_t nbits" 89.Ft void 90.Fn bit_clear "bitstr_t *name" "size_t bit" 91.Ft void 92.Fn bit_count "bitstr_t *name" "size_t count" "size_t nbits" "ssize_t *value" 93.Ft void 94.Fn bit_ffc "bitstr_t *name" "size_t nbits" "ssize_t *value" 95.Ft void 96.Fn bit_ffs "bitstr_t *name" "size_t nbits" "ssize_t *value" 97.Ft void 98.Fn bit_ffc_at "bitstr_t *name" "size_t start" "size_t nbits" "ssize_t *value" 99.Ft void 100.Fn bit_ffs_at "bitstr_t *name" "size_t start" "size_t nbits" "ssize_t *value" 101.Ft void 102.Fn bit_ff_at "bitstr_t *name" "size_t start" "size_t nbits" "int match" "ssize_t *value" 103.Ft void 104.Fn bit_ffc_area "bitstr_t *name" "size_t nbits" "size_t size" "ssize_t *value" 105.Ft void 106.Fn bit_ffs_area "bitstr_t *name" "size_t nbits" "size_t size" "ssize_t *value" 107.Ft void 108.Fn bit_ffc_area_at "bitstr_t *name" "size_t start" "size_t nbits" "size_t size" "ssize_t *value" 109.Ft void 110.Fn bit_ffs_area_at "bitstr_t *name" "size_t start" "size_t nbits" "size_t size" "ssize_t *value" 111.Ft void 112.Fn bit_ff_area_at "bitstr_t *name" "size_t start" "size_t nbits" "size_t size" "int match" "ssize_t *value" 113.Fn bit_foreach "bitstr_t *name" "size_t nbits" "size_t var" 114.Fn bit_foreach_at "bitstr_t *name" "size_t start" "size_t nbits" "size_t var" 115.Fn bit_foreach_unset "bitstr_t *name" "size_t nbits" "size_t var" 116.Fn bit_foreach_unset_at "bitstr_t *name" "size_t start" "size_t nbits" "size_t var" 117.Ft void 118.Fn bit_nclear "bitstr_t *name" "size_t start" "size_t stop" 119.Ft void 120.Fn bit_nset "bitstr_t *name" "size_t start" "size_t stop" 121.Ft int 122.Fn bit_ntest "bitstr_t *name" "size_t start" "size_t stop" "int match" 123.Ft void 124.Fn bit_set "bitstr_t *name" "size_t bit" 125.Ft int 126.Fn bitstr_size "size_t nbits" 127.Ft int 128.Fn bit_test "bitstr_t *name" "size_t bit" 129.Sh DESCRIPTION 130These macros operate on strings of bits. 131.Pp 132The function 133.Fn bit_alloc 134returns a pointer of type 135.Dq Fa "bitstr_t *" 136to sufficient space to store 137.Fa nbits 138bits, or 139.Dv NULL 140if no space is available. 141If successful, the returned bit string is initialized with all bits cleared. 142.Pp 143The macro 144.Fn bit_decl 145declares a bit string with sufficient space to store 146.Fa nbits 147bits. 148.Fn bit_decl 149may be used to include statically sized bit strings in structure 150definitions or to create bit strings on the stack. 151Users of this macro are responsible for initialization of the bit string, 152typically via a global initialization of the containing struct or use of the 153.Fn bit_nset 154or 155.Fn bin_nclear 156functions. 157.Pp 158The macro 159.Fn bitstr_size 160returns the number of bytes necessary to store 161.Fa nbits 162bits. 163This is useful for copying bit strings. 164.Pp 165The functions 166.Fn bit_clear 167and 168.Fn bit_set 169clear or set the zero-based numbered bit 170.Fa bit , 171in the bit string 172.Ar name . 173.Pp 174The 175.Fn bit_nset 176and 177.Fn bit_nclear 178functions 179set or clear the zero-based numbered bits from 180.Fa start 181through 182.Fa stop 183in the bit string 184.Ar name . 185.Pp 186The 187.Fn bit_test 188function 189evaluates to non-zero if the zero-based numbered bit 190.Fa bit 191of bit string 192.Fa name 193is set, and zero otherwise. 194.Pp 195The 196.Fn bit_ntest 197function 198evaluates to non-zero if the zero-based numbered bits from 199.Fa start 200through 201.Fa stop 202in the bit string 203.Ar name 204all have the value 205.Ar match . 206.Pp 207The function 208.Fn bit_ffc 209stores in the location referenced by 210.Fa value 211the zero-based number of the first bit not set in the array of 212.Fa nbits 213bits referenced by 214.Fa name . 215If all bits are set, the location referenced by 216.Fa value 217is set to \-1. 218.Pp 219The 220.Fn bit_ffs 221function 222stores in the location referenced by 223.Fa value 224the zero-based number of the first bit set in the array of 225.Fa nbits 226bits referenced by 227.Fa name . 228If no bits are set, the location referenced by 229.Fa value 230is set to \-1. 231.Pp 232The function 233.Fn bit_ffc_at 234stores in the location referenced by 235.Fa value 236the zero-based number of the first bit not set in the array of 237.Fa nbits 238bits referenced by 239.Fa name , 240at or after the zero-based bit index 241.Fa start . 242If all bits at or after 243.Fa start 244are set, the location referenced by 245.Fa value 246is set to \-1. 247.Pp 248The 249.Fn bit_ffs_at 250function 251stores in the location referenced by 252.Fa value 253the zero-based number of the first bit set in the array of 254.Fa nbits 255bits referenced by 256.Fa name , 257at or after the zero-based bit index 258.Fa start . 259If no bits are set after 260.Fa start , 261the location referenced by 262.Fa value 263is set to \-1. 264.Pp 265The 266.Fn bit_ff_at 267function 268stores in the location referenced by 269.Fa value 270the zero-based number of the first bit in the array of 271.Fa nbits 272bits referenced by 273.Fa name , 274at or after the zero-based bit index 275.Fa start 276that has value 277.Fa match . 278If no bits after 279.Fa start 280match that value, the location referenced by 281.Fa value 282is set to \-1. 283.Pp 284The 285.Fn bit_ffc_area 286function stores in the location referenced by 287.Fa value 288the zero-based number of the first bit beginning a sequence of unset bits of 289at least 290.Fa size 291unset bits in the array of 292.Fa nbits 293bits referenced by 294.Fa name . 295If no sequence of contiguous unset bits of the specified 296.Fa size 297can be found, the location referenced by 298.Fa value 299is set to \-1. 300.Pp 301The 302.Fn bit_ffs_area 303function stores in the location referenced by 304.Fa value 305the zero-based number of the first bit beginning a sequence of set bits of 306at least 307.Fa size 308set bits in the array of 309.Fa nbits 310bits referenced by 311.Fa name . 312If no sequence of contiguous set bits of the specified 313.Fa size 314can be found, the location referenced by 315.Fa value 316is set to \-1. 317.Pp 318The 319.Fn bit_ffc_area_at 320function stores in the location referenced by 321.Fa value 322the zero-based number of the first bit beginning a sequence of unset bits of 323at least 324.Fa size 325unset bits in the array of 326.Fa nbits 327bits referenced by 328.Fa name , 329at or after the zero-based bit index 330.Fa start . 331If no sequence of contiguous unset bits of the specified 332.Fa size 333can be found at or after 334.Fa start , 335the location referenced by 336.Fa value 337is set to \-1. 338.Pp 339The 340.Fn bit_ffs_area_at 341function stores in the location referenced by 342.Fa value 343the zero-based number of the first bit beginning a sequence of set bits of 344at least 345.Fa size 346set bits in the array of 347.Fa nbits 348bits referenced by 349.Fa name , 350at or after the zero-based bit index 351.Fa start . 352If no sequence of contiguous set bits of the specified 353.Fa size 354can be found at or after 355.Fa start , 356the location referenced by 357.Fa value 358is set to \-1. 359.Pp 360The 361.Fn bit_ff_area_at 362function stores in the location referenced by 363.Fa value 364the zero-based number of the first bit beginning a sequence of bits of 365at least 366.Fa size 367bits in the array of 368.Fa nbits 369bits referenced by 370.Fa name , 371at or after the zero-based bit index 372.Fa start 373in which all bits have the value 374.Fa match . 375If no sequence of contiguous such bits of the specified 376.Fa size 377can be found at or after 378.Fa start , 379the location referenced by 380.Fa value 381is set to \-1. 382.Pp 383The 384.Fn bit_count 385function stores in the location referenced by 386.Fa value 387the number of bits set in the array of 388.Fa nbits 389bits referenced by 390.Fa name , 391at or after the zero-based bit index 392.Fa start . 393.Pp 394The macro 395.Fn bit_foreach 396traverses all set bits in the array of 397.Fa nbits 398referenced by 399.Fa name 400in the forward direction, assigning each location in turn to 401.Fa var . 402.Pp 403The macro 404.Fn bit_foreach_at 405traverses all set bits in the array of 406.Fa nbits 407referenced by 408.Fa name 409in the forward direction at or after the zero-based bit index 410.Fa start , 411assigning each location in turn to 412.Fa var . 413.Pp 414The macro 415.Fn bit_foreach_unset 416traverses all unset bits in the array of 417.Fa nbits 418referenced by 419.Fa name 420in the forward direction, assigning each location in turn to 421.Fa var . 422.Pp 423The macro 424.Fn bit_foreach_unset_at 425traverses all unset bits in the array of 426.Fa nbits 427referenced by 428.Fa name 429in the forward direction at or after the zero-based bit index 430.Fa start , 431assigning each location in turn to 432.Fa var . 433.Pp 434The arguments in bit string macros are evaluated only once and may safely 435have side effects. 436.Sh EXAMPLES 437.Bd -literal -offset indent 438#include <limits.h> 439#include <bitstring.h> 440 441\&... 442#define LPR_BUSY_BIT 0 443#define LPR_FORMAT_BIT 1 444#define LPR_DOWNLOAD_BIT 2 445\&... 446#define LPR_AVAILABLE_BIT 9 447#define LPR_MAX_BITS 10 448 449make_lpr_available() 450{ 451 bitstr_t bit_decl(bitlist, LPR_MAX_BITS); 452 ... 453 bit_nclear(bitlist, 0, LPR_MAX_BITS - 1); 454 ... 455 if (!bit_test(bitlist, LPR_BUSY_BIT)) { 456 bit_clear(bitlist, LPR_FORMAT_BIT); 457 bit_clear(bitlist, LPR_DOWNLOAD_BIT); 458 bit_set(bitlist, LPR_AVAILABLE_BIT); 459 } 460} 461.Ed 462.Sh SEE ALSO 463.Xr malloc 3 , 464.Xr bitset 9 465.Sh HISTORY 466The 467.Nm bitstring 468functions first appeared in 469.Bx 4.4 . 470