← 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-07-01 20:14:24 UTC
  • Revision ID: brian@tangent.org-20080701201424-rsof5enxl7gkr50p
More cleanup on pread()

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;
85
85
 
86
86
static inline void bitmap_lock(MY_BITMAP *map __attribute__((unused)))
87
87
{
 
88
#ifdef THREAD
88
89
  if (map->mutex)
89
90
    pthread_mutex_lock(map->mutex);
 
91
#endif
90
92
}
91
93
 
92
94
static inline void bitmap_unlock(MY_BITMAP *map __attribute__((unused)))
93
95
{
 
96
#ifdef THREAD
94
97
  if (map->mutex)
95
98
    pthread_mutex_unlock(map->mutex);
 
99
#endif
96
100
}
97
101
 
98
102
 
99
 
bool bitmap_init(MY_BITMAP *map, my_bitmap_map *buf, uint32_t n_bits,
100
 
                    bool thread_safe __attribute__((unused)))
 
103
my_bool bitmap_init(MY_BITMAP *map, my_bitmap_map *buf, uint n_bits,
 
104
                    my_bool thread_safe __attribute__((unused)))
101
105
{
 
106
  DBUG_ENTER("bitmap_init");
102
107
  if (!buf)
103
108
  {
104
 
    uint32_t size_in_bytes= bitmap_buffer_size(n_bits);
105
 
    uint32_t extra= 0;
 
109
    uint size_in_bytes= bitmap_buffer_size(n_bits);
 
110
    uint extra= 0;
 
111
#ifdef THREAD
106
112
    if (thread_safe)
107
113
    {
108
114
      size_in_bytes= ALIGN_SIZE(size_in_bytes);
109
115
      extra= sizeof(pthread_mutex_t);
110
116
    }
111
117
    map->mutex= 0;
 
118
#endif
112
119
    if (!(buf= (my_bitmap_map*) my_malloc(size_in_bytes+extra, MYF(MY_WME))))
113
 
      return(1);
 
120
      DBUG_RETURN(1);
 
121
#ifdef THREAD
114
122
    if (thread_safe)
115
123
    {
116
124
      map->mutex= (pthread_mutex_t *) ((char*) buf + size_in_bytes);
117
125
      pthread_mutex_init(map->mutex, MY_MUTEX_INIT_FAST);
118
126
    }
 
127
#endif
119
128
  }
 
129
#ifdef THREAD
120
130
  else
121
131
  {
122
 
    assert(thread_safe == 0);
 
132
    DBUG_ASSERT(thread_safe == 0);
123
133
  }
 
134
#endif
124
135
 
125
136
  map->bitmap= buf;
126
137
  map->n_bits= n_bits;
127
138
  create_last_word_mask(map);
128
139
  bitmap_clear_all(map);
129
 
  return(0);
 
140
  DBUG_RETURN(0);
130
141
}
131
142
 
132
143
 
133
144
void bitmap_free(MY_BITMAP *map)
134
145
{
 
146
  DBUG_ENTER("bitmap_free");
135
147
  if (map->bitmap)
136
148
  {
 
149
#ifdef THREAD
137
150
    if (map->mutex)
138
151
      pthread_mutex_destroy(map->mutex);
139
 
    free((char*) map->bitmap);
 
152
#endif
 
153
    my_free((char*) map->bitmap, MYF(0));
140
154
    map->bitmap=0;
141
155
  }
142
 
  return;
 
156
  DBUG_VOID_RETURN;
143
157
}
144
158
 
145
159
 
156
170
    !=0  bit was set
157
171
*/
158
172
 
159
 
bool bitmap_fast_test_and_set(MY_BITMAP *map, uint32_t bitmap_bit)
 
173
my_bool bitmap_fast_test_and_set(MY_BITMAP *map, uint bitmap_bit)
160
174
{
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;
 
175
  uchar *value= ((uchar*) map->bitmap) + (bitmap_bit / 8);
 
176
  uchar bit= 1 << ((bitmap_bit) & 7);
 
177
  uchar res= (*value) & bit;
164
178
  *value|= bit;
165
179
  return res;
166
180
}
179
193
    !=0  bit was set
180
194
*/
181
195
 
182
 
bool bitmap_test_and_set(MY_BITMAP *map, uint32_t bitmap_bit)
 
