git: dfd3bde5775e - main - bitset(9): Introduce BIT_FOREACH_ISSET and BIT_FOREACH_ISCLR
Mark Johnston
markj at FreeBSD.org
Tue Sep 21 16:09:20 UTC 2021
The branch main has been updated by markj:
URL: https://cgit.FreeBSD.org/src/commit/?id=dfd3bde5775ecf88851d5dffd6a8ed6076b53566
commit dfd3bde5775ecf88851d5dffd6a8ed6076b53566
Author: Mark Johnston <markj at FreeBSD.org>
AuthorDate: 2021-09-21 15:32:23 +0000
Commit: Mark Johnston <markj at FreeBSD.org>
CommitDate: 2021-09-21 16:07:39 +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
MFC after: 2 weeks
Sponsored by: The FreeBSD Foundation
Differential Revision: https://reviews.freebsd.org/D32028
---
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 30632e0a6cb6..49601b9b7f48 100644
--- a/share/man/man9/Makefile
+++ b/share/man/man9/Makefile
@@ -623,6 +623,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 } }
More information about the dev-commits-src-all
mailing list