← Back to branch summary

~drizzle-trunk/drizzle/development

« back to all changes in this revision

Viewing changes to mysys/my_bitmap.cc

  • Committer: devananda
  • Date: 2009-07-01 17:38:47 UTC
  • mto: (1093.1.7 captain)
  • mto: This revision was merged to the branch mainline in revision 1095.
  • Revision ID: devananda.vdv@gmail.com-20090701173847-3n3mbtessg5ff35e
refactored function/benchmark into plugin/benchmark

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