« back to all changes in this revision
Viewing changes to mysys/my_bitmap.cc
- browse files at revision 1115.3.11
- compare with another revision
- download diff
- download tarball
- view history from revision 1115.3.11
- Committer: Jay Pipes
- Date: 2009-08-20 20:29:18 UTC
- mfrom: (1103.6.6 refactor-bitmap-class)
- mto: This revision was merged to the branch mainline in revision 1121.
- Revision ID: jpipes@serialcoder-20090820202918-39ey4uyvwh9z4ya5
Merge Padraig's refactoring of MY_BITMAP struct to a proper class interface.
- files modified:
- drizzled/filesort.cc
added
removed
mysys/my_bitmap.cc
13
13
along with this program; if not, write to the Free Software
14
14
Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA */
15
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
25
26
Original version created by Sergei Golubchik 2001 - 2004.
27
New version written and test program added and some changes to the interface
28
was made by Mikael Ronström 2005, with assistance of Tomas Ulin and Mats
29
Kindahl.
30
*/
31
32
16
#include "mysys_priv.h"
33
17
#include <mysys/my_bitmap.h>
34
18
#include <mystrings/m_string.h>
35
19
#include <mysys/my_bit.h>
36
20
37
#include <algorithm>
38
39
21
using namespace std;
40
22
41
void create_last_word_mask(MY_BITMAP *map)
23
void MyBitmap::createLastWordMask()
42
24
{
43
25
/* Get the number of used bits (1..8) in the last byte */
44
unsigned int const used= 1U + ((map->n_bits-1U) & 0x7U);
26
unsigned int const used= 1U + ((n_bits-1U) & 0x7U);
45
27
46
28
/*
47
29
Create a mask with the upper 'unused' bits set and the lower 'used'
55
37
bytes not used by the bitvector. Finally the last byte contains bits
56
38
as set by the mask above.
57
39
*/
58
unsigned char *ptr= (unsigned char*)&map->last_word_mask;
40
unsigned char *ptr= (unsigned char*)&last_word_mask;
59
41
60
map->last_word_ptr= map->bitmap + no_words_in_map(map)-1;
61
switch (no_bytes_in_map(map) & 3) {
42
last_word_ptr= bitmap + numOfWordsInMap()-1;
43
switch (numOfBytesInMap() & 3)
44
{
62
45
case 1:
63
map->last_word_mask= UINT32_MAX;
46
last_word_mask= UINT32_MAX;
64
47
ptr[0]= mask;
65
48
return;
66
49
case 2:
67
map->last_word_mask= UINT32_MAX;
50
last_word_mask= UINT32_MAX;
68
51
ptr[0]= 0;
69
52
ptr[1]= mask;
70
53
return;
71
54
case 3:
72
map->last_word_mask= 0;
55
last_word_mask= 0;
73
56
ptr[2]= mask;
74
57
ptr[3]= 0xFFU;
75
58
return;
76
59
case 0:
77
map->last_word_mask= 0U;
60
last_word_mask= 0U;
78
61
ptr[3]= mask;
79
62
return;
80
63
}
81
64
}
82
65
83
66
84
bool bitmap_init(MY_BITMAP *map, my_bitmap_map *buf, uint32_t n_bits)
85
{
86
if (!buf)
87
{
88
uint32_t size_in_bytes= bitmap_buffer_size(n_bits);
89
size_in_bytes= ALIGN_SIZE(size_in_bytes);
90
if (!(buf= (my_bitmap_map*) malloc(size_in_bytes)))
91
return(1);
92
}
93
94
map->bitmap= buf;
95
map->n_bits= n_bits;
96
create_last_word_mask(map);
97
bitmap_clear_all(map);
98
return(0);
99
}
100
101
102
void bitmap_free(MY_BITMAP *map)
103
{
104
if (map->bitmap)
105
{
106
free((char*) map->bitmap);
107
map->bitmap=0;
108
}
109
return;
110
}
111
112
113
/*
114
test if bit already set and set it if it was not
115
116
SYNOPSIS
117
bitmap_test_and_set()
118
MAP bit map struct
119
BIT bit number
120
121
RETURN
122
0 bit was not set
123
!=0 bit was set
124
*/
125
126
bool bitmap_test_and_set(MY_BITMAP *map, uint32_t bitmap_bit)
127
{
128
unsigned char *value= ((unsigned char*) map->bitmap) + (bitmap_bit / 8);
129
unsigned char bit= 1 << ((bitmap_bit) & 7);
67
bool MyBitmap::init(my_bitmap_map *buf, uint32_t num_bits)
68
{
69
if (! buf)
70
{
71
uint32_t size_in_bytes= bitmap_buffer_size(num_bits);
72
if (! (buf= new(std::nothrow) my_bitmap_map[size_in_bytes]()))
73
{
74
return true;
75
}
76
}
77
78
bitmap= buf;
79
n_bits= num_bits;
80
createLastWordMask();
81
clearAll();
82
83
return false;
84
}
85
86
87
bool MyBitmap::testAndSet(const uint32_t bitPos)
88
{
89
unsigned char *value= ((unsigned char*) bitmap) + (bitPos / 8);
90
unsigned char bit= 1 << ((bitPos) & 7);
130
91
unsigned char res= (*value) & bit;
131
92
*value|= bit;
132
93
return res;
134
95
135
96
136
97
137
/*
138
test if bit already set and clear it if it was set
139
140
SYNOPSIS
141
bitmap_test_and_set()
142
MAP bit map struct
143
BIT bit number
144
145
RETURN
146
0 bit was not set
147
!=0 bit was set
148
*/
149
150
bool bitmap_test_and_clear(MY_BITMAP *map, uint32_t bitmap_bit)
98
bool MyBitmap::testAndClear(const uint32_t bitPos)
151
99
{
152
unsigned char *byte= (unsigned char*) map->bitmap + (bitmap_bit / 8);
153
unsigned char bit= 1 << ((bitmap_bit) & 7);
100
unsigned char *byte= (unsigned char*) bitmap + (bitPos / 8);
101
unsigned char bit= 1 << ((bitPos) & 7);
154
102
unsigned char res= (*byte) & bit;
155
103
*byte&= ~bit;
156
104
return res;
158
106
159
107
160
108
161
uint32_t bitmap_set_next(MY_BITMAP *map)
109
uint32_t MyBitmap::setNext()
162
110
{
163
111
uint32_t bit_found;
164
assert(map->bitmap);
165
if ((bit_found= bitmap_get_first(map)) != MY_BIT_NONE)
166
bitmap_set_bit(map, bit_found);
112
assert(bitmap);
113
if ((bit_found= getFirst()) != MY_BIT_NONE)
114
{
115
setBit(bit_found);
116
}
167
117
return bit_found;
168
118
}
169
119
170
120
171
void bitmap_set_prefix(MY_BITMAP *map, uint32_t prefix_size)
121
void MyBitmap::setPrefix(uint32_t prefix_size)
172
122
{
173
123
uint32_t prefix_bytes, prefix_bits, d;
174
unsigned char *m= (unsigned char *)map->bitmap;
124
unsigned char *m= (unsigned char *) bitmap;
175
125
176
assert(map->bitmap &&
177
(prefix_size <= map->n_bits || prefix_size == UINT32_MAX));
178
set_if_smaller(prefix_size, map->n_bits);
126
assert(bitmap &&
127
(prefix_size <= n_bits || prefix_size == UINT32_MAX));
128
set_if_smaller(prefix_size, n_bits);
179
129
if ((prefix_bytes= prefix_size / 8))
130
{
180
131
memset(m, 0xff, prefix_bytes);
132
}
181
133
m+= prefix_bytes;
182
134
if ((prefix_bits= prefix_size & 7))
135
{
183
136
*m++= (1 << prefix_bits)-1;
184
if ((d= no_bytes_in_map(map)-prefix_bytes))
137
}
138
if ((d= numOfBytesInMap() - prefix_bytes))
139
{
185
140
memset(m, 0, d);
141
}
186
142
}
187
143
188
144
189
bool bitmap_is_prefix(const MY_BITMAP *map, uint32_t prefix_size)
145
bool MyBitmap::isPrefix(const uint32_t prefix_size) const
190
146
{
191
147
uint32_t prefix_bits= prefix_size & 0x7, res;
192
unsigned char *m= (unsigned char*)map->bitmap;
193
unsigned char *end_prefix= m+prefix_size/8;
148
unsigned char *m= (unsigned char*) bitmap;
149
unsigned char *end_prefix= m + prefix_size/8;
194
150
unsigned char *end;
195
assert(m && prefix_size <= map->n_bits);
196
end= m+no_bytes_in_map(map);
151
assert(m && prefix_size <= n_bits);
152
end= m + numOfBytesInMap();
197
153
198
154
while (m < end_prefix)
155
{
199
156
if (*m++ != 0xff)
157
{
200
158
return 0;
159
}
160
}
201
161
202
*map->last_word_ptr&= ~map->last_word_mask; /*Clear bits*/
162
*last_word_ptr&= ~last_word_mask; /*Clear bits*/
203
163
res= 0;
204
164
if (prefix_bits && *m++ != (1 << prefix_bits)-1)
165
{
205
166
goto ret;
167
}
206
168
207
169
while (m < end)
170
{
208
171
if (*m++ != 0)
172
{
209
173
goto ret;
174
}
175
}
210
176
res= 1;
211
177
ret:
212
178
return res;
213
179
}
214
180
215
181
216
bool bitmap_is_set_all(const MY_BITMAP *map)
182
bool MyBitmap::isSetAll() const
217
183
{
218
my_bitmap_map *data_ptr= map->bitmap;
219
my_bitmap_map *end= map->last_word_ptr;
220
*map->last_word_ptr |= map->last_word_mask;
184
my_bitmap_map *data_ptr= bitmap;
185
my_bitmap_map *end= last_word_ptr;
186
*last_word_ptr |= last_word_mask;
221
187
for (; data_ptr <= end; data_ptr++)
188
{
222
189
if (*data_ptr != 0xFFFFFFFF)
190
{
223
191
return false;
192
}
193
}
224
194
return true;
225
195
}
226
196
227
197
228
bool bitmap_is_clear_all(const MY_BITMAP *map)
198
bool MyBitmap::isClearAll() const
229
199
{
230
my_bitmap_map *data_ptr= map->bitmap;
200
my_bitmap_map *data_ptr= bitmap;
231
201
my_bitmap_map *end;
232
if (*map->last_word_ptr & ~map->last_word_mask)
202
if (*last_word_ptr & ~last_word_mask)
203
{
233
204
return false;
234
end= map->last_word_ptr;
205
}
206
end= last_word_ptr;
235
207
for (; data_ptr < end; data_ptr++)
208
{
236
209
if (*data_ptr)
210
{
237
211
return false;
212
}
213
}
238
214
return true;
239
215
}
240
216
241
217
/* Return true if map1 is a subset of map2 */
242
218
243
bool bitmap_is_subset(const MY_BITMAP *map1, const MY_BITMAP *map2)
219
bool bitmap_is_subset(const MyBitmap *map1, const MyBitmap *map2)
244
220
{
245
my_bitmap_map *m1= map1->bitmap, *m2= map2->bitmap, *end;
246
247
assert(map1->bitmap && map2->bitmap &&
248
map1->n_bits==map2->n_bits);
249
250
end= map1->last_word_ptr;
251
*map1->last_word_ptr &= ~map1->last_word_mask;
252
*map2->last_word_ptr &= ~map2->last_word_mask;
221
my_bitmap_map *m1= map1->getBitmap(), *m2= map2->getBitmap(), *end;
222
223
assert(map1->getBitmap() && map2->getBitmap() &&
224
map1->numOfBitsInMap() == map2->numOfBitsInMap());
225
226
end= map1->getLastWordPtr();
227
map1->subtractMaskFromLastWord();
228
map2->subtractMaskFromLastWord();
253
229
while (m1 <= end)
254
230
{
255
231
if ((*m1++) & ~(*m2++))
232
{
256
233
return 0;
234
}
257
235
}
258
236
return 1;
259
237
}
260
238
261
239
/* True if bitmaps has any common bits */
262
240
263
bool bitmap_is_overlapping(const MY_BITMAP *map1, const MY_BITMAP *map2)
241
bool bitmap_is_overlapping(const MyBitmap *map1, const MyBitmap *map2)
264
242
{
265
my_bitmap_map *m1= map1->bitmap, *m2= map2->bitmap, *end;
266
267
assert(map1->bitmap && map2->bitmap &&
268
map1->n_bits==map2->n_bits);
269
270
end= map1->last_word_ptr;
271
*map1->last_word_ptr &= ~map1->last_word_mask;
272
*map2->last_word_ptr &= ~map2->last_word_mask;
243
my_bitmap_map *m1= map1->getBitmap(), *m2= map2->getBitmap(), *end;
244
245
assert(map1->getBitmap() && map2->getBitmap() &&
246
map1->numOfBitsInMap() == map2->numOfBitsInMap());
247
248
end= map1->getLastWordPtr();
249
map1->subtractMaskFromLastWord();
250
map2->subtractMaskFromLastWord();
273
251
while (m1 <= end)
274
252
{
275
253
if ((*m1++) & (*m2++))
279
257
}
280
258
281
259
282
void bitmap_intersect(MY_BITMAP *map, const MY_BITMAP *map2)
260
void bitmap_intersect(MyBitmap *map, const MyBitmap *map2)
283
261
{
284
my_bitmap_map *to= map->bitmap, *from= map2->bitmap, *end;
285
uint32_t len= no_words_in_map(map), len2 = no_words_in_map(map2);
262
my_bitmap_map *to= map->getBitmap(), *from= map2->getBitmap(), *end;
263
uint32_t len= map->numOfWordsInMap(), len2 = map2->numOfWordsInMap();
286
264
287
assert(map->bitmap && map2->bitmap);
265
assert(map->getBitmap() && map2->getBitmap());
288
266
289
267
end= to+min(len,len2);
290
*map2->last_word_ptr&= ~map2->last_word_mask; /*Clear last bits in map2*/
268
map2->subtractMaskFromLastWord(); /* Clear last bits in map2 */
291
269
while (to < end)
270
{
292
271
*to++ &= *from++;
272
}
293
273
294
274
if (len2 < len)
295
275
{
296
276
end+=len-len2;
297
277
while (to < end)
278
{
298
279
*to++=0;
280
}
299
281
}
300
282
}
301
283
302
284
303
/*
304
Set/clear all bits above a bit.
305
306
SYNOPSIS
307
bitmap_set_above()
308
map RETURN The bitmap to change.
309
from_byte The bitmap buffer byte offset to start with.
310
use_bit The bit value (1/0) to use for all upper bits.
311
312
NOTE
313
You can only set/clear full bytes.
314
The function is meant for the situation that you copy a smaller bitmap
315
to a bigger bitmap. Bitmap lengths are always multiple of eigth (the
316
size of a byte). Using 'from_byte' saves multiplication and division
317
by eight during parameter passing.
318
319
RETURN
320
void
321
*/
322
323
void bitmap_set_above(MY_BITMAP *map, uint32_t from_byte, uint32_t use_bit)
285
void MyBitmap::setAbove(const uint32_t from_byte, const uint32_t use_bit)
324
286
{
325
287
unsigned char use_byte= use_bit ? 0xff : 0;
326
unsigned char *to= (unsigned char *)map->bitmap + from_byte;
327
unsigned char *end= (unsigned char *)map->bitmap + (map->n_bits+7)/8;
288
unsigned char *to= (unsigned char *) bitmap + from_byte;
289
unsigned char *end= (unsigned char *) bitmap + (n_bits+7)/8;
328
290
329
291
while (to < end)
292
{
330
293
*to++= use_byte;
294
}
331
295
}
332
296
333
297
334
void bitmap_subtract(MY_BITMAP *map, const MY_BITMAP *map2)
298
void bitmap_subtract(MyBitmap *map, const MyBitmap *map2)
335
299
{
336
my_bitmap_map *to= map->bitmap, *from= map2->bitmap, *end;
337
assert(map->bitmap && map2->bitmap &&
338
map->n_bits==map2->n_bits);
300
my_bitmap_map *to= map->getBitmap(), *from= map2->getBitmap(), *end;
301
assert(map->getBitmap() && map2->getBitmap() &&
302
map->numOfBitsInMap() == map2->numOfBitsInMap());
339
303
340
end= map->last_word_ptr;
304
end= map->getLastWordPtr();
341
305
342
306
while (to <= end)
307
{
343
308
*to++ &= ~(*from++);
309
}
344
310
}
345
311
346
312
347
void bitmap_union(MY_BITMAP *map, const MY_BITMAP *map2)
313
void bitmap_union(MyBitmap *map, const MyBitmap *map2)
348
314
{
349
my_bitmap_map *to= map->bitmap, *from= map2->bitmap, *end;
315
my_bitmap_map *to= map->getBitmap(), *from= map2->getBitmap(), *end;
350
316
351
assert(map->bitmap && map2->bitmap &&
352
map->n_bits==map2->n_bits);
353
end= map->last_word_ptr;
317
assert(map->getBitmap() && map2->getBitmap() &&
318
map->numOfBitsInMap() == map2->numOfBitsInMap());
319
end= map->getLastWordPtr();
354
320
355
321
while (to <= end)
322
{
356
323
*to++ |= *from++;
324
}
357
325
}
358
326
359
327
360
void bitmap_xor(MY_BITMAP *map, const MY_BITMAP *map2)
328
void bitmap_xor(MyBitmap *map, const MyBitmap *map2)
361
329
{
362
my_bitmap_map *to= map->bitmap, *from= map2->bitmap, *end= map->last_word_ptr;
363
assert(map->bitmap && map2->bitmap &&
364
map->n_bits==map2->n_bits);
330
my_bitmap_map *to= map->getBitmap();
331
my_bitmap_map *from= map2->getBitmap();
332
my_bitmap_map *end= map->getLastWordPtr();
333
assert(map->getBitmap() && map2->getBitmap() &&
334
map->numOfBitsInMap() == map2->numOfBitsInMap());
365
335
while (to <= end)
336
{
366
337
*to++ ^= *from++;
338
}
367
339
}
368
340
369
341
370
void bitmap_invert(MY_BITMAP *map)
342
void bitmap_invert(MyBitmap *map)
371
343
{
372
my_bitmap_map *to= map->bitmap, *end;
344
my_bitmap_map *to= map->getBitmap(), *end;
373
345
374
assert(map->bitmap);
375
end= map->last_word_ptr;
346
assert(map->getBitmap());
347
end= map->getLastWordPtr();
376
348
377
349
while (to <= end)
350
{
378
351
*to++ ^= 0xFFFFFFFF;
352
}
379
353
}
380
354
381
355
382
uint32_t bitmap_bits_set(const MY_BITMAP *map)
356
uint32_t MyBitmap::getBitsSet()
383
357
{
384
unsigned char *m= (unsigned char*)map->bitmap;
385
unsigned char *end= m + no_bytes_in_map(map);
358
unsigned char *m= (unsigned char*) bitmap;
359
unsigned char *end= m + numOfBytesInMap();
386
360
uint32_t res= 0;
387
361
388
assert(map->bitmap);
389
*map->last_word_ptr&= ~map->last_word_mask; /*Reset last bits to zero*/
362
assert(bitmap);
363
*last_word_ptr&= ~last_word_mask; /*Reset last bits to zero*/
390
364
while (m < end)
365
{
391
366
res+= my_count_bits_uint16(*m++);
367
}
392
368
return res;
393
369
}
394
370
395
396
void bitmap_copy(MY_BITMAP *map, const MY_BITMAP *map2)
397
{
398
my_bitmap_map *to= map->bitmap, *from= map2->bitmap, *end;
399
400
assert(map->bitmap && map2->bitmap &&
401
map->n_bits==map2->n_bits);
402
end= map->last_word_ptr;
403
while (to <= end)
404
*to++ = *from++;
405
}
406
407
408
uint32_t bitmap_get_first_set(const MY_BITMAP *map)
371
MyBitmap::MyBitmap(const MyBitmap& rhs)
372
{
373
my_bitmap_map *to= this->bitmap, *from= rhs.bitmap, *end;
374
375
if (this->bitmap && rhs.bitmap &&
376
this->n_bits == rhs.n_bits)
377
{
378
end= this->last_word_ptr;
379
while (to <= end)
380
{
381
*to++ = *from++;
382
}
383
}
384
else
385
{
386
this->n_bits= rhs.n_bits;
387
this->bitmap= rhs.bitmap;
388
}
389
}
390
391
MyBitmap& MyBitmap::operator=(const MyBitmap& rhs)
392
{
393
if (this == &rhs)
394
return *this;
395
396
my_bitmap_map *to= this->bitmap, *from= rhs.bitmap, *end;
397
398
if (this->bitmap && rhs.bitmap &&
399
this->n_bits == rhs.n_bits)
400
{
401
end= this->last_word_ptr;
402
while (to <= end)
403
{
404
*to++ = *from++;
405
}
406
}
407
else
408
{
409
this->n_bits= rhs.n_bits;
410
this->bitmap= rhs.bitmap;
411
}
412
413
return *this;
414
}
415
416
uint32_t MyBitmap::getFirstSet()
409
417
{
410
418
unsigned char *byte_ptr;
411
419
uint32_t i,j,k;
412
my_bitmap_map *data_ptr, *end= map->last_word_ptr;
420
my_bitmap_map *data_ptr, *end= last_word_ptr;
413
421
414
assert(map->bitmap);
415
data_ptr= map->bitmap;
416
*map->last_word_ptr &= ~map->last_word_mask;
422
assert(bitmap);
423
data_ptr= bitmap;
424
*last_word_ptr &= ~last_word_mask;
417
425
418
426
for (i=0; data_ptr <= end; data_ptr++, i++)
419
427
{
437
445
}
438
446
439
447
440
uint32_t bitmap_get_first(const MY_BITMAP *map)
448
uint32_t MyBitmap::getFirst()
441
449
{
442
450
unsigned char *byte_ptr;
443
451
uint32_t i,j,k;
444
my_bitmap_map *data_ptr, *end= map->last_word_ptr;
452
my_bitmap_map *data_ptr, *end= last_word_ptr;
445
453
446
assert(map->bitmap);
447
data_ptr= map->bitmap;
448
*map->last_word_ptr|= map->last_word_mask;
454
assert(bitmap);
455
data_ptr= bitmap;
456
*last_word_ptr|= last_word_mask;
449
457
450
458
for (i=0; data_ptr <= end; data_ptr++, i++)
451
459
{
476
484
return (rand() % bitsize);
477
485
}
478
486
479
bool test_set_get_clear_bit(MY_BITMAP *map, uint32_t bitsize)
487
bool test_set_get_clear_bit(MyBitmap *map, uint32_t bitsize)
480
488
{
481
489
uint32_t i, test_bit;
482
490
uint32_t no_loops= bitsize > 128 ? 128 : bitsize;
483
491
for (i=0; i < no_loops; i++)
484
492
{
485
493
test_bit= get_rand_bit(bitsize);
486
bitmap_set_bit(map, test_bit);
487
if (!bitmap_is_set(map, test_bit))
494
map->setBit(test_bit);
495
if (! map->isBitSet(test_bit))
496
{
488
497
goto error1;
489
bitmap_clear_bit(map, test_bit);
490
if (bitmap_is_set(map, test_bit))
498
}
499
map->clearBit(test_bit);
500
if (map->isBitSet(test_bit))
501
{
491
502
goto error2;
503
}
492
504
}
493
505
return false;
494
506
error1:
499
511
return true;
500
512
}
501
513
502
bool test_flip_bit(MY_BITMAP *map, uint32_t bitsize)
514
bool test_flip_bit(MyBitmap *map, uint32_t bitsize)
503
515
{
504
516
uint32_t i, test_bit;
505
517
uint32_t no_loops= bitsize > 128 ? 128 : bitsize;
506
518
for (i=0; i < no_loops; i++)
507
519
{
508
520
test_bit= get_rand_bit(bitsize);
509
bitmap_flip_bit(map, test_bit);
510
if (!bitmap_is_set(map, test_bit))
521
map->flipBit(test_bit);
522
if (!map->isBitSet(test_bit))
511
523
goto error1;
512
bitmap_flip_bit(map, test_bit);
513
if (bitmap_is_set(map, test_bit))
524
map->flipBit(test_bit);
525
if (map->isBitSet(test_bit))
514
526
goto error2;
515
527
}
516
528
return false;
522
534
return true;
523
535
}
524
536
525
bool test_operators(MY_BITMAP *, uint32_t)
537
bool test_operators(MyBitmap *, uint32_t)
526
538
{
527
539
return false;
528
540
}
529
541
530
bool test_get_all_bits(MY_BITMAP *map, uint32_t bitsize)
542
bool test_get_all_bits(MyBitmap *map, uint32_t bitsize)
531
543
{
532
544
uint32_t i;
533
bitmap_set_all(map);
534
if (!bitmap_is_set_all(map))
545
map->setAll();
546
if (!map->isSetAll())
535
547
goto error1;
536
if (!bitmap_is_prefix(map, bitsize))
548
if (!map->isPrefix(bitsize))
537
549
goto error5;
538
bitmap_clear_all(map);
539
if (!bitmap_is_clear_all(map))
550
map->clearAll();
551
if (!map->isClearAll())
540
552
goto error2;
541
if (!bitmap_is_prefix(map, 0))
553
if (!map->isPrefix(0))
542
554
goto error6;
543
555
for (i=0; i<bitsize;i++)
544
bitmap_set_bit(map, i);
545
if (!bitmap_is_set_all(map))
556
map->setBit(i);
557
if (!map->isSetAll())
546
558
goto error3;
547
559
for (i=0; i<bitsize;i++)
548
bitmap_clear_bit(map, i);
549
if (!bitmap_is_clear_all(map))
560
map->clearBit(i);
561
if (!map->isClearAll())
550
562
goto error4;
551
563
return false;
552
564
error1:
569
581
return true;
570
582
}
571
583
572
bool test_compare_operators(MY_BITMAP *map, uint32_t bitsize)
584
bool test_compare_operators(MyBitmap *map, uint32_t bitsize)
573
585
{
574
586
uint32_t i, j, test_bit1, test_bit2, test_bit3,test_bit4;
575
587
uint32_t no_loops= bitsize > 128 ? 128 : bitsize;
576
MY_BITMAP map2_obj, map3_obj;
577
MY_BITMAP *map2= &map2_obj, *map3= &map3_obj;
588
MyBitmap map2_obj, map3_obj;
589
MyBitmap *map2= &map2_obj, *map3= &map3_obj;
578
590
my_bitmap_map map2buf[1024];
579
591
my_bitmap_map map3buf[1024];
580
bitmap_init(&map2_obj, map2buf, bitsize);
581
bitmap_init(&map3_obj, map3buf, bitsize);
582
bitmap_clear_all(map2);
583
bitmap_clear_all(map3);
592
map2_obj.init(map2buf, bitsize);
593
map3_obj.init(map3buf, bitsize);
594
map2->clearAll();
595
map3->clearAll();
584
596
for (i=0; i < no_loops; i++)
585
597
{
586
598
test_bit1=get_rand_bit(bitsize);
587
bitmap_set_prefix(map, test_bit1);
599
map->setPrefix(test_bit1);
588
600
test_bit2=get_rand_bit(bitsize);
589
bitmap_set_prefix(map2, test_bit2);
601
map2->setPrefix(test_bit2);
590
602
bitmap_intersect(map, map2);
591
603
test_bit3= test_bit2 < test_bit1 ? test_bit2 : test_bit1;
592
bitmap_set_prefix(map3, test_bit3);
604
map3->setPrefix(test_bit3);
593
605
if (!bitmap_cmp(map, map3))
594
606
goto error1;
595
bitmap_clear_all(map);
596
bitmap_clear_all(map2);
597
bitmap_clear_all(map3);
607
map->clearAll();
608
map2->clearAll();
609
map3->clearAll();
598
610
test_bit1=get_rand_bit(bitsize);
599
611
test_bit2=get_rand_bit(bitsize);
600
612
test_bit3=get_rand_bit(bitsize);
601
bitmap_set_prefix(map, test_bit1);
602
bitmap_set_prefix(map2, test_bit2);
613
map->setPrefix(test_bit1);
614
map2->setPrefix(test_bit2);
603
615
test_bit3= test_bit2 > test_bit1 ? test_bit2 : test_bit1;
604
bitmap_set_prefix(map3, test_bit3);
616
map3->setPrefix(test_bit3);
605
617
bitmap_union(map, map2);
606
618
if (!bitmap_cmp(map, map3))
607
619
goto error2;
608
bitmap_clear_all(map);
609
bitmap_clear_all(map2);
610
bitmap_clear_all(map3);
620
map->clearAll();
621
map2->clearAll();
622
map3->clearAll();
611
623
test_bit1=get_rand_bit(bitsize);
612
624
test_bit2=get_rand_bit(bitsize);
613
625
test_bit3=get_rand_bit(bitsize);
614
bitmap_set_prefix(map, test_bit1);
615
bitmap_set_prefix(map2, test_bit2);
626
map->setPrefix(test_bit1);
627
map2->setPrefix(test_bit2);
616
628
bitmap_xor(map, map2);
617
629
test_bit3= test_bit2 > test_bit1 ? test_bit2 : test_bit1;
618
630
test_bit4= test_bit2 < test_bit1 ? test_bit2 : test_bit1;
619
bitmap_set_prefix(map3, test_bit3);
631
map3->setPrefix(test_bit3);
620
632
for (j=0; j < test_bit4; j++)
621
bitmap_clear_bit(map3, j);
633
map3->clearBit(j);
622
634
if (!bitmap_cmp(map, map3))
623
635
goto error3;
624
bitmap_clear_all(map);
625
bitmap_clear_all(map2);
626
bitmap_clear_all(map3);
636
map->clearAll();
637
map2->clearAll();
638
map3->clearAll();
627
639
test_bit1=get_rand_bit(bitsize);
628
640
test_bit2=get_rand_bit(bitsize);
629
641
test_bit3=get_rand_bit(bitsize);
630
bitmap_set_prefix(map, test_bit1);
631
bitmap_set_prefix(map2, test_bit2);
642
map->setPrefix(test_bit1);
643
map2->setPrefix(test_bit2);
632
644
bitmap_subtract(map, map2);
633
645
if (test_bit2 < test_bit1)
634
646
{
635
bitmap_set_prefix(map3, test_bit1);
647
map3->setPrefix(test_bit1);
636
648
for (j=0; j < test_bit2; j++)
637
bitmap_clear_bit(map3, j);
649
map3->clearBit(j);
638
650
}
639
651
if (!bitmap_cmp(map, map3))
640
652
goto error4;
641
bitmap_clear_all(map);
642
bitmap_clear_all(map2);
643
bitmap_clear_all(map3);
653
map->clearAll();
654
map2->clearAll();
655
map3->clearAll();
644
656
test_bit1=get_rand_bit(bitsize);
645
bitmap_set_prefix(map, test_bit1);
657
map->setPrefix(test_bit1);
646
658
bitmap_invert(map);
647
bitmap_set_all(map3);
659
map3->setAll();
648
660
for (j=0; j < test_bit1; j++)
649
bitmap_clear_bit(map3, j);
661
map3->clearBit(j);
650
662
if (!bitmap_cmp(map, map3))
651
663
goto error5;
652
bitmap_clear_all(map);
653
bitmap_clear_all(map3);
664
map->clearAll();
665
map3->clearAll();
654
666
}
655
667
return false;
656
668
error1:
675
687
return true;
676
688
}
677
689
678
bool test_count_bits_set(MY_BITMAP *map, uint32_t bitsize)
690
bool test_count_bits_set(MyBitmap *map, uint32_t bitsize)
679
691
{
680
692
uint32_t i, bit_count=0, test_bit;
681
693
uint32_t no_loops= bitsize > 128 ? 128 : bitsize;
682
694
for (i=0; i < no_loops; i++)
683
695
{
684
696
test_bit=get_rand_bit(bitsize);
685
if (!bitmap_is_set(map, test_bit))
697
if (!map->isBitSet(test_bit))
686
698
{
687
bitmap_set_bit(map, test_bit);
699
map->setBit(test_bit);
688
700
bit_count++;
689
701
}
690
702
}
691
703
if (bit_count==0 && bitsize > 0)
692
704
goto error1;
693
if (bitmap_bits_set(map) != bit_count)
705
if (getBitsSet() != bit_count)
694
706
goto error2;
695
707
return false;
696
708
error1:
701
713
return true;
702
714
}
703
715
704
bool test_get_first_bit(MY_BITMAP *map, uint32_t bitsize)
716
bool test_get_first_bit(MyBitmap *map, uint32_t bitsize)
705
717
{
706
718
uint32_t i, test_bit;
707
719
uint32_t no_loops= bitsize > 128 ? 128 : bitsize;
708
720
for (i=0; i < no_loops; i++)
709
721
{
710
722
test_bit=get_rand_bit(bitsize);
711
bitmap_set_bit(map, test_bit);
723
map->setBit(test_bit);
712
724
if (bitmap_get_first_set(map) != test_bit)
713
725
goto error1;
714
bitmap_set_all(map);
715
bitmap_clear_bit(map, test_bit);
716
if (bitmap_get_first(map) != test_bit)
726
map->setAll();
727
map->clearBit(test_bit);
728
if (getFirst() != test_bit)
717
729
goto error2;
718
bitmap_clear_all(map);
730
map->clearAll();
719
731
}
720
732
return false;
721
733
error1:
726
738
return true;
727
739
}
728
740
729
bool test_get_next_bit(MY_BITMAP *map, uint32_t bitsize)
741
bool test_get_next_bit(MyBitmap *map, uint32_t bitsize)
730
742
{
731
743
uint32_t i, j, test_bit;
732
744
uint32_t no_loops= bitsize > 128 ? 128 : bitsize;
734
746
{
735
747
test_bit=get_rand_bit(bitsize);
736
748
for (j=0; j < test_bit; j++)
737
bitmap_set_next(map);
738
if (!bitmap_is_prefix(map, test_bit))
749
setNext();
750
if (!map->isPrefix(test_bit))
739
751
goto error1;
740
bitmap_clear_all(map);
752
map->clearAll();
741
753
}
742
754
return false;
743
755
error1:
745
757
return true;
746
758
}
747
759
748
bool test_prefix(MY_BITMAP *map, uint32_t bitsize)
760
bool test_prefix(MyBitmap *map, uint32_t bitsize)
749
761
{
750
762
uint32_t i, j, test_bit;
751
763
uint32_t no_loops= bitsize > 128 ? 128 : bitsize;
752
764
for (i=0; i < no_loops; i++)
753
765
{
754
766
test_bit=get_rand_bit(bitsize);
755
bitmap_set_prefix(map, test_bit);
756
if (!bitmap_is_prefix(map, test_bit))
767
map->setPrefix(map, test_bit);
768
if (!map->isPrefix(test_bit))
757
769
goto error1;
758
bitmap_clear_all(map);
770
map->clearAll();
759
771
for (j=0; j < test_bit; j++)
760
bitmap_set_bit(map, j);
761
if (!bitmap_is_prefix(map, test_bit))
772
map->setBit(j);
773
if (!map->isPrefix(test_bit))
762
774
goto error2;
763
bitmap_set_all(map);
775
map->setAll();
764
776
for (j=bitsize - 1; ~(j-test_bit); j--)
765
bitmap_clear_bit(map, j);
766
if (!bitmap_is_prefix(map, test_bit))
777
map->clearBit(j);
778
if (!map->isPrefix(test_bit))
767
779
goto error3;
768
bitmap_clear_all(map);
780
map->clearAll();
769
781
}
770
782
return false;
771
783
error1:
782
794
783
795
bool do_test(uint32_t bitsize)
784
796
{
785
MY_BITMAP map;
797
MyBitmap map;
786
798
my_bitmap_map buf[1024];
787
if (bitmap_init(&map, buf, bitsize))
799
if (map.init(buf, bitsize))
788
800
{
789
801
printf("init error for bitsize %d", bitsize);
790
802
goto error;
791
803
}
792
804
if (test_set_get_clear_bit(&map,bitsize))
793
805
goto error;
794
bitmap_clear_all(&map);
806
map.clearAll();
795
807
if (test_flip_bit(&map,bitsize))
796
808
goto error;
797
bitmap_clear_all(&map);
809
map.clearAll();
798
810
if (test_operators(&map,bitsize))
799
811
goto error;
800
bitmap_clear_all(&map);
812
map.clearAll();
801
813
if (test_get_all_bits(&map, bitsize))
802
814
goto error;
803
bitmap_clear_all(&map);
815
map.clearAll();
804
816
if (test_compare_operators(&map,bitsize))
805
817
goto error;
806
bitmap_clear_all(&map);
818
map.clearAll();
807
819
if (test_count_bits_set(&map,bitsize))
808
820
goto error;
809
bitmap_clear_all(&map);
821
map.clearAll();
810
822
if (test_get_first_bit(&map,bitsize))
811
823
goto error;
812
bitmap_clear_all(&map);
824
map.clearAll();
813
825
if (test_get_next_bit(&map,bitsize))
814
826
goto error;
815
827
if (test_prefix(&map,bitsize))
Loggerhead is a web-based interface for Breezy
Version: 2.0.1