git: 8f559509a22b - stable/13 - bitstring(3): Add bitstring traversal macros.
Vladimir Kondratyev
wulf at FreeBSD.org
Mon Aug 23 22:26:21 UTC 2021
The branch stable/13 has been updated by wulf:
URL: https://cgit.FreeBSD.org/src/commit/?id=8f559509a22ba8725fa6ec50eca32313e5841fe2
commit 8f559509a22ba8725fa6ec50eca32313e5841fe2
Author: Vladimir Kondratyev <wulf at FreeBSD.org>
AuthorDate: 2021-08-16 20:18:58 +0000
Commit: Vladimir Kondratyev <wulf at FreeBSD.org>
CommitDate: 2021-08-23 22:23:10 +0000
bitstring(3): Add bitstring traversal macros.
The macro bit_foreach() traverses all set bits in the bitstring in the
forward direction, assigning each location in turn to variable.
The macro bit_foreach_at() traverses all set bits in the bitstring in
the forward direction at or after the zero-based bit index, assigning
each location in turn to variable.
The bit_foreach_unset() and bit_foreach_unset_at() macros which
traverses unset bits are implemented for completeness.
Reviewed by: asomers, dougm
(cherry picked from commit 14a4d6d01335dd233023834e05897377cb70d52a)
---
share/man/man3/bitstring.3 | 46 ++++++++-
sys/sys/bitstring.h | 16 ++++
tests/sys/sys/bitstring_test.c | 207 +++++++++++++++++++++++++++++++++++++++++
3 files changed, 268 insertions(+), 1 deletion(-)
diff --git a/share/man/man3/bitstring.3 b/share/man/man3/bitstring.3
index 20f5bae24d4d..e5be67a89e4f 100644
--- a/share/man/man3/bitstring.3
+++ b/share/man/man3/bitstring.3
@@ -58,7 +58,7 @@
.\" @(#)bitstring.3 8.1 (Berkeley) 7/19/93
.\" $FreeBSD$
.\"
-.Dd November 18, 2019
+.Dd August 8, 2021
.Dt BITSTRING 3
.Os
.Sh NAME
@@ -106,6 +106,10 @@
.Fn bit_ffc_area_at "bitstr_t *name" "int start" "int nbits" "int size" "int *value"
.Ft void
.Fn bit_ffs_area_at "bitstr_t *name" "int start" "int nbits" "int size" "int *value"
+.Fn bit_foreach "bitstr_t *name" "int nbits" "int var"
+.Fn bit_foreach_at "bitstr_t *name" "int start" "int nbits" "int var"
+.Fn bit_foreach_unset "bitstr_t *name" "int nbits" "int var"
+.Fn bit_foreach_unset_at "bitstr_t *name" "int start" "int nbits" "int var"
.Ft void
.Fn bit_nclear "bitstr_t *name" "int start" "int stop"
.Ft void
@@ -327,6 +331,46 @@ bits referenced by
at or after the zero-based bit index
.Fa start .
.Pp
+The macro
+.Fn bit_foreach
+traverses all set bits in the array of
+.Fa nbits
+referenced by
+.Fa name
+in the forward direction, assigning each location in turn to
+.Fa var .
+.Pp
+The macro
+.Fn bit_foreach_at
+traverses all set bits in the array of
+.Fa nbits
+referenced by
+.Fa name
+in the forward direction at or after the zero-based bit index
+.Fa start ,
+assigning each location in turn to
+.Fa var .
+.Pp
+The macro
+.Fn bit_foreach_unset
+traverses all unset bits in the array of
+.Fa nbits
+referenced by
+.Fa name
+in the forward direction, assigning each location in turn to
+.Fa var .
+.Pp
+The macro
+.Fn bit_foreach_unset_at
+traverses all unset bits in the array of
+.Fa nbits
+referenced by
+.Fa name
+in the forward direction at or after the zero-based bit index
+.Fa start ,
+assigning each location in turn to
+.Fa var .
+.Pp
The arguments in bit string macros are evaluated only once and may safely
have side effects.
.Sh EXAMPLES
diff --git a/sys/sys/bitstring.h b/sys/sys/bitstring.h
index 97b841bbdda6..f898a2392be6 100644
--- a/sys/sys/bitstring.h
+++ b/sys/sys/bitstring.h
@@ -419,4 +419,20 @@ out:
*_result = _value;
}
+/* Traverse all set bits, assigning each location in turn to iter */
+#define bit_foreach_at(_bitstr, _start, _nbits, _iter) \
+ for (bit_ffs_at((_bitstr), (_start), (_nbits), &(_iter)); \
+ (_iter) != -1; \
+ bit_ffs_at((_bitstr), (_iter) + 1, (_nbits), &(_iter)))
+#define bit_foreach(_bitstr, _nbits, _iter) \
+ bit_foreach_at(_bitstr, /*start*/0, _nbits, _iter)
+
+/* Traverse all unset bits, assigning each location in turn to iter */
+#define bit_foreach_unset_at(_bitstr, _start, _nbits, _iter) \
+ for (bit_ffc_at((_bitstr), (_start), (_nbits), &(_iter)); \
+ (_iter) != -1; \
+ bit_ffc_at((_bitstr), (_iter) + 1, (_nbits), &(_iter)))
+#define bit_foreach_unset(_bitstr, _nbits, _iter) \
+ bit_foreach_unset_at(_bitstr, /*start*/0, _nbits, _iter)
+
#endif /* _SYS_BITSTRING_H_ */
diff --git a/tests/sys/sys/bitstring_test.c b/tests/sys/sys/bitstring_test.c
index 8fdc68ecf68e..c891a98645f8 100644
--- a/tests/sys/sys/bitstring_test.c
+++ b/tests/sys/sys/bitstring_test.c
@@ -601,6 +601,209 @@ BITSTRING_TC_DEFINE(bit_count)
}
+BITSTRING_TC_DEFINE(bit_foreach)
+/* bitstr_t *bitstr, int nbits, const char *memloc */
+{
+ int i, set_bit;
+
+ /* Empty bitstr */
+ memset(bitstr, 0x00, bitstr_size(nbits));
+ bit_foreach (bitstr, nbits, set_bit) {
+ atf_tc_fail("bit_foreach_%d_%s_%s: Failed at location %d",
+ nbits, "clear", memloc, set_bit);
+ }
+
+ /* Full bitstr */
+ i = 0;
+ memset(bitstr, 0xFF, bitstr_size(nbits));
+ bit_foreach(bitstr, nbits, set_bit) {
+ ATF_REQUIRE_MSG(set_bit == i,
+ "bit_foreach_%d_%s_%s: Failed on turn %d at location %d",
+ nbits, "set", memloc, i, set_bit);
+ i++;
+ }
+ ATF_REQUIRE_MSG(i == nbits,
+ "bit_foreach_%d_%s_%s: Invalid number of turns %d",
+ nbits, "set", memloc, i);
+
+ /* Alternating bitstr, starts with 0 */
+ i = 0;
+ memset(bitstr, 0xAA, bitstr_size(nbits));
+ bit_foreach(bitstr, nbits, set_bit) {
+ ATF_REQUIRE_MSG(set_bit == i * 2 + 1,
+ "bit_foreach_%d_%s_%d_%s: "
+ "Failed on turn %d at location %d",
+ nbits, "alternating", 0, memloc, i, set_bit);
+ i++;
+ }
+ ATF_REQUIRE_MSG(i == nbits / 2,
+ "bit_foreach_%d_%s_%d_%s: Invalid number of turns %d",
+ nbits, "alternating", 0, memloc, i);
+
+ /* Alternating bitstr, starts with 1 */
+ i = 0;
+ memset(bitstr, 0x55, bitstr_size(nbits));
+ bit_foreach(bitstr, nbits, set_bit) {
+ ATF_REQUIRE_MSG(set_bit == i * 2,
+ "bit_foreach_%d_%s_%d_%s: "
+ "Failed on turn %d at location %d",
+ nbits, "alternating", 1, memloc, i, set_bit);
+ i++;
+ }
+ ATF_REQUIRE_MSG(i == (nbits + 1) / 2,
+ "bit_foreach_%d_%s_%d_%s: Invalid number of turns %d",
+ nbits, "alternating", 1, memloc, i);
+}
+
+BITSTRING_TC_DEFINE(bit_foreach_at)
+/* bitstr_t *bitstr, int nbits, const char *memloc */
+{
+ int i, s, e, set_bit;
+
+ /* Invalid _start value */
+ memset(bitstr, 0xFF, bitstr_size(nbits));
+ bit_foreach_at(bitstr, nbits, nbits, set_bit) {
+ atf_tc_fail("bit_foreach_at_%d_%s_%s: Failed at location %d",
+ nbits, "invalid_start", memloc, set_bit);
+ }
+
+ /* Varying start location */
+ memset(bitstr, 0xAA, bitstr_size(nbits));
+ for (s = 0; s < nbits; s++) {
+ i = 0;
+ bit_foreach_at(bitstr, s, nbits, set_bit) {
+ ATF_REQUIRE_MSG(set_bit == (i + s / 2) * 2 + 1,
+ "bit_foreach_at_%d_%s_%d_%s: "
+ "Failed on turn %d at location %d",
+ nbits, "vary_start", s, memloc, i, set_bit);
+ i++;
+ }
+ ATF_REQUIRE_MSG(i == nbits / 2 - s / 2,
+ "bit_foreach_at_%d_%s_%d_%s: Invalid number of turns %d",
+ nbits, "vary_start", s, memloc, i);
+ }
+
+ /* Varying end location */
+ memset(bitstr, 0xAA, bitstr_size(nbits));
+ for (e = 0; e < nbits; e++) {
+ i = 0;
+ bit_foreach_at(bitstr, 0, e, set_bit) {
+ ATF_REQUIRE_MSG(set_bit == i * 2 + 1,
+ "bit_foreach_at_%d_%s_%d_%s: "
+ "Failed on turn %d at location %d",
+ nbits, "vary_end", e, memloc, i, set_bit);
+ i++;
+ }
+ ATF_REQUIRE_MSG(i == e / 2,
+ "bit_foreach_at_%d_%s_%d_%s: Invalid number of turns %d",
+ nbits, "vary_end", e, memloc, i);
+ }
+}
+
+BITSTRING_TC_DEFINE(bit_foreach_unset)
+/* bitstr_t *bitstr, int nbits, const char *memloc */
+{
+ int i, unset_bit;
+
+ /* Empty bitstr */
+ i = 0;
+ memset(bitstr, 0, bitstr_size(nbits));
+ bit_foreach_unset(bitstr, nbits, unset_bit) {
+ ATF_REQUIRE_MSG(unset_bit == i,
+ "bit_foreach_unset_%d_%s_%s: "
+ "Failed on turn %d at location %d",
+ nbits, "clear", memloc, i, unset_bit);
+ i++;
+ }
+ ATF_REQUIRE_MSG(i == nbits,
+ "bit_foreach_unset_%d_%s_%s: Invalid number of turns %d",
+ nbits, "set", memloc, i);
+
+ /* Full bitstr */
+ memset(bitstr, 0xFF, bitstr_size(nbits));
+ bit_foreach_unset(bitstr, nbits, unset_bit) {
+ atf_tc_fail("bit_foreach_unset_%d_%s_%s: "
+ "Failed at location %d",
+ nbits, "set", memloc, unset_bit);
+ }
+
+ /* Alternating bitstr, starts with 0 */
+ i = 0;
+ memset(bitstr, 0xAA, bitstr_size(nbits));
+ bit_foreach_unset(bitstr, nbits, unset_bit) {
+ ATF_REQUIRE_MSG(unset_bit == i * 2,
+ "bit_foreach_unset_%d_%s_%d_%s: "
+ "Failed on turn %d at location %d",
+ nbits, "alternating", 0, memloc, i, unset_bit);
+ i++;
+ }
+ ATF_REQUIRE_MSG(i == (nbits + 1) / 2,
+ "bit_foreach_unset_%d_%s_%d_%s: Invalid number of turns %d",
+ nbits, "alternating", 0, memloc, i);
+
+ /* Alternating bitstr, starts with 1 */
+ i = 0;
+ memset(bitstr, 0x55, bitstr_size(nbits));
+ bit_foreach_unset(bitstr, nbits, unset_bit) {
+ ATF_REQUIRE_MSG(unset_bit == i * 2 + 1,
+ "bit_foreach_unset_%d_%s_%d_%s: "
+ "Failed on turn %d at location %d",
+ nbits, "alternating", 1, memloc, i, unset_bit);
+ i++;
+ }
+ ATF_REQUIRE_MSG(i == nbits / 2,
+ "bit_foreach_unset_%d_%s_%d_%s: Invalid number of turns %d",
+ nbits, "alternating", 1, memloc, i);
+}
+
+BITSTRING_TC_DEFINE(bit_foreach_unset_at)
+/* bitstr_t *bitstr, int nbits, const char *memloc */
+{
+ int i, s, e, unset_bit;
+
+ /* Invalid _start value */
+ memset(bitstr, 0, bitstr_size(nbits));
+ bit_foreach_unset_at(bitstr, nbits, nbits, unset_bit) {
+ atf_tc_fail("bit_foreach_unset_at_%d_%s_%s: "
+ "Failed at location %d",
+ nbits, "invalid_start", memloc, unset_bit);
+ }
+
+ /* Varying start location */
+ memset(bitstr, 0xAA, bitstr_size(nbits));
+ for (s = 0; s < nbits; s++) {
+ i = 0;
+ bit_foreach_unset_at(bitstr, s, nbits, unset_bit) {
+ ATF_REQUIRE_MSG(unset_bit == (i + (s + 1) / 2) * 2,
+ "bit_foreach_unset_at_%d_%s_%d_%s: "
+ "Failed on turn %d at location %d",
+ nbits, "vary_start", s, memloc, i, unset_bit);
+ i++;
+ }
+ ATF_REQUIRE_MSG(i == (nbits + 1) / 2 - (s + 1) / 2,
+ "bit_foreach_unset_at_%d_%s_%d_%s: "
+ "Invalid number of turns %d",
+ nbits, "vary_start", s, memloc, i);
+ }
+
+ /* Varying end location */
+ memset(bitstr, 0xAA, bitstr_size(nbits));
+ for (e = 0; e < nbits; e++) {
+ i = 0;
+ bit_foreach_unset_at(bitstr, 0, e, unset_bit) {
+ ATF_REQUIRE_MSG(unset_bit == i * 2,
+ "bit_foreach_unset_at_%d_%s_%d_%s: "
+ "Failed on turn %d at location %d",
+ nbits, "vary_end", e, memloc, i, unset_bit);
+ i++;
+ }
+ ATF_REQUIRE_MSG(i == (e + 1) / 2,
+ "bit_foreach_unset_at_%d_%s_%d_%s: "
+ "Invalid number of turns %d",
+ nbits, "vary_end", e, memloc, i);
+ }
+}
+
ATF_TP_ADD_TCS(tp)
{
@@ -619,6 +822,10 @@ ATF_TP_ADD_TCS(tp)
BITSTRING_TC_ADD(tp, bit_count);
BITSTRING_TC_ADD(tp, bit_ffs_area_no_match);
BITSTRING_TC_ADD(tp, bit_ffc_area_no_match);
+ BITSTRING_TC_ADD(tp, bit_foreach);
+ BITSTRING_TC_ADD(tp, bit_foreach_at);
+ BITSTRING_TC_ADD(tp, bit_foreach_unset);
+ BITSTRING_TC_ADD(tp, bit_foreach_unset_at);
return (atf_no_error());
}
More information about the dev-commits-src-all
mailing list