MySQL 5.6.14 Source Code Document
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
my_bitmap-t.cc
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 
18 #include "my_config.h"
19 #include <gtest/gtest.h>
20 
21 #include <my_global.h>
22 #include <my_pthread.h>
23 #include <my_bitmap.h>
24 
25 namespace my_bitmap_unittest {
26 
27 const uint MAX_TESTED_BITMAP_SIZE= 1024;
28 
29 uint get_rand_bit(uint bitsize)
30 {
31  return (rand() % bitsize);
32 }
33 
34 bool test_set_get_clear_bit(MY_BITMAP *map, uint bitsize)
35 {
36  uint i, test_bit;
37  uint no_loops= bitsize > 128 ? 128 : bitsize;
38  for (i=0; i < no_loops; i++)
39  {
40  test_bit= get_rand_bit(bitsize);
41  bitmap_set_bit(map, test_bit);
42  if (!bitmap_is_set(map, test_bit))
43  goto error1;
44  bitmap_clear_bit(map, test_bit);
45  if (bitmap_is_set(map, test_bit))
46  goto error2;
47  }
48  return false;
49 error1:
50  ADD_FAILURE() << "Error in set bit bit=" << test_bit;
51  return true;
52 error2:
53  ADD_FAILURE() << "Error in clear bit bit=" << test_bit;
54  return true;
55 }
56 
57 bool test_flip_bit(MY_BITMAP *map, uint bitsize)
58 {
59  uint i, test_bit;
60  uint no_loops= bitsize > 128 ? 128 : bitsize;
61  for (i=0; i < no_loops; i++)
62  {
63  test_bit= get_rand_bit(bitsize);
64  bitmap_flip_bit(map, test_bit);
65  if (!bitmap_is_set(map, test_bit))
66  goto error1;
67  bitmap_flip_bit(map, test_bit);
68  if (bitmap_is_set(map, test_bit))
69  goto error2;
70  }
71  return false;
72 error1:
73  ADD_FAILURE() << "Error in flip bit 1 bit=" << test_bit;
74  return true;
75 error2:
76  ADD_FAILURE() << "Error in flip bit 2 bit=" << test_bit;
77  return true;
78 }
79 
80 bool test_get_all_bits(MY_BITMAP *map, uint bitsize)
81 {
82  uint i;
83  bitmap_set_all(map);
84  if (!bitmap_is_set_all(map))
85  goto error1;
86  if (!bitmap_is_prefix(map, bitsize))
87  goto error5;
88  bitmap_clear_all(map);
89  if (!bitmap_is_clear_all(map))
90  goto error2;
91  if (!bitmap_is_prefix(map, 0))
92  goto error6;
93  for (i=0; i<bitsize;i++)
94  bitmap_set_bit(map, i);
95  if (!bitmap_is_set_all(map))
96  goto error3;
97  for (i=0; i<bitsize;i++)
98  bitmap_clear_bit(map, i);
99  if (!bitmap_is_clear_all(map))
100  goto error4;
101  return false;
102 error1:
103  ADD_FAILURE() << "Error in set_all";
104  return true;
105 error2:
106  ADD_FAILURE() << "Error in clear_all";
107  return true;
108 error3:
109  ADD_FAILURE() << "Error in bitmap_is_set_all";
110  return true;
111 error4:
112  ADD_FAILURE() << "Error in bitmap_is_clear_all";
113  return true;
114 error5:
115  ADD_FAILURE() << "Error in set_all through set_prefix";
116  return true;
117 error6:
118  ADD_FAILURE() << "Error in clear_all through set_prefix";
119  return true;
120 }
121 
122 bool test_compare_operators(MY_BITMAP *map, uint bitsize)
123 {
124  uint i, j, test_bit1, test_bit2, test_bit3,test_bit4;
125  uint no_loops= bitsize > 128 ? 128 : bitsize;
126  MY_BITMAP map2_obj, map3_obj;
127  MY_BITMAP *map2= &map2_obj, *map3= &map3_obj;
128  my_bitmap_map map2buf[MAX_TESTED_BITMAP_SIZE];
129  my_bitmap_map map3buf[MAX_TESTED_BITMAP_SIZE];
130  bitmap_init(&map2_obj, map2buf, bitsize, false);
131  bitmap_init(&map3_obj, map3buf, bitsize, false);
132  bitmap_clear_all(map2);
133  bitmap_clear_all(map3);
134  for (i=0; i < no_loops; i++)
135  {
136  test_bit1=get_rand_bit(bitsize);
137  bitmap_set_prefix(map, test_bit1);
138  test_bit2=get_rand_bit(bitsize);
139  bitmap_set_prefix(map2, test_bit2);
140  bitmap_intersect(map, map2);
141  test_bit3= test_bit2 < test_bit1 ? test_bit2 : test_bit1;
142  bitmap_set_prefix(map3, test_bit3);
143  if (!bitmap_cmp(map, map3))
144  goto error1;
145  bitmap_clear_all(map);
146  bitmap_clear_all(map2);
147  bitmap_clear_all(map3);
148  test_bit1=get_rand_bit(bitsize);
149  test_bit2=get_rand_bit(bitsize);
150  test_bit3=get_rand_bit(bitsize);
151  bitmap_set_prefix(map, test_bit1);
152  bitmap_set_prefix(map2, test_bit2);
153  test_bit3= test_bit2 > test_bit1 ? test_bit2 : test_bit1;
154  bitmap_set_prefix(map3, test_bit3);
155  bitmap_union(map, map2);
156  if (!bitmap_cmp(map, map3))
157  goto error2;
158  bitmap_clear_all(map);
159  bitmap_clear_all(map2);
160  bitmap_clear_all(map3);
161  test_bit1=get_rand_bit(bitsize);
162  test_bit2=get_rand_bit(bitsize);
163  test_bit3=get_rand_bit(bitsize);
164  bitmap_set_prefix(map, test_bit1);
165  bitmap_set_prefix(map2, test_bit2);
166  bitmap_xor(map, map2);
167  test_bit3= test_bit2 > test_bit1 ? test_bit2 : test_bit1;
168  test_bit4= test_bit2 < test_bit1 ? test_bit2 : test_bit1;
169  bitmap_set_prefix(map3, test_bit3);
170  for (j=0; j < test_bit4; j++)
171  bitmap_clear_bit(map3, j);
172  if (!bitmap_cmp(map, map3))
173  goto error3;
174  bitmap_clear_all(map);
175  bitmap_clear_all(map2);
176  bitmap_clear_all(map3);
177  test_bit1=get_rand_bit(bitsize);
178  test_bit2=get_rand_bit(bitsize);
179  test_bit3=get_rand_bit(bitsize);
180  bitmap_set_prefix(map, test_bit1);
181  bitmap_set_prefix(map2, test_bit2);
182  bitmap_subtract(map, map2);
183  if (test_bit2 < test_bit1)
184  {
185  bitmap_set_prefix(map3, test_bit1);
186  for (j=0; j < test_bit2; j++)
187  bitmap_clear_bit(map3, j);
188  }
189  if (!bitmap_cmp(map, map3))
190  goto error4;
191  bitmap_clear_all(map);
192  bitmap_clear_all(map2);
193  bitmap_clear_all(map3);
194  test_bit1=get_rand_bit(bitsize);
195  bitmap_set_prefix(map, test_bit1);
196  bitmap_invert(map);
197  bitmap_set_all(map3);
198  for (j=0; j < test_bit1; j++)
199  bitmap_clear_bit(map3, j);
200  if (!bitmap_cmp(map, map3))
201  goto error5;
202  bitmap_clear_all(map);
203  bitmap_clear_all(map3);
204  }
205  return false;
206 error1:
207  ADD_FAILURE() << "intersect error size1=" << test_bit1
208  << ",size2=" << test_bit2;
209  return true;
210 error2:
211  ADD_FAILURE() << "union error size1=" << test_bit1
212  << ",size2=" << test_bit2;
213  return true;
214 error3:
215  ADD_FAILURE() << "xor error size1=" << test_bit1
216  << ",size2=" << test_bit2;
217  return true;
218 error4:
219  ADD_FAILURE() << "subtract error size1=" << test_bit1
220  << ",size2=" << test_bit2;
221  return true;
222 error5:
223  ADD_FAILURE() << "invert error size=" << test_bit1;
224  return true;
225 }
226 
227 bool test_count_bits_set(MY_BITMAP *map, uint bitsize)
228 {
229  uint i, bit_count=0, test_bit;
230  uint no_loops= bitsize > 128 ? 128 : bitsize;
231  for (i=0; i < no_loops; i++)
232  {
233  test_bit=get_rand_bit(bitsize);
234  if (!bitmap_is_set(map, test_bit))
235  {
236  bitmap_set_bit(map, test_bit);
237  bit_count++;
238  }
239  }
240  if (bit_count==0 && bitsize > 0)
241  goto error1;
242  if (bitmap_bits_set(map) != bit_count)
243  goto error2;
244  return false;
245 error1:
246  ADD_FAILURE() << "No bits set";
247  return true;
248 error2:
249  ADD_FAILURE() << "Wrong count of bits set";
250  return true;
251 }
252 
253 bool test_get_first_bit(MY_BITMAP *map, uint bitsize)
254 {
255  uint i, test_bit= 0;
256  uint no_loops= bitsize > 128 ? 128 : bitsize;
257 
258  bitmap_set_all(map);
259  for (i=0; i < bitsize; i++)
260  bitmap_clear_bit(map, i);
261  if (bitmap_get_first_set(map) != MY_BIT_NONE)
262  goto error1;
263  bitmap_clear_all(map);
264  for (i=0; i < bitsize; i++)
265  bitmap_set_bit(map, i);
266  if (bitmap_get_first(map) != MY_BIT_NONE)
267  goto error2;
268  bitmap_clear_all(map);
269 
270  for (i=0; i < no_loops; i++)
271  {
272  test_bit=get_rand_bit(bitsize);
273  bitmap_set_bit(map, test_bit);
274  if (bitmap_get_first_set(map) != test_bit)
275  goto error1;
276  bitmap_set_all(map);
277  bitmap_clear_bit(map, test_bit);
278  if (bitmap_get_first(map) != test_bit)
279  goto error2;
280  bitmap_clear_all(map);
281  }
282  return false;
283 error1:
284  ADD_FAILURE() << "get_first_set error prefix_size=" << test_bit;
285  return true;
286 error2:
287  ADD_FAILURE() << "get_first error prefix_size=" << test_bit;
288  return true;
289 }
290 
291 bool test_set_next_bit(MY_BITMAP *map, uint bitsize)
292 {
293  uint i, j, test_bit;
294  uint no_loops= bitsize > 128 ? 128 : bitsize;
295  for (i=0; i < no_loops; i++)
296  {
297  test_bit=get_rand_bit(bitsize);
298  for (j=0; j < test_bit; j++)
299  bitmap_set_next(map);
300  if (!bitmap_is_prefix(map, test_bit))
301  goto error1;
302  bitmap_clear_all(map);
303  }
304  return false;
305 error1:
306  ADD_FAILURE() << "set_next error prefix_size=" << test_bit;
307  return true;
308 }
309 
310 bool test_get_next_bit(MY_BITMAP *map, uint bitsize)
311 {
312  uint i, bit_count=0, test_bit, next_count=0;
313  uint no_loops= bitsize > 128 ? 128 : bitsize;
314  for (i=0; i < no_loops; i++)
315  {
316  test_bit=get_rand_bit(bitsize);
317  if (!bitmap_is_set(map, test_bit))
318  {
319  bitmap_set_bit(map, test_bit);
320  bit_count++;
321  }
322  }
323  if (bit_count==0 && bitsize > 0)
324  goto error1;
325  if (bitmap_bits_set(map) != bit_count)
326  goto error2;
327 
328  for (test_bit= bitmap_get_first_set(map);
329  test_bit != MY_BIT_NONE;
330  test_bit= bitmap_get_next_set(map, test_bit))
331  {
332  if (test_bit >= bitsize)
333  goto error3;
334  if (!bitmap_is_set(map, test_bit))
335  goto error4;
336  next_count++;
337  }
338  if (next_count != bit_count)
339  goto error5;
340  return false;
341 error1:
342  ADD_FAILURE() << "No bits set";
343  return true;
344 error2:
345  ADD_FAILURE() << "Wrong count of bits set";
346  return true;
347 error3:
348  ADD_FAILURE() << "get_next_set out of range";
349  return true;
350 error4:
351  ADD_FAILURE() << "get_next_set bit not set";
352  return true;
353 error5:
354  ADD_FAILURE() << "Wrong count get_next_set";
355  return true;
356 }
357 
358 bool test_prefix(MY_BITMAP *map, uint bitsize)
359 {
360  uint i, j, test_bit;
361  uint no_loops= bitsize > 128 ? 128 : bitsize;
362  for (i=0; i < no_loops; i++)
363  {
364  test_bit=get_rand_bit(bitsize);
365  bitmap_set_prefix(map, test_bit);
366  if (!bitmap_is_prefix(map, test_bit))
367  goto error1;
368  bitmap_clear_all(map);
369  for (j=0; j < test_bit; j++)
370  bitmap_set_bit(map, j);
371  if (!bitmap_is_prefix(map, test_bit))
372  goto error2;
373  bitmap_set_all(map);
374  for (j=bitsize - 1; ~(j-test_bit); j--)
375  bitmap_clear_bit(map, j);
376  if (!bitmap_is_prefix(map, test_bit))
377  goto error3;
378  bitmap_clear_all(map);
379  }
380  for (i=0; i < bitsize; i++)
381  {
382  if (bitmap_is_prefix(map, i + 1))
383  goto error4;
384  bitmap_set_bit(map, i);
385  if (!bitmap_is_prefix(map, i + 1))
386  goto error5;
387  test_bit=get_rand_bit(bitsize);
388  bitmap_set_bit(map, test_bit);
389  if (test_bit <= i && !bitmap_is_prefix(map, i + 1))
390  goto error5;
391  else if (test_bit > i)
392  {
393  if (bitmap_is_prefix(map, i + 1))
394  goto error4;
395  bitmap_clear_bit(map, test_bit);
396  }
397  }
398  return false;
399 error1:
400  ADD_FAILURE() << "prefix1 error prefix_size=" << test_bit;
401  return true;
402 error2:
403  ADD_FAILURE() << "prefix2 error prefix_size=" << test_bit;
404  return true;
405 error3:
406  ADD_FAILURE() << "prefix3 error prefix_size=" << test_bit;
407  return true;
408 error4:
409  ADD_FAILURE() << "prefix4 error i=" << i;
410  return true;
411 error5:
412  ADD_FAILURE() << "prefix5 error i=" << i;
413  return true;
414 }
415 
416 bool test_compare(MY_BITMAP *map, uint bitsize)
417 {
418  MY_BITMAP map2;
419  my_bitmap_map map2buf[MAX_TESTED_BITMAP_SIZE];
420  uint i, test_bit;
421  uint no_loops= bitsize > 128 ? 128 : bitsize;
422  bitmap_init(&map2, map2buf, bitsize, false);
423 
424  /* Test all 4 possible combinations of set/unset bits. */
425  for (i=0; i < no_loops; i++)
426  {
427  test_bit=get_rand_bit(bitsize);
428  bitmap_clear_bit(map, test_bit);
429  bitmap_clear_bit(&map2, test_bit);
430  if (!bitmap_is_subset(map, &map2))
431  goto error_is_subset;
432  bitmap_set_bit(map, test_bit);
433  if (bitmap_is_subset(map, &map2))
434  goto error_is_subset;
435  bitmap_set_bit(&map2, test_bit);
436  if (!bitmap_is_subset(map, &map2))
437  goto error_is_subset;
438  bitmap_clear_bit(map, test_bit);
439  if (!bitmap_is_subset(map, &map2))
440  goto error_is_subset;
441  /* Note that test_bit is not cleared i map2. */
442  }
443  bitmap_clear_all(map);
444  bitmap_clear_all(&map2);
445  /* Test all 4 possible combinations of set/unset bits. */
446  for (i=0; i < no_loops; i++)
447  {
448  test_bit=get_rand_bit(bitsize);
449  if (bitmap_is_overlapping(map, &map2))
450  goto error_is_overlapping;
451  bitmap_set_bit(map, test_bit);
452  if (bitmap_is_overlapping(map, &map2))
453  goto error_is_overlapping;
454  bitmap_set_bit(&map2, test_bit);
455  if (!bitmap_is_overlapping(map, &map2))
456  goto error_is_overlapping;
457  bitmap_clear_bit(map, test_bit);
458  if (bitmap_is_overlapping(map, &map2))
459  goto error_is_overlapping;
460  bitmap_clear_bit(&map2, test_bit);
461  /* Note that test_bit is not cleared i map2. */
462  }
463  return false;
464 error_is_subset:
465  ADD_FAILURE() << "is_subset error";
466  return true;
467 error_is_overlapping:
468  ADD_FAILURE() << "is_overlapping error";
469  return true;
470 }
471 
472 bool test_intersect(MY_BITMAP *map, uint bitsize)
473 {
474  uint bitsize2 = 1 + get_rand_bit(MAX_TESTED_BITMAP_SIZE - 1);
475  MY_BITMAP map2;
476  my_bitmap_map *map2buf= new my_bitmap_map[bitsize2];
477  uint i, test_bit1, test_bit2, test_bit3;
478  bitmap_init(&map2, map2buf, bitsize2, false);
479 
480  test_bit1= get_rand_bit(bitsize);
481  test_bit2= get_rand_bit(bitsize);
482  bitmap_set_bit(map, test_bit1);
483  bitmap_set_bit(map, test_bit2);
484  test_bit3= get_rand_bit(bitsize2);
485  bitmap_set_bit(&map2, test_bit3);
486  if (test_bit2 < bitsize2)
487  bitmap_set_bit(&map2, test_bit2);
488 
489  bitmap_intersect(map, &map2);
490  if (test_bit2 < bitsize2)
491  {
492  if (!bitmap_is_set(map, test_bit2))
493  goto error;
494  bitmap_clear_bit(map, test_bit2);
495  }
496  if (test_bit1 == test_bit3)
497  {
498  if (!bitmap_is_set(map, test_bit1))
499  goto error;
500  bitmap_clear_bit(map, test_bit1);
501  }
502  if (!bitmap_is_clear_all(map))
503  goto error;
504 
505  bitmap_set_all(map);
506  bitmap_set_all(&map2);
507  for (i=0; i < bitsize2; i++)
508  bitmap_clear_bit(&map2, i);
509  bitmap_intersect(map, &map2);
510  if (!bitmap_is_clear_all(map))
511  goto error;
512  delete[] map2buf;
513  return false;
514 error:
515  ADD_FAILURE() << "intersect error bit1=" << test_bit1
516  << ",bit2=" << test_bit2 << ",bit3=" << test_bit3;
517  return true;
518 }
519 
520 #if defined(GTEST_HAS_PARAM_TEST)
521 
522 class BitMapTest : public ::testing::TestWithParam<uint>
523 {
524 protected:
525  virtual void SetUp()
526  {
527  bitsize= GetParam();
528  ASSERT_FALSE(bitmap_init(&map, buf, bitsize, false));
529  bitmap_clear_all(&map);
530  }
531 
532  MY_BITMAP map;
533  my_bitmap_map buf[MAX_TESTED_BITMAP_SIZE];
534  uint bitsize;
535 };
536 
537 const uint test_values[]=
538 {
539  1, 2, 3, 4, 5, 6, 7, 8, 9, 10,
540  11, 12, 13, 14, 15, 16, 17, 18, 19, 20,
541  21, 22, 23, 24, 25, 26, 27, 28, 29, 30,
542  31, 32, 33, 34, 35, 36, 37, 38, 39, 40,
543  2*32U - 1, 2*32U, 2*32U + 1,
544  3*32U - 1, 3*32U, 3*32U + 1,
545  4*32U - 1, 4*32U, 4*32U + 1,
546  MAX_TESTED_BITMAP_SIZE
547 };
548 
549 INSTANTIATE_TEST_CASE_P(Foo, BitMapTest,
550  ::testing::ValuesIn(test_values));
551 
552 TEST_P(BitMapTest, TestSetGetClearBit)
553 {
554  EXPECT_FALSE(test_set_get_clear_bit(&map, bitsize)) << "bitsize=" << bitsize;
555 }
556 
557 TEST_P(BitMapTest, TestFlipBit)
558 {
559  EXPECT_FALSE(test_flip_bit(&map, bitsize)) << "bitsize=" << bitsize;
560 }
561 
562 TEST_P(BitMapTest, TestGetAllBits)
563 {
564  EXPECT_FALSE(test_get_all_bits(&map, bitsize)) << "bitsize=" << bitsize;
565 }
566 
567 TEST_P(BitMapTest, TestCompareOperators)
568 {
569  EXPECT_FALSE(test_compare_operators(&map, bitsize)) << "bitsize=" << bitsize;
570 }
571 
572 TEST_P(BitMapTest, TestCountBitsSet)
573 {
574  EXPECT_FALSE(test_count_bits_set(&map, bitsize)) << "bitsize=" << bitsize;
575 }
576 
577 TEST_P(BitMapTest, TestGetFirstBit)
578 {
579  EXPECT_FALSE(test_get_first_bit(&map, bitsize)) << "bitsize=" << bitsize;
580 }
581 
582 TEST_P(BitMapTest, TestSetNextBit)
583 {
584  EXPECT_FALSE(test_set_next_bit(&map, bitsize)) << "bitsize=" << bitsize;
585 }
586 
587 TEST_P(BitMapTest, TestGetNextBit)
588 {
589  EXPECT_FALSE(test_get_next_bit(&map, bitsize)) << "bitsize=" << bitsize;
590 }
591 
592 TEST_P(BitMapTest, TestPrefix)
593 {
594  EXPECT_FALSE(test_prefix(&map, bitsize)) << "bitsize=" << bitsize;
595 }
596 
597 TEST_P(BitMapTest, TestCompare)
598 {
599  EXPECT_FALSE(test_compare(&map, bitsize)) << "bitsize=" << bitsize;
600 }
601 
602 TEST_P(BitMapTest, TestIntersect)
603 {
604  EXPECT_FALSE(test_intersect(&map, bitsize)) << "bitsize=" << bitsize;
605 }
606 
607 #endif
608 
609 }