2
Copyright (c) 2002,2003 Anatoliy Kuznetsov.
4
Permission is hereby granted, free of charge, to any person
5
obtaining a copy of this software and associated documentation
6
files (the "Software"), to deal in the Software without restriction,
7
including without limitation the rights to use, copy, modify, merge,
8
publish, distribute, sublicense, and/or sell copies of the Software,
9
and to permit persons to whom the Software is furnished to do so,
10
subject to the following conditions:
12
The above copyright notice and this permission notice shall be included
13
in all copies or substantial portions of the Software.
15
THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
16
EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES
17
OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
18
IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM,
19
DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE,
20
ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
21
OTHER DEALINGS IN THE SOFTWARE.
24
//#define BM_SET_MMX_GUARD
47
#define POOL_SIZE 5000
52
template<class T> T* pool_allocate(T** pool, int& i, size_t n)
54
return i ? pool[i--] : (T*) ::malloc(n * sizeof(T));
57
inline void* pool_allocate2(void** pool, int& i, size_t n)
59
return i ? pool[i--] : malloc(n * sizeof(void*));
64
template<class T> void pool_free(T** pool, int& i, T* p)
66
i < POOL_SIZE ? (free(p),(void*)0) : pool[++i]=p;
70
class pool_block_allocator
74
static bm::word_t* allocate(size_t n, const void *)
77
bm::word_t** pool = 0;
81
case bm::set_block_size:
82
idx = &bit_blocks_idx_;
83
pool = free_bit_blocks_;
87
idx = &gap_blocks_idx0_;
88
pool = gap_bit_blocks0_;
92
idx = &gap_blocks_idx1_;
93
pool = gap_bit_blocks1_;
97
idx = &gap_blocks_idx2_;
98
pool = gap_bit_blocks2_;
102
idx = &gap_blocks_idx3_;
103
pool = gap_bit_blocks3_;
110
return pool_allocate(pool, *idx, n);
113
static void deallocate(bm::word_t* p, size_t n)
116
bm::word_t** pool = 0;
120
case bm::set_block_size:
121
idx = &bit_blocks_idx_;
122
pool = free_bit_blocks_;
126
idx = &gap_blocks_idx0_;
127
pool = gap_bit_blocks0_;
131
idx = &gap_blocks_idx1_;
132
pool = gap_bit_blocks1_;
136
idx = &gap_blocks_idx2_;
137
pool = gap_bit_blocks2_;
141
idx = &gap_blocks_idx3_;
142
pool = gap_bit_blocks3_;
149
pool_free(pool, *idx, p);
153
static bm::word_t* free_bit_blocks_[];
154
static int bit_blocks_idx_;
156
static bm::word_t* gap_bit_blocks0_[];
157
static int gap_blocks_idx0_;
159
static bm::word_t* gap_bit_blocks1_[];
160
static int gap_blocks_idx1_;
162
static bm::word_t* gap_bit_blocks2_[];
163
static int gap_blocks_idx2_;
165
static bm::word_t* gap_bit_blocks3_[];
166
static int gap_blocks_idx3_;
169
bm::word_t* pool_block_allocator::free_bit_blocks_[POOL_SIZE];
170
int pool_block_allocator::bit_blocks_idx_ = 0;
172
bm::word_t* pool_block_allocator::gap_bit_blocks0_[POOL_SIZE];
173
int pool_block_allocator::gap_blocks_idx0_ = 0;
175
bm::word_t* pool_block_allocator::gap_bit_blocks1_[POOL_SIZE];
176
int pool_block_allocator::gap_blocks_idx1_ = 0;
178
bm::word_t* pool_block_allocator::gap_bit_blocks2_[POOL_SIZE];
179
int pool_block_allocator::gap_blocks_idx2_ = 0;
181
bm::word_t* pool_block_allocator::gap_bit_blocks3_[POOL_SIZE];
182
int pool_block_allocator::gap_blocks_idx3_ = 0;
187
class pool_ptr_allocator
191
static void* allocate(size_t n, const void *)
193
return pool_allocate2(free_ptr_blocks_, ptr_blocks_idx_, n);
196
static void deallocate(void* p, size_t)
198
pool_free(free_ptr_blocks_, ptr_blocks_idx_, p);
202
static void* free_ptr_blocks_[];
203
static int ptr_blocks_idx_;
206
void* pool_ptr_allocator::free_ptr_blocks_[POOL_SIZE];
207
int pool_ptr_allocator::ptr_blocks_idx_ = 0;
215
class dbg_block_allocator
221
static bm::word_t* allocate(size_t n, const void *)
226
(bm::word_t*) ::malloc((n+1) * sizeof(bm::word_t));
231
static void deallocate(bm::word_t* p, size_t n)
237
printf("Block memory deallocation error!\n");
249
unsigned dbg_block_allocator::na_ = 0;
250
unsigned dbg_block_allocator::nf_ = 0;
252
class dbg_ptr_allocator
258
static void* allocate(size_t n, const void *)
261
assert(sizeof(size_t) == sizeof(void*));
262
void* p = ::malloc((n+1) * sizeof(void*));
263
size_t* s = (size_t*) p;
268
static void deallocate(void* p, size_t n)
271
size_t* s = (size_t*) p;
275
printf("Ptr memory deallocation error!\n");
288
unsigned dbg_ptr_allocator::na_ = 0;
289
unsigned dbg_ptr_allocator::nf_ = 0;
292
typedef mem_alloc<dbg_block_allocator, dbg_ptr_allocator> dbg_alloc;
294
typedef bm::bvector<dbg_alloc> bvect;
295
typedef bm::bvector_mini<dbg_block_allocator> bvect_mini;
301
typedef mem_alloc<pool_block_allocator, pool_ptr_allocator> pool_alloc;
302
typedef bm::bvector<pool_alloc> bvect;
303
typedef bm::bvector_mini<bm::block_allocator> bvect_mini;
308
typedef bm::bvector<> bvect;
309
typedef bm::bvector_mini<bm::block_allocator> bvect_mini;
315
//const unsigned BITVECT_SIZE = 100000000 * 8;
317
// This this setting program will consume around 150M of RAM
318
const unsigned BITVECT_SIZE = 100000000 * 2;
320
const unsigned ITERATIONS = 100000;
321
const unsigned PROGRESS_PRINT = 2000000;
325
void CheckVectors(bvect_mini &bvect_min,
328
bool detailed = false);
331
unsigned random_minmax(unsigned min, unsigned max)
333
unsigned r = (rand() << 16) | rand();
334
return r % (max-min) + min;
338
void FillSets(bvect_mini* bvect_min,
342
unsigned fill_factor)
350
unsigned n_id = (max - min) / 100;
351
printf("random filling : %i\n", n_id);
352
for (i = 0; i < n_id; i++)
354
id = random_minmax(min, max);
355
bvect_min->set_bit(id);
356
bvect_full->set_bit(id);
359
if ( (i % PROGRESS_PRINT) == 0)
361
cout << "+" << flush;
369
printf("fill_factor random filling : factor = %i\n", fill_factor);
371
for(i = 0; i < fill_factor; i++)
378
unsigned start = min + (max - min) / (fill_factor * k);
381
start += random_minmax(1, (max - min) / (fill_factor * 10));
389
unsigned end = start + (max - start) / (fill_factor *2);
392
end -= random_minmax(1, (max - start) / (fill_factor * 10));
408
int inc = rand() % 3;
410
unsigned end2 = start + rand() % 1000;
415
bvect_min->set_bit(start);
416
bvect_full->set_bit(start);
422
if ( ( ((i+1)*(end-start)) % PROGRESS_PRINT) == 0)
424
cout << "+" << flush;
433
bvect_min->set_bit(start);
434
bvect_full->set_bit(start);
440
bvect_min->set_bit(start);
441
bvect_full->set_bit(start);
446
if ( ( ((i+1)*(end-start)) % PROGRESS_PRINT) == 0)
448
cout << "+" << flush;
459
for(; start < end; ++start)
461
bvect_min->set_bit(start);
462
bvect_full->set_bit(start);
471
if ( ( ((i+1)*(end-start)) % PROGRESS_PRINT) == 0)
473
cout << "+" << flush;
487
// 111........111111........111111..........11111111.......1111111...
491
void FillSetsIntervals(bvect_mini* bvect_min,
495
unsigned fill_factor,
499
while(fill_factor==0)
501
fill_factor=rand()%10;
504
cout << "Intervals filling. Factor="
505
<< fill_factor << endl << endl;
508
unsigned factor = 70 * fill_factor;
509
for (i = min; i < max; ++i)
515
len = rand() % factor;
518
} while (end >= max);
520
if (set_flag == false)
522
cout << "Cleaning: " << i << "-" << end << endl;
526
cout << "Add: " << i << "-" << end << endl;
531
bvect_full->set_range(i, end-1, set_flag);
534
for (j = i; j < end; ++j)
538
bvect_min->set_bit(j);
539
//bvect_full->set_bit(j);
543
bvect_min->clear_bit(j);
544
//bvect_full->clear_bit(j);
548
bool b = bvect_full->count_check();
551
cout << "Count check failed (clear)!" << endl;
552
cout << "bit=" << j << endl;
562
//cout << "Checking range filling " << from << "-" << to << endl;
563
//CheckVectors(*bvect_min, *bvect_full, 100000000);
569
len = rand() % (factor* 10 * bm::gap_max_bits);
572
len *= rand() % (factor * 10);
580
if (set_flag == false)
582
cout << "Additional Cleaning: " << i << "-" << end << endl;
585
for(unsigned k=0; k < 1000 && i < max; k+=3,i+=3)
589
bvect_min->set_bit(i);
590
bvect_full->set_bit(i);
594
bvect_min->clear_bit(j);
595
bvect_full->clear_bit(j);
605
void FillSetClearIntervals(bvect_mini* bvect_min,
609
unsigned fill_factor)
611
FillSetsIntervals(bvect_min, bvect_full, min, max, fill_factor, true);
612
FillSetsIntervals(bvect_min, bvect_full, min, max, fill_factor, false);
616
void FillSetsRandom(bvect_mini* bvect_min,
620
unsigned fill_factor)
622
unsigned diap = max - min;
641
for (unsigned i = 0; i < count; ++i)
643
unsigned bn = rand() % count;
650
bvect_min->set_bit(bn);
651
bvect_full->set_bit(bn);
653
if ( (i % PROGRESS_PRINT) == 0)
655
cout << "+" << flush;
658
cout << "Ok" << endl;
664
// Quasi random filling with choosing randomizing method.
667
void FillSetsRandomMethod(bvect_mini* bvect_min,
684
cout << "Random filling: method - FillSets - factor(0)" << endl;
685
FillSets(bvect_min, bvect_full, min, max, 0);
689
cout << "Random filling: method - FillSets - factor(random)" << endl;
691
FillSets(bvect_min, bvect_full, min, max, factor?factor:1);
695
cout << "Random filling: method - Set-Clear Intervals - factor(random)" << endl;
697
FillSetClearIntervals(bvect_min, bvect_full, min, max, factor);
700
cout << "Random filling: method - FillRandom - factor(random)" << endl;
702
FillSetsRandom(bvect_min, bvect_full, min, max, factor?factor:1);
706
cout << "Random filling: method - Set Intervals - factor(random)" << endl;
708
FillSetsIntervals(bvect_min, bvect_full, min, max, factor);
713
if (optimize && (method <= 1))
715
cout << "Vector optimization..." << flush;
716
bvect::optmode opt = bvect::opt_compress;
717
if (rand() % 3 == 0) {
718
opt = bvect::opt_free_01;
720
bvect_full->optimize(0, opt);
721
cout << "OK" << endl;
727
void print_mv(const bvect_mini &bvect_min, unsigned size)
730
for (i = 0; i < size; ++i)
732
bool bflag = bvect_min.is_bit_true(i) != 0;
738
if ((i % 31) == 0 && (i != 0))
745
void print_gap(const gap_vector& gap_vect, unsigned size)
747
const gap_word_t *buf = gap_vect.get_buf();
748
unsigned len = gap_length(buf);
749
printf("[%i:]", *buf++ & 1);
751
for (unsigned i = 1; i < len; ++i)
753
printf("%i,", *buf++);
759
void CheckGAPMin(const gap_vector& gapv, const bvect_mini& bvect_min, unsigned len)
761
for (unsigned i = 0; i < len; ++i)
763
int bit1 = (gapv.is_bit_true(i) == 1);
764
int bit2 = (bvect_min.is_bit_true(i) != 0);
767
cout << "Bit comparison failed. " << "Bit N=" << i << endl;
774
void CheckIntervals(const bvect& bv, unsigned max_bit)
776
unsigned cnt0 = count_intervals(bv);
778
bool bit_prev = bv.test(0);
779
for (unsigned i = 1; i < max_bit; ++i)
781
bool bit = bv.test(i);
782
cnt1 += bit_prev ^ bit;
787
cout << "CheckIntervals error. " << "bm count=" << cnt0
788
<< " Control = " << cnt1 << endl;
793
template<class T> void CheckCountRange(const T& vect,
796
unsigned* block_count_arr=0)
798
unsigned cnt1 = vect.count_range(left, right, block_count_arr);
801
for (unsigned i = left; i <= right; ++i)
805
// cout << i << " " << flush;
812
cout << "Bitcount range failed!" << "left=" << left
813
<< " right=" << right << endl
814
<< "count_range()=" << cnt1
815
<< " check=" << cnt2;
821
unsigned BitCountChange(unsigned word)
824
unsigned bit_prev = word & 1;
826
for (unsigned i = 1; i < 32; ++i)
828
unsigned bit = word & 1;
829
count += bit ^ bit_prev;
837
void DetailedCheckVectors(const bvect_mini &bvect_min,
838
const bvect &bvect_full,
841
cout << "Detailed check" << endl;
845
// detailed bit by bit comparison. Paranoia check.
848
for (i = 0; i < size; ++i)
850
bool bv_m_flag = bvect_min.is_bit_true(i) != 0;
851
bool bv_f_flag = bvect_full.get_bit(i) != 0;
853
if (bv_m_flag != bv_f_flag)
855
printf("Bit %u is non conformant. vect_min=%i vect_full=%i\n",
856
i, (int)bv_m_flag, (int)bv_f_flag);
858
cout << "Non-conformant block number is: " << unsigned(i >> bm::set_block_shift) << endl;
865
if ( (i % PROGRESS_PRINT) == 0)
873
printf("\n detailed check ok.\n");
878
// vectors comparison check
880
void CheckVectors(bvect_mini &bvect_min,
885
cout << "\nVectors checking...bits to compare = " << size << endl;
887
cout << "Bitcount summary : " << endl;
888
unsigned min_count = bvect_min.bit_count();
889
cout << "minvector count = " << min_count << endl;
890
unsigned count = bvect_full.count();
891
unsigned full_count = bvect_full.recalc_count();
892
cout << "fullvector re-count = " << full_count << endl;
894
if (min_count != full_count)
896
cout << "fullvector count = " << count << endl;
897
cout << "Count comparison failed !!!!" << endl;
899
DetailedCheckVectors(bvect_min, bvect_full, size);
906
bool any = bvect_full.any();
909
cout << "Anycheck failed!" << endl;
914
// get_next comparison
916
cout << "Positive bits comparison..." << flush;
917
unsigned nb_min = bvect_min.get_first();
918
unsigned nb_ful = bvect_full.get_first();
920
bvect::counted_enumerator en = bvect_full.first();
921
unsigned nb_en = *en;
922
if (nb_min != nb_ful)
924
cout << "!!!! First bit comparison failed. Full id = "
925
<< nb_ful << " Min id = " << nb_min
928
bool bit_f = bvect_full.get_bit(nb_ful);
929
cout << "Full vector'd bit #" << nb_ful << "is:"
932
bool bit_m = (bvect_min.is_bit_true(nb_min) == 1);
933
cout << "Min vector'd bit #" << nb_min << "is:"
939
DetailedCheckVectors(bvect_min, bvect_full, size);
946
unsigned bit_count = 1;
947
unsigned en_prev = nb_en;
951
nb_min = bvect_min.get_next(nb_min);
961
// nb_en = bvect_full.get_next(nb_en);
967
nb_ful = bvect_full.get_next(en_prev);
968
cout << "!!!!! next bit comparison failed. Full id = "
969
<< nb_ful << " Min id = " << nb_min
970
<< " Enumerator = " << nb_en
973
// bvect_full.stat();
975
// DetailedCheckVectors(bvect_min, bvect_full, size);
979
if ( (bit_count % PROGRESS_PRINT) == 0)
981
cout << "." << flush;
984
} while (en.valid());
985
if (bit_count != min_count)
987
cout << " Bit count failed."
988
<< " min = " << min_count
989
<< " bit = " << bit_count
995
cout << "OK" << endl;
1007
for (int i = 0; i < 100000; ++i)
1009
bvect_full.set_bit(i);
1011
bvect_full.optimize();
1016
int count = bvect_full.count();
1024
cout << "---------------------------- WordCmp test" << endl;
1026
for (int i = 0; i < 10000000; ++i)
1028
unsigned w1 = rand();
1029
unsigned w2 = rand();
1030
int res = wordcmp0(w1, w2);
1031
int res2 = wordcmp(w1, w2);
1034
printf("WordCmp failed !\n");
1038
res = wordcmp0((unsigned)0U, (unsigned)w2);
1039
res2 = wordcmp((unsigned)0U, (unsigned)w2);
1043
printf("WordCmp 0 test failed !\n");
1047
res = wordcmp0((unsigned)~0U, (unsigned)w2);
1048
res2 = wordcmp((unsigned)~0U, (unsigned)w2);
1052
printf("WordCmp ~0 test failed !\n");
1056
res = wordcmp0((unsigned)w2, (unsigned)0);
1057
res2 = wordcmp((unsigned)w2, (unsigned)0);
1061
printf("WordCmp 0-2 test failed !\n");
1067
cout << "Ok." << endl;
1070
void BasicFunctionalityTest()
1072
cout << "---------------------------- Basic functinality test" << endl;
1074
assert(ITERATIONS < BITVECT_SIZE);
1077
bvect_mini bvect_min(BITVECT_SIZE);
1081
printf("\nBasic functionality test.\n");
1083
// filling vectors with regular values
1086
for (i = 0; i < ITERATIONS; ++i)
1088
bvect_min.set_bit(i);
1089
bvect_full.set_bit(i);
1092
bvect_full1.set_range(0, ITERATIONS-1);
1094
CheckCountRange(bvect_full, 0, ITERATIONS);
1095
CheckCountRange(bvect_full, 10, ITERATIONS+10);
1097
if (bvect_full1 != bvect_full)
1099
cout << "set_range failed!" << endl;
1107
// checking the results
1108
unsigned count_min = 0;
1109
for (i = 0; i < ITERATIONS; ++i)
1111
if (bvect_min.is_bit_true(i))
1117
unsigned count_full = bvect_full.count();
1119
if (count_min == count_full)
1121
printf("simple count test ok.\n");
1125
printf("simple count test failed count_min = %i count_full = %i\n",
1126
count_min, count_full);
1131
// detailed vectors verification
1133
CheckVectors(bvect_min, bvect_full, ITERATIONS);
1137
for (i = 0; i < ITERATIONS; i+=2)
1139
bvect_min.clear_bit(i);
1140
bvect_full.clear_bit(i);
1141
bvect_full1.set_range(i, i, false);
1144
CheckVectors(bvect_min, bvect_full, ITERATIONS);
1145
CheckVectors(bvect_min, bvect_full1, ITERATIONS);
1147
for (i = 0; i < ITERATIONS; ++i)
1149
bvect_min.clear_bit(i);
1153
CheckVectors(bvect_min, bvect_full, ITERATIONS);
1155
cout << "Random step filling" << endl;
1157
for (i = rand()%10; i < ITERATIONS; i+=rand()%10)
1159
bvect_min.clear_bit(i);
1160
bvect_full.clear_bit(i);
1163
CheckVectors(bvect_min, bvect_full, ITERATIONS);
1171
bv2[200] = bv2[700] = bv2[500] = true;
1175
if (bv1.count() != 3)
1177
cout << "Swap test failed!" << endl;
1181
if (bv2.count() != 2)
1183
cout << "Swap test failed!" << endl;
1188
void SimpleRandomFillTest()
1190
assert(ITERATIONS < BITVECT_SIZE);
1192
cout << "-------------------------- SimpleRandomFillTest" << endl;
1195
printf("Simple random fill test 1.");
1196
bvect_mini bvect_min(BITVECT_SIZE);
1198
bvect_full.set_new_blocks_strat(bm::BM_BIT);
1201
unsigned iter = ITERATIONS / 5;
1203
printf("\nSimple Random fill test ITERATIONS = %i\n", iter);
1205
bvect_min.set_bit(0);
1206
bvect_full.set_bit(0);
1209
for (i = 0; i < iter; ++i)
1211
unsigned num = ::rand() % iter;
1212
bvect_min.set_bit(num);
1213
bvect_full.set_bit(num);
1214
if ((i % 1000) == 0) cout << "." << flush;
1215
CheckCountRange(bvect_full, 0, num);
1216
CheckCountRange(bvect_full, num, num+iter);
1219
CheckVectors(bvect_min, bvect_full, iter);
1220
CheckCountRange(bvect_full, 0, iter);
1222
printf("Simple random fill test 2.");
1224
for(i = 0; i < iter; ++i)
1226
unsigned num = ::rand() % iter;
1227
bvect_min.clear_bit(num);
1228
bvect_full.clear_bit(num);
1231
CheckVectors(bvect_min, bvect_full, iter);
1236
printf("\nSimple random fill test 3.\n");
1237
bvect_mini bvect_min(BITVECT_SIZE);
1238
bvect bvect_full(bm::BM_GAP);
1241
unsigned iter = ITERATIONS;
1243
printf("\nSimple Random fill test ITERATIONS = %i\n", iter);
1246
for(i = 0; i < iter; ++i)
1248
unsigned num = ::rand() % iter;
1249
bvect_min.set_bit(num);
1250
bvect_full.set_bit(num);
1251
CheckCountRange(bvect_full, 0, 65535);
1252
CheckCountRange(bvect_full, 0, num);
1253
CheckCountRange(bvect_full, num, num+iter);
1254
if ((i % 1000) == 0) cout << "." << flush;
1257
CheckVectors(bvect_min, bvect_full, iter);
1259
printf("Simple random fill test 4.");
1261
for(i = 0; i < iter; ++i)
1263
unsigned num = ::rand() % iter;
1264
bvect_min.clear_bit(num);
1265
bvect_full.clear_bit(num);
1266
CheckCountRange(bvect_full, 0, num);
1267
CheckCountRange(bvect_full, num, num+iter);
1268
if ((i % 1000) == 0) cout << "." << flush;
1271
CheckVectors(bvect_min, bvect_full, iter);
1272
CheckCountRange(bvect_full, 0, iter);
1281
void RangeRandomFillTest()
1283
assert(ITERATIONS < BITVECT_SIZE);
1285
cout << "----------------------------------- RangeRandomFillTest" << endl;
1288
bvect_mini bvect_min(BITVECT_SIZE);
1291
printf("Range Random fill test\n");
1293
unsigned min = BITVECT_SIZE / 2;
1294
unsigned max = BITVECT_SIZE / 2 + ITERATIONS;
1295
if (max > BITVECT_SIZE)
1296
max = BITVECT_SIZE - 1;
1298
FillSets(&bvect_min, &bvect_full, min, max, 0);
1300
CheckVectors(bvect_min, bvect_full, BITVECT_SIZE);
1301
CheckCountRange(bvect_full, min, max);
1307
bvect_mini bvect_min(BITVECT_SIZE);
1310
printf("Range Random fill test\n");
1312
unsigned min = BITVECT_SIZE / 2;
1313
unsigned max = BITVECT_SIZE / 2 + ITERATIONS;
1314
if (max > BITVECT_SIZE)
1315
max = BITVECT_SIZE - 1;
1317
FillSetsIntervals(&bvect_min, &bvect_full, min, max, 4);
1319
CheckVectors(bvect_min, bvect_full, BITVECT_SIZE);
1320
CheckCountRange(bvect_full, min, max);
1326
void AndOperationsTest()
1328
assert(ITERATIONS < BITVECT_SIZE);
1330
cout << "----------------------------------- AndOperationTest" << endl;
1334
bvect_mini bvect_min1(256);
1335
bvect_mini bvect_min2(256);
1339
bvect_full1.set_new_blocks_strat(bm::BM_GAP);
1340
bvect_full2.set_new_blocks_strat(bm::BM_GAP);
1344
printf("AND test\n");
1346
bvect_min1.set_bit(1);
1347
bvect_min1.set_bit(12);
1348
bvect_min1.set_bit(13);
1350
bvect_min2.set_bit(12);
1351
bvect_min2.set_bit(13);
1353
bvect_min1.combine_and(bvect_min2);
1355
bvect_full1.set_bit(1);
1356
bvect_full1.set_bit(12);
1357
bvect_full1.set_bit(13);
1359
bvect_full2.set_bit(12);
1360
bvect_full2.set_bit(13);
1362
bm::id_t predicted_count = bm::count_and(bvect_full1, bvect_full2);
1364
bvect_full1.bit_and(bvect_full2);
1366
bm::id_t count = bvect_full1.count();
1367
if (count != predicted_count)
1369
cout << "Predicted count error!" << endl;
1373
CheckVectors(bvect_min1, bvect_full1, 256);
1374
CheckCountRange(bvect_full1, 0, 256);
1380
bvect_mini bvect_min1(BITVECT_SIZE);
1381
bvect_mini bvect_min2(BITVECT_SIZE);
1386
printf("AND test stage 1.\n");
1388
for (int i = 0; i < 112; ++i)
1390
bvect_min1.set_bit(i);
1391
bvect_full1.set_bit(i);
1393
bvect_min2.set_bit(i);
1394
bvect_full2.set_bit(i);
1398
CheckVectors(bvect_min1, bvect_full1, BITVECT_SIZE/10+10);
1399
CheckCountRange(bvect_full1, 0, BITVECT_SIZE/10+10);
1401
// FillSets(&bvect_min1, &bvect_full1, 1, BITVECT_SIZE/7, 0);
1402
// FillSets(&bvect_min2, &bvect_full2, 1, BITVECT_SIZE/7, 0);
1404
bvect_min1.combine_and(bvect_min2);
1406
bm::id_t predicted_count = bm::count_and(bvect_full1,bvect_full2);
1408
bvect_full1.bit_and(bvect_full2);
1410
bm::id_t count = bvect_full1.count();
1411
if (count != predicted_count)
1413
cout << "Predicted count error!" << endl;
1417
CheckVectors(bvect_min1, bvect_full1, BITVECT_SIZE/10+10);
1418
CheckCountRange(bvect_full1, 0, BITVECT_SIZE/10+10);
1425
bvect_mini bvect_min1(BITVECT_SIZE);
1426
bvect_mini bvect_min2(BITVECT_SIZE);
1430
bvect_full1.set_new_blocks_strat(bm::BM_GAP);
1431
bvect_full2.set_new_blocks_strat(bm::BM_GAP);
1433
printf("AND test stage 2.\n");
1436
FillSets(&bvect_min1, &bvect_full1, 1, BITVECT_SIZE/7, 0);
1437
FillSets(&bvect_min2, &bvect_full2, 1, BITVECT_SIZE/7, 0);
1439
bm::id_t predicted_count = bm::count_and(bvect_full1,bvect_full2);
1441
bvect_min1.combine_and(bvect_min2);
1443
bvect_full1.bit_and(bvect_full2);
1445
bm::id_t count = bvect_full1.count();
1446
if (count != predicted_count)
1448
cout << "Predicted count error!" << endl;
1453
CheckVectors(bvect_min1, bvect_full1, BITVECT_SIZE/10+10);
1454
CheckCountRange(bvect_full1, 0, BITVECT_SIZE/10+10);
1460
bvect_mini bvect_min1(BITVECT_SIZE);
1461
bvect_mini bvect_min2(BITVECT_SIZE);
1465
bvect_full1.set_new_blocks_strat(bm::BM_BIT);
1466
bvect_full2.set_new_blocks_strat(bm::BM_BIT);
1468
cout << "------------------------------" << endl;
1469
printf("AND test stage 3.\n");
1472
FillSets(&bvect_min1, &bvect_full1, 1, BITVECT_SIZE/5, 2);
1473
FillSets(&bvect_min2, &bvect_full2, 1, BITVECT_SIZE/5, 2);
1475
bvect_min1.combine_and(bvect_min2);
1477
bm::id_t predicted_count = bm::count_and(bvect_full1, bvect_full2);
1479
bvect_full1.bit_and(bvect_full2);
1481
bm::id_t count = bvect_full1.count();
1482
if (count != predicted_count)
1484
cout << "Predicted count error!" << endl;
1488
CheckVectors(bvect_min1, bvect_full1, BITVECT_SIZE);
1489
CheckCountRange(bvect_full1, 0, BITVECT_SIZE);
1491
bvect_full1.optimize();
1492
CheckVectors(bvect_min1, bvect_full1, BITVECT_SIZE);
1493
CheckCountRange(bvect_full1, 0, BITVECT_SIZE);
1494
CheckCountRange(bvect_full1, BITVECT_SIZE/2, BITVECT_SIZE);
1503
void OrOperationsTest()
1505
assert(ITERATIONS < BITVECT_SIZE);
1507
cout << "----------------------------------- OrOperationTest" << endl;
1511
bvect_mini bvect_min1(256);
1512
bvect_mini bvect_min2(256);
1516
bvect_full1.set_new_blocks_strat(bm::BM_GAP);
1517
bvect_full2.set_new_blocks_strat(bm::BM_GAP);
1521
printf("OR test\n");
1523
bvect_min1.set_bit(1);
1524
bvect_min1.set_bit(12);
1525
bvect_min1.set_bit(13);
1527
bvect_min2.set_bit(12);
1528
bvect_min2.set_bit(13);
1530
bvect_min1.combine_or(bvect_min2);
1532
bvect_full1.set_bit(1);
1533
bvect_full1.set_bit(12);
1534
bvect_full1.set_bit(13);
1536
bvect_full2.set_bit(12);
1537
bvect_full2.set_bit(13);
1539
bm::id_t predicted_count = bm::count_or(bvect_full1, bvect_full2);
1541
bvect_full1.bit_or(bvect_full2);
1543
bm::id_t count = bvect_full1.count();
1544
if (count != predicted_count)
1546
cout << "Predicted count error!" << endl;
1547
cout << predicted_count << " " << count << endl;
1553
CheckVectors(bvect_min1, bvect_full1, 256);
1554
CheckCountRange(bvect_full1, 0, 256);
1555
CheckCountRange(bvect_full1, 128, 256);
1560
bvect_mini bvect_min1(BITVECT_SIZE);
1561
bvect_mini bvect_min2(BITVECT_SIZE);
1565
bvect_full1.set_new_blocks_strat(bm::BM_GAP);
1566
bvect_full2.set_new_blocks_strat(bm::BM_GAP);
1568
printf("OR test stage 2.\n");
1571
FillSets(&bvect_min1, &bvect_full1, 1, BITVECT_SIZE/7, 0);
1572
FillSets(&bvect_min2, &bvect_full2, 1, BITVECT_SIZE/7, 0);
1574
bvect_min1.combine_or(bvect_min2);
1576
bm::id_t predicted_count = bm::count_or(bvect_full1, bvect_full2);
1578
bvect_full1.bit_or(bvect_full2);
1580
bm::id_t count = bvect_full1.count();
1581
if (count != predicted_count)
1583
cout << "Predicted count error!" << endl;
1587
CheckVectors(bvect_min1, bvect_full1, BITVECT_SIZE/10+10);
1588
CheckCountRange(bvect_full1, 0, BITVECT_SIZE/10+10);
1594
bvect_mini bvect_min1(BITVECT_SIZE);
1595
bvect_mini bvect_min2(BITVECT_SIZE);
1599
bvect_full1.set_new_blocks_strat(bm::BM_BIT);
1600
bvect_full2.set_new_blocks_strat(bm::BM_BIT);
1602
cout << "------------------------------" << endl;
1603
printf("OR test stage 3.\n");
1606
FillSets(&bvect_min1, &bvect_full1, 1, BITVECT_SIZE/5, 2);
1607
FillSets(&bvect_min2, &bvect_full2, 1, BITVECT_SIZE/5, 2);
1609
bvect_min1.combine_or(bvect_min2);
1611
bm::id_t predicted_count = bm::count_or(bvect_full1, bvect_full2);
1613
bvect_full1.bit_or(bvect_full2);
1615
bm::id_t count = bvect_full1.count();
1616
if (count != predicted_count)
1618
cout << "Predicted count error!" << endl;
1622
CheckVectors(bvect_min1, bvect_full1, BITVECT_SIZE);
1624
bvect_full1.optimize();
1626
CheckVectors(bvect_min1, bvect_full1, BITVECT_SIZE);
1627
CheckCountRange(bvect_full1, 0, BITVECT_SIZE);
1632
cout << "Testing combine_or" << endl;
1638
bvect_mini bvect_min1(BITVECT_SIZE);
1640
bvect_full1.set_new_blocks_strat(bm::BM_GAP);
1641
bvect_full2.set_new_blocks_strat(bm::BM_GAP);
1643
unsigned ids[10000];
1644
unsigned to_add = 10000;
1647
for (unsigned i = 0; i < to_add; ++i)
1650
bvect_full2.set(bn);
1651
bvect_min1.set_bit(bn);
1655
unsigned* first = ids;
1656
unsigned* last = ids + to_add;
1658
bm::combine_or(bvect_full1, first, last);
1660
CheckVectors(bvect_min1, bvect_full1, BITVECT_SIZE);
1662
bm::combine_or(bvect_full1, first, last);
1663
CheckVectors(bvect_min1, bvect_full1, BITVECT_SIZE);
1669
unsigned ids[] = {0, 65536, 65535, 65535*3, 65535*2, 10};
1670
unsigned to_add = sizeof(ids)/sizeof(unsigned);
1673
bvect_mini bvect_min1(BITVECT_SIZE);
1675
bvect_full1.set_new_blocks_strat(bm::BM_GAP);
1676
bvect_full2.set_new_blocks_strat(bm::BM_GAP);
1679
for (unsigned i = 0; i < to_add; ++i)
1682
bvect_full2.set(bn);
1683
bvect_min1.set_bit(bn);
1687
unsigned* first = ids;
1688
unsigned* last = ids + to_add;
1690
bm::combine_or(bvect_full1, first, last);
1691
CheckVectors(bvect_min1, bvect_full1, BITVECT_SIZE);
1693
bm::combine_or(bvect_full1, first, last);
1694
CheckVectors(bvect_min1, bvect_full1, BITVECT_SIZE);
1702
void SubOperationsTest()
1704
assert(ITERATIONS < BITVECT_SIZE);
1706
cout << "----------------------------------- SubOperationTest" << endl;
1710
bvect_mini bvect_min1(256);
1711
bvect_mini bvect_min2(256);
1715
bvect_full1.set_new_blocks_strat(bm::BM_GAP);
1716
bvect_full2.set_new_blocks_strat(bm::BM_GAP);
1720
printf("SUB test\n");
1722
bvect_min1.set_bit(1);
1723
bvect_min1.set_bit(12);
1724
bvect_min1.set_bit(13);
1726
bvect_min2.set_bit(12);
1727
bvect_min2.set_bit(13);
1729
bvect_min1.combine_sub(bvect_min2);
1731
bvect_full1.set_bit(1);
1732
bvect_full1.set_bit(12);
1733
bvect_full1.set_bit(13);
1735
bvect_full2.set_bit(12);
1736
bvect_full2.set_bit(13);
1738
bm::id_t predicted_count = bm::count_sub(bvect_full1, bvect_full2);
1740
bvect_full1.bit_sub(bvect_full2);
1742
bm::id_t count = bvect_full1.count();
1743
if (count != predicted_count)
1745
cout << "Predicted count error!" << endl;
1749
CheckVectors(bvect_min1, bvect_full1, 256);
1750
CheckCountRange(bvect_full1, 0, 256);
1756
bvect_mini bvect_min1(BITVECT_SIZE);
1757
bvect_mini bvect_min2(BITVECT_SIZE);
1761
bvect_full1.set_new_blocks_strat(bm::BM_GAP);
1762
bvect_full2.set_new_blocks_strat(bm::BM_GAP);
1764
printf("SUB test stage 2.\n");
1767
FillSets(&bvect_min1, &bvect_full1, 1, BITVECT_SIZE/7, 0);
1768
FillSets(&bvect_min2, &bvect_full2, 1, BITVECT_SIZE/7, 0);
1770
bvect_min1.combine_sub(bvect_min2);
1772
bm::id_t predicted_count = bm::count_sub(bvect_full1, bvect_full2);
1774
bvect_full1.bit_sub(bvect_full2);
1776
bm::id_t count = bvect_full1.count();
1777
if (count != predicted_count)
1779
cout << "Predicted count error!" << endl;
1780
cout << predicted_count << " " << count << endl;
1787
CheckVectors(bvect_min1, bvect_full1, BITVECT_SIZE/10+10);
1788
CheckCountRange(bvect_full1, 0, BITVECT_SIZE/10+10);
1794
bvect_mini bvect_min1(BITVECT_SIZE);
1795
bvect_mini bvect_min2(BITVECT_SIZE);
1799
bvect_full1.set_new_blocks_strat(bm::BM_BIT);
1800
bvect_full2.set_new_blocks_strat(bm::BM_BIT);
1802
cout << "------------------------------" << endl;
1803
printf("SUB test stage 3.\n");
1806
FillSets(&bvect_min1, &bvect_full1, 1, BITVECT_SIZE/5, 2);
1807
FillSets(&bvect_min2, &bvect_full2, 1, BITVECT_SIZE/5, 2);
1809
bvect_min1.combine_sub(bvect_min2);
1811
bm::id_t predicted_count = bm::count_sub(bvect_full1, bvect_full2);
1813
bvect_full1.bit_sub(bvect_full2);
1815
bm::id_t count = bvect_full1.count();
1816
if (count != predicted_count)
1818
cout << "Predicted count error!" << endl;
1823
CheckVectors(bvect_min1, bvect_full1, BITVECT_SIZE);
1825
bvect_full1.optimize();
1826
CheckVectors(bvect_min1, bvect_full1, BITVECT_SIZE);
1827
CheckCountRange(bvect_full1, 0, BITVECT_SIZE);
1836
void XorOperationsTest()
1838
assert(ITERATIONS < BITVECT_SIZE);
1840
cout << "----------------------------------- XorOperationTest" << endl;
1844
bvect_mini bvect_min1(256);
1845
bvect_mini bvect_min2(256);
1849
bvect_full1.set_new_blocks_strat(bm::BM_GAP);
1850
bvect_full2.set_new_blocks_strat(bm::BM_GAP);
1854
printf("XOR test\n");
1856
bvect_min1.set_bit(1);
1857
bvect_min1.set_bit(12);
1858
bvect_min1.set_bit(13);
1860
bvect_min2.set_bit(12);
1861
bvect_min2.set_bit(13);
1863
bvect_min1.combine_xor(bvect_min2);
1865
bvect_full1.set_bit(1);
1866
bvect_full1.set_bit(12);
1867
bvect_full1.set_bit(13);
1869
bvect_full2.set_bit(12);
1870
bvect_full2.set_bit(13);
1872
bm::id_t predicted_count = bm::count_xor(bvect_full1, bvect_full2);
1874
bvect_full1.bit_xor(bvect_full2);
1876
bm::id_t count = bvect_full1.count();
1877
if (count != predicted_count)
1879
cout << "1.Predicted count error!" << endl;
1883
CheckVectors(bvect_min1, bvect_full1, 256);
1884
CheckCountRange(bvect_full1, 0, 256);
1885
CheckCountRange(bvect_full1, 128, 256);
1891
bvect_mini bvect_min1(BITVECT_SIZE);
1894
bvect_mini bvect_min2(BITVECT_SIZE);
1897
for (int i = 0; i < 150000; ++i)
1900
bvect_min2.set_bit(i);
1905
bm::id_t predicted_count = bm::count_xor(bvect1, bvect2);
1907
bvect1.bit_xor(bvect2);
1909
bm::id_t count = bvect1.count();
1910
if (count != predicted_count)
1912
cout << "2.Predicted count error!" << endl;
1916
bvect_min1.combine_xor(bvect_min2);
1917
CheckVectors(bvect_min1, bvect1, BITVECT_SIZE, true);
1918
CheckCountRange(bvect1, 0, BITVECT_SIZE);
1924
bvect_mini bvect_min1(BITVECT_SIZE);
1927
bvect_mini bvect_min2(BITVECT_SIZE);
1930
for (int i = 0; i < 150000; ++i)
1933
bvect_min1.set_bit(i);
1938
bm::id_t predicted_count = bm::count_xor(bvect1, bvect2);
1940
bvect1.bit_xor(bvect2);
1942
bm::id_t count = bvect1.count();
1943
if (count != predicted_count)
1945
cout << "3.Predicted count error!" << endl;
1949
bvect_min1.combine_xor(bvect_min2);
1950
CheckVectors(bvect_min1, bvect1, BITVECT_SIZE, true);
1956
bvect_mini bvect_min1(BITVECT_SIZE);
1959
bvect_mini bvect_min2(BITVECT_SIZE);
1962
for (int i = 0; i < 150000; ++i)
1965
bvect_min1.set_bit(i);
1967
bvect_min2.set_bit(i);
1972
bm::id_t predicted_count = bm::count_xor(bvect1, bvect2);
1974
bvect1.bit_xor(bvect2);
1976
bm::id_t count = bvect1.count();
1977
if (count != predicted_count)
1979
cout << "4.Predicted count error!" << endl;
1980
cout << count << " " << predicted_count << endl;
1985
bvect_min1.combine_xor(bvect_min2);
1986
CheckVectors(bvect_min1, bvect1, BITVECT_SIZE, true);
1993
bvect_mini bvect_min1(BITVECT_SIZE);
1994
bvect_mini bvect_min2(BITVECT_SIZE);
1998
bvect_full1.set_new_blocks_strat(bm::BM_GAP);
1999
bvect_full2.set_new_blocks_strat(bm::BM_GAP);
2001
printf("XOR test stage 2.\n");
2004
FillSets(&bvect_min1, &bvect_full1, 1, BITVECT_SIZE/7, 0);
2005
FillSets(&bvect_min2, &bvect_full2, 1, BITVECT_SIZE/7, 0);
2007
bvect_min1.combine_xor(bvect_min2);
2009
bm::id_t predicted_count = bm::count_xor(bvect_full1, bvect_full2);
2011
bvect_full1.bit_xor(bvect_full2);
2013
bm::id_t count = bvect_full1.count();
2014
if (count != predicted_count)
2016
cout << "5.Predicted count error!" << endl;
2017
cout << count << " " << predicted_count << endl;
2022
CheckVectors(bvect_min1, bvect_full1, BITVECT_SIZE/10+10);
2023
CheckCountRange(bvect_full1, 0, BITVECT_SIZE/10+10);
2029
bvect_mini bvect_min1(BITVECT_SIZE);
2030
bvect_mini bvect_min2(BITVECT_SIZE);
2034
bvect_full1.set_new_blocks_strat(bm::BM_BIT);
2035
bvect_full2.set_new_blocks_strat(bm::BM_BIT);
2037
cout << "------------------------------" << endl;
2038
printf("XOR test stage 3.\n");
2041
FillSets(&bvect_min1, &bvect_full1, 1, BITVECT_SIZE/5, 2);
2042
FillSets(&bvect_min2, &bvect_full2, 1, BITVECT_SIZE/5, 2);
2044
bm::id_t predicted_count = bm::count_xor(bvect_full1, bvect_full2);
2046
bvect_min1.combine_xor(bvect_min2);
2048
bvect_full1.bit_xor(bvect_full2);
2050
bm::id_t count = bvect_full1.count();
2051
if (count != predicted_count)
2053
cout << "6.Predicted count error!" << endl;
2058
CheckVectors(bvect_min1, bvect_full1, BITVECT_SIZE);
2060
bvect_full1.optimize();
2061
CheckVectors(bvect_min1, bvect_full1, BITVECT_SIZE);
2062
CheckCountRange(bvect_full1, 0, BITVECT_SIZE);
2068
cout << "Testing combine_xor" << endl;
2074
bvect_mini bvect_min1(BITVECT_SIZE);
2076
bvect_full1.set_new_blocks_strat(bm::BM_GAP);
2077
bvect_full2.set_new_blocks_strat(bm::BM_GAP);
2079
unsigned ids[10000];
2080
unsigned to_add = 10000;
2083
for (unsigned i = 0; i < to_add; ++i)
2086
bvect_full2.set(bn);
2087
bvect_min1.set_bit(bn);
2091
unsigned* first = ids;
2092
unsigned* last = ids + to_add;
2094
bm::combine_xor(bvect_full1, first, last);
2096
CheckVectors(bvect_min1, bvect_full1, BITVECT_SIZE);
2098
bm::combine_xor(bvect_full1, first, last);
2099
if (bvect_full1.count())
2101
cout << "combine_xor count failed!" << endl;
2111
bvect_mini bvect_min1(BITVECT_SIZE);
2113
bvect_full1.set_new_blocks_strat(bm::BM_GAP);
2114
bvect_full2.set_new_blocks_strat(bm::BM_GAP);
2116
unsigned ids[10000]={0,};
2117
unsigned to_add = 10000;
2119
for (unsigned i = 0; i < to_add; i+=100)
2123
bvect_min1.set_bit(i);
2125
unsigned* first = ids;
2126
unsigned* last = ids + to_add;
2128
bm::combine_xor(bvect_full1, first, last);
2130
CheckVectors(bvect_min1, bvect_full1, BITVECT_SIZE);
2132
bm::combine_xor(bvect_full1, first, last);
2133
if (bvect_full1.count())
2135
cout << "combine_xor count failed!" << endl;
2143
unsigned ids[] = {0, 65536, 65535, 65535*3, 65535*2, 10};
2144
unsigned to_add = sizeof(ids)/sizeof(unsigned);
2147
bvect_mini bvect_min1(BITVECT_SIZE);
2149
bvect_full1.set_new_blocks_strat(bm::BM_BIT);
2150
bvect_full2.set_new_blocks_strat(bm::BM_BIT);
2153
for (unsigned i = 0; i < to_add; ++i)
2156
bvect_full2.set(bn);
2157
bvect_min1.set_bit(bn);
2161
unsigned* first = ids;
2162
unsigned* last = ids + to_add;
2164
bm::combine_xor(bvect_full1, first, last);
2165
CheckVectors(bvect_min1, bvect_full1, BITVECT_SIZE);
2167
bm::combine_xor(bvect_full1, first, last);
2168
if (bvect_full1.count())
2170
cout << "combine_xor count failed!" << endl;
2177
unsigned ids[] = {0, 65536, 65535, 65535*3, 65535*2, 10};
2178
unsigned to_add = sizeof(ids)/sizeof(unsigned);
2181
bvect_mini bvect_min1(BITVECT_SIZE);
2183
bvect_full1.set_new_blocks_strat(bm::BM_GAP);
2184
bvect_full2.set_new_blocks_strat(bm::BM_GAP);
2187
for (unsigned i = 0; i < to_add; ++i)
2190
bvect_full2.set(bn);
2191
bvect_min1.set_bit(bn);
2195
unsigned* first = ids;
2196
unsigned* last = ids + to_add;
2198
bm::combine_xor(bvect_full1, first, last);
2199
CheckVectors(bvect_min1, bvect_full1, BITVECT_SIZE);
2201
bm::combine_xor(bvect_full1, first, last);
2202
if (bvect_full1.count())
2204
cout << "combine_xor count failed!" << endl;
2212
void ComparisonTest()
2214
cout << "-------------------------------------- ComparisonTest" << endl;
2216
bvect_mini bvect_min1(BITVECT_SIZE);
2217
bvect_mini bvect_min2(BITVECT_SIZE);
2222
bvect_full1.set_bit(31);
2223
bvect_full2.set_bit(63);
2225
res1 = bvect_full1.compare(bvect_full2);
2228
printf("Comparison test failed 1\n");
2232
bvect_full1.clear();
2233
bvect_full2.clear();
2235
bvect_min1.set_bit(10);
2236
bvect_min2.set_bit(10);
2238
bvect_full1.set_bit(10);
2239
bvect_full2.set_bit(10);
2241
res1 = bvect_min1.compare(bvect_min2);
2242
res2 = bvect_full1.compare(bvect_full2);
2246
printf("Comparison test failed 1\n");
2250
printf("Comparison 2.\n");
2252
bvect_min1.set_bit(11);
2253
bvect_full1.set_bit(11);
2255
res1 = bvect_min1.compare(bvect_min2);
2256
res2 = bvect_full1.compare(bvect_full2);
2258
if (res1 != res2 && res1 != 1)
2260
printf("Comparison test failed 2\n");
2264
res1 = bvect_min2.compare(bvect_min1);
2265
res2 = bvect_full2.compare(bvect_full1);
2267
if (res1 != res2 && res1 != -1)
2269
printf("Comparison test failed 2.1\n");
2273
printf("Comparison 3.\n");
2275
bvect_full1.optimize();
2277
res1 = bvect_min1.compare(bvect_min2);
2278
res2 = bvect_full1.compare(bvect_full2);
2280
if (res1 != res2 && res1 != 1)
2282
printf("Comparison test failed 3\n");
2286
res1 = bvect_min2.compare(bvect_min1);
2287
res2 = bvect_full2.compare(bvect_full1);
2289
if (res1 != res2 && res1 != -1)
2291
printf("Comparison test failed 3.1\n");
2295
printf("Comparison 4.\n");
2297
bvect_full2.optimize();
2299
res1 = bvect_min1.compare(bvect_min2);
2300
res2 = bvect_full1.compare(bvect_full2);
2302
if (res1 != res2 && res1 != 1)
2304
printf("Comparison test failed 4\n");
2308
res1 = bvect_min2.compare(bvect_min1);
2309
res2 = bvect_full2.compare(bvect_full1);
2311
if (res1 != res2 && res1 != -1)
2313
printf("Comparison test failed 4.1\n");
2317
printf("Comparison 5.\n");
2320
for (i = 0; i < 65536; ++i)
2322
bvect_full1.set_bit(i);
2325
res1 = bvect_min1.compare(bvect_min2);
2326
res2 = bvect_full1.compare(bvect_full2);
2328
if (res1 != res2 && res1 != 1)
2330
printf("Comparison test failed 5\n");
2334
bvect_full1.optimize();
2336
res1 = bvect_min2.compare(bvect_min1);
2337
res2 = bvect_full2.compare(bvect_full1);
2339
if (res1 != res2 && res1 != -1)
2341
printf("Comparison test failed 5.1\n");
2347
void DesrializationTest2()
2350
unsigned size = BITVECT_SIZE - 10;
2356
for (i = 10; i < 165536; i+=2)
2364
struct bvect::statistics st1;
2365
bv1.calc_stat(&st1);
2368
unsigned char* sermem = new unsigned char[st1.max_serialize_mem];
2370
unsigned slen2 = bm::serialize(bv1, sermem);
2374
bm::deserialize(bvtotal, sermem);
2377
for (i = 55000; i < 165536; ++i)
2384
struct bvect::statistics st2;
2385
bv2.calc_stat(&st2);
2387
unsigned char* sermem2 = new unsigned char[st2.max_serialize_mem];
2389
unsigned slen = bm::serialize(bv2, sermem2);
2393
bm::deserialize(bvtotal, sermem2);
2396
// bvtotal.optimize();
2399
bm::deserialize(bvtotal, sermem2);
2401
bm::deserialize(bvtotal, sermem);
2411
int repetitions = 25;
2412
for (i = 0; i < repetitions; ++i)
2414
cout << endl << "Deserialization STEP " << i << endl;
2416
bvect_mini* bvect_min1= new bvect_mini(size);
2417
bvect* bvect_full1= new bvect();
2419
FillSetsRandomMethod(bvect_min1, bvect_full1, 1, size, 1);
2421
struct bvect::statistics st;
2422
bvect_full1->calc_stat(&st);
2424
unsigned char* sermem = new unsigned char[st.max_serialize_mem];
2426
unsigned slen = bm::serialize(*bvect_full1, sermem);
2428
unsigned char* smem = new unsigned char[slen];
2429
::memcpy(smem, sermem, slen);
2431
// cout << "Serialized vector" << endl;
2432
// bvect_full1->stat();
2434
// cout << "Before deserialization" << endl;
2436
bm::deserialize(bvtotal, smem);
2438
// cout << "After deserialization" << endl;
2443
// cout << "After optimization" << endl;
2452
// cout << "Post clear." << endl;
2467
void StressTest(int repetitions)
2470
unsigned RatioSum = 0;
2471
unsigned SRatioSum = 0;
2472
unsigned DeltaSum = 0;
2473
unsigned SDeltaSum = 0;
2475
unsigned clear_count = 0;
2478
bvtotal.set_new_blocks_strat(bm::BM_GAP);
2481
cout << "----------------------------StressTest" << endl;
2483
unsigned size = BITVECT_SIZE - 10;
2484
//size = BITVECT_SIZE / 10;
2486
for (i = 0; i < repetitions; ++i)
2488
cout << endl << " - - - - - - - - - - - - STRESS STEP " << i << endl;
2493
size = BITVECT_SIZE / 10;
2496
size = BITVECT_SIZE / 2;
2499
size = BITVECT_SIZE - 10;
2504
bvect_mini* bvect_min1= new bvect_mini(size);
2505
bvect_mini* bvect_min2= new bvect_mini(size);
2506
bvect* bvect_full1= new bvect();
2507
bvect* bvect_full2= new bvect();
2509
bvect_full1->set_new_blocks_strat(i&1 ? bm::BM_GAP : bm::BM_BIT);
2510
bvect_full2->set_new_blocks_strat(i&1 ? bm::BM_GAP : bm::BM_BIT);
2512
int opt = rand() % 2;
2514
unsigned start1 = 0;
2525
unsigned start2 = 0;
2541
FillSetsRandomMethod(bvect_min1, bvect_full1, start1, size, opt);
2542
FillSetsRandomMethod(bvect_min2, bvect_full2, start2, size, opt);
2546
unsigned arr[bm::set_total_blocks]={0,};
2547
bm::id_t cnt = bvect_full1->count();
2548
unsigned last_block = bvect_full1->count_blocks(arr);
2549
unsigned sum = bm::sum_arr(&arr[0], &arr[last_block+1]);
2553
cout << "Error in function count_blocks." << endl;
2554
cout << "Array sum = " << sum << endl;
2555
cout << "BitCount = " << cnt << endl;
2556
cnt = bvect_full1->count();
2557
for (unsigned i = 0; i <= last_block; ++i)
2561
cout << "[" << i << ":" << arr[i] << "]";
2565
cout << "================" << endl;
2566
bvect_full1->stat();
2572
CheckCountRange(*bvect_full1, start1, BITVECT_SIZE, arr);
2573
CheckIntervals(*bvect_full1, BITVECT_SIZE);
2578
CheckCountRange(*bvect_full2, start2, BITVECT_SIZE);
2580
CheckCountRange(*bvect_full1, 0, start1, arr);
2581
CheckCountRange(*bvect_full2, 0, start2);
2585
cout << "!!!!!!!!!!!!!!!" << endl;
2586
CheckVectors(*bvect_min1, *bvect_full1, size);
2587
cout << "!!!!!!!!!!!!!!!" << endl;
2588
CheckVectors(*bvect_min2, *bvect_full2, size);
2589
cout << "!!!!!!!!!!!!!!!" << endl;
2592
bvect_full1->stat();
2593
cout << " --" << endl;
2594
bvect_full2->stat();
2597
int operation = rand()%4;
2603
cout << "Operation OR" << endl;
2604
bvect_min1->combine_or(*bvect_min2);
2608
cout << "Operation SUB" << endl;
2609
bvect_min1->combine_sub(*bvect_min2);
2613
cout << "Operation XOR" << endl;
2614
bvect_min1->combine_xor(*bvect_min2);
2618
cout << "Operation AND" << endl;
2619
bvect_min1->combine_and(*bvect_min2);
2623
int cres1 = bvect_min1->compare(*bvect_min2);
2631
cout << "Operation OR" << endl;
2633
bm::id_t predicted_count = bm::count_or(*bvect_full1, *bvect_full2);
2635
bvect_full1->bit_or(*bvect_full2);
2637
bm::id_t count = bvect_full1->count();
2639
if (count != predicted_count)
2641
cout << "Predicted count error!" << endl;
2642
cout << "Count = " << count << "Predicted count = " << predicted_count << endl;
2651
cout << "Operation SUB" << endl;
2653
bm::id_t predicted_count = bm::count_sub(*bvect_full1, *bvect_full2);
2655
bvect_full1->bit_sub(*bvect_full2);
2657
bm::id_t count = bvect_full1->count();
2659
if (count != predicted_count)
2661
cout << "Predicted count error!" << endl;
2662
cout << "Count = " << count << "Predicted count = " << predicted_count << endl;
2672
cout << "Operation XOR" << endl;
2674
bm::id_t predicted_count = bm::count_xor(*bvect_full1, *bvect_full2);
2676
bvect_full1->bit_xor(*bvect_full2);
2678
bm::id_t count = bvect_full1->count();
2680
if (count != predicted_count)
2682
cout << "Predicted count error!" << endl;
2683
cout << "Count = " << count << "Predicted count = " << predicted_count << endl;
2693
cout << "Operation AND" << endl;
2695
bm::id_t predicted_count = bm::count_and(*bvect_full1, *bvect_full2);
2697
bvect_full1->bit_and(*bvect_full2);
2699
bm::id_t count = bvect_full1->count();
2701
if (count != predicted_count)
2703
cout << "Predicted count error!" << endl;
2704
cout << "Count = " << count << "Predicted count = " << predicted_count << endl;
2712
cout << "Operation comparison" << endl;
2713
CheckVectors(*bvect_min1, *bvect_full1, size);
2715
int cres2 = bvect_full1->compare(*bvect_full2);
2717
CheckIntervals(*bvect_full1, BITVECT_SIZE);
2721
cout << cres1 << " " << cres2 << endl;
2722
cout << bvect_full1->get_first() << " " << bvect_full1->count() << endl;
2723
cout << bvect_full2->get_first() << " " << bvect_full2->count() << endl;
2725
// bvect_full1->stat(1000);
2727
// bvect_full2->stat(1000);
2728
printf("Bitset comparison operation failed.\n");
2735
struct bvect::statistics st1;
2736
bvect_full1->calc_stat(&st1);
2737
bvect_full1->optimize();
2738
bvect_full1->optimize_gap_size();
2739
struct bvect::statistics st2;
2740
bvect_full1->calc_stat(&st2);
2742
unsigned Ratio = (st2.memory_used * 100)/st1.memory_used;
2744
DeltaSum+=st1.memory_used - st2.memory_used;
2746
cout << "Optimization statistics: " << endl
2747
<< " MemUsedBefore=" << st1.memory_used
2748
<< " MemUsed=" << st2.memory_used
2749
<< " Ratio=" << Ratio << "%"
2750
<< " Delta=" << st1.memory_used - st2.memory_used
2753
cout << "Optimization comparison" << endl;
2755
CheckVectors(*bvect_min1, *bvect_full1, size);
2757
bvect_full1->set_gap_levels(gap_len_table_min<true>::_len);
2758
CheckVectors(*bvect_min1, *bvect_full1, size);
2759
CheckIntervals(*bvect_full1, BITVECT_SIZE);
2761
//CheckCountRange(*bvect_full1, 0, size);
2765
bvect_full1->calc_stat(&st2);
2767
cout << "Memory allocation: " << st2.max_serialize_mem << endl;
2768
unsigned char* sermem = new unsigned char[st2.max_serialize_mem];
2770
// bvect_full1->stat();
2772
cout << "Serialization...";
2773
unsigned slen = bm::serialize(*bvect_full1, sermem);
2774
cout << "Ok" << endl;
2778
unsigned SRatio = (slen*100)/st2.memory_used;
2780
SDeltaSum+=st2.memory_used - slen;
2783
cout << "Serialized mem_max = " << st2.max_serialize_mem
2784
<< " size= " << slen
2785
<< " Ratio=" << SRatio << "%"
2786
<< " Delta=" << st2.memory_used - slen
2789
bvect* bvect_full3= new bvect();
2790
unsigned char* new_sermem = new unsigned char[slen];
2791
memcpy(new_sermem, sermem, slen);
2794
cout << "Deserialization...";
2796
bm::deserialize(*bvect_full3, new_sermem);
2798
bm::deserialize(bvtotal, new_sermem);
2800
cout << "Ok." << endl;
2801
delete [] new_sermem;
2803
cout << "Optimization...";
2805
cout << "Ok." << endl;
2809
if (clear_count == 4)
2815
cout << "Serialization comparison" << endl;
2816
CheckVectors(*bvect_min1, *bvect_full3, size, true);
2825
cout << "Repetitions:" << i <<
2826
" AVG optimization ratio:" << RatioSum/i
2827
<< " AVG Delta:" << DeltaSum/i
2829
<< " AVG serialization Ratio:"<< SRatioSum/i
2830
<< " Delta:" << SDeltaSum/i
2836
cout << "-------------------------------------------GAPCheck" << endl;
2841
bvect_mini bvect_min(bm::gap_max_bits);
2844
for( i = 0; i < 454; ++i)
2846
bvect_min.set_bit(i);
2850
for(i = 0; i < 254; ++i)
2852
bvect_min.clear_bit(i);
2856
for(i = 5; i < 10; ++i)
2858
bvect_min.set_bit(i);
2862
for( i = 0; i < bm::gap_max_bits; ++i)
2864
int bit1 = (gapv.is_bit_true(i) == 1);
2865
int bit2 = (bvect_min.is_bit_true(i) != 0);
2866
int bit3 = (gapv.test(i) == 1);
2869
cout << "problem with bit comparison " << i << endl;
2874
cout << "problem with bit test comparison " << i << endl;
2885
int bit = gapv.is_bit_true(65535);
2889
cout << "Bit != 1" << endl;
2894
for (i = 0; i < 65536; ++i)
2896
bit = gapv.is_bit_true(i);
2899
cout << "2.Bit != 1" << endl;
2903
unsigned cnt = gapv.count_range(0, 65535);
2906
cout << "count_range failed:" << cnt << endl;
2910
CheckCountRange(gapv, 10, 20);
2911
CheckCountRange(gapv, 0, 20);
2913
printf("gapv 1 check ok\n");
2920
int bit = gapv.is_bit_true(65535);
2921
int bit1 = gapv.test(65535);
2924
cout << "Bit != 0" << endl;
2929
for (i = 0; i < 65536; ++i)
2931
bit = gapv.is_bit_true(i);
2932
bit1 = gapv.test(i);
2935
cout << "2.Bit != 0 bit =" << i << endl;
2940
cout << "2.Bit test != 0 bit =" << i << endl;
2944
unsigned cnt = gapv.count_range(0, 65535);
2947
cout << "count_range failed:" << cnt << endl;
2950
CheckCountRange(gapv, 10, 20);
2951
CheckCountRange(gapv, 0, 20);
2953
printf("gapv 2 check ok\n");
2963
CheckCountRange(gapv, 0, 20);
2965
int bit = gapv.is_bit_true(0);
2969
cout << "Trouble" << endl;
2973
bit = gapv.is_bit_true(1);
2976
cout << "Trouble 2." << endl;
2981
bit = gapv.is_bit_true(2);
2984
cout << "Trouble 3." << endl;
3002
CheckCountRange(gapv, 4, 5);
3003
CheckCountRange(gapv, 3, 5);
3006
CheckCountRange(gapv, 3, 3);
3007
CheckCountRange(gapv, 3, 5);
3011
int bit = gapv.is_bit_true(0);
3014
cout << "Bug" << endl;
3016
bit = gapv.is_bit_true(1);
3019
cout << "Bug2" << endl;
3027
printf("gapv 3 check ok\n");
3032
bvect_mini bvect_min(bm::gap_max_bits);
3033
cout << "++++++1" << endl;
3034
print_gap(gapv, 10);
3035
gapv.set_bit(bm::gap_max_bits-1);
3037
print_gap(gapv, 10);
3039
//cout << "++++++2" << endl;
3040
//cout << "m_buf=" << bvect_min.m_buf << endl;
3042
bvect_min.set_bit(bm::gap_max_bits-1);
3043
cout << "++++++3" << endl;
3047
bvect_min.set_bit(5);
3048
cout << "++++++4" << endl;
3050
CheckCountRange(gapv, 13, 150);
3054
for (i = 0; i < bm::gap_max_bits; ++i)
3058
int bit1 = (gapv.is_bit_true(i) == 1);
3059
int bit2 = (bvect_min.is_bit_true(i) != 0);
3060
int bit3 = (gapv.test(i) == 1);
3063
cout << "problem with bit comparison " << i << endl;
3067
cout << "problem with bit test comparison " << i << endl;
3073
bvect_min.clear_bit(5);
3076
for ( i = 0; i < bm::gap_max_bits; ++i)
3080
int bit1 = (gapv.is_bit_true(i) == 1);
3081
int bit2 = (bvect_min.is_bit_true(i) != 0);
3082
int bit3 = (gapv.test(i) == 1);
3085
cout << "2.problem with bit comparison " << i << endl;
3089
cout << "2.problem with bit test comparison " << i << endl;
3092
printf("gapv check 4 ok.\n");
3097
bvect_mini bvect_min(65536);
3100
for (i = 10; i > 0; i-=2)
3102
bvect_min.set_bit(i);
3105
CheckCountRange(gapv, 0, i);
3107
int bit1 = (gapv.is_bit_true(i) == 1);
3108
int bit2 = (bvect_min.is_bit_true(i) != 0);
3109
int bit3 = (gapv.test(i) != 0);
3112
cout << "3.problem with bit comparison " << i << endl;
3116
cout << "3.problem with bit test comparison " << i << endl;
3120
for (i = 0; i < (int)bm::gap_max_bits; ++i)
3122
int bit1 = (gapv.is_bit_true(i) == 1);
3123
int bit2 = (bvect_min.is_bit_true(i) != 0);
3124
int bit3 = (gapv.test(i) == 1);
3128
cout << "3.problem with bit comparison " << i << endl;
3132
cout << "3.problem with bit test comparison " << i << endl;
3135
printf("gapv check 5 ok.\n");
3140
bvect_mini bvect_min(bm::gap_max_bits);
3143
for (i = 0; i < 25; ++i)
3145
unsigned id = random_minmax(0, bm::gap_max_bits);
3146
bvect_min.set_bit(id);
3149
CheckCountRange(gapv, 0, id);
3150
CheckCountRange(gapv, id, 65535);
3153
for (i = 0; i < (int)bm::gap_max_bits; ++i)
3155
int bit1 = (gapv.is_bit_true(i) == 1);
3156
int bit2 = (bvect_min.is_bit_true(i) != 0);
3159
cout << "4.problem with bit comparison " << i << endl;
3163
for (i = bm::gap_max_bits; i < 0; --i)
3165
int bit1 = (gapv.is_bit_true(i) == 1);
3166
int bit2 = (bvect_min.is_bit_true(i) != 0);
3169
cout << "5.problem with bit comparison " << i << endl;
3172
printf("gapv check 6 ok.\n");
3176
printf("gapv random bit set check ok.\n");
3179
// conversion functions test
3182
// aligned position test
3189
unsigned* buf = (unsigned*) bvect.get_block(0);
3191
bm::or_bit_block(buf, 0, 4);
3192
unsigned cnt = bm::bit_block_calc_count_range(buf, 0, 3);
3195
bool bit = bvect.get_bit(0);
3197
bit = bvect.get_bit(1);
3199
bit = bvect.get_bit(2);
3201
bit = bvect.get_bit(3);
3203
bit = bvect.get_bit(4);
3206
bm::or_bit_block(buf, 0, 36);
3207
cnt = bm::bit_block_calc_count_range(buf, 0, 35);
3210
for (int i = 0; i < 36; ++i)
3212
bit = (bvect.get_bit(i) != 0);
3215
bit = (bvect.get_bit(36) != 0);
3218
unsigned count = bvect.recalc_count();
3219
assert(count == 36);
3221
cout << "Aligned position test ok." << endl;
3227
// unaligned position test
3233
unsigned* buf = (unsigned*) bvect.get_block(0);
3235
bm::or_bit_block(buf, 5, 32);
3236
bool bit = (bvect.get_bit(4) != 0);
3238
unsigned cnt = bm::bit_block_calc_count_range(buf, 5, 5+32-1);
3240
cnt = bm::bit_block_calc_count_range(buf, 5, 5+32);
3244
for (i = 5; i < 4 + 32; ++i)
3246
bit = bvect.get_bit(i);
3249
int count = bvect.recalc_count();
3252
cout << "Unaligned position ok." << endl;
3258
cout << "random test" << endl;
3265
unsigned* buf = (unsigned*) bvect.get_block(0);
3266
for (int i = 0; i < 5000; ++i)
3268
unsigned start = rand() % 65535;
3269
unsigned end = rand() % 65535;
3276
unsigned len = end - start;
3279
bm::or_bit_block(buf, start, len);
3280
unsigned cnt = bm::bit_block_calc_count_range(buf, start, end);
3283
cout << "random test: count_range comparison failed. "
3284
<< " LEN = " << len << " cnt = " << cnt
3289
unsigned count = bvect.recalc_count();
3293
cout << "random test: count comparison failed. "
3294
<< " LEN = " << len << " count = " << count
3299
for (unsigned j = start; j < end; ++j)
3301
bool bit = bvect.get_bit(j);
3304
cout << "random test: bit comparison failed. bit#"
3315
cout << "*" << flush;
3319
cout << endl << "Random test Ok." << endl;
3326
cout << "Conversion test" << endl;
3339
CheckCountRange(gapv, 3, 15);
3341
print_gap(gapv, 100);
3345
unsigned* buf = (unsigned*) bvect.get_block(0);
3348
gapv.convert_to_bitset(buf);
3351
unsigned bitcount = bvect.recalc_count();
3356
cout << "test failed: bitcout = " << bitcount << endl;
3361
gap_vector gapv1(0);
3362
gap_word_t* gap_buf = gapv1.get_buf();
3364
bit_convert_to_gap(gap_buf, buf, bm::gap_max_bits, bm::gap_max_buff_len);
3365
print_gap(gapv1, 100);
3367
bitcount = gapv1.bit_count();
3370
cout << "2.test_failed: bitcout = " << bitcount << endl;
3374
printf("conversion test ok.\n");
3381
// special case 1: operand is all 1
3382
gap_vector gapv1(0);
3384
gap_vector gapv2(1);
3386
gapv1.combine_and(gapv2.get_buf());
3388
print_gap(gapv1, 0);
3390
int count = gapv1.bit_count();
3392
int bit = gapv1.is_bit_true(2);
3395
cout << "Wrong bit" << endl;
3398
CheckCountRange(gapv1, 0, 17);
3403
// special case 2: src is all 1
3404
gap_vector gapv1(1);
3405
gap_vector gapv2(0);
3408
gapv1.combine_and(gapv2.get_buf());
3410
print_gap(gapv1, 0);
3412
int count = gapv1.bit_count();
3414
int bit = gapv1.is_bit_true(2);
3421
gap_vector gapv1(0);
3425
print_gap(gapv1, 0);
3427
gap_vector gapv2(0);
3430
print_gap(gapv2, 0);
3432
bm::gap_buff_op((gap_word_t*)gapv.get_buf(),
3434
gapv2.get_buf(), 0, bm::and_op);
3439
int bit1 = (gapv.is_bit_true(3) == 1);
3442
cout << "Checking failed." << endl;
3446
gapv1.combine_or(gapv2);
3447
print_gap(gapv1, 0);
3453
printf("gap AND test 1.\n");
3454
gap_vector gapv1(0);
3455
gap_vector gapv2(0);
3456
bvect_mini bvect_min1(65536);
3457
bvect_mini bvect_min2(65536);
3459
gapv1.set_bit(65535);
3460
bvect_min1.set_bit(65535);
3462
bvect_min1.set_bit(4);
3464
gapv2.set_bit(65535);
3465
bvect_min2.set_bit(65535);
3467
bvect_min2.set_bit(3);
3468
CheckCountRange(gapv2, 3, 65535);
3472
printf("vect1:"); print_gap(gapv1, 0);
3473
printf("vect2:");print_gap(gapv2, 0);
3475
gapv1.combine_and(gapv2.get_buf());
3476
printf("vect1:");print_gap(gapv1, 0);
3479
unsigned bit1 = gapv1.is_bit_true(65535);
3482
bvect_min1.combine_and(bvect_min2);
3483
CheckGAPMin(gapv1, bvect_min1, bm::gap_max_bits);
3487
printf("gap random AND test.\n");
3488
gap_vector gapv1(0);
3489
gap_vector gapv2(0);
3490
bvect_mini bvect_min1(65536);
3491
bvect_mini bvect_min2(65536);
3494
for (i = 0; i < 25; ++i)
3496
unsigned id = random_minmax(0, 65535);
3497
bvect_min1.set_bit(id);
3500
CheckCountRange(gapv1, 0, id);
3501
CheckCountRange(gapv1, id, 65535);
3503
for (i = 0; i < 25; ++i)
3505
unsigned id = random_minmax(0, 65535);
3506
bvect_min2.set_bit(id);
3511
gapv1.combine_and(gapv2.get_buf());
3514
bvect_min1.combine_and(bvect_min2);
3516
CheckGAPMin(gapv1, bvect_min1, bm::gap_max_bits);
3518
printf("gap random AND test ok.\n");
3523
printf("gap OR test.\n");
3525
gap_vector gapv1(0);
3526
gap_vector gapv2(0);
3531
gapv1.combine_or(gapv2);
3533
print_gap(gapv1, 0);
3534
int bit1 = (gapv1.is_bit_true(0) == 1);
3536
bit1=(gapv1.is_bit_true(2) == 1);
3538
bit1=(gapv1.is_bit_true(3) == 1);
3543
printf("gap XOR test.\n");
3545
gap_vector gapv1(0);
3546
gap_vector gapv2(0);
3552
print_gap(gapv1, 0);
3553
print_gap(gapv2, 0);
3555
gapv1.combine_xor(gapv2);
3557
print_gap(gapv1, 0);
3558
int bit1 = (gapv1.is_bit_true(0) == 0);
3560
bit1=(gapv1.is_bit_true(2) == 1);
3562
bit1=(gapv1.is_bit_true(3) == 1);
3564
bit1=(gapv1.is_bit_true(4) == 0);
3572
printf("gap random OR test.\n");
3573
gap_vector gapv1(0);
3574
gap_vector gapv2(0);
3575
bvect_mini bvect_min1(bm::gap_max_bits);
3576
bvect_mini bvect_min2(bm::gap_max_bits);
3578
for (i = 0; i < 10; ++i)
3580
unsigned id = random_minmax(0, 100);
3581
bvect_min1.set_bit(id);
3585
for (i = 0; i < 10; ++i)
3587
unsigned id = random_minmax(0, 100);
3588
bvect_min2.set_bit(id);
3593
print_mv(bvect_min1, 64);
3594
print_mv(bvect_min2, 64);
3596
gapv1.combine_or(gapv2);
3599
bvect_min1.combine_or(bvect_min2);
3601
print_mv(bvect_min1, 64);
3603
CheckGAPMin(gapv1, bvect_min1, bm::gap_max_bits);
3605
printf("gap random OR test ok.\n");
3612
printf("gap random SUB test.\n");
3613
gap_vector gapv1(0);
3614
gap_vector gapv2(0);
3615
bvect_mini bvect_min1(bm::gap_max_bits);
3616
bvect_mini bvect_min2(bm::gap_max_bits);
3618
for (i = 0; i < 25; ++i)
3620
unsigned id = random_minmax(0, 100);
3621
bvect_min1.set_bit(id);
3625
for (i = 0; i < 25; ++i)
3627
unsigned id = random_minmax(0, 100);
3628
bvect_min2.set_bit(id);
3633
print_mv(bvect_min1, 64);
3634
print_mv(bvect_min2, 64);
3636
gapv1.combine_sub(gapv2);
3639
bvect_min1.combine_sub(bvect_min2);
3641
print_mv(bvect_min1, 64);
3643
CheckGAPMin(gapv1, bvect_min1, bm::gap_max_bits);
3645
printf("gap random SUB test ok.\n");
3649
printf("GAP comparison test.\n");
3651
gap_vector gapv1(0);
3652
gap_vector gapv2(0);
3657
int res = gapv1.compare(gapv2);
3660
printf("GAP comparison failed!");
3667
res = gapv1.compare(gapv2);
3670
printf("GAP comparison failed!");
3677
res = gapv1.compare(gapv2);
3680
printf("GAP comparison failed!");
3686
res = gapv1.compare(gapv2);
3689
printf("GAP comparison failed!");
3695
res = gapv1.compare(gapv2);
3698
printf("GAP comparison failed!");
3708
// -----------------------------------------------------------------------------
3713
cout << "--------------------------------- MutationTest" << endl;
3715
bvect_mini bvect_min(BITVECT_SIZE);
3718
printf("\nMutation test.\n");
3720
bvect_full.set_new_blocks_strat(bm::BM_GAP);
3722
bvect_full.set_bit(5);
3723
bvect_full.set_bit(5);
3725
bvect_min.set_bit(5);
3727
bvect_full.set_bit(65535);
3728
bvect_full.set_bit(65537);
3729
bvect_min.set_bit(65535);
3730
bvect_min.set_bit(65537);
3732
bvect_min.set_bit(100000);
3733
bvect_full.set_bit(100000);
3736
// detailed vectors verification
3737
::CheckVectors(bvect_min, bvect_full, ITERATIONS, false);
3740
for (i = 5; i < 20000; i+=3)
3742
bvect_min.set_bit(i);
3743
bvect_full.set_bit(i);
3746
::CheckVectors(bvect_min, bvect_full, ITERATIONS, false);
3748
for (i = 100000; i < 200000; i+=3)
3750
bvect_min.set_bit(i);
3751
bvect_full.set_bit(i);
3754
::CheckVectors(bvect_min, bvect_full, 300000);
3756
// set-clear functionality
3759
printf("Set-clear functionality test.");
3761
bvect_mini bvect_min(BITVECT_SIZE);
3763
bvect_full.set_new_blocks_strat(bm::BM_GAP);
3766
for (i = 100000; i < 100010; ++i)
3768
bvect_min.set_bit(i);
3769
bvect_full.set_bit(i);
3771
::CheckVectors(bvect_min, bvect_full, 300000);
3773
for (i = 100000; i < 100010; ++i)
3775
bvect_min.clear_bit(i);
3776
bvect_full.clear_bit(i);
3778
::CheckVectors(bvect_min, bvect_full, 300000);
3780
bvect_full.optimize();
3781
CheckVectors(bvect_min, bvect_full, 65536);//max+10);
3786
void MutationOperationsTest()
3789
cout << "------------------------------------ MutationOperationsTest" << endl;
3791
printf("Mutation operations test 1.\n");
3793
bvect_mini bvect_min1(BITVECT_SIZE);
3794
bvect_mini bvect_min2(BITVECT_SIZE);
3798
bvect_full1.set_new_blocks_strat(bm::BM_GAP);
3799
bvect_full2.set_new_blocks_strat(bm::BM_BIT);
3801
bvect_full1.set_bit(100);
3802
bvect_min1.set_bit(100);
3805
for(i = 0; i < 10000; i+=2)
3807
bvect_full2.set_bit(i);
3808
bvect_min2.set_bit(i);
3811
CheckVectors(bvect_min2, bvect_full2, 65536, true);
3813
bvect_min1.combine_and(bvect_min2);
3814
bvect_full1.bit_and(bvect_full2);
3816
CheckVectors(bvect_min1, bvect_full1, 65536);//max+10);
3820
printf("Mutation operations test 2.\n");
3822
unsigned delta = 65536;
3823
bvect_mini bvect_min1(BITVECT_SIZE);
3824
bvect_mini bvect_min2(BITVECT_SIZE);
3828
bvect_full1.set_new_blocks_strat(bm::BM_GAP);
3829
bvect_full2.set_new_blocks_strat(bm::BM_GAP);
3832
for(i = 0; i < 1000; i+=1)
3834
bvect_full1.set_bit(delta+i);
3835
bvect_min1.set_bit(delta+i);
3838
for(i = 0; i < 100; i+=2)
3840
bvect_full2.set_bit(delta+i);
3841
bvect_min2.set_bit(delta+i);
3843
// CheckVectors(bvect_min2, bvect_full2, 65536);
3845
bvect_min1.combine_and(bvect_min2);
3846
bvect_full1.bit_and(bvect_full2);
3848
CheckVectors(bvect_min1, bvect_full1, 65536);//max+10);
3849
bvect_full1.optimize();
3850
CheckVectors(bvect_min1, bvect_full1, 65536);//max+10);
3855
bvect_mini bvect_min1(BITVECT_SIZE);
3858
bvect_full1.set_bit(3);
3859
bvect_min1.set_bit(3);
3861
struct bvect::statistics st;
3862
bvect_full1.calc_stat(&st);
3866
unsigned char* sermem = new unsigned char[st.max_serialize_mem];
3867
unsigned slen = bm::serialize(bvect_full1, sermem);
3868
cout << "BVECTOR SERMEM=" << slen << endl;
3872
bm::deserialize(bvect_full3, sermem);
3874
CheckVectors(bvect_min1, bvect_full3, 100, true);
3878
printf("Mutation operations test 3.\n");
3880
bvect_mini bvect_min1(BITVECT_SIZE);
3881
bvect_mini bvect_min2(BITVECT_SIZE);
3885
bvect_full1.set_new_blocks_strat(bm::BM_GAP);
3886
bvect_full2.set_new_blocks_strat(bm::BM_GAP);
3889
unsigned min = BITVECT_SIZE / 2 - ITERATIONS;
3890
unsigned max = BITVECT_SIZE / 2 + ITERATIONS;
3891
if (max > BITVECT_SIZE)
3892
max = BITVECT_SIZE - 1;
3894
unsigned len = max - min;
3896
FillSets(&bvect_min1, &bvect_full1, min, max, 0);
3897
FillSets(&bvect_min1, &bvect_full1, 0, len, 5);
3898
printf("Bvect_FULL 1 STAT\n");
3900
// CheckVectors(bvect_min1, bvect_full1, max+10, false);
3901
FillSets(&bvect_min2, &bvect_full2, min, max, 0);
3902
FillSets(&bvect_min2, &bvect_full2, 0, len, 0);
3903
printf("Bvect_FULL 2 STAT\n");
3905
// CheckVectors(bvect_min2, bvect_full2, max+10);
3908
bvect_min1.combine_and(bvect_min2);
3909
bvect_full1.bit_and(bvect_full2);
3910
printf("Bvect_FULL 1 STAT after AND\n");
3913
CheckVectors(bvect_min1, bvect_full1, max+10, false);
3915
struct bvect::statistics st;
3916
bvect_full1.calc_stat(&st);
3917
cout << "BVECTOR: GAP=" << st.gap_blocks << " BIT=" << st.bit_blocks
3918
<< " MEM=" << st.memory_used << " SERMAX=" << st.max_serialize_mem
3920
cout << "MINIVECT: " << bvect_min1.mem_used() << endl;
3922
bvect_full1.optimize();
3925
CheckVectors(bvect_min1, bvect_full1, max+10, false);
3927
bvect_full1.calc_stat(&st);
3928
cout << "BVECTOR: GAP=" << st.gap_blocks << " BIT=" << st.bit_blocks
3929
<< " MEM=" << st.memory_used << " SERMAX=" << st.max_serialize_mem
3931
cout << "MINIVECT: " << bvect_min1.mem_used() << endl;
3937
unsigned char* sermem = new unsigned char[st.max_serialize_mem];
3938
unsigned slen = bm::serialize(bvect_full1, sermem);
3939
cout << "BVECTOR SERMEM=" << slen << endl;
3944
bm::deserialize(bvect_full3, sermem);
3946
CheckVectors(bvect_min1, bvect_full3, max+10, true);
3951
cout << "Copy constructor check." << endl;
3955
bvect bvect_full4(bvect_full3);
3957
CheckVectors(bvect_min1, bvect_full4, max+10, true);
3966
void SerializationTest()
3969
cout << " ----------------------------------- SerializationTest" << endl;
3971
cout << "Serialization STEP 0" << endl;
3974
unsigned size = BITVECT_SIZE/6000;
3977
bvect_mini* bvect_min1= new bvect_mini(BITVECT_SIZE);
3978
bvect* bvect_full1= new bvect();
3979
bvect* bvect_full2= new bvect();
3981
bvect_full1->set_new_blocks_strat(bm::BM_BIT);
3982
bvect_full2->set_new_blocks_strat(bm::BM_BIT);
3984
for(unsigned i = 0; i < size; ++i)
3986
bvect_full1->set_bit(i);
3987
bvect_min1->set_bit(i);
3990
bvect_full1->optimize();
3991
CheckVectors(*bvect_min1, *bvect_full1, size, true);
3995
bvect::statistics st;
3996
bvect_full1->calc_stat(&st);
3997
unsigned char* sermem = new unsigned char[st.max_serialize_mem];
3998
unsigned slen = bm::serialize(*bvect_full1, sermem);
3999
cout << "Serialized mem_max = " << st.max_serialize_mem
4000
<< " size= " << slen
4001
<< " Ratio=" << (slen*100)/st.max_serialize_mem << "%"
4004
bm::deserialize(*bvect_full2, sermem);
4008
CheckVectors(*bvect_min1, *bvect_full2, size, true);
4019
unsigned size = BITVECT_SIZE/6000;
4022
bvect_mini* bvect_min1= new bvect_mini(BITVECT_SIZE);
4023
bvect* bvect_full1= new bvect();
4024
bvect* bvect_full2= new bvect();
4026
bvect_full1->set_new_blocks_strat(bm::BM_BIT);
4027
bvect_full2->set_new_blocks_strat(bm::BM_BIT);
4029
bvect_full1->set_bit(131072);
4030
bvect_min1->set_bit(131072);
4033
bvect_full1->optimize();
4035
bvect::statistics st;
4036
bvect_full1->calc_stat(&st);
4037
unsigned char* sermem = new unsigned char[st.max_serialize_mem];
4038
unsigned slen = bm::serialize(*bvect_full1, sermem);
4039
cout << "Serialized mem_max = " << st.max_serialize_mem
4040
<< " size= " << slen
4041
<< " Ratio=" << (slen*100)/st.max_serialize_mem << "%"
4044
bm::deserialize(*bvect_full2, sermem);
4047
CheckVectors(*bvect_min1, *bvect_full2, size, true);
4056
cout << "Serialization STEP 1." << endl;
4059
bvect_mini bvect_min1(BITVECT_SIZE);
4062
bvect_full1.set_new_blocks_strat(bm::BM_GAP);
4064
unsigned min = BITVECT_SIZE / 2 - ITERATIONS;
4065
unsigned max = BITVECT_SIZE / 2 + ITERATIONS;
4066
if (max > BITVECT_SIZE)
4067
max = BITVECT_SIZE - 1;
4069
unsigned len = max - min;
4071
FillSets(&bvect_min1, &bvect_full1, min, max, 0);
4072
FillSets(&bvect_min1, &bvect_full1, 0, len, 5);
4074
// shot some random bits
4077
for (i = 0; i < 10000; ++i)
4079
unsigned bit = rand() % BITVECT_SIZE;
4080
bvect_full1.set_bit(bit);
4081
bvect_min1.set_bit(bit);
4084
bvect::statistics st;
4085
bvect_full1.calc_stat(&st);
4087
unsigned char* sermem = new unsigned char[st.max_serialize_mem];
4090
unsigned slen = bm::serialize(bvect_full1, sermem);
4092
cout << "Serialized len = " << slen << endl;
4095
bm::deserialize(bvect_full3, sermem);
4096
CheckVectors(bvect_min1, bvect_full3, max+10, true);
4103
cout << "Stage 2" << endl;
4107
bvect_mini* bvect_min1= new bvect_mini(BITVECT_SIZE);
4108
// bm::bvect_mini* bvect_min2= new bm::bvect_mini(BITVECT_SIZE);
4109
bvect* bvect_full1= new bvect();
4110
bvect* bvect_full2= new bvect();
4112
bvect_full1->set_new_blocks_strat(bm::BM_GAP);
4113
bvect_full2->set_new_blocks_strat(bm::BM_GAP);
4115
FillSetsRandomMethod(bvect_min1, bvect_full1, 1, BITVECT_SIZE-10, 1);
4116
// FillSetsRandomMethod(bvect_min2, bvect_full2, 1, BITVECT_SIZE-10, 1);
4118
//bvect_full1->stat();
4119
cout << "Filling. OK." << endl;
4120
bvect::statistics st;
4121
bvect_full1->calc_stat(&st);
4122
cout << st.max_serialize_mem << endl;
4123
unsigned char* sermem = new unsigned char[st.max_serialize_mem];
4124
cout << "Serialization" << endl;
4125
unsigned slen = bm::serialize(*bvect_full1, sermem);
4127
cout << "Serialized mem_max = " << st.max_serialize_mem
4128
<< " size= " << slen
4129
<< " Ratio=" << (slen*100)/st.max_serialize_mem << "%"
4131
cout << "Deserialization" << endl;
4132
bm::deserialize(*bvect_full2, sermem);
4133
cout << "Deserialization ok" << endl;
4135
CheckVectors(*bvect_min1, *bvect_full2, BITVECT_SIZE, true);
4148
cout << "Stage 3" << endl;
4152
bvect_mini* bvect_min1= new bvect_mini(BITVECT_SIZE);
4153
bvect_mini* bvect_min2= new bvect_mini(BITVECT_SIZE);
4154
bvect* bvect_full1= new bvect();
4155
bvect* bvect_full2= new bvect();
4157
bvect_full1->set_new_blocks_strat(bm::BM_GAP);
4158
bvect_full2->set_new_blocks_strat(bm::BM_GAP);
4161
FillSetsRandomMethod(bvect_min1, bvect_full1, 1, BITVECT_SIZE-10, 1);
4162
FillSetsRandomMethod(bvect_min2, bvect_full2, 1, BITVECT_SIZE-10, 1);
4164
bvect::statistics st;
4165
bvect_full1->calc_stat(&st);
4166
unsigned char* sermem = new unsigned char[st.max_serialize_mem];
4167
unsigned slen = bm::serialize(*bvect_full1, sermem);
4170
cout << "Serialized mem_max = " << st.max_serialize_mem
4171
<< " size= " << slen
4172
<< " Ratio=" << (slen*100)/st.max_serialize_mem << "%"
4174
bm::deserialize(*bvect_full2, sermem);
4177
bvect_min2->combine_or(*bvect_min1);
4180
CheckVectors(*bvect_min2, *bvect_full2, BITVECT_SIZE, true);
4189
cout << "Stage 4. " << endl;
4192
unsigned size = BITVECT_SIZE/3;
4195
bvect_mini* bvect_min1= new bvect_mini(BITVECT_SIZE);
4196
bvect* bvect_full1= new bvect();
4197
bvect* bvect_full2= new bvect();
4199
bvect_full1->set_new_blocks_strat(bm::BM_BIT);
4200
bvect_full2->set_new_blocks_strat(bm::BM_BIT);
4203
for(i = 0; i < 65000; ++i)
4205
bvect_full1->set_bit(i);
4206
bvect_min1->set_bit(i);
4209
for(i = 65536; i < 65536+65000; ++i)
4211
bvect_full1->set_bit(i);
4212
bvect_min1->set_bit(i);
4215
for (i = 65536*2; i < size/6; ++i)
4217
bvect_full1->set_bit(i);
4218
bvect_min1->set_bit(i);
4222
bvect_full1->optimize();
4224
bvect_full1->stat();
4227
bvect::statistics st;
4228
bvect_full1->calc_stat(&st);
4229
unsigned char* sermem = new unsigned char[st.max_serialize_mem];
4230
unsigned slen = bm::serialize(*bvect_full1, sermem);
4231
cout << "Serialized mem_max = " << st.max_serialize_mem
4232
<< " size= " << slen
4233
<< " Ratio=" << (slen*100)/st.max_serialize_mem << "%"
4236
unsigned char* new_sermem = new unsigned char[st.max_serialize_mem];
4237
::memcpy(new_sermem, sermem, slen);
4239
bm::deserialize(*bvect_full2, new_sermem);
4241
delete [] new_sermem;
4243
CheckVectors(*bvect_min1, *bvect_full2, size, true);
4257
cout << "-------------------------------------------- GetNextTest" << endl;
4260
for(i = 0; i < 2; ++i)
4262
cout << "Strategy " << i << endl;
4266
bvect_mini bvect_min1(BITVECT_SIZE);
4268
bvect_full1.set_new_blocks_strat(i ? bm::BM_GAP : bm::BM_BIT);
4270
bvect_full1.set_bit(0);
4271
bvect_min1.set_bit(0);
4274
bvect_full1.set_bit(65536);
4275
bvect_min1.set_bit(65536);
4277
unsigned nbit1 = bvect_full1.get_first();
4278
unsigned nbit2 = bvect_min1.get_first();
4282
cout << "1. get_first failed() " << nbit1 << " " << nbit2 << endl;
4285
nbit1 = bvect_full1.get_next(nbit1);
4286
nbit2 = bvect_min1.get_next(nbit2);
4287
if ((nbit1 != nbit2) || (nbit1 != 65536))
4289
cout << "1. get_next failed() " << nbit1 << " " << nbit2 << endl;
4298
bvect_mini bvect_min1(BITVECT_SIZE);
4299
bvect_full1.set_new_blocks_strat(i ? bm::BM_GAP : bm::BM_BIT);
4301
bvect_full1.set_bit(65535);
4302
bvect_min1.set_bit(65535);
4304
unsigned nbit1 = bvect_full1.get_first();
4305
unsigned nbit2 = bvect_min1.get_first();
4307
if ((nbit1 != nbit2) || (nbit1 != 65535))
4309
cout << "1. get_first failed() " << nbit1 << " " << nbit2 << endl;
4312
nbit1 = bvect_full1.get_next(nbit1);
4313
nbit2 = bvect_min1.get_next(nbit2);
4314
if (nbit1 != nbit2 )
4316
cout << "1. get_next failed() " << nbit1 << " " << nbit2 << endl;
4322
cout << "--------------" << endl;
4324
bvect_mini bvect_min1(BITVECT_SIZE);
4325
bvect_full1.set_new_blocks_strat(i ? bm::BM_GAP : bm::BM_BIT);
4327
bvect_full1.set_bit(655350);
4328
bvect_min1.set_bit(655350);
4330
unsigned nbit1 = bvect_full1.get_first();
4331
unsigned nbit2 = bvect_min1.get_first();
4333
if (nbit1 != nbit2 || nbit1 != 655350)
4335
cout << "1. get_first failed() " << nbit1 << " " << nbit2 << endl;
4339
nbit1 = bvect_full1.get_next(nbit1);
4340
nbit2 = bvect_min1.get_next(nbit2);
4343
cout << "1. get_next failed() " << nbit1 << " " << nbit2 << endl;
4351
bvect_mini bvect_min1(BITVECT_SIZE);
4353
bvect_full1.set_new_blocks_strat(i ? bm::BM_GAP : bm::BM_BIT);
4355
bvect_full1.set_bit(256);
4356
bvect_min1.set_bit(256);
4358
// bvect_full1.clear_bit(256);
4359
bvect_full1.set_bit(65536);
4360
bvect_min1.set_bit(65536);
4362
unsigned nbit1 = bvect_full1.get_first();
4363
unsigned nbit2 = bvect_min1.get_first();
4367
cout << "get_first failed " << nbit1 << " " << nbit2 << endl;
4373
cout << nbit1 << endl;
4374
nbit1 = bvect_full1.get_next(nbit1);
4375
nbit2 = bvect_min1.get_next(nbit2);
4378
cout << "get_next failed " << nbit1 << " " << nbit2 << endl;
4391
// Test contributed by Maxim Shemanarev.
4399
for(i = 0; i < 100; i++)
4401
int n = rand() % 2000 + 1;
4403
for(j = 0; j < n; j++)
4405
id += rand() % 10 + 1;
4411
fprintf(stderr, ".");
4416
void CalcBeginMask()
4418
printf("BeginMask:\n");
4421
for (i = 0; i < 32; ++i)
4425
for(int j = i; j < 32; ++j)
4428
nbit &= bm::set_word_mask;
4429
bm::word_t mask1 = (((bm::word_t)1) << j);
4434
printf("0x%x, ", mask);
4442
printf("EndMask:\n");
4445
for (i = 0; i < 32; ++i)
4449
for(int j = i; j > 0; --j)
4452
nbit &= bm::set_word_mask;
4453
bm::word_t mask1 = (((bm::word_t)1) << j);
4458
printf("0x%x,", mask);
4465
void EnumeratorTest()
4467
cout << "-------------------------------------------- EnumeratorTest" << endl;
4472
bvect1.set_bit(100);
4474
bvect::enumerator en = bvect1.first();
4478
cout << "Enumerator error !" << endl;
4482
bvect1.clear_bit(100);
4484
bvect1.set_bit(2000000000);
4487
if (*en != 2000000000)
4489
cout << "Enumerator error !" << endl;
4499
bvect1.set_bit(1000);
4500
bvect1.set_bit(2016519);
4501
bvect1.set_bit(2034779);
4502
bvect1.set_bit(bm::id_max-1);
4504
bvect::enumerator en = bvect1.first();
4506
unsigned num = bvect1.get_first();
4508
bvect::enumerator end = bvect1.end();
4513
cout << "Enumeration comparison failed !" <<
4514
" enumerator = " << *en <<
4515
" get_next() = " << num << endl;
4519
num = bvect1.get_next(num);
4523
cout << "Enumeration error!" << endl;
4532
bvect::enumerator en = bvect1.first();
4534
unsigned num = bvect1.get_first();
4536
while (en < bvect1.end())
4540
cout << "Enumeration comparison failed !" <<
4541
" enumerator = " << *en <<
4542
" get_next() = " << num << endl;
4547
num = bvect1.get_next(num);
4551
cout << "Enumeration error!" << endl;
4561
for(i = 0; i < 65536; ++i)
4566
for(i = 65536*10; i < 65536*20; i+=3)
4572
bvect::enumerator en = bvect1.first();
4574
unsigned num = bvect1.get_first();
4576
while (en < bvect1.end())
4580
cout << "Enumeration comparison failed !" <<
4581
" enumerator = " << *en <<
4582
" get_next() = " << num << endl;
4586
num = bvect1.get_next(num);
4594
cout << "Enumeration error!" << endl;
4602
bvect1.set_new_blocks_strat(bm::BM_GAP);
4603
bvect1.set_bit(100);
4605
bvect::enumerator en = bvect1.first();
4609
cout << "Enumerator error !" << endl;
4613
bvect1.clear_bit(100);
4615
bvect1.set_bit(2000000);
4620
cout << "Enumerator error !" << endl;
4628
bvect1.set_new_blocks_strat(bm::BM_GAP);
4632
bvect1.set_bit(100);
4633
bvect1.set_bit(1000);
4635
bvect::enumerator en = bvect1.first();
4637
unsigned num = bvect1.get_first();
4639
while (en < bvect1.end())
4643
cout << "Enumeration comparison failed !" <<
4644
" enumerator = " << *en <<
4645
" get_next() = " << num << endl;
4649
num = bvect1.get_next(num);
4653
cout << "Enumeration error!" << endl;
4663
void BlockLevelTest()
4668
bv.set_new_blocks_strat(bm::BM_GAP);
4669
bv2.set_new_blocks_strat(bm::BM_GAP);
4672
for (i = 0; i < 500; i+=1)
4678
for (i = 0; i < 1000; i+=2)
4684
struct bvect::statistics st;
4687
unsigned char* sermem = new unsigned char[st.max_serialize_mem];
4689
unsigned slen = bm::serialize(bv2, sermem);
4693
bm::deserialize(bv, sermem);
4701
__int64 CalcBitCount64(__int64 b)
4703
b = (b & 0x5555555555555555) + (b >> 1 & 0x5555555555555555);
4704
b = (b & 0x3333333333333333) + (b >> 2 & 0x3333333333333333);
4705
b = b + (b >> 4) & 0x0F0F0F0F0F0F0F0F;
4708
b = b + (b >> 32) & 0x0000007F;
4712
unsigned CalcBitCount32(unsigned b)
4714
b = (b & 0x55555555) + (b >> 1 & 0x55555555);
4715
b = (b & 0x33333333) + (b >> 2 & 0x33333333);
4716
b = b + (b >> 4) & 0x0F0F0F0F;
4718
b = b + (b >> 16) & 0x0000003F;
4726
cout << "----------------------------- Syntax test." << endl;
4729
bvect::allocator_type a = bv1.get_allocator();
4753
bvect::reference ref = bv1[10];
4763
cout << "----------------------------- Syntax test ok." << endl;
4775
if (cnt != bm::id_max)
4777
cout << "Set test failed!." << endl;
4785
cout << "Set invert test failed!." << endl;
4790
bv.set(bm::id_max-1);
4799
if (cnt != bm::id_max-2)
4801
cout << "Set invert test failed!." << endl;
4807
template<class A, class B> void CompareMiniSet(const A& ms,
4810
for (unsigned i = 0; i < bm::set_total_blocks; ++i)
4812
bool ms_val = ms.test(i)!=0;
4813
bool bvm_val = bvm.is_bit_true(i)!=0;
4814
if (ms_val != bvm_val)
4816
printf("MiniSet comparison error: %u\n",i);
4824
cout << "----------------------- MiniSetTest" << endl;
4826
bm::miniset<bm::block_allocator, bm::set_total_blocks> ms;
4827
bvect_mini bvm(bm::set_total_blocks);
4830
CompareMiniSet(ms, bvm);
4836
CompareMiniSet(ms, bvm);
4840
for (i = 1; i < 10; i++)
4845
CompareMiniSet(ms, bvm);
4847
for (i = 1; i < 10; i++)
4852
CompareMiniSet(ms, bvm);
4855
for (i = 1; i < 10; i+=3)
4860
CompareMiniSet(ms, bvm);
4862
for (i = 1; i < 5; i+=3)
4867
CompareMiniSet(ms, bvm);
4872
bm::miniset<bm::block_allocator, bm::set_total_blocks> ms;
4873
bvect_mini bvm(bm::set_total_blocks);
4879
CompareMiniSet(ms, bvm);
4882
for (i = 1; i < bm::set_total_blocks; i+=3)
4887
CompareMiniSet(ms, bvm);
4889
for (i = 1; i < bm::set_total_blocks/2; i+=3)
4894
CompareMiniSet(ms, bvm);
4899
bm::bvmini<bm::set_total_blocks> ms(0);
4900
bvect_mini bvm(bm::set_total_blocks);
4903
CompareMiniSet(ms, bvm);
4909
CompareMiniSet(ms, bvm);
4913
for (i = 1; i < 10; i++)
4918
CompareMiniSet(ms, bvm);
4920
for (i = 1; i < 10; i++)
4925
CompareMiniSet(ms, bvm);
4928
for (i = 1; i < bm::set_total_blocks; i+=3)
4933
CompareMiniSet(ms, bvm);
4935
for (i = 1; i < bm::set_total_blocks/2; i+=3)
4940
CompareMiniSet(ms, bvm);
4945
bm::miniset<bm::block_allocator, bm::set_total_blocks> ms;
4946
bvect_mini bvm(bm::set_total_blocks);
4952
CompareMiniSet(ms, bvm);
4955
for (i = 1; i < 15; i+=3)
4960
CompareMiniSet(ms, bvm);
4962
for (i = 1; i < 7; i+=3)
4967
CompareMiniSet(ms, bvm);
4971
cout << "----------------------- MiniSetTest ok" << endl;
4975
unsigned CalcBitCount32(unsigned b)
4977
b = (b & 0x55555555) + (b >> 1 & 0x55555555);
4978
b = (b & 0x33333333) + (b >> 2 & 0x33333333);
4979
b = b + (b >> 4) & 0x0F0F0F0F;
4981
b = b + (b >> 16) & 0x0000003F;
4986
void PrintGapLevels(const gap_word_t* glevel)
4988
cout << "Gap levels:" << endl;
4990
for (i = 0; i < bm::gap_levels; ++i)
4992
cout << glevel[i] << ",";
4999
gap_word_t glevel[bm::gap_levels];
5000
::memcpy(glevel, gap_len_table<true>::_len, bm::gap_levels * sizeof(gap_word_t));
5003
gap_word_t length[] = { 2, 2, 5, 5, 10, 11, 12 };
5004
unsigned lsize = sizeof(length) / sizeof(gap_word_t);
5006
bm::improve_gap_levels(length, length + lsize, glevel);
5008
PrintGapLevels(glevel);
5012
gap_word_t length[] = { 3, 5, 15, 15, 100, 110, 120 };
5013
unsigned lsize = sizeof(length) / sizeof(gap_word_t);
5015
bm::improve_gap_levels(length, length + lsize, glevel);
5016
PrintGapLevels(glevel);
5020
gap_word_t length[] = { 15, 80, 5, 3, 100, 110, 95 };
5021
unsigned lsize = sizeof(length) / sizeof(gap_word_t);
5023
bm::improve_gap_levels(length, length + lsize, glevel);
5024
PrintGapLevels(glevel);
5028
gap_word_t length[] =
5029
{ 16,30,14,24,14,30,18,14,12,16,8,38,28,4,20,18,28,22,32,14,12,16,10,8,14,18,14,8,
5030
16,30,8,8,58,28,18,4,26,14,52,12,18,10,14,18,22,18,20,70,12,6,26,6,8,22,12,4,8,8,
5031
8,54,18,6,8,4,4,10,4,4,4,4,4,6,22,14,38,40,56,50,6,10,8,18,82,16,6,18,20,12,12,
5032
16,8,14,14,10,16,12,10,16,14,12,18,14,18,34,14,12,18,18,10,20,10,18,8,14,14,22,16,
5033
10,10,18,8,20,14,10,14,12,12,14,16,16,6,10,14,6,10,10,10,10,12,4,8,8,8,10,10,8,
5034
8,12,10,10,14,14,14,8,4,4,10,10,4,10,4,8,6,52,104,584,218
5036
unsigned lsize = sizeof(length) / sizeof(gap_word_t);
5038
bm::improve_gap_levels(length, length + lsize, glevel);
5039
PrintGapLevels(glevel);
5043
gap_word_t length[] = {
5044
30,46,26,4,4,68,72,6,10,4,6,14,6,42,198,22,12,4,6,24,12,8,18,4,6,10,6,4,6,6,12,6
5045
,6,4,4,78,38,8,52,4,8,10,6,8,8,6,10,4,6,6,4,10,6,8,16,22,28,14,10,10,16,10,20,10
5046
,14,12,8,18,4,8,10,6,10,4,6,12,16,12,6,4,8,4,14,14,6,8,4,10,10,8,8,6,8,6,8,4,8,4
5049
unsigned lsize = sizeof(length) / sizeof(gap_word_t);
5051
bm::improve_gap_levels(length, length + lsize, glevel);
5052
PrintGapLevels(glevel);
5058
void BitCountChangeTest()
5060
cout << "---------------------------- BitCountChangeTest " << endl;
5063
for(i = 0xFFFFFFFF; i; i <<= 1)
5065
unsigned a0 = bm::bit_count_change(i);
5066
unsigned a1 = BitCountChange(i);
5071
<< "Bit count change test failed!"
5072
<< " i = " << i << " return = "
5073
<< a0 << " check = " << a1
5079
cout << "---------------------------- STEP 2 " << endl;
5081
for(i = 0xFFFFFFFF; i; i >>= 1)
5083
unsigned a0 = bm::bit_count_change(i);
5084
unsigned a1 = BitCountChange(i);
5088
cout << "Bit count change test failed!"
5089
<< " i = " << i << " return = "
5090
<< a0 << " check = " << a1
5096
cout << "---------------------------- STEP 3 " << endl;
5098
for (i = 0; i < 0xFFFFFFF; ++i)
5100
unsigned a0 = bm::bit_count_change(i);
5101
unsigned a1 = BitCountChange(i);
5105
cout << "Bit count change test failed!"
5106
<< " i = " << i << " return = "
5107
<< a0 << " check = " << a1
5114
bm::word_t arr[16] = {0,};
5115
arr[0] = (bm::word_t)(1 << 31);
5116
arr[1] = 1; //(bm::word_t)(1 << 31);
5120
cnt = bm::bit_count_change(arr[1]);
5121
cout << cnt << endl;
5124
cout << "0.count_change() failed " << cnt << endl;
5128
cnt = bm::bit_block_calc_count_change(arr, arr+4);
5132
cout << "1.count_intervals() failed " << cnt << endl;
5136
arr[0] = arr[1] = arr[2] = 0xFFFFFFFF;
5137
arr[3] = (bm::word_t)(0xFFFFFFFF >> 1);
5139
cnt = bm::bit_block_calc_count_change(arr, arr+4);
5140
cout << cnt << endl;
5144
cout << "1.1 count_intervals() failed " << cnt << endl;
5149
cout << "---------------------------- STEP 4 " << endl;
5152
cnt = bm::count_intervals(bv1);
5156
cout << "1.count_intervals() failed " << cnt << endl;
5159
CheckIntervals(bv1, 65536);
5163
cnt = count_intervals(bv1);
5164
cout << "Inverted cnt=" << cnt << endl;
5168
cout << "2.inverted count_intervals() failed " << cnt << endl;
5174
for (i = 10; i < 100000; ++i)
5179
cnt = count_intervals(bv1);
5183
cout << "3.count_intervals() failed " << cnt << endl;
5186
cout << "-----" << endl;
5187
CheckIntervals(bv1, 65536*2);
5188
cout << "Optmization..." << endl;
5190
cnt = count_intervals(bv1);
5194
cout << "4.count_intervals() failed " << cnt << endl;
5198
CheckIntervals(bv1, 65536*2);
5200
cout << "---------------------------- BitCountChangeTest Ok." << endl;
5207
assert(bv.any() == false);
5208
assert(bv.count() == 0);
5214
assert(bv1.size() == bv2.size());
5219
assert(bv.any() == false);
5220
assert(bv.count() == 0);
5222
unsigned cnt = bv.count();
5231
assert(bv1.size() == 10);
5232
assert(bv2.size() == 0);
5233
assert(bv1.count() == 1);
5234
assert(bv2.count() == 0);
5238
assert(bv2.size() == 10);
5239
assert(bv2.count() == 1);
5240
assert(bv1.size() == 0);
5241
assert(bv1.count() == 0);
5249
assert(bv1.size() == bm::id_max);
5250
assert(bv1.count() == 2);
5252
assert(bv1.size() == 101);
5253
assert(bv1.count() == 1);
5255
bm::id_t f = bv1.get_first();
5257
f = bv1.get_next(f);
5262
assert(bv1.size() == 10);
5263
assert(bv1.count() == 0);
5264
bm::id_t f = bv1.get_first();
5274
bv.set_range(0, 65536*10, false);
5278
// test logical operations
5281
bvect bv1(65536 * 10);
5282
bvect bv2(65536 * 100);
5287
assert(bv2.size() == 65536 * 100);
5288
assert(bv2.count() == 1);
5289
assert(bv2.get_first() == 5);
5299
assert(bv1.size() == bv2.size());
5300
assert(bv1.count() == 1);
5301
assert(bv1.get_first() == 5);
5311
assert(bv1.size() == bv2.size());
5312
assert(bv1.count() == 3);
5323
cmp = bv1.compare(bv2);
5328
cmp = bv1.compare(bv2);
5330
cmp = bv2.compare(bv1);
5340
bvect::insert_iterator it(bv1);
5343
assert(bv1.size() == 100 * 65536 + 1);
5351
struct bvect::statistics st1;
5352
bv1.calc_stat(&st1);
5354
unsigned char* sermem = new unsigned char[st1.max_serialize_mem];
5355
unsigned slen2 = bm::serialize(bv1, sermem);
5358
bm::deserialize(bv2, sermem);
5361
assert(bv2.size() == 10);
5362
assert(bv2.count() == 1);
5363
assert(bv2.get_first() == 5);
5370
unsigned int arg[] = { 10, 65536, 65537, 65538 * 10000 };
5371
unsigned* it1 = arg;
5372
unsigned* it2 = arg + 4;
5373
combine_or(bv1, it1, it2);
5374
assert(bv1.size() == 65538 * 10000 + 1);
5375
bvect::enumerator en = bv1.first();
5387
#define POWER_CHECK(w, mask) \
5388
(bm::bit_count_table<true>::_count[(w&mask) ^ ((w&mask)-1)])
5392
unsigned bits[64] = {0,};
5399
int bn3 = POWER_CHECK(w, 1 << 3) - 1;
5400
int bn2 = POWER_CHECK(w, 1 << 2) - 1;
5401
int bn0 = POWER_CHECK(w, 1 << 0) - 1;
5403
bit_list(w, bits+1);
5411
time_t start_time = time(0);
5420
// cout << sizeof(__int64) << endl;
5422
// ::srand((unsigned)::time(NULL));
5432
BitCountChangeTest();
5436
BasicFunctionalityTest();
5446
SimpleRandomFillTest();
5448
RangeRandomFillTest();
5450
AndOperationsTest();
5454
XorOperationsTest();
5456
SubOperationsTest();
5464
MutationOperationsTest();
5466
SerializationTest();
5468
DesrializationTest2();
5474
finish_time = time(0);
5477
cout << "Test execution time = " << finish_time - start_time << endl;
5480
cout << "Number of BLOCK allocations = " << dbg_block_allocator::na_ << endl;
5481
cout << "Number of PTR allocations = " << dbg_ptr_allocator::na_ << endl << endl;
5483
assert(dbg_block_allocator::balance() == 0);
5484
assert(dbg_ptr_allocator::balance() == 0);
2
Copyright (c) 2002,2003 Anatoliy Kuznetsov.
4
Permission is hereby granted, free of charge, to any person
5
obtaining a copy of this software and associated documentation
6
files (the "Software"), to deal in the Software without restriction,
7
including without limitation the rights to use, copy, modify, merge,
8
publish, distribute, sublicense, and/or sell copies of the Software,
9
and to permit persons to whom the Software is furnished to do so,
10
subject to the following conditions:
12
The above copyright notice and this permission notice shall be included
13
in all copies or substantial portions of the Software.
15
THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
16
EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES
17
OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
18
IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM,
19
DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE,
20
ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
21
OTHER DEALINGS IN THE SOFTWARE.
26
//#define BM_SET_MMX_GUARD
30
#include <ncbi_pch.hpp>
50
#define POOL_SIZE 5000
55
template<class T> T* pool_allocate(T** pool, int& i, size_t n)
57
return i ? pool[i--] : (T*) ::malloc(n * sizeof(T));
60
inline void* pool_allocate2(void** pool, int& i, size_t n)
62
return i ? pool[i--] : malloc(n * sizeof(void*));
67
template<class T> void pool_free(T** pool, int& i, T* p)
69
i < POOL_SIZE ? (free(p),(void*)0) : pool[++i]=p;
73
class pool_block_allocator
77
static bm::word_t* allocate(size_t n, const void *)
80
bm::word_t** pool = 0;
84
case bm::set_block_size:
85
idx = &bit_blocks_idx_;
86
pool = free_bit_blocks_;
90
idx = &gap_blocks_idx0_;
91
pool = gap_bit_blocks0_;
95
idx = &gap_blocks_idx1_;
96
pool = gap_bit_blocks1_;
100
idx = &gap_blocks_idx2_;
101
pool = gap_bit_blocks2_;
105
idx = &gap_blocks_idx3_;
106
pool = gap_bit_blocks3_;
113
return pool_allocate(pool, *idx, n);
116
static void deallocate(bm::word_t* p, size_t n)
119
bm::word_t** pool = 0;
123
case bm::set_block_size:
124
idx = &bit_blocks_idx_;
125
pool = free_bit_blocks_;
129
idx = &gap_blocks_idx0_;
130
pool = gap_bit_blocks0_;
134
idx = &gap_blocks_idx1_;
135
pool = gap_bit_blocks1_;
139
idx = &gap_blocks_idx2_;
140
pool = gap_bit_blocks2_;
144
idx = &gap_blocks_idx3_;
145
pool = gap_bit_blocks3_;
152
pool_free(pool, *idx, p);
156
static bm::word_t* free_bit_blocks_[];
157
static int bit_blocks_idx_;
159
static bm::word_t* gap_bit_blocks0_[];
160
static int gap_blocks_idx0_;
162
static bm::word_t* gap_bit_blocks1_[];
163
static int gap_blocks_idx1_;
165
static bm::word_t* gap_bit_blocks2_[];
166
static int gap_blocks_idx2_;
168
static bm::word_t* gap_bit_blocks3_[];
169
static int gap_blocks_idx3_;
172
bm::word_t* pool_block_allocator::free_bit_blocks_[POOL_SIZE];
173
int pool_block_allocator::bit_blocks_idx_ = 0;
175
bm::word_t* pool_block_allocator::gap_bit_blocks0_[POOL_SIZE];
176
int pool_block_allocator::gap_blocks_idx0_ = 0;
178
bm::word_t* pool_block_allocator::gap_bit_blocks1_[POOL_SIZE];
179
int pool_block_allocator::gap_blocks_idx1_ = 0;
181
bm::word_t* pool_block_allocator::gap_bit_blocks2_[POOL_SIZE];
182
int pool_block_allocator::gap_blocks_idx2_ = 0;
184
bm::word_t* pool_block_allocator::gap_bit_blocks3_[POOL_SIZE];
185
int pool_block_allocator::gap_blocks_idx3_ = 0;
190
class pool_ptr_allocator
194
static void* allocate(size_t n, const void *)
196
return pool_allocate2(free_ptr_blocks_, ptr_blocks_idx_, n);
199
static void deallocate(void* p, size_t)
201
pool_free(free_ptr_blocks_, ptr_blocks_idx_, p);
205
static void* free_ptr_blocks_[];
206
static int ptr_blocks_idx_;
209
void* pool_ptr_allocator::free_ptr_blocks_[POOL_SIZE];
210
int pool_ptr_allocator::ptr_blocks_idx_ = 0;
218
class dbg_block_allocator
224
static bm::word_t* allocate(size_t n, const void *)
229
(bm::word_t*) ::malloc((n+1) * sizeof(bm::word_t));
234
static void deallocate(bm::word_t* p, size_t n)
240
printf("Block memory deallocation error!\n");
252
unsigned dbg_block_allocator::na_ = 0;
253
unsigned dbg_block_allocator::nf_ = 0;
255
class dbg_ptr_allocator
261
static void* allocate(size_t n, const void *)
264
assert(sizeof(size_t) == sizeof(void*));
265
void* p = ::malloc((n+1) * sizeof(void*));
266
size_t* s = (size_t*) p;
271
static void deallocate(void* p, size_t n)
274
size_t* s = (size_t*) p;
278
printf("Ptr memory deallocation error!\n");
291
unsigned dbg_ptr_allocator::na_ = 0;
292
unsigned dbg_ptr_allocator::nf_ = 0;
295
typedef mem_alloc<dbg_block_allocator, dbg_ptr_allocator> dbg_alloc;
297
typedef bm::bvector<dbg_alloc> bvect;
298
typedef bm::bvector_mini<dbg_block_allocator> bvect_mini;
304
typedef mem_alloc<pool_block_allocator, pool_ptr_allocator> pool_alloc;
305
typedef bm::bvector<pool_alloc> bvect;
306
typedef bm::bvector_mini<bm::block_allocator> bvect_mini;
311
typedef bm::bvector<> bvect;
312
typedef bm::bvector_mini<bm::block_allocator> bvect_mini;
318
//const unsigned BITVECT_SIZE = 100000000 * 8;
320
// This this setting program will consume around 150M of RAM
321
const unsigned BITVECT_SIZE = 100000000 * 2;
323
const unsigned ITERATIONS = 100000;
324
const unsigned PROGRESS_PRINT = 2000000;
328
void CheckVectors(bvect_mini &bvect_min,
331
bool detailed = false);
334
unsigned random_minmax(unsigned min, unsigned max)
336
unsigned r = (rand() << 16) | rand();
337
return r % (max-min) + min;
341
void FillSets(bvect_mini* bvect_min,
345
unsigned fill_factor)
353
unsigned n_id = (max - min) / 100;
354
printf("random filling : %i\n", n_id);
355
for (i = 0; i < n_id; i++)
357
id = random_minmax(min, max);
358
bvect_min->set_bit(id);
359
bvect_full->set_bit(id);
362
if ( (i % PROGRESS_PRINT) == 0)
364
cout << "+" << flush;
372
printf("fill_factor random filling : factor = %i\n", fill_factor);
374
for(i = 0; i < fill_factor; i++)
381
unsigned start = min + (max - min) / (fill_factor * k);
384
start += random_minmax(1, (max - min) / (fill_factor * 10));
392
unsigned end = start + (max - start) / (fill_factor *2);
395
end -= random_minmax(1, (max - start) / (fill_factor * 10));
411
int inc = rand() % 3;
413
unsigned end2 = start + rand() % 1000;
418
bvect_min->set_bit(start);
419
bvect_full->set_bit(start);
425
if ( ( ((i+1)*(end-start)) % PROGRESS_PRINT) == 0)
427
cout << "+" << flush;
436
bvect_min->set_bit(start);
437
bvect_full->set_bit(start);
443
bvect_min->set_bit(start);
444
bvect_full->set_bit(start);
449
if ( ( ((i+1)*(end-start)) % PROGRESS_PRINT) == 0)
451
cout << "+" << flush;
462
for(; start < end; ++start)
464
bvect_min->set_bit(start);
465
bvect_full->set_bit(start);
474
if ( ( ((i+1)*(end-start)) % PROGRESS_PRINT) == 0)
476
cout << "+" << flush;
490
// 111........111111........111111..........11111111.......1111111...
494
void FillSetsIntervals(bvect_mini* bvect_min,
498
unsigned fill_factor,
502
while(fill_factor==0)
504
fill_factor=rand()%10;
507
cout << "Intervals filling. Factor="
508
<< fill_factor << endl << endl;
511
unsigned factor = 70 * fill_factor;
512
for (i = min; i < max; ++i)
518
len = rand() % factor;
521
} while (end >= max);
523
if (set_flag == false)
525
cout << "Cleaning: " << i << "-" << end << endl;
529
cout << "Add: " << i << "-" << end << endl;
534
bvect_full->set_range(i, end-1, set_flag);
537
for (j = i; j < end; ++j)
541
bvect_min->set_bit(j);
542
//bvect_full->set_bit(j);
546
bvect_min->clear_bit(j);
547
//bvect_full->clear_bit(j);
551
bool b = bvect_full->count_check();
554
cout << "Count check failed (clear)!" << endl;
555
cout << "bit=" << j << endl;
565
//cout << "Checking range filling " << from << "-" << to << endl;
566
//CheckVectors(*bvect_min, *bvect_full, 100000000);
572
len = rand() % (factor* 10 * bm::gap_max_bits);
575
len *= rand() % (factor * 10);
583
if (set_flag == false)
585
cout << "Additional Cleaning: " << i << "-" << end << endl;
588
for(unsigned k=0; k < 1000 && i < max; k+=3,i+=3)
592
bvect_min->set_bit(i);
593
bvect_full->set_bit(i);
597
bvect_min->clear_bit(j);
598
bvect_full->clear_bit(j);
608
void FillSetClearIntervals(bvect_mini* bvect_min,
612
unsigned fill_factor)
614
FillSetsIntervals(bvect_min, bvect_full, min, max, fill_factor, true);
615
FillSetsIntervals(bvect_min, bvect_full, min, max, fill_factor, false);
619
void FillSetsRandom(bvect_mini* bvect_min,
623
unsigned fill_factor)
625
unsigned diap = max - min;
644
for (unsigned i = 0; i < count; ++i)
646
unsigned bn = rand() % count;
653
bvect_min->set_bit(bn);
654
bvect_full->set_bit(bn);
656
if ( (i % PROGRESS_PRINT) == 0)
658
cout << "+" << flush;
661
cout << "Ok" << endl;
667
// Quasi random filling with choosing randomizing method.
670
void FillSetsRandomMethod(bvect_mini* bvect_min,
687
cout << "Random filling: method - FillSets - factor(0)" << endl;
688
FillSets(bvect_min, bvect_full, min, max, 0);
692
cout << "Random filling: method - FillSets - factor(random)" << endl;
694
FillSets(bvect_min, bvect_full, min, max, factor?factor:1);
698
cout << "Random filling: method - Set-Clear Intervals - factor(random)" << endl;
700
FillSetClearIntervals(bvect_min, bvect_full, min, max, factor);
703
cout << "Random filling: method - FillRandom - factor(random)" << endl;
705
FillSetsRandom(bvect_min, bvect_full, min, max, factor?factor:1);
709
cout << "Random filling: method - Set Intervals - factor(random)" << endl;
711
FillSetsIntervals(bvect_min, bvect_full, min, max, factor);
716
if (optimize && (method <= 1))
718
cout << "Vector optimization..." << flush;
719
bvect_full->optimize();
720
cout << "OK" << endl;
724
// do logical operation through serialization
725
unsigned SerializationOperation(bvect* bv_target,
726
/*const*/ bvect& bv1,
727
/*const*/ bvect& bv2,
729
bool check_reverse=false)
737
if (op == set_COUNT_SUB_AB ||
738
op == set_COUNT_SUB_BA)
740
check_reverse = false;
743
// serialize input vectors
744
bvect::statistics *st1_op, *st2_op;
745
st1_op = new bvect::statistics;
746
st2_op = new bvect::statistics;
748
bv1.optimize(0, bvect::opt_compress, st1_op);
749
bv2.optimize(0, bvect::opt_compress, st2_op);
752
struct bvect::statistics st1, st2;
757
if (st1.max_serialize_mem > st1_op->max_serialize_mem)
759
cout << "Optimize failed to compute max_serialize_mem" << endl;
760
cout << "calc_stat=" << st1.max_serialize_mem << endl;
761
cout << "optimize=" << st1_op->max_serialize_mem << endl;
764
if (st2.max_serialize_mem > st2_op->max_serialize_mem)
766
cout << "Optimize failed to compute max_serialize_mem" << endl;
767
cout << "calc_stat=" << st2.max_serialize_mem << endl;
768
cout << "optimize=" << st2_op->max_serialize_mem << endl;
775
unsigned char* smem1 = new unsigned char[st1.max_serialize_mem];
776
unsigned char* smem2 = new unsigned char[st2.max_serialize_mem];
778
unsigned slen1 = bm::serialize(bv1, smem1);
779
unsigned slen2 = bm::serialize(bv2, smem2);
782
operation_deserializer<bvect>::deserialize(*bv_target,
786
int res = bv1.compare(*bv_target);
789
cout << "set_ASSIGN 1 failed!" << endl;
792
// PrintSet(cout, *bv_target);
796
operation_deserializer<bvect>::deserialize(*bv_target,
803
bvect bv_tmp2(BM_GAP);
804
operation_deserializer<bvect>::deserialize(bv_tmp2,
808
int res = bv_tmp2.compare(bv2);
811
cout << "set_ASSIGN failed 2! " << endl;
814
// PrintSet(cout, bv_tmp2);
817
operation_deserializer<bvect>::deserialize(bv_tmp2,
821
if (count != count_rev)
824
cout << "Serialization operation reverse check failed"
825
<< " count = " << count
826
<< " count rev= " << count_rev
839
void SerializationOperation2Test(bvect* bv_target,
842
unsigned predicted_count,
843
set_operation op_count,
844
set_operation op_combine)
846
bv_target->clear(true);
847
unsigned scount1 = SerializationOperation(0,
851
true /*reverse check*/);
853
unsigned scount2 = SerializationOperation(bv_target,
857
scount2 = bv_target->count();
858
if (predicted_count != scount2 || scount1 != scount2)
860
cout << "Serialization count != predicted" << endl
861
<< " predicted=" << predicted_count
862
<< " scount1=" << scount1
863
<< " scount2=" << scount2
866
cout << endl << "target:" << endl;
868
cout << endl << endl << "Reference" << endl;
869
if (op_combine == set_AND)
880
void print_mv(const bvect_mini &bvect_min, unsigned size)
883
for (i = 0; i < size; ++i)
885
bool bflag = bvect_min.is_bit_true(i) != 0;
891
if ((i % 31) == 0 && (i != 0))
898
void print_gap(const gap_vector& gap_vect, unsigned size)
900
const gap_word_t *buf = gap_vect.get_buf();
901
unsigned len = gap_length(buf);
902
printf("[%i:]", *buf++ & 1);
904
for (unsigned i = 1; i < len; ++i)
906
printf("%i,", *buf++);
912
void CheckGAPMin(const gap_vector& gapv, const bvect_mini& bvect_min, unsigned len)
914
for (unsigned i = 0; i < len; ++i)
916
int bit1 = (gapv.is_bit_true(i) == 1);
917
int bit2 = (bvect_min.is_bit_true(i) != 0);
920
cout << "Bit comparison failed. " << "Bit N=" << i << endl;
927
void CheckIntervals(const bvect& bv, unsigned max_bit)
929
unsigned cnt0 = count_intervals(bv);
931
bool bit_prev = bv.test(0);
932
for (unsigned i = 1; i < max_bit; ++i)
934
bool bit = bv.test(i);
935
cnt1 += bit_prev ^ bit;
940
cout << "CheckIntervals error. " << "bm count=" << cnt0
941
<< " Control = " << cnt1 << endl;
946
template<class T> void CheckCountRange(const T& vect,
949
unsigned* block_count_arr=0)
951
unsigned cnt1 = vect.count_range(left, right, block_count_arr);
954
for (unsigned i = left; i <= right; ++i)
958
// cout << i << " " << flush;
965
cout << "Bitcount range failed!" << "left=" << left
966
<< " right=" << right << endl
967
<< "count_range()=" << cnt1
968
<< " check=" << cnt2;
974
unsigned BitCountChange(unsigned word)
977
unsigned bit_prev = word & 1;
979
for (unsigned i = 1; i < 32; ++i)
981
unsigned bit = word & 1;
982
count += bit ^ bit_prev;
990
void DetailedCheckVectors(const bvect_mini &bvect_min,
991
const bvect &bvect_full,
994
cout << "Detailed check" << endl;
998
// detailed bit by bit comparison. Paranoia check.
1001
for (i = 0; i < size; ++i)
1003
bool bv_m_flag = bvect_min.is_bit_true(i) != 0;
1004
bool bv_f_flag = bvect_full.get_bit(i) != 0;
1006
if (bv_m_flag != bv_f_flag)
1008
printf("Bit %u is non conformant. vect_min=%i vect_full=%i\n",
1009
i, (int)bv_m_flag, (int)bv_f_flag);
1011
cout << "Non-conformant block number is: " << unsigned(i >> bm::set_block_shift) << endl;
1018
if ( (i % PROGRESS_PRINT) == 0)
1026
printf("\n detailed check ok.\n");
1031
// vectors comparison check
1033
void CheckVectors(bvect_mini &bvect_min,
1038
cout << "\nVectors checking...bits to compare = " << size << endl;
1040
cout << "Bitcount summary : " << endl;
1041
unsigned min_count = bvect_min.bit_count();
1042
cout << "minvector count = " << min_count << endl;
1043
unsigned count = bvect_full.count();
1044
unsigned full_count = bvect_full.recalc_count();
1045
cout << "fullvector re-count = " << full_count << endl;
1047
if (min_count != full_count)
1049
cout << "fullvector count = " << count << endl;
1050
cout << "Count comparison failed !!!!" << endl;
1052
DetailedCheckVectors(bvect_min, bvect_full, size);
1059
bool any = bvect_full.any();
1062
cout << "Anycheck failed!" << endl;
1067
// get_next comparison
1069
cout << "Positive bits comparison..." << flush;
1070
unsigned nb_min = bvect_min.get_first();
1071
unsigned nb_ful = bvect_full.get_first();
1073
bvect::counted_enumerator en = bvect_full.first();
1074
unsigned nb_en = *en;
1075
if (nb_min != nb_ful)
1077
cout << "!!!! First bit comparison failed. Full id = "
1078
<< nb_ful << " Min id = " << nb_min
1081
bool bit_f = bvect_full.get_bit(nb_ful);
1082
cout << "Full vector'd bit #" << nb_ful << "is:"
1085
bool bit_m = (bvect_min.is_bit_true(nb_min) == 1);
1086
cout << "Min vector'd bit #" << nb_min << "is:"
1092
DetailedCheckVectors(bvect_min, bvect_full, size);
1099
unsigned bit_count = 1;
1100
unsigned en_prev = nb_en;
1104
nb_min = bvect_min.get_next(nb_min);
1114
// nb_en = bvect_full.get_next(nb_en);
1118
if (nb_en != nb_min)
1120
nb_ful = bvect_full.get_next(en_prev);
1121
cout << "!!!!! next bit comparison failed. Full id = "
1122
<< nb_ful << " Min id = " << nb_min
1123
<< " Enumerator = " << nb_en
1126
// bvect_full.stat();
1128
// DetailedCheckVectors(bvect_min, bvect_full, size);
1132
if ( (bit_count % PROGRESS_PRINT) == 0)
1134
cout << "." << flush;
1137
} while (en.valid());
1138
if (bit_count != min_count)
1140
cout << " Bit count failed."
1141
<< " min = " << min_count
1142
<< " bit = " << bit_count
1148
cout << "OK" << endl;
1158
for (int i = 0; i < 100000; ++i)
1160
bvect_full.set_bit(i);
1162
bvect_full.optimize();
1167
int count = bvect_full.count();
1175
cout << "---------------------------- WordCmp test" << endl;
1177
for (int i = 0; i < 10000000; ++i)
1179
unsigned w1 = rand();
1180
unsigned w2 = rand();
1181
int res = wordcmp0(w1, w2);
1182
int res2 = wordcmp(w1, w2);
1185
printf("WordCmp failed !\n");
1189
res = wordcmp0((unsigned)0U, (unsigned)w2);
1190
res2 = wordcmp((unsigned)0U, (unsigned)w2);
1194
printf("WordCmp 0 test failed !\n");
1198
res = wordcmp0((unsigned)~0U, (unsigned)w2);
1199
res2 = wordcmp((unsigned)~0U, (unsigned)w2);
1203
printf("WordCmp ~0 test failed !\n");
1207
res = wordcmp0((unsigned)w2, (unsigned)0);
1208
res2 = wordcmp((unsigned)w2, (unsigned)0);
1212
printf("WordCmp 0-2 test failed !\n");
1218
cout << "Ok." << endl;
1221
void BasicFunctionalityTest()
1223
cout << "---------------------------- Basic functinality test" << endl;
1225
assert(ITERATIONS < BITVECT_SIZE);
1228
bvect_mini bvect_min(BITVECT_SIZE);
1232
printf("\nBasic functionality test.\n");
1234
// filling vectors with regular values
1237
for (i = 0; i < ITERATIONS; ++i)
1239
bvect_min.set_bit(i);
1240
bvect_full.set_bit(i);
1243
bvect_full1.set_range(0, ITERATIONS-1);
1245
CheckCountRange(bvect_full, 0, ITERATIONS);
1246
CheckCountRange(bvect_full, 10, ITERATIONS+10);
1248
if (bvect_full1 != bvect_full)
1250
cout << "set_range failed!" << endl;
1258
// checking the results
1259
unsigned count_min = 0;
1260
for (i = 0; i < ITERATIONS; ++i)
1262
if (bvect_min.is_bit_true(i))
1268
unsigned count_full = bvect_full.count();
1270
if (count_min == count_full)
1272
printf("simple count test ok.\n");
1276
printf("simple count test failed count_min = %i count_full = %i\n",
1277
count_min, count_full);
1282
// detailed vectors verification
1284
CheckVectors(bvect_min, bvect_full, ITERATIONS);
1288
for (i = 0; i < ITERATIONS; i+=2)
1290
bvect_min.clear_bit(i);
1291
bvect_full.clear_bit(i);
1292
bvect_full1.set_range(i, i, false);
1295
CheckVectors(bvect_min, bvect_full, ITERATIONS);
1296
CheckVectors(bvect_min, bvect_full1, ITERATIONS);
1298
for (i = 0; i < ITERATIONS; ++i)
1300
bvect_min.clear_bit(i);
1304
CheckVectors(bvect_min, bvect_full, ITERATIONS);
1306
cout << "Random step filling" << endl;
1308
for (i = rand()%10; i < ITERATIONS; i+=rand()%10)
1310
bvect_min.clear_bit(i);
1311
bvect_full.clear_bit(i);
1314
CheckVectors(bvect_min, bvect_full, ITERATIONS);
1322
bv2[200] = bv2[700] = bv2[500] = true;
1326
if (bv1.count() != 3)
1328
cout << "Swap test failed!" << endl;
1332
if (bv2.count() != 2)
1334
cout << "Swap test failed!" << endl;
1339
void SimpleRandomFillTest()
1341
assert(ITERATIONS < BITVECT_SIZE);
1343
cout << "-------------------------- SimpleRandomFillTest" << endl;
1346
printf("Simple random fill test 1.");
1347
bvect_mini bvect_min(BITVECT_SIZE);
1349
bvect_full.set_new_blocks_strat(bm::BM_BIT);
1352
unsigned iter = ITERATIONS / 5;
1354
printf("\nSimple Random fill test ITERATIONS = %i\n", iter);
1356
bvect_min.set_bit(0);
1357
bvect_full.set_bit(0);
1360
for (i = 0; i < iter; ++i)
1362
unsigned num = ::rand() % iter;
1363
bvect_min.set_bit(num);
1364
bvect_full.set_bit(num);
1365
if ((i % 1000) == 0) cout << "." << flush;
1366
CheckCountRange(bvect_full, 0, num);
1367
CheckCountRange(bvect_full, num, num+iter);
1370
CheckVectors(bvect_min, bvect_full, iter);
1371
CheckCountRange(bvect_full, 0, iter);
1373
printf("Simple random fill test 2.");
1375
for(i = 0; i < iter; ++i)
1377
unsigned num = ::rand() % iter;
1378
bvect_min.clear_bit(num);
1379
bvect_full.clear_bit(num);
1382
CheckVectors(bvect_min, bvect_full, iter);
1387
printf("\nSimple random fill test 3.\n");
1388
bvect_mini bvect_min(BITVECT_SIZE);
1389
bvect bvect_full(bm::BM_GAP);
1392
unsigned iter = ITERATIONS;
1394
printf("\nSimple Random fill test ITERATIONS = %i\n", iter);
1397
for(i = 0; i < iter; ++i)
1399
unsigned num = ::rand() % iter;
1400
bvect_min.set_bit(num);
1401
bvect_full.set_bit(num);
1402
CheckCountRange(bvect_full, 0, 65535);
1403
CheckCountRange(bvect_full, 0, num);
1404
CheckCountRange(bvect_full, num, num+iter);
1405
if ((i % 1000) == 0) cout << "." << flush;
1408
CheckVectors(bvect_min, bvect_full, iter);
1410
printf("Simple random fill test 4.");
1412
for(i = 0; i < iter; ++i)
1414
unsigned num = ::rand() % iter;
1415
bvect_min.clear_bit(num);
1416
bvect_full.clear_bit(num);
1417
CheckCountRange(bvect_full, 0, num);
1418
CheckCountRange(bvect_full, num, num+iter);
1419
if ((i % 1000) == 0) cout << "." << flush;
1422
CheckVectors(bvect_min, bvect_full, iter);
1423
CheckCountRange(bvect_full, 0, iter);
1432
void RangeRandomFillTest()
1434
assert(ITERATIONS < BITVECT_SIZE);
1436
cout << "----------------------------------- RangeRandomFillTest" << endl;
1439
bvect_mini bvect_min(BITVECT_SIZE);
1442
printf("Range Random fill test\n");
1444
unsigned min = BITVECT_SIZE / 2;
1445
unsigned max = BITVECT_SIZE / 2 + ITERATIONS;
1446
if (max > BITVECT_SIZE)
1447
max = BITVECT_SIZE - 1;
1449
FillSets(&bvect_min, &bvect_full, min, max, 0);
1451
CheckVectors(bvect_min, bvect_full, BITVECT_SIZE);
1452
CheckCountRange(bvect_full, min, max);
1458
bvect_mini bvect_min(BITVECT_SIZE);
1461
printf("Range Random fill test\n");
1463
unsigned min = BITVECT_SIZE / 2;
1464
unsigned max = BITVECT_SIZE / 2 + ITERATIONS;
1465
if (max > BITVECT_SIZE)
1466
max = BITVECT_SIZE - 1;
1468
FillSetsIntervals(&bvect_min, &bvect_full, min, max, 4);
1470
CheckVectors(bvect_min, bvect_full, BITVECT_SIZE);
1471
CheckCountRange(bvect_full, min, max);
1479
void AndOperationsTest()
1481
assert(ITERATIONS < BITVECT_SIZE);
1483
cout << "----------------------------------- AndOperationTest" << endl;
1487
bvect_mini bvect_min1(256);
1488
bvect_mini bvect_min2(256);
1492
bvect_full1.set_new_blocks_strat(bm::BM_GAP);
1493
bvect_full2.set_new_blocks_strat(bm::BM_GAP);
1497
printf("AND test\n");
1499
bvect_min1.set_bit(1);
1500
bvect_min1.set_bit(12);
1501
bvect_min1.set_bit(13);
1503
bvect_min2.set_bit(12);
1504
bvect_min2.set_bit(13);
1506
bvect_min1.combine_and(bvect_min2);
1508
bvect_full1.set_bit(1);
1509
bvect_full1.set_bit(12);
1510
bvect_full1.set_bit(13);
1512
bvect_full2.set_bit(12);
1513
bvect_full2.set_bit(13);
1515
bm::id_t predicted_count = bm::count_and(bvect_full1, bvect_full2);
1517
bm::id_t predicted_any = bm::any_and(bvect_full1, bvect_full2);
1518
if (predicted_any == 0 && predicted_count != 0)
1520
cout << "Predicted any error!" << endl;
1525
SerializationOperation2Test(&bv_target_s,
1533
bvect_full1.bit_and(bvect_full2);
1535
bm::id_t count = bvect_full1.count();
1536
if (count != predicted_count)
1538
cout << "Predicted count error!" << endl;
1542
CheckVectors(bvect_min1, bvect_full1, 256);
1543
CheckVectors(bvect_min1, bv_target_s, 256);
1544
CheckCountRange(bvect_full1, 0, 256);
1550
bvect_mini bvect_min1(BITVECT_SIZE);
1551
bvect_mini bvect_min2(BITVECT_SIZE);
1556
printf("AND test stage 1.\n");
1558
for (int i = 0; i < 112; ++i)
1560
bvect_min1.set_bit(i);
1561
bvect_full1.set_bit(i);
1563
bvect_min2.set_bit(i);
1564
bvect_full2.set_bit(i);
1568
CheckVectors(bvect_min1, bvect_full1, BITVECT_SIZE/10+10);
1569
CheckCountRange(bvect_full1, 0, BITVECT_SIZE/10+10);
1571
// FillSets(&bvect_min1, &bvect_full1, 1, BITVECT_SIZE/7, 0);
1572
// FillSets(&bvect_min2, &bvect_full2, 1, BITVECT_SIZE/7, 0);
1574
bvect_min1.combine_and(bvect_min2);
1576
bm::id_t predicted_count = bm::count_and(bvect_full1,bvect_full2);
1577
bm::id_t predicted_any = bm::any_and(bvect_full1, bvect_full2);
1578
if (predicted_any == 0 && predicted_count != 0)
1580
cout << "Predicted any error!" << endl;
1585
SerializationOperation2Test(&bv_target_s,
1592
bvect_full1.bit_and(bvect_full2);
1594
bm::id_t count = bvect_full1.count();
1595
if (count != predicted_count)
1597
cout << "Predicted count error!" << endl;
1601
CheckVectors(bvect_min1, bvect_full1, BITVECT_SIZE/10+10);
1602
CheckVectors(bvect_min1, bv_target_s, BITVECT_SIZE/10+10);
1603
CheckCountRange(bvect_full1, 0, BITVECT_SIZE/10+10);
1610
bvect_mini bvect_min1(BITVECT_SIZE);
1611
bvect_mini bvect_min2(BITVECT_SIZE);
1615
bvect_full1.set_new_blocks_strat(bm::BM_GAP);
1616
bvect_full2.set_new_blocks_strat(bm::BM_GAP);
1618
printf("AND test stage 2.\n");
1621
FillSets(&bvect_min1, &bvect_full1, 1, BITVECT_SIZE/7, 0);
1622
FillSets(&bvect_min2, &bvect_full2, 1, BITVECT_SIZE/7, 0);
1624
bm::id_t predicted_count = bm::count_and(bvect_full1,bvect_full2);
1625
bm::id_t predicted_any = bm::any_and(bvect_full1, bvect_full2);
1626
if (predicted_any == 0 && predicted_count != 0)
1628
cout << "Predicted any error!" << endl;
1633
SerializationOperation2Test(&bv_target_s,
1640
bvect_min1.combine_and(bvect_min2);
1642
bvect_full1.bit_and(bvect_full2);
1644
bm::id_t count = bvect_full1.count();
1645
if (count != predicted_count)
1647
cout << "Predicted count error!" << endl;
1652
CheckVectors(bvect_min1, bvect_full1, BITVECT_SIZE/10+10);
1653
CheckVectors(bvect_min1, bv_target_s, BITVECT_SIZE/10+10);
1654
CheckCountRange(bvect_full1, 0, BITVECT_SIZE/10+10);
1660
bvect_mini bvect_min1(BITVECT_SIZE);
1661
bvect_mini bvect_min2(BITVECT_SIZE);
1665
bvect_full1.set_new_blocks_strat(bm::BM_BIT);
1666
bvect_full2.set_new_blocks_strat(bm::BM_BIT);
1668
cout << "------------------------------" << endl;
1669
printf("AND test stage 3.\n");
1672
FillSets(&bvect_min1, &bvect_full1, 1, BITVECT_SIZE/5, 2);
1673
FillSets(&bvect_min2, &bvect_full2, 1, BITVECT_SIZE/5, 2);
1675
bvect_min1.combine_and(bvect_min2);
1677
bm::id_t predicted_count = bm::count_and(bvect_full1, bvect_full2);
1678
bm::id_t predicted_any = bm::any_and(bvect_full1, bvect_full2);
1679
if (predicted_any == 0 && predicted_count != 0)
1681
cout << "Predicted any error!" << endl;
1686
SerializationOperation2Test(&bv_target_s,
1693
bvect_full1.bit_and(bvect_full2);
1695
bm::id_t count = bvect_full1.count();
1696
if (count != predicted_count)
1698
cout << "Predicted count error!" << endl;
1702
CheckVectors(bvect_min1, bvect_full1, BITVECT_SIZE);
1703
CheckVectors(bvect_min1, bv_target_s, BITVECT_SIZE);
1704
CheckCountRange(bvect_full1, 0, BITVECT_SIZE);
1706
bvect_full1.optimize();
1707
CheckVectors(bvect_min1, bvect_full1, BITVECT_SIZE);
1708
CheckCountRange(bvect_full1, 0, BITVECT_SIZE);
1709
CheckCountRange(bvect_full1, BITVECT_SIZE/2, BITVECT_SIZE);
1713
cout << "------------------------------" << endl;
1714
printf("AND test stage 4. combine_and_sorted\n");
1716
unsigned ids[] = {0, 1, 2, 3, 10, 65535, 65536, 65535*2, 65535*3};
1717
unsigned to_add = sizeof(ids)/sizeof(unsigned);
1720
bvect_mini bvect_min1(BITVECT_SIZE);
1721
bvect_mini bvect_min2(BITVECT_SIZE);
1723
bvect_full1.set_new_blocks_strat(bm::BM_GAP);
1724
bvect_full2.set_new_blocks_strat(bm::BM_GAP);
1726
for (unsigned i = 2; i < to_add; ++i)
1728
bvect_full1.set(ids[i]);
1729
bvect_min1.set_bit(ids[i]);
1730
bvect_full2.set(ids[i]);
1731
bvect_min2.set_bit(ids[i]);
1734
unsigned* first = ids;
1735
unsigned* last = ids + to_add;
1737
bvect_min1.combine_and(bvect_min2);
1739
bm::combine_and_sorted(bvect_full1, first, last);
1740
CheckVectors(bvect_min1, bvect_full1, BITVECT_SIZE);
1746
void OrOperationsTest()
1748
assert(ITERATIONS < BITVECT_SIZE);
1750
cout << "----------------------------------- OrOperationTest" << endl;
1754
bvect_mini bvect_min1(256);
1755
bvect_mini bvect_min2(256);
1759
bvect_full1.set_new_blocks_strat(bm::BM_GAP);
1760
bvect_full2.set_new_blocks_strat(bm::BM_GAP);
1764
printf("OR test\n");
1766
bvect_min1.set_bit(1);
1767
bvect_min1.set_bit(12);
1768
bvect_min1.set_bit(13);
1770
bvect_min2.set_bit(12);
1771
bvect_min2.set_bit(13);
1773
bvect_min1.combine_or(bvect_min2);
1775
bvect_full1.set_bit(1);
1776
bvect_full1.set_bit(12);
1777
bvect_full1.set_bit(13);
1779
bvect_full2.set_bit(12);
1780
bvect_full2.set_bit(13);
1782
bm::id_t predicted_count = bm::count_or(bvect_full1, bvect_full2);
1783
bm::id_t predicted_any = bm::any_or(bvect_full1, bvect_full2);
1784
if (predicted_any == 0 && predicted_count != 0)
1786
cout << "Predicted any error!" << endl;
1791
SerializationOperation2Test(&bv_target_s,
1799
bvect_full1.bit_or(bvect_full2);
1801
bm::id_t count = bvect_full1.count();
1802
if (count != predicted_count)
1804
cout << "Predicted count error!" << endl;
1805
cout << predicted_count << " " << count << endl;
1811
CheckVectors(bvect_min1, bvect_full1, 256);
1812
CheckVectors(bvect_min1, bv_target_s, 256);
1813
CheckCountRange(bvect_full1, 0, 256);
1814
CheckCountRange(bvect_full1, 128, 256);
1819
bvect_mini bvect_min1(BITVECT_SIZE);
1820
bvect_mini bvect_min2(BITVECT_SIZE);
1824
bvect_full1.set_new_blocks_strat(bm::BM_GAP);
1825
bvect_full2.set_new_blocks_strat(bm::BM_GAP);
1827
printf("OR test stage 2.\n");
1830
FillSets(&bvect_min1, &bvect_full1, 1, BITVECT_SIZE/7, 0);
1831
FillSets(&bvect_min2, &bvect_full2, 1, BITVECT_SIZE/7, 0);
1833
bvect_min1.combine_or(bvect_min2);
1835
bm::id_t predicted_count = bm::count_or(bvect_full1, bvect_full2);
1836
bm::id_t predicted_any = bm::any_or(bvect_full1, bvect_full2);
1837
if (predicted_any == 0 && predicted_count != 0)
1839
cout << "Predicted any error!" << endl;
1844
SerializationOperation2Test(&bv_target_s,
1852
bvect_full1.bit_or(bvect_full2);
1854
bm::id_t count = bvect_full1.count();
1855
if (count != predicted_count)
1857
cout << "Predicted count error!" << endl;
1861
CheckVectors(bvect_min1, bvect_full1, BITVECT_SIZE/10+10);
1862
CheckVectors(bvect_min1, bvect_full1, BITVECT_SIZE/10+10);
1863
CheckCountRange(bvect_full1, 0, BITVECT_SIZE/10+10);
1869
bvect_mini bvect_min1(BITVECT_SIZE);
1870
bvect_mini bvect_min2(BITVECT_SIZE);
1874
bvect_full1.set_new_blocks_strat(bm::BM_BIT);
1875
bvect_full2.set_new_blocks_strat(bm::BM_BIT);
1877
cout << "------------------------------" << endl;
1878
printf("OR test stage 3.\n");
1881
FillSets(&bvect_min1, &bvect_full1, 1, BITVECT_SIZE/5, 2);
1882
FillSets(&bvect_min2, &bvect_full2, 1, BITVECT_SIZE/5, 2);
1884
bvect_min1.combine_or(bvect_min2);
1886
bm::id_t predicted_count = bm::count_or(bvect_full1, bvect_full2);
1887
bm::id_t predicted_any = bm::any_or(bvect_full1, bvect_full2);
1888
if (predicted_any == 0 && predicted_count != 0)
1890
cout << "Predicted any error!" << endl;
1895
SerializationOperation2Test(&bv_target_s,
1902
bvect_full1.bit_or(bvect_full2);
1904
bm::id_t count = bvect_full1.count();
1905
if (count != predicted_count)
1907
cout << "Predicted count error!" << endl;
1911
CheckVectors(bvect_min1, bvect_full1, BITVECT_SIZE);
1913
bvect_full1.optimize();
1915
CheckVectors(bvect_min1, bvect_full1, BITVECT_SIZE);
1916
CheckVectors(bvect_min1, bv_target_s, BITVECT_SIZE);
1917
CheckCountRange(bvect_full1, 0, BITVECT_SIZE);
1922
cout << "Testing combine_or" << endl;
1928
bvect_mini bvect_min1(BITVECT_SIZE);
1930
bvect_full1.set_new_blocks_strat(bm::BM_GAP);
1931
bvect_full2.set_new_blocks_strat(bm::BM_GAP);
1933
unsigned ids[10000];
1934
unsigned to_add = 10000;
1937
for (unsigned i = 0; i < to_add; ++i)
1940
bvect_full2.set(bn);
1941
bvect_min1.set_bit(bn);
1945
unsigned* first = ids;
1946
unsigned* last = ids + to_add;
1948
bm::combine_or(bvect_full1, first, last);
1950
CheckVectors(bvect_min1, bvect_full1, BITVECT_SIZE);
1952
bm::combine_or(bvect_full1, first, last);
1953
CheckVectors(bvect_min1, bvect_full1, BITVECT_SIZE);
1959
unsigned ids[] = {0, 65536, 65535, 65535*3, 65535*2, 10};
1960
unsigned to_add = sizeof(ids)/sizeof(unsigned);
1963
bvect_mini bvect_min1(BITVECT_SIZE);
1965
bvect_full1.set_new_blocks_strat(bm::BM_GAP);
1966
bvect_full2.set_new_blocks_strat(bm::BM_GAP);
1969
for (unsigned i = 0; i < to_add; ++i)
1972
bvect_full2.set(bn);
1973
bvect_min1.set_bit(bn);
1977
unsigned* first = ids;
1978
unsigned* last = ids + to_add;
1980
bm::combine_or(bvect_full1, first, last);
1981
CheckVectors(bvect_min1, bvect_full1, BITVECT_SIZE);
1983
bm::combine_or(bvect_full1, first, last);
1984
CheckVectors(bvect_min1, bvect_full1, BITVECT_SIZE);
1992
void SubOperationsTest()
1994
assert(ITERATIONS < BITVECT_SIZE);
1996
cout << "----------------------------------- SubOperationTest" << endl;
2000
bvect_mini bvect_min1(256);
2001
bvect_mini bvect_min2(256);
2005
bvect_full1.set_new_blocks_strat(bm::BM_GAP);
2006
bvect_full2.set_new_blocks_strat(bm::BM_GAP);
2010
printf("SUB test\n");
2012
bvect_min1.set_bit(1);
2013
bvect_min1.set_bit(12);
2014
bvect_min1.set_bit(13);
2016
bvect_min2.set_bit(12);
2017
bvect_min2.set_bit(13);
2019
bvect_min1.combine_sub(bvect_min2);
2021
bvect_full1.set_bit(1);
2022
bvect_full1.set_bit(12);
2023
bvect_full1.set_bit(13);
2025
bvect_full2.set_bit(12);
2026
bvect_full2.set_bit(13);
2028
bm::id_t predicted_count = bm::count_sub(bvect_full1, bvect_full2);
2029
bm::id_t predicted_any = bm::any_sub(bvect_full1, bvect_full2);
2030
if (predicted_any == 0 && predicted_count != 0)
2032
cout << "Predicted any error!" << endl;
2037
SerializationOperation2Test(&bv_target_s,
2045
bvect_full1.bit_sub(bvect_full2);
2047
bm::id_t count = bvect_full1.count();
2048
if (count != predicted_count)
2050
cout << "Predicted count error!" << endl;
2054
CheckVectors(bvect_min1, bvect_full1, 256);
2055
CheckVectors(bvect_min1, bv_target_s, 256);
2056
CheckCountRange(bvect_full1, 0, 256);
2062
bvect_mini bvect_min1(BITVECT_SIZE);
2063
bvect_mini bvect_min2(BITVECT_SIZE);
2067
bvect_full1.set_new_blocks_strat(bm::BM_GAP);
2068
bvect_full2.set_new_blocks_strat(bm::BM_GAP);
2070
printf("SUB test stage 2.\n");
2073
FillSets(&bvect_min1, &bvect_full1, 1, BITVECT_SIZE/7, 0);
2074
FillSets(&bvect_min2, &bvect_full2, 1, BITVECT_SIZE/7, 0);
2076
bvect_min1.combine_sub(bvect_min2);
2078
bm::id_t predicted_count = bm::count_sub(bvect_full1, bvect_full2);
2079
bm::id_t predicted_any = bm::any_sub(bvect_full1, bvect_full2);
2080
if (predicted_any == 0 && predicted_count != 0)
2082
cout << "Predicted any error!" << endl;
2087
SerializationOperation2Test(&bv_target_s,
2094
bvect_full1.bit_sub(bvect_full2);
2096
bm::id_t count = bvect_full1.count();
2097
if (count != predicted_count)
2099
cout << "Predicted count error!" << endl;
2100
cout << predicted_count << " " << count << endl;
2107
CheckVectors(bvect_min1, bvect_full1, BITVECT_SIZE/10+10);
2108
CheckVectors(bvect_min1, bv_target_s, BITVECT_SIZE/10+10);
2109
CheckCountRange(bvect_full1, 0, BITVECT_SIZE/10+10);
2115
bvect_mini bvect_min1(BITVECT_SIZE);
2116
bvect_mini bvect_min2(BITVECT_SIZE);
2120
bvect_full1.set_new_blocks_strat(bm::BM_BIT);
2121
bvect_full2.set_new_blocks_strat(bm::BM_BIT);
2123
cout << "------------------------------" << endl;
2124
printf("SUB test stage 3.\n");
2127
FillSets(&bvect_min1, &bvect_full1, 1, BITVECT_SIZE/5, 2);
2128
FillSets(&bvect_min2, &bvect_full2, 1, BITVECT_SIZE/5, 2);
2130
bvect_min1.combine_sub(bvect_min2);
2132
bm::id_t predicted_count = bm::count_sub(bvect_full1, bvect_full2);
2133
bm::id_t predicted_any = bm::any_sub(bvect_full1, bvect_full2);
2134
if (predicted_any == 0 && predicted_count != 0)
2136
cout << "Predicted any error!" << endl;
2141
SerializationOperation2Test(&bv_target_s,
2148
bvect_full1.bit_sub(bvect_full2);
2150
bm::id_t count = bvect_full1.count();
2151
if (count != predicted_count)
2153
cout << "Predicted count error!" << endl;
2158
CheckVectors(bvect_min1, bvect_full1, BITVECT_SIZE);
2160
bvect_full1.optimize();
2161
CheckVectors(bvect_min1, bvect_full1, BITVECT_SIZE);
2162
CheckVectors(bvect_min1, bv_target_s, BITVECT_SIZE);
2163
CheckCountRange(bvect_full1, 0, BITVECT_SIZE);
2171
void XorOperationsTest()
2173
assert(ITERATIONS < BITVECT_SIZE);
2175
cout << "----------------------------------- XorOperationTest" << endl;
2178
bvect_mini bvect_min1(256);
2179
bvect_mini bvect_min2(256);
2183
bvect_full1.set_new_blocks_strat(bm::BM_GAP);
2184
bvect_full2.set_new_blocks_strat(bm::BM_GAP);
2188
printf("XOR test\n");
2190
bvect_min1.set_bit(1);
2191
bvect_min1.set_bit(12);
2192
bvect_min1.set_bit(13);
2194
bvect_min2.set_bit(12);
2195
bvect_min2.set_bit(13);
2197
bvect_min1.combine_xor(bvect_min2);
2199
bvect_full1.set_bit(1);
2200
bvect_full1.set_bit(12);
2201
bvect_full1.set_bit(13);
2203
bvect_full2.set_bit(12);
2204
bvect_full2.set_bit(13);
2206
bm::id_t predicted_count = bm::count_xor(bvect_full1, bvect_full2);
2207
bm::id_t predicted_any = bm::any_xor(bvect_full1, bvect_full2);
2208
if (predicted_any == 0 && predicted_count != 0)
2210
cout << "Predicted any error!" << endl;
2215
SerializationOperation2Test(&bv_target_s,
2223
bvect_full1.bit_xor(bvect_full2);
2225
bm::id_t count = bvect_full1.count();
2226
if (count != predicted_count)
2228
cout << "1.Predicted count error!" << endl;
2232
CheckVectors(bvect_min1, bvect_full1, 256);
2233
CheckVectors(bvect_min1, bv_target_s, 256);
2234
CheckCountRange(bvect_full1, 0, 256);
2235
CheckCountRange(bvect_full1, 128, 256);
2240
bvect_mini bvect_min1(BITVECT_SIZE);
2243
bvect_mini bvect_min2(BITVECT_SIZE);
2246
for (int i = 0; i < 150000; ++i)
2249
bvect_min2.set_bit(i);
2254
bm::id_t predicted_count = bm::count_xor(bvect1, bvect2);
2255
bm::id_t predicted_any = bm::any_xor(bvect1, bvect2);
2256
if (predicted_any == 0 && predicted_count != 0)
2258
cout << "Predicted any error!" << endl;
2263
SerializationOperation2Test(&bv_target_s,
2270
bvect1.bit_xor(bvect2);
2272
bm::id_t count = bvect1.count();
2273
if (count != predicted_count)
2275
cout << "2.Predicted count error!" << endl;
2279
bvect_min1.combine_xor(bvect_min2);
2280
CheckVectors(bvect_min1, bvect1, BITVECT_SIZE, true);
2281
CheckVectors(bvect_min1, bv_target_s, BITVECT_SIZE, true);
2282
CheckCountRange(bvect1, 0, BITVECT_SIZE);
2288
bvect_mini bvect_min1(BITVECT_SIZE);
2291
bvect_mini bvect_min2(BITVECT_SIZE);
2294
for (int i = 0; i < 150000; ++i)
2297
bvect_min1.set_bit(i);
2302
bm::id_t predicted_count = bm::count_xor(bvect1, bvect2);
2303
bm::id_t predicted_any = bm::any_xor(bvect1, bvect2);
2304
if (predicted_any == 0 && predicted_count != 0)
2306
cout << "Predicted any error!" << endl;
2311
SerializationOperation2Test(&bv_target_s,
2318
bvect1.bit_xor(bvect2);
2320
bm::id_t count = bvect1.count();
2321
if (count != predicted_count)
2323
cout << "3.Predicted count error!" << endl;
2327
bvect_min1.combine_xor(bvect_min2);
2328
CheckVectors(bvect_min1, bvect1, BITVECT_SIZE, true);
2329
CheckVectors(bvect_min1, bv_target_s, BITVECT_SIZE, true);
2335
bvect_mini bvect_min1(BITVECT_SIZE);
2338
bvect_mini bvect_min2(BITVECT_SIZE);
2341
for (int i = 0; i < 150000; ++i)
2344
bvect_min1.set_bit(i);
2346
bvect_min2.set_bit(i);
2351
bm::id_t predicted_count = bm::count_xor(bvect1, bvect2);
2352
bm::id_t predicted_any = bm::any_xor(bvect1, bvect2);
2353
if (predicted_any == 0 && predicted_count != 0)
2355
cout << "Predicted any error!" << endl;
2360
SerializationOperation2Test(&bv_target_s,
2367
bvect1.bit_xor(bvect2);
2369
bm::id_t count = bvect1.count();
2370
if (count != predicted_count)
2372
cout << "4.Predicted count error!" << endl;
2373
cout << count << " " << predicted_count << endl;
2378
bvect_min1.combine_xor(bvect_min2);
2379
CheckVectors(bvect_min1, bvect1, BITVECT_SIZE, true);
2386
bvect_mini bvect_min1(BITVECT_SIZE);
2387
bvect_mini bvect_min2(BITVECT_SIZE);
2391
bvect_full1.set_new_blocks_strat(bm::BM_GAP);
2392
bvect_full2.set_new_blocks_strat(bm::BM_GAP);
2394
printf("XOR test stage 2.\n");
2396
FillSets(&bvect_min1, &bvect_full1, 1, BITVECT_SIZE/7, 0);
2397
FillSets(&bvect_min2, &bvect_full2, 1, BITVECT_SIZE/7, 0);
2399
bvect_min1.combine_xor(bvect_min2);
2401
bm::id_t predicted_count = bm::count_xor(bvect_full1, bvect_full2);
2402
bm::id_t predicted_any = bm::any_xor(bvect_full1, bvect_full2);
2403
if (predicted_any == 0 && predicted_count != 0)
2405
cout << "Predicted any error!" << endl;
2410
SerializationOperation2Test(&bv_target_s,
2418
bvect_full1.bit_xor(bvect_full2);
2420
bm::id_t count = bvect_full1.count();
2421
if (count != predicted_count)
2423
cout << "5.Predicted count error!" << endl;
2424
cout << count << " " << predicted_count << endl;
2429
CheckVectors(bvect_min1, bvect_full1, BITVECT_SIZE/10+10);
2430
CheckVectors(bvect_min1, bv_target_s, BITVECT_SIZE/10+10);
2431
CheckCountRange(bvect_full1, 0, BITVECT_SIZE/10+10);
2437
bvect_mini bvect_min1(BITVECT_SIZE);
2438
bvect_mini bvect_min2(BITVECT_SIZE);
2442
bvect_full1.set_new_blocks_strat(bm::BM_BIT);
2443
bvect_full2.set_new_blocks_strat(bm::BM_BIT);
2445
cout << "------------------------------" << endl;
2446
printf("XOR test stage 3.\n");
2449
FillSets(&bvect_min1, &bvect_full1, 1, BITVECT_SIZE/5, 2);
2450
FillSets(&bvect_min2, &bvect_full2, 1, BITVECT_SIZE/5, 2);
2452
bm::id_t predicted_count = bm::count_xor(bvect_full1, bvect_full2);
2453
bm::id_t predicted_any = bm::any_xor(bvect_full1, bvect_full2);
2454
if (predicted_any == 0 && predicted_count != 0)
2456
cout << "Predicted any error!" << endl;
2461
SerializationOperation2Test(&bv_target_s,
2468
bvect_min1.combine_xor(bvect_min2);
2470
bvect_full1.bit_xor(bvect_full2);
2472
bm::id_t count = bvect_full1.count();
2473
if (count != predicted_count)
2475
cout << "6.Predicted count error!" << endl;
2480
CheckVectors(bvect_min1, bvect_full1, BITVECT_SIZE);
2482
bvect_full1.optimize();
2483
CheckVectors(bvect_min1, bvect_full1, BITVECT_SIZE);
2484
CheckVectors(bvect_min1, bv_target_s, BITVECT_SIZE);
2485
CheckCountRange(bvect_full1, 0, BITVECT_SIZE);
2491
cout << "Testing combine_xor" << endl;
2497
bvect_mini bvect_min1(BITVECT_SIZE);
2499
bvect_full1.set_new_blocks_strat(bm::BM_GAP);
2500
bvect_full2.set_new_blocks_strat(bm::BM_GAP);
2502
unsigned ids[10000];
2503
unsigned to_add = 10000;
2506
for (unsigned i = 0; i < to_add; ++i)
2509
bvect_full2.set(bn);
2510
bvect_min1.set_bit(bn);
2514
unsigned* first = ids;
2515
unsigned* last = ids + to_add;
2517
bm::combine_xor(bvect_full1, first, last);
2519
CheckVectors(bvect_min1, bvect_full1, BITVECT_SIZE);
2521
bm::combine_xor(bvect_full1, first, last);
2522
if (bvect_full1.count())
2524
cout << "combine_xor count failed!" << endl;
2534
bvect_mini bvect_min1(BITVECT_SIZE);
2536
bvect_full1.set_new_blocks_strat(bm::BM_GAP);
2537
bvect_full2.set_new_blocks_strat(bm::BM_GAP);
2539
unsigned ids[10000]={0,};
2540
unsigned to_add = 10000;
2542
for (unsigned i = 0; i < to_add; i+=100)
2546
bvect_min1.set_bit(i);
2548
unsigned* first = ids;
2549
unsigned* last = ids + to_add;
2551
bm::combine_xor(bvect_full1, first, last);
2553
CheckVectors(bvect_min1, bvect_full1, BITVECT_SIZE);
2555
bm::combine_xor(bvect_full1, first, last);
2556
if (bvect_full1.count())
2558
cout << "combine_xor count failed!" << endl;
2566
unsigned ids[] = {0, 65536, 65535, 65535*3, 65535*2, 10};
2567
unsigned to_add = sizeof(ids)/sizeof(unsigned);
2570
bvect_mini bvect_min1(BITVECT_SIZE);
2572
bvect_full1.set_new_blocks_strat(bm::BM_BIT);
2573
bvect_full2.set_new_blocks_strat(bm::BM_BIT);
2576
for (unsigned i = 0; i < to_add; ++i)
2579
bvect_full2.set(bn);
2580
bvect_min1.set_bit(bn);
2584
unsigned* first = ids;
2585
unsigned* last = ids + to_add;
2587
bm::combine_xor(bvect_full1, first, last);
2588
CheckVectors(bvect_min1, bvect_full1, BITVECT_SIZE);
2590
bm::combine_xor(bvect_full1, first, last);
2591
if (bvect_full1.count())
2593
cout << "combine_xor count failed!" << endl;
2600
unsigned ids[] = {0, 65536, 65535, 65535*3, 65535*2, 10};
2601
unsigned to_add = sizeof(ids)/sizeof(unsigned);
2604
bvect_mini bvect_min1(BITVECT_SIZE);
2606
bvect_full1.set_new_blocks_strat(bm::BM_GAP);
2607
bvect_full2.set_new_blocks_strat(bm::BM_GAP);
2610
for (unsigned i = 0; i < to_add; ++i)
2613
bvect_full2.set(bn);
2614
bvect_min1.set_bit(bn);
2618
unsigned* first = ids;
2619
unsigned* last = ids + to_add;
2621
bm::combine_xor(bvect_full1, first, last);
2622
CheckVectors(bvect_min1, bvect_full1, BITVECT_SIZE);
2624
bm::combine_xor(bvect_full1, first, last);
2625
if (bvect_full1.count())
2627
cout << "combine_xor count failed!" << endl;
2635
void ComparisonTest()
2637
cout << "-------------------------------------- ComparisonTest" << endl;
2639
bvect_mini bvect_min1(BITVECT_SIZE);
2640
bvect_mini bvect_min2(BITVECT_SIZE);
2645
bvect_full1.set_bit(31);
2646
bvect_full2.set_bit(63);
2648
res1 = bvect_full1.compare(bvect_full2);
2651
printf("Comparison test failed 1\n");
2655
bvect_full1.clear();
2656
bvect_full2.clear();
2658
bvect_min1.set_bit(10);
2659
bvect_min2.set_bit(10);
2661
bvect_full1.set_bit(10);
2662
bvect_full2.set_bit(10);
2664
res1 = bvect_min1.compare(bvect_min2);
2665
res2 = bvect_full1.compare(bvect_full2);
2669
printf("Comparison test failed 1\n");
2673
printf("Comparison 2.\n");
2675
bvect_min1.set_bit(11);
2676
bvect_full1.set_bit(11);
2678
res1 = bvect_min1.compare(bvect_min2);
2679
res2 = bvect_full1.compare(bvect_full2);
2681
if (res1 != res2 && res1 != 1)
2683
printf("Comparison test failed 2\n");
2687
res1 = bvect_min2.compare(bvect_min1);
2688
res2 = bvect_full2.compare(bvect_full1);
2690
if (res1 != res2 && res1 != -1)
2692
printf("Comparison test failed 2.1\n");
2696
printf("Comparison 3.\n");
2698
bvect_full1.optimize();
2700
res1 = bvect_min1.compare(bvect_min2);
2701
res2 = bvect_full1.compare(bvect_full2);
2703
if (res1 != res2 && res1 != 1)
2705
printf("Comparison test failed 3\n");
2709
res1 = bvect_min2.compare(bvect_min1);
2710
res2 = bvect_full2.compare(bvect_full1);
2712
if (res1 != res2 && res1 != -1)
2714
printf("Comparison test failed 3.1\n");
2718
printf("Comparison 4.\n");
2720
bvect_full2.optimize();
2722
res1 = bvect_min1.compare(bvect_min2);
2723
res2 = bvect_full1.compare(bvect_full2);
2725
if (res1 != res2 && res1 != 1)
2727
printf("Comparison test failed 4\n");
2731
res1 = bvect_min2.compare(bvect_min1);
2732
res2 = bvect_full2.compare(bvect_full1);
2734
if (res1 != res2 && res1 != -1)
2736
printf("Comparison test failed 4.1\n");
2740
printf("Comparison 5.\n");
2743
for (i = 0; i < 65536; ++i)
2745
bvect_full1.set_bit(i);
2748
res1 = bvect_min1.compare(bvect_min2);
2749
res2 = bvect_full1.compare(bvect_full2);
2751
if (res1 != res2 && res1 != 1)
2753
printf("Comparison test failed 5\n");
2757
bvect_full1.optimize();
2759
res1 = bvect_min2.compare(bvect_min1);
2760
res2 = bvect_full2.compare(bvect_full1);
2762
if (res1 != res2 && res1 != -1)
2764
printf("Comparison test failed 5.1\n");
2770
void DesrializationTest2()
2773
unsigned size = BITVECT_SIZE - 10;
2779
for (i = 10; i < 165536; i+=2)
2787
struct bvect::statistics st1;
2788
bv1.calc_stat(&st1);
2791
unsigned char* sermem = new unsigned char[st1.max_serialize_mem];
2793
unsigned slen2 = bm::serialize(bv1, sermem);
2797
bm::deserialize(bvtotal, sermem);
2799
operation_deserializer<bvect>::deserialize(bv_target_s,
2805
int res = bvtotal.compare(bv_target_s);
2808
cout << "Operation deserialization error 1" << endl;
2812
for (i = 55000; i < 165536; ++i)
2819
struct bvect::statistics st2;
2820
bv2.calc_stat(&st2);
2822
unsigned char* sermem2 = new unsigned char[st2.max_serialize_mem];
2824
unsigned slen = bm::serialize(bv2, sermem2);
2828
bm::deserialize(bvtotal, sermem2);
2830
operation_deserializer<bvect>::deserialize(bv_target_s,
2834
res = bvtotal.compare(bv_target_s);
2837
cout << "Operation deserialization error 2" << endl;
2841
// bvtotal.optimize();
2844
bm::deserialize(bvtotal, sermem2);
2846
bm::deserialize(bvtotal, sermem);
2848
operation_deserializer<bvect>::deserialize(bv_target_s,
2852
operation_deserializer<bvect>::deserialize(bv_target_s,
2857
res = bvtotal.compare(bv_target_s);
2860
cout << "Deserialization test failed! 3" << endl;
2869
bv_target_s.clear(false);
2873
int repetitions = 25;
2874
for (i = 0; i < repetitions; ++i)
2876
cout << endl << "Deserialization STEP " << i << endl;
2878
bvect_mini* bvect_min1= new bvect_mini(size);
2879
bvect* bvect_full1= new bvect();
2881
FillSetsRandomMethod(bvect_min1, bvect_full1, 1, size, 1);
2883
struct bvect::statistics st;
2884
bvect_full1->calc_stat(&st);
2886
unsigned char* sermem = new unsigned char[st.max_serialize_mem];
2888
unsigned slen = bm::serialize(*bvect_full1, sermem);
2890
unsigned char* smem = new unsigned char[slen];
2891
::memcpy(smem, sermem, slen);
2893
// cout << "Serialized vector" << endl;
2894
// bvect_full1->stat();
2896
// cout << "Before deserialization" << endl;
2898
bm::deserialize(bvtotal, smem);
2899
operation_deserializer<bvect>::deserialize(bv_target_s,
2903
res = bvtotal.compare(bv_target_s);
2906
cout << "Operation deserialization error 2" << endl;
2910
// cout << "After deserialization" << endl;
2914
bv_target_s.optimize();
2916
// cout << "After optimization" << endl;
2924
bv_target_s.clear();
2926
// cout << "Post clear." << endl;
2941
void StressTest(int repetitions)
2944
unsigned RatioSum = 0;
2945
unsigned SRatioSum = 0;
2946
unsigned DeltaSum = 0;
2947
unsigned SDeltaSum = 0;
2949
unsigned clear_count = 0;
2952
bvtotal.set_new_blocks_strat(bm::BM_GAP);
2955
cout << "----------------------------StressTest" << endl;
2957
unsigned size = BITVECT_SIZE - 10;
2958
//size = BITVECT_SIZE / 10;
2960
for (i = 0; i < repetitions; ++i)
2962
cout << endl << " - - - - - - - - - - - - STRESS STEP " << i << endl;
2967
size = BITVECT_SIZE / 10;
2970
size = BITVECT_SIZE / 2;
2973
size = BITVECT_SIZE - 10;
2978
bvect_mini* bvect_min1= new bvect_mini(size);
2979
bvect_mini* bvect_min2= new bvect_mini(size);
2980
bvect* bvect_full1= new bvect();
2981
bvect* bvect_full2= new bvect();
2983
bvect_full1->set_new_blocks_strat(i&1 ? bm::BM_GAP : bm::BM_BIT);
2984
bvect_full2->set_new_blocks_strat(i&1 ? bm::BM_GAP : bm::BM_BIT);
2986
int opt = rand() % 2;
2988
unsigned start1 = 0;
2999
unsigned start2 = 0;
3015
FillSetsRandomMethod(bvect_min1, bvect_full1, start1, size, opt);
3016
FillSetsRandomMethod(bvect_min2, bvect_full2, start2, size, opt);
3020
unsigned arr[bm::set_total_blocks]={0,};
3021
bm::id_t cnt = bvect_full1->count();
3022
unsigned last_block = bvect_full1->count_blocks(arr);
3023
unsigned sum = bm::sum_arr(&arr[0], &arr[last_block+1]);
3027
cout << "Error in function count_blocks." << endl;
3028
cout << "Array sum = " << sum << endl;
3029
cout << "BitCount = " << cnt << endl;
3030
cnt = bvect_full1->count();
3031
for (unsigned i = 0; i <= last_block; ++i)
3035
cout << "[" << i << ":" << arr[i] << "]";
3039
cout << "================" << endl;
3040
bvect_full1->stat();
3046
CheckCountRange(*bvect_full1, start1, BITVECT_SIZE, arr);
3047
CheckIntervals(*bvect_full1, BITVECT_SIZE);
3052
CheckCountRange(*bvect_full2, start2, BITVECT_SIZE);
3054
CheckCountRange(*bvect_full1, 0, start1, arr);
3055
CheckCountRange(*bvect_full2, 0, start2);
3059
cout << "!!!!!!!!!!!!!!!" << endl;
3060
CheckVectors(*bvect_min1, *bvect_full1, size);
3061
cout << "!!!!!!!!!!!!!!!" << endl;
3062
CheckVectors(*bvect_min2, *bvect_full2, size);
3063
cout << "!!!!!!!!!!!!!!!" << endl;
3066
bvect_full1->stat();
3067
cout << " --" << endl;
3068
bvect_full2->stat();
3071
int operation = rand()%4;
3077
cout << "Operation OR" << endl;
3078
bvect_min1->combine_or(*bvect_min2);
3082
cout << "Operation SUB" << endl;
3083
bvect_min1->combine_sub(*bvect_min2);
3087
cout << "Operation XOR" << endl;
3088
bvect_min1->combine_xor(*bvect_min2);
3092
cout << "Operation AND" << endl;
3093
bvect_min1->combine_and(*bvect_min2);
3097
int cres1 = bvect_min1->compare(*bvect_min2);
3105
cout << "Operation OR" << endl;
3107
bm::id_t predicted_count = bm::count_or(*bvect_full1, *bvect_full2);
3108
bm::id_t predicted_any = bm::any_or(*bvect_full1, *bvect_full2);
3109
if (predicted_any == 0 && predicted_count != 0)
3111
cout << "Predicted any error!" << endl;
3116
SerializationOperation2Test(&bv_target_s,
3123
bvect_full1->bit_or(*bvect_full2);
3125
bm::id_t count = bvect_full1->count();
3127
if (count != predicted_count)
3129
cout << "Predicted count error!" << endl;
3130
cout << "Count = " << count << "Predicted count = " << predicted_count << endl;
3133
int res = bvect_full1->compare(bv_target_s);
3136
cout << "Serialization operation failed!" << endl;
3145
cout << "Operation SUB" << endl;
3147
bm::id_t predicted_count = bm::count_sub(*bvect_full1, *bvect_full2);
3148
bm::id_t predicted_any = bm::any_sub(*bvect_full1, *bvect_full2);
3149
if (predicted_any == 0 && predicted_count != 0)
3151
cout << "Predicted any error!" << endl;
3156
SerializationOperation2Test(&bv_target_s,
3163
bvect_full1->bit_sub(*bvect_full2);
3165
bm::id_t count = bvect_full1->count();
3167
if (count != predicted_count)
3169
cout << "Predicted count error!" << endl;
3170
cout << "Count = " << count << "Predicted count = " << predicted_count << endl;
3173
int res = bvect_full1->compare(bv_target_s);
3176
cout << "Serialization operation failed!" << endl;
3186
cout << "Operation XOR" << endl;
3188
bm::id_t predicted_count = bm::count_xor(*bvect_full1, *bvect_full2);
3189
bm::id_t predicted_any = bm::any_xor(*bvect_full1, *bvect_full2);
3190
if (predicted_any == 0 && predicted_count != 0)
3192
cout << "Predicted any error!" << endl;
3197
SerializationOperation2Test(&bv_target_s,
3204
bvect_full1->bit_xor(*bvect_full2);
3206
bm::id_t count = bvect_full1->count();
3208
if (count != predicted_count)
3210
cout << "Predicted count error!" << endl;
3211
cout << "Count = " << count << "Predicted count = " << predicted_count << endl;
3214
int res = bvect_full1->compare(bv_target_s);
3217
cout << "Serialization operation failed!" << endl;
3227
cout << "Operation AND" << endl;
3229
bm::id_t predicted_count = bm::count_and(*bvect_full1, *bvect_full2);
3230
bm::id_t predicted_any = bm::any_and(*bvect_full1, *bvect_full2);
3231
if (predicted_any == 0 && predicted_count != 0)
3233
cout << "Predicted any error!" << endl;
3238
SerializationOperation2Test(&bv_target_s,
3245
bvect_full1->bit_and(*bvect_full2);
3247
bm::id_t count = bvect_full1->count();
3249
if (count != predicted_count)
3251
cout << "Predicted count error!" << endl;
3252
cout << "Count = " << count << "Predicted count = " << predicted_count << endl;
3255
int res = bvect_full1->compare(bv_target_s);
3258
cout << "Serialization operation failed!" << endl;
3266
cout << "Operation comparison" << endl;
3267
CheckVectors(*bvect_min1, *bvect_full1, size);
3269
int cres2 = bvect_full1->compare(*bvect_full2);
3271
CheckIntervals(*bvect_full1, BITVECT_SIZE);
3275
cout << cres1 << " " << cres2 << endl;
3276
cout << bvect_full1->get_first() << " " << bvect_full1->count() << endl;
3277
cout << bvect_full2->get_first() << " " << bvect_full2->count() << endl;
3279
// bvect_full1->stat(1000);
3281
// bvect_full2->stat(1000);
3282
printf("Bitset comparison operation failed.\n");
3287
bvect bv1(*bvect_full1);
3288
unsigned idx = rand() % size;
3293
changed = bv1.set_bit_conditional(idx, true, false);
3296
cout << "Set bit conditional failed!" << endl;
3302
cout << "Set bit conditional failed!" << endl;
3306
changed = bv1.set_bit_conditional(idx, false, false);
3309
cout << "Set bit conditional failed!" << endl;
3312
changed = bv1.set_bit_conditional(idx, true, true);
3315
cout << "Set bit conditional failed!" << endl;
3318
changed = bv1.set_bit_conditional(idx, false, true);
3321
cout << "Set bit conditional failed!" << endl;
3327
cout << "Set bit conditional failed!" << endl;
3333
changed = bv1.set_bit_conditional(idx, false, true);
3336
cout << "Set bit conditional failed!" << endl;
3339
changed = bv1.set_bit_conditional(idx, true, false);
3342
cout << "Set bit conditional failed!" << endl;
3348
cout << "Set bit conditional failed!" << endl;
3359
struct bvect::statistics st1;
3360
bvect_full1->calc_stat(&st1);
3361
bvect_full1->optimize();
3362
bvect_full1->optimize_gap_size();
3363
struct bvect::statistics st2;
3364
bvect_full1->calc_stat(&st2);
3366
unsigned Ratio = (st2.memory_used * 100)/st1.memory_used;
3368
DeltaSum+=st1.memory_used - st2.memory_used;
3370
cout << "Optimization statistics: " << endl
3371
<< " MemUsedBefore=" << st1.memory_used
3372
<< " MemUsed=" << st2.memory_used
3373
<< " Ratio=" << Ratio << "%"
3374
<< " Delta=" << st1.memory_used - st2.memory_used
3377
cout << "Optimization comparison" << endl;
3379
CheckVectors(*bvect_min1, *bvect_full1, size);
3381
bvect_full1->set_gap_levels(gap_len_table_min<true>::_len);
3382
CheckVectors(*bvect_min1, *bvect_full1, size);
3383
CheckIntervals(*bvect_full1, BITVECT_SIZE);
3385
//CheckCountRange(*bvect_full1, 0, size);
3389
bvect_full1->calc_stat(&st2);
3391
cout << "Memory allocation: " << st2.max_serialize_mem << endl;
3392
unsigned char* sermem = new unsigned char[st2.max_serialize_mem];
3394
// bvect_full1->stat();
3396
cout << "Serialization...";
3398
bm::serialize(*bvect_full1, sermem,
3399
BM_NO_GAP_LENGTH|BM_NO_BYTE_ORDER);
3400
cout << "Ok" << endl;
3404
unsigned SRatio = (slen*100)/st2.memory_used;
3406
SDeltaSum+=st2.memory_used - slen;
3409
cout << "Serialized mem_max = " << st2.max_serialize_mem
3410
<< " size= " << slen
3411
<< " Ratio=" << SRatio << "%"
3412
<< " Delta=" << st2.memory_used - slen
3415
bvect* bvect_full3= new bvect();
3416
unsigned char* new_sermem = new unsigned char[slen];
3417
memcpy(new_sermem, sermem, slen);
3420
cout << "Deserialization...";
3422
bm::deserialize(*bvect_full3, new_sermem);
3424
bm::deserialize(bvtotal, new_sermem);
3426
bvect* bv_target_s=new bvect();
3427
operation_deserializer<bvect>::deserialize(*bv_target_s,
3432
cout << "Ok." << endl;
3433
delete [] new_sermem;
3435
cout << "Optimization...";
3437
cout << "Ok." << endl;
3441
if (clear_count == 4)
3447
cout << "Serialization comparison" << endl;
3449
CheckVectors(*bvect_min1, *bvect_full3, size, true);
3450
int res = bv_target_s->compare(*bvect_full3);
3453
CheckVectors(*bvect_min1, *bv_target_s, size, true);
3463
cout << "Repetitions:" << i <<
3464
" AVG optimization ratio:" << RatioSum/i
3465
<< " AVG Delta:" << DeltaSum/i
3467
<< " AVG serialization Ratio:"<< SRatioSum/i
3468
<< " Delta:" << SDeltaSum/i
3474
cout << "-------------------------------------------GAPCheck" << endl;
3479
bvect_mini bvect_min(bm::gap_max_bits);
3482
for( i = 0; i < 454; ++i)
3484
bvect_min.set_bit(i);
3488
for(i = 0; i < 254; ++i)
3490
bvect_min.clear_bit(i);
3494
for(i = 5; i < 10; ++i)
3496
bvect_min.set_bit(i);
3500
for( i = 0; i < bm::gap_max_bits; ++i)
3502
int bit1 = (gapv.is_bit_true(i) == 1);
3503
int bit2 = (bvect_min.is_bit_true(i) != 0);
3504
int bit3 = (gapv.test(i) == 1);
3507
cout << "problem with bit comparison " << i << endl;
3512
cout << "problem with bit test comparison " << i << endl;
3523
int bit = gapv.is_bit_true(65535);
3527
cout << "Bit != 1" << endl;
3532
for (i = 0; i < 65536; ++i)
3534
bit = gapv.is_bit_true(i);
3537
cout << "2.Bit != 1" << endl;
3541
unsigned cnt = gapv.count_range(0, 65535);
3544
cout << "count_range failed:" << cnt << endl;
3548
CheckCountRange(gapv, 10, 20);
3549
CheckCountRange(gapv, 0, 20);
3551
printf("gapv 1 check ok\n");
3558
int bit = gapv.is_bit_true(65535);
3559
int bit1 = gapv.test(65535);
3562
cout << "Bit != 0" << endl;
3567
for (i = 0; i < 65536; ++i)
3569
bit = gapv.is_bit_true(i);
3570
bit1 = gapv.test(i);
3573
cout << "2.Bit != 0 bit =" << i << endl;
3578
cout << "2.Bit test != 0 bit =" << i << endl;
3582
unsigned cnt = gapv.count_range(0, 65535);
3585
cout << "count_range failed:" << cnt << endl;
3588
CheckCountRange(gapv, 10, 20);
3589
CheckCountRange(gapv, 0, 20);
3591
printf("gapv 2 check ok\n");
3601
CheckCountRange(gapv, 0, 20);
3603
int bit = gapv.is_bit_true(0);
3607
cout << "Trouble" << endl;
3611
bit = gapv.is_bit_true(1);
3614
cout << "Trouble 2." << endl;
3619
bit = gapv.is_bit_true(2);
3622
cout << "Trouble 3." << endl;
3640
CheckCountRange(gapv, 4, 5);
3641
CheckCountRange(gapv, 3, 5);
3644
CheckCountRange(gapv, 3, 3);
3645
CheckCountRange(gapv, 3, 5);
3649
int bit = gapv.is_bit_true(0);
3652
cout << "Bug" << endl;
3654
bit = gapv.is_bit_true(1);
3657
cout << "Bug2" << endl;
3665
printf("gapv 3 check ok\n");
3670
bvect_mini bvect_min(bm::gap_max_bits);
3671
cout << "++++++1" << endl;
3672
print_gap(gapv, 10);
3673
gapv.set_bit(bm::gap_max_bits-1);
3675
print_gap(gapv, 10);
3677
//cout << "++++++2" << endl;
3678
//cout << "m_buf=" << bvect_min.m_buf << endl;
3680
bvect_min.set_bit(bm::gap_max_bits-1);
3681
cout << "++++++3" << endl;
3685
bvect_min.set_bit(5);
3686
cout << "++++++4" << endl;
3688
CheckCountRange(gapv, 13, 150);
3692
for (i = 0; i < bm::gap_max_bits; ++i)
3696
int bit1 = (gapv.is_bit_true(i) == 1);
3697
int bit2 = (bvect_min.is_bit_true(i) != 0);
3698
int bit3 = (gapv.test(i) == 1);
3701
cout << "problem with bit comparison " << i << endl;
3705
cout << "problem with bit test comparison " << i << endl;
3711
bvect_min.clear_bit(5);
3714
for ( i = 0; i < bm::gap_max_bits; ++i)
3718
int bit1 = (gapv.is_bit_true(i) == 1);
3719
int bit2 = (bvect_min.is_bit_true(i) != 0);
3720
int bit3 = (gapv.test(i) == 1);
3723
cout << "2.problem with bit comparison " << i << endl;
3727
cout << "2.problem with bit test comparison " << i << endl;
3730
printf("gapv check 4 ok.\n");
3735
bvect_mini bvect_min(65536);
3738
for (i = 10; i > 0; i-=2)
3740
bvect_min.set_bit(i);
3743
CheckCountRange(gapv, 0, i);
3745
int bit1 = (gapv.is_bit_true(i) == 1);
3746
int bit2 = (bvect_min.is_bit_true(i) != 0);
3747
int bit3 = (gapv.test(i) != 0);
3750
cout << "3.problem with bit comparison " << i << endl;
3754
cout << "3.problem with bit test comparison " << i << endl;
3758
for (i = 0; i < (int)bm::gap_max_bits; ++i)
3760
int bit1 = (gapv.is_bit_true(i) == 1);
3761
int bit2 = (bvect_min.is_bit_true(i) != 0);
3762
int bit3 = (gapv.test(i) == 1);
3766
cout << "3.problem with bit comparison " << i << endl;
3770
cout << "3.problem with bit test comparison " << i << endl;
3773
printf("gapv check 5 ok.\n");
3778
bvect_mini bvect_min(bm::gap_max_bits);
3781
for (i = 0; i < 25; ++i)
3783
unsigned id = random_minmax(0, bm::gap_max_bits);
3784
bvect_min.set_bit(id);
3787
CheckCountRange(gapv, 0, id);
3788
CheckCountRange(gapv, id, 65535);
3791
for (i = 0; i < (int)bm::gap_max_bits; ++i)
3793
int bit1 = (gapv.is_bit_true(i) == 1);
3794
int bit2 = (bvect_min.is_bit_true(i) != 0);
3797
cout << "4.problem with bit comparison " << i << endl;
3801
for (i = bm::gap_max_bits; i < 0; --i)
3803
int bit1 = (gapv.is_bit_true(i) == 1);
3804
int bit2 = (bvect_min.is_bit_true(i) != 0);
3807
cout << "5.problem with bit comparison " << i << endl;
3810
printf("gapv check 6 ok.\n");
3814
printf("gapv random bit set check ok.\n");
3817
// conversion functions test
3820
// aligned position test
3827
unsigned* buf = (unsigned*) bvect.get_block(0);
3829
bm::or_bit_block(buf, 0, 4);
3830
unsigned cnt = bm::bit_block_calc_count_range(buf, 0, 3);
3833
bool bit = bvect.get_bit(0);
3835
bit = bvect.get_bit(1);
3837
bit = bvect.get_bit(2);
3839
bit = bvect.get_bit(3);
3841
bit = bvect.get_bit(4);
3844
bm::or_bit_block(buf, 0, 36);
3845
cnt = bm::bit_block_calc_count_range(buf, 0, 35);
3848
for (int i = 0; i < 36; ++i)
3850
bit = (bvect.get_bit(i) != 0);
3853
bit = (bvect.get_bit(36) != 0);
3856
unsigned count = bvect.recalc_count();
3857
assert(count == 36);
3859
cout << "Aligned position test ok." << endl;
3865
// unaligned position test
3871
unsigned* buf = (unsigned*) bvect.get_block(0);
3873
bm::or_bit_block(buf, 5, 32);
3874
bool bit = (bvect.get_bit(4) != 0);
3876
unsigned cnt = bm::bit_block_calc_count_range(buf, 5, 5+32-1);
3878
cnt = bm::bit_block_calc_count_range(buf, 5, 5+32);
3882
for (i = 5; i < 4 + 32; ++i)
3884
bit = bvect.get_bit(i);
3887
int count = bvect.recalc_count();
3890
cout << "Unaligned position ok." << endl;
3896
cout << "random test" << endl;
3903
unsigned* buf = (unsigned*) bvect.get_block(0);
3904
for (int i = 0; i < 5000; ++i)
3906
unsigned start = rand() % 65535;
3907
unsigned end = rand() % 65535;
3914
unsigned len = end - start;
3917
bm::or_bit_block(buf, start, len);
3918
unsigned cnt = bm::bit_block_calc_count_range(buf, start, end);
3921
cout << "random test: count_range comparison failed. "
3922
<< " LEN = " << len << " cnt = " << cnt
3927
unsigned count = bvect.recalc_count();
3931
cout << "random test: count comparison failed. "
3932
<< " LEN = " << len << " count = " << count
3937
for (unsigned j = start; j < end; ++j)
3939
bool bit = bvect.get_bit(j);
3942
cout << "random test: bit comparison failed. bit#"
3953
cout << "*" << flush;
3957
cout << endl << "Random test Ok." << endl;
3964
cout << "Conversion test" << endl;
3977
CheckCountRange(gapv, 3, 15);
3979
print_gap(gapv, 100);
3983
unsigned* buf = (unsigned*) bvect.get_block(0);
3986
gapv.convert_to_bitset(buf);
3989
unsigned bitcount = bvect.recalc_count();
3994
cout << "test failed: bitcout = " << bitcount << endl;
3999
gap_vector gapv1(0);
4000
gap_word_t* gap_buf = gapv1.get_buf();
4002
bit_convert_to_gap(gap_buf, buf, bm::gap_max_bits, bm::gap_max_buff_len);
4003
print_gap(gapv1, 100);
4005
bitcount = gapv1.bit_count();
4008
cout << "2.test_failed: bitcout = " << bitcount << endl;
4012
printf("conversion test ok.\n");
4019
// special case 1: operand is all 1
4020
gap_vector gapv1(0);
4022
gap_vector gapv2(1);
4024
gapv1.combine_and(gapv2.get_buf());
4026
print_gap(gapv1, 0);
4028
int count = gapv1.bit_count();
4030
int bit = gapv1.is_bit_true(2);
4033
cout << "Wrong bit" << endl;
4036
CheckCountRange(gapv1, 0, 17);
4041
// special case 2: src is all 1
4042
gap_vector gapv1(1);
4043
gap_vector gapv2(0);
4046
gapv1.combine_and(gapv2.get_buf());
4048
print_gap(gapv1, 0);
4050
int count = gapv1.bit_count();
4052
int bit = gapv1.is_bit_true(2);
4059
gap_vector gapv1(0);
4063
print_gap(gapv1, 0);
4065
gap_vector gapv2(0);
4068
print_gap(gapv2, 0);
4070
bm::gap_buff_op((gap_word_t*)gapv.get_buf(),
4072
gapv2.get_buf(), 0, bm::and_op);
4077
int bit1 = (gapv.is_bit_true(3) == 1);
4080
cout << "Checking failed." << endl;
4084
gapv1.combine_or(gapv2);
4085
print_gap(gapv1, 0);
4091
printf("gap AND test 1.\n");
4092
gap_vector gapv1(0);
4093
gap_vector gapv2(0);
4094
bvect_mini bvect_min1(65536);
4095
bvect_mini bvect_min2(65536);
4097
gapv1.set_bit(65535);
4098
bvect_min1.set_bit(65535);
4100
bvect_min1.set_bit(4);
4102
gapv2.set_bit(65535);
4103
bvect_min2.set_bit(65535);
4105
bvect_min2.set_bit(3);
4106
CheckCountRange(gapv2, 3, 65535);
4110
printf("vect1:"); print_gap(gapv1, 0);
4111
printf("vect2:");print_gap(gapv2, 0);
4113
gapv1.combine_and(gapv2.get_buf());
4114
printf("vect1:");print_gap(gapv1, 0);
4117
unsigned bit1 = gapv1.is_bit_true(65535);
4120
bvect_min1.combine_and(bvect_min2);
4121
CheckGAPMin(gapv1, bvect_min1, bm::gap_max_bits);
4125
printf("gap random AND test.\n");
4126
gap_vector gapv1(0);
4127
gap_vector gapv2(0);
4128
bvect_mini bvect_min1(65536);
4129
bvect_mini bvect_min2(65536);
4132
for (i = 0; i < 25; ++i)
4134
unsigned id = random_minmax(0, 65535);
4135
bvect_min1.set_bit(id);
4138
CheckCountRange(gapv1, 0, id);
4139
CheckCountRange(gapv1, id, 65535);
4141
for (i = 0; i < 25; ++i)
4143
unsigned id = random_minmax(0, 65535);
4144
bvect_min2.set_bit(id);
4149
gapv1.combine_and(gapv2.get_buf());
4152
bvect_min1.combine_and(bvect_min2);
4154
CheckGAPMin(gapv1, bvect_min1, bm::gap_max_bits);
4156
printf("gap random AND test ok.\n");
4161
printf("gap OR test.\n");
4163
gap_vector gapv1(0);
4164
gap_vector gapv2(0);
4169
gapv1.combine_or(gapv2);
4171
print_gap(gapv1, 0);
4172
int bit1 = (gapv1.is_bit_true(0) == 1);
4174
bit1=(gapv1.is_bit_true(2) == 1);
4176
bit1=(gapv1.is_bit_true(3) == 1);
4181
printf("gap XOR test.\n");
4183
gap_vector gapv1(0);
4184
gap_vector gapv2(0);
4190
print_gap(gapv1, 0);
4191
print_gap(gapv2, 0);
4193
gapv1.combine_xor(gapv2);
4195
print_gap(gapv1, 0);
4196
int bit1 = (gapv1.is_bit_true(0) == 0);
4198
bit1=(gapv1.is_bit_true(2) == 1);
4200
bit1=(gapv1.is_bit_true(3) == 1);
4202
bit1=(gapv1.is_bit_true(4) == 0);
4210
printf("gap random OR test.\n");
4211
gap_vector gapv1(0);
4212
gap_vector gapv2(0);
4213
bvect_mini bvect_min1(bm::gap_max_bits);
4214
bvect_mini bvect_min2(bm::gap_max_bits);
4216
for (i = 0; i < 10; ++i)
4218
unsigned id = random_minmax(0, 100);
4219
bvect_min1.set_bit(id);
4223
for (i = 0; i < 10; ++i)
4225
unsigned id = random_minmax(0, 100);
4226
bvect_min2.set_bit(id);
4231
print_mv(bvect_min1, 64);
4232
print_mv(bvect_min2, 64);
4234
gapv1.combine_or(gapv2);
4237
bvect_min1.combine_or(bvect_min2);
4239
print_mv(bvect_min1, 64);
4241
CheckGAPMin(gapv1, bvect_min1, bm::gap_max_bits);
4243
printf("gap random OR test ok.\n");
4250
printf("gap random SUB test.\n");
4251
gap_vector gapv1(0);
4252
gap_vector gapv2(0);
4253
bvect_mini bvect_min1(bm::gap_max_bits);
4254
bvect_mini bvect_min2(bm::gap_max_bits);
4256
for (i = 0; i < 25; ++i)
4258
unsigned id = random_minmax(0, 100);
4259
bvect_min1.set_bit(id);
4263
for (i = 0; i < 25; ++i)
4265
unsigned id = random_minmax(0, 100);
4266
bvect_min2.set_bit(id);
4271
print_mv(bvect_min1, 64);
4272
print_mv(bvect_min2, 64);
4274
gapv1.combine_sub(gapv2);
4277
bvect_min1.combine_sub(bvect_min2);
4279
print_mv(bvect_min1, 64);
4281
CheckGAPMin(gapv1, bvect_min1, bm::gap_max_bits);
4283
printf("gap random SUB test ok.\n");
4287
printf("GAP comparison test.\n");
4289
gap_vector gapv1(0);
4290
gap_vector gapv2(0);
4295
int res = gapv1.compare(gapv2);
4298
printf("GAP comparison failed!");
4305
res = gapv1.compare(gapv2);
4308
printf("GAP comparison failed!");
4315
res = gapv1.compare(gapv2);
4318
printf("GAP comparison failed!");
4324
res = gapv1.compare(gapv2);
4327
printf("GAP comparison failed!");
4333
res = gapv1.compare(gapv2);
4336
printf("GAP comparison failed!");
4346
// -----------------------------------------------------------------------------
4351
cout << "--------------------------------- MutationTest" << endl;
4353
bvect_mini bvect_min(BITVECT_SIZE);
4356
printf("\nMutation test.\n");
4358
bvect_full.set_new_blocks_strat(bm::BM_GAP);
4360
bvect_full.set_bit(5);
4361
bvect_full.set_bit(5);
4363
bvect_min.set_bit(5);
4365
bvect_full.set_bit(65535);
4366
bvect_full.set_bit(65537);
4367
bvect_min.set_bit(65535);
4368
bvect_min.set_bit(65537);
4370
bvect_min.set_bit(100000);
4371
bvect_full.set_bit(100000);
4374
// detailed vectors verification
4375
::CheckVectors(bvect_min, bvect_full, ITERATIONS, false);
4378
for (i = 5; i < 20000; i+=3)
4380
bvect_min.set_bit(i);
4381
bvect_full.set_bit(i);
4384
::CheckVectors(bvect_min, bvect_full, ITERATIONS, false);
4386
for (i = 100000; i < 200000; i+=3)
4388
bvect_min.set_bit(i);
4389
bvect_full.set_bit(i);
4392
::CheckVectors(bvect_min, bvect_full, 300000);
4394
// set-clear functionality
4397
printf("Set-clear functionality test.");
4399
bvect_mini bvect_min(BITVECT_SIZE);
4401
bvect_full.set_new_blocks_strat(bm::BM_GAP);
4404
for (i = 100000; i < 100010; ++i)
4406
bvect_min.set_bit(i);
4407
bvect_full.set_bit(i);
4409
::CheckVectors(bvect_min, bvect_full, 300000);
4411
for (i = 100000; i < 100010; ++i)
4413
bvect_min.clear_bit(i);
4414
bvect_full.clear_bit(i);
4416
::CheckVectors(bvect_min, bvect_full, 300000);
4418
bvect_full.optimize();
4419
CheckVectors(bvect_min, bvect_full, 65536);//max+10);
4424
void MutationOperationsTest()
4427
cout << "------------------------------------ MutationOperationsTest" << endl;
4429
printf("Mutation operations test 1.\n");
4431
bvect_mini bvect_min1(BITVECT_SIZE);
4432
bvect_mini bvect_min2(BITVECT_SIZE);
4436
bvect_full1.set_new_blocks_strat(bm::BM_GAP);
4437
bvect_full2.set_new_blocks_strat(bm::BM_BIT);
4439
bvect_full1.set_bit(100);
4440
bvect_min1.set_bit(100);
4443
for(i = 0; i < 10000; i+=2)
4445
bvect_full2.set_bit(i);
4446
bvect_min2.set_bit(i);
4449
CheckVectors(bvect_min2, bvect_full2, 65536, true);
4451
bvect_min1.combine_and(bvect_min2);
4452
bvect_full1.bit_and(bvect_full2);
4454
CheckVectors(bvect_min1, bvect_full1, 65536);//max+10);
4458
printf("Mutation operations test 2.\n");
4460
unsigned delta = 65536;
4461
bvect_mini bvect_min1(BITVECT_SIZE);
4462
bvect_mini bvect_min2(BITVECT_SIZE);
4466
bvect_full1.set_new_blocks_strat(bm::BM_GAP);
4467
bvect_full2.set_new_blocks_strat(bm::BM_GAP);
4470
for(i = 0; i < 1000; i+=1)
4472
bvect_full1.set_bit(delta+i);
4473
bvect_min1.set_bit(delta+i);
4476
for(i = 0; i < 100; i+=2)
4478
bvect_full2.set_bit(delta+i);
4479
bvect_min2.set_bit(delta+i);
4481
// CheckVectors(bvect_min2, bvect_full2, 65536);
4483
bvect_min1.combine_and(bvect_min2);
4484
bvect_full1.bit_and(bvect_full2);
4486
CheckVectors(bvect_min1, bvect_full1, 65536);//max+10);
4487
bvect_full1.optimize();
4488
CheckVectors(bvect_min1, bvect_full1, 65536);//max+10);
4493
bvect_mini bvect_min1(BITVECT_SIZE);
4496
bvect_full1.set_bit(3);
4497
bvect_min1.set_bit(3);
4499
struct bvect::statistics st;
4500
bvect_full1.calc_stat(&st);
4504
unsigned char* sermem = new unsigned char[st.max_serialize_mem];
4505
unsigned slen = bm::serialize(bvect_full1, sermem);
4506
cout << "BVECTOR SERMEM=" << slen << endl;
4510
bm::deserialize(bvect_full3, sermem);
4512
CheckVectors(bvect_min1, bvect_full3, 100, true);
4516
printf("Mutation operations test 3.\n");
4518
bvect_mini bvect_min1(BITVECT_SIZE);
4519
bvect_mini bvect_min2(BITVECT_SIZE);
4523
bvect_full1.set_new_blocks_strat(bm::BM_GAP);
4524
bvect_full2.set_new_blocks_strat(bm::BM_GAP);
4527
unsigned min = BITVECT_SIZE / 2 - ITERATIONS;
4528
unsigned max = BITVECT_SIZE / 2 + ITERATIONS;
4529
if (max > BITVECT_SIZE)
4530
max = BITVECT_SIZE - 1;
4532
unsigned len = max - min;
4534
FillSets(&bvect_min1, &bvect_full1, min, max, 0);
4535
FillSets(&bvect_min1, &bvect_full1, 0, len, 5);
4536
printf("Bvect_FULL 1 STAT\n");
4538
// CheckVectors(bvect_min1, bvect_full1, max+10, false);
4539
FillSets(&bvect_min2, &bvect_full2, min, max, 0);
4540
FillSets(&bvect_min2, &bvect_full2, 0, len, 0);
4541
printf("Bvect_FULL 2 STAT\n");
4543
// CheckVectors(bvect_min2, bvect_full2, max+10);
4546
bvect_min1.combine_and(bvect_min2);
4547
bvect_full1.bit_and(bvect_full2);
4548
printf("Bvect_FULL 1 STAT after AND\n");
4551
CheckVectors(bvect_min1, bvect_full1, max+10, false);
4553
struct bvect::statistics st;
4554
bvect_full1.calc_stat(&st);
4555
cout << "BVECTOR: GAP=" << st.gap_blocks << " BIT=" << st.bit_blocks
4556
<< " MEM=" << st.memory_used << " SERMAX=" << st.max_serialize_mem
4558
cout << "MINIVECT: " << bvect_min1.mem_used() << endl;
4560
bvect_full1.optimize();
4563
CheckVectors(bvect_min1, bvect_full1, max+10, false);
4565
bvect_full1.calc_stat(&st);
4566
cout << "BVECTOR: GAP=" << st.gap_blocks << " BIT=" << st.bit_blocks
4567
<< " MEM=" << st.memory_used << " SERMAX=" << st.max_serialize_mem
4569
cout << "MINIVECT: " << bvect_min1.mem_used() << endl;
4575
unsigned char* sermem = new unsigned char[st.max_serialize_mem];
4576
unsigned slen = bm::serialize(bvect_full1, sermem);
4577
cout << "BVECTOR SERMEM=" << slen << endl;
4582
bm::deserialize(bvect_full3, sermem);
4584
CheckVectors(bvect_min1, bvect_full3, max+10, true);
4589
cout << "Copy constructor check." << endl;
4593
bvect bvect_full4(bvect_full3);
4595
CheckVectors(bvect_min1, bvect_full4, max+10, true);
4604
void SerializationTest()
4607
cout << " ----------------------------------- SerializationTest" << endl;
4609
cout << "Serialization STEP 0" << endl;
4612
unsigned size = BITVECT_SIZE/6000;
4615
bvect_mini* bvect_min1= new bvect_mini(BITVECT_SIZE);
4616
bvect* bvect_full1= new bvect();
4617
bvect* bvect_full2= new bvect();
4618
bvect* bv_target_s= new bvect();
4620
bvect_full1->set_new_blocks_strat(bm::BM_BIT);
4621
bvect_full2->set_new_blocks_strat(bm::BM_BIT);
4623
for(unsigned i = 0; i < size; ++i)
4625
bvect_full1->set_bit(i);
4626
bvect_min1->set_bit(i);
4629
bvect_full1->optimize();
4630
CheckVectors(*bvect_min1, *bvect_full1, size, true);
4634
bvect::statistics st;
4635
bvect_full1->calc_stat(&st);
4636
unsigned char* sermem = new unsigned char[st.max_serialize_mem];
4637
unsigned slen = bm::serialize(*bvect_full1, sermem);
4638
cout << "Serialized mem_max = " << st.max_serialize_mem
4639
<< " size= " << slen
4640
<< " Ratio=" << (slen*100)/st.max_serialize_mem << "%"
4643
bm::deserialize(*bvect_full2, sermem);
4644
operation_deserializer<bvect>::deserialize(*bv_target_s,
4651
CheckVectors(*bvect_min1, *bvect_full2, size, true);
4652
CheckVectors(*bvect_min1, *bv_target_s, size, true);
4664
unsigned size = BITVECT_SIZE/6000;
4667
bvect_mini* bvect_min1= new bvect_mini(BITVECT_SIZE);
4668
bvect* bvect_full1= new bvect();
4669
bvect* bvect_full2= new bvect();
4670
bvect* bv_target_s= new bvect();
4672
bvect_full1->set_new_blocks_strat(bm::BM_BIT);
4673
bvect_full2->set_new_blocks_strat(bm::BM_BIT);
4675
bvect_full1->set_bit(131072);
4676
bvect_min1->set_bit(131072);
4679
bvect_full1->optimize();
4681
bvect::statistics st;
4682
bvect_full1->calc_stat(&st);
4683
unsigned char* sermem = new unsigned char[st.max_serialize_mem];
4684
unsigned slen = bm::serialize(*bvect_full1, sermem);
4685
cout << "Serialized mem_max = " << st.max_serialize_mem
4686
<< " size= " << slen
4687
<< " Ratio=" << (slen*100)/st.max_serialize_mem << "%"
4690
bm::deserialize(*bvect_full2, sermem);
4691
operation_deserializer<bvect>::deserialize(*bv_target_s,
4698
CheckVectors(*bvect_min1, *bvect_full2, size, true);
4699
CheckVectors(*bvect_min1, *bv_target_s, size, true);
4709
cout << "Serialization STEP 1." << endl;
4712
bvect_mini bvect_min1(BITVECT_SIZE);
4715
bvect_full1.set_new_blocks_strat(bm::BM_GAP);
4717
unsigned min = BITVECT_SIZE / 2 - ITERATIONS;
4718
unsigned max = BITVECT_SIZE / 2 + ITERATIONS;
4719
if (max > BITVECT_SIZE)
4720
max = BITVECT_SIZE - 1;
4722
unsigned len = max - min;
4724
FillSets(&bvect_min1, &bvect_full1, min, max, 0);
4725
FillSets(&bvect_min1, &bvect_full1, 0, len, 5);
4727
// shot some random bits
4730
for (i = 0; i < 10000; ++i)
4732
unsigned bit = rand() % BITVECT_SIZE;
4733
bvect_full1.set_bit(bit);
4734
bvect_min1.set_bit(bit);
4737
bvect::statistics st;
4738
bvect_full1.calc_stat(&st);
4740
unsigned char* sermem = new unsigned char[st.max_serialize_mem];
4743
unsigned slen = bm::serialize(bvect_full1, sermem);
4745
cout << "Serialized len = " << slen << endl;
4748
bm::deserialize(bvect_full3, sermem);
4749
bvect* bv_target_s = new bvect();
4750
operation_deserializer<bvect>::deserialize(*bv_target_s,
4755
CheckVectors(bvect_min1, bvect_full3, max+10, true);
4756
CheckVectors(bvect_min1, *bv_target_s, max+10, true);
4764
cout << "Stage 2" << endl;
4768
bvect_mini* bvect_min1= new bvect_mini(BITVECT_SIZE);
4769
// bm::bvect_mini* bvect_min2= new bm::bvect_mini(BITVECT_SIZE);
4770
bvect* bvect_full1= new bvect();
4771
bvect* bvect_full2= new bvect();
4773
bvect_full1->set_new_blocks_strat(bm::BM_GAP);
4774
bvect_full2->set_new_blocks_strat(bm::BM_GAP);
4776
FillSetsRandomMethod(bvect_min1, bvect_full1, 1, BITVECT_SIZE-10, 1);
4777
// FillSetsRandomMethod(bvect_min2, bvect_full2, 1, BITVECT_SIZE-10, 1);
4779
//bvect_full1->stat();
4780
cout << "Filling. OK." << endl;
4781
bvect::statistics st;
4782
bvect_full1->calc_stat(&st);
4783
cout << st.max_serialize_mem << endl;
4784
unsigned char* sermem = new unsigned char[st.max_serialize_mem];
4785
cout << "Serialization" << endl;
4786
unsigned slen = bm::serialize(*bvect_full1, sermem);
4788
cout << "Serialized mem_max = " << st.max_serialize_mem
4789
<< " size= " << slen
4790
<< " Ratio=" << (slen*100)/st.max_serialize_mem << "%"
4792
cout << "Deserialization" << endl;
4793
bm::deserialize(*bvect_full2, sermem);
4794
cout << "Deserialization ok" << endl;
4795
bvect* bv_target_s=new bvect();
4796
operation_deserializer<bvect>::deserialize(*bv_target_s,
4801
CheckVectors(*bvect_min1, *bvect_full2, BITVECT_SIZE, true);
4802
CheckVectors(*bvect_min1, *bv_target_s, BITVECT_SIZE, true);
4815
cout << "Stage 3" << endl;
4819
bvect_mini* bvect_min1= new bvect_mini(BITVECT_SIZE);
4820
bvect_mini* bvect_min2= new bvect_mini(BITVECT_SIZE);
4821
bvect* bvect_full1= new bvect();
4822
bvect* bvect_full2= new bvect();
4824
bvect_full1->set_new_blocks_strat(bm::BM_GAP);
4825
bvect_full2->set_new_blocks_strat(bm::BM_GAP);
4828
FillSetsRandomMethod(bvect_min1, bvect_full1, 1, BITVECT_SIZE, 1);
4829
FillSetsRandomMethod(bvect_min2, bvect_full2, 1, BITVECT_SIZE, 1);
4831
bvect::statistics st;
4832
bvect_full1->calc_stat(&st);
4833
unsigned char* sermem = new unsigned char[st.max_serialize_mem];
4834
unsigned slen = bm::serialize(*bvect_full1, sermem);
4837
cout << "Serialized mem_max = " << st.max_serialize_mem
4838
<< " size= " << slen
4839
<< " Ratio=" << (slen*100)/st.max_serialize_mem << "%"
4842
bvect* bv_target_s=new bvect(*bvect_full2);
4843
bv_target_s->stat();
4845
bm::deserialize(*bvect_full2, sermem);
4847
operation_deserializer<bvect>::deserialize(*bv_target_s,
4853
bvect_min2->combine_or(*bvect_min1);
4856
CheckVectors(*bvect_min2, *bvect_full2, BITVECT_SIZE, true);
4857
CheckVectors(*bvect_min2, *bv_target_s, BITVECT_SIZE, true);
4866
cout << "Stage 4. " << endl;
4869
unsigned size = BITVECT_SIZE/3;
4872
bvect_mini* bvect_min1= new bvect_mini(BITVECT_SIZE);
4873
bvect* bvect_full1= new bvect();
4874
bvect* bvect_full2= new bvect();
4876
bvect_full1->set_new_blocks_strat(bm::BM_BIT);
4877
bvect_full2->set_new_blocks_strat(bm::BM_BIT);
4880
for(i = 0; i < 65000; ++i)
4882
bvect_full1->set_bit(i);
4883
bvect_min1->set_bit(i);
4886
for(i = 65536; i < 65536+65000; ++i)
4888
bvect_full1->set_bit(i);
4889
bvect_min1->set_bit(i);
4892
for (i = 65536*2; i < size/6; ++i)
4894
bvect_full1->set_bit(i);
4895
bvect_min1->set_bit(i);
4899
bvect_full1->optimize();
4901
bvect_full1->stat();
4904
bvect::statistics st;
4905
bvect_full1->calc_stat(&st);
4906
unsigned char* sermem = new unsigned char[st.max_serialize_mem];
4907
unsigned slen = bm::serialize(*bvect_full1, sermem);
4908
cout << "Serialized mem_max = " << st.max_serialize_mem
4909
<< " size= " << slen
4910
<< " Ratio=" << (slen*100)/st.max_serialize_mem << "%"
4913
unsigned char* new_sermem = new unsigned char[st.max_serialize_mem];
4914
::memcpy(new_sermem, sermem, slen);
4916
bvect bv_target_s(*bvect_full2);
4918
bm::deserialize(*bvect_full2, new_sermem);
4919
operation_deserializer<bvect>::deserialize(bv_target_s,
4925
delete [] new_sermem;
4927
CheckVectors(*bvect_min1, *bvect_full2, size, true);
4928
CheckVectors(*bvect_min1, bv_target_s, size, true);
4942
cout << "-------------------------------------------- GetNextTest" << endl;
4945
for(i = 0; i < 2; ++i)
4947
cout << "Strategy " << i << endl;
4951
bvect_mini bvect_min1(BITVECT_SIZE);
4953
bvect_full1.set_new_blocks_strat(i ? bm::BM_GAP : bm::BM_BIT);
4955
bvect_full1.set_bit(0);
4956
bvect_min1.set_bit(0);
4959
bvect_full1.set_bit(65536);
4960
bvect_min1.set_bit(65536);
4962
unsigned nbit1 = bvect_full1.get_first();
4963
unsigned nbit2 = bvect_min1.get_first();
4967
cout << "1. get_first failed() " << nbit1 << " " << nbit2 << endl;
4970
nbit1 = bvect_full1.get_next(nbit1);
4971
nbit2 = bvect_min1.get_next(nbit2);
4972
if ((nbit1 != nbit2) || (nbit1 != 65536))
4974
cout << "1. get_next failed() " << nbit1 << " " << nbit2 << endl;
4983
bvect_mini bvect_min1(BITVECT_SIZE);
4984
bvect_full1.set_new_blocks_strat(i ? bm::BM_GAP : bm::BM_BIT);
4986
bvect_full1.set_bit(65535);
4987
bvect_min1.set_bit(65535);
4989
unsigned nbit1 = bvect_full1.get_first();
4990
unsigned nbit2 = bvect_min1.get_first();
4992
if ((nbit1 != nbit2) || (nbit1 != 65535))
4994
cout << "1. get_first failed() " << nbit1 << " " << nbit2 << endl;
4997
nbit1 = bvect_full1.get_next(nbit1);
4998
nbit2 = bvect_min1.get_next(nbit2);
4999
if (nbit1 != nbit2 )
5001
cout << "1. get_next failed() " << nbit1 << " " << nbit2 << endl;
5007
cout << "--------------" << endl;
5009
bvect_mini bvect_min1(BITVECT_SIZE);
5010
bvect_full1.set_new_blocks_strat(i ? bm::BM_GAP : bm::BM_BIT);
5012
bvect_full1.set_bit(655350);
5013
bvect_min1.set_bit(655350);
5015
unsigned nbit1 = bvect_full1.get_first();
5016
unsigned nbit2 = bvect_min1.get_first();
5018
if (nbit1 != nbit2 || nbit1 != 655350)
5020
cout << "1. get_first failed() " << nbit1 << " " << nbit2 << endl;
5024
nbit1 = bvect_full1.get_next(nbit1);
5025
nbit2 = bvect_min1.get_next(nbit2);
5028
cout << "1. get_next failed() " << nbit1 << " " << nbit2 << endl;
5036
bvect_mini bvect_min1(BITVECT_SIZE);
5038
bvect_full1.set_new_blocks_strat(i ? bm::BM_GAP : bm::BM_BIT);
5040
bvect_full1.set_bit(256);
5041
bvect_min1.set_bit(256);
5043
// bvect_full1.clear_bit(256);
5044
bvect_full1.set_bit(65536);
5045
bvect_min1.set_bit(65536);
5047
unsigned nbit1 = bvect_full1.get_first();
5048
unsigned nbit2 = bvect_min1.get_first();
5052
cout << "get_first failed " << nbit1 << " " << nbit2 << endl;
5058
cout << nbit1 << endl;
5059
nbit1 = bvect_full1.get_next(nbit1);
5060
nbit2 = bvect_min1.get_next(nbit2);
5063
cout << "get_next failed " << nbit1 << " " << nbit2 << endl;
5076
// Test contributed by Maxim Shemanarev.
5084
for(i = 0; i < 100; i++)
5086
int n = rand() % 2000 + 1;
5088
for(j = 0; j < n; j++)
5090
id += rand() % 10 + 1;
5096
fprintf(stderr, ".");
5101
void CalcBeginMask()
5103
printf("BeginMask:\n");
5106
for (i = 0; i < 32; ++i)
5110
for(int j = i; j < 32; ++j)
5113
nbit &= bm::set_word_mask;
5114
bm::word_t mask1 = (((bm::word_t)1) << j);
5119
printf("0x%x, ", mask);
5127
printf("EndMask:\n");
5130
for (i = 0; i < 32; ++i)
5134
for(int j = i; j > 0; --j)
5137
nbit &= bm::set_word_mask;
5138
bm::word_t mask1 = (((bm::word_t)1) << j);
5143
printf("0x%x,", mask);
5150
void EnumeratorTest()
5152
cout << "-------------------------------------------- EnumeratorTest" << endl;
5157
bvect1.set_bit(100);
5159
bvect::enumerator en = bvect1.first();
5163
cout << "Enumerator error !" << endl;
5167
bvect1.clear_bit(100);
5169
bvect1.set_bit(2000000000);
5172
if (*en != 2000000000)
5174
cout << "Enumerator error !" << endl;
5184
bvect1.set_bit(1000);
5185
bvect1.set_bit(2016519);
5186
bvect1.set_bit(2034779);
5187
bvect1.set_bit(bm::id_max-1);
5189
bvect::enumerator en = bvect1.first();
5191
unsigned num = bvect1.get_first();
5193
bvect::enumerator end = bvect1.end();
5198
cout << "Enumeration comparison failed !" <<
5199
" enumerator = " << *en <<
5200
" get_next() = " << num << endl;
5204
num = bvect1.get_next(num);
5208
cout << "Enumeration error!" << endl;
5217
bvect::enumerator en = bvect1.first();
5219
unsigned num = bvect1.get_first();
5221
while (en < bvect1.end())
5225
cout << "Enumeration comparison failed !" <<
5226
" enumerator = " << *en <<
5227
" get_next() = " << num << endl;
5232
num = bvect1.get_next(num);
5236
cout << "Enumeration error!" << endl;
5246
for(i = 0; i < 65536; ++i)
5251
for(i = 65536*10; i < 65536*20; i+=3)
5257
bvect::enumerator en = bvect1.first();
5259
unsigned num = bvect1.get_first();
5261
while (en < bvect1.end())
5265
cout << "Enumeration comparison failed !" <<
5266
" enumerator = " << *en <<
5267
" get_next() = " << num << endl;
5271
num = bvect1.get_next(num);
5279
cout << "Enumeration error!" << endl;
5287
bvect1.set_new_blocks_strat(bm::BM_GAP);
5288
bvect1.set_bit(100);
5290
bvect::enumerator en = bvect1.first();
5294
cout << "Enumerator error !" << endl;
5298
bvect1.clear_bit(100);
5300
bvect1.set_bit(2000000);
5305
cout << "Enumerator error !" << endl;
5313
bvect1.set_new_blocks_strat(bm::BM_GAP);
5317
bvect1.set_bit(100);
5318
bvect1.set_bit(1000);
5320
bvect::enumerator en = bvect1.first();
5322
unsigned num = bvect1.get_first();
5324
while (en < bvect1.end())
5328
cout << "Enumeration comparison failed !" <<
5329
" enumerator = " << *en <<
5330
" get_next() = " << num << endl;
5334
num = bvect1.get_next(num);
5338
cout << "Enumeration error!" << endl;
5348
void BlockLevelTest()
5353
bv.set_new_blocks_strat(bm::BM_GAP);
5354
bv2.set_new_blocks_strat(bm::BM_GAP);
5357
for (i = 0; i < 500; i+=1)
5363
for (i = 0; i < 1000; i+=2)
5369
struct bvect::statistics st;
5372
unsigned char* sermem = new unsigned char[st.max_serialize_mem];
5374
unsigned slen = bm::serialize(bv2, sermem);
5378
bm::deserialize(bv, sermem);
5386
__int64 CalcBitCount64(__int64 b)
5388
b = (b & 0x5555555555555555) + (b >> 1 & 0x5555555555555555);
5389
b = (b & 0x3333333333333333) + (b >> 2 & 0x3333333333333333);
5390
b = b + (b >> 4) & 0x0F0F0F0F0F0F0F0F;
5393
b = b + (b >> 32) & 0x0000007F;
5397
unsigned CalcBitCount32(unsigned b)
5399
b = (b & 0x55555555) + (b >> 1 & 0x55555555);
5400
b = (b & 0x33333333) + (b >> 2 & 0x33333333);
5401
b = b + (b >> 4) & 0x0F0F0F0F;
5403
b = b + (b >> 16) & 0x0000003F;
5411
cout << "----------------------------- Syntax test." << endl;
5414
bvect::allocator_type a = bv1.get_allocator();
5438
bvect::reference ref = bv1[10];
5448
cout << "----------------------------- Syntax test ok." << endl;
5460
if (cnt != bm::id_max)
5462
cout << "Set test failed!." << endl;
5470
cout << "Set invert test failed!." << endl;
5475
bv.set(bm::id_max-1);
5484
if (cnt != bm::id_max-2)
5486
cout << "Set invert test failed!." << endl;
5495
cout << "Set &= test failed!" << endl;
5504
cout << "Set &= test failed (2)!" << endl;
5513
cout << "Set &= test failed (2)!" << endl;
5520
bvect::statistics stat1;
5521
bv2.calc_stat(&stat1);
5525
bvect::statistics stat2;
5526
bv2.calc_stat(&stat2);
5528
if (stat2.bit_blocks != 0 ||
5529
stat2.gap_blocks != 0 ||
5530
stat1.memory_used <= stat2.memory_used)
5532
cout << "Optimization memory free test failed (2)!" << endl;
5539
changed = bv3.set_bit_conditional(10, true, true);
5542
cout << "Conditional bit set failed." << endl;
5545
changed = bv3.set_bit_conditional(10, true, false);
5547
if (!v || !changed) {
5548
cout << "Conditional bit set failed." << endl;
5551
changed = bv3.set_bit_conditional(10, false, false);
5553
if (!v || changed) {
5554
cout << "Conditional bit set failed." << endl;
5557
changed = bv3.set_bit_conditional(10, false, true);
5559
if (v || !changed) {
5560
cout << "Conditional bit set failed." << endl;
5565
bvect bv3(bm::BM_GAP);
5567
changed = bv3.set_bit_conditional(10, true, true);
5570
cout << "Conditional bit set failed." << endl;
5573
changed = bv3.set_bit_conditional(10, true, false);
5575
if (!v || !changed) {
5576
cout << "Conditional bit set failed." << endl;
5579
changed = bv3.set_bit_conditional(10, false, false);
5581
if (!v || changed) {
5582
cout << "Conditional bit set failed." << endl;
5585
changed = bv3.set_bit_conditional(10, false, true);
5587
if (v || !changed) {
5588
cout << "Conditional bit set failed." << endl;
5593
bvect bv3(bm::BM_GAP);
5597
changed = bv3.set_bit_conditional(10, true, true);
5599
if (!v || changed) {
5600
cout << "Conditional bit set failed." << endl;
5603
changed = bv3.set_bit_conditional(10, true, false);
5605
if (!v || changed) {
5606
cout << "Conditional bit set failed." << endl;
5609
changed = bv3.set_bit_conditional(10, false, false);
5611
if (!v || changed) {
5612
cout << "Conditional bit set failed." << endl;
5615
changed = bv3.set_bit_conditional(10, false, true);
5617
if (v || !changed) {
5618
cout << "Conditional bit set failed." << endl;
5621
changed = bv3.set_bit_conditional(10, true, false);
5623
if (!v || !changed) {
5624
cout << "Conditional bit set failed." << endl;
5632
template<class A, class B> void CompareMiniSet(const A& ms,
5635
for (unsigned i = 0; i < bm::set_total_blocks; ++i)
5637
bool ms_val = ms.test(i)!=0;
5638
bool bvm_val = bvm.is_bit_true(i)!=0;
5639
if (ms_val != bvm_val)
5641
printf("MiniSet comparison error: %u\n",i);
5649
cout << "----------------------- MiniSetTest" << endl;
5651
bm::miniset<bm::block_allocator, bm::set_total_blocks> ms;
5652
bvect_mini bvm(bm::set_total_blocks);
5655
CompareMiniSet(ms, bvm);
5661
CompareMiniSet(ms, bvm);
5665
for (i = 1; i < 10; i++)
5670
CompareMiniSet(ms, bvm);
5672
for (i = 1; i < 10; i++)
5677
CompareMiniSet(ms, bvm);
5680
for (i = 1; i < 10; i+=3)
5685
CompareMiniSet(ms, bvm);
5687
for (i = 1; i < 5; i+=3)
5692
CompareMiniSet(ms, bvm);
5697
bm::miniset<bm::block_allocator, bm::set_total_blocks> ms;
5698
bvect_mini bvm(bm::set_total_blocks);
5704
CompareMiniSet(ms, bvm);
5707
for (i = 1; i < bm::set_total_blocks; i+=3)
5712
CompareMiniSet(ms, bvm);
5714
for (i = 1; i < bm::set_total_blocks/2; i+=3)
5719
CompareMiniSet(ms, bvm);
5724
bm::bvmini<bm::set_total_blocks> ms(0);
5725
bvect_mini bvm(bm::set_total_blocks);
5728
CompareMiniSet(ms, bvm);
5734
CompareMiniSet(ms, bvm);
5738
for (i = 1; i < 10; i++)
5743
CompareMiniSet(ms, bvm);
5745
for (i = 1; i < 10; i++)
5750
CompareMiniSet(ms, bvm);
5753
for (i = 1; i < bm::set_total_blocks; i+=3)
5758
CompareMiniSet(ms, bvm);
5760
for (i = 1; i < bm::set_total_blocks/2; i+=3)
5765
CompareMiniSet(ms, bvm);
5770
bm::miniset<bm::block_allocator, bm::set_total_blocks> ms;
5771
bvect_mini bvm(bm::set_total_blocks);
5777
CompareMiniSet(ms, bvm);
5780
for (i = 1; i < 15; i+=3)
5785
CompareMiniSet(ms, bvm);
5787
for (i = 1; i < 7; i+=3)
5792
CompareMiniSet(ms, bvm);
5796
cout << "----------------------- MiniSetTest ok" << endl;
5800
unsigned CalcBitCount32(unsigned b)
5802
b = (b & 0x55555555) + (b >> 1 & 0x55555555);
5803
b = (b & 0x33333333) + (b >> 2 & 0x33333333);
5804
b = b + (b >> 4) & 0x0F0F0F0F;
5806
b = b + (b >> 16) & 0x0000003F;
5811
void PrintGapLevels(const gap_word_t* glevel)
5813
cout << "Gap levels:" << endl;
5815
for (i = 0; i < bm::gap_levels; ++i)
5817
cout << glevel[i] << ",";
5824
gap_word_t glevel[bm::gap_levels];
5825
::memcpy(glevel, gap_len_table<true>::_len, bm::gap_levels * sizeof(gap_word_t));
5828
gap_word_t length[] = { 2, 2, 5, 5, 10, 11, 12 };
5829
unsigned lsize = sizeof(length) / sizeof(gap_word_t);
5831
bm::improve_gap_levels(length, length + lsize, glevel);
5833
PrintGapLevels(glevel);
5837
gap_word_t length[] = { 3, 5, 15, 15, 100, 110, 120 };
5838
unsigned lsize = sizeof(length) / sizeof(gap_word_t);
5840
bm::improve_gap_levels(length, length + lsize, glevel);
5841
PrintGapLevels(glevel);
5845
gap_word_t length[] = { 15, 80, 5, 3, 100, 110, 95 };
5846
unsigned lsize = sizeof(length) / sizeof(gap_word_t);
5848
bm::improve_gap_levels(length, length + lsize, glevel);
5849
PrintGapLevels(glevel);
5853
gap_word_t length[] =
5854
{ 16,30,14,24,14,30,18,14,12,16,8,38,28,4,20,18,28,22,32,14,12,16,10,8,14,18,14,8,
5855
16,30,8,8,58,28,18,4,26,14,52,12,18,10,14,18,22,18,20,70,12,6,26,6,8,22,12,4,8,8,
5856
8,54,18,6,8,4,4,10,4,4,4,4,4,6,22,14,38,40,56,50,6,10,8,18,82,16,6,18,20,12,12,
5857
16,8,14,14,10,16,12,10,16,14,12,18,14,18,34,14,12,18,18,10,20,10,18,8,14,14,22,16,
5858
10,10,18,8,20,14,10,14,12,12,14,16,16,6,10,14,6,10,10,10,10,12,4,8,8,8,10,10,8,
5859
8,12,10,10,14,14,14,8,4,4,10,10,4,10,4,8,6,52,104,584,218
5861
unsigned lsize = sizeof(length) / sizeof(gap_word_t);
5863
bm::improve_gap_levels(length, length + lsize, glevel);
5864
PrintGapLevels(glevel);
5868
gap_word_t length[] = {
5869
30,46,26,4,4,68,72,6,10,4,6,14,6,42,198,22,12,4,6,24,12,8,18,4,6,10,6,4,6,6,12,6
5870
,6,4,4,78,38,8,52,4,8,10,6,8,8,6,10,4,6,6,4,10,6,8,16,22,28,14,10,10,16,10,20,10
5871
,14,12,8,18,4,8,10,6,10,4,6,12,16,12,6,4,8,4,14,14,6,8,4,10,10,8,8,6,8,6,8,4,8,4
5874
unsigned lsize = sizeof(length) / sizeof(gap_word_t);
5876
bm::improve_gap_levels(length, length + lsize, glevel);
5877
PrintGapLevels(glevel);
5883
void BitCountChangeTest()
5885
cout << "---------------------------- BitCountChangeTest " << endl;
5888
for(i = 0xFFFFFFFF; i; i <<= 1)
5890
unsigned a0 = bm::bit_count_change(i);
5891
unsigned a1 = BitCountChange(i);
5896
<< "Bit count change test failed!"
5897
<< " i = " << i << " return = "
5898
<< a0 << " check = " << a1
5904
cout << "---------------------------- STEP 2 " << endl;
5906
for(i = 0xFFFFFFFF; i; i >>= 1)
5908
unsigned a0 = bm::bit_count_change(i);
5909
unsigned a1 = BitCountChange(i);
5913
cout << "Bit count change test failed!"
5914
<< " i = " << i << " return = "
5915
<< a0 << " check = " << a1
5921
cout << "---------------------------- STEP 3 " << endl;
5923
for (i = 0; i < 0xFFFFFFF; ++i)
5925
unsigned a0 = bm::bit_count_change(i);
5926
unsigned a1 = BitCountChange(i);
5930
cout << "Bit count change test failed!"
5931
<< " i = " << i << " return = "
5932
<< a0 << " check = " << a1
5939
bm::word_t arr[16] = {0,};
5940
arr[0] = (bm::word_t)(1 << 31);
5941
arr[1] = 1; //(bm::word_t)(1 << 31);
5945
cnt = bm::bit_count_change(arr[1]);
5946
cout << cnt << endl;
5949
cout << "0.count_change() failed " << cnt << endl;
5953
cnt = bm::bit_block_calc_count_change(arr, arr+4);
5957
cout << "1.count_intervals() failed " << cnt << endl;
5961
arr[0] = arr[1] = arr[2] = 0xFFFFFFFF;
5962
arr[3] = (bm::word_t)(0xFFFFFFFF >> 1);
5964
cnt = bm::bit_block_calc_count_change(arr, arr+4);
5965
cout << cnt << endl;
5969
cout << "1.1 count_intervals() failed " << cnt << endl;
5974
cout << "---------------------------- STEP 4 " << endl;
5977
cnt = bm::count_intervals(bv1);
5981
cout << "1.count_intervals() failed " << cnt << endl;
5984
CheckIntervals(bv1, 65536);
5988
cnt = count_intervals(bv1);
5989
cout << "Inverted cnt=" << cnt << endl;
5993
cout << "2.inverted count_intervals() failed " << cnt << endl;
5999
for (i = 10; i < 100000; ++i)
6004
cnt = count_intervals(bv1);
6008
cout << "3.count_intervals() failed " << cnt << endl;
6011
cout << "-----" << endl;
6012
CheckIntervals(bv1, 65536*2);
6013
cout << "Optmization..." << endl;
6015
cnt = count_intervals(bv1);
6019
cout << "4.count_intervals() failed " << cnt << endl;
6023
CheckIntervals(bv1, 65536*2);
6025
cout << "---------------------------- BitCountChangeTest Ok." << endl;
6029
#define POWER_CHECK(w, mask) \
6030
(bm::bit_count_table<true>::_count[(w&mask) ^ ((w&mask)-1)])
6034
unsigned bits[64] = {0,};
6041
int bn3 = POWER_CHECK(w, 1 << 3) - 1;
6042
int bn2 = POWER_CHECK(w, 1 << 2) - 1;
6043
int bn0 = POWER_CHECK(w, 1 << 0) - 1;
6045
bit_list(w, bits+1);
6054
assert(bv.any() == false);
6055
assert(bv.count() == 0);
6061
assert(bv1.size() == bv2.size());
6066
assert(bv.any() == false);
6067
assert(bv.count() == 0);
6069
unsigned cnt = bv.count();
6078
assert(bv1.size() == 10);
6079
assert(bv2.size() == 0);
6080
assert(bv1.count() == 1);
6081
assert(bv2.count() == 0);
6085
assert(bv2.size() == 10);
6086
assert(bv2.count() == 1);
6087
assert(bv1.size() == 0);
6088
assert(bv1.count() == 0);
6096
assert(bv1.size() == bm::id_max);
6097
assert(bv1.count() == 2);
6099
assert(bv1.size() == 101);
6100
assert(bv1.count() == 1);
6102
bm::id_t f = bv1.get_first();
6104
f = bv1.get_next(f);
6109
assert(bv1.size() == 10);
6110
assert(bv1.count() == 0);
6111
bm::id_t f = bv1.get_first();
6121
bv.set_range(0, 65536*10, false);
6125
// test logical operations
6128
bvect bv1(65536 * 10);
6129
bvect bv2(65536 * 100);
6134
assert(bv2.size() == 65536 * 100);
6135
assert(bv2.count() == 1);
6136
assert(bv2.get_first() == 5);
6146
assert(bv1.size() == bv2.size());
6147
assert(bv1.count() == 1);
6148
assert(bv1.get_first() == 5);
6158
assert(bv1.size() == bv2.size());
6159
assert(bv1.count() == 3);
6170
cmp = bv1.compare(bv2);
6175
cmp = bv1.compare(bv2);
6177
cmp = bv2.compare(bv1);
6187
bvect::insert_iterator it(bv1);
6190
assert(bv1.size() == 100 * 65536 + 1);
6198
struct bvect::statistics st1;
6199
bv1.calc_stat(&st1);
6201
unsigned char* sermem = new unsigned char[st1.max_serialize_mem];
6202
unsigned slen2 = bm::serialize(bv1, sermem);
6205
bm::deserialize(bv2, sermem);
6208
assert(bv2.size() == 10);
6209
assert(bv2.count() == 1);
6210
assert(bv2.get_first() == 5);
6217
unsigned int arg[] = { 10, 65536, 65537, 65538 * 10000 };
6218
unsigned* it1 = arg;
6219
unsigned* it2 = arg + 4;
6220
combine_or(bv1, it1, it2);
6221
assert(bv1.size() == 65538 * 10000 + 1);
6222
bvect::enumerator en = bv1.first();
6234
cout << "---------------------------- ExportTest..." << endl;
6237
char buf[20] = {0,};
6241
buf[2]= (char)(1 << 1);
6244
export_array(bv1, buf + 0, buf + 20);
6246
assert(bv1.count() == 3);
6247
assert(bv1.test(0));
6248
assert(bv1.test(8));
6249
assert(bv1.test(17));
6253
char buf[65536*10] = {0,};
6257
buf[2]= (char)(1 << 1);
6260
export_array(bv1, buf + 0, buf + 65536*10);
6262
assert(bv1.count() == 3);
6263
assert(bv1.test(0));
6264
assert(bv1.test(8));
6265
assert(bv1.test(17));
6269
short buf[20] = {0,};
6273
buf[2]= (char)(1 << 1);
6276
export_array(bv1, buf + 0, buf + 20);
6278
assert(bv1.count() == 3);
6279
assert(bv1.test(0));
6280
assert(bv1.test(16));
6281
assert(bv1.test(33));
6289
buf[2]= (char)(1 << 1);
6292
export_array(bv1, buf + 0, buf + 20);
6294
assert(bv1.count() == 3);
6295
assert(bv1.test(0));
6296
assert(bv1.test(32));
6297
assert(bv1.test(65));
6301
cout << "---------------------------- ExportTest Ok." << endl;
6307
bm::word_t b1[bm::set_block_size]= {0,};
6308
bm::word_t b2[bm::set_block_size]= {0,};
6309
bm::word_t br[bm::set_block_size]= {0,};
6315
bitblock_get_adapter bga1(b1);
6316
bitblock_get_adapter bga2(b2);
6317
bitblock_store_adapter bbsa(br);
6318
bm::bit_AND<bm::word_t> and_func;
6319
bit_recomb<bitblock_get_adapter,
6320
bitblock_get_adapter,
6321
bm::bit_AND<bm::word_t>,
6322
bitblock_store_adapter>
6323
(bga1, bga2,and_func, bbsa);
6325
bit_recomb(bitblock_get_adapter(b1),
6326
bitblock_get_adapter(b2),
6327
bit_AND<bm::word_t>(),
6328
bitblock_store_adapter(br)
6332
for (int i = 1; i < bm::set_block_size; ++i)
6337
bitblock_sum_adapter sa;
6338
bit_recomb(bitblock_get_adapter(b1),
6339
bitblock_get_adapter(b2),
6340
bit_COUNT_AND<bm::word_t>(),
6343
assert(sa.sum() == 1);
6350
time_t start_time = time(0);
6360
unsigned a = bm::id_max / 65536;
6362
bvect bv(BM_BIT, bm::gap_len_table<true>::_len, 65536*10);
6363
bm::id_t c = bv.capacity();
6364
bv.set(bm::id_max-1);
6367
// cout << sizeof(__int64) << endl;
6369
// ::srand((unsigned)::time(NULL));
6387
cout << bv.count() << endl;
6389
bvect::statistics st;
6391
unsigned char buf[2048];
6392
unsigned slen = bm::serialize(bv, buf);
6393
cout << "slen=" << slen << endl;
6396
operation_deserializer<bvect>::deserialize(bv2,
6401
cout << "count2=" << bv2.count() << endl;
6402
PrintSet(cout, bv2);
6414
BitCountChangeTest();
6418
BasicFunctionalityTest();
6428
SimpleRandomFillTest();
6430
RangeRandomFillTest();
6432
AndOperationsTest();
6436
XorOperationsTest();
6438
SubOperationsTest();
6446
MutationOperationsTest();
6448
SerializationTest();
6450
DesrializationTest2();
6456
finish_time = time(0);
6459
cout << "Test execution time = " << finish_time - start_time << endl;
6462
cout << "Number of BLOCK allocations = " << dbg_block_allocator::na_ << endl;
6463
cout << "Number of PTR allocations = " << dbg_ptr_allocator::na_ << endl << endl;
6465
assert(dbg_block_allocator::balance() == 0);
6466
assert(dbg_ptr_allocator::balance() == 0);