Changeset View
Changeset View
Standalone View
Standalone View
sys/sys/bitstring.h
Show First 20 Lines • Show All 271 Lines • ▼ Show 20 Lines | |||||
static inline void | static inline void | ||||
bit_ffc(bitstr_t *_bitstr, int _nbits, int *_result) | bit_ffc(bitstr_t *_bitstr, int _nbits, int *_result) | ||||
{ | { | ||||
bit_ffc_at(_bitstr, /*start*/0, _nbits, _result); | bit_ffc_at(_bitstr, /*start*/0, _nbits, _result); | ||||
} | } | ||||
/* Find contiguous sequence of at least size set bits at or after start */ | /* Find contiguous sequence of at least size set bits at or after start */ | ||||
static inline void | static inline void | ||||
bit_ffs_area_at(bitstr_t *_bitstr, int _start, int _nbits, int _size, int *_result) | bit_ffs_area_at(bitstr_t *_bitstr, int _start, int _nbits, int _size, | ||||
int *_result) | |||||
{ | { | ||||
int _index, _end, _i; | bitstr_t *_curbitstr; | ||||
again: | bitstr_t _test; | ||||
/* Find the first set bit */ | int _value, _offset, _logsize, _b; | ||||
bit_ffs_at(_bitstr, _start, _nbits, &_index); | |||||
if (_index < 0) { | |||||
*_result = -1; | |||||
return; | |||||
} | |||||
/* Make sure there is enough room left in the bitstr */ | if (_start + _size > _nbits || _nbits <= 0) { | ||||
_end = _index + _size; | |||||
if (_end > _nbits) { | |||||
*_result = -1; | *_result = -1; | ||||
return; | return; | ||||
} | } | ||||
/* Find the next cleared bit starting at _index, stopping at _end */ | _logsize = fls(_size - 1); | ||||
bit_ffc_at(_bitstr, _index, _end, &_i); | _value = _start; | ||||
if (_i >= 0) { | _curbitstr = _bitstr + _bit_idx(_start); | ||||
/* we found a clear bit between _index and _end, so skip ahead | _test = ~*_curbitstr; | ||||
* to the next bit and try again | if (_bit_offset(_start) != 0) | ||||
_test |= _bit_make_mask(0, _start - 1); | |||||
_offset = 0; | |||||
for (;;) { | |||||
/* | |||||
* The current 0-area starts -_offset bits before _test start. | |||||
* If _test has enough leading 0s to finish 0-area, stop. | |||||
*/ | */ | ||||
_start = _i + 1; | if (_offset + _size < (int)_BITSTR_BITS && | ||||
goto again; | (_test & _bit_make_mask(0, _offset + _size)) == 0) | ||||
break; | |||||
/* Shrink-left every 0-area in _test by size-1 bits. */ | |||||
_b = _logsize; | |||||
while ((_test & (_test + 1)) != 0 && _b-- > 0) | |||||
_test |= _test >> ((((_size - 1) >> _b) + 1) / 2); | |||||
/* Find the start of the first 0-area in _test. */ | |||||
++_curbitstr; | |||||
if (_test == 0) | |||||
_offset -= _BITSTR_BITS; | |||||
else if (~_test == 0) | |||||
_offset = 0; | |||||
else | |||||
_offset = ffsl(~_test) - 1 - _BITSTR_BITS; | |||||
if (_test != 0) { | |||||
_value = ((_curbitstr - _bitstr) * _BITSTR_BITS) + | |||||
_offset; | |||||
/* If there's insufficient space left, give up. */ | |||||
if (_value + _size > _nbits) { | |||||
_value = -1; | |||||
break; | |||||
} | } | ||||
*_result = _index; | |||||
} | } | ||||
if (_offset + _size <= 0) | |||||
break; | |||||
_test = ~*_curbitstr; | |||||
} | |||||
*_result = _value; | |||||
} | |||||
/* Find contiguous sequence of at least size cleared bits at or after start */ | /* Find contiguous sequence of at least size cleared bits at or after start */ | ||||
static inline void | static inline void | ||||
bit_ffc_area_at(bitstr_t *_bitstr, int _start, int _nbits, int _size, int *_result) | bit_ffc_area_at(bitstr_t *_bitstr, int _start, int _nbits, int _size, | ||||
int *_result) | |||||
{ | { | ||||
int _index, _end, _i; | bitstr_t *_curbitstr; | ||||
again: | bitstr_t _test; | ||||
/* Find the first zero bit */ | int _value, _offset, _logsize, _b; | ||||
bit_ffc_at(_bitstr, _start, _nbits, &_index); | |||||
if (_index < 0) { | |||||
*_result = -1; | |||||
return; | |||||
} | |||||
/* Make sure there is enough room left in the bitstr */ | if (_start + _size > _nbits || _nbits <= 0) { | ||||
_end = _index + _size; | |||||
if (_end > _nbits) { | |||||
*_result = -1; | *_result = -1; | ||||
return; | return; | ||||
} | } | ||||
/* Find the next set bit starting at _index, stopping at _end */ | _logsize = fls(_size - 1); | ||||
bit_ffs_at(_bitstr, _index, _end, &_i); | _value = _start; | ||||
if (_i >= 0) { | _curbitstr = _bitstr + _bit_idx(_start); | ||||
/* we found a set bit between _index and _end, so skip ahead | _test = *_curbitstr; | ||||
* to the next bit and try again | if (_bit_offset(_start) != 0) | ||||
_test |= _bit_make_mask(0, _start - 1); | |||||
_offset = 0; | |||||
for (;;) { | |||||
/* | |||||
* The current 0-area starts -_offset bits before _test start. | |||||
* If _test has enough leading 0s to finish 0-area, stop. | |||||
*/ | */ | ||||
_start = _i + 1; | if (_offset + _size < (int)_BITSTR_BITS && | ||||
goto again; | (_test & _bit_make_mask(0, _offset + _size)) == 0) | ||||
break; | |||||
/* Shrink-left every 0-area in _test by size-1 bits. */ | |||||
_b = _logsize; | |||||
while ((_test & (_test + 1)) != 0 && _b-- > 0) | |||||
_test |= _test >> ((((_size - 1) >> _b) + 1) / 2); | |||||
/* Find the start of the first 0-area in _test. */ | |||||
++_curbitstr; | |||||
if (_test == 0) | |||||
_offset -= _BITSTR_BITS; | |||||
else if (~_test == 0) | |||||
_offset = 0; | |||||
else | |||||
_offset = ffsl(~_test) - 1 - _BITSTR_BITS; | |||||
if (_test != 0) { | |||||
_value = ((_curbitstr - _bitstr) * _BITSTR_BITS) + | |||||
_offset; | |||||
/* If there's insufficient space left, give up. */ | |||||
if (_value + _size > _nbits) { | |||||
_value = -1; | |||||
break; | |||||
} | } | ||||
*_result = _index; | } | ||||
if (_offset + _size <= 0) | |||||
break; | |||||
_test = *_curbitstr; | |||||
} | |||||
*_result = _value; | |||||
} | } | ||||
/* Find contiguous sequence of at least size set bits in bit string */ | /* Find contiguous sequence of at least size set bits in bit string */ | ||||
static inline void | static inline void | ||||
bit_ffs_area(bitstr_t *_bitstr, int _nbits, int _size, int *_result) | bit_ffs_area(bitstr_t *_bitstr, int _nbits, int _size, int *_result) | ||||
{ | { | ||||
bit_ffs_area_at(_bitstr, /*start*/0, _nbits, _size, _result); | bit_ffs_area_at(_bitstr, /*start*/0, _nbits, _size, _result); | ||||
} | } | ||||
▲ Show 20 Lines • Show All 45 Lines • Show Last 20 Lines |