← Back to branch summary

~drizzle-trunk/drizzle/development

« back to all changes in this revision

Viewing changes to mysys/my_bitmap.c

Removed DBUG symbols and fixed TRUE/FALSE

Show diffs side-by-side

added added

removed removed

Lines of Context:
mysys/my_bitmap.c
14
14
   Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA */
15
15
 
16
16
/*
17
 
  Handling of unsigned char arrays as large bitmaps.
 
17
  Handling of uchar arrays as large bitmaps.
18
18
 
19
19
  API limitations (or, rather asserted safety assumptions,
20
20
  to encourage correct programming)
36
36
*/
37
37
 
38
38
#include "mysys_priv.h"
39
 
#include <mysys/my_bitmap.h>
40
 
#include <mystrings/m_string.h>
41
 
#include <mysys/my_bit.h>
 
39
#include <my_bitmap.h>
 
40
#include <m_string.h>
 
41
#include <my_bit.h>
42
42
 
43
43
void create_last_word_mask(MY_BITMAP *map)
44
44
{
62
62
  map->last_word_ptr= map->bitmap + no_words_in_map(map)-1;
63
63
  switch (no_bytes_in_map(map) & 3) {
64
64
  case 1:
65
 
    map->last_word_mask= UINT32_MAX;
 
65
    map->last_word_mask= ~0U;
66
66
    ptr[0]= mask;
67
67
    return;
68
68
  case 2:
69
 
    map->last_word_mask= UINT32_MAX;
 
69
    map->last_word_mask= ~0U;
70
70
    ptr[0]= 0;
71
71
    ptr[1]= mask;
72
72
    return;
73
73
  case 3:
74
 
    map->last_word_mask= 0;
 
74
    map->last_word_mask= 0U;
75
75
    ptr[2]= mask;
76
76
    ptr[3]= 0xFFU;
77
77
    return;
96
96
}
97
97
 
98
98
 
99
 
bool bitmap_init(MY_BITMAP *map, my_bitmap_map *buf, uint32_t n_bits,
100
 
                    bool thread_safe __attribute__((unused)))
 
99
my_bool bitmap_init(MY_BITMAP *map, my_bitmap_map *buf, uint n_bits,
 
100
                    my_bool thread_safe __attribute__((unused)))
101
101
{
 
102
  DBUG_ENTER("bitmap_init");
102
103
  if (!buf)
103
104
  {
104
 
    uint32_t size_in_bytes= bitmap_buffer_size(n_bits);
105
 
    uint32_t extra= 0;
 
105
    uint size_in_bytes= bitmap_buffer_size(n_bits);
 
106
    uint extra= 0;
106
107
    if (thread_safe)
107
108
    {
108
109
      size_in_bytes= ALIGN_SIZE(size_in_bytes);
110
111
    }
111
112
    map->mutex= 0;
112
113
    if (!(buf= (my_bitmap_map*) my_malloc(size_in_bytes+extra, MYF(MY_WME))))
113
 
      return(1);
 
114
      DBUG_RETURN(1);
114
115
    if (thread_safe)
115
116
    {
116
117
      map->mutex= (pthread_mutex_t *) ((char*) buf + size_in_bytes);
119
120
  }
120
121
  else
121
122
  {
122
 
    assert(thread_safe == 0);
 
123
    DBUG_ASSERT(thread_safe == 0);
123
124
  }
124
125
 
125
126
  map->bitmap= buf;
126
127
  map->n_bits= n_bits;
127
128
  create_last_word_mask(map);
128
129
  bitmap_clear_all(map);
129
 
  return(0);
 
130
  DBUG_RETURN(0);
130
131
}
131
132
 
132
133
 
133
134
void bitmap_free(MY_BITMAP *map)
134
135
{
 
136
  DBUG_ENTER("bitmap_free");
135
137
  if (map->bitmap)
136
138
  {
137
139
    if (map->mutex)
138
140
      pthread_mutex_destroy(map->mutex);
139
 
    free((char*) map->bitmap);
 
141
    my_free((char*) map->bitmap, MYF(0));
140
142
    map->bitmap=0;
141
143
  }
142
 
  return;
 
144
  DBUG_VOID_RETURN;
143
145
}
144
146
 
145
147
 
156
158
    !=0  bit was set
157
159
*/
158
160
 
159
 
bool bitmap_fast_test_and_set(MY_BITMAP *map, uint32_t bitmap_bit)
 
161
my_bool bitmap_fast_test_and_set(MY_BITMAP *map, uint bitmap_bit)
160
162
{
161
 
  unsigned char *value= ((unsigned char*) map->bitmap) + (bitmap_bit / 8);
162
 
  unsigned char bit= 1 << ((bitmap_bit) & 7);
163
 
  unsigned char res= (*value) & bit;
 
163
  uchar *value= ((uchar*) map->bitmap) + (bitmap_bit / 8);
 
164
  uchar bit= 1 << ((bitmap_bit) & 7);
 
165
  uchar res= (*value) & bit;
164
166
  *value|= bit;
165
167
  return res;
166
168
}
179
181
    !=0  bit was set
180
182
*/
181
183
 
182
 
bool bitmap_test_and_set(MY_BITMAP *map, uint32_t bitmap_bit)
 
184
my_bool bitmap_test_and_set(MY_BITMAP *map, uint bitmap_bit)
183
185
{
184
 
  bool res;
185
 
  assert(map->bitmap && bitmap_bit < map->n_bits);
 
186
  my_bool res;
 
187
  DBUG_ASSERT(map->bitmap && bitmap_bit < map->n_bits);
186
188
  bitmap_lock(map);
187
189
  res= bitmap_fast_test_and_set(map, bitmap_bit);
188
190
  bitmap_unlock(map);
202
204
    !=0  bit was set
203
205
*/
204
206
 
205
 
bool bitmap_fast_test_and_clear(MY_BITMAP *map, uint32_t bitmap_bit)
 
207
my_bool bitmap_fast_test_and_clear(MY_BITMAP *map, uint bitmap_bit)
206
208
{
207
 
  unsigned char *byte= (unsigned char*) map->bitmap + (bitmap_bit / 8);
208
 
  unsigned char bit= 1 << ((bitmap_bit) & 7);
209
 
  unsigned char res= (*byte) & bit;
 
209
  uchar *byte= (uchar*) map->bitmap + (bitmap_bit / 8);
 
210
  uchar bit= 1 << ((bitmap_bit) & 7);
 
211
  uchar res= (*byte) & bit;
210
212
  *byte&= ~bit;
211
213
  return res;
212
214
}
213
215
 
214
216
 
215
 
bool bitmap_test_and_clear(MY_BITMAP *map, uint32_t bitmap_bit)
 
217
my_bool bitmap_test_and_clear(MY_BITMAP *map, uint bitmap_bit)
216
218
{
217
 
  bool res;
218
 
  assert(map->bitmap && bitmap_bit < map->n_bits);
 
219
  my_bool res;
 
220
  DBUG_ASSERT(map->bitmap && bitmap_bit < map->n_bits);
219
221
  bitmap_lock(map);
220
222
  res= bitmap_fast_test_and_clear(map, bitmap_bit);
221
223
  bitmap_unlock(map);
223
225
}
224
226
 
225
227
 
226
 
uint32_t bitmap_set_next(MY_BITMAP *map)
 
228
uint bitmap_set_next(MY_BITMAP *map)
227
229
{
228
 
  uint32_t bit_found;
229
 
  assert(map->bitmap);
 
230
  uint bit_found;
 
231
  DBUG_ASSERT(map->bitmap);
230
232
  if ((bit_found= bitmap_get_first(map)) != MY_BIT_NONE)
231
233
    bitmap_set_bit(map, bit_found);
232
234
  return bit_found;
233
235
}
234
236
 
235
237
 
236
 
void bitmap_set_prefix(MY_BITMAP *map, uint32_t prefix_size)
 
238
void bitmap_set_prefix(MY_BITMAP *map, uint prefix_size)
237
239
{
238
 
  uint32_t prefix_bytes, prefix_bits, d;
239
 
  unsigned char *m= (unsigned char *)map->bitmap;
 
240
  uint prefix_bytes, prefix_bits, d;
 
241
  uchar *m= (uchar *)map->bitmap;
240
242
 
241
 
  assert(map->bitmap &&
242
 
              (prefix_size <= map->n_bits || prefix_size == UINT32_MAX));
 
243
  DBUG_ASSERT(map->bitmap &&
 
244
              (prefix_size <= map->n_bits || prefix_size == (uint) ~0));
243
245
  set_if_smaller(prefix_size, map->n_bits);
244
246
  if ((prefix_bytes= prefix_size / 8))
245
247
    memset(m, 0xff, prefix_bytes);
247
249
  if ((prefix_bits= prefix_size & 7))
248
250
    *m++= (1 << prefix_bits)-1;
249
251
  if ((d= no_bytes_in_map(map)-prefix_bytes))
250
 
    memset(m, 0, d);
 
252
    bzero(m, d);
251
253
}
252
254
 
253
255
 
254
 
bool bitmap_is_prefix(const MY_BITMAP *map, uint32_t prefix_size)
 
256
my_bool bitmap_is_prefix(const MY_BITMAP *map, uint prefix_size)
255
257
{
256
 
  uint32_t prefix_bits= prefix_size & 0x7, res;
257
 
  unsigned char *m= (unsigned char*)map->bitmap;
258
 
  unsigned char *end_prefix= m+prefix_size/8;
259
 
  unsigned char *end;
260
 
  assert(m && prefix_size <= map->n_bits);
 
258
  uint prefix_bits= prefix_size & 0x7, res;
 
259
  uchar *m= (uchar*)map->bitmap;
 
260
  uchar *end_prefix= m+prefix_size/8;
 
261
  uchar *end;
 
262
  DBUG_ASSERT(m && prefix_size <= map->n_bits);
261
263
  end= m+no_bytes_in_map(map);
262
264
 
263
265
  while (m < end_prefix)
278
280
}
279
281
 
280
282
 
281
 
bool bitmap_is_set_all(const MY_BITMAP *map)
 
283
my_bool bitmap_is_set_all(const MY_BITMAP *map)
282
284
{
283
285
  my_bitmap_map *data_ptr= map->bitmap;
284
286
  my_bitmap_map *end= map->last_word_ptr;
285
287
  *map->last_word_ptr |= map->last_word_mask;
286
288
  for (; data_ptr <= end; data_ptr++)
287
289
    if (*data_ptr != 0xFFFFFFFF)
288
 
      return false;
289
 
  return true;
 
290
      return FALSE;
 
291
  return TRUE;
290
292
}
291
293
 
292
294
 
293
 
bool bitmap_is_clear_all(const MY_BITMAP *map)
 
295
my_bool bitmap_is_clear_all(const MY_BITMAP *map)
294
296
{
295
297
  my_bitmap_map *data_ptr= map->bitmap;
296
298
  my_bitmap_map *end;
297
299
  if (*map->last_word_ptr & ~map->last_word_mask)
298
 
    return false;
 
300
    return FALSE;
299
301
  end= map->last_word_ptr;
300
302
  for (; data_ptr < end; data_ptr++)
301
303
    if (*data_ptr)
302
 
      return false;
303
 
  return true;
 
304
      return FALSE;
 
305
  return TRUE;
304
306
}
305
307
 
306
 
/* Return true if map1 is a subset of map2 */
 
308
/* Return TRUE if map1 is a subset of map2 */
307
309
 
308
 
bool bitmap_is_subset(const MY_BITMAP *map1, const MY_BITMAP *map2)
 
310
my_bool bitmap_is_subset(const MY_BITMAP *map1, const MY_BITMAP *map2)
309
311
{
310
312
  my_bitmap_map *m1= map1->bitmap, *m2= map2->bitmap, *end;
311
313
 
312
 
  assert(map1->bitmap && map2->bitmap &&
 
314
  DBUG_ASSERT(map1->bitmap && map2->bitmap &&
313
315
              map1->n_bits==map2->n_bits);
314
316
 
315
317
  end= map1->last_word_ptr;
325
327
 
326
328
/* True if bitmaps has any common bits */
327
329
 
328
 
bool bitmap_is_overlapping(const MY_BITMAP *map1, const MY_BITMAP *map2)
 
330
my_bool bitmap_is_overlapping(const MY_BITMAP *map1, const MY_BITMAP *map2)
329
331
{
330
332
  my_bitmap_map *m1= map1->bitmap, *m2= map2->bitmap, *end;
331
333
 
332
 
  assert(map1->bitmap && map2->bitmap &&
 
334
  DBUG_ASSERT(map1->bitmap && map2->bitmap &&
333
335
              map1->n_bits==map2->n_bits);
334
336
 
335
337
  end= map1->last_word_ptr;
347
349
void bitmap_intersect(MY_BITMAP *map, const MY_BITMAP *map2)
348
350
{
349
351
  my_bitmap_map *to= map->bitmap, *from= map2->bitmap, *end;
350
 
  uint32_t len= no_words_in_map(map), len2 = no_words_in_map(map2);
351
 
 
352
 
  assert(map->bitmap && map2->bitmap);
353
 
 
354
 
  end= to+cmin(len,len2);
 
352
  uint len= no_words_in_map(map), len2 = no_words_in_map(map2);
 
353
 
 
354
  DBUG_ASSERT(map->bitmap && map2->bitmap);
 
355
 
 
356
  end= to+min(len,len2);
355
357
  *map2->last_word_ptr&= ~map2->last_word_mask; /*Clear last bits in map2*/
356
358
  while (to < end)
357
359
    *to++ &= *from++;
385
387
    void
386
388
*/
387
389
 
388
 
void bitmap_set_above(MY_BITMAP *map, uint32_t from_byte, uint32_t use_bit)
 
390
void bitmap_set_above(MY_BITMAP *map, uint from_byte, uint use_bit)
389
391
{
390
 
  unsigned char use_byte= use_bit ? 0xff : 0;
391
 
  unsigned char *to= (unsigned char *)map->bitmap + from_byte;
392
 
  unsigned char *end= (unsigned char *)map->bitmap + (map->n_bits+7)/8;
 
392
  uchar use_byte= use_bit ? 0xff : 0;
 
393
  uchar *to= (uchar *)map->bitmap + from_byte;
 
394
  uchar *end= (uchar *)map->bitmap + (map->n_bits+7)/8;
393
395
 
394
396
  while (to < end)
395
397
    *to++= use_byte;
399
401
void bitmap_subtract(MY_BITMAP *map, const MY_BITMAP *map2)
400
402
{
401
403
  my_bitmap_map *to= map->bitmap, *from= map2->bitmap, *end;
402
 
  assert(map->bitmap && map2->bitmap &&
 
404
  DBUG_ASSERT(map->bitmap && map2->bitmap &&
403
405
              map->n_bits==map2->n_bits);
404
406
 
405
407
  end= map->last_word_ptr;
413
415
{
414
416
  my_bitmap_map *to= map->bitmap, *from= map2->bitmap, *end;
415
417
 
416
 
  assert(map->bitmap && map2->bitmap &&
 
418
  DBUG_ASSERT(map->bitmap && map2->bitmap &&
417
419
              map->n_bits==map2->n_bits);
418
420
  end= map->last_word_ptr;
419
421
 
425
427
void bitmap_xor(MY_BITMAP *map, const MY_BITMAP *map2)
426
428
{
427
429
  my_bitmap_map *to= map->bitmap, *from= map2->bitmap, *end= map->last_word_ptr;
428
 
  assert(map->bitmap && map2->bitmap &&
 
430
  DBUG_ASSERT(map->bitmap && map2->bitmap &&
429
431
              map->n_bits==map2->n_bits);
430
432
  while (to <= end)
431
433
    *to++ ^= *from++;
436
438
{
437
439
  my_bitmap_map *to= map->bitmap, *end;
438
440
 
439
 
  assert(map->bitmap);
 
441
  DBUG_ASSERT(map->bitmap);
440
442
  end= map->last_word_ptr;
441
443
 
442
444
  while (to <= end)
444
446
}
445
447
 
446
448
 
447
 
uint32_t bitmap_bits_set(const MY_BITMAP *map)
 
449
uint bitmap_bits_set(const MY_BITMAP *map)
448
450
{  
449
 
  unsigned char *m= (unsigned char*)map->bitmap;
450
 
  unsigned char *end= m + no_bytes_in_map(map);
451
 
  uint32_t res= 0;
 
451
  uchar *m= (uchar*)map->bitmap;
 
452
  uchar *end= m + no_bytes_in_map(map);
 
453
  uint res= 0;
452
454
 
453
 
  assert(map->bitmap);
 
455
  DBUG_ASSERT(map->bitmap);
454
456
  *map->last_word_ptr&= ~map->last_word_mask; /*Reset last bits to zero*/
455
457
  while (m < end)
456
 
    res+= my_count_bits_uint16(*m++);
 
458
    res+= my_count_bits_ushort(*m++);
457
459
  return res;
458
460
}
459
461
 
462
464
{
463
465
  my_bitmap_map *to= map->bitmap, *from= map2->bitmap, *end;
464
466
 
465
 
  assert(map->bitmap && map2->bitmap &&
 
467
  DBUG_ASSERT(map->bitmap && map2->bitmap &&
466
468
              map->n_bits==map2->n_bits);
467
469
  end= map->last_word_ptr;
468
470
  while (to <= end)
470
472
}
471
473
 
472
474
 
473
 
uint32_t bitmap_get_first_set(const MY_BITMAP *map)
 
475
uint bitmap_get_first_set(const MY_BITMAP *map)
474
476
{
475
 
  unsigned char *byte_ptr;
476
 
  uint32_t i,j,k;
 
477
  uchar *byte_ptr;
 
478
  uint i,j,k;
477
479
  my_bitmap_map *data_ptr, *end= map->last_word_ptr;
478
480
 
479
 
  assert(map->bitmap);
 
481
  DBUG_ASSERT(map->bitmap);
480
482
  data_ptr= map->bitmap;
481
483
  *map->last_word_ptr &= ~map->last_word_mask;
482
484
 
484
486
  {
485
487
    if (*data_ptr)
486
488
    {
487
 
      byte_ptr= (unsigned char*)data_ptr;
 
489
      byte_ptr= (uchar*)data_ptr;
488
490
      for (j=0; ; j++, byte_ptr++)
489
491
      {
490
492
        if (*byte_ptr)
494
496
            if (*byte_ptr & (1 << k))
495
497
              return (i*32) + (j*8) + k;
496
498
          }
497
 
          assert(0);
 
499
          DBUG_ASSERT(0);
498
500
        }
499
501
      }
500
 
      assert(0);
 
502
      DBUG_ASSERT(0);
501
503
    }
502
504
  }
503
505
  return MY_BIT_NONE;
504
506
}
505
507
 
506
508
 
507
 
uint32_t bitmap_get_first(const MY_BITMAP *map)
 
509
uint bitmap_get_first(const MY_BITMAP *map)
508
510
{
509
 
  unsigned char *byte_ptr;
510
 
  uint32_t i,j,k;
 
511
  uchar *byte_ptr;
 
512
  uint i,j,k;
511
513
  my_bitmap_map *data_ptr, *end= map->last_word_ptr;
512
514
 
513
 
  assert(map->bitmap);
 
515
  DBUG_ASSERT(map->bitmap);
514
516
  data_ptr= map->bitmap;
515
517
  *map->last_word_ptr|= map->last_word_mask;
516
518
 
518
520
  {
519
521
    if (*data_ptr != 0xFFFFFFFF)
520
522
    {
521
 
      byte_ptr= (unsigned char*)data_ptr;
 
523
      byte_ptr= (uchar*)data_ptr;
522
524
      for (j=0; ; j++, byte_ptr++)
523
525
      { 
524
526
        if (*byte_ptr != 0xFF)
528
530
            if (!(*byte_ptr & (1 << k)))
529
531
              return (i*32) + (j*8) + k;
530
532
          }
531
 
          assert(0);
 
533
          DBUG_ASSERT(0);
532
534
        }
533
535
      }
534
 
      assert(0);
 
536
      DBUG_ASSERT(0);
535
537
    }
536
538
  }
537
539
  return MY_BIT_NONE;
538
540
}
539
541
 
540
542
 
541
 
uint32_t bitmap_lock_set_next(MY_BITMAP *map)
 
543
uint bitmap_lock_set_next(MY_BITMAP *map)
542
544
{
543
 
  uint32_t bit_found;
 
545
  uint bit_found;
544
546
  bitmap_lock(map);
545
547
  bit_found= bitmap_set_next(map);
546
548
  bitmap_unlock(map);
548
550
}
549
551
 
550
552
 
551
 
void bitmap_lock_clear_bit(MY_BITMAP *map, uint32_t bitmap_bit)
 
553
void bitmap_lock_clear_bit(MY_BITMAP *map, uint bitmap_bit)
552
554
{
553
555
  bitmap_lock(map);
554
 
  assert(map->bitmap && bitmap_bit < map->n_bits);
 
556
  DBUG_ASSERT(map->bitmap && bitmap_bit < map->n_bits);
555
557
  bitmap_clear_bit(map, bitmap_bit);
556
558
  bitmap_unlock(map);
557
559
}
558
560
 
559
561
 
560
562
#ifdef NOT_USED
561
 
bool bitmap_lock_is_prefix(const MY_BITMAP *map, uint32_t prefix_size)
 
563
my_bool bitmap_lock_is_prefix(const MY_BITMAP *map, uint prefix_size)
562
564
{
563
 
  bool res;
 
565
  my_bool res;
564
566
  bitmap_lock((MY_BITMAP *)map);
565
567
  res= bitmap_is_prefix(map, prefix_size);
566
568
  bitmap_unlock((MY_BITMAP *)map);
584
586
}
585
587
 
586
588
 
587
 
void bitmap_lock_set_prefix(MY_BITMAP *map, uint32_t prefix_size)
 
589
void bitmap_lock_set_prefix(MY_BITMAP *map, uint prefix_size)
588
590
{
589
591
  bitmap_lock(map);
590
592
  bitmap_set_prefix(map, prefix_size);
592
594
}
593
595
 
594
596
 
595
 
bool bitmap_lock_is_clear_all(const MY_BITMAP *map)
 
597
my_bool bitmap_lock_is_clear_all(const MY_BITMAP *map)
596
598
{
597
 
  uint32_t res;
 
599
  uint res;
598
600
  bitmap_lock((MY_BITMAP *)map);
599
601
  res= bitmap_is_clear_all(map);
600
602
  bitmap_unlock((MY_BITMAP *)map);
602
604
}
603
605
 
604
606
 
605
 
bool bitmap_lock_is_set_all(const MY_BITMAP *map)
 
607
my_bool bitmap_lock_is_set_all(const MY_BITMAP *map)
606
608
{
607
 
  uint32_t res;
 
609
  uint res;
608
610
  bitmap_lock((MY_BITMAP *)map);
609
611
  res= bitmap_is_set_all(map);
610
612
  bitmap_unlock((MY_BITMAP *)map);
612
614
}
613
615
 
614
616
 
615
 
bool bitmap_lock_is_set(const MY_BITMAP *map, uint32_t bitmap_bit)
 
617
my_bool bitmap_lock_is_set(const MY_BITMAP *map, uint bitmap_bit)
616
618
{
617
 
  bool res;
618
 
  assert(map->bitmap && bitmap_bit < map->n_bits);
 
619
  my_bool res;
 
620
  DBUG_ASSERT(map->bitmap && bitmap_bit < map->n_bits);
619
621
  bitmap_lock((MY_BITMAP *)map);
620
622
  res= bitmap_is_set(map, bitmap_bit);
621
623
  bitmap_unlock((MY_BITMAP *)map);
623
625
}
624
626
 
625
627
 
626
 
bool bitmap_lock_is_subset(const MY_BITMAP *map1, const MY_BITMAP *map2)
 
628
my_bool bitmap_lock_is_subset(const MY_BITMAP *map1, const MY_BITMAP *map2)
627
629
{
628
 
  uint32_t res;
 
630
  uint res;
629
631
  bitmap_lock((MY_BITMAP *)map1);
630
632
  bitmap_lock((MY_BITMAP *)map2);
631
633
  res= bitmap_is_subset(map1, map2);
635
637
}
636
638
 
637
639
 
638
 
bool bitmap_lock_cmp(const MY_BITMAP *map1, const MY_BITMAP *map2)
 
640
my_bool bitmap_lock_cmp(const MY_BITMAP *map1, const MY_BITMAP *map2)
639
641
{
640
 
  uint32_t res;
 
642
  uint res;
641
643
 
642
 
  assert(map1->bitmap && map2->bitmap &&
 
644
  DBUG_ASSERT(map1->bitmap && map2->bitmap &&
643
645
              map1->n_bits==map2->n_bits);
644
646
  bitmap_lock((MY_BITMAP *)map1);
645
647
  bitmap_lock((MY_BITMAP *)map2);
687
689
  RETURN
688
690
    Number of set bits in the bitmap.
689
691
*/
690
 
uint32_t bitmap_lock_bits_set(const MY_BITMAP *map)
 
692
uint bitmap_lock_bits_set(const MY_BITMAP *map)
691
693
{
692
 
  uint32_t res;
 
694
  uint res;
693
695
  bitmap_lock((MY_BITMAP *)map);
694
 
  assert(map->bitmap);
 
696
  DBUG_ASSERT(map->bitmap);
695
697
  res= bitmap_bits_set(map);
696
698
  bitmap_unlock((MY_BITMAP *)map);
697
699
  return res;
705
707
  RETURN 
706
708
    Number of first unset bit in the bitmap or MY_BIT_NONE if all bits are set.
707
709
*/
708
 
uint32_t bitmap_lock_get_first(const MY_BITMAP *map)
 
710
uint bitmap_lock_get_first(const MY_BITMAP *map)
709
711
{
710
 
  uint32_t res;
 
712
  uint res;
711
713
  bitmap_lock((MY_BITMAP*)map);
712
714
  res= bitmap_get_first(map);
713
715
  bitmap_unlock((MY_BITMAP*)map);
715
717
}
716
718
 
717
719
 
718
 
uint32_t bitmap_lock_get_first_set(const MY_BITMAP *map)
 
720
uint bitmap_lock_get_first_set(const MY_BITMAP *map)
719
721
{
720
 
  uint32_t res;
 
722
  uint res;
721
723
  bitmap_lock((MY_BITMAP*)map);
722
724
  res= bitmap_get_first_set(map);
723
725
  bitmap_unlock((MY_BITMAP*)map);
725
727
}
726
728
 
727
729
 
728
 
void bitmap_lock_set_bit(MY_BITMAP *map, uint32_t bitmap_bit)
 
730
void bitmap_lock_set_bit(MY_BITMAP *map, uint bitmap_bit)
729
731
{
730
 
  assert(map->bitmap && bitmap_bit < map->n_bits);
 
732
  DBUG_ASSERT(map->bitmap && bitmap_bit < map->n_bits);
731
733
  bitmap_lock(map);
732
734
  bitmap_set_bit(map, bitmap_bit);
733
735
  bitmap_unlock(map);
734
736
}
735
737
 
736
738
 
737
 
void bitmap_lock_flip_bit(MY_BITMAP *map, uint32_t bitmap_bit)
 
739
void bitmap_lock_flip_bit(MY_BITMAP *map, uint bitmap_bit)
738
740
{
739
 
  assert(map->bitmap && bitmap_bit < map->n_bits);
 
741
  DBUG_ASSERT(map->bitmap && bitmap_bit < map->n_bits);
740
742
  bitmap_lock(map);
741
743
  bitmap_flip_bit(map, bitmap_bit);
742
744
  bitmap_unlock(map);
744
746
#endif
745
747
#ifdef MAIN
746
748
 
747
 
uint32_t get_rand_bit(uint32_t bitsize)
 
749
uint get_rand_bit(uint bitsize)
748
750
{
749
751
  return (rand() % bitsize);
750
752
}
751
753
 
752
 
bool test_set_get_clear_bit(MY_BITMAP *map, uint32_t bitsize)
 
754
my_bool test_set_get_clear_bit(MY_BITMAP *map, uint bitsize)
753
755
{
754
 
  uint32_t i, test_bit;
755
 
  uint32_t no_loops= bitsize > 128 ? 128 : bitsize;
 
756
  uint i, test_bit;
 
757
  uint no_loops= bitsize > 128 ? 128 : bitsize;
756
758
  for (i=0; i < no_loops; i++)
757
759
  {
758
760
    test_bit= get_rand_bit(bitsize);
763
765
    if (bitmap_is_set(map, test_bit))
764
766
      goto error2;
765
767
  }
766
 
  return false;
 
768
  return FALSE;
767
769
error1:
768
770
  printf("Error in set bit, bit %u, bitsize = %u", test_bit, bitsize);
769
 
  return true;
 
771
  return TRUE;
770
772
error2:
771
773
  printf("Error in clear bit, bit %u, bitsize = %u", test_bit, bitsize);
772
 
  return true;
 
774
  return TRUE;
773
775
}
774
776
 
775
 
bool test_flip_bit(MY_BITMAP *map, uint32_t bitsize)
 
777
my_bool test_flip_bit(MY_BITMAP *map, uint bitsize)
776
778
{
777
 
  uint32_t i, test_bit;
778
 
  uint32_t no_loops= bitsize > 128 ? 128 : bitsize;
 
779
  uint i, test_bit;
 
780
  uint no_loops= bitsize > 128 ? 128 : bitsize;
779
781
  for (i=0; i < no_loops; i++)
780
782
  {
781
783
    test_bit= get_rand_bit(bitsize);
786
788
    if (bitmap_is_set(map, test_bit))
787
789
      goto error2;
788
790
  }
789
 
  return false;
 
791
  return FALSE;
790
792
error1:
791
793
  printf("Error in flip bit 1, bit %u, bitsize = %u", test_bit, bitsize);
792
 
  return true;
 
794
  return TRUE;
793
795
error2:
794
796
  printf("Error in flip bit 2, bit %u, bitsize = %u", test_bit, bitsize);
795
 
  return true;
796
 
}
797
 
 
798
 
bool test_operators(MY_BITMAP *map __attribute__((unused)),
799
 
                    uint32_t bitsize __attribute__((unused)))
800
 
{
801
 
  return false;
802
 
}
803
 
 
804
 
bool test_get_all_bits(MY_BITMAP *map, uint32_t bitsize)
805
 
{
806
 
  uint32_t i;
 
797
  return TRUE;
 
798
}
 
799
 
 
800
my_bool test_operators(MY_BITMAP *map __attribute__((unused)),
 
801
                    uint bitsize __attribute__((unused)))
 
802
{
 
803
  return FALSE;
 
804
}
 
805
 
 
806
my_bool test_get_all_bits(MY_BITMAP *map, uint bitsize)
 
807
{
 
808
  uint i;
807
809
  bitmap_set_all(map);
808
810
  if (!bitmap_is_set_all(map))
809
811
    goto error1;
822
824
    bitmap_clear_bit(map, i);
823
825
  if (!bitmap_is_clear_all(map))
824
826
    goto error4;
825
 
  return false;
 
827
  return FALSE;
826
828
error1:
827
829
  printf("Error in set_all, bitsize = %u", bitsize);
828
 
  return true;
 
830
  return TRUE;
829
831
error2:
830
832
  printf("Error in clear_all, bitsize = %u", bitsize);
831
 
  return true;
 
833
  return TRUE;
832
834
error3:
833
835
  printf("Error in bitmap_is_set_all, bitsize = %u", bitsize);
834
 
  return true;
 
836
  return TRUE;
835
837
error4:
836
838
  printf("Error in bitmap_is_clear_all, bitsize = %u", bitsize);
837
 
  return true;
 
839
  return TRUE;
838
840
error5:
839
841
  printf("Error in set_all through set_prefix, bitsize = %u", bitsize);
840
 
  return true;
 
842
  return TRUE;
841
843
error6:
842
844
  printf("Error in clear_all through set_prefix, bitsize = %u", bitsize);
843
 
  return true;
 
845
  return TRUE;
844
846
}
845
847
 
846
 
bool test_compare_operators(MY_BITMAP *map, uint32_t bitsize)
 
848
my_bool test_compare_operators(MY_BITMAP *map, uint bitsize)
847
849
{
848
 
  uint32_t i, j, test_bit1, test_bit2, test_bit3,test_bit4;
849
 
  uint32_t no_loops= bitsize > 128 ? 128 : bitsize;
 
850
  uint i, j, test_bit1, test_bit2, test_bit3,test_bit4;
 
851
  uint no_loops= bitsize > 128 ? 128 : bitsize;
850
852
  MY_BITMAP map2_obj, map3_obj;
851
853
  MY_BITMAP *map2= &map2_obj, *map3= &map3_obj;
852
854
  my_bitmap_map map2buf[1024];
853
855
  my_bitmap_map map3buf[1024];
854
 
  bitmap_init(&map2_obj, map2buf, bitsize, false);
855
 
  bitmap_init(&map3_obj, map3buf, bitsize, false);
 
856
  bitmap_init(&map2_obj, map2buf, bitsize, FALSE);
 
857
  bitmap_init(&map3_obj, map3buf, bitsize, FALSE);
856
858
  bitmap_clear_all(map2);
857
859
  bitmap_clear_all(map3);
858
860
  for (i=0; i < no_loops; i++)
926
928
    bitmap_clear_all(map);
927
929
    bitmap_clear_all(map3);
928
930
  }
929
 
  return false;
 
931
  return FALSE;
930
932
error1:
931
933
  printf("intersect error  bitsize=%u,size1=%u,size2=%u", bitsize,
932
934
  test_bit1,test_bit2);
933
 
  return true;
 
935
  return TRUE;
934
936
error2:
935
937
  printf("union error  bitsize=%u,size1=%u,size2=%u", bitsize,
936
938
  test_bit1,test_bit2);
937
 
  return true;
 
939
  return TRUE;
938
940
error3:
939
941
  printf("xor error  bitsize=%u,size1=%u,size2=%u", bitsize,
940
942
  test_bit1,test_bit2);
941
 
  return true;
 
943
  return TRUE;
942
944
error4:
943
945
  printf("subtract error  bitsize=%u,size1=%u,size2=%u", bitsize,
944
946
  test_bit1,test_bit2);
945
 
  return true;
 
947
  return TRUE;
946
948
error5:
947
949
  printf("invert error  bitsize=%u,size=%u", bitsize,
948
950
  test_bit1);
949
 
  return true;
 
951
  return TRUE;
950
952
}
951
953
 
952
 
bool test_count_bits_set(MY_BITMAP *map, uint32_t bitsize)
 
954
my_bool test_count_bits_set(MY_BITMAP *map, uint bitsize)
953
955
{
954
 
  uint32_t i, bit_count=0, test_bit;
955
 
  uint32_t no_loops= bitsize > 128 ? 128 : bitsize;
 
956
  uint i, bit_count=0, test_bit;
 
957
  uint no_loops= bitsize > 128 ? 128 : bitsize;
956
958
  for (i=0; i < no_loops; i++)
957
959
  {
958
960
    test_bit=get_rand_bit(bitsize);
966
968
    goto error1;
967
969
  if (bitmap_bits_set(map) != bit_count)
968
970
    goto error2;
969
 
  return false;
 
971
  return FALSE;
970
972
error1:
971
973
  printf("No bits set  bitsize = %u", bitsize);
972
 
  return true;
 
974
  return TRUE;
973
975
error2:
974
976
  printf("Wrong count of bits set, bitsize = %u", bitsize);
975
 
  return true;
 
977
  return TRUE;
976
978
}
977
979
 
978
 
bool test_get_first_bit(MY_BITMAP *map, uint32_t bitsize)
 
980
my_bool test_get_first_bit(MY_BITMAP *map, uint bitsize)
979
981
{
980
 
  uint32_t i, test_bit;
981
 
  uint32_t no_loops= bitsize > 128 ? 128 : bitsize;
 
982
  uint i, test_bit;
 
983
  uint no_loops= bitsize > 128 ? 128 : bitsize;
982
984
  for (i=0; i < no_loops; i++)
983
985
  {
984
986
    test_bit=get_rand_bit(bitsize);
991
993
      goto error2;
992
994
    bitmap_clear_all(map);
993
995
  }
994
 
  return false;
 
996
  return FALSE;
995
997
error1:
996
998
  printf("get_first_set error bitsize=%u,prefix_size=%u",bitsize,test_bit);
997
 
  return true;
 
999
  return TRUE;
998
1000
error2:
999
1001
  printf("get_first error bitsize= %u, prefix_size= %u",bitsize,test_bit);
1000
 
  return true;
 
1002
  return TRUE;
1001
1003
}
1002
1004
 
1003
 
bool test_get_next_bit(MY_BITMAP *map, uint32_t bitsize)
 
1005
my_bool test_get_next_bit(MY_BITMAP *map, uint bitsize)
1004
1006
{
1005
 
  uint32_t i, j, test_bit;
1006
 
  uint32_t no_loops= bitsize > 128 ? 128 : bitsize;
 
1007
  uint i, j, test_bit;
 
1008
  uint no_loops= bitsize > 128 ? 128 : bitsize;
1007
1009
  for (i=0; i < no_loops; i++)
1008
1010
  {
1009
1011
    test_bit=get_rand_bit(bitsize);
1013
1015
      goto error1;
1014
1016
    bitmap_clear_all(map);
1015
1017
  }
1016
 
  return false;
 
1018
  return FALSE;
1017
1019
error1:
1018
1020
  printf("get_next error  bitsize= %u, prefix_size= %u", bitsize,test_bit);
1019
 
  return true;
 
1021
  return TRUE;
1020
1022
}
1021
1023
 
1022
 
bool test_prefix(MY_BITMAP *map, uint32_t bitsize)
 
1024
my_bool test_prefix(MY_BITMAP *map, uint bitsize)
1023
1025
{
1024
 
  uint32_t i, j, test_bit;
1025
 
  uint32_t no_loops= bitsize > 128 ? 128 : bitsize;
 
1026
  uint i, j, test_bit;
 
1027
  uint no_loops= bitsize > 128 ? 128 : bitsize;
1026
1028
  for (i=0; i < no_loops; i++)
1027
1029
  {
1028
1030
    test_bit=get_rand_bit(bitsize);
1041
1043
      goto error3;
1042
1044
    bitmap_clear_all(map);
1043
1045
  }
1044
 
  return false;
 
1046
  return FALSE;
1045
1047
error1:
1046
1048
  printf("prefix1 error  bitsize = %u, prefix_size = %u", bitsize,test_bit);
1047
 
  return true;
 
1049
  return TRUE;
1048
1050
error2:
1049
1051
  printf("prefix2 error  bitsize = %u, prefix_size = %u", bitsize,test_bit);
1050
 
  return true;
 
1052
  return TRUE;
1051
1053
error3:
1052
1054
  printf("prefix3 error  bitsize = %u, prefix_size = %u", bitsize,test_bit);
1053
 
  return true;
 
1055
  return TRUE;
1054
1056
}
1055
1057
 
1056
1058
 
1057
 
bool do_test(uint32_t bitsize)
 
1059
my_bool do_test(uint bitsize)
1058
1060
{
1059
1061
  MY_BITMAP map;
1060
1062
  my_bitmap_map buf[1024];
1061
 
  if (bitmap_init(&map, buf, bitsize, false))
 
1063
  if (bitmap_init(&map, buf, bitsize, FALSE))
1062
1064
  {
1063
1065
    printf("init error for bitsize %d", bitsize);
1064
1066
    goto error;
1088
1090
    goto error;
1089
1091
  if (test_prefix(&map,bitsize))
1090
1092
    goto error;
1091
 
  return false;
 
1093
  return FALSE;
1092
1094
error:
1093
1095
  printf("\n");
1094
 
  return true;
 
1096
  return TRUE;
1095
1097
}
1096
1098
 
1097
1099
int main()