Needs a sign-off.
I'm pretty sure that bitmap_equal() is wrong: doesn't it access one
past the end of the bitmap arrays?
I think that rightmost_1bit_idx() might make bitmap_scan() faster.
The nice thing about the previous implementations was that they were
obviously correct. Now, I'd prefer to have some tests.
On Sun, Jul 27, 2014 at 01:09:30PM +0800, Kmindg wrote:
> ---
> lib/bitmap.c | 36 ++++++++++++++++++++++++------------
> 1 file changed, 24 insertions(+), 12 deletions(-)
>
> diff --git a/lib/bitmap.c b/lib/bitmap.c
> index 7889aa1..b62a8be 100644
> --- a/lib/bitmap.c
> +++ b/lib/bitmap.c
> @@ -65,16 +65,17 @@ bool
> bitmap_equal(const unsigned long *a, const unsigned long *b, size_t n)
> {
> size_t i;
> + unsigned long mask = 1;
>
> if (memcmp(a, b, n / BITMAP_ULONG_BITS * sizeof(unsigned long))) {
> return false;
> }
> - for (i = ROUND_DOWN(n, BITMAP_ULONG_BITS); i < n; i++) {
> - if (bitmap_is_set(a, i) != bitmap_is_set(b, i)) {
> - return false;
> - }
> - }
> - return true;
> +
> + i = bitmap_n_longs(n);
> + mask <<= n % BITMAP_ULONG_BITS;
> + mask -= 1;
> +
> + return !mask || !((a[i] ^ b[i]) & mask);
> }
>
> /* Scans 'bitmap' from bit offset 'start' to 'end', excluding 'end' itself.
> @@ -84,15 +85,26 @@ size_t
> bitmap_scan(const unsigned long int *bitmap, bool target,
> size_t start, size_t end)
> {
> - /* XXX slow */
> - size_t i;
> -
> - for (i = start; i < end; i++) {
> - if (bitmap_is_set(bitmap, i) == target) {
> + size_t count = end - start;
> + unsigned long t = -(unsigned long)(!target);
> + for (; count && start % BITMAP_ULONG_BITS; count--,start++) {
> + if (bitmap_is_set(bitmap, start) == target) {
> + return start;
> + }
> + }
> + for (; count >= BITMAP_ULONG_BITS; count -= BITMAP_ULONG_BITS) {
> + if (*bitmap_unit__(bitmap, start) != t) {
> break;
> }
> + start += BITMAP_ULONG_BITS;
> + }
> + for (; count; count--,start++) {
> + if (bitmap_is_set(bitmap, start) == target) {
> + return start;
> + }
> }
> - return i;
> +
> + return start;
> }
>
> /* Returns the number of 1-bits in the 'n'-bit bitmap at 'bitmap'. */
> --
> 2.0.3
>
> _______________________________________________
> dev mailing list
> [email protected]
> http://openvswitch.org/mailman/listinfo/dev
_______________________________________________
dev mailing list
[email protected]
http://openvswitch.org/mailman/listinfo/dev
