1 files changed, 161 insertions, 154 deletions

diff --git a/mysys/my_bitmap.c b/mysys/my_bitmap.c
index 47646feab79..414d5acaaf0 100644
--- a/mysys/my_bitmap.c
+++ b/mysys/my_bitmap.c
@@ -1,5 +1,6 @@
 /*
-   Copyright (c) 2001, 2011, Oracle and/or its affiliates. All rights reserved.
+   Copyright (c) 2001, 2011, Oracle and/or its affiliates.
+   Copyright (C) 2009, 2011, Monty Program Ab
 
    This program is free software; you can redistribute it and/or modify
    it under the terms of the GNU General Public License as published by
@@ -22,14 +23,13 @@
 
     * the internal size is a set of 32 bit words
     * the number of bits specified in creation can be any number > 0
-    * there are THREAD safe versions of most calls called bitmap_lock_*
 
   TODO:
-  Make assembler THREAD safe versions of these using test-and-set instructions
+  Make assembler thread safe versions of these using test-and-set instructions
 
   Original version created by Sergei Golubchik 2001 - 2004.
   New version written and test program added and some changes to the interface
-  was made by Mikael Ronström 2005, with assistance of Tomas Ulin and Mats
+  was made by Mikael Ronstrom 2005, with assistance of Tomas Ulin and Mats
   Kindahl.
 */
 
@@ -38,16 +38,31 @@
 #include <m_string.h>
 #include <my_bit.h>
 
-void create_last_word_mask(MY_BITMAP *map)
+
+/* Create a mask of the significant bits for the last byte (1,3,7,..255) */
+
+static inline uchar last_byte_mask(uint bits)
 {
-  /* Get the number of used bits (1..8) in the last byte */
-  unsigned int const used= 1U + ((map->n_bits-1U) & 0x7U);
+  /* Get the number of used bits-1 (0..7) in the last byte */
+  unsigned int const used= (bits - 1U) & 7U;
+  /* Return bitmask for the significant bits */
+  return ((2U << used) - 1);
+}
+
+/*
+  Create a mask with the upper 'unused' bits set and the lower 'used'
+  bits clear. The bits within each byte is stored in big-endian order.
+*/
+
+static inline uchar invers_last_byte_mask(uint bits)
+{
+  return last_byte_mask(bits) ^ 255;
+}
 
