HomeFreeBSD

Change the implementation of bit_ffc_area_at so that, in the worst

Description

Change the implementation of bit_ffc_area_at so that, in the worst
case, the number of operations spent on each b-bit word is
proportional to lg b rather than b.

For one word, shrink all regions of 0-bits by size-1 bit positions in
no more than O(lg(min(b,size))) operations. In what remains, the first
0-bit is either the start of an area of sufficient size contained
within the original word, or the start of an area that could spill
over into the next word, and prove to be of sufficient size once the
start of that word is examined.

Change bit_ffs_area_at similarly.

Reviewed by: erj, jacob.e.keller_intel.com
MFC with: r354977
Differential Revision: https://reviews.freebsd.org/D22523

Details

Provenance
dougmAuthored on
Reviewer
erj
Differential Revision
D22523: Avoid finding every bit transition in bit_ffs_area_at
Parents
rS355376: caroot update to latest tip: one (1) addition, none (0) removed
Branches
Unknown
Tags
Unknown