← Back to branch summary

~drizzle-trunk/drizzle/development

« back to all changes in this revision

Viewing changes to mysys/my_bitmap.c

  • Committer: Monty Taylor
  • Date: 2008-09-16 00:00:48 UTC
  • mto: This revision was merged to the branch mainline in revision 391.
  • Revision ID: monty@inaugust.com-20080916000048-3rvrv3gv9l0ad3gs
Fixed copyright headers in drizzled/

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