← Back to branch summary

~drizzle-trunk/drizzle/development

« back to all changes in this revision

Viewing changes to drizzled/sql_bitmap.cc

Merged in changes. 
Edited a the comment test case so deal with our version bump.

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