Hi, Timour! On Oct 21, timour@askmonty.org 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