-  /*
-    Create a mask with the upper 'unused' bits set and the lower 'used'
-    bits clear. The bits within each byte is stored in big-endian order.
-   */
-  unsigned char const mask= (~((1 << used) - 1)) & 255;
+
+void create_last_word_mask(MY_BITMAP *map)
+{
+  unsigned char const mask= invers_last_byte_mask(map->n_bits);
 
   /*
     The first bytes are to be set to zero since they represent real  bits
@@ -87,7 +102,6 @@ static inline void bitmap_lock(MY_BITMAP *map __attribute__((unused)))
     mysql_mutex_lock(map->mutex);
 }
 
-
 static inline void bitmap_unlock(MY_BITMAP *map __attribute__((unused)))
 {
   if (map->mutex)
@@ -95,46 +109,6 @@ static inline void bitmap_unlock(MY_BITMAP *map __attribute__((unused)))
 }
 
 
-static inline uint get_first_set(uint32 value, uint word_pos)
-{
-  uchar *byte_ptr= (uchar*)&value;
-  uchar byte_value;
-  uint byte_pos, bit_pos;
-
-  for (byte_pos=0; byte_pos < 4; byte_pos++, byte_ptr++)
-  {
-    byte_value= *byte_ptr;
-    if (byte_value)
-    {
-      for (bit_pos=0; ; bit_pos++)
-        if (byte_value & (1 << bit_pos))
-          return (word_pos*32) + (byte_pos*8) + bit_pos;
-    }
-  }
-  return MY_BIT_NONE;
-}
-
-
-static inline uint get_first_not_set(uint32 value, uint word_pos)
-{
-  uchar *byte_ptr= (uchar*)&value;
-  uchar byte_value;
-  uint byte_pos, bit_pos;
-
-  for (byte_pos=0; byte_pos < 4; byte_pos++, byte_ptr++)
-  {
-    byte_value= *byte_ptr;
-    if (byte_value != 0xFF)
-    {
-      for (bit_pos=0; ; bit_pos++)
-        if (!(byte_value & (1 << bit_pos)))
-          return (word_pos*32) + (byte_pos*8) + bit_pos;
-    }
-  }
-  return MY_BIT_NONE;
-}
-
-
 my_bool bitmap_init(MY_BITMAP *map, my_bitmap_map *buf, uint n_bits,
 		    my_bool thread_safe __attribute__((unused)))
 {
@@ -143,31 +117,25 @@ my_bool bitmap_init(MY_BITMAP *map, my_bitmap_map *buf, uint n_bits,
   {
     uint size_in_bytes= bitmap_buffer_size(n_bits);
     uint extra= 0;
-
     if (thread_safe)
     {
       size_in_bytes= ALIGN_SIZE(size_in_bytes);
       extra= sizeof(mysql_mutex_t);
     }
     map->mutex= 0;
-
     if (!(buf= (my_bitmap_map*) my_malloc(size_in_bytes+extra, MYF(MY_WME))))
       DBUG_RETURN(1);
-
     if (thread_safe)
     {
       map->mutex= (mysql_mutex_t *) ((char*) buf + size_in_bytes);
       mysql_mutex_init(key_BITMAP_mutex, map->mutex, MY_MUTEX_INIT_FAST);
     }
-
   }
-
   else
   {
     DBUG_ASSERT(thread_safe == 0);
   }
 
-
   map->bitmap= buf;
   map->n_bits= n_bits;
   create_last_word_mask(map);
@@ -183,7 +151,6 @@ void bitmap_free(MY_BITMAP *map)
   {
     if (map->mutex)
       mysql_mutex_destroy(map->mutex);
-
     my_free(map->bitmap);
     map->bitmap=0;
   }
@@ -293,7 +260,10 @@ void bitmap_set_prefix(MY_BITMAP *map, uint prefix_size)
     memset(m, 0xff, prefix_bytes);
   m+= prefix_bytes;
   if ((prefix_bits= prefix_size & 7))
-    *(m++)= (1 << prefix_bits)-1;
+  {
+    *m++= (1 << prefix_bits)-1;
+    prefix_bytes++;
+  }
   if ((d= no_bytes_in_map(map)-prefix_bytes))
     bzero(m, d);
 }
@@ -301,43 +271,31 @@ void bitmap_set_prefix(MY_BITMAP *map, uint prefix_size)
 
 my_bool bitmap_is_prefix(const MY_BITMAP *map, uint prefix_size)
 {
-  uint prefix_bits= prefix_size % 32;
-  my_bitmap_map *word_ptr= map->bitmap, last_word;
-  my_bitmap_map *end_prefix= word_ptr + prefix_size / 32;
-  DBUG_ASSERT(word_ptr && prefix_size <= map->n_bits);
-
-  /* 1: Words that should be filled with 1 */
-  for (; word_ptr < end_prefix; word_ptr++)
-    if (*word_ptr != 0xFFFFFFFF)
-      return FALSE;
-
-  last_word= *map->last_word_ptr & ~map->last_word_mask;
-
-  /* 2: Word which contains the end of the prefix (if any) */
-  if (prefix_bits)
-  {
-    if (word_ptr == map->last_word_ptr)
-      return uint4korr((uchar*)&last_word) == (uint32)((1 << prefix_bits) - 1);
-    else if (uint4korr((uchar*)word_ptr) != (uint32)((1 << prefix_bits) - 1))
-      return FALSE;
-    word_ptr++;
-  }
-
-  /* 3: Words that should be filled with 0 */
-  for (; word_ptr < map->last_word_ptr; word_ptr++)
-    if (*word_ptr != 0)
-      return FALSE;
-
-  /*
-    We can end up here in two situations:
-    1) We went through the whole bitmap in step 1. This will happen if the
-       whole bitmap is filled with 1 and prefix_size is a multiple of 32
-       (i.e. the prefix does not end in the middle of a word).
-       In this case word_ptr will be larger than map->last_word_ptr.
-    2) We have gone through steps 1-3 and just need to check that also
-       the last word is 0.
-  */
-  return word_ptr > map->last_word_ptr || last_word == 0;
+  uint prefix_mask= last_byte_mask(prefix_size);
+  uchar *m= (uchar*) map->bitmap;
+  uchar *end_prefix= m+(prefix_size-1)/8;
+  uchar *end;
+  DBUG_ASSERT(m && prefix_size <= map->n_bits);
+
+  /* Empty prefix is always true */
+  if (!prefix_size)
+    return 1;
+
+  while (m < end_prefix)
+    if (*m++ != 0xff)
+      return 0;
+
+  end= ((uchar*) map->bitmap) + no_bytes_in_map(map) - 1;
+  if (m == end)
+    return ((*m & last_byte_mask(map->n_bits)) == prefix_mask);
+
+  if (*m != prefix_mask)
+    return 0;
+
+  while (++m < end)
+    if (*m != 0)
+      return 0;
+  return ((*m & last_byte_mask(map->n_bits)) == 0);
 }
 
 
