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-1335  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 
81 
test_get_all_bits(MY_BITMAP * map,uint bitsize)82 my_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;
104 error1:
105   diag("Error in set_all, bitsize = %u", bitsize);
106   return TRUE;
107 error2:
108   diag("Error in clear_all, bitsize = %u", bitsize);
109   return TRUE;
110 error3:
111   diag("Error in bitmap_is_set_all, bitsize = %u", bitsize);
112   return TRUE;
113 error4:
114   diag("Error in bitmap_is_clear_all, bitsize = %u", bitsize);
115   return TRUE;
116 error5:
117   diag("Error in set_all through set_prefix, bitsize = %u", bitsize);
118   return TRUE;
119 error6:
120   diag("Error in clear_all through set_prefix, bitsize = %u", bitsize);
121   return TRUE;
122 }
123 
test_compare_operators(MY_BITMAP * map,uint bitsize)124 my_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;
208 error1:
209   diag("intersect error  bitsize=%u,size1=%u,size2=%u", bitsize,
210   test_bit1,test_bit2);
211   return TRUE;
212 error2:
213   diag("union error  bitsize=%u,size1=%u,size2=%u", bitsize,
214   test_bit1,test_bit2);
215   return TRUE;
216 error3:
217   diag("xor error  bitsize=%u,size1=%u,size2=%u", bitsize,
218   test_bit1,test_bit2);
219   return TRUE;
220 error4:
221   diag("subtract error  bitsize=%u,size1=%u,size2=%u", bitsize,
222   test_bit1,test_bit2);
223   return TRUE;
224 error5:
225   diag("invert error  bitsize=%u,size=%u", bitsize,
226   test_bit1);
227   return TRUE;
228 }
229 
test_count_bits_set(MY_BITMAP * map,uint bitsize)230 my_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;
248 error1:
249   diag("No bits set  bitsize = %u", bitsize);
250   return TRUE;
251 error2:
252   diag("Wrong count of bits set, bitsize = %u", bitsize);
253   return TRUE;
254 }
255 
test_get_first_bit(MY_BITMAP * map,uint bitsize)256 my_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;
286 error1:
287   diag("get_first_set error bitsize=%u,prefix_size=%u",bitsize,test_bit);
288   return TRUE;
289 error2:
290   diag("get_first error bitsize= %u, prefix_size= %u",bitsize,test_bit);
291   return TRUE;
292 }
293 
test_get_next_bit(MY_BITMAP * map,uint bitsize)294 my_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;
308 error1:
309   diag("get_next error  bitsize= %u, prefix_size= %u", bitsize,test_bit);
310   return TRUE;
311 }
312 
test_prefix(MY_BITMAP * map,uint bitsize)313 my_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;
354 error1:
355   diag("prefix1 error  bitsize = %u, prefix_size = %u", bitsize,test_bit);
356   return TRUE;
357 error2:
358   diag("prefix2 error  bitsize = %u, prefix_size = %u", bitsize,test_bit);
359   return TRUE;
360 error3:
361   diag("prefix3 error  bitsize = %u, prefix_size = %u", bitsize,test_bit);
362   return TRUE;
363 error4:
364   diag("prefix4 error  bitsize = %u, i = %u", bitsize,i);
365   return TRUE;
366 error5:
367   diag("prefix5 error  bitsize = %u, i = %u", bitsize,i);
368   return TRUE;
369 }
370 
test_compare(MY_BITMAP * map,uint bitsize)371 my_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;
422 error_is_subset:
423   diag("is_subset error  bitsize = %u", bitsize);
424   return TRUE;
425 error_is_overlapping:
426   diag("is_overlapping error  bitsize = %u", bitsize);
427   return TRUE;
428 }
429 
test_intersect(MY_BITMAP * map,uint bitsize)430 my_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;
474 error:
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 
do_test(uint bitsize)480 my_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;
519 error:
520   return TRUE;
521 }
522 
main(int argc,char * argv[])523 int 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