key_map with more that 64 bits width

sql/field.cc:
  typedef Bitmap<64> key_map
  all tests pass
sql/ha_berkeley.cc:
  typedef Bitmap<64> key_map
  all tests pass
sql/ha_berkeley.h:
  typedef Bitmap<64> key_map
  all tests pass
sql/item.cc:
  typedef Bitmap<64> key_map
  all tests pass
sql/item_func.cc:
  typedef Bitmap<64> key_map
  all tests pass
sql/opt_sum.cc:
  typedef Bitmap<64> key_map
  all tests pass
sql/sql_delete.cc:
  typedef Bitmap<64> key_map
  all tests pass
sql/sql_show.cc:
  typedef Bitmap<64> key_map
  all tests pass
sql/sql_test.cc:
  typedef Bitmap<64> key_map
  all tests pass
sql/sql_update.cc:
  typedef Bitmap<64> key_map
  all tests pass
include/my_bitmap.h:
  more bitmap methods
mysys/my_bitmap.c:
  more bitmap methods
sql/field.h:
  init bitmaps
sql/ha_innodb.h:
  optimization
sql/ha_isam.cc:
  optimization
sql/ha_myisam.cc:
  optimization
sql/ha_myisammrg.cc:
  optimization
sql/handler.h:
  optimization
sql/mysqld.cc:
  bitmap_init() interface changed
sql/opt_range.cc:
  optimization
sql/opt_range.h:
  optimization
sql/slave.cc:
  bitmap_init() interface changed
sql/sql_base.cc:
  optimization
sql/sql_select.cc:
  init bitmaps
  using const for bitmaps whenever possible
sql/sql_select.h:
  cleanup
sql/table.cc:
  always init bitmaps
BitKeeper/etc/ignore:
  Added sql/udf_example.so to the ignore list
sql/mysql_priv.h:
  use Bitmap over ulonglong by default

1 files changed, 175 insertions, 13 deletions

diff --git a/mysys/my_bitmap.c b/mysys/my_bitmap.c
index 8834dda98e1..70b15eaa1d8 100644
--- a/mysys/my_bitmap.c
+++ b/mysys/my_bitmap.c
@@ -27,7 +27,7 @@
 #include <assert.h>
 #include <m_string.h>
 
-inline void bitmap_lock(MY_BITMAP* map)
+inline void bitmap_lock(MY_BITMAP *map)
 {
 #ifdef THREAD
   if (map->thread_safe)
@@ -35,7 +35,7 @@ inline void bitmap_lock(MY_BITMAP* map)
 #endif
 }
 
-inline void bitmap_unlock(MY_BITMAP* map)
+inline void bitmap_unlock(MY_BITMAP *map)
 {
 #ifdef THREAD
   if (map->thread_safe)
@@ -43,9 +43,10 @@ inline void bitmap_unlock(MY_BITMAP* map)
 #endif
 }
 
