← Back to branch summary

~drizzle-trunk/drizzle/development

« back to all changes in this revision

Viewing changes to mysys/my_bitmap.cc

  • Committer: Brian Aker
  • Date: 2008-08-16 15:41:14 UTC
  • mto: This revision was merged to the branch mainline in revision 346.
  • Revision ID: brian@tangent.org-20080816154114-eufmwf31p6ie1nd6
Cleaned up depend in Proto utils. Modified int to bool. Put TmpTable class
into play.

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