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