← Back to branch summary

~stewart/drizzle/embedded-innodb-create-select-transaction-arrgh

« back to all changes in this revision

Viewing changes to mysys/my_bitmap.c

  • Committer: brian
  • Date: 2008-06-25 05:29:13 UTC
  • Revision ID: brian@localhost.localdomain-20080625052913-6upwo0jsrl4lnapl
clean slate

Show diffs side-by-side

added added

removed removed

Lines of Context:
mysys/my_bitmap.c
 
1
/* Copyright (C) 2000 MySQL AB
 
2
 
 
3
   This program is free software; you can redistribute it and/or modify
 
4
   it under the terms of the GNU General Public License as published by
 
5
   the Free Software Foundation; version 2 of the License.
 
6
 
 
7
   This program is distributed in the hope that it will be useful,
 
8
   but WITHOUT ANY WARRANTY; without even the implied warranty of
 
9
   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 
10
   GNU General Public License for more details.
 
11
 
 
12
   You should have received a copy of the GNU General Public License
 
13
   along with this program; if not, write to the Free Software
 
14
   Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA */
 
15
 
 
16
/*
 
17
  Handling of uchar arrays as large bitmaps.
 
18
 
 
19
  API limitations (or, rather asserted safety assumptions,
 
20
  to encourage correct programming)
 
21
 
 
22
    * the internal size is a set of 32 bit words
 
23
    * the number of bits specified in creation can be any number > 0
 
24
    * there are THREAD safe versions of most calls called bitmap_lock_*
 
25
      many of those are not used and not compiled normally but the code
 
26
      already exist for them in an #ifdef:ed part. These can only be used
 
27
      if THREAD was specified in bitmap_init
 
28
 
 
29
  TODO:
 
30
  Make assembler THREAD safe versions of these using test-and-set instructions
 
31
 
 
32
  Original version created by Sergei Golubchik 2001 - 2004.
 
33
  New version written and test program added and some changes to the interface
 
34
  was made by Mikael Ronström 2005, with assistance of Tomas Ulin and Mats
 
35
  Kindahl.
 
36
*/
 
37
 
 
38
#include "mysys_priv.h"
 
39
#include <my_bitmap.h>
 
40
#include <m_string.h>
 
41
#include <my_bit.h>
 
42
 
 
43
void create_last_word_mask(MY_BITMAP *map)
 
44
{
 
45
  /* Get the number of used bits (1..8) in the last byte */
 
46
  unsigned int const used= 1U + ((map->n_bits-1U) & 0x7U);
 
47
 
 
48
  /*
 
49
    Create a mask with the upper 'unused' bits set and the lower 'used'
 
50
    bits clear. The bits within each byte is stored in big-endian order.
 
51
   */
 
52
  unsigned char const mask= (~((1 << used) - 1)) & 255;
 
53
 
 
54
  /*
 
55
    The first bytes are to be set to zero since they represent real  bits
 
56
    in the bitvector. The last bytes are set to 0xFF since they  represent
 
57
    bytes not used by the bitvector. Finally the last byte contains  bits
 
58
    as set by the mask above.
 
59
  */
 
60
  unsigned char *ptr= (unsigned char*)&map->last_word_mask;
 
61
 
 
62
  map->last_word_ptr= map->bitmap + no_words_in_map(map)-1;
 
63
  switch (no_bytes_in_map(map) & 3) {
 
64
  case 1:
 
65
    map->last_word_mask= ~0U;
 
66
    ptr[0]= mask;
 
67
    return;
 
68
  case 2:
 
69
    map->last_word_mask= ~0U;
 
70
    ptr[0]= 0;
 
71
    ptr[1]= mask;
 
72
    return;
 
73
  case 3:
 
74
    map->last_word_mask= 0U;
 
75
    ptr[2]= mask;
 
76
    ptr[3]= 0xFFU;
 
77
    return;
 
78
  case 0:
 
79
    map->last_word_mask= 0U;
 
80
    ptr[3]= mask;
 
81
    return;
 
82
  }
 
83
}
 
84
 
 
85
 
 
86
static inline void bitmap_lock(MY_BITMAP *map __attribute__((unused)))
 
87
{
 
88
#ifdef THREAD
 
89
  if (map->mutex)
 
90
    pthread_mutex_lock(map->mutex);
 
91
#endif
 
92
}
 
93
 
 
94
static inline void bitmap_unlock(MY_BITMAP *map __attribute__((unused)))
 
95
{
 
96
#ifdef THREAD
 
97
  if (map->mutex)
 
98
    pthread_mutex_unlock(map->mutex);
 
99
#endif
 
100
}
 
101
 
 
102
 
 
103
my_bool bitmap_init(MY_BITMAP *map, my_bitmap_map *buf, uint n_bits,
 
104
                    my_bool thread_safe __attribute__((unused)))
 
105
{
 
106
  DBUG_ENTER("bitmap_init");
 
107
  if (!buf)
 
108
  {
 
109
    uint size_in_bytes= bitmap_buffer_size(n_bits);
 
110
    uint extra= 0;
 
111
#ifdef THREAD
 
112
    if (thread_safe)
 
113
    {
 
114
      size_in_bytes= ALIGN_SIZE(size_in_bytes);
 
115
      extra= sizeof(pthread_mutex_t);
 
116
    }
 
117
    map->mutex= 0;
 
118
#endif
 
119
    if (!(buf= (my_bitmap_map*) my_malloc(size_in_bytes+extra, MYF(MY_WME))))
 
120
      DBUG_RETURN(1);
 
121
#ifdef THREAD
 
122
    if (thread_safe)
 
123
    {
 
124
      map->mutex= (pthread_mutex_t *) ((char*) buf + size_in_bytes);
 
125
      pthread_mutex_init(map->mutex, MY_MUTEX_INIT_FAST);
 
126
    }
 
127
#endif
 
128
  }
 
129
#ifdef THREAD
 
130
  else
 
131
  {
 
132
    DBUG_ASSERT(thread_safe == 0);
 
133
  }
 
134
#endif
 
135
 
 
136
  map->bitmap= buf;
 
137
  map->n_bits= n_bits;
 
138
  create_last_word_mask(map);
 
139
  bitmap_clear_all(map);
 
140
  DBUG_RETURN(0);
 
141
}
 
