[11/18] hbitmap: Add @advance param to hbitmap_iter_next()

This new parameter allows the caller to just query the next dirty
position without moving the iterator.

Signed-off-by: Max Reitz <mreitz@redhat.com>
---
 include/qemu/hbitmap.h |  4 +++-
 block/dirty-bitmap.c   |  2 +-
 tests/test-hbitmap.c   | 26 +++++++++++++-------------
 util/hbitmap.c         | 10 +++++++---
 4 files changed, 24 insertions(+), 18 deletions(-)

13.09.2017 21:19, Max Reitz wrote:
> This new parameter allows the caller to just query the next dirty
> position without moving the iterator.
>
> Signed-off-by: Max Reitz <mreitz@redhat.com>
> ---
>   include/qemu/hbitmap.h |  4 +++-
>   block/dirty-bitmap.c   |  2 +-
>   tests/test-hbitmap.c   | 26 +++++++++++++-------------
>   util/hbitmap.c         | 10 +++++++---
>   4 files changed, 24 insertions(+), 18 deletions(-)
>
> diff --git a/include/qemu/hbitmap.h b/include/qemu/hbitmap.h
> index d3a74a21fc..6a52575ad5 100644
> --- a/include/qemu/hbitmap.h
> +++ b/include/qemu/hbitmap.h
> @@ -316,11 +316,13 @@ void hbitmap_free_meta(HBitmap *hb);
>   /**
>    * hbitmap_iter_next:
>    * @hbi: HBitmapIter to operate on.
> + * @advance: If true, advance the iterator.  Otherwise, the next call
> + *           of this function will return the same result.

it's not quit right, as hbitmap iterator allows concurrent resetting of 
bits, and in
this case next call may return some other result. (see f63ea4e92bad1db)

>    *
>    * Return the next bit that is set in @hbi's associated HBitmap,
>    * or -1 if all remaining bits are zero.
>    */
> -int64_t hbitmap_iter_next(HBitmapIter *hbi);
> +int64_t hbitmap_iter_next(HBitmapIter *hbi, bool advance);
>   
>   /**
>    * hbitmap_iter_next_word:
> diff --git a/block/dirty-bitmap.c b/block/dirty-bitmap.c
> index 30462d4f9a..aee57cf8c8 100644
> --- a/block/dirty-bitmap.c
> +++ b/block/dirty-bitmap.c
> @@ -547,7 +547,7 @@ void bdrv_dirty_iter_free(BdrvDirtyBitmapIter *iter)
>   
>   int64_t bdrv_dirty_iter_next(BdrvDirtyBitmapIter *iter)
>   {
> -    return hbitmap_iter_next(&iter->hbi);
> +    return hbitmap_iter_next(&iter->hbi, true);
>   }
>   
>   /* Called within bdrv_dirty_bitmap_lock..unlock */
> diff --git a/tests/test-hbitmap.c b/tests/test-hbitmap.c
> index 1acb353889..e6d4d563cb 100644
> --- a/tests/test-hbitmap.c
> +++ b/tests/test-hbitmap.c
> @@ -46,7 +46,7 @@ static void hbitmap_test_check(TestHBitmapData *data,
>   
>       i = first;
>       for (;;) {
> -        next = hbitmap_iter_next(&hbi);
> +        next = hbitmap_iter_next(&hbi, true);
>           if (next < 0) {
>               next = data->size;
>           }
> @@ -435,25 +435,25 @@ static void test_hbitmap_iter_granularity(TestHBitmapData *data,
>       /* Note that hbitmap_test_check has to be invoked manually in this test.  */
>       hbitmap_test_init(data, 131072 << 7, 7);
>       hbitmap_iter_init(&hbi, data->hb, 0);
> -    g_assert_cmpint(hbitmap_iter_next(&hbi), <, 0);
> +    g_assert_cmpint(hbitmap_iter_next(&hbi, true), <, 0);
>   
>       hbitmap_test_set(data, ((L2 + L1 + 1) << 7) + 8, 8);
>       hbitmap_iter_init(&hbi, data->hb, 0);
> -    g_assert_cmpint(hbitmap_iter_next(&hbi), ==, (L2 + L1 + 1) << 7);
> -    g_assert_cmpint(hbitmap_iter_next(&hbi), <, 0);
> +    g_assert_cmpint(hbitmap_iter_next(&hbi, true), ==, (L2 + L1 + 1) << 7);
> +    g_assert_cmpint(hbitmap_iter_next(&hbi, true), <, 0);
>   
>       hbitmap_iter_init(&hbi, data->hb, (L2 + L1 + 2) << 7);
> -    g_assert_cmpint(hbitmap_iter_next(&hbi), <, 0);
> +    g_assert_cmpint(hbitmap_iter_next(&hbi, true), <, 0);
>   
>       hbitmap_test_set(data, (131072 << 7) - 8, 8);
>       hbitmap_iter_init(&hbi, data->hb, 0);
> -    g_assert_cmpint(hbitmap_iter_next(&hbi), ==, (L2 + L1 + 1) << 7);
> -    g_assert_cmpint(hbitmap_iter_next(&hbi), ==, 131071 << 7);
> -    g_assert_cmpint(hbitmap_iter_next(&hbi), <, 0);
> +    g_assert_cmpint(hbitmap_iter_next(&hbi, true), ==, (L2 + L1 + 1) << 7);
> +    g_assert_cmpint(hbitmap_iter_next(&hbi, true), ==, 131071 << 7);
> +    g_assert_cmpint(hbitmap_iter_next(&hbi, true), <, 0);
>   
>       hbitmap_iter_init(&hbi, data->hb, (L2 + L1 + 2) << 7);
> -    g_assert_cmpint(hbitmap_iter_next(&hbi), ==, 131071 << 7);
> -    g_assert_cmpint(hbitmap_iter_next(&hbi), <, 0);
> +    g_assert_cmpint(hbitmap_iter_next(&hbi, true), ==, 131071 << 7);
> +    g_assert_cmpint(hbitmap_iter_next(&hbi, true), <, 0);
>   }
>   
>   static void hbitmap_test_set_boundary_bits(TestHBitmapData *data, ssize_t diff)
> @@ -893,7 +893,7 @@ static void test_hbitmap_serialize_zeroes(TestHBitmapData *data,
>       for (i = 0; i < num_positions; i++) {
>           hbitmap_deserialize_zeroes(data->hb, positions[i], min_l1, true);
>           hbitmap_iter_init(&iter, data->hb, 0);
> -        next = hbitmap_iter_next(&iter);
> +        next = hbitmap_iter_next(&iter, true);
>           if (i == num_positions - 1) {
>               g_assert_cmpint(next, ==, -1);
>           } else {
> @@ -919,10 +919,10 @@ static void test_hbitmap_iter_and_reset(TestHBitmapData *data,
>   
>       hbitmap_iter_init(&hbi, data->hb, BITS_PER_LONG - 1);
>   
> -    hbitmap_iter_next(&hbi);
> +    hbitmap_iter_next(&hbi, true);
>   
>       hbitmap_reset_all(data->hb);
> -    hbitmap_iter_next(&hbi);
> +    hbitmap_iter_next(&hbi, true);
>   }
>   
>   int main(int argc, char **argv)
> diff --git a/util/hbitmap.c b/util/hbitmap.c
> index 21535cc90b..96525983ce 100644
> --- a/util/hbitmap.c
> +++ b/util/hbitmap.c
> @@ -141,7 +141,7 @@ unsigned long hbitmap_iter_skip_words(HBitmapIter *hbi)
>       return cur;
>   }
>   
> -int64_t hbitmap_iter_next(HBitmapIter *hbi)
> +int64_t hbitmap_iter_next(HBitmapIter *hbi, bool advance)
>   {
>       unsigned long cur = hbi->cur[HBITMAP_LEVELS - 1] &
>               hbi->hb->levels[HBITMAP_LEVELS - 1][hbi->pos];
> @@ -154,8 +154,12 @@ int64_t hbitmap_iter_next(HBitmapIter *hbi)
>           }
>       }
>   
> -    /* The next call will resume work from the next bit.  */
> -    hbi->cur[HBITMAP_LEVELS - 1] = cur & (cur - 1);
> +    if (advance) {
> +        /* The next call will resume work from the next bit.  */
> +        hbi->cur[HBITMAP_LEVELS - 1] = cur & (cur - 1);
> +    } else {
> +        hbi->cur[HBITMAP_LEVELS - 1] = cur;
> +    }
>       item = ((uint64_t)hbi->pos << BITS_PER_LEVEL) + ctzl(cur);
>   
>       return item << hbi->granularity;

On 2017-09-25 17:38, Vladimir Sementsov-Ogievskiy wrote:
> 13.09.2017 21:19, Max Reitz wrote:
>> This new parameter allows the caller to just query the next dirty
>> position without moving the iterator.
>>
>> Signed-off-by: Max Reitz <mreitz@redhat.com>
>> ---
>>   include/qemu/hbitmap.h |  4 +++-
>>   block/dirty-bitmap.c   |  2 +-
>>   tests/test-hbitmap.c   | 26 +++++++++++++-------------
>>   util/hbitmap.c         | 10 +++++++---
>>   4 files changed, 24 insertions(+), 18 deletions(-)
>>
>> diff --git a/include/qemu/hbitmap.h b/include/qemu/hbitmap.h
>> index d3a74a21fc..6a52575ad5 100644
>> --- a/include/qemu/hbitmap.h
>> +++ b/include/qemu/hbitmap.h
>> @@ -316,11 +316,13 @@ void hbitmap_free_meta(HBitmap *hb);
>>   /**
>>    * hbitmap_iter_next:
>>    * @hbi: HBitmapIter to operate on.
>> + * @advance: If true, advance the iterator.  Otherwise, the next call
>> + *           of this function will return the same result.
> 
> it's not quit right, as hbitmap iterator allows concurrent resetting of
> bits, and in
> this case next call may return some other result. (see f63ea4e92bad1db)

Ah, right!  I think it should still be useful for what I (currently)
need in patch 12, I would just need a different description then.

(Like "...will return the same result (if that position is still dirty).")

Max