← Back to branch summary

~drizzle-trunk/drizzle/development

« back to all changes in this revision

Viewing changes to mysys/my_bitmap.cc

pandora-build v0.72 - Moved remaining hard-coded tests into pandora-build
macros.
Add PANDORA_DRIZZLE_BUILD to run the extra checks that drizzle needs that 
plugins would also need to run so we can just use that macro in generated
external plugin builds.
Added support to register_plugins for external plugin building.
Renamed register_plugins.py to pandora-plugin.

Show diffs side-by-side

added added

removed removed

Lines of Context:
mysys/my_bitmap.cc
 
1
/* Copyright (C) 2000 MySQL AB
 
2
 
 
3
   This program is free software; you can redistribute it and/or modify
 
4
   it under the terms of the GNU General Public License as published by
 
5
   the Free Software Foundation; version 2 of the License.
 
6
 
 
7
   This program is distributed in the hope that it will be useful,
 
8
   but WITHOUT ANY WARRANTY; without even the implied warranty of
 
9
   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 
10
   GNU General Public License for more details.
 
11
 
 
12
   You should have received a copy of the GNU General Public License
 
13
   along with this program; if not, write to the Free Software
 
14
   Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA */
 
15
 
 
16
#include "mysys_priv.h"
 
17
#include <mysys/my_bitmap.h>
 
18
#include <mystrings/m_string.h>
 
19
#include <mysys/my_bit.h>
 
20
 
 
21
using namespace std;
 
22
 
 
23
void MyBitmap::createLastWordMask()
 
24
{
 
25
  /* Get the number of used bits (1..8) in the last byte */
 
26
  unsigned int const used= 1U + ((n_bits-1U) & 0x7U);
 
27
 
 
28
  /*
 
29
    Create a mask with the upper 'unused' bits set and the lower 'used'
 
30
    bits clear. The bits within each byte is stored in big-endian order.
 
31
   */
 
32
  unsigned char const mask= static_cast<unsigned char const>((~((1 << used) - 1)) & 255); 
 
33
 
 
34
  /*
 
35
    The first bytes are to be set to zero since they represent real  bits
 
36
    in the bitvector. The last bytes are set to 0xFF since they  represent
 
37
    bytes not used by the bitvector. Finally the last byte contains  bits
 
38
    as set by the mask above.
 
39
  */
 
40
  unsigned char *ptr= (unsigned char*)&last_word_mask;
 
41
 
 
42
  last_word_ptr= bitmap + numOfWordsInMap()-1;
 
43
  switch (numOfBytesInMap() & 3) 
 
44
  {
 
45
  case 1:
 
46
    last_word_mask= UINT32_MAX;
 
47
    ptr[0]= mask;
 
48
    return;
 
49
  case 2:
 
50
    last_word_mask= UINT32_MAX;
 
51
    ptr[0]= 0;
 
52
    ptr[1]= mask;
 
53
    return;
 
54
  case 3:
 
55
    last_word_mask= 0;
 
56
    ptr[2]= mask;
 
57
    ptr[3]= 0xFFU;
 
58
    return;
 
59
  case 0:
 
60
    last_word_mask= 0U;
 
61
    ptr[3]= mask;
 
62
    return;
 
63
  }
 
64
}
 
65
 
 
66
 
 
67
bool MyBitmap::init(my_bitmap_map *buf, uint32_t num_bits)
 
68
{
 
69
  if (! buf)
 
70
  {
 
71
    uint32_t size_in_bytes= bitmap_buffer_size(num_bits);
 
72
    if (! (buf= new(std::nothrow) my_bitmap_map[size_in_bytes]()))
 
73
    {
 
74
      return true;
 
75
    }
 
76
  }
 
77
 
 
78
  bitmap= buf;
 
79
  n_bits= num_bits;
 
80
  createLastWordMask();
 
81
  clearAll();
 
82
 
 
83
  return false;
 
84
}
 
85
 
 
86
 
 
87
bool MyBitmap::testAndSet(const uint32_t bitPos)
 
88
{
 
89
  unsigned char *value= ((unsigned char*) bitmap) + (bitPos / 8);
 
90
  unsigned char bit= static_cast<unsigned char>(1 << ((bitPos) & 7));
 
91
  unsigned char res= static_cast<unsigned char>((*value) & bit);
 
92
  *value= static_cast<unsigned char>(*value | bit);
 
93
  return res;
 
94
}
 