142
 
 
143
 
 
144
void bitmap_free(MY_BITMAP *map)
 
145
{
 
146
  DBUG_ENTER("bitmap_free");
 
147
  if (map->bitmap)
 
148
  {
 
149
#ifdef THREAD
 
150
    if (map->mutex)
 
151
      pthread_mutex_destroy(map->mutex);
 
152
#endif
 
153
    my_free((char*) map->bitmap, MYF(0));
 
154
    map->bitmap=0;
 
155
  }
 
156
  DBUG_VOID_RETURN;
 
157
}
 
158
 
 
159
 
 
160
/*
 
161
  test if bit already set and set it if it was not (thread unsafe method)
 
162
 
 
163
  SYNOPSIS
 
164
    bitmap_fast_test_and_set()
 
165
    MAP   bit map struct
 
166
    BIT   bit number
 
167
 
 
168
  RETURN
 
169
    0    bit was not set
 
170
    !=0  bit was set
 
171
*/
 
172
 
 
173
my_bool bitmap_fast_test_and_set(MY_BITMAP *map, uint bitmap_bit)
 
174
{
 
175
  uchar *value= ((uchar*) map->bitmap) + (bitmap_bit / 8);
 
176
  uchar bit= 1 << ((bitmap_bit) & 7);
 
177
  uchar res= (*value) & bit;
 
178
  *value|= bit;
 
179
  return res;
 
180
}
 
181
 
 
182
 
 
183
/*
 
184
  test if bit already set and set it if it was not (thread safe method)
 
185
 
 
186
  SYNOPSIS
 
187
    bitmap_fast_test_and_set()
 
188
    map          bit map struct
 
189
    bitmap_bit   bit number
 
190
 
 
191
  RETURN
 
192
    0    bit was not set
 
193
    !=0  bit was set
 
194
*/
 
195
 
 
196
my_bool bitmap_test_and_set(MY_BITMAP *map, uint bitmap_bit)
 
197
{
 
198
  my_bool res;
 
199
  DBUG_ASSERT(map->bitmap && bitmap_bit < map->n_bits);
 
200
  bitmap_lock(map);
 
201
  res= bitmap_fast_test_and_set(map, bitmap_bit);
 
202
  bitmap_unlock(map);
 
203
  return res;
 
204
}
 
205
 
 
206
/*
 
207
  test if bit already set and clear it if it was set(thread unsafe method)
 
208
 
 
209
  SYNOPSIS
 
210
    bitmap_fast_test_and_set()
 
211
    MAP   bit map struct
 
212
    BIT   bit number
 
213
 
 
214
  RETURN
 
215
    0    bit was not set
 
216
    !=0  bit was set
 
217
*/
 
218
 
 
219
my_bool bitmap_fast_test_and_clear(MY_BITMAP *map, uint bitmap_bit)
 
220
{
 
221
  uchar *byte= (uchar*) map->bitmap + (bitmap_bit / 8);
 
222
  uchar bit= 1 << ((bitmap_bit) & 7);
 
223
  uchar res= (*byte) & bit;
 
224
  *byte&= ~bit;
 
225
  return res;
 
226
}
 
227
 
 
228
 
 
229
my_bool bitmap_test_and_clear(MY_BITMAP *map, uint bitmap_bit)
 
230
{
 
231
  my_bool res;
 
232
  DBUG_ASSERT(map->bitmap && bitmap_bit < map->n_bits);
 
233
  bitmap_lock(map);
 
234
  res= bitmap_fast_test_and_clear(map, bitmap_bit);
 
235
  bitmap_unlock(map);
 
236
  return res;
 
237
}
 
238
 
 
239
 
 
240
uint bitmap_set_next(MY_BITMAP *map)
 
241
{
 
242
  uint bit_found;
 
243
  DBUG_ASSERT(map->bitmap);
 
244
  if ((bit_found= bitmap_get_first(map)) != MY_BIT_NONE)
 
245
    bitmap_set_bit(map, bit_found);
 
246
  return bit_found;
 
247
}
 
248
 
 
249
 
 
250
void bitmap_set_prefix(MY_BITMAP *map, uint prefix_size)
 
251
{
 
252
  uint prefix_bytes, prefix_bits, d;
 
253
  uchar *m= (uchar *)map->bitmap;
 
254
 
 
255
  DBUG_ASSERT(map->bitmap &&
 
256
              (prefix_size <= map->n_bits || prefix_size == (uint) ~0));
 
257
  set_if_smaller(prefix_size, map->n_bits);
 
258
  if ((prefix_bytes= prefix_size / 8))
 
259
    memset(m, 0xff, prefix_bytes);
 
260
  m+= prefix_bytes;
 
261
  if ((prefix_bits= prefix_size & 7))
 
262
    *m++= (1 << prefix_bits)-1;
 
263
  if ((d= no_bytes_in_map(map)-prefix_bytes))
 
264
    bzero(m, d);
 
265
}
 
266
 
 
267
 
 
268
my_bool bitmap_is_prefix(const MY_BITMAP *map, uint prefix_size)
 
269
{
 
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);
 
275
  end= m+no_bytes_in_map(map);
 
276
 
 
277
  while (m < end_prefix)
 
278
    if (*m++ != 0xff)
 
279
      return 0;
 
280
 
 
281
  *map->last_word_ptr&= ~map->last_word_mask; /*Clear bits*/
 
282
  res= 0;
 
283
  if (prefix_bits && *m++ != (1 << prefix_bits)-1)
 
284
    goto ret;
 
285
 
 
286
  while (m < end)
 
287
    if (*m++ != 0)
 
288
      goto ret;
 
