svn commit: r289467 - in head: lib/libc/string share/man/man3 share/man/man9
Conrad E. Meyer
cem at FreeBSD.org
Sat Oct 17 19:55:59 UTC 2015
Author: cem
Date: Sat Oct 17 19:55:58 2015
New Revision: 289467
URL: https://svnweb.freebsd.org/changeset/base/289467
Log:
Document bitset(9)
Added:
head/share/man/man9/bitset.9 (contents, props changed)
Modified:
head/lib/libc/string/ffs.3
head/share/man/man3/bitstring.3
head/share/man/man9/Makefile
Modified: head/lib/libc/string/ffs.3
==============================================================================
--- head/lib/libc/string/ffs.3 Sat Oct 17 19:52:17 2015 (r289466)
+++ head/lib/libc/string/ffs.3 Sat Oct 17 19:55:58 2015 (r289467)
@@ -30,7 +30,7 @@
.\" @(#)ffs.3 8.2 (Berkeley) 4/19/94
.\" $FreeBSD$
.\"
-.Dd September 29, 2012
+.Dd October 17, 2015
.Dt FFS 3
.Os
.Sh NAME
@@ -81,7 +81,8 @@ Bits are numbered starting at 1, the lea
A return value of zero from any of these functions means that the
argument was zero.
.Sh SEE ALSO
-.Xr bitstring 3
+.Xr bitstring 3 ,
+.Xr bitset 9
.Sh HISTORY
The
.Fn ffs
Modified: head/share/man/man3/bitstring.3
==============================================================================
--- head/share/man/man3/bitstring.3 Sat Oct 17 19:52:17 2015 (r289466)
+++ head/share/man/man3/bitstring.3 Sat Oct 17 19:55:58 2015 (r289467)
@@ -30,7 +30,7 @@
.\" @(#)bitstring.3 8.1 (Berkeley) 7/19/93
.\" $FreeBSD$
.\"
-.Dd July 19, 1993
+.Dd October 17, 2015
.Dt BITSTRING 3
.Os
.Sh NAME
@@ -178,7 +178,8 @@ make_lpr_available()
}
.Ed
.Sh SEE ALSO
-.Xr malloc 3
+.Xr malloc 3 ,
+.Xr bitset 9
.Sh HISTORY
The
.Nm bitstring
Modified: head/share/man/man9/Makefile
==============================================================================
--- head/share/man/man9/Makefile Sat Oct 17 19:52:17 2015 (r289466)
+++ head/share/man/man9/Makefile Sat Oct 17 19:55:58 2015 (r289467)
@@ -11,6 +11,7 @@ MAN= accept_filter.9 \
altq.9 \
atomic.9 \
bios.9 \
+ bitset.9 \
boot.9 \
bpf.9 \
buf.9 \
@@ -429,6 +430,32 @@ MLINKS+=atomic.9 atomic_add.9 \
atomic.9 atomic_subtract.9 \
atomic.9 atomic_swap.9 \
atomic.9 atomic_testandset.9
+MLINKS+=bitset.9 BITSET_DEFINE.9 \
+ bitset.9 BITSET_T_INITIALIZER.9 \
+ bitset.9 BITSET_FSET.9 \
+ bitset.9 BIT_CLR.9 \
+ bitset.9 BIT_COPY.9 \
+ bitset.9 BIT_ISSET.9 \
+ bitset.9 BIT_SET.9 \
+ bitset.9 BIT_ZERO.9 \
+ bitset.9 BIT_FILL.9 \
+ bitset.9 BIT_SETOF.9 \
+ bitset.9 BIT_EMPTY.9 \
+ bitset.9 BIT_ISFULLSET.9 \
+ bitset.9 BIT_FFS.9 \
+ bitset.9 BIT_COUNT.9 \
+ bitset.9 BIT_SUBSET.9 \
+ bitset.9 BIT_OVERLAP.9 \
+ bitset.9 BIT_CMP.9 \
+ bitset.9 BIT_OR.9 \
+ bitset.9 BIT_AND.9 \
+ bitset.9 BIT_NAND.9 \
+ bitset.9 BIT_CLR_ATOMIC.9 \
+ bitset.9 BIT_SET_ATOMIC.9 \
+ bitset.9 BIT_SET_ATOMIC_ACQ.9 \
+ bitset.9 BIT_AND_ATOMIC.9 \
+ bitset.9 BIT_OR_ATOMIC.9 \
+ bitset.9 BIT_COPY_STORE_REL.9
MLINKS+=bpf.9 bpfattach.9 \
bpf.9 bpfattach2.9 \
bpf.9 bpfdetach.9 \
Added: head/share/man/man9/bitset.9
==============================================================================
--- /dev/null 00:00:00 1970 (empty, because file is newly added)
+++ head/share/man/man9/bitset.9 Sat Oct 17 19:55:58 2015 (r289467)
@@ -0,0 +1,400 @@
+.\" Copyright (c) 2015 Conrad Meyer <cem at FreeBSD.org>
+.\" All rights reserved.
+.\"
+.\" Redistribution and use in source and binary forms, with or without
+.\" modification, are permitted provided that the following conditions
+.\" are met:
+.\" 1. Redistributions of source code must retain the above copyright
+.\" notice, this list of conditions and the following disclaimer.
+.\" 2. Redistributions in binary form must reproduce the above copyright
+.\" notice, this list of conditions and the following disclaimer in the
+.\" documentation and/or other materials provided with the distribution.
+.\"
+.\" THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS''
+.\" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
+.\" TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
+.\" PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE
+.\" LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
+.\" CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
+.\" SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
+.\" INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
+.\" CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
+.\" ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
+.\" POSSIBILITY OF SUCH DAMAGE.
+.\"
+.\" $FreeBSD$
+.\"
+.Dd October 17, 2015
+.Dt BITSET 9
+.Os
+.Sh NAME
+.Nm bitset(9)
+\(em
+.Nm BITSET_DEFINE ,
+.Nm BITSET_T_INITIALIZER ,
+.Nm BITSET_FSET ,
+.Nm BIT_CLR ,
+.Nm BIT_COPY ,
+.Nm BIT_ISSET ,
+.Nm BIT_SET ,
+.Nm BIT_ZERO ,
+.Nm BIT_FILL ,
+.Nm BIT_SETOF ,
+.Nm BIT_EMPTY ,
+.Nm BIT_ISFULLSET ,
+.Nm BIT_FFS ,
+.Nm BIT_COUNT ,
+.Nm BIT_SUBSET ,
+.Nm BIT_OVERLAP ,
+.Nm BIT_CMP ,
+.Nm BIT_OR ,
+.Nm BIT_AND ,
+.Nm BIT_NAND ,
+.Nm BIT_CLR_ATOMIC ,
+.Nm BIT_SET_ATOMIC ,
+.Nm BIT_SET_ATOMIC_ACQ ,
+.Nm BIT_AND_ATOMIC ,
+.Nm BIT_OR_ATOMIC ,
+.Nm BIT_COPY_STORE_REL
+.Nd bitset manipulation macros
+.Sh SYNOPSIS
+.In sys/_bitset.h
+.In sys/bitset.h
+.\"
+.Fn BITSET_DEFINE "STRUCTNAME" "const SETSIZE"
+.Fn BITSET_T_INITIALIZER "ARRAY_CONTENTS"
+.Fn BITSET_FSET "N_WORDS"
+.\"
+.Fn BIT_CLR "const SETSIZE" "size_t bit" "struct STRUCTNAME *bitset"
+.Fn BIT_COPY "const SETSIZE" "struct STRUCTNAME *from" "struct STRUCTNAME *to"
+.Ft bool
+.Fn BIT_ISSET "const SETSIZE" "size_t bit" "struct STRUCTNAME *bitset"
+.Fn BIT_SET "const SETSIZE" "size_t bit" "struct STRUCTNAME *bitset"
+.Fn BIT_ZERO "const SETSIZE" "struct STRUCTNAME *bitset"
+.Fn BIT_FILL "const SETSIZE" "struct STRUCTNAME *bitset"
+.Fn BIT_SETOF "const SETSIZE" "size_t bit" "struct STRUCTNAME *bitset"
+.Ft bool
+.Fn BIT_EMPTY "const SETSIZE" "struct STRUCTNAME *bitset"
+.Ft bool
+.Fn BIT_ISFULLSET "const SETSIZE" "struct STRUCTNAME *bitset"
+.Ft size_t
+.Fn BIT_FFS "const SETSIZE" "struct STRUCTNAME *bitset"
+.Ft size_t
+.Fn BIT_COUNT "const SETSIZE" "struct STRUCTNAME *bitset"
+.\"
+.Ft bool
+.Fo BIT_SUBSET
+.Fa "const SETSIZE" "struct STRUCTNAME *haystack" "struct STRUCTNAME *needle"
+.Fc
+.Ft bool
+.Fo BIT_OVERLAP
+.Fa "const SETSIZE" "struct STRUCTNAME *bitset1" "struct STRUCTNAME *bitset2"
+.Fc
+.Ft bool
+.Fo BIT_CMP
+.Fa "const SETSIZE" "struct STRUCTNAME *bitset1" "struct STRUCTNAME *bitset2"
+.Fc
+.Fn BIT_OR "const SETSIZE" "struct STRUCTNAME *dst" "struct STRUCTNAME *src"
+.Fn BIT_AND "const SETSIZE" "struct STRUCTNAME *dst" "struct STRUCTNAME *src"
+.Fn BIT_NAND "const SETSIZE" "struct STRUCTNAME *dst" "struct STRUCTNAME *src"
+.\"
+.Fn BIT_CLR_ATOMIC "const SETSIZE" "size_t bit" "struct STRUCTNAME *bitset"
+.Fn BIT_SET_ATOMIC "const SETSIZE" "size_t bit" "struct STRUCTNAME *bitset"
+.Fn BIT_SET_ATOMIC_ACQ "const SETSIZE" "size_t bit" "struct STRUCTNAME *bitset"
+.\"
+.Fo BIT_AND_ATOMIC
+.Fa "const SETSIZE" "struct STRUCTNAME *dst" "struct STRUCTNAME *src"
+.Fc
+.Fo BIT_OR_ATOMIC
+.Fa "const SETSIZE" "struct STRUCTNAME *dst" "struct STRUCTNAME *src"
+.Fc
+.Fo BIT_COPY_STORE_REL
+.Fa "const SETSIZE" "struct STRUCTNAME *from" "struct STRUCTNAME *to"
+.Fc
+.Sh DESCRIPTION
+The
+.Nm
+family of macros provide a flexible and efficient bitset implementation if the
+maximum size of the set is known at compilation.
+Throughout this manual page, the name
+.Fa SETSIZE
+refers to the size of the bitset in bits.
+Individual bits in bitsets are referenced with indices zero through
+.Fa SETSIZE - 1 .
+One example use of
+.In sys/bitset.h
+is
+.In sys/cpuset.h .
+.Pp
+The
+.Fn BITSET_DEFINE
+macro defines a bitset struct
+.Fa STRUCTNAME
+with room to represent
+.Fa SETSIZE
+bits.
+.Pp
+The
+.Fn BITSET_T_INITIALIZER
+macro allows one to initialize a bitset struct with a compile time literal
+value.
+.Pp
+The
+.Fn BITSET_FSET
+macro generates a compile time literal, usable by
+.Fn BITSET_T_INITIALIZER ,
+representing a full bitset (all bits set).
+For examples of
+.Fn BITSET_T_INITIALIZER
+and
+.Fn BITSET_FSET
+usage, see the
+.Sx BITSET_T_INITIALIZER EXAMPLE
+section.
+The
+.Fa N_WORDS
+parameter to
+.Fn BITSET_FSET
+should be:
+.Bd -literal -offset indent
+__bitset_words(SETSIZE)
+.Ed
+.Pp
+The
+.Fn BIT_CLR
+macro clears bit
+.Fa bit
+in the bitset pointed to by
+.Fa bitset .
+The
+.Fn BIT_CLR_ATOMIC
+macro is identical, but the bit is cleared atomically.
+.Pp
+The
+.Fn BIT_COPY
+macro copies the contents of the bitset
+.Fa from
+to the bitset
+.Fa to .
+.Fn BIT_COPY_STORE_REL
+is similar, but copies component machine words from
+.Fa from
+and writes them to
+.Fa to
+with atomic store with release semantics.
+(That is, if
+.Fa to
+is composed of multiple machine words,
+.Fn BIT_COPY_STORE_REL
+performs multiple individually atomic operations.)
+.Pp
+The
+.Fn BIT_SET
+macro sets bit
+.Fa bit
+in the bitset pointed to by
+.Fa bitset .
+The
+.Fn BIT_SET_ATOMIC
+macro is identical, but the bit is set atomically.
+The
+.Fn BIT_SET_ATOMIC_ACQ
+macro sets the bit with acquire semantics.
+.Pp
+The
+.Fn BIT_ZERO
+macro clears all bits in
+.Fa bitset .
+.Pp
+The
+.Fn BIT_FILL
+macro sets all bits in
+.Fa bitset .
+.Pp
+The
+.Fn BIT_SETOF
+macro clears all bits in
+.Fa bitset
+before setting only bit
+.Fa bit .
+.Pp
+The
+.Fn BIT_EMPTY
+macro returns
+.Dv true
+if
+.Fa bitset
+is empty.
+.Pp
+The
+.Fn BIT_ISFULLSET
+macro returns
+.Dv true
+if
+.Fa bitset
+is full (all bits set).
+.Pp
+The
+.Fn BIT_FFS
+macro returns the 1-index of the first (lowest) set bit in
+.Fa bitset ,
+or zero if
+.Fa bitset
+is empty.
+Like with
+.Xr ffs 3 ,
+to use the non-zero result of
+.Fn BIT_FFS
+as a
+.Fa bit
+index parameter to any other
+.Nm
+macro, you must subtract one from the result.
+.Pp
+The
+.Fn BIT_COUNT
+macro returns the total number of set bits in
+.Fa bitset .
+.Pp
+The
+.Fn BIT_SUBSET
+macro returns
+.Dv true
+if
+.Fa needle
+is a subset of
+.Fa haystack .
+.Pp
+The
+.Fn BIT_OVERLAP
+macro returns
+.Dv true
+if
+.Fa bitset1
+and
+.Fa bitset2
+have any common bits.
+(That is, if
+.Fa bitset1
+AND
+.Fa bitset2
+is not the empty set.)
+.Pp
+The
+.Fn BIT_CMP
+macro returns
+.Dv true
+if
+.Fa bitset1
+is NOT equal to
+.Fa bitset2 .
+.Pp
+The
+.Fn BIT_OR
+macro sets bits present in
+.Fa src
+in
+.Fa dst .
+(It is the
+.Nm
+equivalent of the scalar:
+.Fa dst
+|=
+.Fa src . )
+.Fn BIT_OR_ATOMIC
+is similar, but sets bits in the component machine words in
+.Fa dst
+atomically.
+(That is, if
+.Fa dst
+is composed of multiple machine words,
+.Fn BIT_OR_ATOMIC
+performs multiple individually atomic operations.)
+.Pp
+The
+.Fn BIT_AND
+macro clears bits absent from
+.Fa src
+from
+.Fa dst .
+(It is the
+.Nm
+equivalent of the scalar:
+.Fa dst
+&=
+.Fa src . )
+.Fn BIT_AND_ATOMIC
+is similar, with the same atomic semantics as
+.Fn BIT_OR_ATOMIC .
+.Pp
+The
+.Fn BIT_NAND
+macro clears bits set in
+.Fa src
+from
+.Fa dst .
+(It is the
+.Nm
+equivalent of the scalar:
+.Fa dst
+&=
+.Fa ~ src . )
+.Sh BITSET_T_INITIALIZER EXAMPLE
+.Bd -literal
+BITSET_DEFINE(_myset, MYSETSIZE);
+
+struct _myset myset;
+
+/* Initialize myset to filled (all bits set) */
+myset = BITSET_T_INITIALIZER(BITSET_FSET(__bitset_words(MYSETSIZE)));
+
+/* Initialize myset to only the lowest bit set */
+myset = BITSET_T_INITIALIZER(0x1);
+.Ed
+.Sh SEE ALSO
+The older
+.Xr bitstring 3 .
+.Sh HISTORY
+.In sys/cpuset.h
+first appeared in
+.Fx 7.1 ,
+released in January 2009, and in
+.Fx 8.0 ,
+released in November 2009 .
+.Pp
+The
+.Nm
+macros first appeared in
+.Fx 10.0
+in January 2014.
+They were MFCed to
+.Fx 9.3 ,
+released in July 2014.
+.Pp
+This manual page first appeared in
+.Fx 11.0 .
+.Sh AUTHORS
+.An -nosplit
+The
+.Nm
+macros were written for
+.In sys/cpuset.h
+by
+.An Jeff Roberson Aq Mt jeff at FreeBSD.org ;
+they were generalized and pulled out as
+.In sys/_bitset.h
+and
+.In sys/bitset.h
+by
+.An Attilio Rao Aq Mt attilio at FreeBSD.org .
+This manual page was written by
+.An Conrad Meyer Aq Mt cem at FreeBSD.org .
+.Sh CAVEATS
+The
+.Fa SETSIZE
+argument to all of these macros must match the value given to
+.Fn BITSET_DEFINE .
+.Pp
+Unlike every other reference to individual set members, which are zero-indexed,
+.Fn BIT_FFS
+returns a one-indexed result (or zero if the set is empty).
More information about the svn-src-head
mailing list