git: 2788bb20cc05 - stable/13 - bitset(9): Introduce BIT_FOREACH_ISSET and BIT_FOREACH_ISCLR

The branch stable/13 has been updated by markj:

URL: https://cgit.FreeBSD.org/src/commit/?id=2788bb20cc05f581a57b4f50e5c63f9c70e04208

commit 2788bb20cc05f581a57b4f50e5c63f9c70e04208
Author:     Mark Johnston <markj@FreeBSD.org>
AuthorDate: 2021-09-21 15:32:23 +0000
Commit:     Mark Johnston <markj@FreeBSD.org>
CommitDate: 2021-11-01 13:20:11 +0000

    bitset(9): Introduce BIT_FOREACH_ISSET and BIT_FOREACH_ISCLR
    
    These allow one to non-destructively iterate over the set or clear bits
    in a bitset.  The motivation is that we have several code fragments
    which iterate over a CPU set like this:
    
    while ((cpu = CPU_FFS(&cpus)) != 0) {
            cpu--;
            CPU_CLR(cpu, &cpus);
            <do something>;
    }
    
    This is slow since CPU_FFS begins the search at the beginning of the
    bitset each time.  On amd64 and arm64, CPU sets have size 256, so there
    are four limbs in the bitset and we do a lot of unnecessary scanning.
    
    A second problem is that this is destructive, so code which needs to
    preserve the original set has to make a copy.  In particular, we have
    quite a few functions which take a cpuset_t parameter by value, meaning
    that each call has to copy the 32 byte cpuset_t.
    
    The new macros address both problems.
    
    Reviewed by:    cem, kib
    Sponsored by:   The FreeBSD Foundation
    
    (cherry picked from commit dfd3bde5775ecf88851d5dffd6a8ed6076b53566)
---
 share/man/man9/Makefile |  2 ++
 share/man/man9/bitset.9 | 34 ++++++++++++++++++++++++++++++++--
 sys/sys/bitset.h        | 10 ++++++++++
 3 files changed, 44 insertions(+), 2 deletions(-)

diff --git a/share/man/man9/Makefile b/share/man/man9/Makefile
index c180742bdb4b..8793eb6b7278 100644
--- a/share/man/man9/Makefile
+++ b/share/man/man9/Makefile
@@ -616,6 +616,8 @@ MLINKS+=bitset.9 BITSET_DEFINE.9 \
 	bitset.9 BIT_FFS.9 \
 	bitset.9 BIT_FFS_AT.9 \
 	bitset.9 BIT_FLS.9 \
+	bitset.9 BIT_FOREACH_ISSET.9 \
+	bitset.9 BIT_FOREACH_ISCLR.9 \
 	bitset.9 BIT_COUNT.9 \
 	bitset.9 BIT_SUBSET.9 \
 	bitset.9 BIT_OVERLAP.9 \
diff --git a/share/man/man9/bitset.9 b/share/man/man9/bitset.9
index 1e080f515788..5788f09f2465 100644
--- a/share/man/man9/bitset.9
+++ b/share/man/man9/bitset.9
@@ -24,7 +24,7 @@
 .\"
 .\" $FreeBSD$
 .\"
-.Dd December 31, 2020
+.Dd September 20, 2021
 .Dt BITSET 9
 .Os
 .Sh NAME
@@ -45,6 +45,8 @@
 .Nm BIT_FFS ,
 .Nm BIT_FFS_AT ,
 .Nm BIT_FLS ,
+.Nm BIT_FOREACH_ISSET ,
+.Nm BIT_FOREACH_ISCLR ,
 .Nm BIT_COUNT ,
 .Nm BIT_SUBSET ,
 .Nm BIT_OVERLAP ,
@@ -92,9 +94,18 @@
 .Fn BIT_FFS_AT "const SETSIZE" "struct STRUCTNAME *bitset" "long start"
 .Ft long
 .Fn BIT_FLS "const SETSIZE" "struct STRUCTNAME *bitset"
+.Fo BIT_FOREACH_ISSET
+.Fa "const SETSIZE"
+.Fa "size_t bit"
+.Fa "const struct STRUCTNAME *bitset"
+.Fc
+.Fo BIT_FOREACH_ISCLR
+.Fa "const SETSIZE"
+.Fa "size_t bit"
+.Fa "const struct STRUCTNAME *bitset"
+.Fc
 .Ft long
 .Fn BIT_COUNT "const SETSIZE" "struct STRUCTNAME *bitset"
-.\"
 .Ft bool
 .Fo BIT_SUBSET
 .Fa "const SETSIZE" "struct STRUCTNAME *haystack" "struct STRUCTNAME *needle"
@@ -329,6 +340,25 @@ index parameter to any other
 macro, you must subtract one from the result.
 .Pp
 The
+.Fn BIT_FOREACH_ISSET
+macro can be used to iterate over all set bits in
+.Fa bitset .
+The index variable
+.Fa bit
+must have been declared with type
+.Ft int ,
+and upon each iteration
+.Fa bit
+is set to the index of successive set bits.
+The value of
+.Fa bit
+after the loop terminates is undefined.
+Similarly,
+.Fn BIT_FOREACH_ISCLR
+iterates over all clear bits in
+.Fa bitset .
+.Pp
+The
 .Fn BIT_COUNT
 macro returns the total number of set bits in
 .Fa bitset .
diff --git a/sys/sys/bitset.h b/sys/sys/bitset.h
index 2b5df78a8193..ab6eaf85b8df 100644
--- a/sys/sys/bitset.h
+++ b/sys/sys/bitset.h
@@ -271,6 +271,16 @@
 	__count;							\
 })
 
+/* Non-destructively loop over all set or clear bits in the set. */
+#define	_BIT_FOREACH(_s, i, p, op)					\
+	for (__size_t __i = 0; __i < __bitset_words(_s); __i++)		\
+		for (long __j = op((p)->__bits[__i]), __b = ffsl(__j);	\
+		    (i = (__b - 1) + __i * _BITSET_BITS), __j != 0;	\
+		    __j &= ~(1l << i), __b = ffsl(__j))
+
+#define	BIT_FOREACH_ISSET(_s, i, p)	_BIT_FOREACH(_s, i, p, )
+#define	BIT_FOREACH_ISCLR(_s, i, p)	_BIT_FOREACH(_s, i, p, ~)
+
 #define	BITSET_T_INITIALIZER(x)						\
 	{ .__bits = { x } }