289
  res= 1;
 
290
ret:
 
291
  return res; 
 
292
}
 
293
 
 
294
 
 
295
my_bool bitmap_is_set_all(const MY_BITMAP *map)
 
296
{
 
297
  my_bitmap_map *data_ptr= map->bitmap;
 
298
  my_bitmap_map *end= map->last_word_ptr;
 
299
  *map->last_word_ptr |= map->last_word_mask;
 
300
  for (; data_ptr <= end; data_ptr++)
 
301
    if (*data_ptr != 0xFFFFFFFF)
 
302
      return FALSE;
 
303
  return TRUE;
 
304
}
 
305
 
 
306
 
 
307
my_bool bitmap_is_clear_all(const MY_BITMAP *map)
 
308
{
 
309
  my_bitmap_map *data_ptr= map->bitmap;
 
310
  my_bitmap_map *end;
 
311
  if (*map->last_word_ptr & ~map->last_word_mask)
 
312
    return FALSE;
 
313
  end= map->last_word_ptr;
 
314
  for (; data_ptr < end; data_ptr++)
 
315
    if (*data_ptr)
 
316
      return FALSE;
 
317
  return TRUE;
 
318
}
 
319
 
 
320
/* Return TRUE if map1 is a subset of map2 */
 
321
 
 
322
my_bool bitmap_is_subset(const MY_BITMAP *map1, const MY_BITMAP *map2)
 
323
{
 
324
  my_bitmap_map *m1= map1->bitmap, *m2= map2->bitmap, *end;
 
325
 
 
326
  DBUG_ASSERT(map1->bitmap && map2->bitmap &&
 
327
              map1->n_bits==map2->n_bits);
 
328
 
 
329
  end= map1->last_word_ptr;
 
330
  *map1->last_word_ptr &= ~map1->last_word_mask;
 
331
  *map2->last_word_ptr &= ~map2->last_word_mask;
 
332
  while (m1 <= end)
 
333
  {
 
334
    if ((*m1++) & ~(*m2++))
 
335
      return 0;
 
336
  }
 
337
  return 1;
 
338
}
 
339
 
 
340
/* True if bitmaps has any common bits */
 
341
 
 
342
my_bool bitmap_is_overlapping(const MY_BITMAP *map1, const MY_BITMAP *map2)
 
343
{
 
344
  my_bitmap_map *m1= map1->bitmap, *m2= map2->bitmap, *end;
 
345
 
 
346
  DBUG_ASSERT(map1->bitmap && map2->bitmap &&
 
347
              map1->n_bits==map2->n_bits);
 
348
 
 
349
  end= map1->last_word_ptr;
 
350
  *map1->last_word_ptr &= ~map1->last_word_mask;
 
351
  *map2->last_word_ptr &= ~map2->last_word_mask;
 
352
  while (m1 <= end)
 
353
  {
 
354
    if ((*m1++) & (*m2++))
 
355
      return 1;
 
356
  }
 
357
  return 0;
 
358
}
 
359
 
 
360
 
 
361
void bitmap_intersect(MY_BITMAP *map, const MY_BITMAP *map2)
 
362
{
 
363
  my_bitmap_map *to= map->bitmap, *from= map2->bitmap, *end;
 
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);
 
369
  *map2->last_word_ptr&= ~map2->last_word_mask; /*Clear last bits in map2*/
 
370
  while (to < end)
 
371
    *to++ &= *from++;
 
372
 
 
373
  if (len2 < len)
 
374
  {
 
375
    end+=len-len2;
 
376
    while (to < end)
 
377
      *to++=0;
 
378
  }
 
379
}
 
380
 
 
381
 
 
382
/*
 
383
  Set/clear all bits above a bit.
 
384
 
 
385
  SYNOPSIS
 
386
    bitmap_set_above()
 
387
    map                  RETURN The bitmap to change.
 
388
    from_byte                   The bitmap buffer byte offset to start with.
 
389
    use_bit                     The bit value (1/0) to use for all upper bits.
 
390
 
 
391
  NOTE
 
392
    You can only set/clear full bytes.
 
393
    The function is meant for the situation that you copy a smaller bitmap
 
394
    to a bigger bitmap. Bitmap lengths are always multiple of eigth (the
 
395
    size of a byte). Using 'from_byte' saves multiplication and division
 
396
    by eight during parameter passing.
 
397
 
 
398
  RETURN
 
399
    void
 
400
*/
 
401
 
 
402
void bitmap_set_above(MY_BITMAP *map, uint from_byte, uint use_bit)
 
403
{
 
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;
 
407
 
 
408
  while (to < end)
 
409
    *to++= use_byte;
 
410
}
 
411
 
 
412
 
 
413
void bitmap_subtract(MY_BITMAP *map, const MY_BITMAP *map2)
 
414
{
 
415
  my_bitmap_map *to= map->bitmap, *from= map2->bitmap, *end;
 
416
  DBUG_ASSERT(map->bitmap && map2->bitmap &&
 
417
              map->n_bits==map2->n_bits);
 
418
 
 
419
  end= map->last_word_ptr;
 
420
 
 
421
  while (to <= end)
 
422
    *to++ &= ~(*from++);
 
423
}
 
424
 
 
425
 
 
426
void bitmap_union(MY_BITMAP *map, const MY_BITMAP *map2)
 
427
{
 
428
  my_bitmap_map *to= map->bitmap, *from= map2->bitmap, *end;
 
429
 
 
430
  DBUG_ASSERT(map->bitmap && map2->bitmap &&
 
431
              map->n_bits==map2->n_bits);
 
432
  end= map->last_word_ptr;
 
433
 
 
434
  while (to <= end)
 
435
    *to++ |= *from++;
 
436
}
 
437
 
 
438
 
 
439
void bitmap_xor(MY_BITMAP *map, const MY_BITMAP *map2)
 
