[libvirt] [PATCH 26/34] util: bitmap: Introduce bitmap subtraction

[John Ferlan]

On 01/14/2016 11:27 AM, Peter Krempa wrote:
> Performs binary subtraction of two bitmaps. Stores result in the first
> operand.
> ---
>  src/libvirt_private.syms |  1 +
>  src/util/virbitmap.c     | 21 ++++++++++++++++++
>  src/util/virbitmap.h     |  3 +++
>  tests/virbitmaptest.c    | 55 ++++++++++++++++++++++++++++++++++++++++++++++++
>  4 files changed, 80 insertions(+)
> 
> diff --git a/src/libvirt_private.syms b/src/libvirt_private.syms
> index 9cebaeb..8213ff3 100644
> --- a/src/libvirt_private.syms
> +++ b/src/libvirt_private.syms
> @@ -1151,6 +1151,7 @@ virBitmapSetAll;
>  virBitmapSetBit;
>  virBitmapSize;
>  virBitmapString;
> +virBitmapSubtract;
>  virBitmapToData;
>  virBitmapToDataBuf;
> 
> diff --git a/src/util/virbitmap.c b/src/util/virbitmap.c
> index 57135a0..f116607 100644
> --- a/src/util/virbitmap.c
> +++ b/src/util/virbitmap.c
> @@ -859,3 +859,24 @@ virBitmapOverlaps(virBitmapPtr b1,
> 
>      return false;
>  }
> +
> +/**
> + * virBitmapSubtract:
> + * @a: minuend/result
> + * @b: subtrahend
> + *
> + * Performs bitwise subtraction: a = a - b
> + */
> +void
> +virBitmapSubtract(virBitmapPtr a,
> +                  virBitmapPtr b)
> +{
> +    size_t i;
> +    size_t max = a->map_len;
> +
> +    if (max > b->map_len)
> +        max = b->map_len;
> +
> +    for (i = 0; i < max; i++)
> +        a->map[i] &= ~b->map[i];
> +}
> diff --git a/src/util/virbitmap.h b/src/util/virbitmap.h
> index 47488de..846aca3 100644
> --- a/src/util/virbitmap.h
> +++ b/src/util/virbitmap.h
> @@ -129,4 +129,7 @@ bool virBitmapOverlaps(virBitmapPtr b1,
>                         virBitmapPtr b2)
>      ATTRIBUTE_NONNULL(1) ATTRIBUTE_NONNULL(2);
> 
> +void virBitmapSubtract(virBitmapPtr a, virBitmapPtr b)
> +    ATTRIBUTE_NONNULL(1) ATTRIBUTE_NONNULL(2);
> +
>  #endif
> diff --git a/tests/virbitmaptest.c b/tests/virbitmaptest.c
> index 8e458d2..967a5c8 100644
> --- a/tests/virbitmaptest.c
> +++ b/tests/virbitmaptest.c
> @@ -552,9 +552,55 @@ test10(const void *opaque ATTRIBUTE_UNUSED)
>      return ret;
>  }
> 
> +struct testBinaryOpData {
> +    const char *a;
> +    const char *b;
> +    const char *res;
> +};
> +
> +static int
> +test11(const void *opaque)
> +{
> +    const struct testBinaryOpData *data = opaque;
> +    virBitmapPtr amap = NULL;
> +    virBitmapPtr bmap = NULL;
> +    virBitmapPtr resmap = NULL;
> +    int ret = -1;
> +
> +    if (virBitmapParse(data->a, 0, &amap, 256) < 0 ||
> +        virBitmapParse(data->b, 0, &bmap, 256) < 0 ||
> +        virBitmapParse(data->res, 0, &resmap, 256) < 0)
> +        goto cleanup;
> +
> +    virBitmapSubtract(amap, bmap);
> +
> +    if (!virBitmapEqual(amap, resmap)) {
> +        fprintf(stderr, "\n bitmap subtraction failed: '%s'-'%s'!='%s'\n",
> +                data->a, data->b, data->res);
> +        goto cleanup;
> +    }
> +
> +    ret = 0;
> +
> + cleanup:
> +    virBitmapFree(amap);
> +    virBitmapFree(bmap);
> +    virBitmapFree(resmap);
> +
> +    return ret;
> +}
> +
> +#define TESTBINARYOP(A, B, RES, FUNC)                                         \
> +    testBinaryOpData.a = A;                                                   \
> +    testBinaryOpData.b = B;                                                   \
> +    testBinaryOpData.res = RES;                                               \
> +    if (virtTestRun(virtTestCounterNext(), FUNC, &testBinaryOpData) < 0)      \
> +        ret = -1;
> +
>  static int
>  mymain(void)
>  {
> +    struct testBinaryOpData testBinaryOpData;
>      int ret = 0;
> 
>      if (virtTestRun("test1", test1, NULL) < 0)
> @@ -578,6 +624,15 @@ mymain(void)
>      if (virtTestRun("test10", test10, NULL) < 0)
>          ret = -1;
> 
> +    virtTestCounterReset("test11-");
> +    TESTBINARYOP("0", "0", "0,^0", test11);
> +    TESTBINARYOP("0-3", "0", "1-3", test11);
> +    TESTBINARYOP("0-3", "0,3", "1-2", test11);
> +    TESTBINARYOP("0,^0", "0", "0,^0", test11);
> +    TESTBINARYOP("0-3", "0-3", "0,^0", test11);
> +    TESTBINARYOP("0-3", "0,^0", "0-3", test11);
> +    TESTBINARYOP("0,2", "1,3", "0,2", test11);
> +

0,^0 is "interesting" considering patches 22 & 23

Concept seems fine though... although I guess I'd "half expect" there
would be a need for "Add" as well as "Subtract".

Could be closer to 29/34 since that's where it's first used; however, I
see that 27...30 all are related, even though they seem to mix vcpu and
iothread callers...  Fine with it here... Just typing out loud again ;-)

John
>      return ret;
>  }
>