← Back to branch summary

~drizzle-trunk/drizzle/development

« back to all changes in this revision

Viewing changes to mysys/my_bitmap.cc

  • Committer: Stewart Smith
  • Date: 2009-06-16 00:44:35 UTC
  • mto: (1119.2.6 merge)
  • mto: This revision was merged to the branch mainline in revision 1124.
  • Revision ID: stewart@flamingspork.com-20090616004435-t1vust6erhco7edc
make comment_index test not leave tables behind after running

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