/usr/share/doc/libbitmask-dev/libbitmask.html is in libbitmask-dev 2.0-2.
This file is owned by root:root, with mode 0o644.
The actual contents of the file can be viewed below.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 310 311 312 313 314 315 316 317 318 319 320 321 322 323 324 325 326 327 328 329 330 331 332 333 334 335 336 337 338 339 340 341 342 343 344 345 346 347 348 349 350 351 352 353 354 355 356 357 358 359 360 361 362 363 364 365 366 367 368 369 370 371 372 373 374 375 376 377 378 379 380 381 382 383 384 385 386 387 388 389 390 391 392 393 394 395 396 397 398 399 400 401 402 403 404 405 406 407 408 409 410 411 412 413 414 415 416 417 418 419 420 421 422 423 424 425 426 427 428 429 430 431 432 433 434 435 436 437 438 439 440 441 442 443 444 445 446 447 448 449 450 451 452 453 454 455 456 457 458 459 460 461 462 463 464 465 466 467 468 469 470 471 472 473 474 475 476 477 478 479 480 481 482 483 484 485 486 487 488 489 490 491 492 493 494 495 496 497 498 499 500 501 502 503 504 505 506 507 508 509 510 511 512 513 514 515 516 517 518 519 520 521 522 523 524 525 526 527 528 529 530 531 532 533 534 535 536 537 538 539 540 541 542 543 544 545 546 547 548 549 550 551 552 553 554 555 556 557 558 559 560 561 562 563 564 565 566 567 568 569 570 571 572 573 574 575 576 577 578 579 580 581 582 583 584 585 586 587 588 589 590 591 592 593 594 595 596 597 598 599 600 601 602 603 604 605 606 607 608 609 610 611 612 613 614 615 616 617 618 619 620 621 622 623 624 625 626 627 628 629 630 631 632 633 634 635 636 637 638 639 640 641 642 643 644 645 646 647 648 649 650 651 652 653 654 655 656 657 658 659 660 661 662 663 664 665 666 667 668 669 670 671 672 673 674 675 676 677 678 679 680 681 682 683 684 685 686 687 688 689 690 691 692 693 694 695 696 697 698 699 700 701 702 703 704 705 706 707 708 709 710 711 712 713 714 715 716 717 718 719 720 721 722 723 724 725 726 727 728 729 730 731 732 733 734 735 736 737 738 739 740 741 742 743 744 745 746 747 748 749 750 751 752 753 754 755 756 757 758 759 760 761 762 763 764 765 766 767 768 769 770 771 772 773 774 775 776 777 778 779 780 781 782 783 784 785 786 787 788 789 790 791 792 793 794 795 796 797 798 799 800 801 802 803 804 805 806 807 808 809 810 811 812 813 814 815 816 817 818 819 820 821 822 823 824 825 826 827 828 829 830 831 832 833 834 835 836 837 838 839 840 841 842 843 844 845 846 847 848 849 850 851 852 853 854 855 856 857 858 859 860 861 862 863 864 865 866 867 868 869 870 871 872 873 874 875 876 877 878 879 880 881 882 883 884 885 886 887 888 889 890 891 892 893 894 895 896 897 898 899 900 | <?xml version="1.0" encoding="utf-8" ?>
<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
<html xmlns="http://www.w3.org/1999/xhtml" xml:lang="en" lang="en">
<head>
<meta http-equiv="Content-Type" content="text/html; charset=utf-8" />
<meta name="generator" content="Docutils 0.3.8: http://docutils.sourceforge.net/" />
<title>Multi-word Bitmask Library</title>
</head>
<body>
<div class="document" id="multi-word-bitmask-library">
<h1 class="title">Multi-word Bitmask Library</h1>
<!-- rst3: filename: libbitmask.html -->
<p>This Bitmask library supports multi-word bitmask operations for applications
programmed in 'C'. It works in conjunction with recent Linux kernel support for
processor and memory placement on multiprocessor SMP and NUMA systems. The
<tt class="docutils literal"><span class="pre">cpuset</span></tt> library, being developed in parallel, depends on this bitmask
library.</p>
<table class="docutils field-list" frame="void" rules="none">
<col class="field-name" />
<col class="field-body" />
<tbody valign="top">
<tr class="field"><th class="field-name">Author:</th><td class="field-body">Paul Jackson</td>
</tr>
<tr class="field"><th class="field-name">Address:</th><td class="field-body"><a class="reference" href="mailto:pj@sgi.com">pj@sgi.com</a></td>
</tr>
<tr class="field"><th class="field-name">Date:</th><td class="field-body">23 Sept 2005</td>
</tr>
<tr class="field"><th class="field-name">Copyright:</th><td class="field-body">Copyright (c) 2004-2006 Silicon Graphics, Inc. All rights reserved.</td>
</tr>
</tbody>
</table>
<p>This document is written using the outline processor <a class="reference" href="http://webpages.charter.net/edreamleo/front.html">Leo</a>, and version controlled
using <a class="reference" href="http://cssc.sourceforge.net/index.shtml">CSSC</a>. It is rendered using <a class="reference" href="http://docutils.sourceforge.net">Python Docutils</a> on <a class="reference" href="http://docutils.sourceforge.net/docs/rst/quickstart.html">reStructuredText</a>
extracted from <a class="reference" href="http://webpages.charter.net/edreamleo/front.html">Leo</a>, directly into both <a class="reference" href="http://www.w3.org/MarkUp">html</a> and <a class="reference" href="http://www.latex-project.org">LaTeX</a>. The <a class="reference" href="http://www.latex-project.org">LaTeX</a> is
converted into <a class="reference" href="http://www.adobe.com/products/acrobat">pdf</a> using the <a class="reference" href="http://www.tug.org/applications/pdftex">pdflatex</a> utility. The html is converted into
plain text using the <a class="reference" href="http://lynx.isc.org">lynx</a> utility.</p>
<div class="contents topic" id="table-of-contents">
<p class="topic-title first"><a name="table-of-contents">Table of Contents</a></p>
<ul class="auto-toc simple">
<li><a class="reference" href="#what-are-bitmasks" id="id1" name="id1">1 What are bitmasks?</a></li>
<li><a class="reference" href="#ascii-string-representations" id="id2" name="id2">2 Ascii string representations</a></li>
<li><a class="reference" href="#calling-return-and-error-conventions" id="id3" name="id3">3 Calling, return and error conventions</a></li>
<li><a class="reference" href="#other-bits-always-zero" id="id4" name="id4">4 Other bits always zero</a></li>
<li><a class="reference" href="#internal-binary-representation" id="id5" name="id5">5 Internal binary representation</a></li>
<li><a class="reference" href="#comparing-these-bitmasks-with-the-linux-kernel" id="id6" name="id6">6 Comparing these bitmasks with the Linux kernel</a></li>
<li><a class="reference" href="#bitmask-library-functions" id="id7" name="id7">7 Bitmask Library Functions</a></li>
</ul>
</div>
<div class="section" id="what-are-bitmasks">
<h1><a class="toc-backref" href="#id1" name="what-are-bitmasks">1 What are bitmasks?</a></h1>
<p>Bitmasks provide multi-word bit masks and operations thereon to do
such things as set and clear bits, intersect and union masks, query bits, and
display and parse masks.</p>
<p>The initial intended use for these bitmasks is to represent sets of
CPUs and Memory Nodes, when configuring large SMP and NUMA systems.
However there is little in the semantics of bitmasks that is specific
to this particular use, and bitmasks should be usable for
other purposes that had similar design requirements.</p>
<p>These bitmasks share the same underlying layout as the bitmasks used
by the Linux kernel to represent sets of CPUs and Memory Nodes. Unlike
the kernel bitmasks, these bitmasks use dynamically allocated memory
and are manipulated via a pointer. This enables a program to work
correctly on systems with various numbers of CPUs and Nodes, without
recompilation.</p>
<p>There is a related cpuset library which uses the bitmask type provided
here to represent sets of CPUs and Memory Nodes. The internal
representation (as an array of unsigned longs, in little endian order)
is directly compatible with the <tt class="docutils literal"><span class="pre">sched_setaffinity(2)</span></tt> and
<tt class="docutils literal"><span class="pre">sched_getaffinity(2)</span></tt> system calls (added in Linux 2.6).</p>
</div>
<div class="section" id="ascii-string-representations">
<h1><a class="toc-backref" href="#id2" name="ascii-string-representations">2 Ascii string representations</a></h1>
<p>There are two ascii representations of these multi-word bitmasks,
and this library provides display and parsing routines to convert
both representations to and from the internal binary representation
of bitmasks.</p>
<p>The hex mask representation of a bitmask of size 64, with bits
1,5,6,11-13,17-19 set looks like:</p>
<blockquote>
<pre class="literal-block">
00000000,000E3862
</pre>
</blockquote>
<p>and the decimal list representation for this same value looks like:</p>
<blockquote>
<pre class="literal-block">
1,5,6,11-13,17-19
</pre>
</blockquote>
<div class="section" id="hex-mask">
<h2><a name="hex-mask">2.1 Hex mask</a></h2>
<p>The hex mask representation of multi-word bit masks displays each
32-bit word in hex (zero filled), and for masks longer than
one word, uses a comma separator between words. Words are
displayed in big-endian order most significant first. And hex
digits within a word are also in big-endian order.</p>
<p>The number of 32-bit words displayed is the minimum number needed
to display all bits of the bitmask, based on the size of the
bitmask.</p>
<p>Examples of the hex word bitmask display format:</p>
<blockquote>
<pre class="literal-block">
A mask with just bit 0 set displays as "00000001".
A mask with just bit 127 set displays as "80000000,00000000,00000000,00000000".
A mask with just bit 64 set displays as "00000001,00000000,00000000".
A mask with bits 0, 1, 2, 4, 8, 16, 32 and 64 set displays as
"00000001,00000001,00010117". The first "1" is for bit 64, the second
for bit 32, the third for bit 16, and so forth, to the "7", which is for
bits 2, 1 and 0.
A mask with bits 32 through 39 set displays as "000000ff,00000000".
A 64 bit bitmask with bits 1, 5, 6, 11-13, and 17-19 set displays as
"00000000,000E3862".
</pre>
</blockquote>
</div>
<div class="section" id="decimal-list">
<h2><a name="decimal-list">2.2 Decimal list</a></h2>
<p>The decimal list representation of bitmasks represents
them as a list of numbers and ranges of numbers.</p>
<p>This format supports a space separated list of one or more comma
separated sequences of ascii decimal bit numbers and ranges,
optionally modified by a <cite>stride operator</cite>.</p>
<p>Example of the decimal list bitmask display format:</p>
<blockquote>
<pre class="literal-block">
0-4,9 # set bits 0, 1, 2, 3, 4, and 9
</pre>
</blockquote>
<p>The <cite>stride operator</cite> is used to designate every N-th bit in a range
It is written as a colon <strong>":"</strong> followed by the number N,
with no spaces on either side of the colon.</p>
<p>Examples of the <cite>stride operator</cite>:</p>
<blockquote>
<pre class="literal-block">
0-31:2 # the 16 even bits 0, 2, 4, ... 30 <br>
1-31:2 # the 16 odd bits 1, 3, 5, ... 31 <br>
0-31 # all 32 bits 0, 1, 2, ... 31
</pre>
</blockquote>
</div>
</div>
<div class="section" id="calling-return-and-error-conventions">
<h1><a class="toc-backref" href="#id3" name="calling-return-and-error-conventions">3 Calling, return and error conventions</a></h1>
<p>As explained in more detail in the next section,
all bitmask operations treat all bits, outside of the originally
specified bit range from 0 to size-1, as if they were zero.</p>
<p>Most of the operations change the bitmask referenced
by the first argument, and return a pointer to that bitmask,
to allow convenient chaining of calls. However, be careful
of such usage - it's really easy to code memory leaks this way.
Each <tt class="docutils literal"><span class="pre">struct</span> <span class="pre">bitmask</span> <span class="pre">*</span></tt> pointer obtained from a call to
<a class="reference" href="#bitmask-alloc">bitmask_alloc</a> needs to be free'd with a call (exactly <em>one</em> call)
to <a class="reference" href="#bitmask-free">bitmask_free</a>.</p>
<p>Bit positions in bitmasks are zero based (not one based). The bit
positions in a bitmask of size n are numbered 0 through n-1.</p>
<p>The Boolean functions return 1 (True) or 0 (False).</p>
<p>All but the first <tt class="docutils literal"><span class="pre">struct</span> <span class="pre">bitmask</span> <span class="pre">*</span></tt> pointers passed to any of the
following operations are read-only, declared as: <tt class="docutils literal"><span class="pre">const</span> <span class="pre">struct</span> <span class="pre">bitmask</span> <span class="pre">*</span></tt>.</p>
<p>The unary operations, such as <a class="reference" href="#bitmask-complement">bitmask_complement</a>, take two bitmask
arguments, for the result and the source, in that order. The same
<tt class="docutils literal"><span class="pre">struct</span> <span class="pre">bitmask</span> <span class="pre">*</span></tt> pointer may be passed for both arguments, in
order to apply the operation in place.</p>
<p>The binary operations, such as <a class="reference" href="#bitmask-and">bitmask_and</a>, take three bitmask
arguments, for the result and the two sources. Either source may be
the same as the result. Indeed, all three arguments may be the same
pointer (though it is not clear what purpose that would serve).</p>
<p>The shift operations zero fill, whether left or right shifting.</p>
<p>The range operations follow 'C' conventions in using closed
left, open right intervals. That is, the range of bit positions
determined by the pair of integer arguments (i, j) includes
exactly all positions >= i and < j.</p>
<p>The <a class="reference" href="#bitmask-next">bitmask_next</a> function returns the bitmask size if all bits are clear
above the requested position.</p>
<p>The <a class="reference" href="#bitmask-first">bitmask_first</a> and <a class="reference" href="#bitmask-last">bitmask_last</a> functions return the bitmask size if
all bits are clear in the bitmask.</p>
<p>Two masks are equal if they have the same set bits, regardless
of whether they have the same size.</p>
<p>Most of the operations or functions have no error return cases.
They are defined so as to have valid returns for all well formed
arguments. Of course, if the arguments are not well formed, then
your application will probably exit with a Segmentation Violation.
This is 'C' after all.</p>
<p>The <a class="reference" href="#bitmask-alloc">bitmask_alloc</a> function returns a zero pointer (NULL) and sets
<cite>errno</cite> in the event that <tt class="docutils literal"><span class="pre">malloc(3)</span></tt> fails. See the <tt class="docutils literal"><span class="pre">malloc(3)</span></tt>
man page for possible values of <cite>errno</cite> (<strong>ENOMEM</strong> being the most
likely).</p>
<p>The <a class="reference" href="#bitmask-displayhex">bitmask_displayhex</a>, <a class="reference" href="#bitmask-displaylist">bitmask_displaylist</a>, <a class="reference" href="#bitmask-parsehex">bitmask_parsehex</a>, and
<a class="reference" href="#bitmask-parselist">bitmask_parselist</a> routines have more complex error and return
conventions. See their detailed descriptions below.</p>
</div>
<div class="section" id="other-bits-always-zero">
<h1><a class="toc-backref" href="#id4" name="other-bits-always-zero">4 Other bits always zero</a></h1>
<p>All bitmask operations treat all bits, outside of the originally
specified bit range from 0 to size-1, as if they were zero. Even bits
that might actually be present, due to the use of some multiple of
unsigned longs to represent the masks, are always zero, if they are
outside the specified number of bits in the mask.</p>
<p>The specified number of bits in a bitmask (its size) is established
in the <a class="reference" href="#bitmask-alloc">bitmask_alloc</a> call, and <strong>never</strong> changed after that.</p>
<dl class="docutils">
<dt>Note:</dt>
<dd>In particular, observe that the <a class="reference" href="#bitmask-copy">bitmask_copy</a> function does <strong>not</strong>
change the size of the target bitmask. Hence the result of copying a
large bitmask to a small one will often not be equal to the original
large bitmask - rather it will be shortened (to the smaller target size,
with bits above that size zero'd).</dd>
</dl>
<p>For example, if you invoke:</p>
<blockquote>
<pre class="literal-block">
struct bitmask *bmp = bitmask_alloc(17);
bitmask_setall(bmp);
bitmask_setbit(bmp, 21);
</pre>
</blockquote>
<p>then the calls:</p>
<blockquote>
<pre class="literal-block">
{
int x = bitmask_last(bmp);
int y = bitmask_isbitset(999);
}
</pre>
</blockquote>
<p>will set x to 16 (the 17 bits are numbered 0 to 16), not 21 or some
other higher number, and they will set y to 0.</p>
<p>Requests to set bits outside those in the range specified
in the initial <a class="reference" href="#bitmask-alloc">bitmask_alloc</a> are ignored and do not
cause any error.</p>
<p>Requests to display or query bits outside those in the range
specified in the initial <a class="reference" href="#bitmask-alloc">bitmask_alloc</a> always behave as
if those bits were present and zero.</p>
</div>
<div class="section" id="internal-binary-representation">
<h1><a class="toc-backref" href="#id5" name="internal-binary-representation">5 Internal binary representation</a></h1>
<p>The 'C' code that uses bitmasks sees only a <tt class="docutils literal"><span class="pre">struct</span> <span class="pre">bitmask</span> <span class="pre">*</span></tt> opaque pointer.</p>
<p>Hidden within the implementation of bitmasks, a <tt class="docutils literal"><span class="pre">struct</span> <span class="pre">bitmask</span></tt> is simply:</p>
<blockquote>
<pre class="literal-block">
struct bitmask {
unsigned int size; /* size in bits of bitmask */
unsigned long *maskp; /* array of unsigned longs */
};
</pre>
</blockquote>
<p>This structure, and the variable length array of unsigned long words
to which it points are allocated using <tt class="docutils literal"><span class="pre">malloc(3)</span></tt> in the calls to
<a class="reference" href="#bitmask-alloc">bitmask_alloc</a>, and deallocated using <tt class="docutils literal"><span class="pre">free(3)</span></tt> in the calls to
<a class="reference" href="#bitmask-free">bitmask_free</a>.</p>
<p>The <tt class="docutils literal"><span class="pre">maskp</span></tt> array of unsigned longs is arranged the same as the
bitmask operands to the <tt class="docutils literal"><span class="pre">sched_setaffinity(2)</span></tt> and
<tt class="docutils literal"><span class="pre">sched_getaffinity(2)</span></tt> system calls (added in Linux 2.6). As of this
writing this is the same layout as is used by the kernels
<tt class="docutils literal"><span class="pre">cpumask_t</span></tt> and <tt class="docutils literal"><span class="pre">nodemask_t</span></tt> types and the task struct
<tt class="docutils literal"><span class="pre">cpus_allowed</span></tt> and <tt class="docutils literal"><span class="pre">mems_allowed</span></tt> fields.</p>
<p>This representation places multiple unsigned long words in little
endian order - low order word first. Within each unsigned long, bits
are addressed in 'natural C' order, as 1<<n, for n between 0 and 31 on
32 bit architectures, and between 0 and 63 on 64 bit architectures.</p>
<p>The implementation of this bitmask library reserves the right to
extend or change this structure and other details of this internal
representation.</p>
</div>
<div class="section" id="comparing-these-bitmasks-with-the-linux-kernel">
<h1><a class="toc-backref" href="#id6" name="comparing-these-bitmasks-with-the-linux-kernel">6 Comparing these bitmasks with the Linux kernel</a></h1>
<p>This section compares this bitmask library with the implementation
of bitmasks in the Linux kernel, as of version 2.6.</p>
<p>Users of this library don't actually need to understand these differences.
However users already familiar with kernel bitmasks may find this comparison
helpful. And this comparison provides an interesting way to present a few of
the design tradeoffs that were made in creating this library.</p>
<blockquote>
<ul class="simple">
<li>This library implementation and API is optimized for ease of porting,
ease of use and flexible runtime behaviour.</li>
<li>The Linux kernel bitmasks are optimized for optimum space and time
performance with compiled in fixed sizing of critical cpu and node
masks.</li>
<li>This library provides a larger, more complete and consistent set
of bitmask routines than the kernel bitmasks.</li>
<li>All calls are actual subroutine calls, not gcc inline functions or
macros.</li>
</ul>
</blockquote>
<div class="section" id="dynamic-memory">
<h2><a name="dynamic-memory">6.1 Dynamic Memory</a></h2>
<p>The representation of bitmasks in the Linux kernel,
as of this writing, is essentially:</p>
<blockquote>
<pre class="literal-block">
struct { unsigned long bitmask[N]; };
</pre>
</blockquote>
<p>None of this uses memory allocated dynamically at runtime.
Instead, all sizes are known at compile time, and the compiler,
along with some inline functions and macros, sizes each bitmask
to a hardcoded size, such as NR_CPUS (number of CPUs which that
kernel will support).</p>
<p>The current representation of bitmasks in this library, as
noted in the previous section, is:</p>
<blockquote>
<pre class="literal-block">
struct bitmask {
unsigned int size; /* size in bits of bitmask */
unsigned long *maskp; /* array of unsigned longs */
};
</pre>
</blockquote>
<p>Both this structure, and the array <tt class="docutils literal"><span class="pre">maskp</span></tt> it references, are
dynamically allocated at runtime.</p>
<p>User programs, unlike a specific compilation of the kernel, usually avoid
hardcoding the number of CPUs and Memory Nodes which they support.
It is for this simple reason that this library uses dynamic memory
allocation and runtime sizing, instead of the static allocation and
compile time sizing used by the kernel's bitmask implementation.</p>
</div>
<div class="section" id="portable-c">
<h2><a name="portable-c">6.2 Portable C</a></h2>
<p>This library is implemented in Portable C, and presents an API that
can easily be used in any Portable C code. The implementing code is
kept simple, portable and easy to develop and maintain. The code is
not optimized for critical inner loop performance requirements.</p>
<p>The Linux kernel bitmasks make essential use of gcc extensions
in order to provide the compile time sizing and optimum performance
that is required for use in critical scheduler and allocator loops.</p>
</div>
<div class="section" id="larger-api">
<h2><a name="larger-api">6.3 Larger API</a></h2>
<p>In order to make it easy to code bitmask operations, and reduce the
costs of coding errors in the applications using these routines, this
library provides a larger, more complete and consistent set of bitmask
routines than the kernel bitmasks.</p>
<p>The kernel has some carefully optimized bitmasks routines for specific
architectures, which makes it a bit more difficult to keep their API
as straightforward and consistent as this library. And it avoids
providing routines that don't have an actual use in existing kernel
code.</p>
</div>
<div class="section" id="no-macros-or-access-to-bitmask-internals">
<h2><a name="no-macros-or-access-to-bitmask-internals">6.4 No macros or access to bitmask internals</a></h2>
<p>The implementation of this bitmask library uses no gcc inline
functions or preprocessor macro functions of <tt class="docutils literal"><span class="pre">struct</span> <span class="pre">bitmask</span></tt> in
the bitmask.h header file, and produces no code in the application
binary that knows the internals of <tt class="docutils literal"><span class="pre">struct</span> <span class="pre">bitmask</span></tt>.</p>
<p>Everything that looks like a function on bitmasks is a real function
call into the libmask.so library. The <tt class="docutils literal"><span class="pre">struct</span> <span class="pre">bitmask</span></tt> structure is
declared in <tt class="docutils literal"><span class="pre">bitmask.h</span></tt> without its members defined, as simply:</p>
<blockquote>
<pre class="literal-block">
struct bitmask;
</pre>
</blockquote>
<p>The reason that there are no such macro or inline functions in the bitmask.h
header file is that without access to the internals of the bitmask
structure, they could not be compiled.</p>
<p>There are two reasons that the internals of the bitmask structure are
not accessible in the bitmask.h header.</p>
<p>One reason is to discourage code that looks inside a structure that is
intended to be opaque. This reduces the risk that some future change
to the implementation internals of this structure will adversely
impact existing application binaries using this API.</p>
<p>The other reason is to discourage bitmask structure assignment, which
reduces the risk of memory corruption bugs from misuse of this structure.</p>
<p>Code such as the following will not compile, but it if did, would
typically result in memory corruption.</p>
<blockquote>
<pre class="literal-block">
#include <bitmask.h>
struct bitmask *bmp1 = bitmask_alloc(32);
struct bitmask *bmp2 = bitmask_alloc(32);
*bmp2 = *bmp1; /* 1. Doesn't compile - if it did, would be unsafe assignment */
bitmask_free(bmp1); /* 2. Free it once */
bitmask_free(bmp2); /* 3. Free it twice: corrupted malloc heap */
</pre>
</blockquote>
<p>At step [1], the dynamic memory allocated to bmp2 is lost (memory
leak) and the dynamic memory allocated to bmp1 is now referenced
twice. At step [2], the memory for bmp1 is free'd once. At step [3],
it is free'd again, resulting in a corrupt malloc heap, and likely an
obscure crash later in the program execution.</p>
<p>Assigning the pointers, and passing them as arguments, is acceptable,
so long as you are careful not to cause a memory leak by assigning to
a <cite>struct bitmask *</cite> pointer that is currently referencing some other
dynamically allocated bitmask which should first be freed via that
pointer.</p>
<blockquote>
<pre class="literal-block">
#include <bitmask.h>
struct bitmask *bmp1;
struct bitmask *bmp2 = bitmask_alloc(32);
extern void f(struct bitmask *);
bmp1 = bmp2; /* ok */
f(bmp1); /* ok */
</pre>
</blockquote>
<p>Both of the above reasons reflect the same basic design tradeoff to prefer
robust, portable code over aggressive extraction of performance.</p>
<p>The above choices also enable application binaries to continue working
correctly in the face of internal changes to the bitmask library,
without requiring the applications to be recompiled. This is quite
unlike the Linux kernel, which is routinely recompiled in its
entirety, as a single unit, anytime any part of it changes.</p>
</div>
</div>
<div class="section" id="bitmask-library-functions">
<h1><a class="toc-backref" href="#id7" name="bitmask-library-functions">7 Bitmask Library Functions</a></h1>
<p>The following inclusion and linkage provides access to the bitmask API
from 'C' code:</p>
<blockquote>
<pre class="literal-block">
#include <bitmask.h>
/* link with -lbitmask */
</pre>
</blockquote>
<p>The following functions are supported in the 'C' bitmask API. In some
cases, 'C' equivalent code is shown, as if bitmasks were a single
unsigned long, even though they are packaged in a structure,
referenced by a pointer, and actually contain an array of perhaps
multiple unsigned longs.</p>
<p>None of these operations other than <a class="reference" href="#bitmask-alloc">bitmask_alloc</a> allocate new bitmasks,
and none of them other than <a class="reference" href="#bitmask-free">bitmask_free</a> free existing bitmasks.</p>
<p>None of these operations other than <a class="reference" href="#bitmask-alloc">bitmask_alloc</a> set or change the
size of a bitmask.</p>
<p>The following functions are supported in the 'C' bitmask API:</p>
<ul class="simple">
<li>Allocate and free <tt class="docutils literal"><span class="pre">struct</span> <span class="pre">bitmask</span> <span class="pre">*</span></tt><ul>
<li><a class="reference" href="#bitmask-alloc">bitmask_alloc</a> (n) - Allocate a new struct bitmask with a size of n bits</li>
<li><a class="reference" href="#bitmask-free">bitmask_free</a> (struct bitmask * bmp) - Free struct bitmask</li>
</ul>
</li>
<li>Display and parse ascii string representations<ul>
<li><a class="reference" href="#bitmask-displayhex">bitmask_displayhex</a> (buf, len, bmp) - Write hex word representation of bmp to buf</li>
<li><a class="reference" href="#bitmask-displaylist">bitmask_displaylist</a> (buf, len, bmp) - Write decimal list representation of bmp to buf</li>
<li><a class="reference" href="#bitmask-parsehex">bitmask_parsehex</a> (buf, bmp) - Parse hex word representation in buf to bmp</li>
<li><a class="reference" href="#bitmask-parselist">bitmask_parselist</a> (buf, bmp) - Parse decimal list representation in buf to bmp</li>
</ul>
</li>
<li>Basic initialization operations<ul>
<li><a class="reference" href="#bitmask-copy">bitmask_copy</a> (bmp1, bmp2) - Copy bmp2 to bmp1</li>
<li><a class="reference" href="#bitmask-setall">bitmask_setall</a> (bmp) - Set all bits in bitmask: bmp = ~0</li>
<li><a class="reference" href="#bitmask-clearall">bitmask_clearall</a> (bmp) - Clear all bits in bitmask: bmp = 0</li>
</ul>
</li>
<li>Interface aids for kernel sched_{set,get}affinity system calls<ul>
<li><a class="reference" href="#bitmask-nbytes">bitmask_nbytes</a> (bmp) - Length in bytes of mask - use as second argument to these calls</li>
<li><a class="reference" href="#bitmask-mask">bitmask_mask</a> (bmp) - Direct pointer to bit mask - use as third argument to these calls</li>
</ul>
</li>
<li>Unary numeric queries<ul>
<li><a class="reference" href="#bitmask-nbits">bitmask_nbits</a> (bmp) - Size in bits of entire bitmask</li>
<li><a class="reference" href="#bitmask-weight">bitmask_weight</a> (bmp) - Hamming Weight: number of set bits</li>
</ul>
</li>
<li>Unary Boolean queries<ul>
<li><a class="reference" href="#bitmask-isbitset">bitmask_isbitset</a> (bmp, i) - True if specified bit <strong>i</strong> is set</li>
<li><a class="reference" href="#bitmask-isbitclear">bitmask_isbitclear</a> (bmp, i) - True if specified bit <strong>i</strong> is clear</li>
<li><a class="reference" href="#bitmask-isallset">bitmask_isallset</a> (bmp) - True if all bits are set</li>
<li><a class="reference" href="#bitmask-isallclear">bitmask_isallclear</a> (bmp) - True if all bits are clear</li>
</ul>
</li>
<li>Single bit operations<ul>
<li><a class="reference" href="#bitmask-setbit">bitmask_setbit</a> (bmp, i) - Set a single bit <strong>i</strong> in bitmask</li>
<li><a class="reference" href="#bitmask-clearbit">bitmask_clearbit</a> (bmp, i) - Clear a single bit <strong>i</strong> in bitmask</li>
</ul>
</li>
<li>Binary Boolean operations: bmp1 op? bmp2<ul>
<li><a class="reference" href="#bitmask-equal">bitmask_equal</a> (bmp1, bmp2) - True if two bitmasks are equal</li>
<li><a class="reference" href="#bitmask-subset">bitmask_subset</a> (bmp1, bmp2) - True if first bitmask is subset of second</li>
<li><a class="reference" href="#bitmask-disjoint">bitmask_disjoint</a> (bmp1, bmp2) - True if two bitmasks don't overlap</li>
<li><a class="reference" href="#bitmask-intersects">bitmask_intersects</a> (bmp1, bmp2) - True if two bitmasks do overlap</li>
</ul>
</li>
<li>Range operations<ul>
<li><a class="reference" href="#bitmask-setrange">bitmask_setrange</a> (bmp, i, j) - Set bits of bitmask in specified range [i, j)</li>
<li><a class="reference" href="#bitmask-clearrange">bitmask_clearrange</a> (bmp, i, j) - Clear bits of bitmask in specified range</li>
<li><a class="reference" href="#bitmask-keeprange">bitmask_keeprange</a> (bmp, i, j) - Clear all but specified range</li>
</ul>
</li>
<li>Unary operations: bmp1 = op(bmp2)<ul>
<li><a class="reference" href="#bitmask-complement">bitmask_complement</a> (bmp1, bmp2) - Complement: bmp1 = ~bmp2</li>
<li><a class="reference" href="#bitmask-shiftright">bitmask_shiftright</a> (bmp1, bmp2, n) - Right shift: bmp1 = bmp2 >> n</li>
<li><a class="reference" href="#bitmask-shiftleft">bitmask_shiftleft</a> (bmp1, bmp2, n) - Left shift: bmp1 = bmp2 << n</li>
</ul>
</li>
<li>Binary operations: bmp1 = bmp2 op bmp3<ul>
<li><a class="reference" href="#bitmask-and">bitmask_and</a> (bmp1, bmp2, bmp3) - Logical <cite>and</cite> of two bitmasks: bmp1 = bmp2 & bmp3</li>
<li><a class="reference" href="#bitmask-andnot">bitmask_andnot</a> (bmp1, bmp2, bmp3) - Logical <cite>andnot</cite> of two bitmasks: bmp1 = bmp2 & ~bmp3</li>
<li><a class="reference" href="#bitmask-or">bitmask_or</a> (bmp1, bmp2, bmp3) - Logical <cite>or</cite> of two bitmasks: bmp1 = bmp2 | bmp3</li>
<li><a class="reference" href="#bitmask-eor">bitmask_eor</a> (bmp1, bmp2, bmp3) - Logical <cite>eor</cite> of two bitmasks: bmp1 = bmp2 ^ bmp3</li>
</ul>
</li>
<li>Iteration operators<ul>
<li><a class="reference" href="#bitmask-first">bitmask_first</a> (bmp) - Number of lowest set bit (min)</li>
<li><a class="reference" href="#bitmask-next">bitmask_next</a> (bmp, i) - Number of next set bit above given bit <strong>i</strong></li>
<li><a class="reference" href="#bitmask-rel-to-abs-pos">bitmask_rel_to_abs_pos</a> (bmp, n) - Absolute position of nth set bit</li>
<li><a class="reference" href="#bitmask-abs-to-rel-pos">bitmask_abs_to_rel_pos</a> (bmp, n) - Relative position amongst set bits of bit n</li>
<li><a class="reference" href="#bitmask-last">bitmask_last</a> (bmp) - Number of highest set bit (max)</li>
</ul>
</li>
</ul>
<div class="section" id="bitmask-alloc">
<h2><a name="bitmask-alloc">7.1 bitmask_alloc</a></h2>
<div class="section" id="struct-bitmask-bitmask-alloc-unsigned-int-nbits">
<h3><a name="struct-bitmask-bitmask-alloc-unsigned-int-nbits"><tt class="docutils literal"><span class="pre">struct</span> <span class="pre">bitmask</span> <span class="pre">*bitmask_alloc(unsigned</span> <span class="pre">int</span> <span class="pre">nbits);</span></tt></a></h3>
<blockquote>
<p>Allocate a new struct bitmask with a size of <tt class="docutils literal"><span class="pre">nbits</span></tt> bits.</p>
<p>This is the only bitmask function that creates bitmasks.</p>
<p>Each <tt class="docutils literal"><span class="pre">struct</span> <span class="pre">bitmask</span> <span class="pre">*</span></tt> pointer obtained from a call to
<a class="reference" href="#bitmask-alloc">bitmask_alloc</a> needs to be free'd with a call (exactly <em>one</em>
call) to <a class="reference" href="#bitmask-free">bitmask_free</a>.</p>
<p>The <a class="reference" href="#bitmask-alloc">bitmask_alloc</a> function uses the underlying <tt class="docutils literal"><span class="pre">malloc(3)</span></tt>
routine to obtain memory. It returns a zero pointer (NULL) and
sets <cite>errno</cite> in the event that <tt class="docutils literal"><span class="pre">malloc(3)</span></tt> fails. See the
<tt class="docutils literal"><span class="pre">malloc(3)</span></tt> man page for possible values of <cite>errno</cite> (<strong>ENOMEM</strong>
being the most likely).</p>
<p>The size of a bitmask, as specified in the <cite>bitmask_alloc</cite> call
that created it, is <em>never</em> changed by subsequent bitmask
operations. Bits at positions outside the range zero to nbits-1 are
always zero. Attempts to modify bits at such positions are always
ignored, doing nothing, successfully.</p>
<p>For portable code, when allocating a bitmask to handle the CPUs or Memory
Nodes on a system, the number of CPUs or Nodes should not be hardcoded, but
obtained dynamically from the system. The routines <tt class="docutils literal"><span class="pre">cpuset_cpus_nbits()</span></tt>
and <tt class="docutils literal"><span class="pre">cpuset_mems_nbits()</span></tt> in the related <cite>libcpuset</cite> library provide the
maximum number of CPUs or Memory Nodes that the operating system was
compiled to support. Use these values to size CPU and Memory Node bitmasks
for calls into the <cite>libcpuset</cite> library.</p>
</blockquote>
</div>
</div>
<div class="section" id="bitmask-free">
<h2><a name="bitmask-free">7.2 bitmask_free</a></h2>
<div class="section" id="void-bitmask-free-struct-bitmask-bmp">
<h3><a name="void-bitmask-free-struct-bitmask-bmp"><tt class="docutils literal"><span class="pre">void</span> <span class="pre">bitmask_free(struct</span> <span class="pre">bitmask</span> <span class="pre">*bmp);</span></tt></a></h3>
<blockquote>
<p>Free a bitmask struct.</p>
<p>This call frees the memory assigned to a bitmask. It is the only
function that frees bitmasks. The <cite>struct bitmask *`</cite> pointer must
have been returned by a previous call to <a class="reference" href="#bitmask-alloc">bitmask_alloc</a>. The
memory is not cleared. If <cite>bmp</cite> is NULL, no operation is
performed.</p>
<p>Each <tt class="docutils literal"><span class="pre">struct</span> <span class="pre">bitmask</span> <span class="pre">*</span></tt> pointer obtained from a call to
<a class="reference" href="#bitmask-alloc">bitmask_alloc</a> needs to be free'd with a call (exactly <em>one</em>
call) to <a class="reference" href="#bitmask-free">bitmask_free</a>.</p>
<p><a class="reference" href="#bitmask-free">bitmask_free</a> returns no value.</p>
</blockquote>
</div>
</div>
<div class="section" id="bitmask-displayhex">
<h2><a name="bitmask-displayhex">7.3 bitmask_displayhex</a></h2>
<div class="section" id="int-bitmask-displayhex-char-buf-int-len-const-struct-bitmask-bmp">
<h3><a name="int-bitmask-displayhex-char-buf-int-len-const-struct-bitmask-bmp"><tt class="docutils literal"><span class="pre">int</span> <span class="pre">bitmask_displayhex(char</span> <span class="pre">*buf,</span> <span class="pre">int</span> <span class="pre">len,</span> <span class="pre">const</span> <span class="pre">struct</span> <span class="pre">bitmask</span> <span class="pre">*bmp);</span></tt></a></h3>
<blockquote>
Write hex mask representation of bmp to buf.</blockquote>
</div>
</div>
<div class="section" id="bitmask-displaylist">
<h2><a name="bitmask-displaylist">7.4 bitmask_displaylist</a></h2>
<div class="section" id="int-bitmask-displaylist-char-buf-int-len-const-struct-bitmask-bmp">
<h3><a name="int-bitmask-displaylist-char-buf-int-len-const-struct-bitmask-bmp"><tt class="docutils literal"><span class="pre">int</span> <span class="pre">bitmask_displaylist(char</span> <span class="pre">*buf,</span> <span class="pre">int</span> <span class="pre">len,</span> <span class="pre">const</span> <span class="pre">struct</span> <span class="pre">bitmask</span> <span class="pre">*bmp);</span></tt></a></h3>
<blockquote>
Write decimal list representation of bmp to buf.</blockquote>
</div>
</div>
<div class="section" id="bitmask-parsehex">
<h2><a name="bitmask-parsehex">7.5 bitmask_parsehex</a></h2>
<div class="section" id="int-bitmask-parsehex-const-char-buf-struct-bitmask-bmp">
<h3><a name="int-bitmask-parsehex-const-char-buf-struct-bitmask-bmp"><tt class="docutils literal"><span class="pre">int</span> <span class="pre">bitmask_parsehex(const</span> <span class="pre">char</span> <span class="pre">*buf,</span> <span class="pre">struct</span> <span class="pre">bitmask</span> <span class="pre">*bmp);</span></tt></a></h3>
<blockquote>
Parse hex mask representation in buf to bmp.</blockquote>
</div>
</div>
<div class="section" id="bitmask-parselist">
<h2><a name="bitmask-parselist">7.6 bitmask_parselist</a></h2>
<div class="section" id="int-bitmask-parselist-const-char-buf-struct-bitmask-bmp">
<h3><a name="int-bitmask-parselist-const-char-buf-struct-bitmask-bmp"><tt class="docutils literal"><span class="pre">int</span> <span class="pre">bitmask_parselist(const</span> <span class="pre">char</span> <span class="pre">*buf,</span> <span class="pre">struct</span> <span class="pre">bitmask</span> <span class="pre">*bmp);</span></tt></a></h3>
<blockquote>
Parse decimal list representation in buf to bmp.</blockquote>
</div>
</div>
<div class="section" id="bitmask-copy">
<h2><a name="bitmask-copy">7.7 bitmask_copy</a></h2>
<div class="section" id="struct-bitmask-bitmask-copy-struct-bitmask-bmp1-const-bitmask-bmp2">
<h3><a name="struct-bitmask-bitmask-copy-struct-bitmask-bmp1-const-bitmask-bmp2"><tt class="docutils literal"><span class="pre">struct</span> <span class="pre">bitmask</span> <span class="pre">*bitmask_copy(struct</span> <span class="pre">bitmask</span> <span class="pre">*bmp1,</span> <span class="pre">const</span> <span class="pre">bitmask</span> <span class="pre">*bmp2);</span></tt></a></h3>
<blockquote>
<p>Copy the value of bitmask bmp2 to bitmask bmp1. If the size of bmp1 is
smaller than bmp2, then bits set in bmp2 beyond what fit in bmp1 are
lost in the bmp1 copy. If the size of bmp1 is larger than bmp2,then
bits set in bmp1 beyond what bmp2 specifies are cleared. The target
bitmask bmp1 is not resized in any case.</p>
<p>Returns the pointer bmp1.</p>
</blockquote>
</div>
</div>
<div class="section" id="bitmask-setall">
<h2><a name="bitmask-setall">7.8 bitmask_setall</a></h2>
<div class="section" id="struct-bitmask-bitmask-setall-struct-bitmask-bmp">
<h3><a name="struct-bitmask-bitmask-setall-struct-bitmask-bmp"><tt class="docutils literal"><span class="pre">struct</span> <span class="pre">bitmask</span> <span class="pre">*bitmask_setall(struct</span> <span class="pre">bitmask</span> <span class="pre">*bmp);</span></tt></a></h3>
<blockquote>
<p>Sets all bits in bitmask bmp.</p>
<p>Returns the pointer bmp.</p>
</blockquote>
</div>
</div>
<div class="section" id="bitmask-clearall">
<h2><a name="bitmask-clearall">7.9 bitmask_clearall</a></h2>
<div class="section" id="struct-bitmask-bitmask-clearall-struct-bitmask-bmp">
<h3><a name="struct-bitmask-bitmask-clearall-struct-bitmask-bmp"><tt class="docutils literal"><span class="pre">struct</span> <span class="pre">bitmask</span> <span class="pre">*bitmask_clearall(struct</span> <span class="pre">bitmask</span> <span class="pre">*bmp);</span></tt></a></h3>
<blockquote>
<p>Clears all bits in bitmask bmp.</p>
<p>Returns the pointer bmp.</p>
</blockquote>
</div>
</div>
<div class="section" id="bitmask-nbytes">
<h2><a name="bitmask-nbytes">7.10 bitmask_nbytes</a></h2>
<div class="section" id="unsigned-int-bitmask-nbytes-struct-bitmask-bmp">
<h3><a name="unsigned-int-bitmask-nbytes-struct-bitmask-bmp"><tt class="docutils literal"><span class="pre">unsigned</span> <span class="pre">int</span> <span class="pre">bitmask_nbytes(struct</span> <span class="pre">bitmask</span> <span class="pre">*bmp);</span></tt></a></h3>
<blockquote>
<p>Returns the length in bytes of a bitmask.</p>
<p>This is useful as the second argument to systems calls (new in
Linux 2.6) <tt class="docutils literal"><span class="pre">sched_setaffinity(2)</span></tt> and <tt class="docutils literal"><span class="pre">sched_getaffinity(2)</span></tt></p>
<p>Example:</p>
<blockquote>
<pre class="literal-block">
/* Bind current process to the 3rd CPU (number 2) of a possible 64 CPUs */
struct bitmask *bmp = bitmask_alloc(64);
bitmask_setbit(2);
if (sched_setaffinity(0, bitmask_nbytes(bmp), bitmask_mask(bmp)) < 0)
... handle error ...
bitmask_free(bmp);
</pre>
</blockquote>
</blockquote>
</div>
</div>
<div class="section" id="bitmask-mask">
<h2><a name="bitmask-mask">7.11 bitmask_mask</a></h2>
<div class="section" id="unsigned-long-bitmask-mask-struct-bitmask-bmp">
<h3><a name="unsigned-long-bitmask-mask-struct-bitmask-bmp"><tt class="docutils literal"><span class="pre">unsigned</span> <span class="pre">long</span> <span class="pre">*bitmask_mask(struct</span> <span class="pre">bitmask</span> <span class="pre">*bmp);</span></tt></a></h3>
<blockquote>
<p>Returns a direct pointer to the unsigned long mask array of a bitmask.</p>
<p>This is useful as the third argument to systems calls (new in
Linux 2.6) <tt class="docutils literal"><span class="pre">sched_setaffinity(2)</span></tt> and <tt class="docutils literal"><span class="pre">sched_getaffinity(2)</span></tt></p>
<p>See also the example for <a class="reference" href="#bitmask-nbytes">bitmask_nbytes</a>, above.</p>
</blockquote>
</div>
</div>
<div class="section" id="bitmask-nbits">
<h2><a name="bitmask-nbits">7.12 bitmask_nbits</a></h2>
<div class="section" id="unsigned-int-bitmask-nbits-const-struct-bitmask-bmp">
<h3><a name="unsigned-int-bitmask-nbits-const-struct-bitmask-bmp"><tt class="docutils literal"><span class="pre">unsigned</span> <span class="pre">int</span> <span class="pre">bitmask_nbits(const</span> <span class="pre">struct</span> <span class="pre">bitmask</span> <span class="pre">*bmp);</span></tt></a></h3>
<blockquote>
Size in bits of entire bitmask.</blockquote>
</div>
</div>
<div class="section" id="bitmask-weight">
<h2><a name="bitmask-weight">7.13 bitmask_weight</a></h2>
<div class="section" id="unsigned-int-bitmask-weight-const-struct-bitmask-bmp">
<h3><a name="unsigned-int-bitmask-weight-const-struct-bitmask-bmp"><tt class="docutils literal"><span class="pre">unsigned</span> <span class="pre">int</span> <span class="pre">bitmask_weight(const</span> <span class="pre">struct</span> <span class="pre">bitmask</span> <span class="pre">*bmp);</span></tt></a></h3>
<blockquote>
Hamming Weight: number of set bits.</blockquote>
</div>
</div>
<div class="section" id="bitmask-isbitset">
<h2><a name="bitmask-isbitset">7.14 bitmask_isbitset</a></h2>
<div class="section" id="int-bitmask-isbitset-const-struct-bitmask-bmp-unsigned-int-i">
<h3><a name="int-bitmask-isbitset-const-struct-bitmask-bmp-unsigned-int-i"><tt class="docutils literal"><span class="pre">int</span> <span class="pre">bitmask_isbitset(const</span> <span class="pre">struct</span> <span class="pre">bitmask</span> <span class="pre">*bmp,</span> <span class="pre">unsigned</span> <span class="pre">int</span> <span class="pre">i);</span></tt></a></h3>
<blockquote>
True if specified bit i is set. Always false if i >= bitmask_nbits_().</blockquote>
</div>
</div>
<div class="section" id="bitmask-isbitclear">
<h2><a name="bitmask-isbitclear">7.15 bitmask_isbitclear</a></h2>
<div class="section" id="int-bitmask-isbitclear-const-struct-bitmask-bmp-unsigned-int-i">
<h3><a name="int-bitmask-isbitclear-const-struct-bitmask-bmp-unsigned-int-i"><tt class="docutils literal"><span class="pre">int</span> <span class="pre">bitmask_isbitclear(const</span> <span class="pre">struct</span> <span class="pre">bitmask</span> <span class="pre">*bmp,</span> <span class="pre">unsigned</span> <span class="pre">int</span> <span class="pre">i);</span></tt></a></h3>
<blockquote>
True if specified bit i is clear. Always true if i >= bitmask_nbits_().</blockquote>
</div>
</div>
<div class="section" id="bitmask-isallset">
<h2><a name="bitmask-isallset">7.16 bitmask_isallset</a></h2>
<div class="section" id="int-bitmask-isallset-const-struct-bitmask-bmp">
<h3><a name="int-bitmask-isallset-const-struct-bitmask-bmp"><tt class="docutils literal"><span class="pre">int</span> <span class="pre">bitmask_isallset(const</span> <span class="pre">struct</span> <span class="pre">bitmask</span> <span class="pre">*bmp);</span></tt></a></h3>
<blockquote>
True if all bits from positions 0 to bitmask_nbits_() - 1 are set.</blockquote>
</div>
</div>
<div class="section" id="bitmask-isallclear">
<h2><a name="bitmask-isallclear">7.17 bitmask_isallclear</a></h2>
<div class="section" id="int-bitmask-isallclear-const-struct-bitmask-bmp">
<h3><a name="int-bitmask-isallclear-const-struct-bitmask-bmp"><tt class="docutils literal"><span class="pre">int</span> <span class="pre">bitmask_isallclear(const</span> <span class="pre">struct</span> <span class="pre">bitmask</span> <span class="pre">*bmp);</span></tt></a></h3>
<blockquote>
True if all bits from positions 0 to bitmask_nbits_() - 1 are clear.</blockquote>
</div>
</div>
<div class="section" id="bitmask-setbit">
<h2><a name="bitmask-setbit">7.18 bitmask_setbit</a></h2>
<div class="section" id="struct-bitmask-bitmask-setbit-struct-bitmask-bmp-unsigned-int-i">
<h3><a name="struct-bitmask-bitmask-setbit-struct-bitmask-bmp-unsigned-int-i"><tt class="docutils literal"><span class="pre">struct</span> <span class="pre">bitmask</span> <span class="pre">*bitmask_setbit(struct</span> <span class="pre">bitmask</span> <span class="pre">*bmp,</span> <span class="pre">unsigned</span> <span class="pre">int</span> <span class="pre">i);</span></tt></a></h3>
<blockquote>
Set a single bit i in bitmask. Does nothing successfully
if i >= bitmask_nbits_(). Returns the <tt class="docutils literal"><span class="pre">bmp</span></tt> pointer passed in.</blockquote>
</div>
</div>
<div class="section" id="bitmask-clearbit">
<h2><a name="bitmask-clearbit">7.19 bitmask_clearbit</a></h2>
<div class="section" id="struct-bitmask-bitmask-clearbit-struct-bitmask-bmp-unsigned-int-i">
<h3><a name="struct-bitmask-bitmask-clearbit-struct-bitmask-bmp-unsigned-int-i"><tt class="docutils literal"><span class="pre">struct</span> <span class="pre">bitmask</span> <span class="pre">*bitmask_clearbit(struct</span> <span class="pre">bitmask</span> <span class="pre">*bmp,</span> <span class="pre">unsigned</span> <span class="pre">int</span> <span class="pre">i);</span></tt></a></h3>
<blockquote>
Clear a single bit i in bitmask. Does nothing successfully
if i >= bitmask_nbits_(). Returns the <tt class="docutils literal"><span class="pre">bmp</span></tt> pointer passed in.</blockquote>
</div>
</div>
<div class="section" id="bitmask-equal">
<h2><a name="bitmask-equal">7.20 bitmask_equal</a></h2>
<div class="section" id="int-bitmask-equal-const-struct-bitmask-bmp1-const-bitmask-bmp2">
<h3><a name="int-bitmask-equal-const-struct-bitmask-bmp1-const-bitmask-bmp2"><tt class="docutils literal"><span class="pre">int</span> <span class="pre">bitmask_equal(const</span> <span class="pre">struct</span> <span class="pre">bitmask</span> <span class="pre">*bmp1,</span> <span class="pre">const</span> <span class="pre">bitmask</span> <span class="pre">*bmp2);</span></tt></a></h3>
<blockquote>
True if two bitmasks are equal.</blockquote>
</div>
</div>
<div class="section" id="bitmask-subset">
<h2><a name="bitmask-subset">7.21 bitmask_subset</a></h2>
<div class="section" id="int-bitmask-subset-const-struct-bitmask-bmp1-const-bitmask-bmp2">
<h3><a name="int-bitmask-subset-const-struct-bitmask-bmp1-const-bitmask-bmp2"><tt class="docutils literal"><span class="pre">int</span> <span class="pre">bitmask_subset(const</span> <span class="pre">struct</span> <span class="pre">bitmask</span> <span class="pre">*bmp1,</span> <span class="pre">const</span> <span class="pre">bitmask</span> <span class="pre">*bmp2);</span></tt></a></h3>
<blockquote>
True if first bitmask is subset of second.</blockquote>
</div>
</div>
<div class="section" id="bitmask-disjoint">
<h2><a name="bitmask-disjoint">7.22 bitmask_disjoint</a></h2>
<div class="section" id="int-bitmask-disjoint-const-struct-bitmask-bmp1-const-bitmask-bmp2">
<h3><a name="int-bitmask-disjoint-const-struct-bitmask-bmp1-const-bitmask-bmp2"><tt class="docutils literal"><span class="pre">int</span> <span class="pre">bitmask_disjoint(const</span> <span class="pre">struct</span> <span class="pre">bitmask</span> <span class="pre">*bmp1,</span> <span class="pre">const</span> <span class="pre">bitmask</span> <span class="pre">*bmp2);</span></tt></a></h3>
<blockquote>
True if two bitmasks don't overlap.</blockquote>
</div>
</div>
<div class="section" id="bitmask-intersects">
<h2><a name="bitmask-intersects">7.23 bitmask_intersects</a></h2>
<div class="section" id="int-bitmask-intersects-const-struct-bitmask-bmp1-const-bitmask-bmp2">
<h3><a name="int-bitmask-intersects-const-struct-bitmask-bmp1-const-bitmask-bmp2"><tt class="docutils literal"><span class="pre">int</span> <span class="pre">bitmask_intersects(const</span> <span class="pre">struct</span> <span class="pre">bitmask</span> <span class="pre">*bmp1,</span> <span class="pre">const</span> <span class="pre">bitmask</span> <span class="pre">*bmp2);</span></tt></a></h3>
<blockquote>
True if two bitmasks do overlap.</blockquote>
</div>
</div>
<div class="section" id="bitmask-setrange">
<h2><a name="bitmask-setrange">7.24 bitmask_setrange</a></h2>
<div class="section" id="struct-bitmask-bitmask-setrange-struct-bitmask-bmp-unsigned-int-i-unsigned-int-j">
<h3><a name="struct-bitmask-bitmask-setrange-struct-bitmask-bmp-unsigned-int-i-unsigned-int-j"><tt class="docutils literal"><span class="pre">struct</span> <span class="pre">bitmask</span> <span class="pre">*bitmask_setrange(struct</span> <span class="pre">bitmask</span> <span class="pre">*bmp,</span> <span class="pre">unsigned</span> <span class="pre">int</span> <span class="pre">i,</span> <span class="pre">unsigned</span> <span class="pre">int</span> <span class="pre">j);</span></tt></a></h3>
<blockquote>
Set bits of bitmask in specified range [i, j).</blockquote>
</div>
</div>
<div class="section" id="bitmask-clearrange">
<h2><a name="bitmask-clearrange">7.25 bitmask_clearrange</a></h2>
<div class="section" id="struct-bitmask-bitmask-clearrange-struct-bitmask-bmp-unsigned-int-i-unsigned-int-j">
<h3><a name="struct-bitmask-bitmask-clearrange-struct-bitmask-bmp-unsigned-int-i-unsigned-int-j"><tt class="docutils literal"><span class="pre">struct</span> <span class="pre">bitmask</span> <span class="pre">*bitmask_clearrange(struct</span> <span class="pre">bitmask</span> <span class="pre">*bmp,</span> <span class="pre">unsigned</span> <span class="pre">int</span> <span class="pre">i,</span> <span class="pre">unsigned</span> <span class="pre">int</span> <span class="pre">j);</span></tt></a></h3>
<blockquote>
Clear bits of bitmask in specified range.</blockquote>
</div>
</div>
<div class="section" id="bitmask-keeprange">
<h2><a name="bitmask-keeprange">7.26 bitmask_keeprange</a></h2>
<div class="section" id="struct-bitmask-bitmask-keeprange-struct-bitmask-bmp-unsigned-int-i-unsigned-int-j">
<h3><a name="struct-bitmask-bitmask-keeprange-struct-bitmask-bmp-unsigned-int-i-unsigned-int-j"><tt class="docutils literal"><span class="pre">struct</span> <span class="pre">bitmask</span> <span class="pre">*bitmask_keeprange(struct</span> <span class="pre">bitmask</span> <span class="pre">*bmp,</span> <span class="pre">unsigned</span> <span class="pre">int</span> <span class="pre">i,</span> <span class="pre">unsigned</span> <span class="pre">int</span> <span class="pre">j);</span></tt></a></h3>
<blockquote>
Clear all but specified range.</blockquote>
</div>
</div>
<div class="section" id="bitmask-complement">
<h2><a name="bitmask-complement">7.27 bitmask_complement</a></h2>
<div class="section" id="struct-bitmask-bitmask-complement-struct-bitmask-bmp1-const-bitmask-bmp2">
<h3><a name="struct-bitmask-bitmask-complement-struct-bitmask-bmp1-const-bitmask-bmp2"><tt class="docutils literal"><span class="pre">struct</span> <span class="pre">bitmask</span> <span class="pre">*bitmask_complement(struct</span> <span class="pre">bitmask</span> <span class="pre">*bmp1,</span> <span class="pre">const</span> <span class="pre">bitmask</span> <span class="pre">*bmp2);</span></tt></a></h3>
<blockquote>
Complement: bmp1 = ~bmp2.</blockquote>
</div>
</div>
<div class="section" id="bitmask-shiftright">
<h2><a name="bitmask-shiftright">7.28 bitmask_shiftright</a></h2>
<div class="section" id="struct-bitmask-bitmask-shiftright-struct-bitmask-bmp1-const-bitmask-bmp2-unsigned-int-n">
<h3><a name="struct-bitmask-bitmask-shiftright-struct-bitmask-bmp1-const-bitmask-bmp2-unsigned-int-n"><tt class="docutils literal"><span class="pre">struct</span> <span class="pre">bitmask</span> <span class="pre">*bitmask_shiftright(struct</span> <span class="pre">bitmask</span> <span class="pre">*bmp1,</span> <span class="pre">const</span> <span class="pre">bitmask</span> <span class="pre">*bmp2,</span> <span class="pre">unsigned</span> <span class="pre">int</span> <span class="pre">n);</span></tt></a></h3>
<blockquote>
Right shift: bmp1 = bmp2 >> n.</blockquote>
</div>
</div>
<div class="section" id="bitmask-shiftleft">
<h2><a name="bitmask-shiftleft">7.29 bitmask_shiftleft</a></h2>
<div class="section" id="struct-bitmask-bitmask-shiftleft-struct-bitmask-bmp1-const-bitmask-bmp2-unsigned-int-n">
<h3><a name="struct-bitmask-bitmask-shiftleft-struct-bitmask-bmp1-const-bitmask-bmp2-unsigned-int-n"><tt class="docutils literal"><span class="pre">struct</span> <span class="pre">bitmask</span> <span class="pre">*bitmask_shiftleft(struct</span> <span class="pre">bitmask</span> <span class="pre">*bmp1,</span> <span class="pre">const</span> <span class="pre">bitmask</span> <span class="pre">*bmp2,</span> <span class="pre">unsigned</span> <span class="pre">int</span> <span class="pre">n);</span></tt></a></h3>
<blockquote>
Left shift: bmp1 = bmp2 << n.</blockquote>
</div>
</div>
<div class="section" id="bitmask-and">
<h2><a name="bitmask-and">7.30 bitmask_and</a></h2>
<div class="section" id="struct-bitmask-bitmask-and-struct-bitmask-bmp1-const-bitmask-bmp2-const-bitmask-bmp3">
<h3><a name="struct-bitmask-bitmask-and-struct-bitmask-bmp1-const-bitmask-bmp2-const-bitmask-bmp3"><tt class="docutils literal"><span class="pre">struct</span> <span class="pre">bitmask</span> <span class="pre">*bitmask_and(struct</span> <span class="pre">bitmask</span> <span class="pre">*bmp1,</span> <span class="pre">const</span> <span class="pre">bitmask</span> <span class="pre">*bmp2,</span> <span class="pre">const</span> <span class="pre">bitmask</span> <span class="pre">*bmp3);</span></tt></a></h3>
<blockquote>
<p>Logical <cite>and</cite> of two bitmasks: bmp1 = bmp2 & bmp3.</p>
<p>The bits that are set in the result bitmask, bmp1, are the
intersection of the bits that are set in the source bitmasks
bmp2 and bmp3.</p>
</blockquote>
</div>
</div>
<div class="section" id="bitmask-andnot">
<h2><a name="bitmask-andnot">7.31 bitmask_andnot</a></h2>
<div class="section" id="struct-bitmask-bitmask-andnot-struct-bitmask-bmp1-const-bitmask-bmp2-const-bitmask-bmp3">
<h3><a name="struct-bitmask-bitmask-andnot-struct-bitmask-bmp1-const-bitmask-bmp2-const-bitmask-bmp3"><tt class="docutils literal"><span class="pre">struct</span> <span class="pre">bitmask</span> <span class="pre">*bitmask_andnot(struct</span> <span class="pre">bitmask</span> <span class="pre">*bmp1,</span> <span class="pre">const</span> <span class="pre">bitmask</span> <span class="pre">*bmp2,</span> <span class="pre">const</span> <span class="pre">bitmask</span> <span class="pre">*bmp3);</span></tt></a></h3>
<blockquote>
<p>Logical <cite>andnot</cite> of two bitmasks: bmp1 = bmp2 & ~bmp3.</p>
<p>The bits that are set in the result bitmask, bmp1, are the
the bits that are set in the source bitmask bmp2 but not in
bmp3.</p>
</blockquote>
</div>
</div>
<div class="section" id="bitmask-or">
<h2><a name="bitmask-or">7.32 bitmask_or</a></h2>
<div class="section" id="struct-bitmask-bitmask-or-struct-bitmask-bmp1-const-bitmask-bmp2-const-bitmask-bmp3">
<h3><a name="struct-bitmask-bitmask-or-struct-bitmask-bmp1-const-bitmask-bmp2-const-bitmask-bmp3"><tt class="docutils literal"><span class="pre">struct</span> <span class="pre">bitmask</span> <span class="pre">*bitmask_or(struct</span> <span class="pre">bitmask</span> <span class="pre">*bmp1,</span> <span class="pre">const</span> <span class="pre">bitmask</span> <span class="pre">*bmp2,</span> <span class="pre">const</span> <span class="pre">bitmask</span> <span class="pre">*bmp3);</span></tt></a></h3>
<blockquote>
<p>Logical <cite>or</cite> of two bitmasks: bmp1 = bmp2 | bmp3.</p>
<p>The bits that are set in the result bitmask, bmp1, are the
union of the bits that are set in either source bitmasks
bmp2 or bmp3.</p>
</blockquote>
</div>
</div>
<div class="section" id="bitmask-eor">
<h2><a name="bitmask-eor">7.33 bitmask_eor</a></h2>
<div class="section" id="struct-bitmask-bitmask-eor-struct-bitmask-bmp1-const-bitmask-bmp2-const-bitmask-bmp3">
<h3><a name="struct-bitmask-bitmask-eor-struct-bitmask-bmp1-const-bitmask-bmp2-const-bitmask-bmp3"><tt class="docutils literal"><span class="pre">struct</span> <span class="pre">bitmask</span> <span class="pre">*bitmask_eor(struct</span> <span class="pre">bitmask</span> <span class="pre">*bmp1,</span> <span class="pre">const</span> <span class="pre">bitmask</span> <span class="pre">*bmp2,</span> <span class="pre">const</span> <span class="pre">bitmask</span> <span class="pre">*bmp3);</span></tt></a></h3>
<blockquote>
<p>Logical <cite>eor</cite> of two bitmasks: bmp1 = bmp2 ^ bmp3.</p>
<p>The bits that are set in the result bitmask, bmp1, are the
symmetric difference (in one or the other but not both) of
the bits that are set in the source bitmasks bmp2 or bmp3.</p>
</blockquote>
</div>
</div>
<div class="section" id="bitmask-first">
<h2><a name="bitmask-first">7.34 bitmask_first</a></h2>
<div class="section" id="int-bitmask-first-const-struct-bitmask-bmp">
<h3><a name="int-bitmask-first-const-struct-bitmask-bmp"><tt class="docutils literal"><span class="pre">int</span> <span class="pre">bitmask_first(const</span> <span class="pre">struct</span> <span class="pre">bitmask</span> <span class="pre">*bmp);</span></tt></a></h3>
<blockquote>
Number of lowest set bit (min).</blockquote>
</div>
</div>
<div class="section" id="bitmask-next">
<h2><a name="bitmask-next">7.35 bitmask_next</a></h2>
<div class="section" id="unsigned-int-bitmask-next-const-struct-bitmask-bmp-unsigned-int-i">
<h3><a name="unsigned-int-bitmask-next-const-struct-bitmask-bmp-unsigned-int-i"><tt class="docutils literal"><span class="pre">unsigned</span> <span class="pre">int</span> <span class="pre">bitmask_next(const</span> <span class="pre">struct</span> <span class="pre">bitmask</span> <span class="pre">*bmp,</span> <span class="pre">unsigned</span> <span class="pre">int</span> <span class="pre">i);</span></tt></a></h3>
<blockquote>
Number of next set bit above given bit i.</blockquote>
</div>
</div>
<div class="section" id="bitmask-rel-to-abs-pos">
<h2><a name="bitmask-rel-to-abs-pos">7.36 bitmask_rel_to_abs_pos</a></h2>
<div class="section" id="unsigned-int-bitmask-rel-to-abs-pos-const-struct-bitmask-bmp-unsigned-int-n">
<h3><a name="unsigned-int-bitmask-rel-to-abs-pos-const-struct-bitmask-bmp-unsigned-int-n"><tt class="docutils literal"><span class="pre">unsigned</span> <span class="pre">int</span> <span class="pre">bitmask_rel_to_abs_pos(const</span> <span class="pre">struct</span> <span class="pre">bitmask</span> <span class="pre">*bmp,</span> <span class="pre">unsigned</span> <span class="pre">int</span> <span class="pre">n);</span></tt></a></h3>
<blockquote>
Return the number of the nth set bit. Calling bitmask_rel_to_abs_pos(bmp, 0) is
equivalent to calling bitmask_first(bmp). Calling bitmask_rel_to_abs_pos(bmp,
bitmask_weight(bmp) - 1) is equivalent to calling bitmask_last(bmp).</blockquote>
</div>
</div>
<div class="section" id="bitmask-abs-to-rel-pos">
<h2><a name="bitmask-abs-to-rel-pos">7.37 bitmask_abs_to_rel_pos</a></h2>
<div class="section" id="unsigned-int-bitmask-abs-to-rel-pos-const-struct-bitmask-bmp-unsigned-int-n">
<h3><a name="unsigned-int-bitmask-abs-to-rel-pos-const-struct-bitmask-bmp-unsigned-int-n"><tt class="docutils literal"><span class="pre">unsigned</span> <span class="pre">int</span> <span class="pre">bitmask_abs_to_rel_pos(const</span> <span class="pre">struct</span> <span class="pre">bitmask</span> <span class="pre">*bmp,</span> <span class="pre">unsigned</span> <span class="pre">int</span> <span class="pre">n);</span></tt></a></h3>
<blockquote>
Return the relative bit position, amongst just the set bits, of the nth
bit, if the nth bit is set. If the nth bit is not set, return bitmask_nbytes.
For the bit positions that are set, bitmask_abs_to_rel_pos is the inverse
of bitmask_rel_to_abs_pos.</blockquote>
</div>
</div>
<div class="section" id="bitmask-last">
<h2><a name="bitmask-last">7.38 bitmask_last</a></h2>
<div class="section" id="unsigned-int-bitmask-last-const-struct-bitmask-bmp">
<h3><a name="unsigned-int-bitmask-last-const-struct-bitmask-bmp"><tt class="docutils literal"><span class="pre">unsigned</span> <span class="pre">int</span> <span class="pre">bitmask_last(const</span> <span class="pre">struct</span> <span class="pre">bitmask</span> <span class="pre">*bmp);</span></tt></a></h3>
<blockquote>
Number of highest set bit (max).</blockquote>
</div>
</div>
</div>
</div>
</body>
</html>
|