196
my_bool bitmap_test_and_set(MY_BITMAP *map, uint bitmap_bit)
183
197
{
184
 
  bool res;
185
 
  assert(map->bitmap && bitmap_bit < map->n_bits);
 
198
  my_bool res;
 
199
  DBUG_ASSERT(map->bitmap && bitmap_bit < map->n_bits);
186
200
  bitmap_lock(map);
187
201
  res= bitmap_fast_test_and_set(map, bitmap_bit);
188
202
  bitmap_unlock(map);
202
216
    !=0  bit was set
203
217
*/
204
218
 
205
 
bool bitmap_fast_test_and_clear(MY_BITMAP *map, uint32_t bitmap_bit)
 
219
my_bool bitmap_fast_test_and_clear(MY_BITMAP *map, uint bitmap_bit)
206
220
{
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;
 
221
  uchar *byte= (uchar*) map->bitmap + (bitmap_bit / 8);
 
222
  uchar bit= 1 << ((bitmap_bit) & 7);
 
223
  uchar res= (*byte) & bit;
210
224
  *byte&= ~bit;
211
225
  return res;
212
226
}
213
227
 
214
228
 
215
 
bool bitmap_test_and_clear(MY_BITMAP *map, uint32_t bitmap_bit)
 
229
my_bool bitmap_test_and_clear(MY_BITMAP *map, uint bitmap_bit)
216
230
{
217
 
  bool res;
218
 
  assert(map->bitmap && bitmap_bit < map->n_bits);
 
231
  my_bool res;
 
232
  DBUG_ASSERT(map->bitmap && bitmap_bit < map->n_bits);
219
233
  bitmap_lock(map);
220
234
  res= bitmap_fast_test_and_clear(map, bitmap_bit);
221
235
  bitmap_unlock(map);
223
237
}
224
238
 
225
239
 
226
 
uint32_t bitmap_set_next(MY_BITMAP *map)
 
240
uint bitmap_set_next(MY_BITMAP *map)
227
241
{
228
 
  uint32_t bit_found;
229
 
  assert(map->bitmap);
 
242
  uint bit_found;
 
243
  DBUG_ASSERT(map->bitmap);
230
244
  if ((bit_found= bitmap_get_first(map)) != MY_BIT_NONE)
231
245
    bitmap_set_bit(map, bit_found);
232
246
  return bit_found;
233
247
}
234
248
 
235
249
 
236
 
void bitmap_set_prefix(MY_BITMAP *map, uint32_t prefix_size)
 
250
void bitmap_set_prefix(MY_BITMAP *map, uint prefix_size)
237
251
{
238
 
  uint32_t prefix_bytes, prefix_bits, d;
239
 
  unsigned char *m= (unsigned char *)map->bitmap;
 
252
  uint prefix_bytes, prefix_bits, d;
 
253
  uchar *m= (uchar *)map->bitmap;
240
254
 
241
 
  assert(map->bitmap &&
242
 
              (prefix_size <= map->n_bits || prefix_size == UINT32_MAX));
 
255
  DBUG_ASSERT(map->bitmap &&
 
256
              (prefix_size <= map->n_bits || prefix_size == (uint) ~0));
243
257
  set_if_smaller(prefix_size, map->n_bits);
244
258
  if ((prefix_bytes= prefix_size / 8))
245
259
    memset(m, 0xff, prefix_bytes);
247
261
  if ((prefix_bits= prefix_size & 7))
248
262
    *m++= (1 << prefix_bits)-1;
249
263
  if ((d= no_bytes_in_map(map)-prefix_bytes))
250
 
    memset(m, 0, d);
 
264
    bzero(m, d);
251
265
}
252
266
 
253
267
 
254
 
bool bitmap_is_prefix(const MY_BITMAP *map, uint32_t prefix_size)
 
268
my_bool bitmap_is_prefix(const MY_BITMAP *map, uint prefix_size)
255
269
{
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);
 
270
  uint prefix_bits= prefix_size & 0x7, res;
 
271
  uchar *m= (uchar*)map->bitmap;
 
272
  uchar *end_prefix= m+prefix_size/8;
 
273
  uchar *end;
 
274
  DBUG_ASSERT(m && prefix_size <= map->n_bits);
261
275
  end= m+no_bytes_in_map(map);
262
276
 
263
277
  while (m < end_prefix)
278
292
}
279
293
 
280
294
 
281
 
bool bitmap_is_set_all(const MY_BITMAP *map)
 
295
my_bool bitmap_is_set_all(const MY_BITMAP *map)
282
296
{
283
297
  my_bitmap_map *data_ptr= map->bitmap;
284
298
  my_bitmap_map *end= map->last_word_ptr;
285
299
  *map->last_word_ptr |= map->last_word_mask;
286
300
  for (; data_ptr <= end; data_ptr++)
287
301
    if (*data_ptr != 0xFFFFFFFF)
288
 
      return false;
289
 
  return true;
 
302
      return FALSE;
 
303
  return TRUE;
290
304
}
291
305
 
292
306
 
293
 
bool bitmap_is_clear_all(const MY_BITMAP *map)
 
307
my_bool bitmap_is_clear_all(const MY_BITMAP *map)
294
308
{
295
309
  my_bitmap_map *data_ptr= map->bitmap;
296
310
  my_bitmap_map *end;
297
311
  if (*map->last_word_ptr & ~map->last_word_mask)
298
 
    return false;
 
312
    return FALSE;
299
313
  end= map->last_word_ptr;
300
314
  for (; data_ptr < end; data_ptr++)
301
315
    if (*data_ptr)
302
 
      return false;
303
 
  return true;
 
316
      return FALSE;
 
317
  return TRUE;
304
318
}
305
319
 
