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