5.3->5.5 merge

1 files changed, 90 insertions, 0 deletions

diff --git a/mysys/my_bitmap.c b/mysys/my_bitmap.c
index 414d5acaaf0..8328efea8ac 100644
--- a/mysys/my_bitmap.c
+++ b/mysys/my_bitmap.c
@@ -96,6 +96,44 @@ void create_last_word_mask(MY_BITMAP *map)
 }
 
 
+static inline my_bitmap_map last_word_mask(uint bit)
+{
+  my_bitmap_map last_word_mask;
+  uint n_bits= bit + 1;
+  unsigned char const mask= invers_last_byte_mask(n_bits);
+
+  /*
+    The first bytes are to be set to zero since they represent real  bits
+    in the bitvector. The last bytes are set to 0xFF since they  represent
+    bytes not used by the bitvector. Finally the last byte contains  bits
+    as set by the mask above.
+  */
+  unsigned char *ptr= (unsigned char*)&last_word_mask;
+
+  switch ((n_bits + 7)/8 & 3) {
+  case 1:
+    last_word_mask= ~0U;
+    ptr[0]= mask;
+    break;
+  case 2:
+    last_word_mask= ~0U;
+    ptr[0]= 0;
+    ptr[1]= mask;
+    break;
+  case 3:
+    last_word_mask= 0U;
+    ptr[2]= mask;
+    ptr[3]= 0xFFU;
+    break;
+  case 0:
+    last_word_mask= 0U;
+    ptr[3]= mask;
+    break;
+  }
+  return last_word_mask;
+}
+
+
 static inline void bitmap_lock(MY_BITMAP *map __attribute__((unused)))
 {
   if (map->mutex)
@@ -380,6 +418,58 @@ void bitmap_intersect(MY_BITMAP *map, const MY_BITMAP *map2)
   }
 }
 
+
+/*
+  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
+    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,
+                                   uint bitmap_count,
+                                   uint start_bit, uint end_bit)
+{
+  uint i, j, start_idx, end_idx;
+  my_bitmap_map cur_res;
+
+  DBUG_ASSERT(bitmap_count && end_bit >= start_bit);
+  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];
+  return cur_res != 0;
+}
+
+
 /* True if union of bitmaps have all bits set */
 
 my_bool bitmap_union_is_set_all(const MY_BITMAP *map1, const MY_BITMAP *map2)