summaryrefslogtreecommitdiffstats
path: root/mysys/my_bitmap.c
diff options
context:
space:
mode:
Diffstat (limited to 'mysys/my_bitmap.c')
-rw-r--r--mysys/my_bitmap.c695
1 files changed, 695 insertions, 0 deletions
diff --git a/mysys/my_bitmap.c b/mysys/my_bitmap.c
new file mode 100644
index 00000000..9893c7e4
--- /dev/null
+++ b/mysys/my_bitmap.c
@@ -0,0 +1,695 @@
+/*
+ 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
+ the Free Software Foundation; version 2 of the License.
+
+ This program is distributed in the hope that it will be useful,
+ but WITHOUT ANY WARRANTY; without even the implied warranty of
+ MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ GNU General Public License for more details.
+
+ You should have received a copy of the GNU General Public License
+ along with this program; if not, write to the Free Software
+ Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1335 USA */
+
+/*
+ Handling of uchar arrays as large bitmaps.
+
+ API limitations (or, rather asserted safety assumptions,
+ to encourage correct programming)
+
+ * the internal size is a set of 32 bit words
+ * the number of bits specified in creation can be any number > 0
+
+ TODO:
+ 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 Ronstrom 2005, with assistance of Tomas Ulin and Mats
+ Kindahl.
+*/
+
+#include "mysys_priv.h"
+#include <my_bitmap.h>
+#include <m_string.h>
+#include <my_bit.h>
+
+/*
+ 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;
+}
+
+
+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
+ 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*)&map->last_word_mask;
+
+ map->last_word_ptr= map->bitmap + no_words_in_map(map)-1;
+ switch (no_bytes_in_map(map) & 3) {
+ case 1:
+ map->last_word_mask= ~0U;
+ ptr[0]= mask;
+ return;
+ case 2:
+ map->last_word_mask= ~0U;
+ ptr[0]= 0;
+ ptr[1]= mask;
+ return;
+ case 3:
+ map->last_word_mask= 0U;
+ ptr[2]= mask;
+ ptr[3]= 0xFFU;
+ return;
+ case 0:
+ map->last_word_mask= 0U;
+ ptr[3]= mask;
+ return;
+ }
+}
+
+
+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 uint get_first_set(my_bitmap_map value, uint word_pos)
+{
+ uchar *byte_ptr= (uchar*)&value;
+ uchar byte_value;
+ uint byte_pos, bit_pos;
+
+ DBUG_ASSERT(value);
+ for (byte_pos=0; ; byte_pos++, byte_ptr++)
+ {
+ if ((byte_value= *byte_ptr))
+ {
+ 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; /* Impossible */
+}
+
+/*
+ Initialize a bitmap object. All bits will be set to zero
+*/
+
+my_bool my_bitmap_init(MY_BITMAP *map, my_bitmap_map *buf, uint n_bits)
+{
+ DBUG_ENTER("my_bitmap_init");
+ if (!buf)
+ {
+ uint size_in_bytes= bitmap_buffer_size(n_bits);
+ if (!(buf= (my_bitmap_map*) my_malloc(key_memory_MY_BITMAP_bitmap,
+ size_in_bytes, MYF(MY_WME))))
+ DBUG_RETURN(1);
+ }
+
+ map->bitmap= buf;
+ map->n_bits= n_bits;
+ create_last_word_mask(map);
+ bitmap_clear_all(map);
+ DBUG_RETURN(0);
+}
+
+
+void my_bitmap_free(MY_BITMAP *map)
+{
+ DBUG_ENTER("my_bitmap_free");
+ if (map->bitmap)
+ {
+ my_free(map->bitmap);
+ map->bitmap=0;
+ }
+ DBUG_VOID_RETURN;
+}
+
+
+/*
+ test if bit already set and set it if it was not (thread unsafe method)
+
+ SYNOPSIS
+ bitmap_fast_test_and_set()
+ MAP bit map struct
+ BIT bit number
+
+ RETURN
+ 0 bit was not set
+ !=0 bit was set
+*/
+
+my_bool bitmap_fast_test_and_set(MY_BITMAP *map, uint bitmap_bit)
+{
+ uchar *value= ((uchar*) map->bitmap) + (bitmap_bit / 8);
+ uchar bit= 1 << ((bitmap_bit) & 7);
+ uchar res= (*value) & bit;
+ *value|= bit;
+ return res;
+}
+
+
+/*
+ test if bit already set and set it if it was not (thread safe method)
+
+ SYNOPSIS
+ bitmap_fast_test_and_set()
+ map bit map struct
+ bitmap_bit bit number
+
+ RETURN
+ 0 bit was not set
+ !=0 bit was set
+*/
+
+my_bool bitmap_test_and_set(MY_BITMAP *map, uint bitmap_bit)
+{
+ DBUG_ASSERT(map->bitmap);
+ DBUG_ASSERT(bitmap_bit < map->n_bits);
+ return bitmap_fast_test_and_set(map, bitmap_bit);
+}
+
+/*
+ test if bit already set and clear it if it was set(thread unsafe method)
+
+ SYNOPSIS
+ bitmap_fast_test_and_set()
+ MAP bit map struct
+ BIT bit number
+
+ RETURN
+ 0 bit was not set
+ !=0 bit was set
+*/
+
+my_bool bitmap_fast_test_and_clear(MY_BITMAP *map, uint bitmap_bit)
+{
+ uchar *byte= (uchar*) map->bitmap + (bitmap_bit / 8);
+ uchar bit= 1 << ((bitmap_bit) & 7);
+ uchar res= (*byte) & bit;
+ *byte&= ~bit;
+ return res;
+}
+
+
+my_bool bitmap_test_and_clear(MY_BITMAP *map, uint bitmap_bit)
+{
+ DBUG_ASSERT(map->bitmap);
+ DBUG_ASSERT(bitmap_bit < map->n_bits);
+ return bitmap_fast_test_and_clear(map, bitmap_bit);
+}
+
+
+uint bitmap_set_next(MY_BITMAP *map)
+{
+ uint bit_found;
+ DBUG_ASSERT(map->bitmap);
+ if ((bit_found= bitmap_get_first(map)) != MY_BIT_NONE)
+ bitmap_set_bit(map, bit_found);
+ return bit_found;
+}
+
+
+/**
+ Set the specified number of bits in the bitmap buffer.
+
+ @param map [IN] Bitmap
+ @param prefix_size [IN] Number of bits to be set
+*/
+void bitmap_set_prefix(MY_BITMAP *map, uint prefix_size)
+{
+ uint prefix_bytes, prefix_bits, d;
+ uchar *m= (uchar *)map->bitmap;
+
+ DBUG_ASSERT(map->bitmap);
+ DBUG_ASSERT(prefix_size <= map->n_bits || prefix_size == (uint) ~0);
+ set_if_smaller(prefix_size, map->n_bits);
+ if ((prefix_bytes= prefix_size / 8))
+ memset(m, 0xff, prefix_bytes);
+ m+= prefix_bytes;
+ if ((prefix_bits= prefix_size & 7))
+ {
+ *(m++)= (1 << prefix_bits)-1;
+ // As the prefix bits are set, lets count this byte too as a prefix byte.
+ prefix_bytes ++;
+ }
+ if ((d= no_bytes_in_map(map)-prefix_bytes))
+ memset(m, 0, d);
+}
+
+
+my_bool bitmap_is_prefix(const MY_BITMAP *map, uint prefix_size)
+{
+ 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);
+ DBUG_ASSERT(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);
+}
+
+
+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;
+ return (*data_ptr | map->last_word_mask) == 0xFFFFFFFF;
+}
+
+
+my_bool bitmap_is_clear_all(const MY_BITMAP *map)
+{
+ my_bitmap_map *data_ptr= map->bitmap;
+ my_bitmap_map *end= map->last_word_ptr;
+
+ DBUG_ASSERT(map->n_bits > 0);
+ for (; data_ptr < end; data_ptr++)
+ if (*data_ptr)
+ return FALSE;
+ return (*data_ptr & ~map->last_word_mask) == 0;
+}
+
+/* Return TRUE if map1 is a subset of map2 */
+
+my_bool bitmap_is_subset(const MY_BITMAP *map1, const MY_BITMAP *map2)
+{
+ my_bitmap_map *m1= map1->bitmap, *m2= map2->bitmap, *end;
+
+ DBUG_ASSERT(map1->bitmap && map2->bitmap);
+ DBUG_ASSERT(map1->n_bits==map2->n_bits);
+
+ end= map1->last_word_ptr;
+ 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 */
+
+my_bool bitmap_is_overlapping(const MY_BITMAP *map1, const MY_BITMAP *map2)
+{
+ my_bitmap_map *m1= map1->bitmap, *m2= map2->bitmap, *end;
+
+ DBUG_ASSERT(map1->bitmap);
+ DBUG_ASSERT(map2->bitmap);
+ DBUG_ASSERT(map1->n_bits==map2->n_bits);
+
+ end= map1->last_word_ptr;
+ 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);
+}
+
+
+void bitmap_intersect(MY_BITMAP *map, const MY_BITMAP *map2)
+{
+ my_bitmap_map *to= map->bitmap, *from= map2->bitmap, *end;
+ uint len= no_words_in_map(map), len2 = no_words_in_map(map2);
+
+ DBUG_ASSERT(map->bitmap);
+ DBUG_ASSERT(map2->bitmap);
+
+ end= to+MY_MIN(len,len2);
+ while (to < end)
+ *to++ &= *from++;
+
+ if (len2 <= len)
+ {
+ to[-1]&= ~map2->last_word_mask; /* Clear last not relevant bits */
+ end+= len-len2;
+ while (to < end)
+ *to++= 0;
+ }
+}
+
+
+/*
+ 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);
+ DBUG_ASSERT(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)
+{
+ my_bitmap_map *m1= map1->bitmap, *m2= map2->bitmap, *end;
+
+ DBUG_ASSERT(map1->bitmap);
+ DBUG_ASSERT(map2->bitmap);
+ DBUG_ASSERT(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.
+
+ SYNOPSIS
+ bitmap_set_above()
+ map RETURN The bitmap to change.
+ from_byte The bitmap buffer byte offset to start with.
+ use_bit The bit value (1/0) to use for all upper bits.
+
+ NOTE
+ You can only set/clear full bytes.
+ The function is meant for the situation that you copy a smaller bitmap
+ to a bigger bitmap. Bitmap lengths are always multiple of eigth (the
+ size of a byte). Using 'from_byte' saves multiplication and division
+ by eight during parameter passing.
+
+ RETURN
+ void
+*/
+
+void bitmap_set_above(MY_BITMAP *map, uint from_byte, uint use_bit)
+{
+ uchar use_byte= use_bit ? 0xff : 0;
+ uchar *to= (uchar *)map->bitmap + from_byte;
+ uchar *end= (uchar *)map->bitmap + (map->n_bits+7)/8;
+
+ while (to < end)
+ *to++= use_byte;
+}
+
+
+void bitmap_subtract(MY_BITMAP *map, const MY_BITMAP *map2)
+{
+ my_bitmap_map *to= map->bitmap, *from= map2->bitmap, *end;
+ DBUG_ASSERT(map->bitmap);
+ DBUG_ASSERT(map2->bitmap);
+ DBUG_ASSERT(map->n_bits==map2->n_bits);
+
+ end= map->last_word_ptr;
+
+ 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);
+ DBUG_ASSERT(map2->bitmap);
+ DBUG_ASSERT(map->n_bits == map2->n_bits);
+ end= map->last_word_ptr;
+
+ 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= map->last_word_ptr;
+ DBUG_ASSERT(map->bitmap);
+ DBUG_ASSERT(map2->bitmap);
+ DBUG_ASSERT(map->n_bits == map2->n_bits);
+ 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;
+
+ while (to <= end)
+ *to++ ^= 0xFFFFFFFF;
+}
+
+
+uint bitmap_bits_set(const MY_BITMAP *map)
+{
+ my_bitmap_map *data_ptr= map->bitmap;
+ my_bitmap_map *end= map->last_word_ptr;
+ uint res= 0;
+ DBUG_ASSERT(map->bitmap);
+
+ for (; data_ptr < end; data_ptr++)
+ res+= my_count_bits_uint32(*data_ptr);
+
+ /*Reset last bits to zero*/
+ res+= my_count_bits_uint32(*map->last_word_ptr & ~map->last_word_mask);
+ 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);
+ DBUG_ASSERT(map2->bitmap);
+ DBUG_ASSERT(map->n_bits == map2->n_bits);
+ end= map->last_word_ptr;
+
+ while (to <= end)
+ *to++ = *from++;
+}
+
+
+uint bitmap_get_first_set(const MY_BITMAP *map)
+{
+ uint i;
+ my_bitmap_map *data_ptr= map->bitmap, *end= map->last_word_ptr;
+
+ DBUG_ASSERT(map->bitmap);
+
+ for (i=0; data_ptr < end; data_ptr++, i++)
+ if (*data_ptr)
+ goto found;
+ if (!(*data_ptr & ~map->last_word_mask))
+ return MY_BIT_NONE;
+
+found:
+ return get_first_set(*data_ptr, i);
+}
+
+
+/**
+ Get the next set bit.
+
+ @param map Bitmap
+ @param bitmap_bit Bit to start search from
+
+ @return Index to first bit set after bitmap_bit
+*/
+
+uint bitmap_get_next_set(const MY_BITMAP *map, uint bitmap_bit)
+{
+ uint word_pos, byte_to_mask, i;
+ union { my_bitmap_map bitmap ; uchar bitmap_buff[sizeof(my_bitmap_map)]; }
+ first_word;
+ uchar *ptr= &first_word.bitmap_buff[0];
+ my_bitmap_map *data_ptr, *end= map->last_word_ptr;
+
+ DBUG_ASSERT(map->bitmap);
+
+ /* Look for the next bit */
+ bitmap_bit++;
+ if (bitmap_bit >= map->n_bits)
+ return MY_BIT_NONE;
+ word_pos= bitmap_bit / 32;
+ data_ptr= map->bitmap + word_pos;
+ first_word.bitmap= *data_ptr;
+
+ /* Mask out previous bits from first_word */
+ byte_to_mask= (bitmap_bit % 32) / 8;
+ for (i= 0; i < byte_to_mask; i++)
+ ptr[i]= 0;
+ ptr[byte_to_mask]&= 0xFFU << (bitmap_bit & 7);
+
+ if (data_ptr == end)
+ {
+ if (first_word.bitmap & ~map->last_word_mask)
+ return get_first_set(first_word.bitmap, word_pos);
+ else
+ return MY_BIT_NONE;
+ }
+
+ if (first_word.bitmap)
+ return get_first_set(first_word.bitmap, word_pos);
+
+ for (data_ptr++, word_pos++; data_ptr < end; data_ptr++, word_pos++)
+ if (*data_ptr)
+ return get_first_set(*data_ptr, word_pos);
+
+ if (!(*end & ~map->last_word_mask))
+ return MY_BIT_NONE;
+ return get_first_set(*end, word_pos);
+}
+
+
+/* Get first free bit */
+
+uint bitmap_get_first(const MY_BITMAP *map)
+{
+ 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 (i=0; data_ptr < end; data_ptr++, i++)
+ if (*data_ptr != 0xFFFFFFFF)
+ goto found;
+ if ((*data_ptr | map->last_word_mask) == 0xFFFFFFFF)
+ return MY_BIT_NONE;
+
+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 */
+}