Page MenuHomeFreeBSD
Files F149928208

D33701.id100849.diff
No OneTemporary
Actions

D33701.id100849.diff
View Options

Index: share/man/man9/bitset.9
===================================================================
--- share/man/man9/bitset.9
+++ share/man/man9/bitset.9
@@ -42,9 +42,14 @@
.Nm BIT_SETOF ,
.Nm BIT_EMPTY ,
.Nm BIT_ISFULLSET ,
+.Nm BIT_FFC ,
+.Nm BIT_FFC_AT ,
.Nm BIT_FFS ,
.Nm BIT_FFS_AT ,
+.Nm BIT_FLC ,
+.Nm BIT_FLC_AT ,
.Nm BIT_FLS ,
+.Nm BIT_FLS_AT ,
.Nm BIT_FOREACH_ISSET ,
.Nm BIT_FOREACH_ISCLR ,
.Nm BIT_COUNT ,
@@ -89,11 +94,21 @@
.Ft bool
.Fn BIT_ISFULLSET "const SETSIZE" "struct STRUCTNAME *bitset"
.Ft long
+.Fn BIT_FFC "const SETSIZE" "struct STRUCTNAME *bitset"
+.Ft long
+.Fn BIT_FFC_AT "const SETSIZE" "struct STRUCTNAME *bitset" "long start"
+.Ft long
.Fn BIT_FFS "const SETSIZE" "struct STRUCTNAME *bitset"
.Ft long
.Fn BIT_FFS_AT "const SETSIZE" "struct STRUCTNAME *bitset" "long start"
.Ft long
+.Fn BIT_FLC "const SETSIZE" "struct STRUCTNAME *bitset"
+.Ft long
+.Fn BIT_FLC_AT "const SETSIZE" "struct STRUCTNAME *bitset" "long start"
+.Ft long
.Fn BIT_FLS "const SETSIZE" "struct STRUCTNAME *bitset"
+.Ft long
+.Fn BIT_FLS_AT "const SETSIZE" "struct STRUCTNAME *bitset" "long start"
.Fo BIT_FOREACH_ISSET
.Fa "const SETSIZE"
.Fa "size_t bit"
@@ -256,6 +271,16 @@
performs multiple individually atomic operations.)
.Pp
The
+.Fn BIT_ISSET
+macro returns
+.Dv true
+if the bit
+.Fa bit
+in the bitset pointed to by
+.Fa bitset
+is set.
+.Pp
+The
.Fn BIT_SET
macro sets bit
.Fa bit
@@ -305,6 +330,35 @@
is full (all bits set).
.Pp
The
+.Fn BIT_FFC
+macro returns the 1-index of the first (lowest) clear bit in
+.Fa bitset ,
+or zero if
+.Fa bitset
+is full.
+Like with
+.Xr ffs 3 ,
+to use the non-zero result of
+.Fn BIT_FFC
+as a
+.Fa bit
+index parameter to any other
+.Nm
+macro, you must subtract one from the result.
+.Pp
+The
+.Fn BIT_FFC_AT
+macro returns the 1-index of the first (lowest) clear bit in
+.Fa bitset ,
+which is greater than the given 0-indexed
+.Fa start ,
+or zero if no bits in
+.Fa bitset
+greater than
+.Fa start
+are clear.
+.Pp
+The
.Fn BIT_FFS
macro returns the 1-index of the first (lowest) set bit in
.Fa bitset ,
@@ -325,7 +379,7 @@
.Fn BIT_FFS_AT
macro returns the 1-index of the first (lowest) set bit in
.Fa bitset ,
-which is greater than the given 1-indexed
+which is greater than the given 0-indexed
.Fa start ,
or zero if no bits in
.Fa bitset
@@ -334,6 +388,35 @@
are set.
.Pp
The
+.Fn BIT_FLC
+macro returns the 1-index of the last (highest) clear bit in
+.Fa bitset ,
+or zero if
+.Fa bitset
+is full.
+Like with
+.Xr fls 3 ,
+to use the non-zero result of
+.Fn BIT_FLC
+as a
+.Fa bit
+index parameter to any other
+.Nm
+macro, you must subtract one from the result.
+.Pp
+The
+.Fn BIT_FLC_AT
+macro returns the 1-index of the last (highest) clear bit in
+.Fa bitset ,
+which is greater than the given 0-indexed
+.Fa start ,
+or zero if no bits in
+.Fa bitset
+greater than
+.Fa start
+are clear.
+.Pp
+The
.Fn BIT_FLS
macro returns the 1-index of the last (highest) set bit in
.Fa bitset ,
@@ -351,6 +434,18 @@
macro, you must subtract one from the result.
.Pp
The
+.Fn BIT_FLS_AT
+macro returns the 1-index of the last (highest) set bit in
+.Fa bitset ,
+which is greater than the given 0-indexed
+.Fa start ,
+or zero if no bits in
+.Fa bitset
+greater than
+.Fa start
+are set.
+.Pp
+The
.Fn BIT_FOREACH_ISSET
macro can be used to iterate over all set bits in
.Fa bitset .
Index: sys/sys/bitset.h
===================================================================
--- sys/sys/bitset.h
+++ sys/sys/bitset.h
@@ -222,45 +222,67 @@
} while (0)
/*
- * Note that `start` and the returned value from __BIT_FFS_AT are
- * 1-based bit indices.
+ * Note the returned value from __BIT_FFV_AT is a 1-based bit index.
*/
-#define __BIT_FFS_AT(_s, p, start) __extension__ ({ \
+#define __BIT_FFV_AT(_s, p, start, flip) __extension__ ({ \
__size_t __i; \
long __bit, __mask; \
\
- __mask = ~0UL << ((start) % _BITSET_BITS); \
__bit = 0; \
- for (__i = __bitset_word((_s), (start)); \
- __i < __bitset_words((_s)); \
- __i++) { \
- if (((p)->__bits[__i] & __mask) != 0) { \
- __bit = ffsl((p)->__bits[__i] & __mask); \
+ __i = __bitset_word((_s), (start)); \
+ if ((start) < (_s)) { \
+ __mask = ~0UL << ((start) % _BITSET_BITS); \
+ __mask &= (flip) ^ (p)->__bits[__i]; \
+ while (__mask == 0 && ++__i < __bitset_words((_s))) \
+ __mask = (flip) ^ (p)->__bits[__i]; \
+ if (__mask != 0 && (_s) % _BITSET_BITS != 0 && \
+ __i == __bitset_words((_s)) - 1) \
+ __mask = ~0UL >> (-(_s) & (_BITSET_BITS - 1)); \
+ if (__mask != 0) { \
+ __bit = ffsl(__mask); \
__bit += __i * _BITSET_BITS; \
- break; \
} \
- __mask = ~0UL; \
} \
__bit; \
})
+#define __BIT_FFC_AT(_s, p, start) __BIT_FFV_AT(_s, p, start, ~0UL)
+#define __BIT_FFC(_s, p) __BIT_FFC_AT((_s), (p), 0)
+
+#define __BIT_FFS_AT(_s, p, start) __BIT_FFV_AT(_s, p, start, 0UL)
#define __BIT_FFS(_s, p) __BIT_FFS_AT((_s), (p), 0)
-#define __BIT_FLS(_s, p) __extension__ ({ \
+/*
+ * Note the returned value from __BIT_FLV_AT is a 1-based bit index.
+ */
+#define __BIT_FLV_AT(_s, p, start, flip) __extension__ ({ \
__size_t __i; \
- long __bit; \
+ long __bit, __mask; \
\
__bit = 0; \
- for (__i = __bitset_words((_s)); __i > 0; __i--) { \
- if ((p)->__bits[__i - 1] != 0) { \
- __bit = flsl((p)->__bits[__i - 1]); \
- __bit += (__i - 1) * _BITSET_BITS; \
- break; \
+ __i = __bitset_words((_s)); \
+ if ((start) < (_s)) { \
+ __mask = ~0UL >> (-(_s) & (_BITSET_BITS - 1)); \
+ __mask &= (flip) ^ (p)->__bits[--__i]; \
+ while (__mask == 0 && __bitset_word((_s), (start)) < __i)\
+ __mask = (flip) ^ (p)->__bits[--__i]; \
+ if (__mask != 0 && (start) % _BITSET_BITS != 0 && \
+ __bitset_word((_s), (start)) == __i) \
+ __mask &= ~0UL << ((start) % _BITSET_BITS); \
+ if (__mask != 0) { \
+ __bit = flsl(__mask); \
+ __bit += __i * _BITSET_BITS; \
} \
} \
__bit; \
})
+#define __BIT_FLC_AT(_s, p, start) __BIT_FLV_AT((_s), (p), start, ~0UL)
+#define __BIT_FLC(_s, p) __BIT_FLC_AT((_s), (p), 0)
+
+#define __BIT_FLS_AT(_s, p, start) __BIT_FLV_AT((_s), (p), start, 0UL)
+#define __BIT_FLS(_s, p) __BIT_FLS_AT((_s), (p), 0)
+
#define __BIT_COUNT(_s, p) __extension__ ({ \
__size_t __i; \
long __count; \
@@ -324,10 +346,15 @@
#define BIT_COPY_STORE_REL(_s, f, t) __BIT_COPY_STORE_REL(_s, f, t)
#define BIT_COUNT(_s, p) __BIT_COUNT(_s, p)
#define BIT_EMPTY(_s, p) __BIT_EMPTY(_s, p)
+#define BIT_FFC(_s, p) __BIT_FFC(_s, p)
+#define BIT_FFC_AT(_s, p, start) __BIT_FFC_AT(_s, p, start)
#define BIT_FFS(_s, p) __BIT_FFS(_s, p)
#define BIT_FFS_AT(_s, p, start) __BIT_FFS_AT(_s, p, start)
#define BIT_FILL(_s, p) __BIT_FILL(_s, p)
+#define BIT_FLC(_s, p) __BIT_FLC(_s, p)
+#define BIT_FLC_AT(_s, p, start) __BIT_FLC_AT(_s, p, start)
#define BIT_FLS(_s, p) __BIT_FLS(_s, p)
+#define BIT_FLS_AT(_s, p, start) __BIT_FLS_AT(_s, p, start)
#define BIT_FOREACH(_s, i, p, op) __BIT_FOREACH(_s, i, p, op)
#define BIT_FOREACH_ADVANCE(_s, i, p, op) __BIT_FOREACH_ADVANCE(_s, i, p, op)
#define BIT_FOREACH_ISCLR(_s, i, p) __BIT_FOREACH_ISCLR(_s, i, p)
Index: tests/sys/sys/bitset_test.c
===================================================================
--- tests/sys/sys/bitset_test.c
+++ tests/sys/sys/bitset_test.c
@@ -67,7 +67,7 @@
_BIT_FOREACH_COUNT(256, &bsrand);
ATF_REQUIRE_MSG(setc + clrc == 256, "incorrect counts %d, %d",
setc, clrc);
-
+
/*
* Try to verify that we can safely clear bits in the set while
* iterating.
@@ -83,8 +83,106 @@
#undef _BIT_FOREACH_COUNT
}
+ATF_TC_WITHOUT_HEAD(bit_ffs);
+ATF_TC_BODY(bit_ffs, tc)
+{
+ struct bs256 bsrand;
+ int i, j;
+
+ BIT_ZERO(256, &bsrand);
+ for (i = 0; i < 256; i++)
+ if (random() % 2 != 0)
+ BIT_SET(256, i, &bsrand);
+
+ /*
+ * Try to verify that BIT_FFS_AT is correct
+ * for all start values.
+ */
+ for (i = 0; i < 256; i++) {
+ j = BIT_FFS_AT(256, &bsrand, i);
+ ATF_REQUIRE_MSG(i < j && j <= 256 || j == 0,
+ "out of range ffs value %d not in [%d, 256]", j, i);
+ if (j != 0) {
+ j--;
+ ATF_REQUIRE_MSG(BIT_ISSET(256, j, &bsrand),
+ "ffs[%d, 256] incorrect 0 ffs value %d", i, j);
+ } else
+ j = 256;
+ while (--j >= i)
+ ATF_REQUIRE_MSG(!BIT_ISSET(256, j, &bsrand),
+ "ffs[%d, 256] incorrect 1 ffs value %d", i, j);
+ }
+
+ /*
+ * Try to verify that BIT_FFS is correct
+ * for all size values.
+ */
+ for (i = 1; i <= 256; i++) {
+ j = BIT_FFS(i, &bsrand);
+ ATF_REQUIRE_MSG(0 <= j && j <= i,
+ "out of range ffs value %d not in [0, %d]", j, i);
+ if (j != 0) {
+ j--;
+ ATF_REQUIRE_MSG(BIT_ISSET(256, j, &bsrand),
+ "ffs[0, %d] incorrect 0 ffs value %d", i, j);
+ } else
+ j = i;
+ while (--j >= i)
+ ATF_REQUIRE_MSG(!BIT_ISSET(256, j, &bsrand),
+ "ffs[0, %d] incorrect 1 ffs value %d", i, j);
+ }
+}
+
+ATF_TC_WITHOUT_HEAD(bit_fls);
+ATF_TC_BODY(bit_fls, tc)
+{
+ struct bs256 bsrand;
+ int i, j;
+
+ BIT_ZERO(256, &bsrand);
+ for (i = 0; i < 256; i++)
+ if (random() % 2 != 0)
+ BIT_SET(256, i, &bsrand);
+
+ /*
+ * Try to verify that BIT_FLS_AT is correct
+ * for all start values.
+ */
+ for (i = 0; i < 256; i++) {
+ j = BIT_FLS_AT(256, &bsrand, i);
+ ATF_REQUIRE_MSG(i < j && j <= 256 || j == 0,
+ "out of range fls value %d not in [%d, 256]", j, i);
+ if (j != 0) {
+ ATF_REQUIRE_MSG(BIT_ISSET(256, j - 1, &bsrand),
+ "fls[%d, 256] incorrect 0 fls value %d", i, j - 1);
+ }
+ while (j++ < 256)
+ ATF_REQUIRE_MSG(!BIT_ISSET(256, j - 1, &bsrand),
+ "fls[%d, 256] incorrect 1 fls value %d", i, j - 1);
+ }
+
+ /*
+ * Try to verify that BIT_FLS is correct
+ * for all size values.
+ */
+ for (i = 1; i <= 256; i++) {
+ j = BIT_FLS(i, &bsrand);
+ ATF_REQUIRE_MSG(0 <= j && j <= i,
+ "out of range fls value %d not in [0, %d]", j, i);
+ if (j != 0) {
+ ATF_REQUIRE_MSG(BIT_ISSET(256, j - 1, &bsrand),
+ "fls[0, %d] incorrect 0 fls value %d", i, j - 1);
+ }
+ while (j++ < i)
+ ATF_REQUIRE_MSG(!BIT_ISSET(256, j - 1, &bsrand),
+ "fls[0, %d] incorrect 1 fls value %d", i, j - 1);
+ }
+}
+
ATF_TP_ADD_TCS(tp)
{
ATF_TP_ADD_TC(tp, bit_foreach);
+ ATF_TP_ADD_TC(tp, bit_ffs);
+ ATF_TP_ADD_TC(tp, bit_fls);
return (atf_no_error());
}

File Metadata

Mime Type
text/plain
Expires
Sun, Mar 29, 4:27 AM (3 h, 2 m)
Storage Engine
blob
Storage Format
Raw Data
Storage Handle
30509505
Default Alt Text
D33701.id100849.diff (10 KB)

Event Timeline