440
{
 
441
  my_bitmap_map *to= map->bitmap, *from= map2->bitmap, *end= map->last_word_ptr;
 
442
  DBUG_ASSERT(map->bitmap && map2->bitmap &&
 
443
              map->n_bits==map2->n_bits);
 
444
  while (to <= end)
 
445
    *to++ ^= *from++;
 
446
}
 
447
 
 
448
 
 
449
void bitmap_invert(MY_BITMAP *map)
 
450
{
 
451
  my_bitmap_map *to= map->bitmap, *end;
 
452
 
 
453
  DBUG_ASSERT(map->bitmap);
 
454
  end= map->last_word_ptr;
 
455
 
 
456
  while (to <= end)
 
457
    *to++ ^= 0xFFFFFFFF;
 
458
}
 
459
 
 
460
 
 
461
uint bitmap_bits_set(const MY_BITMAP *map)
 
462
{  
 
463
  uchar *m= (uchar*)map->bitmap;
 
464
  uchar *end= m + no_bytes_in_map(map);
 
465
  uint res= 0;
 
466
 
 
467
  DBUG_ASSERT(map->bitmap);
 
468
  *map->last_word_ptr&= ~map->last_word_mask; /*Reset last bits to zero*/
 
469
  while (m < end)
 
470
    res+= my_count_bits_ushort(*m++);
 
471
  return res;
 
472
}
 
473
 
 
474
 
 
475
void bitmap_copy(MY_BITMAP *map, const MY_BITMAP *map2)
 
476
{
 
477
  my_bitmap_map *to= map->bitmap, *from= map2->bitmap, *end;
 
478
 
 
479
  DBUG_ASSERT(map->bitmap && map2->bitmap &&
 
480
              map->n_bits==map2->n_bits);
 
481
  end= map->last_word_ptr;
 
482
  while (to <= end)
 
483
    *to++ = *from++;
 
484
}
 
485
 
 
486
 
 
487
uint bitmap_get_first_set(const MY_BITMAP *map)
 
488
{
 
489
  uchar *byte_ptr;
 
490
  uint i,j,k;
 
491
  my_bitmap_map *data_ptr, *end= map->last_word_ptr;
 
492
 
 
493
  DBUG_ASSERT(map->bitmap);
 
494
  data_ptr= map->bitmap;
 
495
  *map->last_word_ptr &= ~map->last_word_mask;
 
496
 
 
497
  for (i=0; data_ptr <= end; data_ptr++, i++)
 
498
  {
 
499
    if (*data_ptr)
 
500
    {
 
501
      byte_ptr= (uchar*)data_ptr;
 
502
      for (j=0; ; j++, byte_ptr++)
 
503
      {
 
504
        if (*byte_ptr)
 
505
        {
 
506
          for (k=0; ; k++)
 
507
          {
 
508
            if (*byte_ptr & (1 << k))
 
509
              return (i*32) + (j*8) + k;
 
510
          }
 
511
          DBUG_ASSERT(0);
 
512
        }
 
513
      }
 
514
      DBUG_ASSERT(0);
 
515
    }
 
516
  }
 
517
  return MY_BIT_NONE;
 
518
}
 
519
 
 
520
 
 
521
uint bitmap_get_first(const MY_BITMAP *map)
 
522
{
 
523
  uchar *byte_ptr;
 
524
  uint i,j,k;
 
525
  my_bitmap_map *data_ptr, *end= map->last_word_ptr;
 
526
 
 
527
  DBUG_ASSERT(map->bitmap);
 
528
  data_ptr= map->bitmap;
 
529
  *map->last_word_ptr|= map->last_word_mask;
 
530
 
 
531
  for (i=0; data_ptr <= end; data_ptr++, i++)
 
532
  {
 
533
    if (*data_ptr != 0xFFFFFFFF)
 
534
    {
 
535
      byte_ptr= (uchar*)data_ptr;
 
536
      for (j=0; ; j++, byte_ptr++)
 
537
      { 
 
538
        if (*byte_ptr != 0xFF)
 
539
        {
 
540
          for (k=0; ; k++)
 
541
          {
 
542
            if (!(*byte_ptr & (1 << k)))
 
543
              return (i*32) + (j*8) + k;
 
544
          }
 
545
          DBUG_ASSERT(0);
 
546
        }
 
547
      }
 
548
      DBUG_ASSERT(0);
 
549
    }
 
550
  }
 
551
  return MY_BIT_NONE;
 
552
}
 
553
 
 
554
 
 
555
uint bitmap_lock_set_next(MY_BITMAP *map)
 
556
{
 
557
  uint bit_found;
 
558
  bitmap_lock(map);
 
559
  bit_found= bitmap_set_next(map);
 
560
  bitmap_unlock(map);
 
561
  return bit_found;
 
562
}
 
563
 
 
564
 
 
565
void bitmap_lock_clear_bit(MY_BITMAP *map, uint bitmap_bit)
 
566
{
 
567
  bitmap_lock(map);
 
568
  DBUG_ASSERT(map->bitmap && bitmap_bit < map->n_bits);
 
569
  bitmap_clear_bit(map, bitmap_bit);
 
570
  bitmap_unlock(map);
 
571
}
 
572
 
 
573
 
 
574
#ifdef NOT_USED
 
575
my_bool bitmap_lock_is_prefix(const MY_BITMAP *map, uint prefix_size)
 
576
{
 
577
  my_bool res;
 
578
  bitmap_lock((MY_BITMAP *)map);
 
579
  res= bitmap_is_prefix(map, prefix_size);
 
580
  bitmap_unlock((MY_BITMAP *)map);
 
581
  return res;
 
582
}
 
583
 
 
584
 
 
585
void bitmap_lock_set_all(MY_BITMAP *map)
 
586
{
 
587
  bitmap_lock(map);
 
588
  bitmap_set_all(map);
 
589
  bitmap_unlock(map);
 
590
}
 
591
 
 
592
 
 
593
void bitmap_lock_clear_all(MY_BITMAP *map)
 
