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