← Back to branch summary

~drizzle-trunk/drizzle/development

« back to all changes in this revision

Viewing changes to drizzled/sql_bitmap.cc

Renamed more stuff to drizzle.

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 */