1/*
2 Copyright (c) 2006, 2012, Oracle and/or its affiliates.
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
30uint get_rand_bit(uint bitsize)
31{
32 return (rand() % bitsize);
33}
34
35my_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;
50error1:
51 printf("Error in set bit, bit %u, bitsize = %u", test_bit, bitsize);
52 return TRUE;
53error2:
54 printf("Error in clear bit, bit %u, bitsize = %u", test_bit, bitsize);
55 return TRUE;
56}
57
58my_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;
73error1:
74 printf("Error in flip bit 1, bit %u, bitsize = %u", test_bit, bitsize);
75 return TRUE;
76error2:
77 printf("Error in flip bit 2, bit %u, bitsize = %u", test_bit, bitsize);
78 return TRUE;
79}
80
81
82my_bool test_get_all_bits(MY_BITMAP *map, uint bitsize)
83{
84 uint i;
85 bitmap_set_all(map);
86 if (!bitmap_is_set_all(map))
87 goto error1;
88 if (!bitmap_is_prefix(map, bitsize))
89 goto error5;
90 bitmap_clear_all(map);
91 if (!bitmap_is_clear_all(map))
92 goto error2;
93 if (!bitmap_is_prefix(map, 0))
94 goto error6;
95 for (i=0; i<bitsize;i++)
96 bitmap_set_bit(map, i);
97 if (!bitmap_is_set_all(map))
98 goto error3;
99 for (i=0; i<bitsize;i++)
100 bitmap_clear_bit(map, i);
101 if (!bitmap_is_clear_all(map))
102 goto error4;
103 return FALSE;
104error1:
105 diag("Error in set_all, bitsize = %u", bitsize);
106 return TRUE;
107error2:
108 diag("Error in clear_all, bitsize = %u", bitsize);
109 return TRUE;
110error3:
111 diag("Error in bitmap_is_set_all, bitsize = %u", bitsize);
112 return TRUE;
113error4:
114 diag("Error in bitmap_is_clear_all, bitsize = %u", bitsize);
115 return TRUE;
116error5:
117 diag("Error in set_all through set_prefix, bitsize = %u", bitsize);
118 return TRUE;
119error6:
120 diag("Error in clear_all through set_prefix, bitsize = %u", bitsize);
121 return TRUE;
122}
123
124my_bool test_compare_operators(MY_BITMAP *map, uint bitsize)
125{
126 uint i, j, test_bit1, test_bit2, test_bit3,test_bit4;
127 uint no_loops= bitsize > 128 ? 128 : bitsize;
128 MY_BITMAP map2_obj, map3_obj;
129 MY_BITMAP *map2= &map2_obj, *map3= &map3_obj;
130 my_bitmap_map map2buf[MAX_TESTED_BITMAP_SIZE];
131 my_bitmap_map map3buf[MAX_TESTED_BITMAP_SIZE];
132 my_bitmap_init(&map2_obj, map2buf, bitsize, FALSE);
133 my_bitmap_init(&map3_obj, map3buf, bitsize, FALSE);
134 bitmap_clear_all(map2);
135 bitmap_clear_all(map3);
136 for (i=0; i < no_loops; i++)
137 {
138 test_bit1=get_rand_bit(bitsize);
139 bitmap_set_prefix(map, test_bit1);
140 test_bit2=get_rand_bit(bitsize);
141 bitmap_set_prefix(map2, test_bit2);
142 bitmap_intersect(map, map2);
143 test_bit3= test_bit2 < test_bit1 ? test_bit2 : test_bit1;
144 bitmap_set_prefix(map3, test_bit3);
145 if (!bitmap_cmp(map, map3))
146 goto error1;
147 bitmap_clear_all(map);
148 bitmap_clear_all(map2);
149 bitmap_clear_all(map3);
150 test_bit1=get_rand_bit(bitsize);
151 test_bit2=get_rand_bit(bitsize);
152 test_bit3=get_rand_bit(bitsize);
153 bitmap_set_prefix(map, test_bit1);
154 bitmap_set_prefix(map2, test_bit2);
155 test_bit3= test_bit2 > test_bit1 ? test_bit2 : test_bit1;
156 bitmap_set_prefix(map3, test_bit3);
157 bitmap_union(map, map2);
158 if (!bitmap_cmp(map, map3))
159 goto error2;
160 bitmap_clear_all(map);
161 bitmap_clear_all(map2);
162 bitmap_clear_all(map3);
163 test_bit1=get_rand_bit(bitsize);
164 test_bit2=get_rand_bit(bitsize);
165 test_bit3=get_rand_bit(bitsize);
166 bitmap_set_prefix(map, test_bit1);
167 bitmap_set_prefix(map2, test_bit2);
168 bitmap_xor(map, map2);
169 test_bit3= test_bit2 > test_bit1 ? test_bit2 : test_bit1;
170 test_bit4= test_bit2 < test_bit1 ? test_bit2 : test_bit1;
171 bitmap_set_prefix(map3, test_bit3);
172 for (j=0; j < test_bit4; j++)
173 bitmap_clear_bit(map3, j);
174 if (!bitmap_cmp(map, map3))
175 goto error3;
176 bitmap_clear_all(map);
177 bitmap_clear_all(map2);
178 bitmap_clear_all(map3);
179 test_bit1=get_rand_bit(bitsize);
180 test_bit2=get_rand_bit(bitsize);
181 test_bit3=get_rand_bit(bitsize);
182 bitmap_set_prefix(map, test_bit1);
183 bitmap_set_prefix(map2, test_bit2);
184 bitmap_subtract(map, map2);
185 if (test_bit2 < test_bit1)
186 {
187 bitmap_set_prefix(map3, test_bit1);
188 for (j=0; j < test_bit2; j++)
189 bitmap_clear_bit(map3, j);
190 }
191 if (!bitmap_cmp(map, map3))
192 goto error4;
193 bitmap_clear_all(map);
194 bitmap_clear_all(map2);
195 bitmap_clear_all(map3);
196 test_bit1=get_rand_bit(bitsize);
197 bitmap_set_prefix(map, test_bit1);
198 bitmap_invert(map);
199 bitmap_set_all(map3);
200 for (j=0; j < test_bit1; j++)
201 bitmap_clear_bit(map3, j);
202 if (!bitmap_cmp(map, map3))
203 goto error5;
204 bitmap_clear_all(map);
205 bitmap_clear_all(map3);
206 }
207 return FALSE;
208error1:
209 diag("intersect error bitsize=%u,size1=%u,size2=%u", bitsize,
210 test_bit1,test_bit2);
211 return TRUE;
212error2:
213 diag("union error bitsize=%u,size1=%u,size2=%u", bitsize,
214 test_bit1,test_bit2);
215 return TRUE;
216error3:
217 diag("xor error bitsize=%u,size1=%u,size2=%u", bitsize,
218 test_bit1,test_bit2);
219 return TRUE;
220error4:
221 diag("subtract error bitsize=%u,size1=%u,size2=%u", bitsize,
222 test_bit1,test_bit2);
223 return TRUE;
224error5:
225 diag("invert error bitsize=%u,size=%u", bitsize,
226 test_bit1);
227 return TRUE;
228}
229
230my_bool test_count_bits_set(MY_BITMAP *map, uint bitsize)
231{
232 uint i, bit_count=0, test_bit;
233 uint no_loops= bitsize > 128 ? 128 : bitsize;
234 for (i=0; i < no_loops; i++)
235 {
236 test_bit=get_rand_bit(bitsize);
237 if (!bitmap_is_set(map, test_bit))
238 {
239 bitmap_set_bit(map, test_bit);
240 bit_count++;
241 }
242 }
243 if (bit_count==0 && bitsize > 0)
244 goto error1;
245 if (bitmap_bits_set(map) != bit_count)
246 goto error2;
247 return FALSE;
248error1:
249 diag("No bits set bitsize = %u", bitsize);
250 return TRUE;
251error2:
252 diag("Wrong count of bits set, bitsize = %u", bitsize);
253 return TRUE;
254}
255
256my_bool test_get_first_bit(MY_BITMAP *map, uint bitsize)
257{
258 uint i, test_bit= 0;
259 uint no_loops= bitsize > 128 ? 128 : bitsize;
260
261 bitmap_set_all(map);
262 for (i=0; i < bitsize; i++)
263 bitmap_clear_bit(map, i);
264 if (bitmap_get_first_set(map) != MY_BIT_NONE)
265 goto error1;
266 bitmap_clear_all(map);
267 for (i=0; i < bitsize; i++)
268 bitmap_set_bit(map, i);
269 if (bitmap_get_first(map) != MY_BIT_NONE)
270 goto error2;
271 bitmap_clear_all(map);
272
273 for (i=0; i < no_loops; i++)
274 {
275 test_bit=get_rand_bit(bitsize);
276 bitmap_set_bit(map, test_bit);
277 if (bitmap_get_first_set(map) != test_bit)
278 goto error1;
279 bitmap_set_all(map);
280 bitmap_clear_bit(map, test_bit);
281 if (bitmap_get_first(map) != test_bit)
282 goto error2;
283 bitmap_clear_all(map);
284 }
285 return FALSE;
286error1:
287 diag("get_first_set error bitsize=%u,prefix_size=%u",bitsize,test_bit);
288 return TRUE;
289error2:
290 diag("get_first error bitsize= %u, prefix_size= %u",bitsize,test_bit);
291 return TRUE;
292}
293
294my_bool test_get_next_bit(MY_BITMAP *map, uint bitsize)
295{
296 uint i, j, test_bit;
297 uint no_loops= bitsize > 128 ? 128 : bitsize;
298 for (i=0; i < no_loops; i++)
299 {
300 test_bit=get_rand_bit(bitsize);
301 for (j=0; j < test_bit; j++)
302 bitmap_set_next(map);
303 if (!bitmap_is_prefix(map, test_bit))
304 goto error1;
305 bitmap_clear_all(map);
306 }
307 return FALSE;
308error1:
309 diag("get_next error bitsize= %u, prefix_size= %u", bitsize,test_bit);
310 return TRUE;
311}
312
313my_bool test_prefix(MY_BITMAP *map, uint bitsize)
314{
315 uint i, j, test_bit;
316 uint no_loops= bitsize > 128 ? 128 : bitsize;
317 for (i=0; i < no_loops; i++)
318 {
319 test_bit=get_rand_bit(bitsize);
320 bitmap_set_prefix(map, test_bit);
321 if (!bitmap_is_prefix(map, test_bit))
322 goto error1;
323 bitmap_clear_all(map);
324 for (j=0; j < test_bit; j++)
325 bitmap_set_bit(map, j);
326 if (!bitmap_is_prefix(map, test_bit))
327 goto error2;
328 bitmap_set_all(map);
329 for (j=bitsize - 1; ~(j-test_bit); j--)
330 bitmap_clear_bit(map, j);
331 if (!bitmap_is_prefix(map, test_bit))
332 goto error3;
333 bitmap_clear_all(map);
334 }
335 for (i=0; i < bitsize; i++)
336 {
337 if (bitmap_is_prefix(map, i + 1))
338 goto error4;
339 bitmap_set_bit(map, i);
340 if (!bitmap_is_prefix(map, i + 1))
341 goto error5;
342 test_bit=get_rand_bit(bitsize);
343 bitmap_set_bit(map, test_bit);
344 if (test_bit <= i && !bitmap_is_prefix(map, i + 1))
345 goto error5;
346 else if (test_bit > i)
347 {
348 if (bitmap_is_prefix(map, i + 1))
349 goto error4;
350 bitmap_clear_bit(map, test_bit);
351 }
352 }
353 return FALSE;
354error1:
355 diag("prefix1 error bitsize = %u, prefix_size = %u", bitsize,test_bit);
356 return TRUE;
357error2:
358 diag("prefix2 error bitsize = %u, prefix_size = %u", bitsize,test_bit);
359 return TRUE;
360error3:
361 diag("prefix3 error bitsize = %u, prefix_size = %u", bitsize,test_bit);
362 return TRUE;
363error4:
364 diag("prefix4 error bitsize = %u, i = %u", bitsize,i);
365 return TRUE;
366error5:
367 diag("prefix5 error bitsize = %u, i = %u", bitsize,i);
368 return TRUE;
369}
370
371my_bool test_compare(MY_BITMAP *map, uint bitsize)
372{
373 MY_BITMAP map2;
374 uint32 map2buf[MAX_TESTED_BITMAP_SIZE];
375 uint i, test_bit;
376 uint no_loops= bitsize > 128 ? 128 : bitsize;
377 if (my_bitmap_init(&map2, map2buf, bitsize, FALSE))
378 {
379 diag("init error for bitsize %d", bitsize);
380 return TRUE;
381 }
382 /* Test all 4 possible combinations of set/unset bits. */
383 for (i=0; i < no_loops; i++)
384 {
385 test_bit=get_rand_bit(bitsize);
386 bitmap_clear_bit(map, test_bit);
387 bitmap_clear_bit(&map2, test_bit);
388 if (!bitmap_is_subset(map, &map2))
389 goto error_is_subset;
390 bitmap_set_bit(map, test_bit);
391 if (bitmap_is_subset(map, &map2))
392 goto error_is_subset;
393 bitmap_set_bit(&map2, test_bit);
394 if (!bitmap_is_subset(map, &map2))
395 goto error_is_subset;
396 bitmap_clear_bit(map, test_bit);
397 if (!bitmap_is_subset(map, &map2))
398 goto error_is_subset;
399 /* Note that test_bit is not cleared i map2. */
400 }
401 bitmap_clear_all(map);
402 bitmap_clear_all(&map2);
403 /* Test all 4 possible combinations of set/unset bits. */
404 for (i=0; i < no_loops; i++)
405 {
406 test_bit=get_rand_bit(bitsize);
407 if (bitmap_is_overlapping(map, &map2))
408 goto error_is_overlapping;
409 bitmap_set_bit(map, test_bit);
410 if (bitmap_is_overlapping(map, &map2))
411 goto error_is_overlapping;
412 bitmap_set_bit(&map2, test_bit);
413 if (!bitmap_is_overlapping(map, &map2))
414 goto error_is_overlapping;
415 bitmap_clear_bit(map, test_bit);
416 if (bitmap_is_overlapping(map, &map2))
417 goto error_is_overlapping;
418 bitmap_clear_bit(&map2, test_bit);
419 /* Note that test_bit is not cleared i map2. */
420 }
421 return FALSE;
422error_is_subset:
423 diag("is_subset error bitsize = %u", bitsize);
424 return TRUE;
425error_is_overlapping:
426 diag("is_overlapping error bitsize = %u", bitsize);
427 return TRUE;
428}
429
430my_bool test_intersect(MY_BITMAP *map, uint bitsize)
431{
432 uint bitsize2 = 1 + get_rand_bit(MAX_TESTED_BITMAP_SIZE - 1);
433 MY_BITMAP map2;
434 uint32 map2buf[MAX_TESTED_BITMAP_SIZE];
435 uint i, test_bit1, test_bit2, test_bit3;
436 if (my_bitmap_init(&map2, map2buf, bitsize2, FALSE))
437 {
438 diag("init error for bitsize %d", bitsize2);
439 return TRUE;
440 }
441 test_bit1= get_rand_bit(bitsize);
442 test_bit2= get_rand_bit(bitsize);
443 bitmap_set_bit(map, test_bit1);
444 bitmap_set_bit(map, test_bit2);
445 test_bit3= get_rand_bit(bitsize2);
446 bitmap_set_bit(&map2, test_bit3);
447 if (test_bit2 < bitsize2)
448 bitmap_set_bit(&map2, test_bit2);
449
450 bitmap_intersect(map, &map2);
451 if (test_bit2 < bitsize2)
452 {
453 if (!bitmap_is_set(map, test_bit2))
454 goto error;
455 bitmap_clear_bit(map, test_bit2);
456 }
457 if (test_bit1 == test_bit3)
458 {
459 if (!bitmap_is_set(map, test_bit1))
460 goto error;
461 bitmap_clear_bit(map, test_bit1);
462 }
463 if (!bitmap_is_clear_all(map))
464 goto error;
465
466 bitmap_set_all(map);
467 bitmap_set_all(&map2);
468 for (i=0; i < bitsize2; i++)
469 bitmap_clear_bit(&map2, i);
470 bitmap_intersect(map, &map2);
471 if (!bitmap_is_clear_all(map))
472 goto error;
473 return FALSE;
474error:
475 diag("intersect error bitsize = %u, bit1 = %u, bit2 = %u, bit3 = %u",
476 bitsize, test_bit1, test_bit2, test_bit3);
477 return TRUE;
478}
479
480my_bool do_test(uint bitsize)
481{
482 MY_BITMAP map;
483 my_bitmap_map buf[MAX_TESTED_BITMAP_SIZE];
484 if (my_bitmap_init(&map, buf, bitsize, FALSE))
485 {
486 diag("init error for bitsize %d", bitsize);
487 goto error;
488 }
489 if (test_set_get_clear_bit(&map,bitsize))
490 goto error;
491 bitmap_clear_all(&map);
492 if (test_flip_bit(&map,bitsize))
493 goto error;
494 bitmap_clear_all(&map);
495 if (test_get_all_bits(&map, bitsize))
496 goto error;
497 bitmap_clear_all(&map);
498 if (test_compare_operators(&map,bitsize))
499 goto error;
500 bitmap_clear_all(&map);
501 if (test_count_bits_set(&map,bitsize))
502 goto error;
503 bitmap_clear_all(&map);
504 if (test_get_first_bit(&map,bitsize))
505 goto error;
506 bitmap_clear_all(&map);
507 if (test_get_next_bit(&map,bitsize))
508 goto error;
509 bitmap_clear_all(&map);
510 if (test_prefix(&map,bitsize))
511 goto error;
512 bitmap_clear_all(&map);
513 if (test_compare(&map,bitsize))
514 goto error;
515 bitmap_clear_all(&map);
516 if (test_intersect(&map,bitsize))
517 goto error;
518 return FALSE;
519error:
520 return TRUE;
521}
522
523int main(int argc __attribute__((unused)),char *argv[])
524{
525 int i;
526 int const min_size = 1;
527 int const max_size = MAX_TESTED_BITMAP_SIZE;
528 MY_INIT(argv[0]);
529
530 plan((max_size - min_size)/7+1);
531
532 /*
533 It's ok to do steps in 7, as i module 64 will go trough all values 1..63.
534 Any errors in the code should manifest as we are working with integers
535 of size 16, 32, or 64 bits...
536 */
537 for (i= min_size; i < max_size; i+=7)
538 ok(do_test(i) == 0, "bitmap size %d", i);
539 my_end(0);
540 return exit_status();
541}
542