Date: Mon, 23 Aug 2021 22:26:20 GMT From: Vladimir Kondratyev <wulf@FreeBSD.org> To: src-committers@FreeBSD.org, dev-commits-src-all@FreeBSD.org, dev-commits-src-branches@FreeBSD.org Subject: git: 8f559509a22b - stable/13 - bitstring(3): Add bitstring traversal macros. Message-ID: <202108232226.17NMQK6e014858@gitrepo.freebsd.org>
next in thread | raw e-mail | index | archive | help
The branch stable/13 has been updated by wulf: URL: https://cgit.FreeBSD.org/src/commit/?id=8f559509a22ba8725fa6ec50eca32313e5841fe2 commit 8f559509a22ba8725fa6ec50eca32313e5841fe2 Author: Vladimir Kondratyev <wulf@FreeBSD.org> AuthorDate: 2021-08-16 20:18:58 +0000 Commit: Vladimir Kondratyev <wulf@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()); }
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?202108232226.17NMQK6e014858>