306
 
/* Return true if map1 is a subset of map2 */
 
320
/* Return TRUE if map1 is a subset of map2 */
307
321
 
308
 
bool bitmap_is_subset(const MY_BITMAP *map1, const MY_BITMAP *map2)
 
322
my_bool bitmap_is_subset(const MY_BITMAP *map1, const MY_BITMAP *map2)
309
323
{
310
324
  my_bitmap_map *m1= map1->bitmap, *m2= map2->bitmap, *end;
311
325
 
312
 
  assert(map1->bitmap && map2->bitmap &&
 
326
  DBUG_ASSERT(map1->bitmap && map2->bitmap &&
313
327
              map1->n_bits==map2->n_bits);
314
328
 
315
329
  end= map1->last_word_ptr;
325
339
 
326
340
/* True if bitmaps has any common bits */
327
341
 
328
 
bool bitmap_is_overlapping(const MY_BITMAP *map1, const MY_BITMAP *map2)
 
342
my_bool bitmap_is_overlapping(const MY_BITMAP *map1, const MY_BITMAP *map2)
329
343
{
330
344
  my_bitmap_map *m1= map1->bitmap, *m2= map2->bitmap, *end;
331
345
 
332
 
  assert(map1->bitmap && map2->bitmap &&
 
346
  DBUG_ASSERT(map1->bitmap && map2->bitmap &&
333
347
              map1->n_bits==map2->n_bits);
334
348
 
335
349
  end= map1->last_word_ptr;
347
361
void bitmap_intersect(MY_BITMAP *map, const MY_BITMAP *map2)
348
362
{
349
363
  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);
 
364
  uint len= no_words_in_map(map), len2 = no_words_in_map(map2);
 
365
 
 
366
  DBUG_ASSERT(map->bitmap && map2->bitmap);
 
367
 
 
368
  end= to+min(len,len2);
355
369
  *map2->last_word_ptr&= ~map2->last_word_mask; /*Clear last bits in map2*/
356
370
  while (to < end)
357
371
    *to++ &= *from++;
385
399
    void
386
400
*/
387
401
 
388
 
void bitmap_set_above(MY_BITMAP *map, uint32_t from_byte, uint32_t use_bit)
 
402
void bitmap_set_above(MY_BITMAP *map, uint from_byte, uint use_bit)
389
403
{
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;
 
404
  uchar use_byte= use_bit ? 0xff : 0;
 
405
  uchar *to= (uchar *)map->bitmap + from_byte;
 
406
  uchar *end= (uchar *)map->bitmap + (map->n_bits+7)/8;
393
407
 
394
408
  while (to < end)
395
409
    *to++= use_byte;
399
413
void bitmap_subtract(MY_BITMAP *map, const MY_BITMAP *map2)
400
414
{
401
415
  my_bitmap_map *to= map->bitmap, *from= map2->bitmap, *end;
402
 
  assert(map->bitmap && map2->bitmap &&
 
416
  DBUG_ASSERT(map->bitmap && map2->bitmap &&
403
417
              map->n_bits==map2->n_bits);
404
418
 
405
419
  end= map->last_word_ptr;
413
427
{
414
428
  my_bitmap_map *to= map->bitmap, *from= map2->bitmap, *end;
415
429
 
416
 
  assert(map->bitmap && map2->bitmap &&
 
430
  DBUG_ASSERT(map->bitmap && map2->bitmap &&
417
431
              map->n_bits==map2->n_bits);
418
432
  end= map->last_word_ptr;
419
433
 
425
439
void bitmap_xor(MY_BITMAP *map, const MY_BITMAP *map2)
426
440
{
427
441
  my_bitmap_map *to= map->bitmap, *from= map2->bitmap, *end= map->last_word_ptr;
428
 
  assert(map->bitmap && map2->bitmap &&
 
442
  DBUG_ASSERT(map->bitmap && map2->bitmap &&
429
443
              map->n_bits==map2->n_bits);
430
444
  while (to <= end)
431
445
    *to++ ^= *from++;
436
450
{
437
451
  my_bitmap_map *to= map->bitmap, *end;
438
452
 
439
 
  assert(map->bitmap);
 
453
  DBUG_ASSERT(map->bitmap);
440
454
  end= map->last_word_ptr;
441
455
 
442
456
  while (to <= end)
444
458
}
445
459
 
446
460
 
447
 
uint32_t bitmap_bits_set(const MY_BITMAP *map)
 
461
uint bitmap_bits_set(const MY_BITMAP *map)
448
462
{  
449
 
  unsigned char *m= (unsigned char*)map->bitmap;
450
 
  unsigned char *end= m + no_bytes_in_map(map);
451
 
  uint32_t res= 0;
 
463
  uchar *m= (uchar*)map->bitmap;
 
464
  uchar *end= m + no_bytes_in_map(map);
 
465
  uint res= 0;
452
466
 
453
 
  assert(map->bitmap);
 
467
  DBUG_ASSERT(map->bitmap);
454
468
  *map->last_word_ptr&= ~map->last_word_mask; /*Reset last bits to zero*/
455
469
  while (m < end)
456
 
    res+= my_count_bits_uint16(*m++);
 
470
    res+= my_count_bits_ushort(*m++);
457
471
  return res;
458
472
}
459
473
 
462
476
{
463
477
  my_bitmap_map *to= map->bitmap, *from= map2->bitmap, *end;
464
478
 
465
 
  assert(map->bitmap && map2->bitmap &&
 
479
  DBUG_ASSERT(map->bitmap && map2->bitmap &&
466
480
              map->n_bits==map2->n_bits);
467
481
  end= map->last_word_ptr;
468
482
  while (to <= end)
470
484
}
471
485
 
472
486
 
473
 
uint32_t bitmap_get_first_set(const MY_BITMAP *map)
 
487
uint bitmap_get_first_set(const MY_BITMAP *map)
474
488
{
475
 
  unsigned char *byte_ptr;
476
 
  uint32_t i,j,k;
 
489
  uchar *byte_ptr;
 
490
  uint i,j,k;
477
491
  my_bitmap_map *data_ptr, *end= map->last_word_ptr;
478
492
 
479
 
  assert(map->bitmap);
 
493
  DBUG_ASSERT(map->bitmap);
480
494
  data_ptr= map->bitmap;
481
495
  *map->last_word_ptr &= ~map->last_word_mask;
482
496
 
484
498
  {
485
499
    if (*data_ptr)
486
500
    {
487
 
      byte_ptr= (unsigned char*)data_ptr;
 
501
      byte_ptr= (uchar*)data_ptr;
488
502
      for (j=0; ; j++, byte_ptr++)
489
503
      {
490
504
        if (*byte_ptr)
494
508
            if (*byte_ptr & (1 << k))
495
509
              return (i*32) + (j*8) + k;
496
510
          }
497
 
          assert(0);
 
511
          DBUG_ASSERT(0);
498
512
        }
499
513
      }
500
 
      assert(0);
 
514
      DBUG_ASSERT(0);
501
515
    }
502
516
  }
503
517
  return MY_BIT_NONE;
504
518
}
505
519
 
506
520
 
507
 
uint32_t bitmap_get_first(const MY_BITMAP *map)
 
521
uint bitmap_get_first(const MY_BITMAP *map)
508
522
{
509
 
  unsigned char *byte_ptr;
510
 
  uint32_t i,j,k;
 
523
  uchar *byte_ptr;
 
524
  uint i,j,k;
511
525
  my_bitmap_map *data_ptr, *end= map->last_word_ptr;
512
526
 
513
 
  assert(map->bitmap);
 
527
  DBUG_ASSERT(map->bitmap);
514
528
  data_ptr= map->bitmap;
515
529
  *map->last_word_ptr|= map->last_word_mask;
516
530
 
518
532
  {
519
533
    if (*data_ptr != 0xFFFFFFFF)
520
534
    {
521
 
      byte_ptr= (unsigned char*)data_ptr;
 
535
      byte_ptr= (uchar*)data_ptr;
522
536
      for (j=0; ; j++, byte_ptr++)
523
537
      { 
524
538
        if (*byte_ptr != 0xFF)
528
542
            if (!(*byte_ptr & (1 << k)))
529
543
              return (i*32) + (j*8) + k;
530
544
          }
531
 
          assert(0);
 
545
          DBUG_ASSERT(0);
532
546
        }
533
547
      }
534
 
      assert(0);
 
548
      DBUG_ASSERT(0);
535
549
    }
536
550
  }
537
551
  return MY_BIT_NONE;
538
552
}
539
553
 
540
554
 
541
 
uint32_t bitmap_lock_set_next(MY_BITMAP *map)
 
555
uint bitmap_lock_set_next(MY_BITMAP *map)
542
556
{
543
 
  uint32_t bit_found;
 
557
  uint bit_found;
544
558
  bitmap_lock(map);
545
559
  bit_found= bitmap_set_next(map);
546
560
  bitmap_unlock(map);
548
562
}
549
563
 
550
564
 
551
 
void bitmap_lock_clear_bit(MY_BITMAP *map, uint32_t bitmap_bit)
 
565
void bitmap_lock_clear_bit(MY_BITMAP *map, uint bitmap_bit)
552
566
{
553
567
  bitmap_lock(map);
554
 
  assert(map->bitmap && bitmap_bit < map->n_bits);
 
568
  DBUG_ASSERT(map->bitmap && bitmap_bit < map->n_bits);
555
569
  bitmap_clear_bit(map, bitmap_bit);
556
570
  bitmap_unlock(map);
557
571
}
558
572
 
559
573
 
560
574
#ifdef NOT_USED
561
 
bool bitmap_lock_is_prefix(const MY_BITMAP *map, uint32_t prefix_size)
 
575
my_bool bitmap_lock_is_prefix(const MY_BITMAP *map, uint prefix_size)
562
576
{
563
 
  bool res;
 
577
  my_bool res;
564
578
  bitmap_lock((MY_BITMAP *)map);
565
579
  res= bitmap_is_prefix(map, prefix_size);
566
580
  bitmap_unlock((MY_BITMAP *)map);
584
598
}
585
599
 
586
600
 
587
 
void bitmap_lock_set_prefix(MY_BITMAP *map, uint32_t prefix_size)
 
601
void bitmap_lock_set_prefix(MY_BITMAP *map, uint prefix_size)
588
602
{
589
603
  bitmap_lock(map);
590
604
  bitmap_set_prefix(map, prefix_size);
592
606
}
593
607
 
594
608
 
595
 
bool bitmap_lock_is_clear_all(const MY_BITMAP *map)
 
609
my_bool bitmap_lock_is_clear_all(const MY_BITMAP *map)
596
610
{
597
 
  uint32_t res;
 
611
  uint res;
598
612
  bitmap_lock((MY_BITMAP *)map);
599
613
  res= bitmap_is_clear_all(map);
600
614
  bitmap_unlock((MY_BITMAP *)map);
602
616
}
603
617
 
604
618
 
605
 
bool bitmap_lock_is_set_all(const MY_BITMAP *map)
 
619
my_bool bitmap_lock_is_set_all(const MY_BITMAP *map)
606
620
{
607
 
  uint32_t res;
 
621
  uint res;
608
622
  bitmap_lock((MY_BITMAP *)map);
609
623
  res= bitmap_is_set_all(map);
610
624
  bitmap_unlock((MY_BITMAP *)map);
612
626
}
613
627
 
614
628
 
615
 
bool bitmap_lock_is_set(const MY_BITMAP *map, uint32_t bitmap_bit)
 
629
my_bool bitmap_lock_is_set(const MY_BITMAP *map, uint bitmap_bit)
616
630
{
617
 
  bool res;
618
 
  assert(map->bitmap && bitmap_bit < map->n_bits);
 
631
  my_bool res;
 
632
  DBUG_ASSERT(map->bitmap && bitmap_bit < map->n_bits);
619
633
  bitmap_lock((MY_BITMAP *)map);
620
634
  res= bitmap_is_set(map, bitmap_bit);
621
635
  bitmap_unlock((MY_BITMAP *)map);
623
637
}
624
638
 
625
639
 
626
 
bool bitmap_lock_is_subset(const MY_BITMAP *map1, const MY_BITMAP *map2)
 
640
my_bool bitmap_lock_is_subset(const MY_BITMAP *map1, const MY_BITMAP *map2)
627
641
{
628
 
  uint32_t res;
 
642
  uint res;
629
643
  bitmap_lock((MY_BITMAP *)map1);
630
644
  bitmap_lock((MY_BITMAP *)map2);
631
645
  res= bitmap_is_subset(map1, map2);
635
649
}
636
650
 
637
651
 
638
 
bool bitmap_lock_cmp(const MY_BITMAP *map1, const MY_BITMAP *map2)
 
652
my_bool bitmap_lock_cmp(const MY_BITMAP *map1, const MY_BITMAP *map2)
639
653
{
640
 
  uint32_t res;
 
654
  uint res;
641
655
 
642
 
  assert(map1->bitmap && map2->bitmap &&
 
656
  DBUG_ASSERT(map1->bitmap && map2->bitmap &&
643
657
              map1->n_bits==map2->n_bits);
644
658
  bitmap_lock((MY_BITMAP *)map1);
645
659
  bitmap_lock((MY_BITMAP *)map2);
687
701
  RETURN
688
702
    Number of set bits in the bitmap.
689
703
*/
690
 
uint32_t bitmap_lock_bits_set(const MY_BITMAP *map)
 
704
uint bitmap_lock_bits_set(const MY_BITMAP *map)
691
705
{
692
 
  uint32_t res;
 
706
  uint res;
693
707
  bitmap_lock((MY_BITMAP *)map);
694
 
  assert(map->bitmap);
 
708
  DBUG_ASSERT(map->bitmap);
695
709
  res= bitmap_bits_set(map);
696
710
  bitmap_unlock((MY_BITMAP *)map);
697
711
  return res;
705
719
  RETURN 
706
720
    Number of first unset bit in the bitmap or MY_BIT_NONE if all bits are set.
707
721
*/
708
 
uint32_t bitmap_lock_get_first(const MY_BITMAP *map)
 
722
uint bitmap_lock_get_first(const MY_BITMAP *map)
709
723
{
710
 
  uint32_t res;
 
724
  uint res;
711
725
  bitmap_lock((MY_BITMAP*)map);
712
726
  res= bitmap_get_first(map);
713
727
  bitmap_unlock((MY_BITMAP*)map);
715
729
}
716
730
 
717
731
 
718
 
uint32_t bitmap_lock_get_first_set(const MY_BITMAP *map)
 
732
uint bitmap_lock_get_first_set(const MY_BITMAP *map)
719
733
{
720
 
  uint32_t res;
 
734
  uint res;
721
735
  bitmap_lock((MY_BITMAP*)map);
722
736
  res= bitmap_get_first_set(map);
723
737
  bitmap_unlock((MY_BITMAP*)map);
725
739
}
726
740
 
727
741
 
728
 
void bitmap_lock_set_bit(MY_BITMAP *map, uint32_t bitmap_bit)
 
742
void bitmap_lock_set_bit(MY_BITMAP *map, uint bitmap_bit)
729
743
{
730
 
  assert(map->bitmap && bitmap_bit < map->n_bits);
 
744
  DBUG_ASSERT(map->bitmap && bitmap_bit < map->n_bits);
731
745
  bitmap_lock(map);
732
746
  bitmap_set_bit(map, bitmap_bit);
733
747
  bitmap_unlock(map);
734
748
}
735
749
 
736
750
 
737
 
void bitmap_lock_flip_bit(MY_BITMAP *map, uint32_t bitmap_bit)
 
751
void bitmap_lock_flip_bit(MY_BITMAP *map, uint bitmap_bit)
738
752
{
739
 
  assert(map->bitmap && bitmap_bit < map->n_bits);
 
753
  DBUG_ASSERT(map->bitmap && bitmap_bit < map->n_bits);
740
754
  bitmap_lock(map);
741
755
  bitmap_flip_bit(map, bitmap_bit);
742
756
  bitmap_unlock(map);
744
758
#endif
745
759
#ifdef MAIN
746
760
 
747
 
uint32_t get_rand_bit(uint32_t bitsize)
 
761
uint get_rand_bit(uint bitsize)
748
762
{
749
763
  return (rand() % bitsize);
750
764
}
751
765
 
752
 
bool test_set_get_clear_bit(MY_BITMAP *map, uint32_t bitsize)
 
766
bool test_set_get_clear_bit(MY_BITMAP *map, uint bitsize)
753
767
{
754
 
  uint32_t i, test_bit;
755
 
  uint32_t no_loops= bitsize > 128 ? 128 : bitsize;
 
768
  uint i, test_bit;
 
769
  uint no_loops= bitsize > 128 ? 128 : bitsize;
756
770
  for (i=0; i < no_loops; i++)
757
771
  {
758
772
    test_bit= get_rand_bit(bitsize);
763
777
    if (bitmap_is_set(map, test_bit))
764
778
      goto error2;
765
779
  }
766
 
  return false;
 
780
  return FALSE;
767
781
error1:
768
782
  printf("Error in set bit, bit %u, bitsize = %u", test_bit, bitsize);
769
 
  return true;
 
783
  return TRUE;
770
784
error2:
771
785
  printf("Error in clear bit, bit %u, bitsize = %u", test_bit, bitsize);
772
 
  return true;
 
786
  return TRUE;
773
787
}
774
788
 
775
 
bool test_flip_bit(MY_BITMAP *map, uint32_t bitsize)
 
789
bool test_flip_bit(MY_BITMAP *map, uint bitsize)
776
790
{
777
 
  uint32_t i, test_bit;
778
 
  uint32_t no_loops= bitsize > 128 ? 128 : bitsize;
 
791
  uint i, test_bit;
 
792
  uint no_loops= bitsize > 128 ? 128 : bitsize;
779
793
  for (i=0; i < no_loops; i++)
780
794
  {
781
795
    test_bit= get_rand_bit(bitsize);
786
800
    if (bitmap_is_set(map, test_bit))
787
801
      goto error2;
788
802
  }
789
 
  return false;
 
803
  return FALSE;
790
804
error1:
791
805
  printf("Error in flip bit 1, bit %u, bitsize = %u", test_bit, bitsize);
792
 
  return true;
 
806
  return TRUE;
793
807
error2:
794
808
  printf("Error in flip bit 2, bit %u, bitsize = %u", test_bit, bitsize);
795
 
  return true;
 
809
  return TRUE;
796
810
}
797
811
 
798
812
bool test_operators(MY_BITMAP *map __attribute__((unused)),
799
 
                    uint32_t bitsize __attribute__((unused)))
 
813
                    uint bitsize __attribute__((unused)))
800
814
{
801
 
  return false;
 
815
  return FALSE;
802
816
}
803
817
 
804
 
bool test_get_all_bits(MY_BITMAP *map, uint32_t bitsize)
 
818
bool test_get_all_bits(MY_BITMAP *map, uint bitsize)
805
819
{
806
 
  uint32_t i;
 
820
  uint i;
807
821
  bitmap_set_all(map);
808
822
  if (!bitmap_is_set_all(map))
809
823
    goto error1;
822
836
    bitmap_clear_bit(map, i);
823
837
  if (!bitmap_is_clear_all(map))
824
838
    goto error4;
825
 
  return false;
 
839
  return FALSE;
826
840
error1:
827
841
  printf("Error in set_all, bitsize = %u", bitsize);
828
 
  return true;
 
842
  return TRUE;
829
843
error2:
830
844
  printf("Error in clear_all, bitsize = %u", bitsize);
831
 
  return true;
 
845
  return TRUE;
832
846
error3:
833
847
  printf("Error in bitmap_is_set_all, bitsize = %u", bitsize);
834
 
  return true;
 
848
  return TRUE;
835
849
error4:
836
850
  printf("Error in bitmap_is_clear_all, bitsize = %u", bitsize);
837
 
  return true;
 
851
  return TRUE;
838
852
error5:
839
853
  printf("Error in set_all through set_prefix, bitsize = %u", bitsize);
840
 
  return true;
 
854
  return TRUE;
841
855
error6:
842
856
  printf("Error in clear_all through set_prefix, bitsize = %u", bitsize);
843
 
  return true;
 
857
  return TRUE;
844
858
}
845
859
 
846
 
bool test_compare_operators(MY_BITMAP *map, uint32_t bitsize)
 
860
bool test_compare_operators(MY_BITMAP *map, uint bitsize)
847
861
{
848
 
  uint32_t i, j, test_bit1, test_bit2, test_bit3,test_bit4;
849
 
  uint32_t no_loops= bitsize > 128 ? 128 : bitsize;
 
862
  uint i, j, test_bit1, test_bit2, test_bit3,test_bit4;
 
863
  uint no_loops= bitsize > 128 ? 128 : bitsize;
850
864
  MY_BITMAP map2_obj, map3_obj;
851
865
  MY_BITMAP *map2= &map2_obj, *map3= &map3_obj;
852
866
  my_bitmap_map map2buf[1024];
853
867
  my_bitmap_map map3buf[1024];
854
 
  bitmap_init(&map2_obj, map2buf, bitsize, false);
855
 
  bitmap_init(&map3_obj, map3buf, bitsize, false);
 
868
  bitmap_init(&map2_obj, map2buf, bitsize, FALSE);
 
869
  bitmap_init(&map3_obj, map3buf, bitsize, FALSE);
856
870
  bitmap_clear_all(map2);
857
871
  bitmap_clear_all(map3);
858
872
  for (i=0; i < no_loops; i++)
926
940
    bitmap_clear_all(map);
927
941
    bitmap_clear_all(map3);
928
942
  }
929
 
  return false;
 
943
  return FALSE;
930
944
error1:
931
945
  printf("intersect error  bitsize=%u,size1=%u,size2=%u", bitsize,
932
946
  test_bit1,test_bit2);
933
 
  return true;
 
947
  return TRUE;
934
948
error2:
935
949
  printf("union error  bitsize=%u,size1=%u,size2=%u", bitsize,
936
950
  test_bit1,test_bit2);
937
 
  return true;
 
951
  return TRUE;
938
952
error3:
939
953
  printf("xor error  bitsize=%u,size1=%u,size2=%u", bitsize,
940
954
  test_bit1,test_bit2);
941
 
  return true;
 
955
  return TRUE;
942
956
error4:
943
957
  printf("subtract error  bitsize=%u,size1=%u,size2=%u", bitsize,
944
958
  test_bit1,test_bit2);
945
 
  return true;
 
959
  return TRUE;
946
960
error5:
947
961
  printf("invert error  bitsize=%u,size=%u", bitsize,
948
962
  test_bit1);
949
 
  return true;
 
963
  return TRUE;
950
964
}
951
965
 
952
 
bool test_count_bits_set(MY_BITMAP *map, uint32_t bitsize)
 
966
bool test_count_bits_set(MY_BITMAP *map, uint bitsize)
953
967
{
954
 
  uint32_t i, bit_count=0, test_bit;
955
 
  uint32_t no_loops= bitsize > 128 ? 128 : bitsize;
 
968
  uint i, bit_count=0, test_bit;
 
969
  uint no_loops= bitsize > 128 ? 128 : bitsize;
956
970
  for (i=0; i < no_loops; i++)
957
971
  {
958
972
    test_bit=get_rand_bit(bitsize);
966
980
    goto error1;
967
981
  if (bitmap_bits_set(map) != bit_count)
968
982
    goto error2;
969
 
  return false;
 
983
  return FALSE;
970
984
error1:
971
985
  printf("No bits set  bitsize = %u", bitsize);
972
 
  return true;
 
986
  return TRUE;
973
987
error2:
974
988
  printf("Wrong count of bits set, bitsize = %u", bitsize);
975
 
  return true;
 
989
  return TRUE;
976
990
}
977
991
 
978
 
bool test_get_first_bit(MY_BITMAP *map, uint32_t bitsize)
 
992
bool test_get_first_bit(MY_BITMAP *map, uint bitsize)
979
993
{
980
 
  uint32_t i, test_bit;
981
 
  uint32_t no_loops= bitsize > 128 ? 128 : bitsize;
 
994
  uint i, test_bit;
 
995
  uint no_loops= bitsize > 128 ? 128 : bitsize;
982
996
  for (i=0; i < no_loops; i++)
983
997
  {
984
998
    test_bit=get_rand_bit(bitsize);
991
1005
      goto error2;
992
1006
    bitmap_clear_all(map);
993
1007
  }
994
 
  return false;
 
1008
  return FALSE;
995
1009
error1:
996
1010
  printf("get_first_set error bitsize=%u,prefix_size=%u",bitsize,test_bit);
997
 
  return true;
 
1011
  return TRUE;
998
1012
error2:
999
1013
  printf("get_first error bitsize= %u, prefix_size= %u",bitsize,test_bit);
1000
 
  return true;
 
1014
  return TRUE;
1001
1015
}
1002
1016
 
1003
 
bool test_get_next_bit(MY_BITMAP *map, uint32_t bitsize)
 
1017
bool test_get_next_bit(MY_BITMAP *map, uint bitsize)
1004
1018
{
1005
 
  uint32_t i, j, test_bit;
1006
 
  uint32_t no_loops= bitsize > 128 ? 128 : bitsize;
 
1019
  uint i, j, test_bit;
 
1020
  uint no_loops= bitsize > 128 ? 128 : bitsize;
1007
1021
  for (i=0; i < no_loops; i++)
1008
1022
  {
1009
1023
    test_bit=get_rand_bit(bitsize);
1013
1027
      goto error1;
1014
1028
    bitmap_clear_all(map);
1015
1029
  }
1016
 
  return false;
 
1030
  return FALSE;
1017
1031
error1:
1018
1032
  printf("get_next error  bitsize= %u, prefix_size= %u", bitsize,test_bit);
1019
 
  return true;
 
1033
  return TRUE;
1020
1034
}
1021
1035
 
1022
 
bool test_prefix(MY_BITMAP *map, uint32_t bitsize)
 
1036
bool test_prefix(MY_BITMAP *map, uint bitsize)
1023
1037
{
1024
 
  uint32_t i, j, test_bit;
1025
 
  uint32_t no_loops= bitsize > 128 ? 128 : bitsize;
 
1038
  uint i, j, test_bit;
 
1039
  uint no_loops= bitsize > 128 ? 128 : bitsize;
1026
1040
  for (i=0; i < no_loops; i++)
1027
1041
  {
1028
1042
    test_bit=get_rand_bit(bitsize);
1041
1055
      goto error3;
1042
1056
    bitmap_clear_all(map);
1043
1057
  }
1044
 
  return false;
 
1058
  return FALSE;
1045
1059
error1:
1046
1060
  printf("prefix1 error  bitsize = %u, prefix_size = %u", bitsize,test_bit);
1047
 
  return true;
 
1061
  return TRUE;
1048
1062
error2:
1049
1063
  printf("prefix2 error  bitsize = %u, prefix_size = %u", bitsize,test_bit);
1050
 
  return true;
 
1064
  return TRUE;
1051
1065
error3:
1052
1066
  printf("prefix3 error  bitsize = %u, prefix_size = %u", bitsize,test_bit);
1053
 
  return true;
 
1067
  return TRUE;
1054
1068
}
1055
1069
 
1056
1070
 
1057
 
bool do_test(uint32_t bitsize)
 
1071
bool do_test(uint bitsize)
1058
1072
{
1059
1073
  MY_BITMAP map;
1060
1074
  my_bitmap_map buf[1024];
1061
 
  if (bitmap_init(&map, buf, bitsize, false))
 
1075
  if (bitmap_init(&map, buf, bitsize, FALSE))
1062
1076
  {
1063
1077
    printf("init error for bitsize %d", bitsize);
1064
1078
    goto error;
1088
1102
    goto error;
1089
1103
  if (test_prefix(&map,bitsize))
1090
1104
    goto error;
1091
 
  return false;
 
1105
  return FALSE;
1092
1106
error:
1093
1107
  printf("\n");
1094
 
  return true;
 
1108
  return TRUE;
1095
1109
}
1096
1110
 
1097
1111
int main()