Page MenuHomeFreeBSD
Files F152108772

D31469.id93789.diff
No OneTemporary
Actions

D31469.id93789.diff
View Options

diff --git a/share/man/man3/bitstring.3 b/share/man/man3/bitstring.3
--- 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 @@
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
--- a/sys/sys/bitstring.h
+++ b/sys/sys/bitstring.h
@@ -419,4 +419,20 @@
*_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
--- a/tests/sys/sys/bitstring_test.c
+++ b/tests/sys/sys/bitstring_test.c
@@ -601,6 +601,209 @@
}
+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 @@
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());
}

File Metadata

Mime Type
text/plain
Expires
Mon, Apr 13, 7:01 PM (14 h, 24 m)
Storage Engine
blob
Storage Format
Raw Data
Storage Handle
31422210
Default Alt Text
D31469.id93789.diff (9 KB)

Event Timeline