← 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: 2009-10-06 19:37:52 UTC
  • mto: This revision was merged to the branch mainline in revision 1184.
  • Revision ID: mordred@inaugust.com-20091006193752-4dx2c8u35j4em79g
Removed more server_includes.h from headers.

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= ~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
 
  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 == (uint) ~0));
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