diff options
| -rw-r--r-- | include/my_bit.h | 24 | ||||
| -rw-r--r-- | include/my_bitmap.h | 9 | ||||
| -rw-r--r-- | mysys/my_bitmap.c | 635 | ||||
| -rw-r--r-- | unittest/mysys/bitmap-t.c | 173 |
4 files changed, 331 insertions, 510 deletions
diff --git a/include/my_bit.h b/include/my_bit.h index 2e464e89049..2ab47b04184 100644 --- a/include/my_bit.h +++ b/include/my_bit.h @@ -1,3 +1,18 @@ +/* Copyright (c) 2007, 2011, Oracle and/or its affiliates. All rights reserved. + + 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 St, Fifth Floor, Boston, MA 02110-1301 USA */ + /* Some useful bit functions */ @@ -42,9 +57,12 @@ STATIC_INLINE uint my_count_bits(ulonglong v) #endif } -STATIC_INLINE uint my_count_bits_ushort(ushort v) +STATIC_INLINE uint my_count_bits_uint32(uint32 v) { - return _my_bits_nbits[v]; + return (uint) (uchar) (_my_bits_nbits[(uchar) v] + + _my_bits_nbits[(uchar) (v >> 8)] + + _my_bits_nbits[(uchar) (v >> 16)] + + _my_bits_nbits[(uchar) (v >> 24)]); } @@ -104,6 +122,6 @@ extern uint32 my_round_up_to_next_power(uint32 v); uint32 my_clear_highest_bit(uint32 v); uint32 my_reverse_bits(uint32 key); extern uint my_count_bits(ulonglong v); -extern uint my_count_bits_ushort(ushort v); +extern uint my_count_bits_uint32(uint32 v); #endif /* HAVE_INLINE */ C_MODE_END diff --git a/include/my_bitmap.h b/include/my_bitmap.h index ab69b2d671d..42f985c8918 100644 --- a/include/my_bitmap.h +++ b/include/my_bitmap.h @@ -1,4 +1,4 @@ -/* Copyright (C) 2000 MySQL AB +/* Copyright (c) 2000, 2011, Oracle and/or its affiliates. All rights reserved. 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 @@ -149,9 +149,10 @@ bitmap_is_set(const MY_BITMAP *map,uint bit) static inline my_bool bitmap_cmp(const MY_BITMAP *map1, const MY_BITMAP *map2) { - *(map1)->last_word_ptr|= (map1)->last_word_mask; - *(map2)->last_word_ptr|= (map2)->last_word_mask; - return memcmp((map1)->bitmap, (map2)->bitmap, 4*no_words_in_map((map1)))==0; + if (memcmp(map1->bitmap, map2->bitmap, 4*(no_words_in_map(map1)-1)) != 0) + return FALSE; + return ((*map1->last_word_ptr | map1->last_word_mask) == + (*map2->last_word_ptr | map2->last_word_mask)); } #define bitmap_clear_all(MAP) \ diff --git a/mysys/my_bitmap.c b/mysys/my_bitmap.c index b7258080337..3d3ab16b599 100644 --- a/mysys/my_bitmap.c +++ b/mysys/my_bitmap.c @@ -1,4 +1,4 @@ -/* Copyright (C) 2000 MySQL AB +/* Copyright (c) 2000, 2011, Oracle and/or its affiliates. All rights reserved. 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 @@ -91,6 +91,7 @@ static inline void bitmap_lock(MY_BITMAP *map __attribute__((unused))) #endif } + static inline void bitmap_unlock(MY_BITMAP *map __attribute__((unused))) { #ifdef THREAD @@ -100,6 +101,46 @@ 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))) { @@ -259,7 +300,7 @@ 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; if ((d= no_bytes_in_map(map)-prefix_bytes)) bzero(m, d); } @@ -267,28 +308,43 @@ 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 & 0x7, res; - uchar *m= (uchar*)map->bitmap; - uchar *end_prefix= m+prefix_size/8; - uchar *end; - DBUG_ASSERT(m && prefix_size <= map->n_bits); - end= m+no_bytes_in_map(map); - - while (m < end_prefix) - if (*m++ != 0xff) - return 0; - - *map->last_word_ptr&= ~map->last_word_mask; /*Clear bits*/ - res= 0; - if (prefix_bits && *m++ != (1 << prefix_bits)-1) - goto ret; - - while (m < end) - if (*m++ != 0) - goto ret; - res= 1; -ret: - return res; + 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; } @@ -296,10 +352,12 @@ 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; - *map->last_word_ptr |= map->last_word_mask; - for (; data_ptr <= end; data_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; } @@ -307,13 +365,13 @@ my_bool bitmap_is_set_all(const MY_BITMAP *map) my_bool bitmap_is_clear_all(const MY_BITMAP *map) { my_bitmap_map *data_ptr= map->bitmap; - my_bitmap_map *end; - if (*map->last_word_ptr & ~map->last_word_mask) - return FALSE; - end= map->last_word_ptr; + my_bitmap_map *end= map->last_word_ptr; + for (; data_ptr < end; data_ptr++) if (*data_ptr) return FALSE; + if (*map->last_word_ptr & ~map->last_word_mask) + return FALSE; return TRUE; } @@ -327,14 +385,14 @@ my_bool bitmap_is_subset(const MY_BITMAP *map1, const MY_BITMAP *map2) map1->n_bits==map2->n_bits); end= map1->last_word_ptr; - *map1->last_word_ptr &= ~map1->last_word_mask; - *map2->last_word_ptr &= ~map2->last_word_mask; - while (m1 <= end) - { - if ((*m1++) & ~(*m2++)) - return 0; - } - return 1; + 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; } /* True if bitmaps has any common bits */ @@ -347,14 +405,14 @@ my_bool bitmap_is_overlapping(const MY_BITMAP *map1, const MY_BITMAP *map2) map1->n_bits==map2->n_bits); end= map1->last_word_ptr; - *map1->last_word_ptr &= ~map1->last_word_mask; - *map2->last_word_ptr &= ~map2->last_word_mask; - while (m1 <= end) - { - if ((*m1++) & (*m2++)) - return 1; - } - return 0; + 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; } @@ -366,15 +424,17 @@ void bitmap_intersect(MY_BITMAP *map, const MY_BITMAP *map2) DBUG_ASSERT(map->bitmap && map2->bitmap); end= to+min(len,len2); - *map2->last_word_ptr&= ~map2->last_word_mask; /*Clear last bits in map2*/ - while (to < end) - *to++ &= *from++; + for (; to < end; to++, from++) + *to &= *from; + + if (len >= len2) + map->bitmap[len2 - 1] &= ~map2->last_word_mask; if (len2 < len) { end+=len-len2; - while (to < end) - *to++=0; + for (; to < end; to++) + *to= 0; } } @@ -405,8 +465,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; - while (to < end) - *to++= use_byte; + for (; to < end; to++) + *to= use_byte; } @@ -415,59 +475,60 @@ 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; - while (to <= end) - *to++ &= ~(*from++); + for (; to <= end; to++, from++) + *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; - while (to <= end) - *to++ |= *from++; + for (; to <= end; to++, from++) + *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; + my_bitmap_map *to= map->bitmap, *from= map2->bitmap, *end; DBUG_ASSERT(map->bitmap && map2->bitmap && map->n_bits==map2->n_bits); - while (to <= end) - *to++ ^= *from++; + end= map->last_word_ptr; + + for (; to <= end; to++, from++) + *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; + for (; to <= end; to++) + *to ^= 0xFFFFFFFF; } uint bitmap_bits_set(const MY_BITMAP *map) -{ - uchar *m= (uchar*)map->bitmap; - uchar *end= m + no_bytes_in_map(map); +{ + my_bitmap_map *data_ptr= map->bitmap; + my_bitmap_map *end= map->last_word_ptr; uint res= 0; - DBUG_ASSERT(map->bitmap); - *map->last_word_ptr&= ~map->last_word_mask; /*Reset last bits to zero*/ - while (m < end) - res+= my_count_bits_ushort(*m++); + + 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; } @@ -475,76 +536,44 @@ uint bitmap_bits_set(const MY_BITMAP *map) 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; - while (to <= end) - *to++ = *from++; + + for (; to <= end; to++, from++) + *to = *from; } uint bitmap_get_first_set(const MY_BITMAP *map) { - uchar *byte_ptr; - uint i,j,k; + uint word_pos; 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++) - { + for (word_pos=0; data_ptr < end; data_ptr++, word_pos++) if (*data_ptr) - { - 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; - } - } - } - } - } - return MY_BIT_NONE; + return get_first_set(*data_ptr, word_pos); + + return get_first_set(*map->last_word_ptr & ~map->last_word_mask, word_pos); } uint bitmap_get_first(const MY_BITMAP *map) { - uchar *byte_ptr; - uint i,j,k; + uint word_pos; 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++) - { + for (word_pos=0; data_ptr < end; data_ptr++, word_pos++) if (*data_ptr != 0xFFFFFFFF) - { - 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; - } - } - } - } - } - return MY_BIT_NONE; + return get_first_not_set(*data_ptr, word_pos); + + return get_first_not_set(*map->last_word_ptr | map->last_word_mask, word_pos); } @@ -752,375 +781,3 @@ void bitmap_lock_flip_bit(MY_BITMAP *map, uint bitmap_bit) bitmap_unlock(map); } #endif -#ifdef MAIN - -uint get_rand_bit(uint bitsize) -{ - return (rand() % bitsize); -} - -bool test_set_get_clear_bit(MY_BITMAP *map, uint bitsize) -{ - uint i, test_bit; - uint no_loops= bitsize > 128 ? 128 : bitsize; - for (i=0; i < no_loops; i++) - { - test_bit= get_rand_bit(bitsize); - bitmap_set_bit(map, test_bit); - if (!bitmap_is_set(map, test_bit)) - goto error1; - bitmap_clear_bit(map, test_bit); - if (bitmap_is_set(map, test_bit)) - goto error2; - } - return FALSE; -error1: - printf("Error in set bit, bit %u, bitsize = %u", test_bit, bitsize); - return TRUE; -error2: - printf("Error in clear bit, bit %u, bitsize = %u", test_bit, bitsize); - return TRUE; -} - -bool test_flip_bit(MY_BITMAP *map, uint bitsize) -{ - uint i, test_bit; - uint no_loops= bitsize > 128 ? 128 : bitsize; - for (i=0; i < no_loops; i++) - { - test_bit= get_rand_bit(bitsize); - bitmap_flip_bit(map, test_bit); - if (!bitmap_is_set(map, test_bit)) - goto error1; - bitmap_flip_bit(map, test_bit); - if (bitmap_is_set(map, test_bit)) - goto error2; - } - return FALSE; -error1: - printf("Error in flip bit 1, bit %u, bitsize = %u", test_bit, bitsize); - return TRUE; -error2: - printf("Error in flip bit 2, bit %u, bitsize = %u", test_bit, bitsize); - return TRUE; -} - -bool test_operators(MY_BITMAP *map __attribute__((unused)), - uint bitsize __attribute__((unused))) -{ - return FALSE; -} - -bool test_get_all_bits(MY_BITMAP *map, uint bitsize) -{ - uint i; - bitmap_set_all(map); - if (!bitmap_is_set_all(map)) - goto error1; - if (!bitmap_is_prefix(map, bitsize)) - goto error5; - bitmap_clear_all(map); - if (!bitmap_is_clear_all(map)) - goto error2; - if (!bitmap_is_prefix(map, 0)) - goto error6; - for (i=0; i<bitsize;i++) - bitmap_set_bit(map, i); - if (!bitmap_is_set_all(map)) - goto error3; - for (i=0; i<bitsize;i++) - bitmap_clear_bit(map, i); - if (!bitmap_is_clear_all(map)) - goto error4; - return FALSE; -error1: - printf("Error in set_all, bitsize = %u", bitsize); - return TRUE; -error2: - printf("Error in clear_all, bitsize = %u", bitsize); - return TRUE; -error3: - printf("Error in bitmap_is_set_all, bitsize = %u", bitsize); - return TRUE; -error4: - printf("Error in bitmap_is_clear_all, bitsize = %u", bitsize); - return TRUE; -error5: - printf("Error in set_all through set_prefix, bitsize = %u", bitsize); - return TRUE; -error6: - printf("Error in clear_all through set_prefix, bitsize = %u", bitsize); - return TRUE; -} - -bool test_compare_operators(MY_BITMAP *map, uint bitsize) -{ - uint i, j, test_bit1, test_bit2, test_bit3,test_bit4; - uint no_loops= bitsize > 128 ? 128 : bitsize; - MY_BITMAP map2_obj, map3_obj; - MY_BITMAP *map2= &map2_obj, *map3= &map3_obj; - my_bitmap_map map2buf[1024]; - my_bitmap_map map3buf[1024]; - bitmap_init(&map2_obj, map2buf, bitsize, FALSE); - bitmap_init(&map3_obj, map3buf, bitsize, FALSE); - bitmap_clear_all(map2); - bitmap_clear_all(map3); - for (i=0; i < no_loops; i++) - { - test_bit1=get_rand_bit(bitsize); - bitmap_set_prefix(map, test_bit1); - test_bit2=get_rand_bit(bitsize); - bitmap_set_prefix(map2, test_bit2); - bitmap_intersect(map, map2); - test_bit3= test_bit2 < test_bit1 ? test_bit2 : test_bit1; - bitmap_set_prefix(map3, test_bit3); - if (!bitmap_cmp(map, map3)) - goto error1; - bitmap_clear_all(map); - bitmap_clear_all(map2); - bitmap_clear_all(map3); - test_bit1=get_rand_bit(bitsize); - test_bit2=get_rand_bit(bitsize); - test_bit3=get_rand_bit(bitsize); - bitmap_set_prefix(map, test_bit1); - bitmap_set_prefix(map2, test_bit2); - test_bit3= test_bit2 > test_bit1 ? test_bit2 : test_bit1; - bitmap_set_prefix(map3, test_bit3); - bitmap_union(map, map2); - if (!bitmap_cmp(map, map3)) - goto error2; - bitmap_clear_all(map); - bitmap_clear_all(map2); - bitmap_clear_all(map3); - test_bit1=get_rand_bit(bitsize); - test_bit2=get_rand_bit(bitsize); - test_bit3=get_rand_bit(bitsize); - bitmap_set_prefix(map, test_bit1); - bitmap_set_prefix(map2, test_bit2); - bitmap_xor(map, map2); - test_bit3= test_bit2 > test_bit1 ? test_bit2 : test_bit1; - test_bit4= test_bit2 < test_bit1 ? test_bit2 : test_bit1; - bitmap_set_prefix(map3, test_bit3); - for (j=0; j < test_bit4; j++) - bitmap_clear_bit(map3, j); - if (!bitmap_cmp(map, map3)) - goto error3; - bitmap_clear_all(map); - bitmap_clear_all(map2); - bitmap_clear_all(map3); - test_bit1=get_rand_bit(bitsize); - test_bit2=get_rand_bit(bitsize); - test_bit3=get_rand_bit(bitsize); - bitmap_set_prefix(map, test_bit1); - bitmap_set_prefix(map2, test_bit2); - bitmap_subtract(map, map2); - if (test_bit2 < test_bit1) - { - bitmap_set_prefix(map3, test_bit1); - for (j=0; j < test_bit2; j++) - bitmap_clear_bit(map3, j); - } - if (!bitmap_cmp(map, map3)) - goto error4; - bitmap_clear_all(map); - bitmap_clear_all(map2); - bitmap_clear_all(map3); - test_bit1=get_rand_bit(bitsize); - bitmap_set_prefix(map, test_bit1); - bitmap_invert(map); - bitmap_set_all(map3); - for (j=0; j < test_bit1; j++) - bitmap_clear_bit(map3, j); - if (!bitmap_cmp(map, map3)) - goto error5; - bitmap_clear_all(map); - bitmap_clear_all(map3); - } - return FALSE; -error1: - printf("intersect error bitsize=%u,size1=%u,size2=%u", bitsize, - test_bit1,test_bit2); - return TRUE; -error2: - printf("union error bitsize=%u,size1=%u,size2=%u", bitsize, - test_bit1,test_bit2); - return TRUE; -error3: - printf("xor error bitsize=%u,size1=%u,size2=%u", bitsize, - test_bit1,test_bit2); - return TRUE; -error4: - printf("subtract error bitsize=%u,size1=%u,size2=%u", bitsize, - test_bit1,test_bit2); - return TRUE; -error5: - printf("invert error bitsize=%u,size=%u", bitsize, - test_bit1); - return TRUE; -} - -bool test_count_bits_set(MY_BITMAP *map, uint bitsize) -{ - uint i, bit_count=0, test_bit; - uint no_loops= bitsize > 128 ? 128 : bitsize; - for (i=0; i < no_loops; i++) - { - test_bit=get_rand_bit(bitsize); - if (!bitmap_is_set(map, test_bit)) - { - bitmap_set_bit(map, test_bit); - bit_count++; - } - } - if (bit_count==0 && bitsize > 0) - goto error1; - if (bitmap_bits_set(map) != bit_count) - goto error2; - return FALSE; -error1: - printf("No bits set bitsize = %u", bitsize); - return TRUE; -error2: - printf("Wrong count of bits set, bitsize = %u", bitsize); - return TRUE; -} - -bool test_get_first_bit(MY_BITMAP *map, uint bitsize) -{ - uint i, test_bit; - uint no_loops= bitsize > 128 ? 128 : bitsize; - for (i=0; i < no_loops; i++) - { - test_bit=get_rand_bit(bitsize); - bitmap_set_bit(map, test_bit); - if (bitmap_get_first_set(map) != test_bit) - goto error1; - bitmap_set_all(map); - bitmap_clear_bit(map, test_bit); - if (bitmap_get_first(map) != test_bit) - goto error2; - bitmap_clear_all(map); - } - return FALSE; -error1: - printf("get_first_set error bitsize=%u,prefix_size=%u",bitsize,test_bit); - return TRUE; -error2: - printf("get_first error bitsize= %u, prefix_size= %u",bitsize,test_bit); - return TRUE; -} - -bool test_get_next_bit(MY_BITMAP *map, uint bitsize) -{ - uint i, j, test_bit; - uint no_loops= bitsize > 128 ? 128 : bitsize; - for (i=0; i < no_loops; i++) - { - test_bit=get_rand_bit(bitsize); - for (j=0; j < test_bit; j++) - bitmap_set_next(map); - if (!bitmap_is_prefix(map, test_bit)) - goto error1; - bitmap_clear_all(map); - } - return FALSE; -error1: - printf("get_next error bitsize= %u, prefix_size= %u", bitsize,test_bit); - return TRUE; -} - -bool test_prefix(MY_BITMAP *map, uint bitsize) -{ - uint i, j, test_bit; - uint no_loops= bitsize > 128 ? 128 : bitsize; - for (i=0; i < no_loops; i++) - { - test_bit=get_rand_bit(bitsize); - bitmap_set_prefix(map, test_bit); - if (!bitmap_is_prefix(map, test_bit)) - goto error1; - bitmap_clear_all(map); - for (j=0; j < test_bit; j++) - bitmap_set_bit(map, j); - if (!bitmap_is_prefix(map, test_bit)) - goto error2; - bitmap_set_all(map); - for (j=bitsize - 1; ~(j-test_bit); j--) - bitmap_clear_bit(map, j); - if (!bitmap_is_prefix(map, test_bit)) - goto error3; - bitmap_clear_all(map); - } - return FALSE; -error1: - printf("prefix1 error bitsize = %u, prefix_size = %u", bitsize,test_bit); - return TRUE; -error2: - printf("prefix2 error bitsize = %u, prefix_size = %u", bitsize,test_bit); - return TRUE; -error3: - printf("prefix3 error bitsize = %u, prefix_size = %u", bitsize,test_bit); - return TRUE; -} - - -bool do_test(uint bitsize) -{ - MY_BITMAP map; - my_bitmap_map buf[1024]; - if (bitmap_init(&map, buf, bitsize, FALSE)) - { - printf("init error for bitsize %d", bitsize); - goto error; - } - if (test_set_get_clear_bit(&map,bitsize)) - goto error; - bitmap_clear_all(&map); - if (test_flip_bit(&map,bitsize)) - goto error; - bitmap_clear_all(&map); - if (test_operators(&map,bitsize)) - goto error; - bitmap_clear_all(&map); - if (test_get_all_bits(&map, bitsize)) - goto error; - bitmap_clear_all(&map); - if (test_compare_operators(&map,bitsize)) - goto error; - bitmap_clear_all(&map); - if (test_count_bits_set(&map,bitsize)) - goto error; - bitmap_clear_all(&map); - if (test_get_first_bit(&map,bitsize)) - goto error; - bitmap_clear_all(&map); - if (test_get_next_bit(&map,bitsize)) - goto error; - if (test_prefix(&map,bitsize)) - goto error; - return FALSE; -error: - printf("\n"); - return TRUE; -} - -int main() -{ - int i; - for (i= 1; i < 4096; i++) - { - printf("Start test for bitsize=%u\n",i); - if (do_test(i)) - return -1; - } - printf("OK\n"); - return 0; -} - -/* - In directory mysys: - make test_bitmap - will build the bitmap tests and ./test_bitmap will execute it -*/ - -#endif diff --git a/unittest/mysys/bitmap-t.c b/unittest/mysys/bitmap-t.c index 0bd21b63430..d5c1791ca14 100644 --- a/unittest/mysys/bitmap-t.c +++ b/unittest/mysys/bitmap-t.c @@ -1,4 +1,4 @@ -/* Copyright (C) 2006 MySQL AB +/* Copyright (c) 2000, 2011, Oracle and/or its affiliates. All rights reserved. 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 @@ -24,6 +24,8 @@ #include <tap.h> #include <m_string.h> +#define MAX_TESTED_BITMAP_SIZE 1024 + uint get_rand_bit(uint bitsize) { return (rand() % bitsize); @@ -75,12 +77,6 @@ error2: return TRUE; } -my_bool test_operators(MY_BITMAP *map __attribute__((unused)), - uint bitsize __attribute__((unused))) -{ - return FALSE; -} - my_bool test_get_all_bits(MY_BITMAP *map, uint bitsize) { uint i; @@ -129,8 +125,8 @@ my_bool test_compare_operators(MY_BITMAP *map, uint bitsize) uint no_loops= bitsize > 128 ? 128 : bitsize; MY_BITMAP map2_obj, map3_obj; MY_BITMAP *map2= &map2_obj, *map3= &map3_obj; - uint32 map2buf[1024]; - uint32 map3buf[1024]; + uint32 map2buf[MAX_TESTED_BITMAP_SIZE]; + uint32 map3buf[MAX_TESTED_BITMAP_SIZE]; bitmap_init(&map2_obj, map2buf, bitsize, FALSE); bitmap_init(&map3_obj, map3buf, bitsize, FALSE); bitmap_clear_all(map2); @@ -259,6 +255,19 @@ my_bool test_get_first_bit(MY_BITMAP *map, uint bitsize) { uint i, test_bit; uint no_loops= bitsize > 128 ? 128 : bitsize; + + bitmap_set_all(map); + for (i=0; i < bitsize; i++) + bitmap_clear_bit(map, i); + if (bitmap_get_first_set(map) != MY_BIT_NONE) + goto error1; + bitmap_clear_all(map); + for (i=0; i < bitsize; i++) + bitmap_set_bit(map, i); + if (bitmap_get_first(map) != MY_BIT_NONE) + goto error2; + bitmap_clear_all(map); + for (i=0; i < no_loops; i++) { test_bit=get_rand_bit(bitsize); @@ -321,6 +330,24 @@ my_bool test_prefix(MY_BITMAP *map, uint bitsize) goto error3; bitmap_clear_all(map); } + for (i=0; i < bitsize; i++) + { + if (bitmap_is_prefix(map, i + 1)) + goto error4; + bitmap_set_bit(map, i); + if (!bitmap_is_prefix(map, i + 1)) + goto error5; + test_bit=get_rand_bit(bitsize); + bitmap_set_bit(map, test_bit); + if (test_bit <= i && !bitmap_is_prefix(map, i + 1)) + goto error5; + else if (test_bit > i) + { + if (bitmap_is_prefix(map, i + 1)) + goto error4; + bitmap_clear_bit(map, test_bit); + } + } return FALSE; error1: diag("prefix1 error bitsize = %u, prefix_size = %u", bitsize,test_bit); @@ -331,13 +358,127 @@ error2: error3: diag("prefix3 error bitsize = %u, prefix_size = %u", bitsize,test_bit); return TRUE; +error4: + diag("prefix4 error bitsize = %u, i = %u", bitsize,i); + return TRUE; +error5: + diag("prefix5 error bitsize = %u, i = %u", bitsize,i); + return TRUE; +} + +my_bool test_compare(MY_BITMAP *map, uint bitsize) +{ + MY_BITMAP map2; + uint32 map2buf[MAX_TESTED_BITMAP_SIZE]; + uint i, test_bit; + uint no_loops= bitsize > 128 ? 128 : bitsize; + if (bitmap_init(&map2, map2buf, bitsize, FALSE)) + { + diag("init error for bitsize %d", bitsize); + return TRUE; + } + /* Test all 4 possible combinations of set/unset bits. */ + for (i=0; i < no_loops; i++) + { + test_bit=get_rand_bit(bitsize); + bitmap_clear_bit(map, test_bit); + bitmap_clear_bit(&map2, test_bit); + if (!bitmap_is_subset(map, &map2)) + goto error_is_subset; + bitmap_set_bit(map, test_bit); + if (bitmap_is_subset(map, &map2)) + goto error_is_subset; + bitmap_set_bit(&map2, test_bit); + if (!bitmap_is_subset(map, &map2)) + goto error_is_subset; + bitmap_clear_bit(map, test_bit); + if (!bitmap_is_subset(map, &map2)) + goto error_is_subset; + /* Note that test_bit is not cleared i map2. */ + } + bitmap_clear_all(map); + bitmap_clear_all(&map2); + /* Test all 4 possible combinations of set/unset bits. */ + for (i=0; i < no_loops; i++) + { + test_bit=get_rand_bit(bitsize); + if (bitmap_is_overlapping(map, &map2)) + goto error_is_overlapping; + bitmap_set_bit(map, test_bit); + if (bitmap_is_overlapping(map, &map2)) + goto error_is_overlapping; + bitmap_set_bit(&map2, test_bit); + if (!bitmap_is_overlapping(map, &map2)) + goto error_is_overlapping; + bitmap_clear_bit(map, test_bit); + if (bitmap_is_overlapping(map, &map2)) + goto error_is_overlapping; + bitmap_clear_bit(&map2, test_bit); + /* Note that test_bit is not cleared i map2. */ + } + return FALSE; +error_is_subset: + diag("is_subset error bitsize = %u", bitsize); + return TRUE; +error_is_overlapping: + diag("is_overlapping error bitsize = %u", bitsize); + return TRUE; } +my_bool test_intersect(MY_BITMAP *map, uint bitsize) +{ + uint bitsize2 = 1 + get_rand_bit(MAX_TESTED_BITMAP_SIZE - 1); + MY_BITMAP map2; + uint32 map2buf[bitsize2]; + uint i, test_bit1, test_bit2, test_bit3; + if (bitmap_init(&map2, map2buf, bitsize2, FALSE)) + { + diag("init error for bitsize %d", bitsize2); + return TRUE; + } + test_bit1= get_rand_bit(bitsize); + test_bit2= get_rand_bit(bitsize); + bitmap_set_bit(map, test_bit1); + bitmap_set_bit(map, test_bit2); + test_bit3= get_rand_bit(bitsize2); + bitmap_set_bit(&map2, test_bit3); + if (test_bit2 < bitsize2) + bitmap_set_bit(&map2, test_bit2); + + bitmap_intersect(map, &map2); + if (test_bit2 < bitsize2) + { + if (!bitmap_is_set(map, test_bit2)) + goto error; + bitmap_clear_bit(map, test_bit2); + } + if (test_bit1 == test_bit3) + { + if (!bitmap_is_set(map, test_bit1)) + goto error; + bitmap_clear_bit(map, test_bit1); + } + if (!bitmap_is_clear_all(map)) + goto error; + + bitmap_set_all(map); + bitmap_set_all(&map2); + for (i=0; i < bitsize2; i++) + bitmap_clear_bit(&map2, i); + bitmap_intersect(map, &map2); + if (!bitmap_is_clear_all(map)) + goto error; + return FALSE; +error: + diag("intersect error bitsize = %u, bit1 = %u, bit2 = %u, bit3 = %u", + bitsize, test_bit1, test_bit2, test_bit3); + return TRUE; +} my_bool do_test(uint bitsize) { MY_BITMAP map; - uint32 buf[1024]; + uint32 buf[MAX_TESTED_BITMAP_SIZE]; if (bitmap_init(&map, buf, bitsize, FALSE)) { diag("init error for bitsize %d", bitsize); @@ -349,9 +490,6 @@ my_bool do_test(uint bitsize) if (test_flip_bit(&map,bitsize)) goto error; bitmap_clear_all(&map); - if (test_operators(&map,bitsize)) - goto error; - bitmap_clear_all(&map); if (test_get_all_bits(&map, bitsize)) goto error; bitmap_clear_all(&map); @@ -366,8 +504,15 @@ my_bool do_test(uint bitsize) bitmap_clear_all(&map); if (test_get_next_bit(&map,bitsize)) goto error; + bitmap_clear_all(&map); if (test_prefix(&map,bitsize)) goto error; + bitmap_clear_all(&map); + if (test_compare(&map,bitsize)) + goto error; + bitmap_clear_all(&map); + if (test_intersect(&map,bitsize)) + goto error; return FALSE; error: return TRUE; @@ -377,7 +522,7 @@ int main() { int i; int const min_size = 1; - int const max_size = 1024; + int const max_size = MAX_TESTED_BITMAP_SIZE; MY_INIT("bitmap-t"); plan(max_size - min_size); |