594
{
 
595
  bitmap_lock(map);
 
596
  bitmap_clear_all(map);
 
597
  bitmap_unlock(map);
 
598
}
 
599
 
 
600
 
 
601
void bitmap_lock_set_prefix(MY_BITMAP *map, uint prefix_size)
 
602
{
 
603
  bitmap_lock(map);
 
604
  bitmap_set_prefix(map, prefix_size);
 
605
  bitmap_unlock(map);
 
606
}
 
607
 
 
608
 
 
609
my_bool bitmap_lock_is_clear_all(const MY_BITMAP *map)
 
610
{
 
611
  uint res;
 
612
  bitmap_lock((MY_BITMAP *)map);
 
613
  res= bitmap_is_clear_all(map);
 
614
  bitmap_unlock((MY_BITMAP *)map);
 
615
  return res;
 
616
}
 
617
 
 
618
 
 
619
my_bool bitmap_lock_is_set_all(const MY_BITMAP *map)
 
620
{
 
621
  uint res;
 
622
  bitmap_lock((MY_BITMAP *)map);
 
623
  res= bitmap_is_set_all(map);
 
624
  bitmap_unlock((MY_BITMAP *)map);
 
625
  return res;
 
626
}
 
627
 
 
628
 
 
629
my_bool bitmap_lock_is_set(const MY_BITMAP *map, uint bitmap_bit)
 
630
{
 
631
  my_bool res;
 
632
  DBUG_ASSERT(map->bitmap && bitmap_bit < map->n_bits);
 
633
  bitmap_lock((MY_BITMAP *)map);
 
634
  res= bitmap_is_set(map, bitmap_bit);
 
635
  bitmap_unlock((MY_BITMAP *)map);
 
636
  return res;
 
637
}
 
638
 
 
639
 
 
640
my_bool bitmap_lock_is_subset(const MY_BITMAP *map1, const MY_BITMAP *map2)
 
641
{
 
642
  uint res;
 
643
  bitmap_lock((MY_BITMAP *)map1);
 
644
  bitmap_lock((MY_BITMAP *)map2);
 
645
  res= bitmap_is_subset(map1, map2);
 
646
  bitmap_unlock((MY_BITMAP *)map2);
 
647
  bitmap_unlock((MY_BITMAP *)map1);
 
648
  return res;
 
649
}
 
650
 
 
651
 
 
652
my_bool bitmap_lock_cmp(const MY_BITMAP *map1, const MY_BITMAP *map2)
 
653
{
 
654
  uint res;
 
655
 
 
656
  DBUG_ASSERT(map1->bitmap && map2->bitmap &&
 
657
              map1->n_bits==map2->n_bits);
 
658
  bitmap_lock((MY_BITMAP *)map1);
 
659
  bitmap_lock((MY_BITMAP *)map2);
 
660
  res= bitmap_cmp(map1, map2);
 
661
  bitmap_unlock((MY_BITMAP *)map2);
 
662
  bitmap_unlock((MY_BITMAP *)map1);
 
663
  return res;
 
664
}
 
665
 
 
666
 
 
667
void bitmap_lock_intersect(MY_BITMAP *map, const MY_BITMAP *map2)
 
668
{
 
669
  bitmap_lock(map);
 
670
  bitmap_lock((MY_BITMAP *)map2);
 
671
  bitmap_intersect(map, map2);
 
672
  bitmap_unlock((MY_BITMAP *)map2);
 
673
  bitmap_unlock(map);
 
674
}
 
675
 
 
676
 
 
677
void bitmap_lock_subtract(MY_BITMAP *map, const MY_BITMAP *map2)
 
678
{
 
679
  bitmap_lock(map);
 
680
  bitmap_lock((MY_BITMAP *)map2);
 
681
  bitmap_subtract(map, map2);
 
682
  bitmap_unlock((MY_BITMAP *)map2);
 
683
  bitmap_unlock(map);
 
684
}
 
685
 
 
686
 
 
687
void bitmap_lock_union(MY_BITMAP *map, const MY_BITMAP *map2)
 
688
{
 
689
  bitmap_lock(map);
 
690
  bitmap_lock((MY_BITMAP *)map2);
 
691
  bitmap_union(map, map2);
 
692
  bitmap_unlock((MY_BITMAP *)map2);
 
693
  bitmap_unlock(map);
 
694
}
 
695
 
 
696
 
 
697
/*
 
698
  SYNOPSIS
 
699
    bitmap_bits_set()
 
700
      map
 
701
  RETURN
 
702
    Number of set bits in the bitmap.
 
703
*/
 
704
uint bitmap_lock_bits_set(const MY_BITMAP *map)
 
705
{
 
706
  uint res;
 
707
  bitmap_lock((MY_BITMAP *)map);
 
708
  DBUG_ASSERT(map->bitmap);
 
709
  res= bitmap_bits_set(map);
 
710
  bitmap_unlock((MY_BITMAP *)map);
 
711
  return res;
 
712
}
 
713
 
 
714
 
 
715
/* 
 
716
  SYNOPSIS
 
717
    bitmap_get_first()
 
718
      map
 
719
  RETURN 
 
720
    Number of first unset bit in the bitmap or MY_BIT_NONE if all bits are set.
 
721
*/
 
722
uint bitmap_lock_get_first(const MY_BITMAP *map)
 
723
{
 
724
  uint res;
 
725
  bitmap_lock((MY_BITMAP*)map);
 
726
  res= bitmap_get_first(map);
 
727
  bitmap_unlock((MY_BITMAP*)map);
 
728
  return res;
 
729
}
 
730
 
 
731
 
 
732
uint bitmap_lock_get_first_set(const MY_BITMAP *map)
 
733
{
 
734
  uint res;
 
735
  bitmap_lock((MY_BITMAP*)map);
 
736
  res= bitmap_get_first_set(map);
 
737
  bitmap_unlock((MY_BITMAP*)map);
 
738
  return res;
 
739
}
 
