maria-developers team mailing list archive
-
maria-developers team
-
Mailing list archive
-
Message #04397
Re: [Commits] Rev 3246: Fix bug lp:869036
Hi, Timour!
On Oct 21, timour@xxxxxxxxxxxx wrote:
I don't understand, why do you need map_ptr_array (working memory
provided by the caller). Looks like unnecessary complication to me.
I'd do something like
for (j= 0; j < bitmap_count; j++)
DBUG_ASSERT(end_bit < bitmap_array[j]->n_bits);
start_idx= start_bit/8/sizeof(my_bitmap_map);
end_idx= end_bit/8/sizeof(my_bitmap_map);
for (i= start_idx; i < end_idx; i++)
{
cur_res= ~0;
for (j= 0; cur_res && j < bitmap_count; j++)
cur_res &= bitmap_array[j]->bitmap[i];
if (cur_res)
return TRUE;
}
cur_res= last_word_mask(end_bit);
for (j= 0; cur_res && j < bitmap_count; j++)
cur_res &= bitmap_array[j]->bitmap[end_idx+1];
return cur_res != 0;
}
and created last_word_mask() function by extracting the relevant part of
create_last_word_mask() to a separate inline function.
Besides, it may be that your implementation has a bug - you use a last
word mask from the shortest bitmap, while you should've built it from
end_bit. Now you risk taking more bits into account that end_bit
dictates.
> === modified file 'mysys/my_bitmap.c'
> --- a/mysys/my_bitmap.c 2011-05-02 17:58:45 +0000
> +++ b/mysys/my_bitmap.c 2011-10-21 09:44:36 +0000
> @@ -410,6 +410,88 @@ void bitmap_intersect(MY_BITMAP *map, co
> }
> }
>
> +
> +/*
> + Check if there is some bit index between start_bit and end_bit, such that
> + this is bit is set for all bitmaps in bitmap_list.
> +
> + SYNOPSIS
> + bitmap_exists_intersection()
> + bitmpap_array [in] a set of MY_BITMAPs
> + map_ptr_array [in] wokring memory provided by the caller, same size as
> + bitmpap_array
> + bitmap_count [in] number of elements in bitmpap_array
> + start_bit [in] beginning (inclusive) of the range of bits to search
> + end_bit [in] end (inclusive) of the range of bits to search, must be
> + no bigger than the bits of the shortest bitmap.
> +
> + NOTES
> + This function assumes that for at least one of the bitmaps in bitmap_array all
> + bits outside the range [start_bit, end_bit] are 0. As a result is not
> + necessary to take care of the bits outside the range [start_bit, end_bit].
> +
> + RETURN
> + TRUE if an intersecion exists
> + FALSE no intersection
> +*/
> +
> +my_bool bitmap_exists_intersection(const MY_BITMAP **bitmap_array,
> + const my_bitmap_map **map_ptr_array,
> + uint bitmap_count,
> + uint start_bit, uint end_bit)
> +{
> + const MY_BITMAP *cur_bitmap;
> + my_bitmap_map cur_res, last_word_mask_inverted= 0;
> + uint i, j, min_n_bits= UINT_MAX;
> + uint end_word_idx= end_bit / 32;
> +
> + DBUG_ASSERT(bitmap_count && end_bit >= start_bit);
> + for (j= 0; j < bitmap_count; j++)
> + {
> + cur_bitmap= bitmap_array[j];
> + DBUG_ASSERT(end_bit <= cur_bitmap->n_bits);
> + /*
> + Get the word that contains 'start_bit' so that intersection begins
> + from that word instead of the first word of the bitmap.
> + */
> + map_ptr_array[j]= cur_bitmap->bitmap + start_bit / 32;
> + /*
> + Find and save the last_word_mask of the shortest bitmap that
> + contains end_bit in its last word.
> + */
> + if (no_words_in_map(bitmap_array[j]) - 1 == end_word_idx &&
> + bitmap_array[j]->n_bits < min_n_bits)
> + {
> + min_n_bits= bitmap_array[j]->n_bits;
> + last_word_mask_inverted= ~bitmap_array[j]->last_word_mask;
> + }
> + }
> +
> + /* Find the first word where the intersection of all bits is non-empty. */
> + for (i= 0; i <= end_word_idx; i++)
> + {
> + cur_res= 0xFFFFFFFF;
> + for (j= 0; j < bitmap_count; j++)
> + {
> + cur_res &= *(map_ptr_array[j]);
> + ++map_ptr_array[j];
> + }
> + /* Clear not relevant bits using the longest last_word_mask. */
> + if (last_word_mask_inverted && i == end_word_idx)
> + cur_res&= last_word_mask_inverted;
> + /*
> + If there is at least one non-zero bit, there was at least one sub-row
> + with all bits set, that is one NULL-subrow.
> + */
> + if (cur_res)
> + return TRUE;
> + }
> +
> + /* No intersection was found. */
> + return FALSE;
> +}
Regards,
Sergei