Page MenuHomeFreeBSD
Differential D33312 Diff 101306 sys/sys/bitstring.h

Changeset View

Standalone View

View Options

sys/sys/bitstring.h

Show First 20 Lines • Show All 149 Lines • ▼ Show 20 Lines
/* clear bit N of bit string name */ /* clear bit N of bit string name */
static inline void static inline void
bit_clear(bitstr_t *_bitstr, int _bit) bit_clear(bitstr_t *_bitstr, int _bit)
{ {
_bitstr[_bit_idx(_bit)] &= ~_bit_mask(_bit); _bitstr[_bit_idx(_bit)] &= ~_bit_mask(_bit);
} }
/* Are bits in [start ... stop] in bit string all 0 or all 1? */
static inline int
bit_ntest(const bitstr_t *_bitstr, int _start, int _stop, int _match)
{
const bitstr_t *_stopbitstr;
bitstr_t _mask;
_mask = (_match == 0) ? 0 : _BITSTR_MASK;
_stopbitstr = _bitstr + _bit_idx(_stop);
_bitstr += _bit_idx(_start);
if (_bitstr == _stopbitstr)
return (0 == ((*_bitstr ^ _mask) &
_bit_make_mask(_start, _stop)));
if (_bit_offset(_start) != 0 &&
0 != ((*_bitstr++ ^ _mask) &
_bit_make_mask(_start, _BITSTR_BITS - 1)))
return (0);
if (_bit_offset(_stop) == _BITSTR_BITS - 1)
++_stopbitstr;
while (_bitstr < _stopbitstr) {
if (*_bitstr++ != _mask)
return (0);
}
return (_bit_offset(_stop) == _BITSTR_BITS - 1 ||
0 == ((*_stopbitstr ^ _mask) & _bit_make_mask(0, _stop)));
}
/* Set bits start ... stop inclusive in bit string. */ /* Set bits start ... stop inclusive in bit string. */
static inline void static inline void
bit_nset(bitstr_t *_bitstr, int _start, int _stop) bit_nset(bitstr_t *_bitstr, int _start, int _stop)
{ {
bitstr_t *_stopbitstr; bitstr_t *_stopbitstr;
_stopbitstr = _bitstr + _bit_idx(_stop); _stopbitstr = _bitstr + _bit_idx(_stop);
_bitstr += _bit_idx(_start); _bitstr += _bit_idx(_start);
if (_bitstr == _stopbitstr) { if (_bitstr == _stopbitstr) {
*_bitstr |= _bit_make_mask(_start, _stop); *_bitstr |= _bit_make_mask(_start, _stop);
} else { } else {
*_bitstr |= _bit_make_mask(_start, _BITSTR_BITS - 1); if (_bit_offset(_start) != 0)
while (++_bitstr < _stopbitstr) *_bitstr++ |= _bit_make_mask(_start, _BITSTR_BITS - 1);
*_bitstr = _BITSTR_MASK; if (_bit_offset(_stop) == _BITSTR_BITS - 1)
++_stopbitstr;
while (_bitstr < _stopbitstr)
*_bitstr++ = _BITSTR_MASK;
if (_bit_offset(_stop) != _BITSTR_BITS - 1)
*_stopbitstr |= _bit_make_mask(0, _stop); *_stopbitstr |= _bit_make_mask(0, _stop);
} }
} }
/* Clear bits start ... stop inclusive in bit string. */ /* Clear bits start ... stop inclusive in bit string. */
static inline void static inline void
bit_nclear(bitstr_t *_bitstr, int _start, int _stop) bit_nclear(bitstr_t *_bitstr, int _start, int _stop)
{ {
bitstr_t *_stopbitstr; bitstr_t *_stopbitstr;
_stopbitstr = _bitstr + _bit_idx(_stop); _stopbitstr = _bitstr + _bit_idx(_stop);
_bitstr += _bit_idx(_start); _bitstr += _bit_idx(_start);
if (_bitstr == _stopbitstr) { if (_bitstr == _stopbitstr) {
*_bitstr &= ~_bit_make_mask(_start, _stop); *_bitstr &= ~_bit_make_mask(_start, _stop);
} else { } else {
*_bitstr &= ~_bit_make_mask(_start, _BITSTR_BITS - 1); if (_bit_offset(_start) != 0)
while (++_bitstr < _stopbitstr) *_bitstr++ &= ~_bit_make_mask(_start, _BITSTR_BITS - 1);
*_bitstr = 0; if (_bit_offset(_stop) == _BITSTR_BITS - 1)
++_stopbitstr;
while (_bitstr < _stopbitstr)
*_bitstr++ = 0;
if (_bit_offset(_stop) != _BITSTR_BITS - 1)
*_stopbitstr &= ~_bit_make_mask(0, _stop); *_stopbitstr &= ~_bit_make_mask(0, _stop);
} }
} }
/* Find the first bit set in bit string at or after bit start. */ /* Find the first '_match'-bit in bit string at or after bit start. */
static inline void static inline void
bit_ffs_at(bitstr_t *_bitstr, int _start, int _nbits, int *_result) bit_ff_at(bitstr_t *_bitstr, int _start, int _nbits, int _match,
int *_result)
markjUnsubmitted
Not Done
Inline Actions

