← Back to branch summary

~drizzle-trunk/drizzle/development

« back to all changes in this revision

Viewing changes to mysys/my_bitmap.c

  • Committer: Brian Aker
  • Date: 2008-11-04 15:39:09 UTC
  • mfrom: (575.1.2 devel)
  • Revision ID: brian@tangent.org-20081104153909-c72hn65udxs1ccal
Merge of Monty's work

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 uchar arrays as large bitmaps.
 
17
  Handling of unsigned char arrays as large bitmaps.
18
18
 
19
19
  API limitations (or, rather asserted safety assumptions,
20
20
  to encourage correct programming)
96
96
}
97
97
 
98
98
 
99
 
bool bitmap_init(MY_BITMAP *map, my_bitmap_map *buf, uint n_bits,
 
99
bool bitmap_init(MY_BITMAP *map, my_bitmap_map *buf, uint32_t n_bits,
100
100
                    bool thread_safe __attribute__((unused)))
101
101
{
102
102
  if (!buf)
103
103
  {
104
 
    uint size_in_bytes= bitmap_buffer_size(n_bits);
105
 
    uint extra= 0;
 
104
    uint32_t size_in_bytes= bitmap_buffer_size(n_bits);
 
105
    uint32_t extra= 0;
106
106
    if (thread_safe)
107
107
    {
108
108
      size_in_bytes= ALIGN_SIZE(size_in_bytes);
136
136
  {
137
137
    if (map->mutex)
138
138
      pthread_mutex_destroy(map->mutex);
139
 
    my_free((char*) map->bitmap, MYF(0));
 
139
    free((char*) map->bitmap);
140
140
    map->bitmap=0;
141
141
  }
142
142
  return;
156
156
    !=0  bit was set
157
157
*/
158
158
 
159
 
bool bitmap_fast_test_and_set(MY_BITMAP *map, uint bitmap_bit)
 
159
bool bitmap_fast_test_and_set(MY_BITMAP *map, uint32_t bitmap_bit)
160
160
{
161
 
  uchar *value= ((uchar*) map->bitmap) + (bitmap_bit / 8);
162
 
  uchar bit= 1 << ((bitmap_bit) & 7);
163
 
  uchar res= (*value) & bit;
 
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;
164
164
  *value|= bit;
165
165
  return res;
166
166
}
179
179
    !=0  bit was set
180
180
*/
181
181
 
182
 
bool bitmap_test_and_set(MY_BITMAP *map, uint bitmap_bit)
 
182
bool bitmap_test_and_set(MY_BITMAP *map, uint32_t bitmap_bit)
183
183
{
184
184
  bool res;
185
185
  assert(map->bitmap && bitmap_bit < map->n_bits);
202
202
    !=0  bit was set
203
203
*/
204
204
 
205
 
bool bitmap_fast_test_and_clear(MY_BITMAP *map, uint bitmap_bit)
 
205
bool bitmap_fast_test_and_clear(MY_BITMAP *map, uint32_t bitmap_bit)
206
206
{
207
 
  uchar *byte= (uchar*) map->bitmap + (bitmap_bit / 8);
208
 
  uchar bit= 1 << ((bitmap_bit) & 7);
209
 
  uchar res= (*byte) & bit;
 
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;
210
210
  *byte&= ~bit;
211
211
  return res;
212
212
}
213
213
 
214
214
 
215
 
bool bitmap_test_and_clear(MY_BITMAP *map, uint bitmap_bit)
 
215
bool bitmap_test_and_clear(MY_BITMAP *map, uint32_t bitmap_bit)
216
216
{
217
217
  bool res;
218
218
  assert(map->bitmap && bitmap_bit < map->n_bits);
223
223
}
224
224
 
225
225
 
226
 
uint bitmap_set_next(MY_BITMAP *map)
 
226
uint32_t bitmap_set_next(MY_BITMAP *map)
227
227
{
228
 
  uint bit_found;
 
228
  uint32_t bit_found;
229
229
  assert(map->bitmap);
230
230
  if ((bit_found= bitmap_get_first(map)) != MY_BIT_NONE)
231
231
    bitmap_set_bit(map, bit_found);
233
233
}
234
234
 
235
235
 
236
 
void bitmap_set_prefix(MY_BITMAP *map, uint prefix_size)
 
236
void bitmap_set_prefix(MY_BITMAP *map, uint32_t prefix_size)
237
237
{
238
 
  uint prefix_bytes, prefix_bits, d;
239
 
  uchar *m= (uchar *)map->bitmap;
 
238
  uint32_t prefix_bytes, prefix_bits, d;
 
239
  unsigned char *m= (unsigned char *)map->bitmap;
240
240
 
241
241
  assert(map->bitmap &&
242
242
              (prefix_size <= map->n_bits || prefix_size == UINT32_MAX));
251
251
}
252
252
 
253
253
 
254
 
bool bitmap_is_prefix(const MY_BITMAP *map, uint prefix_size)
 
254
bool bitmap_is_prefix(const MY_BITMAP *map, uint32_t prefix_size)
255
255
{
256
 
  uint prefix_bits= prefix_size & 0x7, res;
257
 
  uchar *m= (uchar*)map->bitmap;
258
 
  uchar *end_prefix= m+prefix_size/8;
259
 
  uchar *end;
 
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
260
  assert(m && prefix_size <= map->n_bits);
261
261
  end= m+no_bytes_in_map(map);
262
262
 
347
347
void bitmap_intersect(MY_BITMAP *map, const MY_BITMAP *map2)
348
348
{
349
349
  my_bitmap_map *to= map->bitmap, *from= map2->bitmap, *end;
350
 
  uint len= no_words_in_map(map), len2 = no_words_in_map(map2);
 
350
  uint32_t len= no_words_in_map(map), len2 = no_words_in_map(map2);
351
351
 
352
352
  assert(map->bitmap && map2->bitmap);
353
353
 
354
 
  end= to+min(len,len2);
 
354
  end= to+cmin(len,len2);
355
355
  *map2->last_word_ptr&= ~map2->last_word_mask; /*Clear last bits in map2*/
356
356
  while (to < end)
357
357
    *to++ &= *from++;
385
385
    void
386
386
*/
387
387
 
388
 
void bitmap_set_above(MY_BITMAP *map, uint from_byte, uint use_bit)
 
388
void bitmap_set_above(MY_BITMAP *map, uint32_t from_byte, uint32_t use_bit)
389
389
{
390
 
  uchar use_byte= use_bit ? 0xff : 0;
391
 
  uchar *to= (uchar *)map->bitmap + from_byte;
392
 
  uchar *end= (uchar *)map->bitmap + (map->n_bits+7)/8;
 
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;
393
393
 
394
394
  while (to < end)
395
395
    *to++= use_byte;
444
444
}
445
445
 
446
446
 
447
 
uint bitmap_bits_set(const MY_BITMAP *map)
 
447
uint32_t bitmap_bits_set(const MY_BITMAP *map)
448
448
{  
449
 
  uchar *m= (uchar*)map->bitmap;
450
 
  uchar *end= m + no_bytes_in_map(map);
451
 
  uint res= 0;
 
449
  unsigned char *m= (unsigned char*)map->bitmap;
 
450
  unsigned char *end= m + no_bytes_in_map(map);
 
451
  uint32_t res= 0;
452
452
 
453
453
  assert(map->bitmap);
454
454
  *map->last_word_ptr&= ~map->last_word_mask; /*Reset last bits to zero*/
455
455
  while (m < end)
456
 
    res+= my_count_bits_ushort(*m++);
 
456
    res+= my_count_bits_uint16(*m++);
457
457
  return res;
458
458
}
459
459
 
470
470
}
471
471
 
472
472
 
473
 
uint bitmap_get_first_set(const MY_BITMAP *map)
 
473
uint32_t bitmap_get_first_set(const MY_BITMAP *map)
474
474
{
475
 
  uchar *byte_ptr;
476
 
  uint i,j,k;
 
475
  unsigned char *byte_ptr;
 
476
  uint32_t i,j,k;
477
477
  my_bitmap_map *data_ptr, *end= map->last_word_ptr;
478
478
 
479
479
  assert(map->bitmap);
484
484
  {
485
485
    if (*data_ptr)
486
486
    {
487
 
      byte_ptr= (uchar*)data_ptr;
 
487
      byte_ptr= (unsigned char*)data_ptr;
488
488
      for (j=0; ; j++, byte_ptr++)
489
489
      {
490
490
        if (*byte_ptr)
504
504
}
505
505
 
506
506
 
507
 
uint bitmap_get_first(const MY_BITMAP *map)
 
507
uint32_t bitmap_get_first(const MY_BITMAP *map)
508
508
{
509
 
  uchar *byte_ptr;
510
 
  uint i,j,k;
 
509
  unsigned char *byte_ptr;
 
510
  uint32_t i,j,k;
511
511
  my_bitmap_map *data_ptr, *end= map->last_word_ptr;
512
512
 
513
513
  assert(map->bitmap);
518
518
  {
519
519
    if (*data_ptr != 0xFFFFFFFF)
520
520
    {
521
 
      byte_ptr= (uchar*)data_ptr;
 
521
      byte_ptr= (unsigned char*)data_ptr;
522
522
      for (j=0; ; j++, byte_ptr++)
523
523
      { 
524
524
        if (*byte_ptr != 0xFF)
538
538
}
539
539
 
540
540
 
541
 
uint bitmap_lock_set_next(MY_BITMAP *map)
 
541
uint32_t bitmap_lock_set_next(MY_BITMAP *map)
542
542
{
543
 
  uint bit_found;
 
543
  uint32_t bit_found;
544
544
  bitmap_lock(map);
545
545
  bit_found= bitmap_set_next(map);
546
546
  bitmap_unlock(map);
548
548
}
549
549
 
550
550
 
551
 
void bitmap_lock_clear_bit(MY_BITMAP *map, uint bitmap_bit)
 
551
void bitmap_lock_clear_bit(MY_BITMAP *map, uint32_t bitmap_bit)
552
552
{
553
553
  bitmap_lock(map);
554
554
  assert(map->bitmap && bitmap_bit < map->n_bits);
558
558
 
559
559
 
560
560
#ifdef NOT_USED
561
 
bool bitmap_lock_is_prefix(const MY_BITMAP *map, uint prefix_size)
 
561
bool bitmap_lock_is_prefix(const MY_BITMAP *map, uint32_t prefix_size)
562
562
{
563
563
  bool res;
564
564
  bitmap_lock((MY_BITMAP *)map);
584
584
}
585
585
 
586
586
 
587
 
void bitmap_lock_set_prefix(MY_BITMAP *map, uint prefix_size)
 
587
void bitmap_lock_set_prefix(MY_BITMAP *map, uint32_t prefix_size)
588
588
{
589
589
  bitmap_lock(map);
590
590
  bitmap_set_prefix(map, prefix_size);
594
594
 
595
595
bool bitmap_lock_is_clear_all(const MY_BITMAP *map)
596
596
{
597
 
  uint res;
 
597
  uint32_t res;
598
598
  bitmap_lock((MY_BITMAP *)map);
599
599
  res= bitmap_is_clear_all(map);
600
600
  bitmap_unlock((MY_BITMAP *)map);
604
604
 
605
605
bool bitmap_lock_is_set_all(const MY_BITMAP *map)
606
606
{
607
 
  uint res;
 
607
  uint32_t res;
608
608
  bitmap_lock((MY_BITMAP *)map);
609
609
  res= bitmap_is_set_all(map);
610
610
  bitmap_unlock((MY_BITMAP *)map);
612
612
}
613
613
 
614
614
 
615
 
bool bitmap_lock_is_set(const MY_BITMAP *map, uint bitmap_bit)
 
615
bool bitmap_lock_is_set(const MY_BITMAP *map, uint32_t bitmap_bit)
616
616
{
617
617
  bool res;
618
618
  assert(map->bitmap && bitmap_bit < map->n_bits);
625
625
 
626
626
bool bitmap_lock_is_subset(const MY_BITMAP *map1, const MY_BITMAP *map2)
627
627
{
628
 
  uint res;
 
628
  uint32_t res;
629
629
  bitmap_lock((MY_BITMAP *)map1);
630
630
  bitmap_lock((MY_BITMAP *)map2);
631
631
  res= bitmap_is_subset(map1, map2);
637
637
 
638
638
bool bitmap_lock_cmp(const MY_BITMAP *map1, const MY_BITMAP *map2)
639
639
{
640
 
  uint res;
 
640
  uint32_t res;
641
641
 
642
642
  assert(map1->bitmap && map2->bitmap &&
643
643
              map1->n_bits==map2->n_bits);
687
687
  RETURN
688
688
    Number of set bits in the bitmap.
689
689
*/
690
 
uint bitmap_lock_bits_set(const MY_BITMAP *map)
 
690
uint32_t bitmap_lock_bits_set(const MY_BITMAP *map)
691
691
{
692
 
  uint res;
 
692
  uint32_t res;
693
693
  bitmap_lock((MY_BITMAP *)map);
694
694
  assert(map->bitmap);
695
695
  res= bitmap_bits_set(map);
705
705
  RETURN 
706
706
    Number of first unset bit in the bitmap or MY_BIT_NONE if all bits are set.
707
707
*/
708
 
uint bitmap_lock_get_first(const MY_BITMAP *map)
 
708
uint32_t bitmap_lock_get_first(const MY_BITMAP *map)
709
709
{
710
 
  uint res;
 
710
  uint32_t res;
711
711
  bitmap_lock((MY_BITMAP*)map);
712
712
  res= bitmap_get_first(map);
713
713
  bitmap_unlock((MY_BITMAP*)map);
715
715
}
716
716
 
717
717
 
718
 
uint bitmap_lock_get_first_set(const MY_BITMAP *map)
 
718
uint32_t bitmap_lock_get_first_set(const MY_BITMAP *map)
719
719
{
720
 
  uint res;
 
720
  uint32_t res;
721
721
  bitmap_lock((MY_BITMAP*)map);
722
722
  res= bitmap_get_first_set(map);
723
723
  bitmap_unlock((MY_BITMAP*)map);
725
725
}
726
726
 
727
727
 
728
 
void bitmap_lock_set_bit(MY_BITMAP *map, uint bitmap_bit)
 
728
void bitmap_lock_set_bit(MY_BITMAP *map, uint32_t bitmap_bit)
729
729
{
730
730
  assert(map->bitmap && bitmap_bit < map->n_bits);
731
731
  bitmap_lock(map);
734
734
}
735
735
 
736
736
 
737
 
void bitmap_lock_flip_bit(MY_BITMAP *map, uint bitmap_bit)
 
737
void bitmap_lock_flip_bit(MY_BITMAP *map, uint32_t bitmap_bit)
738
738
{
739
739
  assert(map->bitmap && bitmap_bit < map->n_bits);
740
740
  bitmap_lock(map);
744
744
#endif
745
745
#ifdef MAIN
746
746
 
747
 
uint get_rand_bit(uint bitsize)
 
747
uint32_t get_rand_bit(uint32_t bitsize)
748
748
{
749
749
  return (rand() % bitsize);
750
750
}
751
751
 
752
 
bool test_set_get_clear_bit(MY_BITMAP *map, uint bitsize)
 
752
bool test_set_get_clear_bit(MY_BITMAP *map, uint32_t bitsize)
753
753
{
754
 
  uint i, test_bit;
755
 
  uint no_loops= bitsize > 128 ? 128 : bitsize;
 
754
  uint32_t i, test_bit;
 
755
  uint32_t no_loops= bitsize > 128 ? 128 : bitsize;
756
756
  for (i=0; i < no_loops; i++)
757
757
  {
758
758
    test_bit= get_rand_bit(bitsize);
772
772
  return true;
773
773
}
774
774
 
775
 
bool test_flip_bit(MY_BITMAP *map, uint bitsize)
 
775
bool test_flip_bit(MY_BITMAP *map, uint32_t bitsize)
776
776
{
777
 
  uint i, test_bit;
778
 
  uint no_loops= bitsize > 128 ? 128 : bitsize;
 
777
  uint32_t i, test_bit;
 
778
  uint32_t no_loops= bitsize > 128 ? 128 : bitsize;
779
779
  for (i=0; i < no_loops; i++)
780
780
  {
781
781
    test_bit= get_rand_bit(bitsize);
796
796
}
797
797
 
798
798
bool test_operators(MY_BITMAP *map __attribute__((unused)),
799
 
                    uint bitsize __attribute__((unused)))
 
799
                    uint32_t bitsize __attribute__((unused)))
800
800
{
801
801
  return false;
802
802
}
803
803
 
804
 
bool test_get_all_bits(MY_BITMAP *map, uint bitsize)
 
804
bool test_get_all_bits(MY_BITMAP *map, uint32_t bitsize)
805
805
{
806
 
  uint i;
 
806
  uint32_t i;
807
807
  bitmap_set_all(map);
808
808
  if (!bitmap_is_set_all(map))
809
809
    goto error1;
843
843
  return true;
844
844
}
845
845
 
846
 
bool test_compare_operators(MY_BITMAP *map, uint bitsize)
 
846
bool test_compare_operators(MY_BITMAP *map, uint32_t bitsize)
847
847
{
848
 
  uint i, j, test_bit1, test_bit2, test_bit3,test_bit4;
849
 
  uint no_loops= bitsize > 128 ? 128 : bitsize;
 
848
  uint32_t i, j, test_bit1, test_bit2, test_bit3,test_bit4;
 
849
  uint32_t no_loops= bitsize > 128 ? 128 : bitsize;
850
850
  MY_BITMAP map2_obj, map3_obj;
851
851
  MY_BITMAP *map2= &map2_obj, *map3= &map3_obj;
852
852
  my_bitmap_map map2buf[1024];
949
949
  return true;
950
950
}
951
951
 
952
 
bool test_count_bits_set(MY_BITMAP *map, uint bitsize)
 
952
bool test_count_bits_set(MY_BITMAP *map, uint32_t bitsize)
953
953
{
954
 
  uint i, bit_count=0, test_bit;
955
 
  uint no_loops= bitsize > 128 ? 128 : bitsize;
 
954
  uint32_t i, bit_count=0, test_bit;
 
955
  uint32_t no_loops= bitsize > 128 ? 128 : bitsize;
956
956
  for (i=0; i < no_loops; i++)
957
957
  {
958
958
    test_bit=get_rand_bit(bitsize);
975
975
  return true;
976
976
}
977
977
 
978
 
bool test_get_first_bit(MY_BITMAP *map, uint bitsize)
 
978
bool test_get_first_bit(MY_BITMAP *map, uint32_t bitsize)
979
979
{
980
 
  uint i, test_bit;
981
 
  uint no_loops= bitsize > 128 ? 128 : bitsize;
 
980
  uint32_t i, test_bit;
 
981
  uint32_t no_loops= bitsize > 128 ? 128 : bitsize;
982
982
  for (i=0; i < no_loops; i++)
983
983
  {
984
984
    test_bit=get_rand_bit(bitsize);
1000
1000
  return true;
1001
1001
}
1002
1002
 
1003
 
bool test_get_next_bit(MY_BITMAP *map, uint bitsize)
 
1003
bool test_get_next_bit(MY_BITMAP *map, uint32_t bitsize)
1004
1004
{
1005
 
  uint i, j, test_bit;
1006
 
  uint no_loops= bitsize > 128 ? 128 : bitsize;
 
1005
  uint32_t i, j, test_bit;
 
1006
  uint32_t no_loops= bitsize > 128 ? 128 : bitsize;
1007
1007
  for (i=0; i < no_loops; i++)
1008
1008
  {
1009
1009
    test_bit=get_rand_bit(bitsize);
1019
1019
  return true;
1020
1020
}
1021
1021
 
1022
 
bool test_prefix(MY_BITMAP *map, uint bitsize)
 
1022
bool test_prefix(MY_BITMAP *map, uint32_t bitsize)
1023
1023
{
1024
 
  uint i, j, test_bit;
1025
 
  uint no_loops= bitsize > 128 ? 128 : bitsize;
 
1024
  uint32_t i, j, test_bit;
 
1025
  uint32_t no_loops= bitsize > 128 ? 128 : bitsize;
1026
1026
  for (i=0; i < no_loops; i++)
1027
1027
  {
1028
1028
    test_bit=get_rand_bit(bitsize);
1054
1054
}
1055
1055
 
1056
1056
 
1057
 
bool do_test(uint bitsize)
 
1057
bool do_test(uint32_t bitsize)
1058
1058
{
1059
1059
  MY_BITMAP map;
1060
1060
  my_bitmap_map buf[1024];