← Back to branch summary

~drizzle-trunk/drizzle/development

« back to all changes in this revision

Viewing changes to mysys/my_bitmap.c

  • Committer: Jay Pipes
  • Date: 2008-07-17 17:54:00 UTC
  • mto: This revision was merged to the branch mainline in revision 182.
  • Revision ID: jay@mysql.com-20080717175400-xm2aazihjra8mdzq
Removal of DBUG from libdrizzle/ - Round 2

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