This function should be documented in bitstring.3.

markj: This function should be documented in bitstring.3.
{ {
bitstr_t *_curbitstr; bitstr_t *_curbitstr;
bitstr_t *_stopbitstr; bitstr_t *_stopbitstr;
bitstr_t _mask;
bitstr_t _test; bitstr_t _test;
int _value, _offset; int _value;
if (_start >= _nbits) { if (_start >= _nbits || _nbits <= 0) {
*_result = -1; *_result = -1;
return; return;
} }
if (_nbits > 0) {
_curbitstr = _bitstr + _bit_idx(_start); _curbitstr = _bitstr + _bit_idx(_start);
_stopbitstr = _bitstr + _bit_idx(_nbits - 1); _stopbitstr = _bitstr + _bit_idx(_nbits - 1);
_mask = _match ? 0 : _BITSTR_MASK;
_test = *_curbitstr; _test = _mask ^ *_curbitstr;
if (_bit_offset(_start) != 0) if (_bit_offset(_start) != 0)
_test &= _bit_make_mask(_start, _BITSTR_BITS - 1); _test &= _bit_make_mask(_start, _BITSTR_BITS - 1);
while (_test == 0 && _curbitstr < _stopbitstr) while (_test == 0 && _curbitstr < _stopbitstr)
_test = *(++_curbitstr); _test = _mask ^ *(++_curbitstr);
_offset = ffsl(_test); _value = ((_curbitstr - _bitstr) * _BITSTR_BITS) + ffsl(_test) - 1;
_value = ((_curbitstr - _bitstr) * _BITSTR_BITS) + _offset - 1; if (_test == 0 ||
if (_offset == 0 || _value >= _nbits) (_bit_offset(_nbits) != 0 && _value >= _nbits))
_value = -1; _value = -1;
} else {
_value = -1;
}
*_result = _value; *_result = _value;
} }
/* Find the first bit set in bit string at or after bit start. */
static inline void
bit_ffs_at(bitstr_t *_bitstr, int _start, int _nbits, int *_result)
{
bit_ff_at(_bitstr, _start, _nbits, 1, _result);
}
/* Find the first bit clear in bit string at or after bit start. */ /* Find the first bit clear in bit string at or after bit start. */
static inline void static inline void
bit_ffc_at(bitstr_t *_bitstr, int _start, int _nbits, int *_result) bit_ffc_at(bitstr_t *_bitstr, int _start, int _nbits, int *_result)
{ {
bitstr_t *_curbitstr; bit_ff_at(_bitstr, _start, _nbits, 0, _result);
bitstr_t *_stopbitstr;
bitstr_t _test;
int _value, _offset;
if (_start >= _nbits) {
*_result = -1;
return;
} }
if (_nbits > 0) {
_curbitstr = _bitstr + _bit_idx(_start);
_stopbitstr = _bitstr + _bit_idx(_nbits - 1);
_test = *_curbitstr;
if (_bit_offset(_start) != 0)
_test |= _bit_make_mask(0, _start - 1);
while (_test == _BITSTR_MASK && _curbitstr < _stopbitstr)
_test = *(++_curbitstr);
_offset = ffsl(~_test);
_value = ((_curbitstr - _bitstr) * _BITSTR_BITS) + _offset - 1;
if (_offset == 0 || _value >= _nbits)
_value = -1;
} else {
_value = -1;
}
*_result = _value;
}
/* Find the first bit set in bit string. */ /* Find the first bit set in bit string. */
static inline void static inline void
bit_ffs(bitstr_t *_bitstr, int _nbits, int *_result) bit_ffs(bitstr_t *_bitstr, int _nbits, int *_result)
{ {
bit_ffs_at(_bitstr, /*start*/0, _nbits, _result); bit_ffs_at(_bitstr, /*start*/0, _nbits, _result);
} }
/* Find the first bit clear in bit string. */ /* Find the first bit clear in bit string. */
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 '_match'-bits at or after start */
static inline void static inline void
bit_ffs_area_at(bitstr_t *_bitstr, int _start, int _nbits, int _size, bit_ff_area_at(bitstr_t *_bitstr, int _start, int _nbits, int _size,
int *_result) int _match, int *_result)
{ {
bitstr_t *_curbitstr; bitstr_t *_curbitstr, _mask, _test;
bitstr_t _test; int _value, _last, _shft, _maxshft;
int _value, _offset, _logsize, _b;
if (_start + _size > _nbits || _nbits <= 0) { if (_start + _size > _nbits || _nbits <= 0) {
*_result = -1; *_result = -1;
return; return;
} }
_logsize = fls(_size - 1); _mask = _match ? _BITSTR_MASK : 0;
_value = _start; _maxshft = _bit_idx(_size - 1) == 0 ? _size : _BITSTR_BITS;
_value = 0;
_curbitstr = _bitstr + _bit_idx(_start); _curbitstr = _bitstr + _bit_idx(_start);
_test = ~*_curbitstr; _test = ~(_BITSTR_MASK << _bit_offset(_start));
if (_bit_offset(_start) != 0) for (_last = _size - 1, _test |= _mask ^ *_curbitstr;
_test |= _bit_make_mask(0, _start - 1); !(_bit_idx(_last) == 0 &&
for (_offset = 0;; _offset -= _BITSTR_BITS, _test = ~*++_curbitstr) { (_test & _bit_make_mask(0, _last)) == 0);
if (_test != 0) { _last -= _BITSTR_BITS, _test = _mask ^ *++_curbitstr) {
/* If leading 0s in _test can finish 0-area, stop. */ if (_test == 0)
if (_offset + _size < (int)_BITSTR_BITS && continue;
(_test & _bit_make_mask(0, _offset + _size)) == 0) /* Shrink-left every 0-area in _test by maxshft-1 bits. */
break; for (_shft = _maxshft; _shft > 1 && (_test & (_test + 1)) != 0;
/* Shrink-left every 0-area in _test by size-1 bits. */ _shft = (_shft + 1) / 2)
_b = _logsize; _test |= _test >> _shft / 2;
while ((_test & (_test + 1)) != 0 && _b-- > 0)
_test |= _test >> (((_size - 1) >> _b) + 1) / 2;
/* Find the start of the first 0-area in _test. */ /* Find the start of the first 0-area in _test. */
_offset = (~_test == 0) ? (int)_BITSTR_BITS : _last = ffsl(~(_test >> 1));
ffsl(~_test) - 1; _value = (_curbitstr - _bitstr) * _BITSTR_BITS + _last;
_value = (_curbitstr - _bitstr) * _BITSTR_BITS +
_offset;
/* If there's insufficient space left, give up. */ /* If there's insufficient space left, give up. */
if (_value + _size > _nbits) { if (_value + _size > _nbits) {
_value = -1; _value = -1;
break; break;
} }
} _last += _size - 1;
if (_offset + _size <= (int)_BITSTR_BITS) /* If a solution is contained in _test, success! */
if (_bit_idx(_last) == 0)
break; break;
/* A solution here needs bits from the next word. */
} }
*_result = _value; *_result = _value;
} }
/* Find contiguous sequence of at least size cleared 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_ffc_area_at(bitstr_t *_bitstr, int _start, int _nbits, int _size, bit_ffs_area_at(bitstr_t *_bitstr, int _start, int _nbits, int _size,
int *_result) int *_result)
{ {
bitstr_t *_curbitstr; bit_ff_area_at(_bitstr, _start, _nbits, _size, 1, _result);
bitstr_t _test;
int _value, _offset, _logsize, _b;
if (_start + _size > _nbits || _nbits <= 0) {
*_result = -1;
return;
} }
_logsize = fls(_size - 1); /* Find contiguous sequence of at least size cleared bits at or after start */
_value = _start; static inline void
_curbitstr = _bitstr + _bit_idx(_start); bit_ffc_area_at(bitstr_t *_bitstr, int _start, int _nbits, int _size,
_test = *_curbitstr; int *_result)
if (_bit_offset(_start) != 0) {
_test |= _bit_make_mask(0, _start - 1); bit_ff_area_at(_bitstr, _start, _nbits, _size, 0, _result);
for (_offset = 0;; _offset -= _BITSTR_BITS, _test = *++_curbitstr) {
if (_test != 0) {
/* If leading 0s in _test can finish 0-area, stop. */
if (_offset + _size < (int)_BITSTR_BITS &&
(_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. */
_offset = (~_test == 0) ? (int)_BITSTR_BITS :
ffsl(~_test) - 1;
_value = (_curbitstr - _bitstr) * _BITSTR_BITS +
_offset;
/* If there's insufficient space left, give up. */
if (_value + _size > _nbits) {
_value = -1;
break;
}
}
if (_offset + _size <= (int)_BITSTR_BITS)
break;
}
*_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 61 Lines • Show Last 20 Lines