summaryrefslogtreecommitdiff
path: root/mysys/my_bitmap.c
diff options
context:
space:
mode:
Diffstat (limited to 'mysys/my_bitmap.c')
-rw-r--r--mysys/my_bitmap.c385
1 files changed, 10 insertions, 375 deletions
diff --git a/mysys/my_bitmap.c b/mysys/my_bitmap.c
index 762a89cd921..8f86e5832f6 100644
--- a/mysys/my_bitmap.c
+++ b/mysys/my_bitmap.c
@@ -1,4 +1,6 @@
-/* Copyright (C) 2000 MySQL AB, 2008-2009 Sun Microsystems, Inc
+/* 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
@@ -258,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;
+ prefix_bytes++;
+ }
if ((d= no_bytes_in_map(map)-prefix_bytes))
bzero(m, d);
}
@@ -293,6 +298,7 @@ my_bool bitmap_is_prefix(const MY_BITMAP *map, uint prefix_size)
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;
@@ -307,8 +313,8 @@ 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;
- end= map->last_word_ptr;
+ my_bitmap_map *end= map->last_word_ptr;
+
for (; data_ptr < end; data_ptr++)
if (*data_ptr)
return FALSE;
@@ -493,6 +499,7 @@ void bitmap_copy(MY_BITMAP *map, const MY_BITMAP *map2)
DBUG_ASSERT(map->bitmap && map2->bitmap &&
map->n_bits==map2->n_bits);
end= map->last_word_ptr;
+
while (to <= end)
*to++ = *from++;
}
@@ -587,375 +594,3 @@ void bitmap_lock_clear_bit(MY_BITMAP *map, uint bitmap_bit)
bitmap_unlock(map);
}
-#ifdef MAIN
-
-uint get_rand_bit(uint bitsize)
-{
- return (rand() % bitsize);
-}
-
-my_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;
-}
-
-my_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;
-}
-
-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;
- 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;
-}
-
-my_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;
-}
-
-my_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;
-}
-
-my_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;
-}
-
-my_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;
-}
-
-my_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;
-}
-
-
-my_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
View Lorry Controller Status