95
 
 
96
 
 
97
 
 
98
bool MyBitmap::testAndClear(const uint32_t bitPos)
 
99
{
 
100
  unsigned char *byte= (unsigned char*) bitmap + (bitPos / 8);
 
101
  unsigned char bit= static_cast<unsigned char>(1 << ((bitPos) & 7));
 
102
  unsigned char res= static_cast<unsigned char>((*byte) & bit);
 
103
  *byte= static_cast<unsigned char>(*byte & ~bit);
 
104
  return res;
 
105
}
 
106
 
 
107
 
 
108
 
 
109
uint32_t MyBitmap::setNext()
 
110
{
 
111
  uint32_t bit_found;
 
112
  assert(bitmap);
 
113
  if ((bit_found= getFirst()) != MY_BIT_NONE)
 
114
  {
 
115
    setBit(bit_found);
 
116
  }
 
117
  return bit_found;
 
118
}
 
119
 
 
120
 
 
121
void MyBitmap::setPrefix(uint32_t prefix_size)
 
122
{
 
123
  uint32_t prefix_bytes, prefix_bits, d;
 
124
  unsigned char *m= (unsigned char *) bitmap;
 
125
 
 
126
  assert(bitmap &&
 
127
         (prefix_size <= n_bits || prefix_size == UINT32_MAX));
 
128
  set_if_smaller(prefix_size, n_bits);
 
129
  if ((prefix_bytes= prefix_size / 8))
 
130
  {
 
131
    memset(m, 0xff, prefix_bytes);
 
132
  }
 
133
  m+= prefix_bytes;
 
134
  if ((prefix_bits= prefix_size & 7))
 
135
  {
 
136
    *m++= static_cast<unsigned char>((1 << prefix_bits)-1);
 
137
  }
 
138
  if ((d= numOfBytesInMap() - prefix_bytes))
 
139
  {
 
140
    memset(m, 0, d);
 
141
  }
 
142
}
 
143
 
 
144
 
 
145
bool MyBitmap::isPrefix(const uint32_t prefix_size) const
 
146
{
 
147
  uint32_t prefix_bits= prefix_size & 0x7, res;
 
148
  unsigned char *m= (unsigned char*) bitmap;
 
149
  unsigned char *end_prefix= m + prefix_size/8;
 
150
  unsigned char *end;
 
151
  assert(m && prefix_size <= n_bits);
 
152
  end= m + numOfBytesInMap();
 
153
 
 
154
  while (m < end_prefix)
 
155
  {
 
156
    if (*m++ != 0xff)
 
157
    {
 
158
      return 0;
 
159
    }
 
160
  }
 
161
 
 
162
  *last_word_ptr&= ~last_word_mask; /*Clear bits*/
 
163
  res= 0;
 
164
  if (prefix_bits && *m++ != (1 << prefix_bits)-1)
 
165
  {
 
166
    goto ret;
 
167
  }
 
168
 
 
169
  while (m < end)
 
170
  {
 
171
    if (*m++ != 0)
 
172
    {
 
173
      goto ret;
 
174
    }
 
175
  }
 
176
  res= 1;
 
177
ret:
 
178
  return res;
 
179
}
 
180
 
 
181
 
 
182
bool MyBitmap::isSetAll() const
 
183
{
 
184
  my_bitmap_map *data_ptr= bitmap;
 
185
  my_bitmap_map *end= last_word_ptr;
 
186
  *last_word_ptr |= last_word_mask;
 
187
  for (; data_ptr <= end; data_ptr++)
 
188
  {
 
189
    if (*data_ptr != 0xFFFFFFFF)
 
190
    {
 
191
      return false;
 
192
    }
 
193
  }
 
194
  return true;
 
195
}
 
196
 
 
197
 
 
198
bool MyBitmap::isClearAll() const
 
199
{
 
200
  my_bitmap_map *data_ptr= bitmap;
 
201
  my_bitmap_map *end;
 
202
  if (*last_word_ptr & ~last_word_mask)
 
203
  {
 
204
    return false;
 
205
  }
 
206
  end= last_word_ptr;
 
207
  for (; data_ptr < end; data_ptr++)
 
208
  {
 
209
    if (*data_ptr)
 
210
    {
 
211
      return false;
 
212
    }
 
213
  }
 
214
  return true;
 
215
}
 
