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 .Pp
 361 The
 362 .Fn BIT_COUNT
 363 macro returns the total number of set bits in
 364 .Fa bitset .
 365 .Pp
 366 The
 367 .Fn BIT_SUBSET
 368 macro returns
 369 .Dv true
 370 if
 371 .Fa needle
 372 is a subset of
 373 .Fa haystack .
 374 .Pp
 375 The
 376 .Fn BIT_OVERLAP
 377 macro returns
 378 .Dv true
 379 if
 380 .Fa bitset1
 381 and
 382 .Fa bitset2
 383 have any common bits.
 384 (That is, if
 385 .Fa bitset1
 386 AND
 387 .Fa bitset2
 388 is not the empty set.)
 389 .Pp
 390 The
 391 .Fn BIT_CMP
 392 macro returns
 393 .Dv true
 394 if
 395 .Fa bitset1
 396 is NOT equal to
 397 .Fa bitset2 .
 398 .Pp
 399 The
 400 .Fn BIT_OR
 401 macro sets bits present in
 402 .Fa src
 403 in
 404 .Fa dst .
 405 (It is the
 406 .Nm
 407 equivalent of the scalar:
 408 .Fa dst
 409 |=
 410 .Fa src . )
 411 .Fn BIT_OR_ATOMIC
 412 is similar, but sets bits in the component machine words in
 413 .Fa dst
 414 atomically.
 415 (That is, if
 416 .Fa dst
 417 is composed of multiple machine words,
 418 .Fn BIT_OR_ATOMIC
 419 performs multiple individually atomic operations.)
 420 .Pp
 421 The
 422 .Fn BIT_OR2
 423 macro computes
 424 .Fa src1
 425 bitwise or
 426 .Fa src2
 427 and assigns the result to
 428 .Fa dst .
 429 (It is the
 430 .Nm
 431 equivalent of the scalar:
 432 .Fa dst
 433 =
 434 .Fa src1
 435 |
 436 .Fa src2 . )
 437 .Pp
 438 The
 439 .Fn BIT_AND
 440 macro clears bits absent from
 441 .Fa src
 442 from
 443 .Fa dst .
 444 (It is the
 445 .Nm
 446 equivalent of the scalar:
 447 .Fa dst
 448 &=
 449 .Fa src . )
 450 .Fn BIT_AND_ATOMIC
 451 is similar, with the same atomic semantics as
 452 .Fn BIT_OR_ATOMIC .
 453 .Pp
 454 The
 455 .Fn BIT_AND2
 456 macro computes
 457 .Fa src1
 458 bitwise and
 459 .Fa src2
 460 and assigns the result to
 461 .Fa dst .
 462 (It is the
 463 .Nm
 464 equivalent of the scalar:
 465 .Fa dst
 466 =
 467 .Fa src1
 468 &
 469 .Fa src2 . )
 470 .Pp
 471 The
 472 .Fn BIT_ANDNOT
 473 macro clears bits set in
 474 .Fa src
 475 from
 476 .Fa dst .
 477 (It is the
 478 .Nm
 479 equivalent of the scalar:
 480 .Fa dst
 481 &=
 482 .Fa ~ src . )
 483 .Pp
 484 The
 485 .Fn BIT_ANDNOT2
 486 macro computes
 487 .Fa src1
 488 bitwise and not
 489 .Fa src2
 490 and assigns the result to
 491 .Fa dst .
 492 (It is the
 493 .Nm
 494 equivalent of the scalar:
 495 .Fa dst
 496 =
 497 .Fa src1
 498 & ~
 499 .Fa src2 . )
 500 .Pp
 501 The
 502 .Fn BIT_XOR
 503 macro toggles bits set in
 504 .Fa src
 505 in
 506 .Fa dst .
 507 (It is the
 508 .Nm
 509 equivalent of the scalar:
 510 .Fa dst
 511 ^=
 512 .Fa src . )
 513 .Pp
 514 The
 515 .Fn BIT_XOR2
 516 macro computes
 517 .Fa src1
 518 bitwise exclusive or
 519 .Fa src2
 520 and assigns the result to
 521 .Fa dst .
 522 (It is the
 523 .Nm
 524 equivalent of the scalar:
 525 .Fa dst
 526 =
 527 .Fa src1
 528 ^
 529 .Fa src2 . )
 530 .Sh BITSET_T_INITIALIZER EXAMPLE
 531 .Bd -literal
 532 BITSET_DEFINE(_myset, MYSETSIZE);
 533
 534 struct _myset myset;
 535
 536 /* Initialize myset to filled (all bits set) */
 537 myset = BITSET_T_INITIALIZER(BITSET_FSET(__bitset_words(MYSETSIZE)));
 538
 539 /* Initialize myset to only the lowest bit set */
 540 myset = BITSET_T_INITIALIZER(0x1);
 541 .Ed
 542 .Sh SEE ALSO
 543 .Xr bitstring 3 ,
 544 .Xr cpuset 9
 545 .Sh HISTORY
 546 The
 547 .Nm
 548 macros first appeared in
 549 .Fx 10.0
 550 in January 2014.
 551 They were MFCed to
 552 .Fx 9.3 ,
 553 released in July 2014.
 554 .Pp
 555 This manual page first appeared in
 556 .Fx 11.0 .
 557 .Sh AUTHORS
 558 .An -nosplit
 559 The
 560 .Nm
 561 macros were generalized and pulled out of
 562 .In sys/cpuset.h
 563 as
 564 .In sys/_bitset.h
 565 and
 566 .In sys/bitset.h
 567 by
 568 .An Attilio Rao Aq Mt attilio@FreeBSD.org .
 569 This manual page was written by
 570 .An Conrad Meyer Aq Mt cem@FreeBSD.org .
 571 .Sh CAVEATS
 572 The
 573 .Fa SETSIZE
 574 argument to all of these macros must match the value given to
 575 .Fn BITSET_DEFINE .
 576 .Pp
 577 Unlike every other reference to individual set members, which are zero-indexed,
 578 .Fn BIT_FFS ,
 579 .Fn BIT_FFS_AT
 580 and
 581 .Fn BIT_FLS
 582 return a one-indexed result (or zero if the set is empty).