740
 
 
741
 
 
742
void bitmap_lock_set_bit(MY_BITMAP *map, uint bitmap_bit)
 
743
{
 
744
  DBUG_ASSERT(map->bitmap && bitmap_bit < map->n_bits);
 
745
  bitmap_lock(map);
 
746
  bitmap_set_bit(map, bitmap_bit);
 
747
  bitmap_unlock(map);
 
748
}
 
749
 
 
750
 
 
751
void bitmap_lock_flip_bit(MY_BITMAP *map, uint bitmap_bit)
 
752
{
 
753
  DBUG_ASSERT(map->bitmap && bitmap_bit < map->n_bits);
 
754
  bitmap_lock(map);
 
755
  bitmap_flip_bit(map, bitmap_bit);
 
756
  bitmap_unlock(map);
 
757
}
 
758
#endif
 
759
#ifdef MAIN
 
760
 
 
761
uint get_rand_bit(uint bitsize)
 
762
{
 
763
  return (rand() % bitsize);
 
764
}
 
765
 
 
766
bool test_set_get_clear_bit(MY_BITMAP *map, uint bitsize)
 
767
{
 
768
  uint i, test_bit;
 
769
  uint no_loops= bitsize > 128 ? 128 : bitsize;
 
770
  for (i=0; i < no_loops; i++)
 
771
  {
 
772
    test_bit= get_rand_bit(bitsize);
 
773
    bitmap_set_bit(map, test_bit);
 
774
    if (!bitmap_is_set(map, test_bit))
 
775
      goto error1;
 
776
    bitmap_clear_bit(map, test_bit);
 
777
    if (bitmap_is_set(map, test_bit))
 
778
      goto error2;
 
779
  }
 
780
  return FALSE;
 
781
error1:
 
782
  printf("Error in set bit, bit %u, bitsize = %u", test_bit, bitsize);
 
783
  return TRUE;
 
784
error2:
 
785
  printf("Error in clear bit, bit %u, bitsize = %u", test_bit, bitsize);
 
786
  return TRUE;
 
787
}
 
788
 
 
789
bool test_flip_bit(MY_BITMAP *map, uint bitsize)
 
790
{
 
791
  uint i, test_bit;
 
792
  uint no_loops= bitsize > 128 ? 128 : bitsize;
 
793
  for (i=0; i < no_loops; i++)
 
794
  {
 
795
    test_bit= get_rand_bit(bitsize);
 
796
    bitmap_flip_bit(map, test_bit);
 
797
    if (!bitmap_is_set(map, test_bit))
 
798
      goto error1;
 
799
    bitmap_flip_bit(map, test_bit);
 
800
    if (bitmap_is_set(map, test_bit))
 
801
      goto error2;
 
802
  }
 
803
  return FALSE;
 
804
error1:
 
805
  printf("Error in flip bit 1, bit %u, bitsize = %u", test_bit, bitsize);
 
806
  return TRUE;
 
807
error2:
 
808
  printf("Error in flip bit 2, bit %u, bitsize = %u", test_bit, bitsize);
 
809
  return TRUE;
 
810
}
 
811
 
 
812
bool test_operators(MY_BITMAP *map __attribute__((unused)),
 
813
                    uint bitsize __attribute__((unused)))
 
814
{
 
815
  return FALSE;
 
816
}
 
817
 
 
818
bool test_get_all_bits(MY_BITMAP *map, uint bitsize)
 
819
{
 
820
  uint i;
 
821
  bitmap_set_all(map);
 
822
  if (!bitmap_is_set_all(map))
 
823
    goto error1;
 
824
  if (!bitmap_is_prefix(map, bitsize))
 
825
    goto error5;
 
826
  bitmap_clear_all(map);
 
827
  if (!bitmap_is_clear_all(map))
 
828
    goto error2;
 
829
  if (!bitmap_is_prefix(map, 0))
 
830
    goto error6;
 
831
  for (i=0; i<bitsize;i++)
 
832
    bitmap_set_bit(map, i);
 
833
  if (!bitmap_is_set_all(map))
 
834
    goto error3;
 
835
  for (i=0; i<bitsize;i++)
 
836
    bitmap_clear_bit(map, i);
 
837
  if (!bitmap_is_clear_all(map))
 
838
    goto error4;
 
839
  return FALSE;
 
840
error1:
 
841
  printf("Error in set_all, bitsize = %u", bitsize);
 
842
  return TRUE;
 
843
error2:
 
844
  printf("Error in clear_all, bitsize = %u", bitsize);
 
845
  return TRUE;
 
846
error3:
 
847
  printf("Error in bitmap_is_set_all, bitsize = %u", bitsize);
 
848
  return TRUE;
 
849
error4:
 
850
  printf("Error in bitmap_is_clear_all, bitsize = %u", bitsize);
 
851
  return TRUE;
 
852
error5:
 
853
  printf("Error in set_all through set_prefix, bitsize = %u", bitsize);
 
854
  return TRUE;
 
855
error6:
 
856
  printf("Error in clear_all through set_prefix, bitsize = %u", bitsize);
 
857
  return TRUE;
 
858
}
 
859
 
 
860
bool test_compare_operators(MY_BITMAP *map, uint bitsize)
 
