Date: Sat, 17 Oct 2015 19:55:58 +0000 (UTC) From: "Conrad E. Meyer" <cem@FreeBSD.org> To: src-committers@freebsd.org, svn-src-all@freebsd.org, svn-src-head@freebsd.org Subject: svn commit: r289467 - in head: lib/libc/string share/man/man3 share/man/man9 Message-ID: <201510171955.t9HJtwUF065449@repo.freebsd.org>
next in thread | raw e-mail | index | archive | help
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@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@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@FreeBSD.org . +This manual page was written by +.An Conrad Meyer Aq Mt cem@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).
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?201510171955.t9HJtwUF065449>