ffu: find first unset >= bit. */
| 239 | |
| 240 | /* ffu: find first unset >= bit. */ |
| 241 | static inline size_t |
| 242 | bitmap_ffu(const bitmap_t *bitmap, const bitmap_info_t *binfo, size_t min_bit) { |
| 243 | assert(min_bit < binfo->nbits); |
| 244 | |
| 245 | #ifdef BITMAP_USE_TREE |
| 246 | size_t bit = 0; |
| 247 | for (unsigned level = binfo->nlevels; level--;) { |
| 248 | size_t lg_bits_per_group = (LG_BITMAP_GROUP_NBITS * (level + |
| 249 | 1)); |
| 250 | bitmap_t group = bitmap[binfo->levels[level].group_offset + (bit |
| 251 | >> lg_bits_per_group)]; |
| 252 | unsigned group_nmask = (unsigned)(((min_bit > bit) ? (min_bit - |
| 253 | bit) : 0) >> (lg_bits_per_group - LG_BITMAP_GROUP_NBITS)); |
| 254 | assert(group_nmask <= BITMAP_GROUP_NBITS); |
| 255 | bitmap_t group_mask = ~((1LU << group_nmask) - 1); |
| 256 | bitmap_t group_masked = group & group_mask; |
| 257 | if (group_masked == 0LU) { |
| 258 | if (group == 0LU) { |
| 259 | return binfo->nbits; |
| 260 | } |
| 261 | /* |
| 262 | * min_bit was preceded by one or more unset bits in |
| 263 | * this group, but there are no other unset bits in this |
| 264 | * group. Try again starting at the first bit of the |
| 265 | * next sibling. This will recurse at most once per |
| 266 | * non-root level. |
| 267 | */ |
| 268 | size_t sib_base = bit + (ZU(1) << lg_bits_per_group); |
| 269 | assert(sib_base > min_bit); |
| 270 | assert(sib_base > bit); |
| 271 | if (sib_base >= binfo->nbits) { |
| 272 | return binfo->nbits; |
| 273 | } |
| 274 | return bitmap_ffu(bitmap, binfo, sib_base); |
| 275 | } |
| 276 | bit += ((size_t)(ffs_lu(group_masked) - 1)) << |
| 277 | (lg_bits_per_group - LG_BITMAP_GROUP_NBITS); |
| 278 | } |
| 279 | assert(bit >= min_bit); |
| 280 | assert(bit < binfo->nbits); |
| 281 | return bit; |
| 282 | #else |
| 283 | size_t i = min_bit >> LG_BITMAP_GROUP_NBITS; |
| 284 | bitmap_t g = bitmap[i] & ~((1LU << (min_bit & BITMAP_GROUP_NBITS_MASK)) |
| 285 | - 1); |
| 286 | size_t bit; |
| 287 | do { |
| 288 | bit = ffs_lu(g); |
| 289 | if (bit != 0) { |
| 290 | return (i << LG_BITMAP_GROUP_NBITS) + (bit - 1); |
| 291 | } |
| 292 | i++; |
| 293 | g = bitmap[i]; |
| 294 | } while (i < binfo->ngroups); |
| 295 | return binfo->nbits; |
| 296 | #endif |
| 297 | } |
| 298 |