diff options
Diffstat (limited to 'mysys/my_bitmap.c')
-rw-r--r-- | mysys/my_bitmap.c | 241 |
1 files changed, 135 insertions, 106 deletions
diff --git a/mysys/my_bitmap.c b/mysys/my_bitmap.c index 3d3ab16b599..0e5421ec484 100644 --- a/mysys/my_bitmap.c +++ b/mysys/my_bitmap.c @@ -1,4 +1,6 @@ -/* Copyright (c) 2000, 2011, Oracle and/or its affiliates. All rights reserved. +/* Copyright (C) 2000 MySQL AB + Copyright (c) 2000, 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 @@ -40,16 +42,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. - */ - unsigned char const mask= (~((1 << used) - 1)) & 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. +*/ + +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 @@ -101,46 +118,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))) { @@ -300,7 +277,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); } @@ -325,7 +305,7 @@ my_bool bitmap_is_prefix(const MY_BITMAP *map, uint prefix_size) { 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)) + if (uint4korr((uchar*)word_ptr) != (uint32)((1 << prefix_bits) - 1)) return FALSE; word_ptr++; } @@ -356,9 +336,7 @@ my_bool bitmap_is_set_all(const MY_BITMAP *map) 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; } @@ -370,9 +348,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 */ @@ -385,14 +361,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 */ @@ -405,14 +380,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); } @@ -424,20 +398,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; + while (to < end) + *to++ &= *from++; - if (len >= len2) - map->bitmap[len2 - 1] &= ~map2->last_word_mask; - - 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. @@ -465,8 +454,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; } @@ -475,45 +464,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; } @@ -540,40 +530,79 @@ void bitmap_copy(MY_BITMAP *map, const MY_BITMAP *map2) 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 */ } @@ -780,4 +809,4 @@ void bitmap_lock_flip_bit(MY_BITMAP *map, uint bitmap_bit) bitmap_flip_bit(map, bitmap_bit); bitmap_unlock(map); } -#endif +#endif /* NOT_USED */ |