861
{
 
862
  uint i, j, test_bit1, test_bit2, test_bit3,test_bit4;
 
863
  uint no_loops= bitsize > 128 ? 128 : bitsize;
 
864
  MY_BITMAP map2_obj, map3_obj;
 
865
  MY_BITMAP *map2= &map2_obj, *map3= &map3_obj;
 
866
  my_bitmap_map map2buf[1024];
 
867
  my_bitmap_map map3buf[1024];
 
868
  bitmap_init(&map2_obj, map2buf, bitsize, FALSE);
 
869
  bitmap_init(&map3_obj, map3buf, bitsize, FALSE);
 
870
  bitmap_clear_all(map2);
 
871
  bitmap_clear_all(map3);
 
872
  for (i=0; i < no_loops; i++)
 
873
  {
 
874
    test_bit1=get_rand_bit(bitsize);
 
875
    bitmap_set_prefix(map, test_bit1);
 
876
    test_bit2=get_rand_bit(bitsize);
 
877
    bitmap_set_prefix(map2, test_bit2);
 
878
    bitmap_intersect(map, map2);
 
879
    test_bit3= test_bit2 < test_bit1 ? test_bit2 : test_bit1;
 
880
    bitmap_set_prefix(map3, test_bit3);
 
881
    if (!bitmap_cmp(map, map3))
 
882
      goto error1;
 
883
    bitmap_clear_all(map);
 
884
    bitmap_clear_all(map2);
 
885
    bitmap_clear_all(map3);
 
886
    test_bit1=get_rand_bit(bitsize);
 
887
    test_bit2=get_rand_bit(bitsize);
 
888
    test_bit3=get_rand_bit(bitsize);
 
889
    bitmap_set_prefix(map, test_bit1);
 
890
    bitmap_set_prefix(map2, test_bit2);
 
891
    test_bit3= test_bit2 > test_bit1 ? test_bit2 : test_bit1;
 
892
    bitmap_set_prefix(map3, test_bit3);
 
893
    bitmap_union(map, map2);
 
894
    if (!bitmap_cmp(map, map3))
 
895
      goto error2;
 
896
    bitmap_clear_all(map);
 
897
    bitmap_clear_all(map2);
 
898
    bitmap_clear_all(map3);
 
899
    test_bit1=get_rand_bit(bitsize);
 
900
    test_bit2=get_rand_bit(bitsize);
 
901
    test_bit3=get_rand_bit(bitsize);
 
902
    bitmap_set_prefix(map, test_bit1);
 
903
    bitmap_set_prefix(map2, test_bit2);
 
904
    bitmap_xor(map, map2);
 
905
    test_bit3= test_bit2 > test_bit1 ? test_bit2 : test_bit1;
 
906
    test_bit4= test_bit2 < test_bit1 ? test_bit2 : test_bit1;
 
907
    bitmap_set_prefix(map3, test_bit3);
 
908
    for (j=0; j < test_bit4; j++)
 
909
      bitmap_clear_bit(map3, j);
 
910
    if (!bitmap_cmp(map, map3))
 
911
      goto error3;
 
912
    bitmap_clear_all(map);
 
913
    bitmap_clear_all(map2);
 
914
    bitmap_clear_all(map3);
 
915
    test_bit1=get_rand_bit(bitsize);
 
916
    test_bit2=get_rand_bit(bitsize);
 
917
    test_bit3=get_rand_bit(bitsize);
 
918
    bitmap_set_prefix(map, test_bit1);
 
919
    bitmap_set_prefix(map2, test_bit2);
 
920
    bitmap_subtract(map, map2);
 
921
    if (test_bit2 < test_bit1)
 
922
    {
 
923
      bitmap_set_prefix(map3, test_bit1);
 
924
      for (j=0; j < test_bit2; j++)
 
925
        bitmap_clear_bit(map3, j);
 
926
    }
 
927
    if (!bitmap_cmp(map, map3))
 
928
      goto error4;
 
929
    bitmap_clear_all(map);
 
930
    bitmap_clear_all(map2);
 
931
    bitmap_clear_all(map3);
 
932
    test_bit1=get_rand_bit(bitsize);
 
933
    bitmap_set_prefix(map, test_bit1);
 
934
    bitmap_invert(map);
 
935
    bitmap_set_all(map3);
 
936
    for (j=0; j < test_bit1; j++)
 
937
      bitmap_clear_bit(map3, j);
 
938
    if (!bitmap_cmp(map, map3))
 
939
      goto error5;
 
940
    bitmap_clear_all(map);
 
941
    bitmap_clear_all(map3);
 
942
  }
 
943
  return FALSE;
 
944
error1:
 
945
  printf("intersect error  bitsize=%u,size1=%u,size2=%u", bitsize,
 
946
  test_bit1,test_bit2);
 
947
  return TRUE;
 
948
error2:
 
949
  printf("union error  bitsize=%u,size1=%u,size2=%u", bitsize,
 
950
  test_bit1,test_bit2);
 
951
  return TRUE;
 
952
error3:
 
953
  printf("xor error  bitsize=%u,size1=%u,size2=%u", bitsize,
 
954
  test_bit1,test_bit2);
 
955
  return TRUE;
 
956
error4:
 
957
  printf("subtract error  bitsize=%u,size1=%u,size2=%u", bitsize,
 
958
  test_bit1,test_bit2);
 
959
  return TRUE;
 
960
error5:
 
961
  printf("invert error  bitsize=%u,size=%u", bitsize,
 
962
  test_bit1);
 
963
  return TRUE;
 
964
}
 
965
 
 
966
bool test_count_bits_set(MY_BITMAP *map, uint bitsize)
 
967
{
 
968
  uint i, bit_count=0, test_bit;
 
969
  uint no_loops= bitsize > 128 ? 128 : bitsize;
 
970
  for (i=0; i < no_loops; i++)
 
971
  {
 
972
    test_bit=get_rand_bit(bitsize);
 
973
    if (!bitmap_is_set(map, test_bit))
 
974
    {
 
975
      bitmap_set_bit(map, test_bit);
 
976
      bit_count++;
 
977
    }
 
978
  }
 
979
  if (bit_count==0 && bitsize > 0)
 
980
    goto error1;
 
981
  if (bitmap_bits_set(map) != bit_count)
 
982
    goto error2;
 
983
  return FALSE;
 
984
error1:
 
985
  printf("No bits set  bitsize = %u", bitsize);
 
986
  return TRUE;
 
987
error2:
 
988
  printf("Wrong count of bits set, bitsize = %u", bitsize);
 
989
  return TRUE;
 
990
}
 
991
 
 
992
bool test_get_first_bit(MY_BITMAP *map, uint bitsize)
 
