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