-my_bool bitmap_init(MY_BITMAP *map, uint bitmap_size, my_bool thread_safe)
+my_bool bitmap_init(MY_BITMAP *map, uchar *buf, uint bitmap_size, my_bool thread_safe)
 {
-  if (!(map->bitmap=(uchar*) my_malloc((bitmap_size+7)/8,
+  if (!(map->bitmap=buf) &&
+      !(map->bitmap=(uchar*) my_malloc((bitmap_size+7)/8,
 				       MYF(MY_WME | MY_ZEROFILL))))
     return 1;
   DBUG_ASSERT(bitmap_size != ~(uint) 0);
@@ -72,6 +73,7 @@ void bitmap_free(MY_BITMAP *map)
 
 void bitmap_set_bit(MY_BITMAP *map, uint bitmap_bit)
 {
+  DBUG_ASSERT(map->bitmap);
   if (bitmap_bit < map->bitmap_size)
   {
     bitmap_lock(map);
@@ -80,7 +82,6 @@ void bitmap_set_bit(MY_BITMAP *map, uint bitmap_bit)
   }
 }
 
-
 uint bitmap_set_next(MY_BITMAP *map)
 {
   uchar *bitmap=map->bitmap;
@@ -88,6 +89,7 @@ uint bitmap_set_next(MY_BITMAP *map)
   uint bitmap_size=map->bitmap_size;
   uint i;
 
+  DBUG_ASSERT(map->bitmap);
   bitmap_lock(map);
   for (i=0; i < bitmap_size ; i++, bitmap++)
   {
@@ -110,9 +112,9 @@ uint bitmap_set_next(MY_BITMAP *map)
   return bit_found;
 }
 
-
 void bitmap_clear_bit(MY_BITMAP *map, uint bitmap_bit)
 {
+  DBUG_ASSERT(map->bitmap);
   if (bitmap_bit < map->bitmap_size)
   {
     bitmap_lock(map);
@@ -121,24 +123,184 @@ void bitmap_clear_bit(MY_BITMAP *map, uint bitmap_bit)
   }
 }
 
+void bitmap_set_prefix(MY_BITMAP *map, uint prefix_size)
+{
+  uint l, m;
+
+  DBUG_ASSERT(map->bitmap);
+  bitmap_lock(map);
+  set_if_smaller(prefix_size, map->bitmap_size);
+  if ((l=prefix_size / 8))
+    memset(map->bitmap, 0xff, l);
+  if ((m=prefix_size & 7))
+    map->bitmap[l++]= (1 << m)-1;
+  if (l < (m=(map->bitmap_size+7)/8))
+    bzero(map->bitmap+l, m-l);
+  bitmap_unlock(map);
+}
+
+void bitmap_clear_all(MY_BITMAP *map)
+{
+  bitmap_set_prefix(map, 0);
+}
+
+void bitmap_set_all(MY_BITMAP *map)
+{
+  bitmap_set_prefix(map, map->bitmap_size);
+}
 
-void bitmap_set_all(MY_BITMAP* map)
+my_bool bitmap_is_prefix(MY_BITMAP *map, uint prefix_size)
 {
+  uint l=prefix_size/8, m=prefix_size & 7, i, res=0;
+
+  DBUG_ASSERT(map->bitmap);
+  if (prefix_size > map->bitmap_size)
+    return 0;
+
   bitmap_lock(map);
-  memset(map->bitmap, 0xff, (map->bitmap_size+7)/8);
+  for (i=0; i < l; i++)
+    if (map->bitmap[i] != 0xff)
+      goto ret;
+
+  if (m && map->bitmap[i++] != (1 << m)-1)
+    goto ret;
+
+  for (m=(map->bitmap_size+7)/8; i < m; i++)
+    if (map->bitmap[i] != 0)
+      goto ret;
+
+  res=1;
+ret:
   bitmap_unlock(map);
+  return res;
+}
+
+my_bool bitmap_is_clear_all(MY_BITMAP *map)
+{
+  return bitmap_is_prefix(map, 0);
+}
+
+my_bool bitmap_is_set_all(MY_BITMAP *map)
+{
+  return bitmap_is_prefix(map, map->bitmap_size);
 }
 
-my_bool bitmap_is_set(MY_BITMAP* map, uint bitmap_bit)
+my_bool bitmap_is_set(MY_BITMAP *map, uint bitmap_bit)
 {
+  DBUG_ASSERT(map->bitmap);
   return (bitmap_bit < map->bitmap_size) ?
-    (map->bitmap[bitmap_bit / 8] & (1 << (bitmap_bit & 7))) :
-    0;
+    (map->bitmap[bitmap_bit / 8] & (1 << (bitmap_bit & 7))) : 0;
+}
+
+my_bool bitmap_is_subset(MY_BITMAP *map1, MY_BITMAP *map2)
+{
+  uint l1, l2, i, res=0;
+  uchar *m1=map1->bitmap, *m2=map2->bitmap;
+
+  DBUG_ASSERT(map1->bitmap);
+  DBUG_ASSERT(map2->bitmap);
+  bitmap_lock(map1);
+  bitmap_lock(map2);
+
+  l1=(map1->bitmap_size+7)/8;
+  l2=(map2->bitmap_size+7)/8;
+  set_if_smaller(l2, l1);
+
+  for (i=0; i < l2; i++)
+    if ((*m1++) & ~(*m2++))
+      goto ret;
+
+  for (; i < l1; i++)
+    if (*m1++)
+      goto ret;
+
+  res=1;
+ret:
+  bitmap_unlock(map2);
+  bitmap_unlock(map1);
+  return res;
+}
+
+my_bool bitmap_cmp(MY_BITMAP *map1, MY_BITMAP *map2)
+{
+  uint res;
+
+  DBUG_ASSERT(map1->bitmap);
+  DBUG_ASSERT(map2->bitmap);
+  bitmap_lock(map1);
+  bitmap_lock(map2);
+
+  res= map1->bitmap_size == map2->bitmap_size &&
+       memcmp(map1->bitmap, map2->bitmap, (map1->bitmap_size+7)/8)==0;
+
+  bitmap_unlock(map2);
+  bitmap_unlock(map1);
+  return res;
 }
 
-void bitmap_clear_all(MY_BITMAP* map)
+void bitmap_intersect(MY_BITMAP *map, MY_BITMAP *map2)
 {
+  uint l1, l2, i;
+  uchar *m=map->bitmap, *m2=map2->bitmap;
+
+  DBUG_ASSERT(map->bitmap);
+  DBUG_ASSERT(map2->bitmap);
   bitmap_lock(map);
-  bzero(map->bitmap,(map->bitmap_size+7)/8);
+  bitmap_lock(map2);
+
+  l1=(map->bitmap_size+7)/8;
+  l2=(map2->bitmap_size+7)/8;
+  set_if_smaller(l2, l1);
+
+  for (i=0; i < l2; i++)
+    *m++ &= *m2++;
+
+  if (l1 > l2)
+    bzero(m, l1-l2);
+
+  bitmap_unlock(map2);
   bitmap_unlock(map);
 }
+
+void bitmap_subtract(MY_BITMAP *map, MY_BITMAP *map2)
+{
+  uint l1, l2, i;
+  uchar *m=map->bitmap, *m2=map2->bitmap;
+
+  DBUG_ASSERT(map->bitmap);
+  DBUG_ASSERT(map2->bitmap);
+  bitmap_lock(map);
+  bitmap_lock(map2);
+
+  l1=(map->bitmap_size+7)/8;
+  l2=(map2->bitmap_size+7)/8;
+  set_if_smaller(l2, l1);
+
+  for (i=0; i < l2; i++)
+    *m++ &= ~(*m2++);
+
+  bitmap_unlock(map2);
+  bitmap_unlock(map);
+}
+
+void bitmap_union(MY_BITMAP *map, MY_BITMAP *map2)
+{
+  uint l1, l2, i;
+  uchar *m=map->bitmap, *m2=map2->bitmap;
+
+  DBUG_ASSERT(map->bitmap);
+  DBUG_ASSERT(map2->bitmap);
+  bitmap_lock(map);
+  bitmap_lock(map2);
+
+  l1=(map->bitmap_size+7)/8;
+  l2=(map2->bitmap_size+7)/8;
+  set_if_smaller(l2, l1);
+
+  for (i=0; i < l2; i++)
+    *m++ |= *m2++;
+
+  bitmap_unlock(map2);
+  bitmap_unlock(map);
+}
+