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