+ return !bitmap_contains (b, start, cnt, false);
+}
+\f
+/* Finding set or unset bits. */
+
+/* Finds and returns the starting index of a group of CNT
+ consecutive bits in B at or after START that are all set to
+ VALUE.
+ If there is no such group, returns BITMAP_ERROR. */
+size_t
+bitmap_scan (const struct bitmap *b, size_t start, size_t cnt, bool value)
+{
+ ASSERT (b != NULL);
+ ASSERT (start <= b->bit_cnt);
+
+ if (cnt <= b->bit_cnt)
+ {
+ size_t last = b->bit_cnt - cnt;
+ size_t middle = start + random_ulong () % (last - start + 1);
+ size_t i = middle;
+ do
+ {
+ if (!bitmap_contains (b, i, cnt, !value))
+ return i;
+ i = i != last ? i + 1 : start;
+ }
+ while (i != middle);
+ }
+ return BITMAP_ERROR;
+}
+
+/* Finds a group of CNT consecutive bits in B at or after
+ START that are all set to VALUE, flips them all to !VALUE,
+ and returns the index of the first bit in the group.
+ If there is no such group, returns BITMAP_ERROR.
+ If CNT is zero, returns 0.
+ Bits are set atomically, but testing bits is not atomic with
+ setting them. */
+size_t
+bitmap_scan_and_flip (struct bitmap *b, size_t start, size_t cnt, bool value)
+{
+ size_t idx = bitmap_scan (b, start, cnt, value);
+ if (idx != BITMAP_ERROR)
+ bitmap_set_multiple (b, idx, cnt, !value);
+ return idx;