← Back to branch summary

~drizzle-trunk/drizzle/development

« back to all changes in this revision

Viewing changes to mysys/my_bitmap.cc

  • Committer: Monty Taylor
  • Date: 2009-01-30 21:02:37 UTC
  • mto: (779.7.3 devel)
  • mto: This revision was merged to the branch mainline in revision 823.
  • Revision ID: mordred@inaugust.com-20090130210237-3n6ld8a9jc084jko
Commented out a test in subselect_sj - I think it might be a regression. Jay?

Show diffs side-by-side

added added

removed removed

Lines of Context:
mysys/my_bitmap.cc
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)
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= ~0U;
 
65
    map->last_word_mask= UINT32_MAX;
66
66
    ptr[0]= mask;
67
67
    return;
68
68
  case 2:
69
 
    map->last_word_mask= ~0U;
 
69
    map->last_word_mask= UINT32_MAX;
70
70
    ptr[0]= 0;
71
71
    ptr[1]= mask;
72
72
    return;
73
73
  case 3:
74
 
    map->last_word_mask= 0U;
 
74
    map->last_word_mask= 0;
75
75
    ptr[2]= mask;
76
76
    ptr[3]= 0xFFU;
77
77
    return;
83
83
}
84
84
 
85
85
 
86
 
static inline void bitmap_lock(MY_BITMAP *map __attribute__((unused)))
 
86
static inline void bitmap_lock(MY_BITMAP *map)
87
87
{
88
88
  if (map->mutex)
89
89
    pthread_mutex_lock(map->mutex);
90
90
}
91
91
 
92
 
static inline void bitmap_unlock(MY_BITMAP *map __attribute__((unused)))
 
92
static inline void bitmap_unlock(MY_BITMAP *map)
93
93
{
94
94
  if (map->mutex)
95
95
    pthread_mutex_unlock(map->mutex);
96
96
}
97
97
 
98
98
 
99
 
bool bitmap_init(MY_BITMAP *map, my_bitmap_map *buf, uint n_bits,
100
 
                    bool thread_safe __attribute__((unused)))
 