216
 
 
217
/* Return true if map1 is a subset of map2 */
 
218
 
 
219
bool bitmap_is_subset(const MyBitmap *map1, const MyBitmap *map2)
 
220
{
 
221
  my_bitmap_map *m1= map1->getBitmap(), *m2= map2->getBitmap(), *end;
 
222
 
 
223
  assert(map1->getBitmap() && map2->getBitmap() &&
 
224
         map1->numOfBitsInMap() == map2->numOfBitsInMap());
 
225
 
 
226
  end= map1->getLastWordPtr();
 
227
  map1->subtractMaskFromLastWord();
 
228
  map2->subtractMaskFromLastWord();
 
229
  while (m1 <= end)
 
230
  {
 
231
    if ((*m1++) & ~(*m2++))
 
232
    {
 
233
      return 0;
 
234
    }
 
235
  }
 
236
  return 1;
 
237
}
 
238
 
 
239
/* True if bitmaps has any common bits */
 
240
 
 
241
bool bitmap_is_overlapping(const MyBitmap *map1, const MyBitmap *map2)
 
242
{
 
243
  my_bitmap_map *m1= map1->getBitmap(), *m2= map2->getBitmap(), *end;
 
244
 
 
245
  assert(map1->getBitmap() && map2->getBitmap() &&
 
246
         map1->numOfBitsInMap() == map2->numOfBitsInMap());
 
247
 
 
248
  end= map1->getLastWordPtr();
 
249
  map1->subtractMaskFromLastWord();
 
250
  map2->subtractMaskFromLastWord();
 
251
  while (m1 <= end)
 
252
  {
 
253
    if ((*m1++) & (*m2++))
 
254
      return 1;
 
255
  }
 
256
  return 0;
 
257
}
 
258
 
 
259
 
 
260
void bitmap_intersect(MyBitmap *map, const MyBitmap *map2)
 
261
{
 
262
  my_bitmap_map *to= map->getBitmap(), *from= map2->getBitmap(), *end;
 
263
  uint32_t len= map->numOfWordsInMap(), len2 = map2->numOfWordsInMap();
 
264
 
 
265
  assert(map->getBitmap() && map2->getBitmap());
 
266
 
 
267
  end= to+min(len,len2);
 
268
  map2->subtractMaskFromLastWord(); /* Clear last bits in map2 */
 
269
  while (to < end)
 
270
  {
 
271
    *to++ &= *from++;
 
272
  }
 
273
 
 
274
  if (len2 < len)
 
275
  {
 
276
    end+=len-len2;
 
277
    while (to < end)
 
278
    {
 
279
      *to++=0;
 
280
    }
 
281
  }
 
282
}
 
283
 
 
284
 
 
285
void MyBitmap::setAbove(const uint32_t from_byte, const uint32_t use_bit)
 
286
{
 
287
  unsigned char use_byte= static_cast<unsigned char>(use_bit ? 0xff : 0);
 
288
  unsigned char *to= (unsigned char *) bitmap + from_byte;
 
289
  unsigned char *end= (unsigned char *) bitmap + (n_bits+7)/8;
 
290
 
 
291
  while (to < end)
 
292
  {
 
293
    *to++= use_byte;
 
294
  }
 
295
}
 
296
 
 
297
 
 
298
void bitmap_subtract(MyBitmap *map, const MyBitmap *map2)
 
299
{
 
300
  my_bitmap_map *to= map->getBitmap(), *from= map2->getBitmap(), *end;
 
301
  assert(map->getBitmap() && map2->getBitmap() &&
 
302
         map->numOfBitsInMap() == map2->numOfBitsInMap());
 
303
 
 
304
  end= map->getLastWordPtr();
 
305
 
 
306
  while (to <= end)
 
307
  {
 
308
    *to++ &= ~(*from++);
 
309
  }
 
310
}
 
311
 
 
312
 
 
313
void bitmap_union(MyBitmap *map, const MyBitmap *map2)
 