@@ -345,13 +303,10 @@ my_bool bitmap_is_set_all(const MY_BITMAP *map)
 {
   my_bitmap_map *data_ptr= map->bitmap;
   my_bitmap_map *end= map->last_word_ptr;
-
   for (; data_ptr < end; data_ptr++)
     if (*data_ptr != 0xFFFFFFFF)
       return FALSE;
-  if ((*map->last_word_ptr | map->last_word_mask) != 0xFFFFFFFF)
-    return FALSE;
-  return TRUE;
+  return (*data_ptr | map->last_word_mask) == 0xFFFFFFFF;
 }
 
 
@@ -363,9 +318,7 @@ my_bool bitmap_is_clear_all(const MY_BITMAP *map)
   for (; data_ptr < end; data_ptr++)
     if (*data_ptr)
       return FALSE;
-  if (*map->last_word_ptr & ~map->last_word_mask)
-    return FALSE;
-  return TRUE;
+  return (*data_ptr & ~map->last_word_mask) == 0;
 }
 
 /* Return TRUE if map1 is a subset of map2 */
@@ -378,14 +331,13 @@ my_bool bitmap_is_subset(const MY_BITMAP *map1, const MY_BITMAP *map2)
               map1->n_bits==map2->n_bits);
 
   end= map1->last_word_ptr;
-  for (; m1 < end; m1++, m2++)
-    if (*m1 & ~(*m2))
-      return FALSE;
-
-  if ((*map1->last_word_ptr & ~map1->last_word_mask) &
-      ~(*map2->last_word_ptr & ~map2->last_word_mask))
-    return FALSE;
-  return TRUE;
+  while (m1 < end)
+  {
+    if ((*m1++) & ~(*m2++))
+      return 0;
+  }
+  /* here both maps have the same number of bits - see assert above */
+  return ((*m1 & ~*m2 & ~map1->last_word_mask) ? 0 : 1);
 }
 
 /* True if bitmaps has any common bits */
@@ -398,14 +350,13 @@ my_bool bitmap_is_overlapping(const MY_BITMAP *map1, const MY_BITMAP *map2)
               map1->n_bits==map2->n_bits);
 
   end= map1->last_word_ptr;
