← Back to branch summary

~drizzle-trunk/drizzle/development

« back to all changes in this revision

Viewing changes to drizzled/sql_bitmap.cc

  • Committer: lbieber
  • Date: 2010-10-02 19:48:35 UTC
  • mfrom: (1730.6.19 drizzle-make-lcov)
  • Revision ID: lbieber@orisndriz08-20101002194835-q5zd9qc4lvx1xnfo
Merge Hartmut - clean up lex, now require flex to build, also "make lcov" improvements

Show diffs side-by-side

added added

removed removed

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