314
{
 
315
  my_bitmap_map *to= map->getBitmap(), *from= map2->getBitmap(), *end;
 
316
 
 
317
  assert(map->getBitmap() && map2->getBitmap() &&
 
318
         map->numOfBitsInMap() == map2->numOfBitsInMap());
 
319
  end= map->getLastWordPtr();
 
320
 
 
321
  while (to <= end)
 
322
  {
 
323
    *to++ |= *from++;
 
324
  }
 
325
}
 
326
 
 
327
 
 
328
void bitmap_xor(MyBitmap *map, const MyBitmap *map2)
 
329
{
 
330
  my_bitmap_map *to= map->getBitmap();
 
331
  my_bitmap_map *from= map2->getBitmap();
 
332
  my_bitmap_map *end= map->getLastWordPtr();
 
333
  assert(map->getBitmap() && map2->getBitmap() &&
 
334
         map->numOfBitsInMap() == map2->numOfBitsInMap());
 
335
  while (to <= end)
 
336
  {
 
337
    *to++ ^= *from++;
 
338
  }
 
339
}
 
340
 
 
341
 
 
342
void bitmap_invert(MyBitmap *map)
 
343
{
 
344
  my_bitmap_map *to= map->getBitmap(), *end;
 
345
 
 
346
  assert(map->getBitmap());
 
347
  end= map->getLastWordPtr();
 
348
 
 
349
  while (to <= end)
 
350
  {
 
351
    *to++ ^= 0xFFFFFFFF;
 
352
  }
 
353
}
 
354
 
 
355
 
 
356
uint32_t MyBitmap::getBitsSet()
 
357
{
 
358
  unsigned char *m= (unsigned char*) bitmap;
 
359
  unsigned char *end= m + numOfBytesInMap();
 
360
  uint32_t res= 0;
 
361
 
 
362
  assert(bitmap);
 
363
  *last_word_ptr&= ~last_word_mask; /*Reset last bits to zero*/
 
364
  while (m < end)
 
365
  {
 
366
    res+= my_count_bits_uint16(*m++);
 
367
  }
 
368
  return res;
 
369
}
 
370
 
 
371
MyBitmap::MyBitmap(const MyBitmap& rhs)
 
372
{
 
373
  my_bitmap_map *to= this->bitmap, *from= rhs.bitmap, *end;
 
374
 
 
375
  if (this->bitmap && rhs.bitmap &&
 
376
      this->n_bits == rhs.n_bits)
 
377
  {
 
378
    end= this->last_word_ptr;
 
379
    while (to <= end)
 
380
    {
 
381
      *to++ = *from++;
 
382
    }
 
383
  }
 
384
  else
 
385
  {
 
386
    this->n_bits= rhs.n_bits;
 
387
    this->bitmap= rhs.bitmap;
 
388
  }
 
389
}
 
390
 
 
391
MyBitmap& MyBitmap::operator=(const MyBitmap& rhs)
 
392
{
 
393
  if (this == &rhs)
 
394
    return *this;
 
395
 
 
396
  my_bitmap_map *to= this->bitmap, *from= rhs.bitmap, *end;
 
397
 
 
398
  if (this->bitmap && rhs.bitmap &&
 
399
      this->n_bits == rhs.n_bits)
 
400
  {
 
401
    end= this->last_word_ptr;
 
402
    while (to <= end)
 
403
    {
 
404
      *to++ = *from++;
 
405
    }
 
406
  }
 
407
  else
 
408
  {
 
409
    this->n_bits= rhs.n_bits;
 
410
    this->bitmap= rhs.bitmap;
 
411
  }
 
412
 
 
413
  return *this;
 
414
}
 
415
 
 
416
uint32_t MyBitmap::getFirstSet()
 
417
{
 
418
  unsigned char *byte_ptr;
 
419
  uint32_t i,j,k;
 
420
  my_bitmap_map *data_ptr, *end= last_word_ptr;
 
421
 
 
422
  assert(bitmap);
 
423
  data_ptr= bitmap;
 
424
  *last_word_ptr &= ~last_word_mask;
 
425
 
 
426
  for (i=0; data_ptr <= end; data_ptr++, i++)
 
427
  {
 
428
    if (*data_ptr)
 
429
    {
 
430
      byte_ptr= (unsigned char*)data_ptr;
 
431
      for (j=0; ; j++, byte_ptr++)
 
432
      {
 
433
        if (*byte_ptr)
 
434
        {
 
435
          for (k=0; ; k++)
 
436
          {
 
437
            if (*byte_ptr & (1 << k))
 
438
              return (i*32) + (j*8) + k;
 
439
          }
 
440
        }
 
441
      }
 
442
    }
 
443
  }
 
444
  return MY_BIT_NONE;
 
445
}
 