99
bool bitmap_init(MY_BITMAP *map, my_bitmap_map *buf, uint32_t n_bits, bool thread_safe)
101
100
{
102
101
  if (!buf)
103
102
  {
104
 
    uint size_in_bytes= bitmap_buffer_size(n_bits);
105
 
    uint extra= 0;
 
103
    uint32_t size_in_bytes= bitmap_buffer_size(n_bits);
 
104
    uint32_t extra= 0;
106
105
    if (thread_safe)
107
106
    {
108
107
      size_in_bytes= ALIGN_SIZE(size_in_bytes);
109
108
      extra= sizeof(pthread_mutex_t);
110
109
    }
111
110
    map->mutex= 0;
112
 
    if (!(buf= (my_bitmap_map*) my_malloc(size_in_bytes+extra, MYF(MY_WME))))
 
111
    if (!(buf= (my_bitmap_map*) malloc(size_in_bytes+extra)))
113
112
      return(1);
114
113
    if (thread_safe)
115
114
    {
136
135
  {
137
136
    if (map->mutex)
138
137
      pthread_mutex_destroy(map->mutex);
139
 
    my_free((char*) map->bitmap, MYF(0));
 
138
    free((char*) map->bitmap);
140
139
    map->bitmap=0;
141
140
  }
142
141
  return;
156
155
    !=0  bit was set
157
156
*/
158
157
 
159
 
bool bitmap_fast_test_and_set(MY_BITMAP *map, uint bitmap_bit)
 
158
bool bitmap_fast_test_and_set(MY_BITMAP *map, uint32_t bitmap_bit)
160
159
{
161
 
  uchar *value= ((uchar*) map->bitmap) + (bitmap_bit / 8);
162
 
  uchar bit= 1 << ((bitmap_bit) & 7);
163
 
  uchar res= (*value) & bit;
 
160
  unsigned char *value= ((unsigned char*) map->bitmap) + (bitmap_bit / 8);
 
161
  unsigned char bit= 1 << ((bitmap_bit) & 7);
 
162
  unsigned char res= (*value) & bit;
164
163
  *value|= bit;
165
164
  return res;
166
165
}
179
178
    !=0  bit was set
180
179
*/
181
180
 
182
 
bool bitmap_test_and_set(MY_BITMAP *map, uint bitmap_bit)
 
181
bool bitmap_test_and_set(MY_BITMAP *map, uint32_t bitmap_bit)
183
182
{
184
183
  bool res;
185
184
  assert(map->bitmap && bitmap_bit < map->n_bits);
202
201
    !=0  bit was set
203
202
*/
204
203
 
205
 
bool bitmap_fast_test_and_clear(MY_BITMAP *map, uint bitmap_bit)
 
204
bool bitmap_fast_test_and_clear(MY_BITMAP *map, uint32_t bitmap_bit)
206
205
{
207
 
  uchar *byte= (uchar*) map->bitmap + (bitmap_bit / 8);
208
 
  uchar bit= 1 << ((bitmap_bit) & 7);
209
 
  uchar res= (*byte) & bit;
 
206
  unsigned char *byte= (unsigned char*) map->bitmap + (bitmap_bit / 8);
 
207
  unsigned char bit= 1 << ((bitmap_bit) & 7);
 
208
  unsigned char res= (*byte) & bit;
210
209
  *byte&= ~bit;
211
210
  return res;
212
211
}
213
212
 
214
213
 
215
 
bool bitmap_test_and_clear(MY_BITMAP *map, uint bitmap_bit)
 
214
bool bitmap_test_and_clear(MY_BITMAP *map, uint32_t bitmap_bit)
216
215
{
217
216
  bool res;
218
217
  assert(map->bitmap && bitmap_bit < map->n_bits);
223
222
}
224
223
 
225
224
 
226
 
uint bitmap_set_next(MY_BITMAP *map)
 
225
uint32_t bitmap_set_next(MY_BITMAP *map)
227
226
{
228
 
  uint bit_found;
 
227
  uint32_t bit_found;
229
228
  assert(map->bitmap);
230
229
  if ((bit_found= bitmap_get_first(map)) != MY_BIT_NONE)
231
230
    bitmap_set_bit(map, bit_found);
233
232
}
234
233
 
235
234
 
236
 
void bitmap_set_prefix(MY_BITMAP *map, uint prefix_size)
 
235
void bitmap_set_prefix(MY_BITMAP *map, uint32_t prefix_size)
237
236
{
238
 
  uint prefix_bytes, prefix_bits, d;
239
 
  uchar *m= (uchar *)map->bitmap;
 
237
  uint32_t prefix_bytes, prefix_bits, d;
 
238
  unsigned char *m= (unsigned char *)map->bitmap;
240
239
 
241
240
  assert(map->bitmap &&
242
 
              (prefix_size <= map->n_bits || prefix_size == (uint) ~0));
 
241
              (prefix_size <= map->n_bits || prefix_size == UINT32_MAX));
243
242
  set_if_smaller(prefix_size, map->n_bits);
244
243
  if ((prefix_bytes= prefix_size / 8))
245
244
    memset(m, 0xff, prefix_bytes);
251
250
}
252
251
 
253
252
 
254
 
bool bitmap_is_prefix(const MY_BITMAP *map, uint prefix_size)
 
253
bool bitmap_is_prefix(const MY_BITMAP *map, uint32_t prefix_size)
255
254
{
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;
 
255
  uint32_t prefix_bits= prefix_size & 0x7, res;
 
256
  unsigned char *m= (unsigned char*)map->bitmap;
 
257
  unsigned char *end_prefix= m+prefix_size/8;
 
258
  unsigned char *end;
260
259
  assert(m && prefix_size <= map->n_bits);
261
260
  end= m+no_bytes_in_map(map);
262
261
 
274
273
      goto ret;
275
274
  res= 1;
276
275
ret:
277
 
  return res; 
 
276
  return res;
278
277
}
279
278
 
280
279
 
347
346
void bitmap_intersect(MY_BITMAP *map, const MY_BITMAP *map2)
348
347
{
349
348
  my_bitmap_map *to= map->bitmap, *from= map2->bitmap, *end;
350
 
  uint len= no_words_in_map(map), len2 = no_words_in_map(map2);
 
349
  uint32_t len= no_words_in_map(map), len2 = no_words_in_map(map2);
351
350
 
352
351
  assert(map->bitmap && map2->bitmap);
353
352
 
354
 
  end= to+min(len,len2);
 
353
  end= to+cmin(len,len2);
355
354
  *map2->last_word_ptr&= ~map2->last_word_mask; /*Clear last bits in map2*/
356
355
  while (to < end)
357
356
    *to++ &= *from++;
385
384
    void
386
385
*/
387
386
 
388
 
void bitmap_set_above(MY_BITMAP *map, uint from_byte, uint use_bit)
 
387
void bitmap_set_above(MY_BITMAP *map, uint32_t from_byte, uint32_t use_bit)
389
388
{
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;
 
389
  unsigned char use_byte= use_bit ? 0xff : 0;
 
390
  unsigned char *to= (unsigned char *)map->bitmap + from_byte;
 
391
  unsigned char *end= (unsigned char *)map->bitmap + (map->n_bits+7)/8;
393
392
 
394
393
  while (to < end)
395
394
    *to++= use_byte;
444
443
}
445
444
 
446
445
 
447
 
uint bitmap_bits_set(const MY_BITMAP *map)
448
 
{  
449
 
  uchar *m= (uchar*)map->bitmap;
450
 
  uchar *end= m + no_bytes_in_map(map);
451
 
  uint res= 0;
 
446
uint32_t bitmap_bits_set(const MY_BITMAP *map)
 
447
{
 
448
  unsigned char *m= (unsigned char*)map->bitmap;
 
449
  unsigned char *end= m + no_bytes_in_map(map);
 
450
  uint32_t res= 0;
452
451
 
453
452
  assert(map->bitmap);
454
453
  *map->last_word_ptr&= ~map->last_word_mask; /*Reset last bits to zero*/
455
454
  while (m < end)
456
 
    res+= my_count_bits_ushort(*m++);
 
455
    res+= my_count_bits_uint16(*m++);
457
456
  return res;
458
457
}
459
458
 
470
469
}
471
470
 
472
471
 
473
 
uint bitmap_get_first_set(const MY_BITMAP *map)
 
472
uint32_t bitmap_get_first_set(const MY_BITMAP *map)
474
473
{
475
 
  uchar *byte_ptr;
476
 
  uint i,j,k;
 
474
  unsigned char *byte_ptr;
 
475
  uint32_t i,j,k;
477
476
  my_bitmap_map *data_ptr, *end= map->last_word_ptr;
478
477
 
479
478
  assert(map->bitmap);
484
483
  {
485
484
    if (*data_ptr)
486
485
    {
487
 
      byte_ptr= (uchar*)data_ptr;
 
486
      byte_ptr= (unsigned char*)data_ptr;
488
487
      for (j=0; ; j++, byte_ptr++)
489
488
      {
490
489
        if (*byte_ptr)
494
493
            if (*byte_ptr & (1 << k))
495
494
              return (i*32) + (j*8) + k;
496
495
          }
497
 
          assert(0);
498
496
        }
499
497
      }
500
 
      assert(0);
501
498
    }
502
499
  }
503
500
  return MY_BIT_NONE;
504
501
}
505
502
 
506
503
 
507
 
uint bitmap_get_first(const MY_BITMAP *map)
 
504
uint32_t bitmap_get_first(const MY_BITMAP *map)
508
505
{
509
 
  uchar *byte_ptr;
510
 
  uint i,j,k;
 
506
  unsigned char *byte_ptr;
 
507
  uint32_t i,j,k;
511
508
  my_bitmap_map *data_ptr, *end= map->last_word_ptr;
512
509
 
513
510
  assert(map->bitmap);
518
515
  {
519
516
    if (*data_ptr != 0xFFFFFFFF)
520
517
    {
521
 
      byte_ptr= (uchar*)data_ptr;
 
518
      byte_ptr= (unsigned char*)data_ptr;
522
519
      for (j=0; ; j++, byte_ptr++)
523
 
      { 
 
520
      {
524
521
        if (*byte_ptr != 0xFF)
525
522
        {
526
523
          for (k=0; ; k++)
528
525
            if (!(*byte_ptr & (1 << k)))
529
526
              return (i*32) + (j*8) + k;
530
527
          }
531
 
          assert(0);
532
528
        }
533
529
      }
534
 
      assert(0);
535
530
    }
536
531
  }
537
532
  return MY_BIT_NONE;
538
533
}
539
534
 
540
535
 
541
 
uint bitmap_lock_set_next(MY_BITMAP *map)
 
536
uint32_t bitmap_lock_set_next(MY_BITMAP *map)
542
537
{
543
 
  uint bit_found;
 
538
  uint32_t bit_found;
544
539
  bitmap_lock(map);
545
540
  bit_found= bitmap_set_next(map);
546
541
  bitmap_unlock(map);
548
543
}
549
544
 
550
545
 
551
 
void bitmap_lock_clear_bit(MY_BITMAP *map, uint bitmap_bit)
 
546
void bitmap_lock_clear_bit(MY_BITMAP *map, uint32_t bitmap_bit)
552
547
{
553
548
  bitmap_lock(map);
554
549
  assert(map->bitmap && bitmap_bit < map->n_bits);
558
553
 
559
554
 
560
555
#ifdef NOT_USED
561
 
bool bitmap_lock_is_prefix(const MY_BITMAP *map, uint prefix_size)
 
556
bool bitmap_lock_is_prefix(const MY_BITMAP *map, uint32_t prefix_size)
562
557
{
563
558
  bool res;
564
559
  bitmap_lock((MY_BITMAP *)map);
584
579
}
585
580
 
586
581
 
587
 
void bitmap_lock_set_prefix(MY_BITMAP *map, uint prefix_size)
 
582
void bitmap_lock_set_prefix(MY_BITMAP *map, uint32_t prefix_size)
588
583
{
589
584
  bitmap_lock(map);
590
585
  bitmap_set_prefix(map, prefix_size);
594
589
 
595
590
bool bitmap_lock_is_clear_all(const MY_BITMAP *map)
596
591
{
597
 
  uint res;
 
592
  uint32_t res;
598
593
  bitmap_lock((MY_BITMAP *)map);
599
594
  res= bitmap_is_clear_all(map);
600
595
  bitmap_unlock((MY_BITMAP *)map);
604
599
 
605
600
bool bitmap_lock_is_set_all(const MY_BITMAP *map)
606
601
{
607
 
  uint res;
 
602
  uint32_t res;
608
603
  bitmap_lock((MY_BITMAP *)map);
609
604
  res= bitmap_is_set_all(map);
610
605
  bitmap_unlock((MY_BITMAP *)map);
612
607
}
613
608
 
614
609
 
615
 
bool bitmap_lock_is_set(const MY_BITMAP *map, uint bitmap_bit)
 
610
bool bitmap_lock_is_set(const MY_BITMAP *map, uint32_t bitmap_bit)
616
611
{
617
612
  bool res;
618
613
  assert(map->bitmap && bitmap_bit < map->n_bits);
625
620
 
626
621
bool bitmap_lock_is_subset(const MY_BITMAP *map1, const MY_BITMAP *map2)
627
622
{
628
 
  uint res;
 
623
  uint32_t res;
629
624
  bitmap_lock((MY_BITMAP *)map1);
630
625
  bitmap_lock((MY_BITMAP *)map2);
631
626
  res= bitmap_is_subset(map1, map2);
637
632
 
638
633
bool bitmap_lock_cmp(const MY_BITMAP *map1, const MY_BITMAP *map2)
639
634
{
640
 
  uint res;
 
635
  uint32_t res;
641
636
 
642
637
  assert(map1->bitmap && map2->bitmap &&
643
638
              map1->n_bits==map2->n_bits);
687
682
  RETURN
688
683
    Number of set bits in the bitmap.
689
684
*/
690
 
uint bitmap_lock_bits_set(const MY_BITMAP *map)
 
685
uint32_t bitmap_lock_bits_set(const MY_BITMAP *map)
691
686
{
692
 
  uint res;
 
687
  uint32_t res;
693
688
  bitmap_lock((MY_BITMAP *)map);
694
689
  assert(map->bitmap);
695
690
  res= bitmap_bits_set(map);
698
693
}
699
694
 
700
695
 
701
 
/* 
 
696
/*
702
697
  SYNOPSIS
703
698
    bitmap_get_first()
704
699
      map
705
 
  RETURN 
 
700
  RETURN
706
701
    Number of first unset bit in the bitmap or MY_BIT_NONE if all bits are set.
707
702
*/
708
 
uint bitmap_lock_get_first(const MY_BITMAP *map)
 
703
uint32_t bitmap_lock_get_first(const MY_BITMAP *map)
709
704
{
710
 
  uint res;
 
705
  uint32_t res;
711
706
  bitmap_lock((MY_BITMAP*)map);
712
707
  res= bitmap_get_first(map);
713
708
  bitmap_unlock((MY_BITMAP*)map);
715
710
}
716
711
 
717
712
 
718
 
uint bitmap_lock_get_first_set(const MY_BITMAP *map)
 
713
uint32_t bitmap_lock_get_first_set(const MY_BITMAP *map)
719
714
{
720
 
  uint res;
 
715
  uint32_t res;
721
716
  bitmap_lock((MY_BITMAP*)map);
722
717
  res= bitmap_get_first_set(map);
723
718
  bitmap_unlock((MY_BITMAP*)map);
725
720
}
726
721
 
727
722
 
728
 
void bitmap_lock_set_bit(MY_BITMAP *map, uint bitmap_bit)
 
723
void bitmap_lock_set_bit(MY_BITMAP *map, uint32_t bitmap_bit)
729
724
{
730
725
  assert(map->bitmap && bitmap_bit < map->n_bits);
731
726
  bitmap_lock(map);
734
729
}
735
730
 
736
731
 
737
 
void bitmap_lock_flip_bit(MY_BITMAP *map, uint bitmap_bit)
 
732
void bitmap_lock_flip_bit(MY_BITMAP *map, uint32_t bitmap_bit)
738
733
{
739
734
  assert(map->bitmap && bitmap_bit < map->n_bits);
740
735
  bitmap_lock(map);
744
739
#endif
745
740
#ifdef MAIN
746
741
 
747
 
uint get_rand_bit(uint bitsize)
 
742
uint32_t get_rand_bit(uint32_t bitsize)
748
743
{
749
744
  return (rand() % bitsize);
750
745
}
751
746
 
752
 
bool test_set_get_clear_bit(MY_BITMAP *map, uint bitsize)
 
747
bool test_set_get_clear_bit(MY_BITMAP *map, uint32_t bitsize)
753
748
{
754
 
  uint i, test_bit;
755
 
  uint no_loops= bitsize > 128 ? 128 : bitsize;
 
749
  uint32_t i, test_bit;
 
750
  uint32_t no_loops= bitsize > 128 ? 128 : bitsize;
756
751
  for (i=0; i < no_loops; i++)
757
752
  {
758
753
    test_bit= get_rand_bit(bitsize);
772
767
  return true;
773
768
}
774
769
 
775
 
bool test_flip_bit(MY_BITMAP *map, uint bitsize)
 
770
bool test_flip_bit(MY_BITMAP *map, uint32_t bitsize)
776
771
{
777
 
  uint i, test_bit;
778
 
  uint no_loops= bitsize > 128 ? 128 : bitsize;
 
772
  uint32_t i, test_bit;
 
773
  uint32_t no_loops= bitsize > 128 ? 128 : bitsize;
779
774
  for (i=0; i < no_loops; i++)
780
775
  {
781
776
    test_bit= get_rand_bit(bitsize);
795
790
  return true;
796
791
}
797
792
 
798
 
bool test_operators(MY_BITMAP *map __attribute__((unused)),
799
 
                    uint bitsize __attribute__((unused)))
 
793
bool test_operators(MY_BITMAP *, uint32_t)
800
794
{
801
795
  return false;
802
796
}
803
797
 
804
 
bool test_get_all_bits(MY_BITMAP *map, uint bitsize)
 
798
bool test_get_all_bits(MY_BITMAP *map, uint32_t bitsize)
805
799
{
806
 
  uint i;
 
800
  uint32_t i;
807
801
  bitmap_set_all(map);
808
802
  if (!bitmap_is_set_all(map))
809
803
    goto error1;
843
837
  return true;
844
838
}
845
839
 
846
 
bool test_compare_operators(MY_BITMAP *map, uint bitsize)
 
840
bool test_compare_operators(MY_BITMAP *map, uint32_t bitsize)
847
841
{
848
 
  uint i, j, test_bit1, test_bit2, test_bit3,test_bit4;
849
 
  uint no_loops= bitsize > 128 ? 128 : bitsize;
 
842
  uint32_t i, j, test_bit1, test_bit2, test_bit3,test_bit4;
 
843
  uint32_t no_loops= bitsize > 128 ? 128 : bitsize;
850
844
  MY_BITMAP map2_obj, map3_obj;
851
845
  MY_BITMAP *map2= &map2_obj, *map3= &map3_obj;
852
846
  my_bitmap_map map2buf[1024];
949
943
  return true;
950
944
}
951
945
 
952
 
bool test_count_bits_set(MY_BITMAP *map, uint bitsize)
 
946
bool test_count_bits_set(MY_BITMAP *map, uint32_t bitsize)
953
947
{
954
 
  uint i, bit_count=0, test_bit;
955
 
  uint no_loops= bitsize > 128 ? 128 : bitsize;
 
948
  uint32_t i, bit_count=0, test_bit;
 
949
  uint32_t no_loops= bitsize > 128 ? 128 : bitsize;
956
950
  for (i=0; i < no_loops; i++)
957
951
  {
958
952
    test_bit=get_rand_bit(bitsize);
975
969
  return true;
976
970
}
977
971
 
978
 
bool test_get_first_bit(MY_BITMAP *map, uint bitsize)
 
972
bool test_get_first_bit(MY_BITMAP *map, uint32_t bitsize)
979
973
{
980
 
  uint i, test_bit;
981
 
  uint no_loops= bitsize > 128 ? 128 : bitsize;
 
974
  uint32_t i, test_bit;
 
975
  uint32_t no_loops= bitsize > 128 ? 128 : bitsize;
982
976
  for (i=0; i < no_loops; i++)
983
977
  {
984
978
    test_bit=get_rand_bit(bitsize);
1000
994
  return true;
1001
995
}
1002
996
 
1003
 
bool test_get_next_bit(MY_BITMAP *map, uint bitsize)
 
997
bool test_get_next_bit(MY_BITMAP *map, uint32_t bitsize)
1004
998
{
1005
 
  uint i, j, test_bit;
1006
 
  uint no_loops= bitsize > 128 ? 128 : bitsize;
 
999
  uint32_t i, j, test_bit;
 
1000
  uint32_t no_loops= bitsize > 128 ? 128 : bitsize;
1007
1001
  for (i=0; i < no_loops; i++)
1008
1002
  {
1009
1003
    test_bit=get_rand_bit(bitsize);
1019
1013
  return true;
1020
1014
}
1021
1015
 
1022
 
bool test_prefix(MY_BITMAP *map, uint bitsize)
 
1016
bool test_prefix(MY_BITMAP *map, uint32_t bitsize)
1023
1017
{
1024
 
  uint i, j, test_bit;
1025
 
  uint no_loops= bitsize > 128 ? 128 : bitsize;
 
1018
  uint32_t i, j, test_bit;
 
1019
  uint32_t no_loops= bitsize > 128 ? 128 : bitsize;
1026
1020
  for (i=0; i < no_loops; i++)
1027
1021
  {
1028
1022
    test_bit=get_rand_bit(bitsize);
1054
1048
}
1055
1049
 
1056
1050
 
1057
 
bool do_test(uint bitsize)
 
1051
bool do_test(uint32_t bitsize)
1058
1052
{
1059
1053
  MY_BITMAP map;
1060
1054
  my_bitmap_map buf[1024];