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