446
 
 
447
 
 
448
uint32_t MyBitmap::getFirst()
 
449
{
 
450
  unsigned char *byte_ptr;
 
451
  uint32_t i,j,k;
 
452
  my_bitmap_map *data_ptr, *end= last_word_ptr;
 
453
 
 
454
  assert(bitmap);
 
455
  data_ptr= bitmap;
 
456
  *last_word_ptr|= last_word_mask;
 
457
 
 
458
  for (i=0; data_ptr <= end; data_ptr++, i++)
 
459
  {
 
460
    if (*data_ptr != 0xFFFFFFFF)
 
461
    {
 
462
      byte_ptr= (unsigned char*)data_ptr;
 
463
      for (j=0; ; j++, byte_ptr++)
 
464
      {
 
465
        if (*byte_ptr != 0xFF)
 
466
        {
 
467
          for (k=0; ; k++)
 
468
          {
 
469
            if (!(*byte_ptr & (1 << k)))
 
470
              return (i*32) + (j*8) + k;
 
471
          }
 
472
        }
 
473
      }
 
474
    }
 
475
  }
 
476
  return MY_BIT_NONE;
 
477
}
 
478
 
 
479
 
 
480
#ifdef MAIN
 
481
 
 
482
uint32_t get_rand_bit(uint32_t bitsize)
 
483
{
 
484
  return (rand() % bitsize);
 
485
}
 
486
 
 
487
bool test_set_get_clear_bit(MyBitmap *map, uint32_t bitsize)
 
488
{
 
489
  uint32_t i, test_bit;
 
490
  uint32_t no_loops= bitsize > 128 ? 128 : bitsize;
 
491
  for (i=0; i < no_loops; i++)
 
492
  {
 
493
    test_bit= get_rand_bit(bitsize);
 
494
    map->setBit(test_bit);
 
495
    if (! map->isBitSet(test_bit))
 
496
    {
 
497
      goto error1;
 
498
    }
 
499
    map->clearBit(test_bit);
 
500
    if (map->isBitSet(test_bit))
 
501
    {
 
502
      goto error2;
 
503
    }
 
504
  }
 
505
  return false;
 
506
error1:
 
507
  printf("Error in set bit, bit %u, bitsize = %u", test_bit, bitsize);
 
508
  return true;
 
509
error2:
 
510
  printf("Error in clear bit, bit %u, bitsize = %u", test_bit, bitsize);
 
511
  return true;
 
512
}
 
513
 
 
514
bool test_flip_bit(MyBitmap *map, uint32_t bitsize)
 
515
{
 
516
  uint32_t i, test_bit;
 
517
  uint32_t no_loops= bitsize > 128 ? 128 : bitsize;
 
518
  for (i=0; i < no_loops; i++)
 
519
  {
 
520
    test_bit= get_rand_bit(bitsize);
 
521
    map->flipBit(test_bit);
 
522
    if (!map->isBitSet(test_bit))
 
523
      goto error1;
 
524
    map->flipBit(test_bit);
 
525
    if (map->isBitSet(test_bit))
 
526
      goto error2;
 
527
  }
 
528
  return false;
 
529
error1:
 
530
  printf("Error in flip bit 1, bit %u, bitsize = %u", test_bit, bitsize);
 
531
  return true;
 
532
error2:
 
533
  printf("Error in flip bit 2, bit %u, bitsize = %u", test_bit, bitsize);
 
534
  return true;
 
535
}
 
536
 
 
537
bool test_operators(MyBitmap *, uint32_t)
 
538
{
 
539
  return false;
 
540
}
 
541
 
 
542
bool test_get_all_bits(MyBitmap *map, uint32_t bitsize)
 
