1 /*
2 Copyright (c) 2006, 2012, Oracle and/or its affiliates. All rights reserved.
3
4 This program is free software; you can redistribute it and/or modify
5 it under the terms of the GNU General Public License as published by
6 the Free Software Foundation; version 2 of the License.
7
8 This program is distributed in the hope that it will be useful,
9 but WITHOUT ANY WARRANTY; without even the implied warranty of
10 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
11 GNU General Public License for more details.
12
13 You should have received a copy of the GNU General Public License
14 along with this program; if not, write to the Free Software
15 Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
16
17 This test was copied from the unit test inside the
18 mysys/my_bitmap.c file and adapted by Mats Kindahl to use the mytap
19 library.
20 */
21
22 #include <my_global.h>
23 #include <my_sys.h>
24 #include <my_bitmap.h>
25 #include <tap.h>
26 #include <m_string.h>
27
28 #define MAX_TESTED_BITMAP_SIZE 1024
29
get_rand_bit(uint bitsize)30 uint get_rand_bit(uint bitsize)
31 {
32 return (rand() % bitsize);
33 }
34
test_set_get_clear_bit(MY_BITMAP * map,uint bitsize)35 my_bool test_set_get_clear_bit(MY_BITMAP *map, uint bitsize)
36 {
37 uint i, test_bit;
38 uint no_loops= bitsize > 128 ? 128 : bitsize;
39 for (i=0; i < no_loops; i++)
40 {
41 test_bit= get_rand_bit(bitsize);
42 bitmap_set_bit(map, test_bit);
43 if (!bitmap_is_set(map, test_bit))
44 goto error1;
45 bitmap_clear_bit(map, test_bit);
46 if (bitmap_is_set(map, test_bit))
47 goto error2;
48 }
49 return FALSE;
50 error1:
51 printf("Error in set bit, bit %u, bitsize = %u", test_bit, bitsize);
52 return TRUE;
53 error2:
54 printf("Error in clear bit, bit %u, bitsize = %u", test_bit, bitsize);
55 return TRUE;
56 }
57
test_flip_bit(MY_BITMAP * map,uint bitsize)58 my_bool test_flip_bit(MY_BITMAP *map, uint bitsize)
59 {
60 uint i, test_bit;
61 uint no_loops= bitsize > 128 ? 128 : bitsize;
62 for (i=0; i < no_loops; i++)
63 {
64 test_bit= get_rand_bit(bitsize);
65 bitmap_flip_bit(map, test_bit);
66 if (!bitmap_is_set(map, test_bit))
67 goto error1;
68 bitmap_flip_bit(map, test_bit);
69 if (bitmap_is_set(map, test_bit))
70 goto error2;
71 }
72 return FALSE;
73 error1:
74 printf("Error in flip bit 1, bit %u, bitsize = %u", test_bit, bitsize);
75 return TRUE;
76 error2:
77 printf("Error in flip bit 2, bit %u, bitsize = %u", test_bit, bitsize);
78 return TRUE;
79 }
80
test_get_all_bits(MY_BITMAP * map,uint bitsize)81 my_bool test_get_all_bits(MY_BITMAP *map, uint bitsize)
82 {
83 uint i;
84 bitmap_set_all(map);
85 if (!bitmap_is_set_all(map))
86 goto error1;
87 if (!bitmap_is_prefix(map, bitsize))
88 goto error5;
89 bitmap_clear_all(map);
90 if (!bitmap_is_clear_all(map))
91 goto error2;
92 if (!bitmap_is_prefix(map, 0))
93 goto error6;
94 for (i=0; i<bitsize;i++)
95 bitmap_set_bit(map, i);
96 if (!bitmap_is_set_all(map))
97 goto error3;
98 for (i=0; i<bitsize;i++)
99 bitmap_clear_bit(map, i);
100 if (!bitmap_is_clear_all(map))
101 goto error4;
102 return FALSE;
103 error1:
104 diag("Error in set_all, bitsize = %u", bitsize);
105 return TRUE;
106 error2:
107 diag("Error in clear_all, bitsize = %u", bitsize);
108 return TRUE;
109 error3:
110 diag("Error in bitmap_is_set_all, bitsize = %u", bitsize);
111 return TRUE;
112 error4:
113 diag("Error in bitmap_is_clear_all, bitsize = %u", bitsize);
114 return TRUE;
115 error5:
116 diag("Error in set_all through set_prefix, bitsize = %u", bitsize);
117 return TRUE;
118 error6:
119 diag("Error in clear_all through set_prefix, bitsize = %u", bitsize);
120 return TRUE;
121 }
122
test_compare_operators(MY_BITMAP * map,uint bitsize)123 my_bool test_compare_operators(MY_BITMAP *map, uint bitsize)
124 {
125 uint i, j, test_bit1, test_bit2, test_bit3,test_bit4;
126 uint no_loops= bitsize > 128 ? 128 : bitsize;
127 MY_BITMAP map2_obj, map3_obj;
128 MY_BITMAP *map2= &map2_obj, *map3= &map3_obj;
129 uint32 map2buf[MAX_TESTED_BITMAP_SIZE];
130 uint32 map3buf[MAX_TESTED_BITMAP_SIZE];
131 bitmap_init(&map2_obj, map2buf, bitsize, FALSE);
132 bitmap_init(&map3_obj, map3buf, bitsize, FALSE);
133 bitmap_clear_all(map2);
134 bitmap_clear_all(map3);
135 for (i=0; i < no_loops; i++)
136 {
137 test_bit1=get_rand_bit(bitsize);
138 bitmap_set_prefix(map, test_bit1);
139 test_bit2=get_rand_bit(bitsize);
140 bitmap_set_prefix(map2, test_bit2);
141 bitmap_intersect(map, map2);
142 test_bit3= test_bit2 < test_bit1 ? test_bit2 : test_bit1;
143 bitmap_set_prefix(map3, test_bit3);
144 if (!bitmap_cmp(map, map3))
145 goto error1;
146 bitmap_clear_all(map);
147 bitmap_clear_all(map2);
148 bitmap_clear_all(map3);
149 test_bit1=get_rand_bit(bitsize);
150 test_bit2=get_rand_bit(bitsize);
151 test_bit3=get_rand_bit(bitsize);
152 bitmap_set_prefix(map, test_bit1);
153 bitmap_set_prefix(map2, test_bit2);
154 test_bit3= test_bit2 > test_bit1 ? test_bit2 : test_bit1;
155 bitmap_set_prefix(map3, test_bit3);
156 bitmap_union(map, map2);
157 if (!bitmap_cmp(map, map3))
158 goto error2;
159 bitmap_clear_all(map);
160 bitmap_clear_all(map2);
161 bitmap_clear_all(map3);
162 test_bit1=get_rand_bit(bitsize);
163 test_bit2=get_rand_bit(bitsize);
164 test_bit3=get_rand_bit(bitsize);
165 bitmap_set_prefix(map, test_bit1);
166 bitmap_set_prefix(map2, test_bit2);
167 bitmap_xor(map, map2);
168 test_bit3= test_bit2 > test_bit1 ? test_bit2 : test_bit1;
169 test_bit4= test_bit2 < test_bit1 ? test_bit2 : test_bit1;
170 bitmap_set_prefix(map3, test_bit3);
171 for (j=0; j < test_bit4; j++)
172 bitmap_clear_bit(map3, j);
173 if (!bitmap_cmp(map, map3))
174 goto error3;
175 bitmap_clear_all(map);
176 bitmap_clear_all(map2);
177 bitmap_clear_all(map3);
178 test_bit1=get_rand_bit(bitsize);
179 test_bit2=get_rand_bit(bitsize);
180 test_bit3=get_rand_bit(bitsize);
181 bitmap_set_prefix(map, test_bit1);
182 bitmap_set_prefix(map2, test_bit2);
183 bitmap_subtract(map, map2);
184 if (test_bit2 < test_bit1)
185 {
186 bitmap_set_prefix(map3, test_bit1);
187 for (j=0; j < test_bit2; j++)
188 bitmap_clear_bit(map3, j);
189 }
190 if (!bitmap_cmp(map, map3))
191 goto error4;
192 bitmap_clear_all(map);
193 bitmap_clear_all(map2);
194 bitmap_clear_all(map3);
195 test_bit1=get_rand_bit(bitsize);
196 bitmap_set_prefix(map, test_bit1);
197 bitmap_invert(map);
198 bitmap_set_all(map3);
199 for (j=0; j < test_bit1; j++)
200 bitmap_clear_bit(map3, j);
201 if (!bitmap_cmp(map, map3))
202 goto error5;
203 bitmap_clear_all(map);
204 bitmap_clear_all(map3);
205 }
206 return FALSE;
207 error1:
208 diag("intersect error bitsize=%u,size1=%u,size2=%u", bitsize,
209 test_bit1,test_bit2);
210 return TRUE;
211 error2:
212 diag("union error bitsize=%u,size1=%u,size2=%u", bitsize,
213 test_bit1,test_bit2);
214 return TRUE;
215 error3:
216 diag("xor error bitsize=%u,size1=%u,size2=%u", bitsize,
217 test_bit1,test_bit2);
218 return TRUE;
219 error4:
220 diag("subtract error bitsize=%u,size1=%u,size2=%u", bitsize,
221 test_bit1,test_bit2);
222 return TRUE;
223 error5:
224 diag("invert error bitsize=%u,size=%u", bitsize,
225 test_bit1);
226 return TRUE;
227 }
228
test_count_bits_set(MY_BITMAP * map,uint bitsize)229 my_bool test_count_bits_set(MY_BITMAP *map, uint bitsize)
230 {
231 uint i, bit_count=0, test_bit;
232 uint no_loops= bitsize > 128 ? 128 : bitsize;
233 for (i=0; i < no_loops; i++)
234 {
235 test_bit=get_rand_bit(bitsize);
236 if (!bitmap_is_set(map, test_bit))
237 {
238 bitmap_set_bit(map, test_bit);
239 bit_count++;
240 }
241 }
242 if (bit_count==0 && bitsize > 0)
243 goto error1;
244 if (bitmap_bits_set(map) != bit_count)
245 goto error2;
246 return FALSE;
247 error1:
248 diag("No bits set bitsize = %u", bitsize);
249 return TRUE;
250 error2:
251 diag("Wrong count of bits set, bitsize = %u", bitsize);
252 return TRUE;
253 }
254
test_get_first_bit(MY_BITMAP * map,uint bitsize)255 my_bool test_get_first_bit(MY_BITMAP *map, uint bitsize)
256 {
257 uint i, test_bit= 0;
258 uint no_loops= bitsize > 128 ? 128 : bitsize;
259
260 bitmap_set_all(map);
261 for (i=0; i < bitsize; i++)
262 bitmap_clear_bit(map, i);
263 if (bitmap_get_first_set(map) != MY_BIT_NONE)
264 goto error1;
265 bitmap_clear_all(map);
266 for (i=0; i < bitsize; i++)
267 bitmap_set_bit(map, i);
268 if (bitmap_get_first(map) != MY_BIT_NONE)
269 goto error2;
270 bitmap_clear_all(map);
271
272 for (i=0; i < no_loops; i++)
273 {
274 test_bit=get_rand_bit(bitsize);
275 bitmap_set_bit(map, test_bit);
276 if (bitmap_get_first_set(map) != test_bit)
277 goto error1;
278 bitmap_set_all(map);
279 bitmap_clear_bit(map, test_bit);
280 if (bitmap_get_first(map) != test_bit)
281 goto error2;
282 bitmap_clear_all(map);
283 }
284 return FALSE;
285 error1:
286 diag("get_first_set error bitsize=%u,prefix_size=%u",bitsize,test_bit);
287 return TRUE;
288 error2:
289 diag("get_first error bitsize= %u, prefix_size= %u",bitsize,test_bit);
290 return TRUE;
291 }
292
test_get_next_bit(MY_BITMAP * map,uint bitsize)293 my_bool test_get_next_bit(MY_BITMAP *map, uint bitsize)
294 {
295 uint i, j, test_bit;
296 uint no_loops= bitsize > 128 ? 128 : bitsize;
297 for (i=0; i < no_loops; i++)
298 {
299 test_bit=get_rand_bit(bitsize);
300 for (j=0; j < test_bit; j++)
301 bitmap_set_next(map);
302 if (!bitmap_is_prefix(map, test_bit))
303 goto error1;
304 bitmap_clear_all(map);
305 }
306 return FALSE;
307 error1:
308 diag("get_next error bitsize= %u, prefix_size= %u", bitsize,test_bit);
309 return TRUE;
310 }
311
test_prefix(MY_BITMAP * map,uint bitsize)312 my_bool test_prefix(MY_BITMAP *map, uint bitsize)
313 {
314 uint i, j, test_bit;
315 uint no_loops= bitsize > 128 ? 128 : bitsize;
316 for (i=0; i < no_loops; i++)
317 {
318 test_bit=get_rand_bit(bitsize);
319 bitmap_set_prefix(map, test_bit);
320 if (!bitmap_is_prefix(map, test_bit))
321 goto error1;
322 bitmap_clear_all(map);
323 for (j=0; j < test_bit; j++)
324 bitmap_set_bit(map, j);
325 if (!bitmap_is_prefix(map, test_bit))
326 goto error2;
327 bitmap_set_all(map);
328 for (j=bitsize - 1; ~(j-test_bit); j--)
329 bitmap_clear_bit(map, j);
330 if (!bitmap_is_prefix(map, test_bit))
331 goto error3;
332 bitmap_clear_all(map);
333 }
334 for (i=0; i < bitsize; i++)
335 {
336 if (bitmap_is_prefix(map, i + 1))
337 goto error4;
338 bitmap_set_bit(map, i);
339 if (!bitmap_is_prefix(map, i + 1))
340 goto error5;
341 test_bit=get_rand_bit(bitsize);
342 bitmap_set_bit(map, test_bit);
343 if (test_bit <= i && !bitmap_is_prefix(map, i + 1))
344 goto error5;
345 else if (test_bit > i)
346 {
347 if (bitmap_is_prefix(map, i + 1))
348 goto error4;
349 bitmap_clear_bit(map, test_bit);
350 }
351 }
352 return FALSE;
353 error1:
354 diag("prefix1 error bitsize = %u, prefix_size = %u", bitsize,test_bit);
355 return TRUE;
356 error2:
357 diag("prefix2 error bitsize = %u, prefix_size = %u", bitsize,test_bit);
358 return TRUE;
359 error3:
360 diag("prefix3 error bitsize = %u, prefix_size = %u", bitsize,test_bit);
361 return TRUE;
362 error4:
363 diag("prefix4 error bitsize = %u, i = %u", bitsize,i);
364 return TRUE;
365 error5:
366 diag("prefix5 error bitsize = %u, i = %u", bitsize,i);
367 return TRUE;
368 }
369
test_compare(MY_BITMAP * map,uint bitsize)370 my_bool test_compare(MY_BITMAP *map, uint bitsize)
371 {
372 MY_BITMAP map2;
373 uint32 map2buf[MAX_TESTED_BITMAP_SIZE];
374 uint i, test_bit;
375 uint no_loops= bitsize > 128 ? 128 : bitsize;
376 if (bitmap_init(&map2, map2buf, bitsize, FALSE))
377 {
378 diag("init error for bitsize %d", bitsize);
379 return TRUE;
380 }
381 /* Test all 4 possible combinations of set/unset bits. */
382 for (i=0; i < no_loops; i++)
383 {
384 test_bit=get_rand_bit(bitsize);
385 bitmap_clear_bit(map, test_bit);
386 bitmap_clear_bit(&map2, test_bit);
387 if (!bitmap_is_subset(map, &map2))
388 goto error_is_subset;
389 bitmap_set_bit(map, test_bit);
390 if (bitmap_is_subset(map, &map2))
391 goto error_is_subset;
392 bitmap_set_bit(&map2, test_bit);
393 if (!bitmap_is_subset(map, &map2))
394 goto error_is_subset;
395 bitmap_clear_bit(map, test_bit);
396 if (!bitmap_is_subset(map, &map2))
397 goto error_is_subset;
398 /* Note that test_bit is not cleared i map2. */
399 }
400 bitmap_clear_all(map);
401 bitmap_clear_all(&map2);
402 /* Test all 4 possible combinations of set/unset bits. */
403 for (i=0; i < no_loops; i++)
404 {
405 test_bit=get_rand_bit(bitsize);
406 if (bitmap_is_overlapping(map, &map2))
407 goto error_is_overlapping;
408 bitmap_set_bit(map, test_bit);
409 if (bitmap_is_overlapping(map, &map2))
410 goto error_is_overlapping;
411 bitmap_set_bit(&map2, test_bit);
412 if (!bitmap_is_overlapping(map, &map2))
413 goto error_is_overlapping;
414 bitmap_clear_bit(map, test_bit);
415 if (bitmap_is_overlapping(map, &map2))
416 goto error_is_overlapping;
417 bitmap_clear_bit(&map2, test_bit);
418 /* Note that test_bit is not cleared i map2. */
419 }
420 return FALSE;
421 error_is_subset:
422 diag("is_subset error bitsize = %u", bitsize);
423 return TRUE;
424 error_is_overlapping:
425 diag("is_overlapping error bitsize = %u", bitsize);
426 return TRUE;
427 }
428
test_intersect(MY_BITMAP * map,uint bitsize)429 my_bool test_intersect(MY_BITMAP *map, uint bitsize)
430 {
431 uint bitsize2 = 1 + get_rand_bit(MAX_TESTED_BITMAP_SIZE - 1);
432 MY_BITMAP map2;
433 uint32 map2buf[MAX_TESTED_BITMAP_SIZE];
434 uint i, test_bit1, test_bit2, test_bit3;
435 if (bitmap_init(&map2, map2buf, bitsize2, FALSE))
436 {
437 diag("init error for bitsize %d", bitsize2);
438 return TRUE;
439 }
440 test_bit1= get_rand_bit(bitsize);
441 test_bit2= get_rand_bit(bitsize);
442 bitmap_set_bit(map, test_bit1);
443 bitmap_set_bit(map, test_bit2);
444 test_bit3= get_rand_bit(bitsize2);
445 bitmap_set_bit(&map2, test_bit3);
446 if (test_bit2 < bitsize2)
447 bitmap_set_bit(&map2, test_bit2);
448
449 bitmap_intersect(map, &map2);
450 if (test_bit2 < bitsize2)
451 {
452 if (!bitmap_is_set(map, test_bit2))
453 goto error;
454 bitmap_clear_bit(map, test_bit2);
455 }
456 if (test_bit1 == test_bit3)
457 {
458 if (!bitmap_is_set(map, test_bit1))
459 goto error;
460 bitmap_clear_bit(map, test_bit1);
461 }
462 if (!bitmap_is_clear_all(map))
463 goto error;
464
465 bitmap_set_all(map);
466 bitmap_set_all(&map2);
467 for (i=0; i < bitsize2; i++)
468 bitmap_clear_bit(&map2, i);
469 bitmap_intersect(map, &map2);
470 if (!bitmap_is_clear_all(map))
471 goto error;
472 return FALSE;
473 error:
474 diag("intersect error bitsize = %u, bit1 = %u, bit2 = %u, bit3 = %u",
475 bitsize, test_bit1, test_bit2, test_bit3);
476 return TRUE;
477 }
478
do_test(uint bitsize)479 my_bool do_test(uint bitsize)
480 {
481 MY_BITMAP map;
482 uint32 buf[MAX_TESTED_BITMAP_SIZE];
483 if (bitmap_init(&map, buf, bitsize, FALSE))
484 {
485 diag("init error for bitsize %d", bitsize);
486 goto error;
487 }
488 if (test_set_get_clear_bit(&map,bitsize))
489 goto error;
490 bitmap_clear_all(&map);
491 if (test_flip_bit(&map,bitsize))
492 goto error;
493 bitmap_clear_all(&map);
494 if (test_get_all_bits(&map, bitsize))
495 goto error;
496 bitmap_clear_all(&map);
497 if (test_compare_operators(&map,bitsize))
498 goto error;
499 bitmap_clear_all(&map);
500 if (test_count_bits_set(&map,bitsize))
501 goto error;
502 bitmap_clear_all(&map);
503 if (test_get_first_bit(&map,bitsize))
504 goto error;
505 bitmap_clear_all(&map);
506 if (test_get_next_bit(&map,bitsize))
507 goto error;
508 bitmap_clear_all(&map);
509 if (test_prefix(&map,bitsize))
510 goto error;
511 bitmap_clear_all(&map);
512 if (test_compare(&map,bitsize))
513 goto error;
514 bitmap_clear_all(&map);
515 if (test_intersect(&map,bitsize))
516 goto error;
517 return FALSE;
518 error:
519 return TRUE;
520 }
521
main()522 int main()
523 {
524 int i;
525 int const min_size = 1;
526 int const max_size = MAX_TESTED_BITMAP_SIZE;
527 MY_INIT("bitmap-t");
528
529 plan(max_size - min_size);
530 for (i= min_size; i < max_size; i++)
531 ok(do_test(i) == 0, "bitmap size %d", i);
532 return exit_status();
533 }
534