-  for (; m1 < end; m1++, m2++)
-    if (*m1 & *m2)
-      return TRUE;
-
-  if ((*map1->last_word_ptr & ~map1->last_word_mask) &
-      (*map2->last_word_ptr & ~map2->last_word_mask))
-    return TRUE;
-  return FALSE;
+  while (m1 < end)
+  {
+    if ((*m1++) & (*m2++))
+      return 1;
+  }
+  /* here both maps have the same number of bits - see assert above */
+  return ((*m1 & *m2 & ~map1->last_word_mask) ? 1 : 0);
 }
 
 
@@ -417,20 +368,35 @@ void bitmap_intersect(MY_BITMAP *map, const MY_BITMAP *map2)
   DBUG_ASSERT(map->bitmap && map2->bitmap);
 
   end= to+min(len,len2);
-  for (; to < end; to++, from++)
-    *to &= *from;
-
-  if (len >= len2)
-    map->bitmap[len2 - 1] &= ~map2->last_word_mask;
+  while (to < end)
+    *to++ &= *from++;
 
-  if (len2 < len)
+  if (len2 <= len)
   {
-    end+=len-len2;
-    for (; to < end; to++)
-      *to= 0;
+    to[-1]&= ~map2->last_word_mask; /* Clear last not relevant bits */
+    end+= len-len2;
+    while (to < end)
+      *to++= 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)
+{
+  my_bitmap_map *m1= map1->bitmap, *m2= map2->bitmap, *end;
+
+  DBUG_ASSERT(map1->bitmap && map2->bitmap &&
+              map1->n_bits==map2->n_bits);
+  end= map1->last_word_ptr;
+  while ( m1 < end)
+    if ((*m1++ | *m2++) != 0xFFFFFFFF)
+      return FALSE;
+  /* here both maps have the same number of bits - see assert above */
+  return ((*m1 | *m2 | map1->last_word_mask) != 0xFFFFFFFF);
+}
+
+
 
 /*
   Set/clear all bits above a bit.
@@ -458,8 +424,8 @@ void bitmap_set_above(MY_BITMAP *map, uint from_byte, uint use_bit)
   uchar *to= (uchar *)map->bitmap + from_byte;
   uchar *end= (uchar *)map->bitmap + (map->n_bits+7)/8;
 
-  for (; to < end; to++)
-    *to= use_byte;
+  while (to < end)
+    *to++= use_byte;
 }
 
 
@@ -468,45 +434,46 @@ void bitmap_subtract(MY_BITMAP *map, const MY_BITMAP *map2)
   my_bitmap_map *to= map->bitmap, *from= map2->bitmap, *end;
   DBUG_ASSERT(map->bitmap && map2->bitmap &&
               map->n_bits==map2->n_bits);
+
   end= map->last_word_ptr;
 
-  for (; to <= end; to++, from++)
-    *to &= ~(*from);
+  while (to <= end)
+    *to++ &= ~(*from++);
 }
 
 
 void bitmap_union(MY_BITMAP *map, const MY_BITMAP *map2)
 {
   my_bitmap_map *to= map->bitmap, *from= map2->bitmap, *end;
+
   DBUG_ASSERT(map->bitmap && map2->bitmap &&
               map->n_bits==map2->n_bits);
   end= map->last_word_ptr;
 
-  for (; to <= end; to++, from++)
-    *to |= *from;
+  while (to <= end)
+    *to++ |= *from++;
 }
 
 
 void bitmap_xor(MY_BITMAP *map, const MY_BITMAP *map2)
 {
-  my_bitmap_map *to= map->bitmap, *from= map2->bitmap, *end;
+  my_bitmap_map *to= map->bitmap, *from= map2->bitmap, *end= map->last_word_ptr;
   DBUG_ASSERT(map->bitmap && map2->bitmap &&
               map->n_bits==map2->n_bits);
-  end= map->last_word_ptr;
-
-  for (; to <= end; to++, from++)
-    *to ^= *from;
+  while (to <= end)
+    *to++ ^= *from++;
 }
 
 
 void bitmap_invert(MY_BITMAP *map)
 {
   my_bitmap_map *to= map->bitmap, *end;
+
   DBUG_ASSERT(map->bitmap);
   end= map->last_word_ptr;
 
-  for (; to <= end; to++)
-    *to ^= 0xFFFFFFFF;
+  while (to <= end)
+    *to++ ^= 0xFFFFFFFF;
 }
 
 
@@ -525,48 +492,87 @@ uint bitmap_bits_set(const MY_BITMAP *map)
   return res;
 }
 
-
 void bitmap_copy(MY_BITMAP *map, const MY_BITMAP *map2)
 {
   my_bitmap_map *to= map->bitmap, *from= map2->bitmap, *end;
+
   DBUG_ASSERT(map->bitmap && map2->bitmap &&
               map->n_bits==map2->n_bits);
   end= map->last_word_ptr;
 
-  for (; to <= end; to++, from++)
-    *to = *from;
+  while (to <= end)
+    *to++ = *from++;
 }
 
 
 uint bitmap_get_first_set(const MY_BITMAP *map)
 {
-  uint word_pos;
+  uchar *byte_ptr;
+  uint i,j,k;
   my_bitmap_map *data_ptr, *end= map->last_word_ptr;
 
   DBUG_ASSERT(map->bitmap);
   data_ptr= map->bitmap;
 
-  for (word_pos=0; data_ptr < end; data_ptr++, word_pos++)
+  for (i=0; data_ptr < end; data_ptr++, i++)
     if (*data_ptr)
-      return get_first_set(*data_ptr, word_pos);
+      goto found;
+  if (!(*data_ptr & ~map->last_word_mask))
+    return MY_BIT_NONE;
 
-  return get_first_set(*map->last_word_ptr & ~map->last_word_mask, word_pos);
+found:
+  {
+    byte_ptr= (uchar*)data_ptr;
+    for (j=0; ; j++, byte_ptr++)
+    {
+      if (*byte_ptr)
+      {
+        for (k=0; ; k++)
+        {
+          if (*byte_ptr & (1 << k))
+            return (i*32) + (j*8) + k;
+        }
+      }
+    }
+  }
+  DBUG_ASSERT(0);
+  return MY_BIT_NONE;                           /* Impossible */
 }
 
 
 uint bitmap_get_first(const MY_BITMAP *map)
 {
-  uint word_pos;
+  uchar *byte_ptr;
+  uint i,j,k;
   my_bitmap_map *data_ptr, *end= map->last_word_ptr;
 
   DBUG_ASSERT(map->bitmap);
   data_ptr= map->bitmap;
+  *map->last_word_ptr|= map->last_word_mask;
 
-  for (word_pos=0; data_ptr < end; data_ptr++, word_pos++)
+  for (i=0; data_ptr < end; data_ptr++, i++)
     if (*data_ptr != 0xFFFFFFFF)
-      return get_first_not_set(*data_ptr, word_pos);
+      goto found;
+  if ((*data_ptr | map->last_word_mask) == 0xFFFFFFFF)
+    return MY_BIT_NONE;
 
-  return get_first_not_set(*map->last_word_ptr | map->last_word_mask, word_pos);
+found:
+  {
+    byte_ptr= (uchar*)data_ptr;
+    for (j=0; ; j++, byte_ptr++)
+    {
+      if (*byte_ptr != 0xFF)
+      {
+        for (k=0; ; k++)
+        {
+          if (!(*byte_ptr & (1 << k)))
+            return (i*32) + (j*8) + k;
+        }
+      }
+    }
+  }
+  DBUG_ASSERT(0);
+  return MY_BIT_NONE;                           /* Impossible */
 }
 
 
@@ -587,3 +593,4 @@ void bitmap_lock_clear_bit(MY_BITMAP *map, uint bitmap_bit)
   bitmap_clear_bit(map, bitmap_bit);
   bitmap_unlock(map);
 }
+