543
{
 
544
  uint32_t i;
 
545
  map->setAll();
 
546
  if (!map->isSetAll())
 
547
    goto error1;
 
548
  if (!map->isPrefix(bitsize))
 
549
    goto error5;
 
550
  map->clearAll();
 
551
  if (!map->isClearAll())
 
552
    goto error2;
 
553
  if (!map->isPrefix(0))
 
554
    goto error6;
 
555
  for (i=0; i<bitsize;i++)
 
556
    map->setBit(i);
 
557
  if (!map->isSetAll())
 
558
    goto error3;
 
559
  for (i=0; i<bitsize;i++)
 
560
    map->clearBit(i);
 
561
  if (!map->isClearAll())
 
562
    goto error4;
 
563
  return false;
 
564
error1:
 
565
  printf("Error in set_all, bitsize = %u", bitsize);
 
566
  return true;
 
567
error2:
 
568
  printf("Error in clear_all, bitsize = %u", bitsize);
 
569
  return true;
 
570
error3:
 
571
  printf("Error in bitmap_is_set_all, bitsize = %u", bitsize);
 
572
  return true;
 
573
error4:
 
574
  printf("Error in bitmap_is_clear_all, bitsize = %u", bitsize);
 
575
  return true;
 
576
error5:
 
577
  printf("Error in set_all through set_prefix, bitsize = %u", bitsize);
 
578
  return true;
 
579
error6:
 
580
  printf("Error in clear_all through set_prefix, bitsize = %u", bitsize);
 
581
  return true;
 
582
}
 
583
 
 
584
bool test_compare_operators(MyBitmap *map, uint32_t bitsize)
 
585
{
 
586
  uint32_t i, j, test_bit1, test_bit2, test_bit3,test_bit4;
 
587
  uint32_t no_loops= bitsize > 128 ? 128 : bitsize;
 
588
  MyBitmap map2_obj, map3_obj;
 
589
  MyBitmap *map2= &map2_obj, *map3= &map3_obj;
 
590
  my_bitmap_map map2buf[1024];
 
591
  my_bitmap_map map3buf[1024];
 
592
  map2_obj.init(map2buf, bitsize);
 
593
  map3_obj.init(map3buf, bitsize);
 
594
  map2->clearAll();
 
595
  map3->clearAll();
 
596
  for (i=0; i < no_loops; i++)
 
597
  {
 
598
    test_bit1=get_rand_bit(bitsize);
 
599
    map->setPrefix(test_bit1);
 
600
    test_bit2=get_rand_bit(bitsize);
 
601
    map2->setPrefix(test_bit2);
 
602
    bitmap_intersect(map, map2);
 
603
    test_bit3= test_bit2 < test_bit1 ? test_bit2 : test_bit1;
 
604
    map3->setPrefix(test_bit3);
 
605
    if (!bitmap_cmp(map, map3))
 
606
      goto error1;
 
607
    map->clearAll();
 
608
    map2->clearAll();
 
609
    map3->clearAll();
 
610
    test_bit1=get_rand_bit(bitsize);
 
611
    test_bit2=get_rand_bit(bitsize);
 
612
    test_bit3=get_rand_bit(bitsize);
 
613
    map->setPrefix(test_bit1);
 
614
    map2->setPrefix(test_bit2);
 
615
    test_bit3= test_bit2 > test_bit1 ? test_bit2 : test_bit1;
 
616
    map3->setPrefix(test_bit3);
 
617
    bitmap_union(map, map2);
 
618
    if (!bitmap_cmp(map, map3))
 
619
      goto error2;
 
620
    map->clearAll();
 
621
    map2->clearAll();
 
622
    map3->clearAll();
 
623
    test_bit1=get_rand_bit(bitsize);
 
624
    test_bit2=get_rand_bit(bitsize);
 
625
    test_bit3=get_rand_bit(bitsize);
 
626
    map->setPrefix(test_bit1);
 
627
    map2->setPrefix(test_bit2);
 
628
    bitmap_xor(map, map2);
 
629
    test_bit3= test_bit2 > test_bit1 ? test_bit2 : test_bit1;
 
630
    test_bit4= test_bit2 < test_bit1 ? test_bit2 : test_bit1;
 
631
    map3->setPrefix(test_bit3);
 
632
    for (j=0; j < test_bit4; j++)
 
633
      map3->clearBit(j);
 
634
    if (!bitmap_cmp(map, map3))
 
635
      goto error3;
 
636
    map->clearAll();
 
637
    map2->clearAll();
 
638
    map3->clearAll();
 
639
    test_bit1=get_rand_bit(bitsize);
 
640
    test_bit2=get_rand_bit(bitsize);
 
641
    test_bit3=get_rand_bit(bitsize);
 
642
    map->setPrefix(test_bit1);
 
643
    map2->setPrefix(test_bit2);
 
644
    bitmap_subtract(map, map2);
 
645
    if (test_bit2 < test_bit1)
 
646
    {
 
647
      map3->setPrefix(test_bit1);
 
648
      for (j=0; j < test_bit2; j++)
 
649
        map3->clearBit(j);
 
650
    }
 
651
    if (!bitmap_cmp(map, map3))
 
652
      goto error4;
 
653
    map->clearAll();
 
654
    map2->clearAll();
 
655
    map3->clearAll();
 
656
    test_bit1=get_rand_bit(bitsize);
 
657
    map->setPrefix(test_bit1);
 
658
    bitmap_invert(map);
 
659
    map3->setAll();
 
660
    for (j=0; j < test_bit1; j++)
 
661
      map3->clearBit(j);
 
662
    if (!bitmap_cmp(map, map3))
 
663
      goto error5;
 
664
    map->clearAll();
 
665
    map3->clearAll();
 
666
  }
 
667
  return false;
 
668
error1:
 
669
  printf("intersect error  bitsize=%u,size1=%u,size2=%u", bitsize,
 
670
  test_bit1,test_bit2);
 
671
  return true;
 
672
error2:
 
673
  printf("union error  bitsize=%u,size1=%u,size2=%u", bitsize,
 
674
  test_bit1,test_bit2);
 
675
  return true;
 
676
error3:
 
677
  printf("xor error  bitsize=%u,size1=%u,size2=%u", bitsize,
 
678
  test_bit1,test_bit2);
 
679
  return true;
 
680
error4:
 
681
  printf("subtract error  bitsize=%u,size1=%u,size2=%u", bitsize,
 
682
  test_bit1,test_bit2);
 
683
  return true;
 
684
error5:
 
685
  printf("invert error  bitsize=%u,size=%u", bitsize,
 
686
  test_bit1);
 
687
  return true;
 
688
}
 
