Index: share/man/man3/bitstring.3 =================================================================== --- share/man/man3/bitstring.3 +++ share/man/man3/bitstring.3 @@ -70,6 +70,10 @@ .Nm bit_ffs , .Nm bit_ffc_at , .Nm bit_ffs_at , +.Nm bit_ffc_area , +.Nm bit_ffs_area , +.Nm bit_ffc_area_at , +.Nm bit_ffs_area_at , .Nm bit_nclear , .Nm bit_nset , .Nm bit_set , @@ -95,6 +99,14 @@ .Ft void .Fn bit_ffs_at "bitstr_t *name" "int start" "int nbits" "int *value" .Ft void +.Fn bit_ffc_area "bitstr_t *name" "int nbits" "int size" "int *value" +.Ft void +.Fn bit_ffs_area "bitstr_t *name" "int nbits" "int size" "int *value" +.Ft void +.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" +.Ft void .Fn bit_nclear "bitstr_t *name" "int start" "int stop" .Ft void .Fn bit_nset "bitstr_t *name" "int start" "int stop" @@ -229,6 +241,82 @@ is set to \-1. .Pp The +.Fn bit_ffc_area +function stores the location referenced by +.Fa value +the zero-based number of the first bit beginning a sequence of unset bits of +at least +.Fa size +unset bits in the array of +.Fa nbits +bits referenced by +.Fa name . +If no sequence of contiguous unset bits of the specified +.Fa size +can be found, the location referenced by +.Fa value +is set to \-1. +.Pp +The +.Fn bit_ffs_area +function stores the location referenced by +.Fa value +the zero-based number of the first bit beginning a sequence of set bits of +at least +.Fa size +set bits in the array of +.Fa nbits +bits referenced by +.Fa name . +If no sequence of contiguous set bits of the specified +.Fa size +can be found, the location referenced by +.Fa value +is set to \-1. +.Pp +The +.Fn bit_ffc_area_at +function stores the location referenced by +.Fa value +the zero-based number of the first bit beginning a sequence of unset bits of +at least +.Fa size +unset bits in the array of +.Fa nbits +bits referenced by +.Fa name , +at or after the zero-based bit index +.Fa start . +If no sequence of contiguous unset bits of the specified +.Fa size +can be found at or after +.Fa start , +the location referenced by +.Fa value +is set to \-1. +.Pp +The +.Fn bit_ffs_area_at +function stores the location referenced by +.Fa value +the zero-based number of the first bit beginning a sequence of set bits of +at least +.Fa size +set bits in the array of +.Fa nbits +bits referenced by +.Fa name , +at or after the zero-based bit index +.Fa start . +If no sequence of contiguous set bits of the specified +.Fa size +can be found at or after +.Fa start , +the location referenced by +.Fa value +is set to \-1. +.Pp +The .Fn bit_count function stores in the location referenced by .Fa value Index: sys/sys/bitstring.h =================================================================== --- sys/sys/bitstring.h +++ sys/sys/bitstring.h @@ -265,6 +265,84 @@ bit_ffc_at(_bitstr, /*start*/0, _nbits, _result); } +/* Find contiguous sequence of at least size set bits at or after start */ +static inline void +bit_ffs_area_at(bitstr_t *_bitstr, int _start, int _nbits, int _size, int *_result) +{ + int _index, _end, _i; +again: + /* Find the first set bit */ + bit_ffs_at(_bitstr, _start, _nbits, &_index); + if (_index < 0) { + *_result = -1; + return; + } + + /* Make sure there is enough room left in the bitstr */ + _end = _index + _size; + if (_end > _nbits) { + *_result = -1; + return; + } + + /* Find the next cleared bit starting at _index, stopping at _end */ + bit_ffc_at(_bitstr, _index, _end, &_i); + if (!(_i < 0)) { + /* we found a clear bit between _index and _end, so skip ahead + * to the next bit and try again + */ + _start = _i + 1; + goto again; + } + *_result = _index; +} + +/* Find contiguous sequence of at least size cleared bits at or after start */ +static inline void +bit_ffc_area_at(bitstr_t *_bitstr, int _start, int _nbits, int _size, int *_result) +{ + int _index, _end, _i; +again: + /* Find the first zero bit */ + bit_ffc_at(_bitstr, _start, _nbits, &_index); + if (_index < 0) { + *_result = -1; + return; + } + + /* Make sure there is enough room left in the bitstr */ + _end = _index + _size; + if (_end > _nbits) { + *_result = -1; + return; + } + + /* Find the next set bit starting at _index, stopping at _end */ + bit_ffs_at(_bitstr, _index, _end, &_i); + if (!(_i < 0)) { + /* we found a set bit between _index and _end, so skip ahead + * to the next bit and try again + */ + _start = _i + 1; + goto again; + } + *_result = _index; +} + +/* Find contiguous sequence of at least size set bits in bit string */ +static inline void +bit_ffs_area(bitstr_t *_bitstr, int _nbits, int _size, int *_result) +{ + bit_ffs_area_at(_bitstr, /*start*/0, _nbits, _size, _result); +} + +/* Find contiguous sequence of at least size cleared bits in bit string */ +static inline void +bit_ffc_area(bitstr_t *_bitstr, int _nbits, int _size, int *_result) +{ + bit_ffc_area_at(_bitstr, /*start*/0, _nbits, _size, _result); +} + /* Count the number of bits set in a bitstr of size _nbits at or after _start */ static inline void bit_count(bitstr_t *_bitstr, int _start, int _nbits, int *_result) Index: sys/sys/param.h =================================================================== --- sys/sys/param.h +++ sys/sys/param.h @@ -60,7 +60,7 @@ * in the range 5 to 9. */ #undef __FreeBSD_version -#define __FreeBSD_version 1300057 /* Master, propagated to newvers */ +#define __FreeBSD_version 1300058 /* Master, propagated to newvers */ /* * __FreeBSD_kernel__ indicates that this system uses the kernel of FreeBSD, Index: tests/sys/sys/bitstring_test.c =================================================================== --- tests/sys/sys/bitstring_test.c +++ tests/sys/sys/bitstring_test.c @@ -299,6 +299,30 @@ } } +BITSTRING_TC_DEFINE(bit_ffc_area) +/* bitstr_t *bitstr, int nbits, const char *memloc */ +{ + int i; + int found_clear_bits; + + memset(bitstr, 0xFF, bitstr_size(nbits)); + bit_ffc_area(bitstr, nbits, &found_clear_bits)) + ATF_REQUIRE_MSG(found_clear_bit == -1, + "bit_ffc_area_%d_%s: Failed all set bits.", nbits, memloc); +} + +BITSTRING_TC_DEFINE(bit_ffs_area) +/* bitstr_t *bitstr, int nbits, const char *memloc */ +{ + int i; + int found_clear_bits; + + memset(bitstr, 0, bitstr_size(nbits)); + bit_ffs_area(bitstr, nbits, &found_clear_bits)) + ATF_REQUIRE_MSG(found_clear_bit == -1, + "bit_ffc_area_%d_%s: Failed all set bits.", nbits, memloc); +} + BITSTRING_TC_DEFINE(bit_nclear) /* bitstr_t *bitstr, int nbits, const char *memloc */ {