993
{
 
994
  uint i, test_bit;
 
995
  uint no_loops= bitsize > 128 ? 128 : bitsize;
 
996
  for (i=0; i < no_loops; i++)
 
997
  {
 
998
    test_bit=get_rand_bit(bitsize);
 
999
    bitmap_set_bit(map, test_bit);
 
1000
    if (bitmap_get_first_set(map) != test_bit)
 
1001
      goto error1;
 
1002
    bitmap_set_all(map);
 
1003
    bitmap_clear_bit(map, test_bit);
 
1004
    if (bitmap_get_first(map) != test_bit)
 
1005
      goto error2;
 
1006
    bitmap_clear_all(map);
 
1007
  }
 
1008
  return FALSE;
 
1009
error1:
 
1010
  printf("get_first_set error bitsize=%u,prefix_size=%u",bitsize,test_bit);
 
1011
  return TRUE;
 
1012
error2:
 
1013
  printf("get_first error bitsize= %u, prefix_size= %u",bitsize,test_bit);
 
1014
  return TRUE;
 
1015
}
 
1016
 
 
1017
bool test_get_next_bit(MY_BITMAP *map, uint bitsize)
 
1018
{
 
1019
  uint i, j, test_bit;
 
1020
  uint no_loops= bitsize > 128 ? 128 : bitsize;
 
1021
  for (i=0; i < no_loops; i++)
 
1022
  {
 
1023
    test_bit=get_rand_bit(bitsize);
 
1024
    for (j=0; j < test_bit; j++)
 
1025
      bitmap_set_next(map);
 
1026
    if (!bitmap_is_prefix(map, test_bit))
 
1027
      goto error1;
 
1028
    bitmap_clear_all(map);
 
1029
  }
 
1030
  return FALSE;
 
1031
error1:
 
1032
  printf("get_next error  bitsize= %u, prefix_size= %u", bitsize,test_bit);
 
1033
  return TRUE;
 
1034
}
 
1035
 
 
1036
bool test_prefix(MY_BITMAP *map, uint bitsize)
 
1037
{
 
1038
  uint i, j, test_bit;
 
1039
  uint no_loops= bitsize > 128 ? 128 : bitsize;
 
1040
  for (i=0; i < no_loops; i++)
 
1041
  {
 
1042
    test_bit=get_rand_bit(bitsize);
 
1043
    bitmap_set_prefix(map, test_bit);
 
1044
    if (!bitmap_is_prefix(map, test_bit))
 
1045
      goto error1;
 
1046
    bitmap_clear_all(map);
 
1047
    for (j=0; j < test_bit; j++)
 
1048
      bitmap_set_bit(map, j);
 
1049
    if (!bitmap_is_prefix(map, test_bit))
 
1050
      goto error2;
 
1051
    bitmap_set_all(map);
 
1052
    for (j=bitsize - 1; ~(j-test_bit); j--)
 
1053
      bitmap_clear_bit(map, j);
 
1054
    if (!bitmap_is_prefix(map, test_bit))
 
1055
      goto error3;
 
1056
    bitmap_clear_all(map);
 
1057
  }
 
1058
  return FALSE;
 
1059
error1:
 
1060
  printf("prefix1 error  bitsize = %u, prefix_size = %u", bitsize,test_bit);
 
1061
  return TRUE;
 
1062
error2:
 
1063
  printf("prefix2 error  bitsize = %u, prefix_size = %u", bitsize,test_bit);
 
1064
  return TRUE;
 
1065
error3:
 
1066
  printf("prefix3 error  bitsize = %u, prefix_size = %u", bitsize,test_bit);
 
1067
  return TRUE;
 
1068
}
 
1069
 
 
1070
 
 
1071
bool do_test(uint bitsize)
 
1072
{
 
1073
  MY_BITMAP map;
 
1074
  my_bitmap_map buf[1024];
 
1075
  if (bitmap_init(&map, buf, bitsize, FALSE))
 
1076
  {
 
1077
    printf("init error for bitsize %d", bitsize);
 
1078
    goto error;
 
1079
  }
 
1080
  if (test_set_get_clear_bit(&map,bitsize))
 
1081
    goto error;
 
1082
  bitmap_clear_all(&map);
 
1083
  if (test_flip_bit(&map,bitsize))
 
1084
    goto error;
 
1085
  bitmap_clear_all(&map);
 
1086
  if (test_operators(&map,bitsize))
 
1087
    goto error;
 
1088
  bitmap_clear_all(&map);
 
1089
  if (test_get_all_bits(&map, bitsize))
 
1090
    goto error;
 
1091
  bitmap_clear_all(&map);
 
1092
  if (test_compare_operators(&map,bitsize))
 
1093
    goto error;
 
1094
  bitmap_clear_all(&map);
 
1095
  if (test_count_bits_set(&map,bitsize))
 
1096
    goto error;
 
1097
  bitmap_clear_all(&map);
 
1098
  if (test_get_first_bit(&map,bitsize))
 
1099
    goto error;
 
1100
  bitmap_clear_all(&map);
 
1101
  if (test_get_next_bit(&map,bitsize))
 
1102
    goto error;
 
1103
  if (test_prefix(&map,bitsize))
 
1104
    goto error;
 
1105
  return FALSE;
 
1106
error:
 
1107
  printf("\n");
 
1108
  return TRUE;
 
1109
}
 
1110
 
 
1111
int main()
 
1112
{
 
1113
  int i;
 
1114
  for (i= 1; i < 4096; i++)
 
1115
  {
 
1116
    printf("Start test for bitsize=%u\n",i);
 
1117
    if (do_test(i))
 
1118
      return -1;
 
1119
  }
 
1120
  printf("OK\n");
 
1121
  return 0;
 
1122
}
 
1123
 
 
1124
/*
 
1125
  In directory mysys:
 
1126
  make test_bitmap
 
1127
  will build the bitmap tests and ./test_bitmap will execute it
 
1128
*/
 
1129
 
 
1130
#endif