689
 
 
690
bool test_count_bits_set(MyBitmap *map, uint32_t bitsize)
 
691
{
 
692
  uint32_t i, bit_count=0, test_bit;
 
693
  uint32_t no_loops= bitsize > 128 ? 128 : bitsize;
 
694
  for (i=0; i < no_loops; i++)
 
695
  {
 
696
    test_bit=get_rand_bit(bitsize);
 
697
    if (!map->isBitSet(test_bit))
 
698
    {
 
699
      map->setBit(test_bit);
 
700
      bit_count++;
 
701
    }
 
702
  }
 
703
  if (bit_count==0 && bitsize > 0)
 
704
    goto error1;
 
705
  if (getBitsSet() != bit_count)
 
706
    goto error2;
 
707
  return false;
 
708
error1:
 
709
  printf("No bits set  bitsize = %u", bitsize);
 
710
  return true;
 
711
error2:
 
712
  printf("Wrong count of bits set, bitsize = %u", bitsize);
 
713
  return true;
 
714
}
 
715
 
 
716
bool test_get_first_bit(MyBitmap *map, uint32_t bitsize)
 
717
{
 
718
  uint32_t i, test_bit;
 
719
  uint32_t no_loops= bitsize > 128 ? 128 : bitsize;
 
720
  for (i=0; i < no_loops; i++)
 
721
  {
 
722
    test_bit=get_rand_bit(bitsize);
 
723
    map->setBit(test_bit);
 
724
    if (bitmap_get_first_set(map) != test_bit)
 
725
      goto error1;
 
726
    map->setAll();
 
727
    map->clearBit(test_bit);
 
728
    if (getFirst() != test_bit)
 
729
      goto error2;
 
730
    map->clearAll();
 
731
  }
 
732
  return false;
 
733
error1:
 
734
  printf("get_first_set error bitsize=%u,prefix_size=%u",bitsize,test_bit);
 
735
  return true;
 
736
error2:
 
737
  printf("get_first error bitsize= %u, prefix_size= %u",bitsize,test_bit);
 
738
  return true;
 
739
}
 
740
 
 
741
bool test_get_next_bit(MyBitmap *map, uint32_t bitsize)
 
