share/man/man9/bitset.9

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