This is first cset for WL#1394 "Optimize index merge when all involved index ranges include only values with equal keys"

The main idea is to exploit the fact that key scans for "key=const" return ordered sequences of rowids.

2 files changed, 61 insertions, 0 deletions

diff --git a/mysys/my_bit.c b/mysys/my_bit.c
index 55dd72f5f76..01c9b5ea68d 100644
--- a/mysys/my_bit.c
+++ b/mysys/my_bit.c
@@ -71,3 +71,8 @@ uint my_count_bits(ulonglong v)
 #endif
 }
 
+uint my_count_bits_ushort(ushort v)
+{
+  return nbits[v];
+}
+
diff --git a/mysys/my_bitmap.c b/mysys/my_bitmap.c
index da16457c299..3c4caa413a9 100644
--- a/mysys/my_bitmap.c
+++ b/mysys/my_bitmap.c
@@ -330,3 +330,59 @@ void bitmap_union(MY_BITMAP *map, const MY_BITMAP *map2)
   bitmap_unlock(map);
 }
 
+
+/*
+  Get number of set bits in the bitmap 
+*/
+uint bitmap_bits_set(const MY_BITMAP *map)
+{  
+  uchar *m= map->bitmap,
+        *end= map->bitmap+map->bitmap_size;
+  uint res= 0;
+
+  DBUG_ASSERT(map->bitmap);
+
+  bitmap_lock((MY_BITMAP *)map);
+  while (m < end)
+  {
+    res+= my_count_bits_ushort(*m++);
+  }
+
+  bitmap_unlock((MY_BITMAP *)map);
+  return res;
+}
+
+
+/* 
+  Return number of first zero bit or MY_BIT_NONE if all bits are set.
+*/
+
+uint bitmap_get_first(const MY_BITMAP *map)
+{
+  uchar *bitmap=map->bitmap;
+  uint bit_found = MY_BIT_NONE;
+  uint bitmap_size=map->bitmap_size*8;
+  uint i;
+
+  DBUG_ASSERT(map->bitmap);
+  bitmap_lock((MY_BITMAP *)map);
+  for (i=0; i < bitmap_size ; i++, bitmap++)
+  {
+    if (*bitmap != 0xff)
+    {						/* Found slot with free bit */
+      uint b;
+      for (b=0; ; b++)
+      {
+	if (!(*bitmap & (1 << b)))
+	{
+	  bit_found = (i*8)+b;
+	  break;
+	}
+      }
+      break;					/* Found bit */
+    }
+  }
+  bitmap_unlock((MY_BITMAP *)map);
+  return bit_found;
+}
+