maria-developers team mailing list archive

[Sergei Golubchik <serg@xxxxxxxxxxxx>]

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