742
{
 
743
  uint32_t i, j, test_bit;
 
744
  uint32_t no_loops= bitsize > 128 ? 128 : bitsize;
 
745
  for (i=0; i < no_loops; i++)
 
746
  {
 
747
    test_bit=get_rand_bit(bitsize);
 
748
    for (j=0; j < test_bit; j++)
 
749
      setNext();
 
750
    if (!map->isPrefix(test_bit))
 
751
      goto error1;
 
752
    map->clearAll();
 
753
  }
 
754
  return false;
 
755
error1:
 
756
  printf("get_next error  bitsize= %u, prefix_size= %u", bitsize,test_bit);
 
757
  return true;
 
758
}
 
759
 
 
760
bool test_prefix(MyBitmap *map, uint32_t bitsize)
 
761
{
 
762
  uint32_t i, j, test_bit;
 
763
  uint32_t no_loops= bitsize > 128 ? 128 : bitsize;
 
764
  for (i=0; i < no_loops; i++)
 
765
  {
 
766
    test_bit=get_rand_bit(bitsize);
 
767
    map->setPrefix(map, test_bit);
 
768
    if (!map->isPrefix(test_bit))
 
769
      goto error1;
 
770
    map->clearAll();
 
771
    for (j=0; j < test_bit; j++)
 
772
      map->setBit(j);
 
773
    if (!map->isPrefix(test_bit))
 
774
      goto error2;
 
775
    map->setAll();
 
776
    for (j=bitsize - 1; ~(j-test_bit); j--)
 
777
      map->clearBit(j);
 
778
    if (!map->isPrefix(test_bit))
 
779
      goto error3;
 
780
    map->clearAll();
 
781
  }
 
782
  return false;
 
783
error1:
 
784
  printf("prefix1 error  bitsize = %u, prefix_size = %u", bitsize,test_bit);
 
785
  return true;
 
786
error2:
 
787
  printf("prefix2 error  bitsize = %u, prefix_size = %u", bitsize,test_bit);
 
788
  return true;
 
789
error3:
 
790
  printf("prefix3 error  bitsize = %u, prefix_size = %u", bitsize,test_bit);
 
791
  return true;
 
792
}
 
793
 
 
794
 
 
795
bool do_test(uint32_t bitsize)
 
796
{
 
797
  MyBitmap map;
 
798
  my_bitmap_map buf[1024];
 
799
  if (map.init(buf, bitsize))
 
800
  {
 
801
    printf("init error for bitsize %d", bitsize);
 
802
    goto error;
 
803
  }
 
804
  if (test_set_get_clear_bit(&map,bitsize))
 
805
    goto error;
 
806
  map.clearAll();
 
807
  if (test_flip_bit(&map,bitsize))
 
808
    goto error;
 
809
  map.clearAll();
 
810
  if (test_operators(&map,bitsize))
 
811
    goto error;
 
812
  map.clearAll();
 
813
  if (test_get_all_bits(&map, bitsize))
 
814
    goto error;
 
815
  map.clearAll();
 
816
  if (test_compare_operators(&map,bitsize))
 
817
    goto error;
 
818
  map.clearAll();
 
819
  if (test_count_bits_set(&map,bitsize))
 
820
    goto error;
 
821
  map.clearAll();
 
822
  if (test_get_first_bit(&map,bitsize))
 
823
    goto error;
 
824
  map.clearAll();
 
825
  if (test_get_next_bit(&map,bitsize))
 
826
    goto error;
 
827
  if (test_prefix(&map,bitsize))
 
828
    goto error;
 
829
  return false;
 
830
error:
 
831
  printf("\n");
 
832
  return true;
 
833
}
 
834
 
 
835
int main()
 
836
{
 
837
  int i;
 
838
  for (i= 1; i < 4096; i++)
 
839
  {
 
840
    printf("Start test for bitsize=%u\n",i);
 
841
    if (do_test(i))
 
842
      return -1;
 
843
  }
 
844
  printf("OK\n");
 
845
  return 0;
 
846
}
 
847
 
 
848
/*
 
849
  In directory mysys:
 
850
  make test_bitmap
 
851
  will build the bitmap tests and ./test_bitmap will execute it
 
852
*/
 
853
 
 
854
#endif