NCBI C++ ToolKit
stress64.cpp
Go to the documentation of this file.

Go to the SVN repository for this file.

1 /*
2 Copyright(c) 2019 Anatoliy Kuznetsov(anatoliy_kuznetsov at yahoo.com)
3 
4 Licensed under the Apache License, Version 2.0 (the "License");
5 you may not use this file except in compliance with the License.
6 You may obtain a copy of the License at
7 
8  http://www.apache.org/licenses/LICENSE-2.0
9 
10 Unless required by applicable law or agreed to in writing, software
11 distributed under the License is distributed on an "AS IS" BASIS,
12 WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 See the License for the specific language governing permissions and
14 limitations under the License.
15 
16 For more information please visit: http://bitmagic.io
17 */
18 
19 #include <ncbi_pch.hpp>
20 
21 //#define BMSSE2OPT
22 //#define BMSSE42OPT
23 //#define BMAVX2OPT
24 
25 #define BMXORCOMP
26 
27 #include <stdio.h>
28 #include <stdlib.h>
29 #undef NDEBUG
30 #include <time.h>
31 #include <math.h>
32 #include <string.h>
33 
34 #include <iostream>
35 #include <iomanip>
36 #include <utility>
37 #include <memory>
38 #include <random>
39 #include <algorithm>
40 #include <iterator>
41 #include <stdarg.h>
42 #include <vector>
43 #include <chrono>
44 #include <functional>
45 
47 #include <util/bitset/bmrandom.h>
49 #include <util/bitset/bmvmin.h>
50 #include <util/bitset/bmdbg.h>
51 #include <util/bitset/bmalgo.h>
53 #include <util/bitset/bmbvimport.h>
55 #include <util/bitset/bmtimer.h>
56 
62 
63 #include <common/test_assert.h>
64 
65 
66 using namespace bm;
67 using namespace std;
68 
69 
70 #include "gena.h"
71 #include "test_util.h"
72 
73 
74 #define POOL_SIZE 5000
75 
76 //#define MEM_POOL
77 
78 bool is_silent = false;
79 
80 template<class T> T* pool_allocate(T** pool, int& i, size_t n)
81 {
82  return i ? pool[i--] : (T*) ::malloc(n * sizeof(T));
83 }
84 
85 inline void* pool_allocate2(void** pool, int& i, size_t n)
86 {
87  return i ? pool[i--] : malloc(n * sizeof(void*));
88 }
89 
90 
91 
92 template<class T> void pool_free(T** pool, int& i, T* p)
93 {
94  i < POOL_SIZE ? (free(p),(void*)0) : pool[++i]=p;
95 }
96 
97 
99 {
100 public:
101 
102  static bm::word_t* allocate(size_t n, const void *)
103  {
104  int *idx = 0;
105  bm::word_t** pool = 0;
106 
107  switch (n)
108  {
109  case bm::set_block_size:
110  idx = &bit_blocks_idx_;
111  pool = free_bit_blocks_;
112  break;
113 
114  case 64:
115  idx = &gap_blocks_idx0_;
116  pool = gap_bit_blocks0_;
117  break;
118 
119  case 128:
120  idx = &gap_blocks_idx1_;
121  pool = gap_bit_blocks1_;
122  break;
123 
124  case 256:
125  idx = &gap_blocks_idx2_;
126  pool = gap_bit_blocks2_;
127  break;
128 
129  case 512:
130  idx = &gap_blocks_idx3_;
131  pool = gap_bit_blocks3_;
132  break;
133 
134  default:
135  assert(0);
136  }
137 
138  return pool_allocate(pool, *idx, n);
139  }
140 
141  static void deallocate(bm::word_t* p, size_t n)
142  {
143  int *idx = 0;
144  bm::word_t** pool = 0;
145 
146  switch (n)
147  {
148  case bm::set_block_size:
149  idx = &bit_blocks_idx_;
150  pool = free_bit_blocks_;
151  break;
152 
153  case 64:
154  idx = &gap_blocks_idx0_;
155  pool = gap_bit_blocks0_;
156  break;
157 
158  case 128:
159  idx = &gap_blocks_idx1_;
160  pool = gap_bit_blocks1_;
161  break;
162 
163  case 256:
164  idx = &gap_blocks_idx2_;
165  pool = gap_bit_blocks2_;
166  break;
167 
168  case 512:
169  idx = &gap_blocks_idx3_;
170  pool = gap_bit_blocks3_;
171  break;
172 
173  default:
174  assert(0);
175  }
176 
177  pool_free(pool, *idx, p);
178  }
179 
180 private:
181  static bm::word_t* free_bit_blocks_[];
182  static int bit_blocks_idx_;
183 
184  static bm::word_t* gap_bit_blocks0_[];
185  static int gap_blocks_idx0_;
186 
187  static bm::word_t* gap_bit_blocks1_[];
188  static int gap_blocks_idx1_;
189 
190  static bm::word_t* gap_bit_blocks2_[];
191  static int gap_blocks_idx2_;
192 
193  static bm::word_t* gap_bit_blocks3_[];
194  static int gap_blocks_idx3_;
195 };
196 
199 
202 
205 
208 
211 
212 
213 
214 
216 {
217 public:
218 
219  static void* allocate(size_t n, const void *)
220  {
221  return pool_allocate2(free_ptr_blocks_, ptr_blocks_idx_, n);
222  }
223 
224  static void deallocate(void* p, size_t)
225  {
226  pool_free(free_ptr_blocks_, ptr_blocks_idx_, p);
227  }
228 
229 private:
230  static void* free_ptr_blocks_[];
231  static int ptr_blocks_idx_;
232 };
233 
236 
237 #if defined(BMSSE2OPT) || defined(BMSSE42OPT) || defined(BMAVX2OPT) || defined(BMAVX512OPT) || defined(__ARM_NEON__)
238 #else
239 # define MEM_DEBUG
240 #endif
241 
242 #ifdef MEM_DEBUG
243 
244 
246 {
247 public:
248 static size_t na_;
249 static size_t nf_;
250 
251  static bm::word_t* allocate(size_t n, const void *)
252  {
253  ++na_;
254  assert(n);
255  bm::word_t* p =
256  (bm::word_t*) ::malloc((n+2) * sizeof(bm::word_t));
257  if (!p)
258  {
259  std::cerr << "ERROR Failed allocation!" << endl;
260  assert(0); exit(1);
261  }
262  size_t* ptr = (size_t*)p;
263  *ptr = n;
264  p+=2;
265  return p;
266  }
267 
268  static void deallocate(bm::word_t* p, size_t n)
269  {
270  ++nf_;
271  p-=2;
272  size_t* ptr = (size_t*)p;
273  if (*ptr != n)
274  {
275  cerr << "Block memory deallocation ERROR! n = " << n << ", block-control = " << *ptr << endl;
276  assert(0); exit(1);
277  }
278  ::free(p);
279  }
280 
281  static size_t balance()
282  {
283  return nf_ - na_;
284  }
285 };
286 
287 size_t dbg_block_allocator::na_ = 0;
288 size_t dbg_block_allocator::nf_ = 0;
289 
290 class dbg_ptr_allocator
291 {
292 public:
293 static size_t na_;
294 static size_t nf_;
295 
296  static void* allocate(size_t n, const void *)
297  {
298  ++na_;
299  assert(sizeof(size_t) == sizeof(void*));
300  void* p = ::malloc((n+1) * sizeof(void*));
301  if (!p)
302  {
303  std::cerr << "ERROR! Failed allocation!" << endl;
304  exit(1);
305  }
306  size_t* s = (size_t*) p;
307  *s = n;
308  return (void*)++s;
309  }
310 
311  static void deallocate(void* p, size_t n)
312  {
313  ++nf_;
314  size_t* s = (size_t*) p;
315  --s;
316  if(*s != n)
317  {
318  printf("Ptr memory deallocation ERROR!\n");
319  assert(0);
320  exit(1);
321  }
322  ::free(s);
323  }
324 
325  static size_t balance()
326  {
327  return nf_ - na_;
328  }
329 
330 };
331 
332 size_t dbg_ptr_allocator::na_ = 0;
333 size_t dbg_ptr_allocator::nf_ = 0;
334 
335 
337 
342 
343 #else
344 
345 #ifdef MEM_POOL
346 
352 
353 
354 #else
355 
356 typedef bm::bvector<> bvect64;
357 typedef bm::bvector<> bvect;
359 typedef bm::rs_index<> rs_ind;
360 
361 #endif
362 
363 #endif
364 
365 typedef std::vector<bm::id64_t> ref_vect;
366 
373 
374 
375 static
377 {
378  cout << "------------------------------------ SyntaxTest()" << endl;
379  ref_vect vect;
380  generate_vect_simpl0(vect);
381  {
382  bvect64 bv0;
383 
384  load_BV_set_ref(cout, bv0, vect);
385  compare_BV_set_ref(bv0, vect);
386 
387 
388  auto idx = vect.size()-1;
389  auto v = vect[idx];
390  assert(bv0.test(v));
391 
392  bvect64 bv1(bv0);
393  cout << bv0.count() << endl;
394  cout << bv1.count() << endl;
395  compare_BV_set_ref(bv1, vect);
396 
397  bvect64 bv2;
398  bv2 = bv0;
399  compare_BV_set_ref(bv1, vect);
400 
401  bvect64 bv3(std::move(bv2));
402  assert(bv2.none());
403  compare_BV_set_ref(bv3, vect);
404 
405  bvect64 bv4;
406  bv4.move_from(bv3);
407  assert(bv3.none());
408  compare_BV_set_ref(bv4, vect);
409 
410  bv0 &= bv4;
411  compare_BV_set_ref(bv0, vect);
412  bv0 |= bv4;
413  compare_BV_set_ref(bv0, vect);
414  bv0 -= bv4;
415  assert(bv0.none());
416  bv1 ^= bv4;
417  assert(bv1.none());
418  }
419 
420  {
421  bvect64 bv0, bv1, bv2;
422 
423  load_BV_set_ref(cout, bv0, vect);
424  bv1 = bv2 = bv0;
425  bool b = (bv1 == bv0);
426  assert(b);
427  b = (bv1 == bv2);
428  assert(b);
429 
430  {
431  bvect64 bv3;
432  bv3 = bv1 | bv2;
433  b = (bv1 == bv3);
434  assert(b);
435  compare_BV_set_ref(bv3, vect);
436  }
437  {
438  bvect64 bv3;
439  bv3 = bv1 & bv2;
440  b = (bv1 == bv3);
441  assert(b);
442  compare_BV_set_ref(bv3, vect);
443  }
444  {
445  bvect64 bv3;
446  bv3 = bv1 - bv2;
447  assert(bv3.none());
448  }
449  {
450  bvect64 bv3;
451  bv3 = bv1 ^ bv2;
452  assert(bv3.count() == 0ULL);
453  }
454  }
455 
456  {
457  bvect64 bv1;
458  bvect64::reference ref = bv1[10];
459  bool bn = !ref;
460  assert(bn);
461  bool bn2 = ~ref;
462  assert(bn2);
463  bv1[10] = bn2;
464  bv1[10] = bn;
465  bn = bn2 = false;
466  assert(!bn);
467  ref.flip();
468  assert(!bv1.test(10));
469  bv1[bm::id_max-1] = 1;
470  assert(bv1[bm::id_max-1]);
471  auto ref1 = bv1[bm::id_max-1];
472  ref1.flip();
473  assert(!ref1);
474  assert(!bv1.test(bm::id_max-1));
475  }
476  {
477  bvect64 bv1;
478  auto ii = bv1.inserter();
479  ii = bm::id_max / 2;
480  assert(bv1.test(bm::id_max / 2));
481  }
482 
483  cout << "------------------------------------ SyntaxTest() OK" << endl;
484 }
485 
486 static
488 {
489  cout << "------------------------------------ GenericBVectorTest()" << endl;
490 
491  {
492  bvect64 bv0;
493  ref_vect vect;
494  generate_vect_simpl0(vect);
495 
496  load_BV_set_ref(cout, bv0, vect);
497  compare_BV_set_ref(bv0, vect);
498 
499  bvect64 bv1(bm::BM_GAP);
500  load_BV_set_ref(cout, bv1, vect);
501  compare_BV_set_ref(bv1, vect);
502 
503  int cmp = bv0.compare(bv1);
504  assert(cmp == 0);
505 
506  bvect64::statistics st1, st2, st3;
507  bv0.calc_stat(&st1);
508  cout << "st1.max_serialize_mem = " << st1.max_serialize_mem << endl;
509  assert(st1.max_serialize_mem < 2*(sizeof(bm::word_t)*st1.bit_blocks * 2048));
510  assert(st1.ptr_sub_blocks == 6);
511  bv0.optimize(0, bvect64::opt_compress, &st2);
514  bv1.calc_stat(&st3);
516  assert(st2.gap_blocks == st3.gap_blocks);
518  }
519 
520  cout << "------------------------------------ GenericBVectorTest() OK" << endl;
521 }
522 
523 static
524 void ArenaTest()
525 {
526  cout << "----------------------------- ArenaTest() " << endl;
527 
528  {
530  bvect bv;
531 
533  assert(st.gap_blocks_sz == 0);
534  assert(st.ptr_sub_blocks_sz == 0);
535  assert(st.bit_blocks_sz == 0);
536 
537  bv.set(0);
538 
540  assert(st.gap_blocks_sz == 0);
543 
544  bv.set(bm::id_max/2);
545 
547  assert(st.gap_blocks_sz == 0);
550  }
551 
552  {
554  bvect bv(bm::BM_GAP);
555 
556  bv.set(1);
557  bv.set(2);
558 
560  assert(st.gap_blocks_sz == 4);
562  assert(st.bit_blocks_sz == 0);
563 
564  bv.set(1+bm::id_max/2);
565 
567  assert(st.gap_blocks_sz == 7);
569  assert(st.bit_blocks_sz == 0);
570  }
571 
572  {
574  bvect bv;
575 
576  bv.set(0);
577  bv.set(1);
578  bv.optimize();
579 
580  bv.set(bm::id_max/2);
581 
583  assert(st.gap_blocks_sz == 3);
586 
587 
589  bvect::blocks_manager_type::arena ar;
590 
591  bman.alloc_arena(&ar, st, bman.get_allocator());
592  bman.free_arena(&ar, bman.get_allocator());
593 
594  }
595 
596 
597  cout << "----------------------------- ArenaTest() OK" << endl;
598 }
599 
600 
601 static
603 {
604  cout << "----------------------------- FreezeTest()" << endl;
605 
606  bool eq;
607  {
608  bvect bv;
610  assert(!bv.is_ro());
611  assert(!bv_ro.is_ro());
612  }
613 
614  // swap test
615  {
616  bvect bv {0};
618 
619  assert(!bv.is_ro());
620  assert(bv_ro.is_ro());
621 
622  eq = bv.equal(bv_ro);
623  assert(eq);
624 
625  bv.swap(bv_ro);
626 
627  assert(bv.is_ro());
628  assert(!bv_ro.is_ro());
629 
630  eq = bv.equal(bv_ro);
631  assert(eq);
632  }
633 
634  {
635  bvect bv;
636  bv.invert();
637 
638  {
640 
641  assert(!bv.is_ro());
642  assert(bv_ro.is_ro());
643 
644  eq = bv.equal(bv_ro);
645  assert(eq);
646  }
647  bv.optimize();
648  {
650 
651  assert(!bv.is_ro());
652  assert(bv_ro.is_ro());
653 
654  eq = bv.equal(bv_ro);
655  assert(eq);
656  }
657  }
658 
659  {
660  bvect bv;
661  bv.set_range(256*65536, bm::id_max/2 + 10);
662 
663  {
665 
666  assert(!bv.is_ro());
667  assert(bv_ro.is_ro());
668 
669  eq = bv.equal(bv_ro);
670  assert(eq); // copy-ctor
671  {
672  bvect bv_ro2(bv_ro, bm::finalization::READONLY);
673  assert(bv_ro2.is_ro());
674  eq = bv.equal(bv_ro2);
675  assert(eq);
676  }
677 
678  { // assignment
679  bvect bv_ro2 { 126 };
680  bv_ro2 = bv_ro;
681  assert(bv_ro2.is_ro());
682  eq = bv.equal(bv_ro2);
683  assert(eq);
684  }
685 
686  { // move ctor/assignment
687  bvect bv_ro2 = std::move(bv_ro);
688  assert(bv_ro2.is_ro());
689  eq = bv.equal(bv_ro2);
690  assert(eq);
691  bvect bv_ro3;
692  bv_ro3 = std::move(bv_ro2);
693  assert(bv_ro3.is_ro());
694  eq = bv.equal(bv_ro3);
695  assert(eq);
696 
697  }
698  }
699  }
700 
701 
702 
703  {
704  std::vector<bvect::size_type> v1 { 0, 65536, 65536 * 256, bm::id_max/2, bm::id_max-1 };
705  for (size_t i = 0; i < v1.size(); ++i)
706  {
707  auto idx = v1[i];
708  bvect bv; bv.set(idx);
709  {
710  for (int pass = 0; pass < 2; ++pass)
711  {
713  assert(!bv.is_ro());
714  assert(bv_ro.is_ro());
715  eq = bv.equal(bv_ro);
716  assert(eq);
718  bool found = bv_ro.find(pos);
719  assert(found);
720  assert(pos == idx);
721 
722  { // freezing copyctor
723  bvect bv_ro2(bv_ro, bm::finalization::READONLY);
724  assert(bv_ro2.is_ro());
725  eq = bv.equal(bv_ro2);
726  assert(eq);
727  }
728 
729  { // copyctor
730  bvect bv_ro2(bv_ro);
731  assert(bv_ro2.is_ro());
732  eq = bv.equal(bv_ro2);
733  assert(eq);
734  }
735  { // assignment tests
736  bvect bv_ro2 { 126 };
737  bv_ro2 = bv_ro;
738  assert(bv_ro2.is_ro());
739  eq = bv.equal(bv_ro2);
740  assert(eq);
741  }
742 
743  { // move ctor/assignment
744  bvect bv_ro2 = std::move(bv_ro);
745  assert(bv_ro2.is_ro());
746  eq = bv.equal(bv_ro2);
747  assert(eq);
748  bvect bv_ro3;
749  bv_ro3 = std::move(bv_ro2);
750  assert(bv_ro3.is_ro());
751  eq = bv.equal(bv_ro3);
752  assert(eq);
753  }
754 
755  bv.optimize();
756  } // for pass
757  }
758  } // for i
759  }
760 
761  {
762  bvect bv { 0 };
763  {
764  for (bvect::size_type i = 0; i < 65535; i+=3)
765  bv.set(i);
766  bv.set(bm::id_max/2);
767  bv.optimize();
768 
770  assert(!bv.is_ro());
771  assert(bv_ro.is_ro());
772  eq = bv.equal(bv_ro);
773  assert(eq);
774 
775  bvect bv_ro2(bv_ro);
776  assert(bv_ro2.is_ro());
777  eq = bv_ro.equal(bv_ro2);
778  assert(eq);
779  eq = bv.equal(bv_ro2);
780  assert(eq);
781  }
782  }
783 
784  cout << "----------------------------- FreezeTest() ON\n" << endl;
785 }
786 
787 
788 static
789 void SetTest()
790 {
791  cout << "------------------------------------ SetTest()" << endl;
792  {
793  bvect bv;
794  bv.set();
795  auto cnt = bv.count();
796  assert (cnt == bm::id_max);
797  }
798 
799  {
800  bvect bv;
801  bv.set();
802  bv.set_range(10, bm::id_max, false);
803  auto cnt = bv.count();
804  assert(cnt == 10);
805  }
806  {
807  bvect bv;
808  bv.set_range(bm::id_max-65535, bm::id_max, true);
809  auto cnt = bv.count();
810  assert(cnt == 65536);
811  }
812 
813  {
814  bvect bv{ 0, 10, 65536, 10000, bm::id_max-1 };
815  auto cnt = bv.count();
816  assert (cnt == 5);
817 
818  bvect bv2;
819  bv2.set(0).set(10).set(65536).set(10000).set(bm::id_max-1);
820 
821  if (bv != bv2)
822  {
823  cout << "Brace initialization comparison test failed!." << endl;
824  assert(0);exit(1);
825  }
826  }
827  {
828  bvect bv;
829  bv.set();
830 
831  auto cnt = bv.count();
832  assert (cnt == bm::id_max);
833 
834  bv.invert();
835  cnt = bv.count();
836  assert (cnt == 0);
837 
838  bv.set(0);
839  bv.set(bm::id_max - 1);
840  cnt = bv.count();
841  assert(cnt == 2);
842 
843  bv.invert();
844  //print_stat(bv);
845  cnt = bv.count();
846  assert (cnt == bm::id_max - 2);
847 
848  bv.clear();
849  bv[1] &= true;
850  bool v = bv[1];
851  assert (!v);
852 
853  bv[1] = true;
854  bv[1] &= true;
855  v = bv[1];
856  assert(v);
857 
858  bv.clear(true);
859  bv.invert();
860  bv[1] &= true;
861  v = bv[1];
862  assert (v);
863  }
864  {
865  bvect bv_full;
866  bv_full.invert();
867  assert(bv_full.test(bm::id_max/2));
868  }
869  {
870  bvect bv1, bv2(BM_GAP);
872  bv1.set(0); bv2.set(0);
873  bv1.set(bm::id_max-1);bv2.set(bm::id_max-1);
874  bv1.set((bm::id_max-1)/2);bv2.set((bm::id_max-1)/2);
875  for (unsigned i = 0; i < 2; ++i)
876  {
877  bv1.set();
878  bv2.set();
879  cnt = bv1.count();
880  assert (cnt == bm::id_max);
881  cnt = bv2.count();
882  assert (cnt == bm::id_max);
883  }
884  }
885 
886  {
887  bvect bv2;
888  bv2[bm::id_max-1] = true;
889  bv2[bm::id_max-1] = false;
890  bvect::statistics stat1;
891  bv2.calc_stat(&stat1);
892 
893  bv2.optimize();
894 
895  bvect::statistics stat2;
896  bv2.calc_stat(&stat2);
897 
898  if (stat2.bit_blocks != 0 ||
899  stat2.gap_blocks != 0 ||
900  stat1.memory_used <= stat2.memory_used)
901  {
902  cout << "Optimization memory free test failed (2)!" << endl;
903  assert(0);exit(1);
904  }
905  }
906 
907  {
908  bvect bv3;
909  bool changed;
910  changed = bv3.set_bit_conditional(bm::id_max-10, true, true);
911  bool v = bv3[10];
912  if (v || changed) {
913  cout << "Conditional bit set failed." << endl;
914  assert(0);exit(1);
915  }
916  changed = bv3.set_bit_conditional(bm::id_max-10, true, false);
917  v = bv3[bm::id_max-10];
918  if (!v || !changed) {
919  cout << "Conditional bit set failed." << endl;
920  assert(0);exit(1);
921  }
922  changed = bv3.set_bit_conditional(bm::id_max-10, false, false);
923  v = bv3[bm::id_max-10];
924  if (!v || changed) {
925  cout << "Conditional bit set failed." << endl;
926  assert(0);exit(1);
927  }
928  changed = bv3.set_bit_conditional(bm::id_max-10, false, true);
929  v = bv3[bm::id_max-10];
930  if (v || !changed) {
931  cout << "Conditional bit set failed." << endl;
932  assert(0);exit(1);
933  }
934  }
935  {
936  bvect bv3(bm::BM_GAP);
937  bool changed;
938  changed = bv3.set_bit_conditional(10, true, true);
939  bool v = bv3[10];
940  if (v || changed) {
941  cout << "Conditional bit set failed." << endl;
942  exit(1);
943  }
944  changed = bv3.set_bit_conditional(10, true, false);
945  v = bv3[10];
946  if (!v || !changed) {
947  cout << "Conditional bit set failed." << endl;
948  exit(1);
949  }
950  changed = bv3.set_bit_conditional(10, false, false);
951  v = bv3[10];
952  if (!v || changed) {
953  cout << "Conditional bit set failed." << endl;
954  exit(1);
955  }
956  changed = bv3.set_bit_conditional(10, false, true);
957  v = bv3[10];
958  if (v || !changed) {
959  cout << "Conditional bit set failed." << endl;
960  exit(1);
961  }
962  }
963 
964  {
965  bvect bv3(bm::BM_GAP);
966  bv3.invert();
967  bv3.optimize();
968  bool changed;
969  changed = bv3.set_bit_conditional(10, true, true);
970  bool v = bv3[10];
971  if (!v || changed) {
972  cout << "Conditional bit set failed." << endl;
973  exit(1);
974  }
975  changed = bv3.set_bit_conditional(10, true, false);
976  v = bv3[10];
977  if (!v || changed) {
978  cout << "Conditional bit set failed." << endl;
979  exit(1);
980  }
981  changed = bv3.set_bit_conditional(10, false, false);
982  v = bv3[10];
983  if (!v || changed) {
984  cout << "Conditional bit set failed." << endl;
985  exit(1);
986  }
987  changed = bv3.set_bit_conditional(10, false, true);
988  v = bv3[10];
989  if (v || !changed) {
990  cout << "Conditional bit set failed." << endl;
991  exit(1);
992  }
993  changed = bv3.set_bit_conditional(10, true, false);
994  v = bv3[10];
995  if (!v || !changed) {
996  cout << "Conditional bit set failed." << endl;
997  exit(1);
998  }
999  }
1000 
1001  {
1002  bvect::size_type new_size(1000001);
1003  bvect bv(0);
1004  bv.resize(new_size);
1005  bv[10] = true;
1006  bv.resize(new_size);
1007  bv[new_size-1] = 1;
1008 
1009  if (bv.size() != new_size)
1010  {
1011  cout << "Resize failed" << endl;
1012  exit(1);
1013  }
1014  if (bv.count() != 2ull)
1015  {
1016  cout << "Resize count failed" << endl;
1017  exit(1);
1018  }
1019 
1020  bv.resize(100);
1021  if (bv.size() != 100)
1022  {
1023  cout << "Resize failed" << endl;
1024  exit(1);
1025  }
1026  if (bv.count() != 1)
1027  {
1028  cout << "Resize count failed" << endl;
1029  exit(1);
1030  }
1031 
1032  bv.resize(60000100);
1033  bv.invert();
1034  bv.clear(true);
1035 
1036 
1037  if (bv.size() != 60000100)
1038  {
1039  cout << "Resize failed" << endl;
1040  exit(1);
1041  }
1042  if (bv.count() != 0)
1043  {
1044  cout << "Resize count failed" << endl;
1045  exit(1);
1046  }
1047  }
1048 
1049  {
1050  bvect bv(100);
1051  assert(bv.size()==100);
1052  bv[bm::id_max-1] = true;
1053  assert(bv.size() == bm::id_max);
1054  bv.set_bit(bm::id_max-1);
1055  assert(bv.size() == bm::id_max);
1056  }
1057 
1058  cout << "------------------------------------ SetTest() OK" << endl;
1059 }
1060 
1061 static
1063 {
1064  cout << "----------------------------- BVImportTest()" << endl;
1065 
1066  {
1067  unsigned int arr[1] = {0, };
1068  arr[0] = 0;
1069  bvect bv;
1070  bm::bit_import_u32(bv, arr, sizeof(arr)/sizeof(arr[0]), false);
1071  assert(bv.count() == 0);
1072  arr[0] = 1;
1073  bm::bit_import_u32(bv, arr, sizeof(arr)/sizeof(arr[0]), false);
1074  assert(bv.count() == 1);
1075  bvect::statistics st;
1076  bv.calc_stat(&st);
1077  assert(st.bit_blocks==1);
1078  assert(st.gap_blocks==0);
1079 
1080 
1081  {
1082  bvect::enumerator en = bv.first();
1083  assert(en.valid() && *en == 0);
1084  }
1085  arr[0] = 1 | (1u << 2) | (1u << 31);
1086  bm::bit_import_u32(bv, arr, sizeof(arr)/sizeof(arr[0]), true);
1087  assert(bv.count() == 3);
1088  {
1089  bvect::enumerator en = bv.first();
1090  assert(en.valid() && *en == 0);
1091  ++en;
1092  assert(*en == 2);
1093  ++en;
1094  assert(*en == 31);
1095  bv.calc_stat(&st);
1096  assert(st.bit_blocks==0);
1097  assert(st.gap_blocks==1);
1098  }
1099  }
1100 
1101  {
1102  unsigned int arr[2048] = {0, };
1103  arr[0] = 0;
1104  bvect bv;
1105  bm::bit_import_u32(bv, arr, sizeof(arr)/sizeof(arr[0]), true);
1106  assert(bv.count() == 0);
1107  arr[0] = 1;
1108  bm::bit_import_u32(bv, arr, sizeof(arr)/sizeof(arr[0]), false);
1109  assert(bv.count() == 1);
1110  assert(bv.test(0));
1111 
1112  arr[2047] = 1u << 31;
1113  bm::bit_import_u32(bv, arr, sizeof(arr)/sizeof(arr[0]), true);
1114  assert(bv.count() == 2);
1115  assert(bv.test(0));
1116  assert(bv.test(65535));
1117  }
1118 
1119  {
1120  unsigned int arr[2048 + 10] = {0, };
1121  arr[0] = 0;
1122  bvect bv;
1123  bm::bit_import_u32(bv, arr, sizeof(arr)/sizeof(arr[0]), false);
1124  assert(bv.count() == 0);
1125  arr[0] = 1 << 16;
1126  bm::bit_import_u32(bv, arr, sizeof(arr)/sizeof(arr[0]), false);
1127  assert(bv.count() == 1);
1128  assert(bv.test(16));
1129 
1130  arr[2047] = 1u << 31;
1131  arr[2048] = 1u << 7;
1132  bm::bit_import_u32(bv, arr, sizeof(arr)/sizeof(arr[0]), false);
1133  assert(bv.count() == 3);
1134  assert(bv.test(16));
1135  assert(bv.test(65535));
1136  assert(bv.test(65536 + 7));
1137  }
1138 
1139 
1140  cout << "... import stress test" << endl;
1141  {
1142  unsigned max = 250000;
1143  for (unsigned size = 1; size < max; ++size)
1144  {
1145  std::vector<unsigned> vect;
1146  vect.resize(size);
1147  bvect bv_control;
1148  {
1149  bvect::bulk_insert_iterator iit(bv_control);
1150  for (size_t i = 0; i < vect.size(); ++i)
1151  {
1152  unsigned w = (i & 1) ? (unsigned)rand() : 0;
1153  vect[i] = w;
1154  bvect::size_type base_idx = bvect::size_type(i * 32);
1155  for (unsigned k = 0; (k < 32) && w; ++k)
1156  {
1157  unsigned mask = (1u << k);
1158  if (w & mask) {
1159  iit = (base_idx + k);
1160  }
1161  w &= ~mask;
1162  } // for k
1163  }
1164  iit.flush();
1165  }
1166 
1167  bvect bv;
1168  bm::bit_import_u32(bv, vect.data(), (unsigned)vect.size(), true);
1169  bool eq = bv.equal(bv_control);
1170  assert(eq);
1171 
1172  if (size % 256 == 0)
1173  cout << "\r" << size << " of " << max << " " << flush;
1174  } // for size
1175  }
1176 
1177 
1178  cout << "\n----------------------------- BVImportTest() OK" << endl;
1179 }
1180 
1181 
1182 
1183 static
1185 {
1186  cout << "---------------------------- ExportTest..." << endl;
1187 
1188  {
1189  char buf[20] = {0,};
1190 
1191  buf[0] = 1;
1192  buf[1] = 1;
1193  buf[2]= (char)(1 << 1);
1194 
1195  bvect bv1;
1196  bm::export_array(bv1, buf + 0, buf + 20);
1197 
1198  auto cnt = bv1.count();
1199  assert(cnt == 3);
1200  assert(bv1.test(0));
1201  assert(bv1.test(8));
1202  assert(bv1.test(17));
1203  }
1204 
1205  {
1206  char buf[65536*10] = {0,};
1207 
1208  buf[0] = 1;
1209  buf[1] = 1;
1210  buf[2]= (char)(1 << 1);
1211 
1212  bvect bv1;
1213  export_array(bv1, buf + 0, buf + 65536*10);
1214 
1215  assert(bv1.count() == 3);
1216  assert(bv1.test(0));
1217  assert(bv1.test(8));
1218  assert(bv1.test(17));
1219  }
1220 
1221  {
1222  short buf[20] = {0,};
1223 
1224  buf[0] = 1;
1225  buf[1] = 1;
1226  buf[2]= (char)(1 << 1);
1227 
1228  bvect bv1;
1229  export_array(bv1, buf + 0, buf + 20);
1230 
1231  assert(bv1.count() == 3);
1232  assert(bv1.test(0));
1233  assert(bv1.test(16));
1234  assert(bv1.test(33));
1235  }
1236 
1237  {
1238  unsigned buf[20] = {0,};
1239 
1240  buf[0] = 1;
1241  buf[1] = 1;
1242  buf[2]= (char)(1 << 1);
1243 
1244  bvect bv1;
1245  export_array(bv1, buf + 0, buf + 20);
1246 
1247  assert(bv1.count() == 3);
1248  assert(bv1.test(0));
1249  assert(bv1.test(32));
1250  assert(bv1.test(65));
1251  }
1252 
1253 
1254  cout << "---------------------------- ExportTest Ok." << endl;
1255 }
1256 
1257 static
1259 {
1260  cout << "---------------------------- ResizeTest()" << endl;
1261  {{
1262  bvect bv(0);
1263  assert(bv.any() == false);
1264  assert(bv.count() == 0);
1265  }}
1266 
1267  {{
1268  bvect bv1(10);
1269  bvect bv2(bv1);
1270  assert(bv1.size() == bv2.size());
1271  }}
1272 
1273  {{
1274  bvect bv;
1275  bv.invert();
1276  bvect::size_type cnt = bv.count();
1277  assert(cnt == bm::id_max);
1278  assert(bv.test(bm::id_max-1));
1279  }}
1280 
1281  {{
1282  bvect bv(10);
1283  assert(bv.any() == false);
1284  assert(bv.count() == 0);
1285  bv.invert();
1286  auto cnt = bv.count();
1287  assert(cnt == 10);
1288  }}
1289 
1290  {{
1291  bvect bv1(10);
1292  bv1.set(1);
1293  bvect bv2(0);
1294 
1295  assert(bv1.size() == 10);
1296  assert(bv2.size() == 0);
1297  assert(bv1.count() == 1);
1298  assert(bv2.count() == 0);
1299 
1300  bv1.swap(bv2);
1301 
1302  assert(bv2.size() == 10);
1303  assert(bv2.count() == 1);
1304  assert(bv1.size() == 0);
1305  assert(bv1.count() == 0);
1306  }}
1307 
1308  {{
1309  bvect bv1;
1310  bv1.set(65536);
1311  bv1.set(100);
1312  assert(bv1.size() == bm::id_max);
1313  assert(bv1.count() == 2);
1314  bv1.resize(101);
1315  assert(bv1.size() == 101);
1316  assert(bv1.count() == 1);
1317  {{
1318  auto f = bv1.get_first();
1319  assert(f == 100);
1320  f = bv1.get_next(f);
1321  assert(f == 0);
1322  }}
1323 
1324  bv1.resize(10);
1325  assert(bv1.size() == 10);
1326  assert(bv1.count() == 0);
1327  auto f = bv1.get_first();
1328  assert(f == 0);
1329  }}
1330 
1331  {{
1332  bvect bv;
1333  //print_stat(bv);
1334  bv.set(100);
1335  bv.set(65536 + 10);
1336  print_stat(cout,bv);
1337  bv.set_range(0, 65536*10, false);
1338  print_stat(cout,bv);
1339  }}
1340 
1341  // test logical operations
1342 
1343  {{
1344  bvect bv1(65536 * 10);
1345  bvect bv2(65536 * 100);
1346  bv1.set(5);
1347  bv2.set(5);
1348  bv2.set(65536 * 2);
1349  bv2 &= bv1;
1350  assert(bv2.size() == 65536 * 100);
1351  assert(bv2.count() == 1);
1352  assert(bv2.get_first() == 5);
1353  }}
1354 
1355  {{
1356  bvect bv1(10);
1357  bvect bv2;
1358  bv1.set(5);
1359  bv2.set(5);
1360  bv2.set(65536 * 2);
1361  bv1 &= bv2;
1362  assert(bv1.size() == bv2.size());
1363  assert(bv1.count() == 1);
1364  assert(bv1.get_first() == 5);
1365  }}
1366 
1367  {{
1368  bvect bv1(10);
1369  bvect bv2;
1370  bv1.set(5);
1371  bv2.set(6);
1372  bv2.set(65536 * 2);
1373  bv1 |= bv2;
1374  assert(bv1.size() == bv2.size());
1375  assert(bv1.count() == 3);
1376  }}
1377 
1378  // comparison test
1379 
1380  {{
1381  int cmp;
1382  bvect bv1(10);
1383  bvect bv2;
1384  bv2.set(65536 * 2);
1385 
1386  cmp = bv1.compare(bv2);
1387  assert(cmp < 0);
1388 
1389  bv1.set(5);
1390  assert(cmp < 0);
1391  cmp = bv1.compare(bv2);
1392  assert(cmp > 0);
1393  cmp = bv2.compare(bv1);
1394  assert(cmp < 0);
1395  }}
1396 
1397  // inserter
1398  //
1399  {{
1400  bvect bv1(10);
1401  bm::id64_t maxs= bm::id_max - 100;
1402  {
1403  bvect::insert_iterator it(bv1);
1404  *it = 100 * 65536;
1405  *it = maxs;
1406  }
1407  auto sz = bv1.size();
1408  assert(sz == maxs+1);
1409  }}
1410 
1411  // serialization
1412  //
1413  {{
1414  const bvect::size_type test_size = bm::id_max - 100;
1415  bvect bv1(test_size);
1416  bv1.set(test_size - 1005);
1417  struct bvect::statistics st1;
1418  bv1.calc_stat(&st1);
1419 
1420  unsigned char* sermem = new unsigned char[st1.max_serialize_mem];
1421  size_t slen2 = bm::serialize(bv1, sermem);
1422  cout << slen2 << endl;
1423 
1424  bvect bv2(0);
1425  bm::deserialize(bv2, sermem);
1426  delete [] sermem;
1427 
1428  assert(bv2.size() == test_size);
1429  assert(bv2.count() == 1);
1430  auto first = bv2.get_first();
1431  assert(first == test_size - 1005);
1432  }}
1433 
1434  {{
1435  bvect bv1(10);
1436  bv1.set(5);
1437  unsigned int arg[] = { 10, 65536, 65537, 65538 * 10000 };
1438  unsigned* it1 = arg;
1439  unsigned* it2 = arg + 4;
1440  combine_or(bv1, it1, it2);
1441  assert(bv1.size() == 65538 * 10000 + 1);
1442  bvect::enumerator en = bv1.first();
1443  while (en.valid())
1444  {
1445  cout << *en << " ";
1446  ++en;
1447  }
1448  }}
1449  cout << "---------------------------- ResizeTest() OK" << endl;
1450 }
1451 
1452 static
1454 {
1455  if (!en1.valid() && !en2.valid())
1456  return;
1457  bool fsm_equal = en1.compare_state(en2);
1458  if (!fsm_equal)
1459  {
1460  cerr << "Enumerators FSM comparison failed" << endl;
1461  assert(0);
1462  exit(1);
1463  }
1464 }
1465 
1466 static
1468 {
1469  cout << "---------------------------- Empty bvector test" << endl;
1470 
1471  {
1472  bvect bv1;
1473  bvect bv2;
1474 
1475  bvect bv3(bv1 & bv2);
1476  bvect bv4 = (bv1 & bv2);
1477 
1478  std::vector< bvect > v;
1479  v.push_back(bvect());
1480  }
1481 
1482  {
1483  bvect bv1;
1484  auto cnt = bv1.count_range(0, 10);
1485  if (cnt)
1486  {
1487  cerr << "Failed count_range()" << endl;
1488  exit(1);
1489  }
1490  bool b = bv1.test(0);
1491  if (b)
1492  {
1493  cerr << "Failed test" << endl;
1494  exit(1);
1495  }
1496 
1497  b = bv1.any();
1498  if (b)
1499  {
1500  cerr << "Failed any" << endl;
1501  exit(1);
1502  }
1503 
1504  bv1.set_bit(0);
1505  if (!bv1.any())
1506  {
1507  cerr << "Failed set_bit" << endl;
1508  exit(1);
1509  }
1510  }
1511  {
1512  bvect bv1;
1513  bool b = bv1.set_bit_and(0, false);
1514  if (bv1.any() || b)
1515  {
1516  cerr << "Failed set_bit" << endl;
1517  exit(1);
1518  }
1519  }
1520  {
1521  bvect bv1;
1522  bv1.set_range(0, 1, false);
1523  if (bv1.any())
1524  {
1525  cerr << "Failed set_range" << endl;
1526  exit(1);
1527  }
1528  bv1.set_range(0, 1, true);
1529  if (bv1.count()!=2)
1530  {
1531  cerr << "Failed set_range(0,1)" << endl;
1532  exit(1);
1533  }
1534  }
1535  {
1536  bvect bv1;
1537  bv1.clear_bit(0);
1538  if (bv1.any())
1539  {
1540  cerr << "Failed clear_bit" << endl;
1541  exit(1);
1542  }
1543  }
1544  {
1545  bvect bv1;
1546  bv1.clear();
1547  if (bv1.any())
1548  {
1549  cerr << "Failed clear()" << endl;
1550  exit(1);
1551  }
1552  }
1553  {
1554  bvect bv1;
1555  bv1.invert();
1556  if (!bv1.any())
1557  {
1558  cerr << "Failed invert()" << endl;
1559  exit(1);
1560  }
1561  }
1562  {
1563  bvect bv1;
1564  bvect bv2;
1565  bv1.swap(bv2);
1566  if (bv1.any() || bv2.any())
1567  {
1568  cerr << "Failed swap()" << endl;
1569  exit(1);
1570  }
1571  }
1572  {
1573  bvect bv1;
1574  if (bv1.get_first() != 0)
1575  {
1576  cerr << "Failed get_first()" << endl;
1577  exit(1);
1578  }
1579  }
1580  {
1581  bvect bv1;
1582  if (bv1.extract_next(0) != 0)
1583  {
1584  cerr << "Failed extract_next()" << endl;
1585  exit(1);
1586  }
1587  }
1588  {
1589  bvect bv1;
1590  bvect::statistics st;
1591  bv1.calc_stat(&st);
1592  if (st.memory_used == 0)
1593  {
1594  cerr << "Failed calc_stat()" << endl;
1595  assert(0);exit(1);
1596  }
1597  }
1598  {
1599  bvect bv1;
1600  bvect bv2;
1601  bvect bv3;
1602  bv1.bit_or(bv2);
1603  if (bv1.any())
1604  {
1605  cerr << "Failed bit_or()" << endl;
1606  exit(1);
1607  }
1608  bv2.set_bit(bm::id_max-100);
1609  bv1.bit_or(bv2);
1610  if (!bv1.any())
1611  {
1612  cerr << "Failed bit_or()" << endl;
1613  exit(1);
1614  }
1615  bv1.bit_or(bv3);
1616  if (bv1.count()!=1)
1617  {
1618  cerr << "Failed bit_or()" << endl;
1619  exit(1);
1620  }
1621  }
1622 
1623  {
1624  bvect bv1;
1625  bvect bv2;
1626  bv1.bit_and(bv2);
1627  if (bv1.any())
1628  {
1629  cerr << "Failed bit_and()" << endl;
1630  exit(1);
1631  }
1632  bv2.set_bit(100000000);
1633  bv1.bit_and(bv2);
1634  if (bv1.any())
1635  {
1636  cerr << "Failed bit_and()" << endl;
1637  exit(1);
1638  }
1639  bv2.bit_and(bv1);
1640  if (bv2.count()!=0)
1641  {
1642  cerr << "Failed bit_and()" << endl;
1643  exit(1);
1644  }
1645  }
1646 
1647  {
1648  bvect bv1;
1649  bvect::statistics st1;
1650  bv1.optimize(0, bvect::opt_compress, &st1);
1651  if (st1.memory_used == 0)
1652  {
1653  cerr << "Failed calc_stat()" << endl;
1654  exit(1);
1655  }
1656  bv1.optimize_gap_size();
1657  }
1658 
1659  {
1660  bvect bv1;
1661  bvect bv2;
1662 
1663  int r = bv1.compare(bv2);
1664  if (r != 0)
1665  {
1666  cerr << "Failed compare()" << endl;
1667  assert(0);
1668  exit(1);
1669 
1670  }
1671  bv2.set_bit(bm::id_max-1000);
1672  r = bv1.compare(bv2);
1673  if (r == 0)
1674  {
1675  cerr << "Failed compare()" << endl;
1676  exit(1);
1677 
1678  }
1679  r = bv2.compare(bv1);
1680  if (r == 0)
1681  {
1682  cerr << "Failed compare()" << endl;
1683  exit(1);
1684  }
1685  }
1686 
1687  {
1688  bvect bv1;
1689  bvect::enumerator en1 = bv1.first();
1690  bvect::enumerator en2 = bv1.get_enumerator(0ULL);
1691  CompareEnumerators(en1, en2);
1692  if (en1.valid() || en2.valid())
1693  {
1694  cerr << "failed first enumerator" << endl;
1695  exit(1);
1696  }
1697  }
1698 
1699  {
1700  bvect bv1;
1701  bv1.resize(0);
1702 
1703  bv1.invert();
1704  assert(!bv1.any());
1705  assert(bv1.size()==0);
1706  }
1707 
1708  cout << "---------------------------- Empty bvector test OK" << endl;
1709 
1710 }
1711 
1712 static
1714 {
1715  cout << "-------------------------------------------- EnumeratorTest" << endl;
1716 
1717  {
1718  bvect bvect1;
1719 
1720  bvect1.set_bit(100);
1721 
1722  {
1723  auto n = bvect1.get_next(101);
1724  assert(!n);
1725  }
1726 
1727  bvect::enumerator en = bvect1.first();
1728  auto n = bvect1.get_next(0);
1729 
1730  bvect::enumerator en1 = bvect1.get_enumerator(n);
1731  if (*en != 100 || n != 100 || *en1 != 100)
1732  {
1733  cout << "1.Enumerator error !" << endl;
1734  exit(1);
1735  }
1736  CompareEnumerators(en, en1);
1737 
1738  bvect1.clear_bit(100);
1739 
1740  bvect1.set_bit(bm::id_max - 100);
1741  en.go_first();
1742  n = bvect1.get_next(0);
1743  en1.go_to(n);
1744  if (*en != bm::id_max - 100 || n != *en || *en1 != *en)
1745  {
1746  cout << "2. Enumerator error !" << endl;
1747  assert(0);
1748  exit(1);
1749  }
1750  CompareEnumerators(en, en1);
1751 
1752  bvect1.optimize();
1753  en = bvect1.first();
1754  n = bvect1.get_next(0);
1755  en1 = bvect1.first();
1756  en1.go_to(n);
1757  if (*en != bm::id_max - 100 || n != *en || *en1 != *en)
1758  {
1759  cout << "2. Enumerator error !" << endl;
1760  assert(0);
1761  exit(1);
1762  }
1763  CompareEnumerators(en, en1);
1764 
1765  }
1766 
1767  {
1768  bvect bvect1;
1769  bvect1.set_bit(0);
1770  bvect1.set_bit(10);
1771  bvect1.set_bit(35);
1772  bvect1.set_bit(1000);
1773  bvect1.set_bit(2016519);
1774  bvect1.set_bit(2034779);
1775  bvect1.set_bit(bm::id_max-1);
1776 
1777  bvect::enumerator en = bvect1.first();
1778 
1779  auto num = bvect1.get_first();
1780 
1781  bvect::enumerator end = bvect1.end();
1782  while (en < end)
1783  {
1784  cout << num << endl;
1785  bvect::enumerator en1 = bvect1.get_enumerator(num ? num-1 : num);
1786  if (*en != num || *en != *en1)
1787  {
1788  cout << "Enumeration comparison failed !" <<
1789  " enumerator = " << *en <<
1790  " get_next() = " << num <<
1791  " goto enumerator = " << *en1 <<
1792  endl;
1793  exit(1);
1794  }
1795  CompareEnumerators(en, en1);
1796 
1797  ++en;
1798  num = bvect1.get_next(num);
1799  ++en1;
1800  CompareEnumerators(en, en1);
1801  {
1802  auto num2 = num / 2;
1803  if (num2 < num)
1804  {
1805  auto idx0 = bvect1.get_next(num2);
1806  bvect::enumerator en3 = bvect1.get_enumerator(num2);
1807  assert(idx0 == *en3);
1808  }
1809  }
1810  }
1811  if (num != 0)
1812  {
1813  cout << "Enumeration error!" << endl;
1814  exit(1);
1815  }
1816  }
1817 
1818  cout << "FULL bvector enumerator stress test (0)..." << endl;
1819  {
1820  bvect bvect1;
1821  bvect1.set();
1822 
1823  {
1824  bvect::enumerator en2(&bvect1, bm::id_max-1);
1825  ++en2;
1826  bool b = en2.valid();
1827  assert(!b);
1828  }
1829 
1830  bvect::enumerator en = bvect1.first();
1831  auto num = bvect1.get_first();
1832  while (en.valid())
1833  {
1834  if (*en != num)
1835  {
1836  cout << "Enumeration comparison failed !" <<
1837  " enumerator = " << *en <<
1838  " get_next() = " << num << endl;
1839  assert(0);
1840  exit(1);
1841  }
1842 
1843  ++en;
1844  num = bvect1.get_next(num);
1845  {
1846  bvect::enumerator en2(&bvect1, num);
1847  if (*en2 != num)
1848  {
1849  cout << "Enumeration comparison failed !" <<
1850  " enumerator = " << *en <<
1851  " get_next() = " << num << endl;
1852  assert(0);
1853  exit(1);
1854  }
1855  CompareEnumerators(en, en2);
1856  }
1857  if (num > (bm::set_sub_array_size * bm::gap_max_bits * 2))
1858  break;
1859  } // while
1860  }
1861  cout << "FULL bvector enumerator stress test (0) ... OK" << endl;
1862 
1863 
1864  cout << "FULL bvector enumerator stress test (1)..." << endl;
1865  {
1866  bvect bvect1;
1867  bvect1.set();
1868 
1870 
1871  bvect::enumerator en(&bvect1, start_idx);
1872  while (en.valid())
1873  {
1874  bvect::size_type pos;
1875  bool b = bvect1.find(start_idx, pos);
1876  if (*en != pos || !b)
1877  {
1878  cout << "2. Enumeration comparison failed !" <<
1879  " enumerator = " << *en <<
1880  " find() = " << pos << endl;
1881  assert(0);
1882  exit(1);
1883  }
1884 
1885  ++en;
1886  pos = bvect1.get_next(pos);
1887  if (pos)
1888  {
1889  bvect::enumerator en2(&bvect1, pos);
1890  if (*en2 != pos)
1891  {
1892  cout << "2. Enumeration comparison failed !" <<
1893  " enumerator = " << *en <<
1894  " get_next() = " << pos << endl;
1895  assert(0);
1896  exit(1);
1897  }
1898  CompareEnumerators(en, en2);
1899  }
1900  else
1901  {
1902  assert(start_idx == bm::id_max-1);
1903  }
1904  start_idx = pos;
1905  } // while
1906  }
1907  cout << "FULL bvector enumerator stress test (1) ... OK" << endl;
1908 
1909  {
1910  bvect bvect1;
1911 
1912  unsigned i;
1913  for(i = 0; i < 65536; ++i)
1914  {
1915  bvect1.set_bit(i);
1916  }
1917  for(i = 65536*10; i < 65536*20; i+=3)
1918  {
1919  bvect1.set_bit(i);
1920  }
1921 
1922  bvect::enumerator en = bvect1.first();
1923  bvect::size_type num = bvect1.get_first();
1924  while (en < bvect1.end())
1925  {
1926  bvect::enumerator en1 = bvect1.get_enumerator(num);
1927  if (*en != num || *en != *en1)
1928  {
1929  cout << "Enumeration comparison failed !" <<
1930  " enumerator = " << *en <<
1931  " get_next() = " << num <<
1932  " goto enumerator = " << *en1
1933  << endl;
1934  exit(1);
1935  }
1936  ++en;
1937  num = bvect1.get_next(num);
1938  if (num == 31)
1939  {
1940  num = num + 0;
1941  }
1942  ++en1;
1943  CompareEnumerators(en, en1);
1944  }
1945  if (num != 0)
1946  {
1947  cout << "Enumeration error!" << endl;
1948  exit(1);
1949  }
1950  }
1951 
1952 
1953  {
1954  bvect bvect1;
1956  bvect1.set_bit(100);
1957 
1958  bvect::enumerator en = bvect1.first();
1959  bvect::enumerator en1 = bvect1.get_enumerator(99);
1960  if (*en != 100 || *en != *en1)
1961  {
1962  cout << "Enumerator error !" << endl;
1963  exit(1);
1964  }
1965  CompareEnumerators(en, en1);
1966 
1967  bvect1.clear_bit(100);
1968 
1969  bvect1.set_bit(bm::id_max - 100);
1970  en.go_first();
1971  en1.go_to(10);
1972 
1973  if ((*en != bm::id_max - 100) || *en != *en1)
1974  {
1975  cout << "Enumerator error !" << endl;
1976  exit(1);
1977  }
1978  CompareEnumerators(en, en1);
1979  print_stat(cout,bvect1);
1980  }
1981 
1982  {
1983  bvect bvect1;
1985  bvect1.set_bit(0);
1986  bvect1.set_bit(1);
1987  bvect1.set_bit(10);
1988  bvect1.set_bit(100);
1989  bvect1.set_bit(1000);
1990 
1991  bvect::enumerator en = bvect1.first();
1992 
1993  auto num = bvect1.get_first();
1994 
1995  while (en < bvect1.end())
1996  {
1997  bvect::enumerator en1 = bvect1.get_enumerator(num);
1998  if (*en != num || *en != *en1)
1999  {
2000  cout << "Enumeration comparison failed !" <<
2001  " enumerator = " << *en <<
2002  " get_next() = " << num <<
2003  " goto enumerator = " << *en1 << endl;
2004  exit(1);
2005  }
2006  CompareEnumerators(en, en1);
2007  ++en;
2008  num = bvect1.get_next(num);
2009  ++en1;
2010  CompareEnumerators(en, en1);
2011  }
2012  if (num != 0)
2013  {
2014  cout << "Enumeration error!" << endl;
2015  exit(1);
2016  }
2017  }
2018 }
2019 
2020 
2021 static
2023 {
2024  cout << "----------------------------- IntervalEnumeratorTest()" << endl;
2025 
2026  bool valid;
2027  cout << "empty bvector tests" << endl;
2028  {
2030  valid = ien.valid();
2031  assert(!valid);
2032  }
2033 
2034  {
2035  bvect bv;
2037 
2038  valid = ien.valid();
2039  assert(!valid);
2040  }
2041 
2042 
2043  cout << "inverted bvector tests" << endl;
2044  {
2045  bvect bv;
2046  bv.invert();
2048 
2049  valid = ien.valid();
2050  assert(valid);
2051  assert(ien.start() == 0);
2052  assert(ien.end() == bm::id_max-1);
2053  }
2054 
2055  cout << "GAP bvector tests" << endl;
2056  {
2057  bvect bv;
2058  bv.set_range(0, 33);
2059 
2061  valid = ien.valid();
2062  assert(valid);
2063  assert(ien.start() == 0);
2064  assert(ien.end() == 33);
2065 
2066  bv.set_range(bm::id_max/2, bm::id_max/2 + 2);
2067  ien.go_to(100);
2068  valid = ien.valid();
2069  assert(valid);
2070  assert(ien.start() == bm::id_max/2);
2071  assert(ien.end() == bm::id_max/2 + 2);
2072 
2073  bv.set_range(bm::id_max-1, bm::id_max-1);
2074  ien.go_to(bm::id_max-2);
2075  valid = ien.valid();
2076  assert(valid);
2077  assert(ien.start() == bm::id_max-1);
2078  assert(ien.end() == bm::id_max-1);
2079 
2080  ien.go_to(0);
2081  valid = ien.valid();
2082  assert(valid);
2083  assert(ien.start() == 0);
2084  assert(ien.end() == 33);
2085 
2086  valid = ien.advance();
2087  assert(valid);
2088  assert(ien.start() == bm::id_max/2);
2089  assert(ien.end() == bm::id_max/2 + 2);
2090 
2091  valid = ien.advance();
2092  assert(valid);
2093  assert(ien.start() == bm::id_max-1);
2094  assert(ien.end() == bm::id_max-1);
2095 
2096  valid = ien.advance();
2097  assert(!valid);
2098  }
2099 
2100  {
2101  bvect bv { 0 };
2103 
2104  valid = ien.valid();
2105  assert(valid);
2106  assert(ien.start() == 0);
2107  assert(ien.end() == 0);
2108  }
2109 
2110 
2111  {
2112  bvect bv { bm::id_max-1};
2114 
2115  valid = ien.valid();
2116  assert(valid);
2117  assert(ien.start() == bm::id_max-1);
2118  assert(ien.end() == bm::id_max-1);
2119 
2120  }
2121 
2122  {
2123  bvect bv { 0, 100, bm::id_max-1 };
2124  for (unsigned pass = 0; pass < 2; ++pass)
2125  {
2127 
2128  valid = ien.valid();
2129  assert(valid);
2130  assert(ien.start() == 0);
2131  assert(ien.end() == 0);
2132 
2133  valid = ien.advance();
2134  assert(valid);
2135  assert(ien.start() == 100);
2136  assert(ien.end() == 100);
2137 
2138  valid = ien.advance();
2139  assert(valid);
2140  assert(ien.start() == bm::id_max-1);
2141  assert(ien.end() == bm::id_max-1);
2142 
2143  valid = ien.advance();
2144  assert(!valid);
2145  bv.optimize();
2146 
2147  } // for pass
2148  }
2149 
2150  cout << "interval_enumerator +N stress test" << endl;
2151  {
2152  unsigned delta_max = 65536;
2153  for (unsigned inc = 1; inc < delta_max; ++inc)
2154  {
2155  if (inc % 256 == 0)
2156  cout << "\rinc = " << inc << " of " << delta_max << flush;
2157  bvect bv;
2158  bvect bv_c;
2159  bvect::size_type test_max = 65535 * 256;
2160 
2161  for (bvect::size_type i = 0; i < test_max; i+=inc)
2162  bv.set(i);
2163 
2164  for (unsigned pass = 0; pass < 2; ++pass)
2165  {
2167  while (ien.valid())
2168  {
2169  auto from = ien.start();
2170  auto to = ien.end();
2171  bv_c.set_range(from, to);
2172  if (!ien.advance())
2173  break;
2174  }
2175  bool eq = bv.equal(bv_c);
2176  assert(eq);
2177 
2178  bv.optimize();
2179  bv_c.clear();
2180  } // for pass
2181  } // for inc
2182 
2183  }
2184 
2185 
2186 
2187 
2188  cout << "\n----------------------------- IntervalEnumeratorTest() OK" << endl;
2189 }
2190 
2191 
2192 static
2193 void VerifyCountRange(const bvect& bv,
2194  const bvect::rs_index_type& bc_arr,
2195  bvect::size_type from,
2196  bvect::size_type to)
2197 {
2198  for (bvect::size_type i = from; i < to; ++i)
2199  {
2200  bvect::size_type cnt1 = bv.count_range(0, i);
2201  bvect::size_type cnt2 = bv.count_to(i, bc_arr);
2202  auto cnt3 = bv.count_to_test(i, bc_arr);
2203 
2204  assert(cnt1 == cnt2);
2205  if (cnt1 != cnt2)
2206  {
2207  cerr << "VerifyCountRange failed!" << " count_range()=" << cnt1
2208  << " count_to()=" << cnt2 << endl;
2209  }
2210  if (cnt3 != cnt1)
2211  {
2212  bool b = bv.test(i);
2213  if (b)
2214  {
2215  cerr << "VerifyCountRange failed! count_to_test()" << cnt3 << " count_range()=" << cnt1
2216  << endl;
2217  }
2218  }
2219 
2220  bvect::size_type cnt4 = bv.count_range(i, to);
2221  bvect::size_type cnt5 = bv.count_range(i, to, bc_arr);
2222  if (cnt4 != cnt5)
2223  {
2224  cnt5 = bv.count_range(i, to, bc_arr);
2225  assert(cnt4 == cnt5);
2226  exit(1);
2227  }
2228  } // for
2229 }
2230 
2231 static
2233 {
2234  cout << "---------------------------- RSIndexTest() test" << endl;
2235 
2236  {
2237  rs_ind rsi;
2238 
2241 
2242  rsi.set_super_block(0, 1);
2243  rsi.set_super_block(1, 2);
2244  rsi.set_super_block(2, 3);
2245  rsi.set_null_super_block(3);
2246  rsi.set_full_super_block(4);
2247 
2248  auto sb_size = rsi.super_block_size();
2249  assert(sb_size == 5);
2250 
2251  auto rc = rsi.get_super_block_count(0);
2252  assert(rc == 1);
2253  rc = rsi.get_super_block_count(1);
2254  assert(rc == 2);
2255  rc = rsi.get_super_block_count(2);
2256  assert(rc == 3);
2257  rc = rsi.get_super_block_count(256);
2258  assert(rc == 0);
2259 
2260 
2261  auto bc = rsi.get_super_block_rcount(0);
2262  assert(bc == 1);
2263  bc = rsi.get_super_block_rcount(1);
2264  assert(bc == 3);
2265  bc = rsi.get_super_block_rcount(2);
2266  assert(bc == 6);
2267 
2268  unsigned i = rsi.find_super_block(1);
2269  assert(i == 0);
2270  i = rsi.find_super_block(2);
2271  assert(i == 1);
2272  i = rsi.find_super_block(3);
2273  assert(i == 1);
2274  i = rsi.find_super_block(4);
2275  assert(i == 2);
2276  i = rsi.find_super_block(200);
2277  assert(i == 4);
2278 /*
2279  i = rsi.find_super_block(bm::id_max);
2280  assert(i == 5);
2281 */
2282  }
2283 
2284  {
2285  unsigned bcount[bm::set_sub_array_size];
2286  bm::id64_t sub_count1[bm::set_sub_array_size];
2287  bm::id64_t sub_count2[bm::set_sub_array_size];
2288  for (unsigned i = 0; i < bm::set_sub_array_size; ++i)
2289  {
2290  bcount[i] = 0, sub_count1[i] = sub_count2[i] = 0;
2291  } // for
2292  bcount[0] = 1;
2293  bcount[255] = 2;
2294 
2295  sub_count1[0] = 1; // sub-range 0
2296  sub_count1[255] = 0; // sub-3
2297  sub_count2[0] = 1 << 16; // sub-2
2298  sub_count2[255] = 1 << 16; // sub 2,3
2299 
2300 
2301  rs_ind rsi;
2302  // -----------------------------------------
2306 
2307 
2308  rsi.set_null_super_block(0);
2309  auto tcnt = rsi.count();
2310  assert(tcnt == 0);
2311  rsi.register_super_block(1, &bcount[0], &sub_count1[0]);
2312  tcnt = rsi.count();
2313  assert(tcnt == 3);
2314  rsi.register_super_block(2, &bcount[0], &sub_count2[0]);
2315  tcnt = rsi.count();
2316  assert(tcnt == 6);
2317  rsi.set_full_super_block(3);
2318  tcnt = rsi.count();
2319  assert(tcnt == 6 + bm::set_sub_array_size * 65536);
2320 
2321  unsigned i = rsi.find_super_block(1);
2322  assert(i == 1);
2323  i = rsi.find_super_block(3);
2324  assert(i == 1);
2325  i = rsi.find_super_block(4);
2326  assert(i == 2);
2327  i = rsi.find_super_block(400);
2328  assert(i == 3);
2329 // i = rsi.find_super_block(bm::id_max);
2330 // assert(i == rsi.super_block_size());
2331 
2332  unsigned bc;
2333  rs_ind::size_type rbc;
2334  for (unsigned nb = 0; nb < bm::set_sub_array_size; ++nb)
2335  {
2336  bc = rsi.count(nb);
2337  assert(bc == 0);
2338  rbc = rsi.rcount(nb);
2339  assert(!rbc);
2340  }
2341  bc = rsi.count(bm::set_sub_array_size);
2342  assert(bc == 1);
2343  rbc = rsi.rcount(bm::set_sub_array_size);
2344  assert(rbc == 1);
2345 
2346  bc = rsi.count(bm::set_sub_array_size+1);
2347  assert(bc == 0);
2348  rbc = rsi.rcount(bm::set_sub_array_size+1);
2349  assert(rbc == 1);
2350 
2351  bc = rsi.count(bm::set_sub_array_size + 255);
2352  assert(bc == 2);
2353  rbc = rsi.rcount(bm::set_sub_array_size + 255);
2354  assert(rbc == 3);
2355 
2356  bc = rsi.count(bm::set_sub_array_size*3);
2357  assert(bc == 65536);
2358  rbc = rsi.rcount(bm::set_sub_array_size*3);
2359  assert(rbc == 65536+6);
2360  rbc = rsi.rcount(bm::set_sub_array_size*3 + 1);
2361  assert(rbc == 65536+6 + 65536);
2362 
2363 
2364  // ==========================
2365  {
2366  auto nb = rsi.find(1);
2367  assert(nb == 256);
2368 
2369  nb = rsi.find(2);
2370  assert(nb == bm::set_sub_array_size+255);
2371  nb = rsi.find(3);
2372  assert(nb == bm::set_sub_array_size+255);
2373 
2374  nb = rsi.find(4);
2375  assert(nb == bm::set_sub_array_size+255+1);
2376 
2377  nb = rsi.find(65536);
2378  assert(nb == 3*bm::set_sub_array_size+0);
2379  nb = rsi.find(65536*2);
2380  assert(nb == 3*bm::set_sub_array_size+1);
2381  nb = rsi.find(65536*3);
2382  assert(nb == 3*bm::set_sub_array_size+2);
2383  }
2384  // ==========================
2385 
2386  {
2387  bool b;
2390  bm::gap_word_t sub_range;
2391 
2392  rank = 1;
2393  b = rsi.find(&rank, &nb, &sub_range);
2394  assert(b);
2395  assert(nb == 256);
2396  assert(sub_range == 0);
2397  assert(rank == 1);
2398 
2399  rank = 2;
2400  b = rsi.find(&rank, &nb, &sub_range);
2401  assert(b);
2402  assert(nb == bm::set_sub_array_size+255);
2403  assert(sub_range == bm::rs3_border1 + 1);
2404  assert(rank == 1);
2405 
2406  rank = 3;
2407  b = rsi.find(&rank, &nb, &sub_range);
2408  assert(b);
2409  assert(nb == bm::set_sub_array_size+255);
2410  assert(sub_range == bm::rs3_border1 + 1);
2411  assert(rank == 2);
2412 
2413  rank = 4;
2414  b = rsi.find(&rank, &nb, &sub_range);
2415  assert(b);
2416  assert(nb == bm::set_sub_array_size+255+1);
2417  assert(sub_range == bm::rs3_border0 + 1);
2418  assert(rank == 1);
2419 
2420  rank = 5;
2421  b = rsi.find(&rank, &nb, &sub_range);
2422  assert(b);
2423  assert(nb == bm::set_sub_array_size+256+255);
2424  assert(sub_range == bm::rs3_border0 + 1);
2425  assert(rank == 1);
2426 
2427  rank = 6;
2428  b = rsi.find(&rank, &nb, &sub_range);
2429  assert(b);
2430  assert(nb == bm::set_sub_array_size+256+255);
2431  assert(sub_range == bm::rs3_border1 + 1);
2432  assert(rank == 1);
2433 
2434  rank = 65536;
2435  b = rsi.find(&rank, &nb, &sub_range);
2436  assert(b);
2437  assert(nb == 3*bm::set_sub_array_size+0);
2438  assert(sub_range == bm::rs3_border1 + 1);
2439  assert(rank == 65536 - 6 - bm::rs3_border1 - 1);
2440 
2441  rank = 65536 + 7;
2442  b = rsi.find(&rank, &nb, &sub_range);
2443  assert(b);
2444  assert(nb == 3*bm::set_sub_array_size+1);
2445  assert(sub_range == 0);
2446  assert(rank == 1);
2447 
2448  rank = bm::id_max;
2449  b = rsi.find(&rank, &nb, &sub_range);
2450  assert(!b);
2451 
2452 
2453  }
2454 
2455  }
2456 
2457 
2458  cout << "---------------------------- RSIndexTest() test OK" << endl;
2459 }
2460 
2461 
2462 
2463 static
2465 {
2466  cout << "---------------------------- CountRangeTest..." << endl;
2467 
2468  cout << "Stage 0" << endl;
2469  {{
2470  bvect bv1 { 0, 1 };
2471 
2472  bvect::rs_index_type bc_arr;
2473  bv1.build_rs_index(&bc_arr);
2474  assert(bc_arr.count() == 2);
2475 
2476  assert(bc_arr.rcount(512) == 2);
2477  for (bvect::size_type i = 0; i < bm::set_total_blocks; ++i)
2478  {
2479  assert(bc_arr.rcount(i) == 2);
2480  } // for
2481 
2482  VerifyCountRange(bv1, bc_arr, 0, 200000);
2483 
2484  bv1.optimize();
2485  bvect::rs_index_type bc_arr1;
2486  bv1.build_rs_index(&bc_arr1);
2487 
2488  for (bvect::size_type i = 0; i < bm::set_total_blocks; ++i)
2489  {
2490  assert(bc_arr1.rcount(i) == 2);
2491  } // for
2492 
2493  VerifyCountRange(bv1, bc_arr1, 0, 200000);
2494  }}
2495 
2496  cout << "Stage 1" << endl;
2497  {{
2498  bvect bv1 { bm::id_max - 100, bm::id_max - 1 };
2499 
2500  bvect::rs_index_type bc_arr;
2501  bv1.build_rs_index(&bc_arr);
2502  assert(bc_arr.count() == 2);
2503 
2504  assert(bc_arr.rcount(bm::set_total_blocks-1) == 2);
2505  for (bvect::size_type i = 0; i < bm::set_total_blocks-1; ++i)
2506  {
2507  assert(bc_arr.rcount(i) == 0);
2508  } // for
2509 
2510  VerifyCountRange(bv1, bc_arr, 0, 200000);
2511 
2512  bv1.optimize();
2513  bvect::rs_index_type bc_arr1;
2514  bv1.build_rs_index(&bc_arr1);
2515 
2516  assert(bc_arr.rcount(bm::set_total_blocks-1) == 2);
2517  for (bvect::size_type i = 0; i < bm::set_total_blocks-1; ++i)
2518  {
2519  assert(bc_arr1.rcount(i) == 0);
2520  } // for
2521 
2522  VerifyCountRange(bv1, bc_arr1, 0, 200000);
2523  VerifyCountRange(bv1, bc_arr1, bm::id_max-2000, bm::id_max-1);
2524  }}
2525 
2526  cout << "Stage 2" << endl;
2527  {{
2528  bvect bv1 { 0, 1, 65535+10, 65535+20, 65535+21, bm::id_max-100};
2529 
2530  bvect::rs_index_type bc_arr;
2531  bv1.build_rs_index(&bc_arr);
2532 
2533  assert(bc_arr.rcount(0) == 2);
2534  assert(bc_arr.rcount(1) == 5);
2535  assert(bc_arr.rcount(bm::set_total_blocks-1) == 6);
2536 
2537  for (bvect::size_type i = 2; i < bm::set_total_blocks-1; ++i)
2538  {
2539  assert(bc_arr.rcount(i) == 5);
2540  } // for
2541 
2542  VerifyCountRange(bv1, bc_arr, bm::id_max-1, bm::id_max-1);
2543  for (unsigned i = 0; i < 2; ++i)
2544  {
2545  cout << "Pass " << i << endl;
2546  cout << "1 ..." << endl;
2547  VerifyCountRange(bv1, bc_arr, 0, 200000);
2548  cout << "2 ..." << endl;
2549  VerifyCountRange(bv1, bc_arr, bm::id_max-200, bm::id_max-1);
2550  // check within empty region
2551  cout << "3 ..." << endl;
2552  VerifyCountRange(bv1, bc_arr, bm::id_max/2-200, bm::id_max/2+2000);
2553 
2554  bv1.optimize();
2555  bv1.build_rs_index(&bc_arr);
2556  }
2557  }}
2558 
2559  cout << "Stage 3. check inverted bvector" << endl;
2560  {{
2561  bvect bv1;
2562 
2563  bv1.invert();
2564 
2565  bvect::rs_index_type bc_arr;
2566  bv1.build_rs_index(&bc_arr);
2567  auto cnt1 = bv1.count();
2568  auto cnt2 = bc_arr.count();
2569  assert(cnt1 == cnt2);
2570 
2571  cout << "1 ..." << endl;
2572  VerifyCountRange(bv1, bc_arr, bm::id_max-1, bm::id_max-1);
2573  cout << "2 ..." << endl;
2574  VerifyCountRange(bv1, bc_arr, 0, 200000);
2575  cout << "3 ..." << endl;
2576  VerifyCountRange(bv1, bc_arr, bm::id_max-2000, bm::id_max-1);
2577  cout << "4 ..." << endl;
2578  VerifyCountRange(bv1, bc_arr, bm::id_max/2-2000, bm::id_max/2+2000);
2579  cout << "Done!" << endl;
2580 
2581  }}
2582 
2583  cout << "---------------------------- CountRangeTest OK" << endl;
2584 }
2585 
2586 // -----------------------------------------------------------------------
2587 
2589 from_arr[] = { 0, 0, 0, 0, 7, 1, 0, 65535, 65535, 0, 0, bm::id_max/2-2001, bm::id_max-2000};
2591 to_arr[] = { 0, 1, 16, 32, 31, 255, 65535, 65536, 65536*2, 65537, bm::id_max/2-2000, bm::id_max/2+2000, bm::id_max-1};
2592 
2593 
2594 static
2595 void verify_all_one_ranges(const bvect& bv, bool all_one)
2596 {
2597  size_t fr_size = sizeof(from_arr) / sizeof(from_arr[0]);
2598  size_t to_size = sizeof(to_arr) / sizeof(to_arr[0]);
2599 
2600  assert(fr_size == to_size);
2601 
2602  for (unsigned t = 0; t < fr_size; ++t)
2603  {
2604  bool one_test, one_test_cnt, any_one_test, is_int;
2605  bvect::size_type from(from_arr[t]), to(to_arr[t]);
2606 
2607  one_test = bv.is_all_one_range(from, to);
2608  any_one_test = bv.any_range(from, to);
2609  is_int = bm::is_interval(bv, from, to);
2610  if (all_one)
2611  {
2612  assert(one_test);
2613  assert(any_one_test);
2614  if (is_int)
2615  {
2616  assert(from == 0 || bv.test(from-1) == false);
2617  assert(bv.test(to+1) == false);
2618  }
2619  }
2620  else
2621  {
2622  auto cnt = bv.count_range(from, to);
2623  one_test_cnt = (cnt == to - from + 1);
2624  assert(one_test_cnt == one_test);
2625  if (cnt)
2626  {
2627  assert(any_one_test);
2628  }
2629  else
2630  {
2631  assert(!any_one_test);
2632  }
2633  if (one_test_cnt)
2634  {
2635  if (!is_int)
2636  {
2637  bool l, r;
2638  if (to < bm::id_max-1)
2639  r = !bv.test(to+1);
2640  else
2641  r = false;
2642  if (from)
2643  l = !bv.test(from-1);
2644  else
2645  l = false;
2646  assert(l==false || r==false);
2647  }
2648  }
2649  }
2650 
2651  // [from-1, to] range check
2652  //
2653  if (from)
2654  {
2655  --from;
2656  one_test = bv.is_all_one_range(from, to);
2657  any_one_test = bv.any_range(from, to);
2658  is_int = bm::is_interval(bv, from, to);
2659  if (all_one)
2660  {
2661  assert(one_test);
2662  assert(any_one_test);
2663  if (is_int)
2664  {
2665  assert(from == 0 || bv.test(from-1) == false);
2666  assert(bv.test(to+1) == false);
2667  }
2668  }
2669  else
2670  {
2671  auto cnt = bv.count_range(from, to);
2672  one_test_cnt = (cnt == to - from + 1);
2673  assert(one_test_cnt == one_test);
2674  if (cnt)
2675  {
2676  assert(any_one_test);
2677  }
2678  else
2679  {
2680  assert(!any_one_test);
2681  }
2682  if (!is_int && one_test_cnt)
2683  {
2684  bool l, r;
2685  if (to < bm::id_max-1)
2686  r = bv.test(to+1);
2687  else
2688  r = false;
2689  if (from)
2690  l = bv.test(from-1);
2691  else
2692  l = false;
2693  assert(l || r);
2694  }
2695 
2696  }
2697  ++from;
2698  }
2699  // [from, to+1] range check
2700  //
2701  if (to < bm::id_max-1)
2702  {
2703  ++to;
2704  one_test = bv.is_all_one_range(from, to);
2705  any_one_test = bv.any_range(from, to);
2706  is_int = bm::is_interval(bv, from, to);
2707  if (all_one)
2708  {
2709  assert(one_test);
2710  assert(any_one_test);
2711  if (is_int)
2712  {
2713  assert(from == 0 || bv.test(from-1) == false);
2714  assert(bv.test(to+1) == false);
2715  }
2716  }
2717  else
2718  {
2719  auto cnt = bv.count_range(from, to);
2720  one_test_cnt = (cnt == to - from + 1);
2721  assert(one_test_cnt == one_test);
2722  if (cnt)
2723  {
2724  assert(any_one_test);
2725  }
2726  else
2727  {
2728  assert(!any_one_test);
2729  }
2730  if (!is_int && one_test_cnt)
2731  {
2732  bool l, r;
2733  if (to < bm::id_max-1)
2734  r = bv.test(to+1);
2735  else
2736  r = false;
2737  if (from)
2738  l = bv.test(from-1);
2739  else
2740  l = false;
2741 
2742  assert(l || r);
2743  }
2744  }
2745  --to;
2746  }
2747  } // for t
2748 }
2749 
2750 static
2752 {
2753  cout << "---------------------------- IsAllOneRangeTest()" << endl;
2754 
2755  cout << "Check empty bvector" << endl;
2756  {{
2757  bvect bv1;
2758  verify_all_one_ranges(bv1, false);
2759  bv1.set(0);
2760  bv1.clear(0);
2761  verify_all_one_ranges(bv1, false);
2762  IntervalsCheck(bv1);
2763  }}
2764 
2765  cout << "Check inverted bvector" << endl;
2766  {{
2767  bvect bv1;
2768  bv1.invert();
2769 
2770  verify_all_one_ranges(bv1, true);
2771  IntervalsCheck(bv1);
2772  }}
2773 
2774  cout << "Check set ranges" << endl;
2775  {{
2776  size_t fr_size = sizeof(from_arr) / sizeof(from_arr[0]);
2777  size_t to_size = sizeof(to_arr) / sizeof(to_arr[0]);
2778  assert(fr_size == to_size);
2779 
2780  for (unsigned t = 0; t < fr_size; ++t)
2781  {
2782  bvect::size_type from(from_arr[t]), to(to_arr[t]);
2783 
2784  {
2785  bvect bv1;
2786  bvect bv2(bm::BM_GAP);
2787 
2788  if (to - from < 65536*10)
2789  {
2790  for (bvect::size_type i = from; i <= to; ++i)
2791  bv1.set(i);
2792  }
2793  else
2794  {
2795  bv1.set_range(from, to);
2796  }
2797  bv2.set_range(from, to);
2798 
2799  bool one_test1 = bv1.is_all_one_range(from, to);
2800  bool one_test2 = bv2.is_all_one_range(from, to);
2801  bool any_one1 = bv1.any_range(from, to);
2802  bool any_one2 = bv2.any_range(from, to);
2803 
2804  assert(one_test1 == one_test2);
2805  assert(any_one1 == any_one2);
2806  auto cnt = bv1.count_range(from, to);
2807  if (any_one1)
2808  {
2809  assert(cnt);
2810  }
2811  else
2812  {
2813  assert(!cnt);
2814  }
2815 
2816  verify_all_one_ranges(bv1, false);
2817  verify_all_one_ranges(bv2, false);
2818 
2819  IntervalsCheck(bv1);
2820  IntervalsCheck(bv2);
2823  }
2824  } // for t
2825 
2826  }}
2827 
2828  cout << "---------------------------- IsAllOneRangeTest() OK" << endl;
2829 }
2830 
2831 
2832 
2833 // -----------------------------------------------------------------------
2834 
2835 static
2836 void optimize_fill(bvect& bv, bvect::size_type base, unsigned inc,
2838  bool value = true)
2839 {
2840  for (bvect::size_type i = 0; i < bm::set_sub_array_size; ++i)
2841  {
2842  bvect::size_type base_idx = i * bm::gap_max_bits;
2843  for (bvect::size_type j = base; j < base+max_bits; j += inc)
2844  {
2845  bv.set(base_idx + j, value);
2846  } // for j
2847  } // for i
2848 }
2849 
2850 static
2852 {
2853  cout << "---------------------------- Bvector Optimize test" << endl;
2855 
2857  {
2858  bvect bv;
2859  optimize_fill(bv, base_idx, 1, bm::gap_max_bits, true);
2860 
2861  bvect::statistics st1;
2862  bv.calc_stat(&st1);
2863 
2865  assert(st1.gap_blocks == 0);
2866  assert(st1.ptr_sub_blocks == 1);
2867 
2868  bv.optimize(tb, bvect::opt_compress, &st1);
2869 
2870  assert(st1.bit_blocks == 0);
2871  assert(st1.gap_blocks == 0);
2872  assert(st1.ptr_sub_blocks == 0);
2873 
2874  bv.calc_stat(&st1);
2875 
2876  assert(st1.bit_blocks == 0);
2877  assert(st1.gap_blocks == 0);
2878  assert(st1.ptr_sub_blocks == 0);
2879  }
2880 
2881  {
2882  bvect bv;
2883  optimize_fill(bv, base_idx, 100, bm::gap_max_bits, true);
2884  optimize_fill(bv, base_idx, 100, bm::gap_max_bits, false);
2885 
2886  bvect::statistics st1;
2887  bv.calc_stat(&st1);
2888 
2890  assert(st1.gap_blocks == 0);
2891  assert(st1.ptr_sub_blocks == 1);
2892 
2893  bv.optimize(tb, bvect::opt_compress, &st1);
2894 
2895  assert(st1.bit_blocks == 0);
2896  assert(st1.gap_blocks == 0);
2897  assert(st1.ptr_sub_blocks == 0);
2898  }
2899 
2900 
2901  {
2902  bvect bv(BM_GAP);
2903  optimize_fill(bv, base_idx, 1, bm::gap_max_bits, true);
2904 
2905  bvect::statistics st1;
2906  bv.calc_stat(&st1);
2907 
2908  assert(st1.bit_blocks == 0);
2910  assert(st1.ptr_sub_blocks == 1);
2911 
2912  bv.optimize(tb, bvect::opt_compress, &st1);
2913 
2914  assert(st1.bit_blocks == 0);
2915  assert(st1.gap_blocks == 0);
2916  assert(st1.ptr_sub_blocks == 0);
2917 
2918  bv.calc_stat(&st1);
2919 
2920  assert(st1.bit_blocks == 0);
2921  assert(st1.gap_blocks == 0);
2922  assert(st1.ptr_sub_blocks == 0);
2923  }
2924 
2925  {
2926  bvect bv(BM_GAP);
2927  optimize_fill(bv, base_idx, 1000, bm::gap_max_bits, true);
2928  optimize_fill(bv, base_idx, 1000, bm::gap_max_bits, false);
2929 
2930  bvect::statistics st1;
2931  bv.calc_stat(&st1);
2932 
2933  assert(st1.bit_blocks == 0);
2935  assert(st1.gaps_by_level[0] == 0);
2937  assert(st1.ptr_sub_blocks == 1);
2938 
2939  bv.optimize(tb, bvect::opt_compress, &st1);
2940 
2941  assert(st1.bit_blocks == 0);
2942  assert(st1.gap_blocks == 0);
2943  assert(st1.ptr_sub_blocks == 0);
2944  }
2945 
2946  {
2947  bvect bv(BM_GAP);
2948  optimize_fill(bv, base_idx+0, 1000, bm::gap_max_bits, true);
2949  optimize_fill(bv, base_idx+1, 1, bm::gap_max_bits, false);
2950 
2951  bvect::statistics st1;
2952  bv.calc_stat(&st1);
2953 
2954  assert(st1.bit_blocks == 0);
2956  assert(st1.gaps_by_level[0] == 0);
2958  assert(st1.ptr_sub_blocks == 1);
2959 
2960  bv.optimize(tb, bvect::opt_compress, &st1);
2961 
2962  assert(st1.bit_blocks == 0);
2963  assert(st1.gap_blocks == 1);
2964  assert(st1.ptr_sub_blocks == 1);
2965  assert(st1.gaps_by_level[0] == 1);
2966  assert(st1.gaps_by_level[1] == 0);
2967  }
2968 
2969 
2970  cout << "---------------------------- Bvector Optimize test OK" << endl;
2971 }
2972 
2973 static
2975 {
2976  cout << "---------------------------- Find Rank test" << endl;
2977 
2979  assert(base_idx > bm::id_max32);
2980 
2981  {
2982  bvect bv1;
2983  bv1[base_idx+30] = true;
2984  bv1[base_idx+65534] = true;
2985 
2986  for (unsigned i = 0; i < 2; ++i)
2987  {
2988  bvect::rs_index_type bc_arr1;
2989  bv1.build_rs_index(&bc_arr1);
2990 
2991  bool rf1, rf2, rf3;
2992  bvect::size_type pos, pos1;
2993  rf1 = bv1.find_rank(1, 20, pos);
2994  rf3 = bv1.find_rank(1, 20, pos1, bc_arr1);
2995  assert(rf1);
2996  assert(rf3);
2997  assert(pos == base_idx+30);
2998  assert(pos1 == base_idx+30);
2999 
3000  rf2 = bv1.find_rank(2, base_idx+30, pos);
3001  rf3 = bv1.find_rank(2, base_idx+30, pos1, bc_arr1);
3002  assert(rf2);
3003  assert(rf3);
3004  assert(pos == base_idx+65534);
3005  assert(pos1 == base_idx+65534);
3006  bv1.optimize();
3007  }
3008  }
3009 
3010  {
3011  bvect bv1;
3012  bv1.set_range(base_idx, bm::id_max-1);
3014  bv1.build_rs_index(&rsi);
3015 
3016  bool rf1, rf3;
3017  bvect::size_type pos, pos1;
3018  rf1 = bv1.find_rank(1, 20, pos);
3019  rf3 = bv1.find_rank(1, 20, pos1, rsi);
3020  assert(rf1);
3021  assert(rf3);
3022  assert(pos == base_idx);
3023  assert(pos1 == base_idx);
3024  }
3025 
3026  cout << "Test bvector<>::select()" << endl;
3027  {
3028  bvect::size_type r(3*65536*256-1), pos;
3029 
3030  bvect bv;
3031  bv.invert();
3032  bv.optimize();
3033 
3034  bvect::rs_index_type rs_idx;
3035  bv.build_rs_index(&rs_idx);
3036 
3038  for (i = 0; i <= r; ++i)
3039  {
3040  bvect::size_type ri = bv.rank(i, rs_idx);
3041  assert(ri == (i+1));
3042  bool f = bv.select(ri, pos, rs_idx);
3043  assert(f);
3044  assert(pos == i);
3045  }
3046  }
3047 
3048 
3049  cout << "Find Rank test stress 1\n" << endl;
3050 
3051  {
3052  const bvect::size_type max_size = base_idx+200000;
3053  const bvect::size_type min_size = base_idx-20000;
3054  bvect bv1;
3055  for (bvect::size_type i = base_idx; i < max_size; i += (unsigned)rand()%5)
3056  {
3057  bv1.set(i);
3058  }
3059  bvect::rs_index_type bc_arr1;
3060  bv1.build_rs_index(&bc_arr1);
3061 
3062 
3063  for (bvect::size_type i = max_size; i > min_size; --i)
3064  {
3065  bool rf1, rf3;
3066  bvect::size_type pos, pos1;
3067 
3068  rf1 = bv1.find_rank(0, i, pos);
3069  rf3 = bv1.find_rank(0, i, pos1, bc_arr1);
3070  assert (rf1 == rf3);
3071  if (rf1)
3072  {
3073  if (pos != pos1)
3074  {
3075  cerr << "Rank cmp test failed! i=" << i
3076  << " pos=" << pos
3077  << " pos1=" << pos1
3078  << endl;
3079  exit(1);
3080  }
3081  }
3082 
3083  rf1 = bv1.find_rank(i, max_size-i, pos);
3084  rf3 = bv1.find_rank(i, max_size-i, pos1, bc_arr1);
3085  assert (rf1 == rf3);
3086  if (rf1)
3087  {
3088  if (pos != pos1)
3089  {
3090  cerr << "Rank cmp test failed! i=" << i
3091  << " pos=" << pos
3092  << " pos1=" << pos1
3093  << endl;
3094  exit(1);
3095  }
3096  }
3097  if ((i & 0xFFFFULL) == 0)
3098  cout << "\r" << i << "/" << max_size << flush;
3099  } // for
3100  cout << endl;
3101  }
3102 
3103  cout << "---------------------------- Find Rank test OK" << endl;
3104 }
3105 
3106 extern "C" {
3107  static
3108  int bit_decode_func(void* handle_ptr, bm::id64_t bit_idx)
3109  {
3110  std::vector<bvect::size_type>* vp = (std::vector<bvect::size_type>*)handle_ptr;
3111  vp->push_back(bit_idx);
3112  return 0;
3113  }
3114 
3115  static
3116  int bit_decode_func2(void* /*handle_ptr*/, bm::id64_t bit_idx)
3117  {
3118  static bm::id64_t prev = 0;
3119  if (bit_idx <= prev)
3120  {
3121  if (prev)
3122  {
3123  cerr << "Incorrect loading sequence prev=" << prev <<
3124  " next=" << bit_idx << endl;
3125  assert(0); exit(1);
3126  }
3127  }
3128  else
3129  {
3130  assert(prev+1 == bit_idx);
3131  }
3132 
3133  const id64_t limit = 65536ULL * 256 * 2ULL;
3134  if (bit_idx > limit)
3135  {
3136  return -1;
3137  }
3138  /*
3139  std::vector<bvect::size_type>* vp = (std::vector<bvect::size_type>*)handle_ptr;
3140  vp->push_back(bit_idx);
3141  */
3142  prev = bit_idx;
3143  return 0;
3144  }
3145 } // extern C
3146 
3147 template<class BV>
3148 void VisitorAllRangeTest(const BV& bv, typename BV::size_type step)
3149 {
3150  cout << ".... VisitorAllRangeTest()";
3151 
3152  typename BV::size_type left, right, next, i_end;
3153  bool non_empty = bv.find_range(left, right);
3154  if (!non_empty)
3155  return;
3156 
3157  auto drange = right - left;
3158  if (!drange)
3159  drange = 256;
3160  if (!step)
3161  {
3162  unsigned factor = (unsigned)rand()%32;
3163  if (!factor) factor = 10;
3164  step = drange / factor;
3165  }
3166  if (!step)
3167  step = 1;
3168  cout << " step=" << step << endl;
3169 
3170 
3171  auto pcnt = 4;
3172  for (auto i = left; i <= right; i+=step, right-=step)
3173  {
3174  {
3175  bvect bv_control;
3176  bm::bit_vistor_copy_functor<bvect> func(bv_control);
3177  bm::for_each_bit_range(bv, i, right, func);
3178 
3179  bvect bv2;
3180  bv2.copy_range(bv, i, right);
3181 
3182  bool eq = bv2.equal(bv_control);
3183  assert(eq);
3184  }
3185  next = bv.get_next(i);
3186  if (next)
3187  {
3188  auto delta = next - i;
3189  if (delta > 32)
3190  {
3191  i += delta / 2;
3192  }
3193  else
3194  if (delta == 1)
3195  {
3196  bool f = bm::find_interval_end(bv, next, i_end);
3197  if (f)
3198  {
3199  delta = i_end - i;
3200  if (delta > 4)
3201  i += delta / 2;
3202  }
3203  else
3204  {
3205  assert(!bv.test(i));
3206  }
3207  }
3208  }
3209  if (!pcnt)
3210  {
3211  cout << "\r" << i << " / " << right << flush;
3212  pcnt = 4;
3213  }
3214  --pcnt;
3215 
3216  } // for i
3217  cout << endl;
3218 /*
3219  pcnt = 4;
3220  for (; left <= right; left+=step, --right)
3221  {
3222  {
3223  bvect bv_control;
3224  bm::bit_vistor_copy_functor<bvect> func(bv_control);
3225  bm::for_each_bit_range(bv, left, right, func);
3226 
3227  bvect bv2;
3228  bv2.copy_range(bv, left, right);
3229 
3230  bool eq = bv2.equal(bv_control);
3231  assert(eq);
3232  }
3233  next = bv.get_next(left);
3234  if (next)
3235  {
3236  auto delta = next - left;
3237  if (delta > 128)
3238  {
3239  left += delta / 2;
3240  }
3241  else
3242  if (delta == 1)
3243  {
3244  bool f = bv.find_interval_end(left, i_end);
3245  if (f)
3246  {
3247  delta = i_end - left;
3248  if (delta > 4)
3249  left += delta / 2;
3250  }
3251  }
3252  }
3253  if (!pcnt)
3254  {
3255  cout << "\r" << left << " / " << right << flush;
3256  pcnt = 4;
3257  }
3258  --pcnt;
3259  } // for i
3260  */
3261  cout << endl;
3262 }
3263 
3264 
3265 
3266 static
3268 {
3269  bvect bv;
3270  bv.set_range(from, to);
3271  std::vector<bvect::size_type> v;
3272  bm::visit_each_bit(bv, (void*)&v, bit_decode_func);
3273 
3274  assert(v.size() == bv.count());
3275  assert(v[0] == from);
3276 
3277  for (size_t i = 1; i < v.size(); ++i)
3278  {
3279  bvect::size_type prev = v[i-1];
3280  bvect::size_type curr = v[i];
3281  assert(prev+1 == curr);
3282  }
3283  bvect bv_control;
3284  bm::combine_or(bv_control, v.begin(), v.end());
3285  int res = bv.compare(bv_control);
3286  assert(res == 0);
3287 }
3288 
3289 static
3291 {
3292  cout << "------------------------ bvector BitForEach Test" << endl;
3293  int res;
3294 
3295  {
3296  cout << "test empty vector" << endl;
3297  bvect bv1;
3298  std::vector<bvect::size_type> v1;
3299 
3300  bm::visit_each_bit(bv1, (void*)&v1, bit_decode_func);
3301  if (v1.size())
3302  {
3303  cerr << "1. Failed empty vector decode " << v1.size() << endl;
3304  exit(1);
3305  }
3306  bv1.init();
3307  bm::visit_each_bit(bv1, (void*)&v1, bit_decode_func);
3308  if (v1.size())
3309  {
3310  cerr << "2. Failed empty vector decode " << v1.size() << endl;
3311  exit(1);
3312  }
3313 
3314  bv1.set(bm::id_max-1, true);
3315  bv1.set(bm::id_max-1, false);
3316 
3317  bm::visit_each_bit(bv1, (void*)&v1, bit_decode_func);
3318  if (v1.size())
3319  {
3320  cerr << "3. Failed empty vector decode " << v1.size() << endl;
3321  exit(1);
3322  }
3323 
3324  bv1.optimize();
3325  bm::visit_each_bit(bv1, (void*)&v1, bit_decode_func);
3326  if (v1.size())
3327  {
3328  cerr << "3. Failed empty vector decode " << v1.size() << endl;
3329  exit(1);
3330  }
3331  }
3332 
3333  {
3334  bvect bv1 { 0,1,2, 10, 32, 100, 65535,
3335  65535+1, 65535+2, 65535+10, 65535+11, 65535+31,
3336  20000000, bm::id_max-1 };
3337  bvect bv2;
3338  std::vector<bvect::size_type> v1;
3339 
3340  bm::visit_each_bit(bv1, (void*)&v1, bit_decode_func);
3341 
3342  {
3343  for (size_t i = 0; i < v1.size(); ++i)
3344  cout << v1[i] << ", ";
3345  cout << endl;
3346  }
3347 
3348  if (v1.size() != bv1.count())
3349  {
3350  std::cerr << "0. Bit for each failed size test. " << v1.size()
3351  << " should be " << bv1.count() << std::endl;
3352  exit(1);
3353  }
3354  bm::combine_or(bv2, v1.begin(), v1.end());
3355 
3356  res = bv2.compare(bv1);
3357  if (res != 0)
3358  {
3359  std::cerr << "0. Bit for each failed comparison test. " << endl;
3360  exit(1);
3361  }
3362 
3363  bv1.optimize();
3364  bv2.reset();
3365  v1.resize(0);
3366  bm::visit_each_bit(bv1, (void*)&v1, bit_decode_func);
3367 
3368  {
3369  for (size_t i = 0; i < v1.size(); ++i)
3370  cout << v1[i] << ", ";
3371  cout << endl;
3372  }
3373 
3374  if (v1.size() != bv1.count())
3375  {
3376  std::cerr << "1. Bit for each failed size test. " << v1.size()
3377  << " should be " << bv1.count() << std::endl;
3378  exit(1);
3379  }
3380  bm::combine_or(bv2, v1.begin(), v1.end());
3381 
3382  res = bv2.compare(bv1);
3383  if (res != 0)
3384  {
3385  std::cerr << "1. Bit for each failed comparison test. " << endl;
3386  exit(1);
3387  }
3388  }
3389 
3390 
3391 
3392  {
3393  bvect bv1, bv2;
3394  std::vector<bvect::size_type> v1;
3395 
3396  generate_bvector(bv1, bm::id_max32/4, false);
3397  v1.reserve(bv1.count());
3398 
3399  bm::visit_each_bit(bv1, (void*)&v1, bit_decode_func);
3400 
3401  if (v1.size() != bv1.count())
3402  {
3403  std::cerr << "Bit for each failed size test. " << v1.size()
3404  << " should be " << bv1.count() << std::endl;
3405  exit(1);
3406  }
3407  bm::combine_or(bv2, v1.begin(), v1.end());
3408 
3409  res = bv2.compare(bv1);
3410  if (res != 0)
3411  {
3412  std::cerr << "Bit for each failed comparison test. " << endl;
3413  exit(1);
3414  }
3415 
3416  cout << "for each bit in optimized bit-vector..." << endl;
3417 
3418  v1.resize(0);
3419  bv2.clear(true);
3420  bv1.optimize();
3421 
3422  bm::visit_each_bit(bv1, (void*)&v1, bit_decode_func);
3423 
3424  if (v1.size() != bv1.count())
3425  {
3426  std::cerr << "Bit for each failed size test. " << v1.size()
3427  << " should be " << bv1.count() << std::endl;
3428  exit(1);
3429  }
3430  bm::combine_or(bv2, v1.begin(), v1.end());
3431 
3432  res = bv2.compare(bv1);
3433  if (res != 0)
3434  {
3435  std::cerr << "Bit for each failed comparison test. " << endl;
3436  exit(1);
3437  }
3438  }
3439 
3440  {
3441  RangeForEachTest(0, 65536);
3442  RangeForEachTest(65536, 65536+65536);
3443  RangeForEachTest(bm::id_max/2, bm::id_max/2 + (65536*256));
3444  }
3445 
3446  {
3447  bvect bv;
3448  bv.set();
3449 
3450  std::vector<bvect::size_type> v1;
3451  try
3452  {
3453  bm::visit_each_bit(bv, (void*)&v1, bit_decode_func2);
3454  } catch (...)
3455  {
3456  }
3457  }
3458 
3459  cout << "------------------------ bvector BitForEach Test OK" << endl;
3460 }
3461 
3462 static
3464 {
3465  cout << "-------------------------------------------- GetNextTest()" << endl;
3466 
3467  cout << "testing bvector<>::find() in bit-mode" << endl;
3468 
3469  {
3470  bvect bv;
3471  bv.set();
3472  bvect::size_type pos=1;
3473  bool b;
3474  b = bv.find(pos);
3475  assert(pos == 0);
3476  assert(b);
3477 
3478  b = bv.find(bm::id_max/2, pos);
3479  assert(b);
3480  assert(pos == bm::id_max/2);
3481 
3482  bv.set(bm::id_max/2, false);
3483  b = bv.find(bm::id_max/2, pos);
3484  assert(b);
3485  assert(pos == bm::id_max/2 + 1);
3486 
3487  b = bv.find_reverse(pos);
3488  assert(b);
3489  assert(pos == bm::id_max-1);
3490 
3491  bvect::size_type f, l;
3492  b = bv.find_range(f, l);
3493  assert(b);
3494  assert(f == 0);
3495  assert(l == bm::id_max-1);
3496  }
3497 
3498  {
3499  bvect bv;
3500  bool found;
3501  bvect::size_type pos;
3502  found = bv.find(0, pos);
3503 
3504  if (found)
3505  {
3506  cout << "1. find() failed" << endl;
3507  exit(1);
3508  }
3509  found = bv.find_reverse(pos);
3510  assert(!found);
3511 
3512  bv[0] = true;
3513  found = bv.find(0, pos);
3514  if (!found || pos != 0)
3515  {
3516  cout << "2. find() failed " << pos << endl;
3517  exit(1);
3518  }
3519  found = bv.find_reverse(pos);
3520  assert(found && pos == 0);
3521 
3522  bv[0] = false;
3523  found = bv.find_reverse(pos);
3524  assert(!found);
3525  bv[0] = true;
3526 
3527  found = bv.find(1, pos);
3528  if (found)
3529  {
3530  cout << "3. find() failed" << endl;
3531  exit(1);
3532  }
3533 
3534  bv[100000] = true;
3535  bv[100001] = true;
3536  found = bv.find(1, pos);
3537  if (!found || pos != 100000)
3538  {
3539  cout << "4. find() failed " << pos << " " << found << endl;
3540  exit(1);
3541  }
3542  found = bv.find_reverse(pos);
3543  assert(found && pos == 100001);
3544 
3545  found = bv.find(100000, pos);
3546  if (!found || pos != 100000)
3547  {
3548  cout << "5. find() failed " << pos << " " << found << endl;
3549  exit(1);
3550  }
3551  found = bv.find(100001, pos);
3552  if (!found || pos != 100001)
3553  {
3554  cout << "6. find() failed " << pos << " " << found << endl;
3555  exit(1);
3556  }
3557  found = bv.find(100002, pos);
3558  if (found)
3559  {
3560  cout << "7. find() failed "<< endl;
3561  exit(1);
3562  }
3563  bv[100001] = false;
3564  found = bv.find_reverse(pos);
3565  assert(found && pos == 100000);
3566  }
3567 
3568  cout << "testing bvector<>::find() in GAP-mode" << endl;
3569 
3570  {
3571  bvect bv(BM_GAP);
3572  bool found;
3573  bvect::size_type pos;
3574  bvect::size_type from;
3575  from = bm::id_max / 2;
3576 
3577  found = bv.find(0, pos);
3578  if (found)
3579  {
3580  cout << "1. find() failed" << endl;
3581  exit(1);
3582  }
3583  found = bv.find_reverse(pos);
3584  assert(!found);
3585 
3586  bv[0] = true;
3587  found = bv.find(0, pos);
3588  if (!found || pos != 0)
3589  {
3590  cout << "2. find() failed " << pos << endl;
3591  exit(1);
3592  }
3593  found = bv.find_reverse(pos);
3594  assert(found && pos == 0);
3595 
3596  found = bv.find(1, pos);
3597  if (found)
3598  {
3599  cout << "3. find() failed" << endl;
3600  exit(1);
3601  }
3602  bv[from] = true;
3603  bv[from+1] = true;
3604  found = bv.find(1, pos);
3605  if (!found || pos != from)
3606  {
3607  cout << "4. find() failed " << pos << " " << found << endl;
3608  exit(1);
3609  }
3610  found = bv.find(from, pos);
3611  if (!found || pos != from)
3612  {
3613  cout << "5. find() failed " << pos << " " << found << endl;
3614  exit(1);
3615  }
3616  found = bv.find(from+1, pos);
3617  if (!found || pos != from+1)
3618  {
3619  cout << "6. find() failed " << pos << " " << found << endl;
3620  exit(1);
3621  }
3622  found = bv.find_reverse(pos);
3623  assert(found && pos == from+1);
3624 
3625  found = bv.find(from+2, pos);
3626  if (found)
3627  {
3628  cout << "7. find() failed "<< endl;
3629  exit(1);
3630  }
3631  bv[from+1] = false;
3632  found = bv.find_reverse(pos);
3633  assert(found && pos == from);
3634 
3635 
3636  }
3637 
3638  {
3639  bvect bv;
3640  bool found;
3641  bvect::size_type from, to;
3642  from = bm::id_max / 2;
3643  to = from + 20000000;
3644 
3645  bv.set_range(from, to);
3646  bvect::size_type pos;
3647  found = bv.find_reverse(pos);
3648  assert(found && pos == to);
3649 
3650  bv.optimize();
3651  found = bv.find_reverse(pos);
3652  assert(found && pos == to);
3653 
3654  bv[bm::id_max-1] = true;
3655  found = bv.find_reverse(pos);
3656  assert(found && pos == bm::id_max-1);
3657 
3658  bv[bm::id_max-1] = false;
3659  found = bv.find_reverse(pos);
3660  assert(found && pos == to);
3661 
3662  bv.set_range(from, to, false);
3663  found = bv.find_reverse(pos);
3664  assert(!found);
3665 
3666  found = bv.find(0, pos);
3667  assert(!found);
3668  }
3669 
3670  {
3671  bvect bv;
3672  bool found;
3673  bvect::size_type pos;
3674  bv.invert();
3675 
3676  found = bv.find_reverse(pos);
3677  assert(found && pos == bm::id_max-1);
3678 
3679  bv.optimize();
3680  found = bv.find_reverse(pos);
3681  assert(found && pos == bm::id_max-1);
3682 
3683  bv.invert();
3684  found = bv.find_reverse(pos);
3685  assert(!found);
3686  found = bv.find(0, pos);
3687  assert(!found);
3688  }
3689 
3690  const bvect::size_type BITVECT_SIZE = bvect::size_type(bm::id_max32)+100; //100000000 * 2;
3691 
3692  int i;
3693  for(i = 0; i < 2; ++i)
3694  {
3695  cout << "Strategy " << i << endl;
3696 
3697  {
3698  bvect bvect_full1;
3699  bvect_mini bvect_min1(BITVECT_SIZE);
3700 
3701  bvect_full1.set_new_blocks_strat(i ? bm::BM_GAP : bm::BM_BIT);
3702 
3703  bvect_full1.set_bit(0);
3704  bvect_min1.set_bit(0);
3705 
3706 
3707  bvect_full1.set_bit(BITVECT_SIZE-1);
3708  bvect_min1.set_bit(BITVECT_SIZE-1);
3709 
3710  auto nbit1 = bvect_full1.get_first();
3711  auto nbit2 = bvect_min1.get_first();
3712 
3713  if (nbit1 != nbit2)
3714  {
3715  cout << "1. get_first failed() " << nbit1 << " " << nbit2 << endl;
3716  exit(1);
3717  }
3718  nbit1 = bvect_full1.get_next(nbit1);
3719  nbit2 = bvect_min1.get_next(nbit2);
3720  if ((nbit1 != nbit2) || (nbit1 != BITVECT_SIZE-1))
3721  {
3722  cout << "2. get_next failed() " << nbit1 << " " << nbit2 << endl;
3723  exit(1);
3724  }
3725  }
3726 
3727 
3728  {
3729  bvect bvect_full1;
3730  bvect_mini bvect_min1(BITVECT_SIZE);
3731 
3732  bvect_full1.set_new_blocks_strat(i ? bm::BM_GAP : bm::BM_BIT);
3733 
3734  bvect_full1.set_bit(256);
3735  bvect_min1.set_bit(256);
3736 
3737  bvect_full1.set_bit(BITVECT_SIZE-65536);
3738  bvect_min1.set_bit(BITVECT_SIZE-65536);
3739 
3740  bvect::size_type nbit1 = bvect_full1.get_first();
3741  bvect::size_type nbit2 = bvect_min1.get_first();
3742 
3743  if (nbit1 != nbit2)
3744  {
3745  cout << "get_first failed " << nbit1 << " " << nbit2 << endl;
3746  exit(1);
3747  }
3748 
3749  bvect::size_type last_found = 0;
3750  while (nbit1)
3751  {
3752  cout << nbit1 << endl;
3753  nbit1 = bvect_full1.get_next(nbit1);
3754  nbit2 = bvect_min1.get_next(nbit2);
3755  if (nbit1 != nbit2)
3756  {
3757  cout << "get_next failed " << nbit1 << " " << nbit2 << endl;
3758  exit(1);
3759  }
3760  if (nbit1)
3761  last_found = nbit1;
3762  } // while
3763 
3764  bvect::size_type pos = 0;
3765  bool found = bvect_full1.find_reverse(pos);
3766  assert(found && pos == last_found);
3767  }
3768 
3769  }// for
3770 
3771  cout << "-------------------------------------------- GetNextTest()" << endl;
3772 
3773 }
3774 
3775 static
3777 {
3778  cout << "---------------------------- Bvector inc test" << endl;
3781 
3782 
3783 
3784  {
3785  bvect bv1;
3786  bool b;
3787 
3788  b = bv1.inc(pos1);
3789  assert(!b);
3790  assert(bv1.count()==1);
3791  b = bv1.inc(pos1);
3792  assert(b);
3793  assert(bv1.count()==0);
3794 
3795  b = bv1.inc(pos2);
3796  assert(!b);
3797  assert(bv1.count()==1);
3798  b = bv1.inc(pos2);
3799  assert(b);
3800  assert(bv1.count()==0);
3801  }
3802 
3803  {
3804  bvect bv1(BM_GAP);
3805  bool b;
3806 
3807  assert(bv1.count()==0);
3808 
3809  b = bv1.inc(pos1);
3810  assert(!b);
3811  cout << bv1.count() << endl;
3812  assert(bv1.count()==1);
3813  b = bv1.inc(pos1);
3814  assert(b);
3815  assert(bv1.count()==0);
3816 
3817  b = bv1.inc(pos2);
3818  assert(!b);
3819  b = bv1.inc(pos2);
3820  assert(b);
3821  }
3822 
3823  {
3824  bvect bv1(BM_GAP);
3825  bool b;
3826 
3827  bv1.flip();
3828 
3829  b = bv1.inc(pos1);
3830  assert(b);
3831  b = bv1.inc(pos1);
3832  assert(!b);
3833 
3834  b = bv1.inc(pos2);
3835  assert(b);
3836  b = bv1.inc(pos2);
3837  assert(!b);
3838  }
3839 
3840  cout << "---------------------------- Bvector inc test OK" << endl;
3841 }
3842 
3843 template<class BV>
3844 void DetailedCompareBVectors(const BV& bv1, const BV& bv2)
3845 {
3846  bvect::counted_enumerator en1 = bv1.first();
3847  bvect::counted_enumerator en2 = bv2.first();
3848 
3849  for (; en1.valid(); ++en1)
3850  {
3851  assert(en2.valid());
3852 
3853  auto i1 = *en1;
3854  auto i2 = *en2;
3855 
3856  if (i1 != i2)
3857  {
3858  auto nb1 = (i1 >> bm::set_block_shift);
3859  auto nb2 = (i2 >> bm::set_block_shift);
3860  auto ii1 = nb1 >> bm::set_array_shift;
3861  auto jj1 = nb1 & bm::set_array_mask;
3862  auto ii2 = nb2 >> bm::set_array_shift;
3863  auto jj2 = nb2 & bm::set_array_mask;
3864 
3865  std::cerr << "Difference detected at: position="
3866  << i1 << " nb=" << nb1
3867  << "[" << ii1 << ", " << jj1 << "]"
3868  " other position = " << i2 <<
3869  " nb=" << nb2
3870  << "[" << ii2 << ", " << jj2 << "]"
3871  << std::endl;
3872  std::cerr << " en1.count()=" << en1.count() << " en2.count()=" << en2.count()
3873  << std::endl;
3874 
3875  exit(1);
3876  return;
3877  }
3878  ++en2;
3879  } // for
3880 
3881  int cmp = bv1.compare(bv2);
3882  if (cmp != 0)
3883  {
3884  cerr << "Compare (1-2) discrepancy! " << cmp << endl;
3885  }
3886  cmp = bv2.compare(bv1);
3887  if (cmp != 0)
3888  {
3889  cerr << "Compare (2-1) discrepancy! " << cmp << endl;
3890  }
3891 
3892  cout << "Detailed compare OK (no difference)." << endl;
3893 }
3894 
3895 
3896 
3897 static
3899 {
3900  cout << "---------------------------- Bvector BULK set test" << endl;
3901  {
3902  bvect::size_type ids[] = { 0 };
3903  bvect bv1, bv2, bv3;
3904  {
3906  for (unsigned i = 0; i < sizeof(ids)/sizeof(ids[0]); ++i)
3907  {
3908  bv1.set(ids[i]);
3909  iit = ids[i];
3910  }
3911  }
3912  bv2.set(&ids[0], sizeof(ids)/sizeof(ids[0]));
3913 
3914  int cmp = bv1.compare(bv2);
3915  assert(cmp==0);
3916  cmp = bv1.compare(bv3);
3917  assert(cmp==0);
3918 
3919  bv2.set(0);
3920  bv2.keep(&ids[0], sizeof(ids)/sizeof(ids[0]));
3921  assert(bv2.count()==1);
3922  assert(bv2.test(0));
3923  }
3924  {
3925  bvect::size_type ids[] = {65535, bm::id_max-1 };
3927  bvect bv2;
3928  bv2.set(&ids[0], sizeof(ids)/sizeof(ids[0]));
3929 
3930  cnt = bv2.count();
3931  cout << cnt << endl;
3932 
3933  assert(cnt == sizeof(ids)/sizeof(ids[0]));
3934  assert(bv2.test(ids[0]));
3935  assert(bv2.test(ids[1]));
3936  }
3937 
3938  // set bits in FULL vector
3939  {
3940  bvect::size_type ids[] = {0, 10, 65535, bm::id_max-1, bm::id_max-2 };
3942  bvect bv2;
3943  bv2.invert();
3944  struct bvect::statistics st1, st2;
3945  bv2.calc_stat(&st1);
3946 
3947  bv2.set(&ids[0], sizeof(ids)/sizeof(ids[0]));
3948 
3949  bv2.calc_stat(&st2);
3950  assert(st1.bit_blocks == st2.bit_blocks);
3951  assert(st1.gap_blocks == st2.gap_blocks);
3952 
3953  cnt = bv2.count();
3954 
3955  assert(cnt == bm::id_max);
3956  }
3957 
3958  // test correct sizing
3959  {
3960  bvect::size_type ids[] = {bm::id_max32+100 };
3961  bvect bv1;
3962  bv1.resize(10);
3963 
3964  bv1.set(&ids[0], sizeof(ids)/sizeof(ids[0]));
3965  assert(bv1.size()==bm::id_max32+100+1);
3966  bv1.keep(&ids[0], sizeof(ids)/sizeof(ids[0]));
3967  cout << bv1.size() << endl;
3968  assert(bv1.size()==bm::id_max32+100+1);
3969  assert(bv1.count()==sizeof(ids)/sizeof(ids[0]));
3970  }
3971 
3972  {
3973  bvect::size_type ids[] = {65536, bm::id_max-1, 65535 };
3974  bvect bv1, bv2;
3975 
3976  for (size_t i = 0; i < sizeof(ids)/sizeof(ids[0]); ++i)
3977  bv1.set(ids[i]);
3978 
3979  bv2.set(&ids[0], sizeof(ids)/sizeof(ids[0]));
3980  int cmp = bv1.compare(bv2);
3981  assert(cmp==0);
3982 
3983  bv2.keep(&ids[0], sizeof(ids)/sizeof(ids[0]));
3984  cmp = bv1.compare(bv2);
3985  assert(cmp==0);
3986  }
3987 
3988  {
3989  bvect::size_type ids[] =
3990  { 0, 1, 2, 3, 4, 5, 256, 1024, 1028, 256000, bm::id_max-100 };
3991 
3992  bvect bv1, bv2;
3993  for (unsigned i = 0; i < sizeof(ids)/sizeof(ids[0]); ++i)
3994  bv1.set(ids[i]);
3995  bv2.set(&ids[0], sizeof(ids)/sizeof(ids[0]));
3996 
3997  DetailedCompareBVectors(bv1, bv2);
3998 
3999  int cmp = bv1.compare(bv2);
4000  assert(cmp==0);
4001 
4002  {
4003  bvect bv_inv;
4004  bv_inv.flip();
4005  bvect::size_type keep_cnt = sizeof(ids)/sizeof(ids[0]);
4006  bv_inv.keep(&ids[0], keep_cnt, bm::BM_SORTED);
4007  auto cnt_inv2 = bv_inv.count();
4008  assert(cnt_inv2 == keep_cnt);
4009  for (unsigned i = 0; i < sizeof(ids)/sizeof(ids[0]); ++i)
4010  {
4011  assert(bv_inv.test(ids[i]));
4012  }
4013  }
4014 
4015  bvect bv3, bv4, bv5;
4016  bv3.invert();
4017  bv4.invert();
4018  bv5.invert();
4019 
4020  {
4022  for (unsigned i = 0; i < sizeof(ids)/sizeof(ids[0]); ++i)
4023  {
4024  bv3.set(ids[i]);
4025  iit = ids[i];
4026  }
4027  }
4028  bv4.set(&ids[0], sizeof(ids)/sizeof(ids[0]));
4029  cmp = bv3.compare(bv4);
4030  assert(cmp==0);
4031  cmp = bv4.compare(bv3);
4032  assert(cmp==0);
4033 
4034  cmp = bv3.compare(bv5);
4035  assert(cmp==0);
4036  }
4037 
4038  bvect::size_type vector_from = bvect::size_type(bm::id_max32) - 18*65536;
4039  bvect::size_type vector_to = bvect::size_type(bm::id_max32) + 128*65536;
4040 
4041  cout << "bvector-set volume test 1" << endl;
4042  {
4043  std::vector<bvect::size_type> v1, v2, v3;
4044  generate_test_vectors(v1, v2, v3, vector_from, vector_to);
4045 
4046  for (unsigned k = 0; k < 2; ++ k)
4047  {
4048  bvect bvu, bvuc;
4049  bvect bv1, bv2, bv3, bv11;
4050  bvect bv1c, bv2c, bv3c;
4051 
4052  {
4053  bvect::bulk_insert_iterator iit(bv11);
4054  for (bvect::size_type i = 0; i < v1.size(); ++i)
4055  {
4056  bv1c.set(v1[i]);
4057  iit = v1[i];
4058  }
4059  iit.flush();
4060  }
4061 
4062  for (bvect::size_type i = 0; i < v2.size(); ++i)
4063  bv2c.set(v2[i]);
4064  for (bvect::size_type i = 0; i < v3.size(); ++i)
4065  bv3c.set(v3[i]);
4066 
4067  // union of 3 vectors
4068  bvuc = bv1c;
4069  bvuc |= bv2c;
4070  bvuc |= bv3c;
4071 
4072  bv1.set(&v1[0], bvect::size_type(v1.size()));
4073  bv2.set(&v2[0], bvect::size_type(v2.size()));
4074  bv3.set(&v3[0], bvect::size_type(v3.size()));
4075 
4076  // imported union of 3 vectors
4077  bvu.set(&v1[0], bvect::size_type(v1.size()));
4078  bvu.set(&v2[0], bvect::size_type(v2.size()));
4079  bvu.set(&v3[0], bvect::size_type(v3.size()));
4080 
4081  cout << bv1.count() << " " << bv1c.count() << endl;
4082 
4083  int cmp;
4084  cmp = bv1c.compare(bv1);
4085  if (cmp != 0)
4086  {
4087  DetailedCompareBVectors(bv1, bv1c);
4088  }
4089  assert(cmp==0);
4090  cmp = bv2c.compare(bv2);
4091  assert(cmp==0);
4092  cmp = bv3c.compare(bv3);
4093  assert(cmp==0);
4094  cmp = bv1.compare(bv11);
4095  assert(cmp==0);
4096 
4097  cmp = bvuc.compare(bvu);
4098  assert(cmp == 0);
4099 
4100  {
4101  std::random_device rd;
4102  std::mt19937 g(rd());
4103 
4104  std::shuffle(v1.begin(), v1.end(), g);
4105  std::shuffle(v2.begin(), v2.end(), g);
4106  std::shuffle(v3.begin(), v3.end(), g);
4107  }
4108  }
4109 
4110  }
4111 
4112  cout << "Bulk bvector<>::set() stress.." << endl;
4113  {
4114  assert(vector_from < vector_to);
4115  unsigned delta_max = 65537;
4116 
4117  bvect bv1, bv2;
4118  bvect bv1c;
4119  std::vector<bvect::size_type> v1;
4120 
4121  for (unsigned delta = 1; delta < delta_max; ++delta)
4122  {
4123  v1.resize(0);
4124  bvect::bulk_insert_iterator iit(bv2);
4125  for (bvect::size_type i = vector_from; i < vector_to; i+=delta)
4126  {
4127  v1.push_back(i);
4128  iit = i;
4129  }
4130  iit.flush();
4131 
4132  bv1.set(&v1[0], bvect::size_type(v1.size()));
4133  bm::combine_or(bv1c, v1.begin(), v1.end());
4134 
4135  int cmp = bv1.compare(bv1c);
4136  if (cmp!=0)
4137  {
4138  cerr << "1.Failed bulk set test at delta=" << delta << endl;
4139  exit(1);
4140  }
4141  cmp = bv1.compare(bv2);
4142  if (cmp!=0)
4143  {
4144  cerr << "2.Failed bulk set test at delta=" << delta << endl;
4145  exit(1);
4146  }
4147 
4148  // test AND/keep
4149  {
4150  bvect bv3(bv1);
4151  bvect bv4;
4152  bv3.keep(&v1[0], bvect::size_type(v1.size()));
4153  bv4.set(&v1[0], bvect::size_type(v1.size()));
4154  cmp = bv3.compare(bv4);
4155  if (cmp!=0)
4156  {
4157  cerr << "3.Failed keep() test at delta=" << delta << endl;
4158  exit(1);
4159  }
4160  if (v1.size())
4161  {
4162  bv3.keep(&v1[0], 1);
4163  assert(bv3.count()==1);
4164  assert(bv3.test(v1[0]));
4165  }
4166  }
4167  bv1.clear();
4168  bv1c.clear();
4169  bv2.clear();
4170 
4171  //if ((delta & 0xFF) == 0)
4172  cout << "\r" << delta << "/" << delta_max << flush;
4173  if (delta < 128)
4174  delta++;
4175  else
4176  delta += delta / 2;
4177 
4178  } // for delta
4179  cout << endl;
4180  }
4181 
4182 
4183  cout << "---------------------------- Bvector BULK set test OK" << endl;
4184 }
4185 
4186 static
4188 {
4189  cout << "----------------------------------- GAP test stress " << endl;
4190  const bvect::size_type from = bvect::size_type(bm::id_max32)-65536;
4191  const bvect::size_type to = bvect::size_type(bm::id_max32)+65536*256;
4192  assert(from < to);
4193 
4194  unsigned ff_to = 65536*256;
4195  for (unsigned ff = 64; ff < ff_to; )
4196  {
4197  bvect bv0, bv1;
4198  SimpleGapFillSets(bv0, bv1, from, to, ff);
4199  bv1.optimize();
4200  for (bvect::size_type i = from; i < to+1; ++i)
4201  {
4202  bool b0 = bv0.test(i);
4203  bool b1 = bv1.test(i);
4204  if (b0 != b1)
4205  {
4206  cerr << "GAP Test Stress failure!" << " FillFactor=" << ff << " bit=" << i << endl;
4207  assert(0);
4208  exit(1);
4209  }
4210  } // for i
4211  //if ((ff & 0xFF) == 0)
4212  {
4213  cout << "\r" << ff << "/" << ff_to << flush;
4214  }
4215  if (ff <= 64)
4216  ++ff;
4217  else
4218  ff += (ff / 2);
4219  } // for j
4220 
4221  cout << "\n----------------------------------- GAP test stress " << endl;
4222 }
4223 
4224 
4225 // -----------------------------------------------------------------------
4226 
4227 static
4229 {
4230  bvect bv_subset;
4231  bvect::size_type bcnt = bv.count();
4232  if (limit)
4233  bcnt = limit;
4234 
4235  bvect::size_type samples[] =
4236  { 0, 1, 2, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, bcnt / 5, bcnt / 4, bcnt / 3, bcnt / 2, (bcnt * 2)/3, bcnt };
4237  bvect::size_type samples_size = sizeof(samples)/sizeof(*samples);
4238 
4239  cout << "Taking random sub-sets: " << samples_size << endl;
4240 
4241  for (bvect::size_type i = 0; i < samples_size; ++i)
4242  {
4243  bvect::size_type sample_count = samples[i];
4244 
4245  cout << "\r" << i << " / " << samples_size << " take = " << sample_count << flush;
4246 
4247  rsub.sample(bv_subset, bv, sample_count);
4248  bv_subset.optimize();
4249  if (sample_count > bcnt)
4250  sample_count = bcnt;
4251 
4252  if (sample_count != bv_subset.count())
4253  {
4254  cout << "\nRandom subset failed! sample_count = %u result_count=%u\n"
4255  << sample_count
4256  << ", " << bv_subset.count()
4257  << endl;
4258 
4259  exit(1);
4260  }
4261  {
4262  bvect bv_subset_copy(bv_subset);
4263  {
4264  bvect bv_set_copy(bv);
4265  bv_set_copy.invert();
4266  bv_subset_copy -= bv_set_copy;
4267  }
4268  int res = bv_subset_copy.compare(bv_subset);
4269  if (res != 0)
4270  {
4271  printf("\nRandom subset failed! inverted set MINUS error! \n");
4272  assert(0); exit(1);
4273  }
4274  }
4275 
4276  bv_subset -= bv;
4277  if (bv_subset.count() != 0)
4278  {
4279  printf("\nRandom subset failed! Extra bits set! \n");
4280  assert(0); exit(1);
4281  }
4282 
4283  } // for
4284  cout << endl;
4285 }
4286 
4287 // find last set bit by scan (not optimal)
4288 //
4289 static
4290 bool FindLastBit(const bvect& bv, bvect::size_type& last_pos)
4291 {
4292  bvect::enumerator en = bv.first();
4293  if (!en.valid())
4294  return false;
4295  for (; en.valid(); ++en)
4296  {
4297  last_pos = *en;
4298  }
4299  return true;
4300 }
4301 
4302 
4303 // vectors comparison check
4304 inline
4305 void CheckVectors(bvect_mini &bvect_min,
4306  bvect &bvect_full,
4308  bool /*detailed*/)
4309 {
4310  cout << "\nVectors checking...bits to compare = " << size << endl;
4311 
4312  cout << "Bitcount summary : " << endl;
4313  bvect::size_type min_count = bvect_min.bit_count();
4314  cout << "minvector count = " << min_count;
4315  bvect::size_type count = bvect_full.count();
4316  bvect::size_type full_count = count;
4317  cout << "fullvector re-count = " << full_count << endl;
4318 
4319  if (min_count != full_count)
4320  {
4321  cout << "fullvector count = " << count << endl;
4322  cout << "Count comparison failed !!!!" << endl;
4323 // print_stat(bvect_full);
4324 // DetailedCheckVectors(bvect_min, bvect_full, size);
4325  assert(0);
4326  exit(1);
4327  }
4328 
4329  if (full_count)
4330  {
4331  bool any = bvect_full.any();
4332  if (!any)
4333  {
4334  cout << "Anycheck failed!" << endl;
4335  assert(0);
4336  exit(1);
4337  }
4338  }
4339 
4340  // find_last check
4341  {
4342  bvect::size_type pos1 = 0;
4343  bvect::size_type pos2 = 0;
4344  bool last_found1 = FindLastBit(bvect_full, pos1);
4345  bool last_found2 = bvect_full.find_reverse(pos2);
4346 
4347  assert(last_found1 == last_found2);
4348  if (last_found1)
4349  {
4350  assert(pos1 == pos2);
4351  }
4352  }
4353 
4354  IntervalsCheck(bvect_full);
4355  IntervalsEnumeratorCheck(bvect_full);
4356 
4357 
4358  // get_next comparison
4359  cout << "Positive bits comparison..." << flush;
4360  bvect::size_type nb_min = bvect_min.get_first();
4361  bvect::size_type nb_ful = bvect_full.get_first();
4362 
4363  bvect::counted_enumerator en = bvect_full.first();
4364  bvect::size_type nb_en = *en;
4365  bvect::enumerator en1 = bvect_full.get_enumerator(*en);
4366  if (nb_min != nb_ful)
4367  {
4368  cout << "!!!! First bit comparison failed. Full id = "
4369  << nb_ful << " Min id = " << nb_min
4370  << endl;
4371 
4372  bool bit_f = bvect_full.get_bit(nb_ful);
4373  cout << "Full vector'd bit #" << nb_ful << "is:"
4374  << bit_f << endl;
4375 
4376  bool bit_m = (bvect_min.is_bit_true(nb_min) == 1);
4377  cout << "Min vector'd bit #" << nb_min << "is:"
4378  << bit_m << endl;
4379 
4380 // print_stat(bvect_full);
4381 // DetailedCheckVectors(bvect_min, bvect_full, size);
4382  assert(0);
4383  exit(1);
4384  }
4385  CompareEnumerators(en, en1);
4386 
4387  if (full_count)
4388  {
4389  bvect::size_type bit_count = 1;
4390  bvect::size_type en_prev = nb_en;
4391 
4392  do
4393  {
4394  nb_min = bvect_min.get_next(nb_min);
4395  if (nb_min == 0)
4396  {
4397  break;
4398  }
4399 
4400  en_prev = nb_en;
4401  ++en;
4402  ++en1;
4403  CompareEnumerators(en, en1);
4404 
4405  if (!(bit_count & 0xFF))
4406  {
4407  bvect::enumerator en2 = bvect_full.get_enumerator(*en);
4408  CompareEnumerators(en, en2);
4409  }
4410 
4411  nb_en = *en;
4412  ++bit_count;
4413 
4414  if (nb_en != nb_min)
4415  {
4416  nb_ful = bvect_full.get_next(en_prev);
4417  cout << "!!!!! next bit comparison failed. Full id = "
4418  << nb_ful << " Min id = " << nb_min
4419  << " Enumerator = " << nb_en
4420  << endl;
4421  // DetailedCheckVectors(bvect_min, bvect_full, size);
4422  assert(0);
4423  exit(1);
4424  }
4425  } while (en.valid());
4426  if (bit_count != min_count)
4427  {
4428  cout << " Bit count failed."
4429  << " min = " << min_count
4430  << " bit = " << bit_count
4431  << endl;
4432  assert(0);
4433  exit(1);
4434  }
4435  }
4436 
4437  cout << "OK" << endl;
4438  return;
4439 }
4440 
4441 
4442 
4443 
4444 const unsigned ITERATIONS = 180000;
4445 
4446 
4447 static
4449 {
4450  std::random_device rd;
4451  std::mt19937_64 mt_rand(rd());
4452 
4454  bvect::size_type BITVECT_FROM = bvect::size_type(bm::id_max32) - 65535;
4455 
4457 
4459 
4460  cout << "-------------------------- SimpleRandomFillTest" << endl;
4461 
4462  printf("Test for Random inverted subset.");
4463 
4464  {
4465  bvect bv;
4466  bv.invert();
4467  TestRandomSubset(bv, rsub, 256);
4468  }
4469 
4470 
4471  {
4472  printf("Simple random fill test 1.");
4473  bvect_mini bvect_min(BITVECT_SIZE);
4474  bvect bvect_full;
4475  bvect_full.set_new_blocks_strat(bm::BM_BIT);
4476 
4477 
4478  bvect::size_type iter = ITERATIONS / 5;
4479 
4480  cout << "\nSimple Random fill test ITERATIONS = " << iter << endl;;
4481 
4482  bvect_min.set_bit(0);
4483  bvect_full.set_bit(0);
4484 
4486  for (i = 0; i < iter; ++i)
4487  {
4488  bvect::size_type num = mt_rand() % iter;
4489  bvect_min.set_bit(BITVECT_FROM + num);
4490  bvect_full.set_bit(BITVECT_FROM + num);
4491  if ((i % 1000) == 0) cout << "." << flush;
4492 // CheckCountRange(bvect_full, 0, num);
4493 // CheckCountRange(bvect_full, num, num+iter);
4494  }
4495 
4496  CheckVectors(bvect_min, bvect_full, iter, false);
4497 // CheckCountRange(bvect_full, 0, iter);
4498 
4499  TestRandomSubset(bvect_full, rsub);
4500 
4501  printf("Simple random fill test 2.");
4502 
4503  for(i = 0; i < iter; ++i)
4504  {
4505  bvect::size_type num = mt_rand() % iter;
4506  bvect_min.clear_bit(BITVECT_FROM + num);
4507  bvect_full.clear_bit(BITVECT_FROM + num);
4508  }
4509 
4510  CheckVectors(bvect_min, bvect_full, iter, false);
4511  }
4512 
4513 
4514  {
4515  printf("\nSimple random fill test 3.\n");
4516  bvect_mini bvect_min(BITVECT_SIZE);
4517  bvect bvect_full(bm::BM_GAP);
4518 
4519 
4521 
4522  cout << "Simple Random fill test ITERATIONS = " << iter << endl;
4523 
4525  for(i = 0; i < iter; ++i)
4526  {
4527  bvect::size_type num = mt_rand() % iter;
4528  bvect_min.set_bit(BITVECT_FROM + num);
4529  bvect_full.set_bit(BITVECT_FROM + num);
4530 // CheckCountRange(bvect_full, 0, 65535);
4531 // CheckCountRange(bvect_full, 0, num);
4532 // CheckCountRange(bvect_full, num, num+iter);
4533  }
4534 
4535  CheckVectors(bvect_min, bvect_full, iter, false);
4536 
4537  TestRandomSubset(bvect_full, rsub);
4538 
4539  printf("Simple random fill test 4.");
4540 
4541  for(i = 0; i < iter; ++i)
4542  {
4543  bvect::size_type num = mt_rand() % iter;
4544  bvect_min.clear_bit(BITVECT_FROM + num);
4545  bvect_full.clear_bit(BITVECT_FROM + num);
4546 // CheckCountRange(bvect_full, 0, num);
4547 // CheckCountRange(bvect_full, num, num+iter);
4548  }
4549 
4550  CheckVectors(bvect_min, bvect_full, iter, false);
4551 // CheckCountRange(bvect_full, 0, iter);
4552 
4553  TestRandomSubset(bvect_full, rsub);
4554  }
4555 
4556 }
4557 
4558 
4559 static
4561 {
4563 // bvect::size_type BITVECT_FROM = bvect::size_type(bm::id_max32) - 65535;
4564 
4566 
4567  cout << "----------------------------------- RangeRandomFillTest" << endl;
4568 
4569  {
4570  bvect_mini bvect_min(BITVECT_SIZE);
4571  bvect bvect_full;
4572 
4573  printf("Range Random fill test\n");
4574 
4577  if (max > BITVECT_SIZE)
4578  max = BITVECT_SIZE - 1;
4579 
4580  FillSets(&bvect_min, &bvect_full, min, max, 0ULL);
4581 
4582  CheckVectors(bvect_min, bvect_full, BITVECT_SIZE, false);
4583  }
4584  {
4585  bvect_mini bvect_min(BITVECT_SIZE);
4586  bvect bvect_full;
4587 
4588  printf("Range Random fill test\n");
4589 
4592  if (max > BITVECT_SIZE)
4593  max = BITVECT_SIZE - 1;
4594 
4595  FillSetsIntervals(&bvect_min, bvect_full, min, max, 4ULL);
4596 
4597  CheckVectors(bvect_min, bvect_full, BITVECT_SIZE, false);
4598  }
4599 }
4600 
4601 inline
4603 {
4604  bvect::size_type f1, l1, f2, l2;
4605 
4606  bvect bv_cp(bv, from, to);
4607  bvect bv_cp2(bv, to, from); // swapped interval copy is legal
4608 
4609  bvect bv_control;
4610  bv_control.set_range(from, to);
4611 
4612  bv_control &= bv;
4613 
4614  int res = bv_control.compare(bv_cp);
4615  if (res != 0)
4616  {
4617  bool found1 = bv_cp.find_range(f1, l1);
4618  bool found2 = bv_control.find_range(f2, l2);
4619 
4620  bvect bv_cp3(bv, from, to);
4621 
4622  cerr << "Error: bvector<>::range_copy() failed. from=" << from << " to=" << to << endl;
4623  if (found1)
4624  cerr << " range copy from=" << f1 << " to=" << l1 << endl;
4625  if (found2)
4626  cerr << " control from=" << f2 << " to=" << l2 << endl;
4627  exit(1);
4628  }
4629 
4630  int res2 = bv_control.compare(bv_cp2);
4631  if (res2 != 0)
4632  {
4633  bool found1 = bv_cp2.find_range(f1, l1);
4634  bool found2 = bv_control.find_range(f2, l2);
4635 
4636  cerr << "Error: reversed bvector<>::range_copy() failed. from=" << from << " to=" << to << endl;
4637  if (found1)
4638  cerr << " range copy from=" << f1 << " to=" << l1 << endl;
4639  if (found2)
4640  cerr << " control from=" << f2 << " to=" << l2 << endl;
4641  exit(1);
4642  }
4643 
4644  bool found1 = bv_cp.find_range(f1, l1);
4645  bool found2 = bv_control.find_range(f2, l2);
4646  if (found1 != found2)
4647  {
4648  cerr << "Error: Dynamic range integrity check." << endl;
4649  exit(1);
4650  }
4651  if (found1)
4652  {
4653  if (f1 != f2 || l1 != l2)
4654  {
4655  cerr << "Error: bvector<>::range_copy() failed (dynamic range check). from=" << from << " to=" << to << endl;
4656  cerr << " range copy from=" << f1 << " to=" << l1 << endl;
4657  cerr << " control from=" << f2 << " to=" << l2 << endl;
4658  exit(1);
4659  }
4660  }
4661 
4662 }
4663 
4664 
4665 static
4667 {
4668  cout << "----------------------------------- RangeCopyTest" << endl;
4669 
4670  {
4672  cout << "Basic range-copy test" << endl;
4673  bvect bvect1
4674  { 10, 20, 21, 100, 65535, 65536, 100000, to_max/2, to_max-1, to_max };
4675 
4676 
4677  CheckRangeCopy(bvect1, 0, 0);
4678  CheckRangeCopy(bvect1, 10, 10);
4679  CheckRangeCopy(bvect1, 15, 15);
4680  CheckRangeCopy(bvect1, 65535, 65535);
4681  CheckRangeCopy(bvect1, 65536, 65536);
4682  CheckRangeCopy(bvect1, 65535, 65536);
4683 
4684  for (unsigned k = 0; k < 2; ++k)
4685  {
4686  cout << "Pass " << k << "-0" << endl;
4687  for (bvect::size_type i = 0; i < to_max;)
4688  {
4689  CheckRangeCopy(bvect1, i, to_max);
4690  if (i < 128)
4691  ++i;
4692  else
4693  {
4694  if ((to_max - 256) > i)
4695  i += i / 5;
4696  else
4697  ++i;
4698  }
4699  cout << "\r" << i << "/" << to_max << flush;
4700  }
4701  cout << "Pass " << k << "-1" << endl;
4702  for (bvect::size_type i = to_max-1; i > 0; )
4703  {
4704  CheckRangeCopy(bvect1, 0, i);
4705  if (i < 128)
4706  --i;
4707  else
4708  {
4709  i -= i / 3;
4710  }
4711  cout << "\r" << i << "/" << to_max << flush;
4712  }
4713 
4714  cout << "Pass " << k << "-2" << endl;
4715  auto to = to_max;
4716  for (bvect::size_type i = 0; i < to; )
4717  {
4718  CheckRangeCopy(bvect1, i, to_max);
4719  if (i > 128)
4720  {
4721  i += i / 3;
4722  to -= to / 5;
4723  }
4724  else
4725  {
4726  i++;
4727  --to;
4728  }
4729  cout << "\r" << i << "/" << to_max << flush;
4730  }
4731  bvect1.optimize();
4732  } // for k
4733  cout << "OK" << endl;
4734  }
4735 
4736  {
4737  cout << "Inverted vector stress test" << endl;
4738  bvect bvect1;
4739  bvect1.invert();
4740 
4741  {
4742  const bvect::size_type to_max = bvect::size_type(bm::id_max-1);
4743  const bvect::size_type from = bvect::size_type(bm::id_max-1)-(200);
4744 
4745  cout << "T1" << endl;
4746  auto to = to_max;
4747 
4748  for (bvect::size_type i = from; i < to; ++i)
4749  {
4750  CheckRangeCopy(bvect1, i, to);
4751  }
4752 
4753  cout << "T2" << endl;
4754  to = to_max;
4755  for (bvect::size_type i = to; i > from; --i)
4756  {
4757  CheckRangeCopy(bvect1, 0, i);
4758  }
4759 
4760  cout << "T3" << endl;
4761  to = to_max;
4762  for (bvect::size_type i = from; i != to; ++i, --to)
4763  {
4764  CheckRangeCopy(bvect1, i, to);
4765  }
4766  cout << "T4" << endl;
4767  to = bm::id_max-1 - to_max - 100;
4768  for (bvect::size_type i = to; i < bm::id_max; ++i)
4769  {
4770  CheckRangeCopy(bvect1, i, bm::id_max);
4771  if ((i & 0xFFFF) == 0)
4772  cout << "\r" << i << flush;
4773  }
4774  cout << endl;
4775  to = bm::id_max-1 - to_max - 100;
4776  for (bvect::size_type i = to; i < bm::id_max-(65536 * 3); i+=65536 * 2)
4777  {
4778  bvect1.set(i, false);
4779  }
4780  for (bvect::size_type k = 0; k < 2; ++k)
4781  {
4782  cout << "T5 pass=" << k << endl;
4783  to = bm::id_max-1 - to_max - (bm::gap_max_bits/2);
4784  for (bvect::size_type i = to; i < bm::id_max; ++i)
4785  {
4786  CheckRangeCopy(bvect1, i, bm::id_max);
4787  if ((i & 0xFFFF) == 0)
4788  cout << "\r" << i << flush;
4789  }
4790  bvect1.optimize();
4791  }
4792  }
4793  }
4794 
4795  cout << "----------------------------------- RangeCopyTest OK" << endl;
4796 }
4797 
4798 
4799 static
4801 {
4803 
4804  cout << "-------------------------------------- ComparisonTest" << endl;
4805 
4806  bvect_mini bvect_min1(BITVECT_SIZE);
4807  bvect_mini bvect_min2(BITVECT_SIZE);
4808  bvect bvect_full1;
4809  bvect bvect_full2;
4810  int res1, res2;
4811 
4812  bvect_full1.set_bit(31);
4813  bvect_full2.set_bit(63);
4814 
4815  res1 = bvect_full1.compare(bvect_full2);
4816  if (res1 != 1)
4817  {
4818  printf("Comparison test failed 1\n");
4819  exit(1);
4820  }
4821 
4822  bvect_full1.clear();
4823  bvect_full2.clear();
4824 
4825  bvect_min1.set_bit(BITVECT_SIZE/2);
4826  bvect_min2.set_bit(BITVECT_SIZE/2);
4827 
4828  bvect_full1.set_bit(10);
4829  bvect_full2.set_bit(10);
4830  res1 = bvect_min1.compare(bvect_min2);
4831  res2 = bvect_full1.compare(bvect_full2);
4832 
4833  if (res1 != res2)
4834  {
4835  printf("Comparison test failed 1\n");
4836  exit(1);
4837  }
4838 
4839  printf("Comparison 2.\n");
4840 
4841  bvect_min1.set_bit(BITVECT_SIZE/2+1);
4842  bvect_full1.set_bit(BITVECT_SIZE/2+1);
4843 
4844  res1 = bvect_min1.compare(bvect_min2);
4845  res2 = bvect_full1.compare(bvect_full2);
4846  if (res1 != res2 && res1 != 1)
4847  {
4848  printf("Comparison test failed 2\n");
4849  exit(1);
4850  }
4851 
4852  res1 = bvect_min2.compare(bvect_min1);
4853  res2 = bvect_full2.compare(bvect_full1);
4854  if (res1 != res2 && res1 != -1)
4855  {
4856  printf("Comparison test failed 2.1\n");
4857  exit(1);
4858  }
4859 
4860  printf("Comparison 3.\n");
4861 
4863  bvect_full1.optimize(tb);
4864 
4865  res1 = bvect_min1.compare(bvect_min2);
4866  res2 = bvect_full1.compare(bvect_full2);
4867  if (res1 != res2 && res1 != 1)
4868  {
4869  printf("Comparison test failed 3\n");
4870  exit(1);
4871  }
4872 
4873  res1 = bvect_min2.compare(bvect_min1);
4874  res2 = bvect_full2.compare(bvect_full1);
4875  if (res1 != res2 && res1 != -1)
4876  {
4877  printf("Comparison test failed 3.1\n");
4878  exit(1);
4879  }
4880 
4881  printf("Comparison 4.\n");
4882 
4883  bvect_full2.optimize();
4884 
4885  res1 = bvect_min1.compare(bvect_min2);
4886  res2 = bvect_full1.compare(bvect_full2);
4887  if (res1 != res2 && res1 != 1)
4888  {
4889  printf("Comparison test failed 4\n");
4890  exit(1);
4891  }
4892  res1 = bvect_min2.compare(bvect_min1);
4893  res2 = bvect_full2.compare(bvect_full1);
4894  if (res1 != res2 && res1 != -1)
4895  {
4896  printf("Comparison test failed 4.1\n");
4897  exit(1);
4898  }
4899 
4900  printf("Comparison 5.\n");
4902  for (i = 0; i < 65536; ++i)
4903  {
4904  bvect_full1.set_bit(i+BITVECT_SIZE/2);
4905  }
4906  res1 = bvect_min1.compare(bvect_min2);
4907  res2 = bvect_full1.compare(bvect_full2);
4908 
4909  if (res1 != res2 && res1 != 1)
4910  {
4911  printf("Comparison test failed 5\n");
4912  exit(1);
4913  }
4914  bvect_full1.optimize();
4915  res1 = bvect_min2.compare(bvect_min1);
4916  res2 = bvect_full2.compare(bvect_full1);
4917  if (res1 != res2 && res1 != -1)
4918  {
4919  printf("Comparison test failed 5.1\n");
4920  exit(1);
4921  }
4922 
4923 }
4924 
4925 static
4927 {
4928  std::random_device rd;
4929  std::mt19937_64 mt_rand(rd());
4931 
4932  cout << " ----------------------------------- SerializationTest" << endl;
4933 
4934  cout << "\nSerialization STEP 0" << endl;
4935 
4936  {
4938 
4939 
4940  bvect_mini* bvect_min1= new bvect_mini(BITVECT_SIZE);
4941  bvect* bvect_full1= new bvect();
4942  bvect* bvect_full2= new bvect();
4943  bvect* bv_target_s= new bvect();
4944 
4945  bvect_full1->set_new_blocks_strat(bm::BM_BIT);
4946  bvect_full2->set_new_blocks_strat(bm::BM_BIT);
4947 
4948  for(bvect::size_type i = 0; i < size; ++i)
4949  {
4950  bvect_full1->set_bit(i);
4951  bvect_min1->set_bit(i);
4952  }
4953 
4954  bvect_full1->optimize();
4955  CheckVectors(*bvect_min1, *bvect_full1, size, true);
4956 
4957 
4958 
4959  bvect::statistics st;
4960  bvect_full1->calc_stat(&st);
4962 
4963  bm::serializer<bvect> bv_ser(tb);
4964  bm::serializer<bvect>::buffer sermem_buf;
4965  bv_ser.serialize(*bvect_full1, sermem_buf, &st);
4966  bvect::size_type slen = sermem_buf.size();
4967 
4968  cout << "Serialized mem_max = " << st.max_serialize_mem
4969  << " size= " << slen
4970  << " Ratio=" << (slen*100)/st.max_serialize_mem << "%"
4971  << endl;
4972 
4973  bm::deserialize(*bvect_full2, sermem_buf.buf());
4975  od.deserialize(*bv_target_s, sermem_buf.buf(), tb, set_OR);
4976 
4977 
4978  CheckVectors(*bvect_min1, *bvect_full2, size, true);
4979  CheckVectors(*bvect_min1, *bv_target_s, size, true);
4980 
4981 
4982  delete bvect_full2;
4983  delete bvect_min1;
4984  delete bvect_full1;
4985  delete bv_target_s;
4986 
4987  }
4988 
4989 
4990  {
4992 
4993 
4994  bvect_mini* bvect_min1= new bvect_mini(BITVECT_SIZE);
4995  bvect* bvect_full1= new bvect();
4996  bvect* bvect_full2= new bvect();
4997  bvect* bv_target_s= new bvect();
4998 
4999  bvect_full1->set_new_blocks_strat(bm::BM_BIT);
5000  bvect_full2->set_new_blocks_strat(bm::BM_BIT);
5001 
5002  bvect_full1->set_bit(BITVECT_SIZE-131072);
5003  bvect_min1->set_bit(BITVECT_SIZE-131072);
5004 
5005 
5006  bvect_full1->optimize();
5007 
5008  bvect::statistics st;
5009  bvect_full1->calc_stat(&st);
5010  unsigned char* sermem = new unsigned char[st.max_serialize_mem];
5011  size_t slen = bm::serialize(*bvect_full1, sermem);
5012  cout << "Serialized mem_max = " << st.max_serialize_mem
5013  << " size= " << slen
5014  << " Ratio=" << (slen*100)/st.max_serialize_mem << "%"
5015  << endl;
5016 
5017  bm::deserialize(*bvect_full2, sermem);
5019 
5020  od.deserialize(*bv_target_s,
5021  sermem,
5022  0,
5023  set_OR);
5024 
5025  delete [] sermem;
5026 
5027  CheckVectors(*bvect_min1, *bvect_full2, size, false);
5028  CheckVectors(*bvect_min1, *bv_target_s, size, false);
5029 
5030  delete bvect_full2;
5031  delete bvect_min1;
5032  delete bvect_full1;
5033  delete bv_target_s;
5034 
5035  }
5036 
5037 
5038  cout << "\nSerialization STEP 1." << endl;
5039 
5040  {
5041  bvect_mini bvect_min1(BITVECT_SIZE);
5042  bvect bvect_full1;
5043 
5044  bvect_full1.set_new_blocks_strat(bm::BM_GAP);
5045 
5048  if (max > BITVECT_SIZE)
5049  max = BITVECT_SIZE - 1;
5050 
5052 
5053  FillSets(&bvect_min1, &bvect_full1, min, max, 0ull);
5054  FillSets(&bvect_min1, &bvect_full1, 0ull, len, 5ull);
5055 
5056  // shot some random bits
5057 
5059  for (i = 0; i < 10000; ++i)
5060  {
5061  bvect::size_type bit = mt_rand() % BITVECT_SIZE;
5062  bvect_full1.set_bit(bit);
5063  bvect_min1.set_bit(bit);
5064  }
5065 
5066  bvect::statistics st;
5067  bvect_full1.calc_stat(&st);
5068 
5069  unsigned char* sermem = new unsigned char[st.max_serialize_mem];
5070  //print_stat(bvect_full1);
5071 
5072  size_t slen = bm::serialize(bvect_full1, sermem);
5073 
5074  cout << "Serialized len = " << slen << endl;
5075 
5076  bvect bvect_full3;
5077  bm::deserialize(bvect_full3, sermem);
5078  bvect* bv_target_s = new bvect();
5080 
5081  od.deserialize(*bv_target_s,
5082  sermem,
5083  0,
5084  set_OR);
5085 
5086  CheckVectors(bvect_min1, bvect_full3, max+10, false);
5087  CheckVectors(bvect_min1, *bv_target_s, max+10, false);
5088 
5089  delete [] sermem;
5090  delete bv_target_s;
5091 
5092  }
5093 
5094 
5095  cout << "\nStage 2" << endl;
5096 
5097  {
5098 
5099  bvect_mini* bvect_min1= new bvect_mini(BITVECT_SIZE);
5100 // bm::bvect_mini* bvect_min2= new bm::bvect_mini(BITVECT_SIZE);
5101  bvect* bvect_full1= new bvect();
5102  bvect* bvect_full2= new bvect();
5103 
5104  bvect_full1->set_new_blocks_strat(bm::BM_GAP);
5105  bvect_full2->set_new_blocks_strat(bm::BM_GAP);
5106 
5107  FillSetsRandomMethod(bvect_min1, bvect_full1, 1ull, BITVECT_SIZE-10, 1);
5108 // FillSetsRandomMethod(bvect_min2, bvect_full2, 1, BITVECT_SIZE-10, 1);
5109 
5110  bvect::statistics st;
5111  bvect_full1->calc_stat(&st);
5112 
5113  bm::serializer<bvect> bv_ser;
5114  bm::serializer<bvect>::buffer sermem_buf;
5115 
5116  bv_ser.serialize(*bvect_full1, sermem_buf, &st);
5117  unsigned slen = (unsigned)sermem_buf.size();
5118 
5119  cout << "Serialized mem_max = " << st.max_serialize_mem
5120  << " size= " << slen
5121  << " Ratio=" << (slen*100)/st.max_serialize_mem << "%"
5122  << endl;
5123  bm::deserialize(*bvect_full2, sermem_buf.buf());
5124  bvect* bv_target_s=new bvect();
5126  od.deserialize(*bv_target_s,
5127  sermem_buf.buf(),
5128  0,
5129  set_OR);
5130 
5131  CheckVectors(*bvect_min1, *bvect_full2, BITVECT_SIZE, false);
5132  CheckVectors(*bvect_min1, *bv_target_s, BITVECT_SIZE, false);
5133 
5134  delete bv_target_s;
5135  delete bvect_full2;
5136  delete bvect_min1;
5137  delete bvect_full1;
5138 
5139  }
5140 
5141 
5142 
5143  cout << "\nStage 3" << endl;
5144 
5145  {
5146 
5147  bvect_mini* bvect_min1= new bvect_mini(BITVECT_SIZE);
5148  bvect_mini* bvect_min2= new bvect_mini(BITVECT_SIZE);
5149  bvect* bvect_full1= new bvect();
5150  bvect* bvect_full2= new bvect();
5151 
5152  bvect_full1->set_new_blocks_strat(bm::BM_GAP);
5153  bvect_full2->set_new_blocks_strat(bm::BM_GAP);
5154 
5155 
5156  FillSetsRandomMethod(bvect_min1, bvect_full1, 1ull, BITVECT_SIZE, 1);
5157  FillSetsRandomMethod(bvect_min2, bvect_full2, 1ull, BITVECT_SIZE, 1);
5158  CheckVectors(*bvect_min1, *bvect_full1, BITVECT_SIZE, true);
5159  CheckVectors(*bvect_min2, *bvect_full2, BITVECT_SIZE, true);
5160 
5161 
5162  bvect::statistics st;
5163  bvect_full1->calc_stat(&st);
5164  unsigned char* sermem = new unsigned char[st.max_serialize_mem];
5165  size_t slen = bm::serialize(*bvect_full1, sermem);
5166 
5167  bvect bvt;
5168  bm::deserialize(bvt, sermem);
5169  if (bvt != *bvect_full1)
5170  {
5171  //print_stat(bvt);
5172  //print_stat(*bvect_full1);
5173  cout << "Error!" << endl;
5174  assert(0); exit(1);
5175  }
5176 
5177  CheckVectors(*bvect_min1, *bvect_full1, BITVECT_SIZE, true);
5178  CheckVectors(*bvect_min2, *bvect_full2, BITVECT_SIZE, true);
5179 
5180  cout << "Serialized mem_max = " << st.max_serialize_mem
5181  << " size= " << slen
5182  << " Ratio=" << (slen*100)/st.max_serialize_mem << "%"
5183  << endl;
5184 
5185  bvect* bv_target_s=new bvect(*bvect_full2);
5186  //print_stat(*bv_target_s);
5187 
5188  //print_stat(*bvect_full2);
5189 
5190  bvect* bvect_full3= new bvect();
5191  *bvect_full3 = *bvect_full1;
5192  *bvect_full3 |= *bvect_full2;
5193  // bug in test here
5194  //CheckVectors(*bvect_min2, *bvect_full3, BITVECT_SIZE, true);
5195 
5196 
5197  bm::deserialize(*bvect_full2, sermem);
5198 
5200  od.deserialize(*bv_target_s,
5201  sermem,
5202  0,
5203  set_OR);
5204  delete [] sermem;
5205 
5206  CheckVectors(*bvect_min1, *bvect_full1, BITVECT_SIZE, true);
5207  // bug in test, commented out
5208 // CheckVectors(*bvect_min1, *bvect_full3, BITVECT_SIZE, true);
5209 
5210  bvect_min2->combine_or(*bvect_min1);
5211  delete bvect_min1;
5212 
5213  if (*bvect_full2 != *bvect_full3)
5214  {
5215  //print_stat(*bvect_full2);
5216  //print_stat(*bvect_full3);
5217 
5218  cout << "Error!" << endl;
5219  assert(0);
5220  exit(1);
5221  }
5222 
5223 
5224  CheckVectors(*bvect_min2, *bvect_full2, BITVECT_SIZE, true);
5225  CheckVectors(*bvect_min2, *bv_target_s, BITVECT_SIZE, true);
5226 
5227  delete bv_target_s;
5228  delete bvect_full1;
5229  delete bvect_full2;
5230  delete bvect_full3;
5231  delete bvect_min2;
5232 
5233 
5234  }
5235 
5236  cout << "\nStage 4. " << endl;
5237 
5238  {
5240 
5241 
5242  bvect_mini* bvect_min1= new bvect_mini(BITVECT_SIZE);
5243  bvect* bvect_full1= new bvect();
5244  bvect* bvect_full2= new bvect();
5245 
5246  bvect_full1->set_new_blocks_strat(bm::BM_BIT);
5247  bvect_full2->set_new_blocks_strat(bm::BM_BIT);
5248 
5249  unsigned i;
5250  for(i = 0; i < 65000; ++i)
5251  {
5252  bvect_full1->set_bit(i);
5253  bvect_min1->set_bit(i);
5254  }
5255 
5256  for (i = 65536; i < 65536+65000; ++i)
5257  {
5258  bvect_full1->set_bit(i);
5259  bvect_min1->set_bit(i);
5260  }
5261 
5262  for (i = 65536*2; i < size/6; ++i)
5263  {
5264  bvect_full1->set_bit(i);
5265  bvect_min1->set_bit(i);
5266  }
5267 
5268 
5269  bvect_full1->optimize();
5270 
5271  print_stat(cout,*bvect_full1);
5272 
5273 
5274  bvect::statistics st;
5275  bvect_full1->calc_stat(&st);
5276  unsigned char* sermem = new unsigned char[st.max_serialize_mem];
5277  size_t slen = bm::serialize(*bvect_full1, sermem);
5278  cout << "Serialized mem_max = " << st.max_serialize_mem
5279  << " size= " << slen
5280  << " Ratio=" << (slen*100)/st.max_serialize_mem << "%"
5281  << endl;
5282 
5283  unsigned char* new_sermem = new unsigned char[st.max_serialize_mem];
5284  ::memcpy(new_sermem, sermem, slen);
5285 
5286  bvect bv_target_s(*bvect_full2);
5287 
5288  bm::deserialize(*bvect_full2, new_sermem);
5289 
5291  od.deserialize(bv_target_s,
5292  new_sermem,
5293  0,
5294  set_OR);
5295 
5296  delete [] sermem;
5297  delete [] new_sermem;
5298 
5299  CheckVectors(*bvect_min1, *bvect_full2, size, true);
5300  CheckVectors(*bvect_min1, bv_target_s, size, true);
5301 
5302 
5303  delete bvect_full2;
5304  delete bvect_min1;
5305  delete bvect_full1;
5306 
5307  }
5308 }
5309 
5310 
5311 static
5313 {
5314  cout << "\n-------------------------------------- DesrializationTest2()" << endl;
5316 
5317 
5318  bvect bv1, bv2;
5319  bvect bvtotal;
5322  unsigned repetitions = 10;
5324 
5325 
5326  for (i = bm::id_max32; i < (bm::id_max32+165536); i+=2)
5327  {
5328  bv1.set_bit(i);
5329  }
5330 
5331  bv1.optimize(tb);
5332 
5333  struct bvect::statistics st1;
5334  bv1.calc_stat(&st1);
5335 
5336  std::vector<unsigned char> sermemv(st1.max_serialize_mem);
5337 
5338  size_t slen2 = bm::serialize(bv1, sermemv.data(), tb);
5339  assert(slen2);
5340  slen2 = 0;
5341 
5342  bm::deserialize(bvtotal, sermemv.data());
5343  bvect bv_target_s;
5344 
5346  od.deserialize(bv_target_s,
5347  sermemv.data(),
5348  0,
5349  set_OR);
5350 
5351  bvtotal.optimize(tb);
5352  int res = bvtotal.compare(bv_target_s);
5353  if (res != 0)
5354  {
5355  cout << "Operation deserialization error 1" << endl;
5356  assert(0);
5357  exit(1);
5358  }
5359 
5360  for (i = bm::id_max32+55000; i < bm::id_max32+165536; ++i)
5361  {
5362  bv2.set_bit(i);
5363  }
5364  bv2.optimize();
5365  print_stat(cout,bv2);
5366 
5367  struct bvect::statistics st2;
5368  bv2.calc_stat(&st2);
5369 
5370  std::vector<unsigned char> sermemv2(st2.max_serialize_mem);
5371 
5372  size_t slen = bm::serialize(bv2, sermemv2.data());
5373  assert(slen);
5374  slen = 0;
5375 
5376  bm::deserialize(bvtotal, sermemv2.data());
5377  print_stat(cout,bvtotal);
5378  //operation_deserializer<bvect64> od;
5379 
5380  od.deserialize(bv_target_s,
5381  sermemv2.data(),
5382  0,
5383  set_OR);
5384  res = bvtotal.compare(bv_target_s);
5385  if (res != 0)
5386  {
5387  cout << "Operation deserialization error 2" << endl;
5388  assert(0);
5389  exit(1);
5390  }
5391 
5392 
5393  bm::deserialize(bvtotal, sermemv2.data());
5394  bm::deserialize(bvtotal, sermemv.data());
5395 
5396  od.deserialize(bv_target_s,
5397  sermemv2.data(),
5398  0,
5399  set_OR);
5400  od.deserialize(bv_target_s,
5401  sermemv2.data(),
5402  0,
5403  set_OR);
5404 
5405  res = bvtotal.compare(bv_target_s);
5406  if (res != 0)
5407  {
5408  cout << "Deserialization test failed! 3" << endl;
5409  assert(0);
5410  exit(1);
5411  }
5412 
5413 
5414  bvtotal.clear();
5415  bv_target_s.clear(false);
5416 
5417  int clcnt = 0;
5418 
5419  for (i = 0; i < repetitions; ++i)
5420  {
5421  cout << endl << endl << "Deserialization STEP " << i << endl;
5422 
5423  bvect_mini* bvect_min1= new bvect_mini(size);
5424  bvect* bvect_full1= new bvect();
5425 
5426  FillSetsRandomMethod(bvect_min1, bvect_full1, 1ull, size, 1ull);
5427 
5428  struct bvect::statistics st;
5429  bvect_full1->calc_stat(&st);
5430 
5431  std::vector<unsigned char> sermemv1(st.max_serialize_mem);
5432 
5433  slen = bm::serialize(*bvect_full1, sermemv1.data(), tb);
5434 
5435  std::vector<unsigned char> smemv(slen);
5436  ::memcpy(smemv.data(), sermemv1.data(), slen);
5437 
5438 
5439  bm::deserialize(bvtotal, smemv.data());
5440  od.deserialize(bv_target_s,
5441  smemv.data(),
5442  0,
5443  set_OR);
5444  res = bvtotal.compare(bv_target_s);
5445  if (res != 0)
5446  {
5447  bvect::size_type bit_idx = bv_target_s.get_first();
5448  cout << bit_idx << " " << bv_target_s.get_next(bit_idx) << endl;;
5449  print_stat(cout,bv_target_s);
5450  cout << "Operation deserialization error 2" << endl;
5451  assert(0);
5452  exit(1);
5453  }
5454 
5455  bvtotal.optimize(tb);
5456  bv_target_s.optimize(tb);
5457 
5458 
5459  if (++clcnt == 5)
5460  {
5461  clcnt = 0;
5462  bvtotal.clear();
5463  bv_target_s.clear();
5464  }
5465 
5466  delete bvect_min1;
5467  delete bvect_full1;
5468 
5469  } // for i
5470 
5471  cout << "de-serialization test 64-bit wide vectors mix.." << endl;
5472  {
5473  for (i = 0; i < repetitions; ++i)
5474  {
5475  bvect64 bv0;
5476  bv1.clear();
5477  {
5478  ref_vect vect0, vect1;
5479 
5480  generate_vect_simpl0(vect0);
5481  generate_vect48(vect1);
5482 
5483  load_BV_set_ref(cout,bv0, vect0, false);
5484  load_BV_set_ref(cout,bv1, vect1, false);
5485  }
5486 
5487  bm::serializer<bvect64> bv_ser;
5488  bm::serializer<bvect64>::buffer sbuf0, sbuf1;
5489  bv_ser.serialize(bv0, sbuf0, 0);
5490  bv_ser.serialize(bv1, sbuf1, 0);
5491 
5492  bvect64 bv_tc;
5493  bv_tc.bit_or(bv0, bv1, bvect64::opt_none);
5494  {
5495  bvect64 bv_tc1(bv0);
5496  bv_tc1 |= bv1;
5497  int cmp = bv_tc.compare(bv_tc1);
5498  assert(cmp==0);
5499  }
5500 
5501  bvect64 bv_tc_and;
5502  bv_tc_and.bit_and(bv0, bv1, bvect64::opt_none);
5503 
5504  // integrity check
5505  {
5506  bvect64 bv_t0;
5507  bm::deserialize(bv_t0, sbuf0.buf());
5508  res = bv0.compare(bv_t0);
5509  assert(res==0);
5510  // pass 2 to make sure deserialization into the same is ok
5511  bm::deserialize(bv_t0, sbuf0.buf());
5512  res = bv0.compare(bv_t0);
5513  assert(res==0);
5514 
5515 
5516  bvect64 bv_t1;
5517  bm::deserialize(bv_t1, sbuf1.buf());
5518  res = bv1.compare(bv_t1);
5519  assert(res==0);
5520  bm::deserialize(bv_t1, sbuf1.buf());
5521  res = bv1.compare(bv_t1);
5522  assert(res==0);
5523  }
5524 
5525  {
5526  bvect64 bv_t0, bv_t1;
5527  od.deserialize(bv_t0, sbuf0.buf(), 0, set_OR);
5528  int cmp = bv0.compare(bv_t0);
5529  assert(cmp == 0);
5530  od.deserialize(bv_t1, sbuf1.buf(), 0, set_OR);
5531  cmp = bv1.compare(bv_t1);
5532  assert(!cmp);
5533  }
5534 
5535  {
5536  bvect64 bv_t;
5537  od.deserialize(bv_t, sbuf1.buf(), 0, set_OR);
5538  od.deserialize(bv_t, sbuf0.buf(), 0, set_OR);
5539  int cmp = bv_tc.compare(bv_t);
5540  if (cmp)
5541  {
5542  std::cerr << "Serialization intergity check failed!" << std::endl;
5543  assert(0); exit(1);
5544  }
5545  }
5546  {
5547  bvect64 bv_t;
5548  od.deserialize(bv_t, sbuf0.buf(), 0, set_OR);
5549  od.deserialize(bv_t, sbuf0.buf(), 0, set_AND);
5550  int cmp = bv0.compare(bv_t);
5551  if (cmp)
5552  {
5553  std::cerr << "AND Serialization intergity check failed!" << std::endl;
5554  assert(0); exit(1);
5555  }
5556  }
5557  {
5558  bvect64 bv_t;
5559  od.deserialize(bv_t, sbuf1.buf(), 0, set_OR);
5560  od.deserialize(bv_t, sbuf1.buf(), 0, set_AND);
5561  int cmp = bv1.compare(bv_t);
5562  if (cmp)
5563  {
5564  std::cerr << "AND Serialization intergity check failed!" << std::endl;
5565  assert(0); exit(1);
5566  }
5567  }
5568 
5569  {
5570  bvect64 bv_t;
5571  od.deserialize(bv_t, sbuf0.buf(), 0, set_OR);
5572  od.deserialize(bv_t, sbuf1.buf(), 0, set_AND);
5573  int cmp = bv_tc_and.compare(bv_t);
5574  if (cmp)
5575  {
5576  std::cerr << "AND Serialization intergity check failed!" << std::endl;
5577  assert(0); exit(1);
5578  }
5579  }
5580 
5581 
5582  // TODO: add detection that blocks are actually getting freed as a result
5583  //
5584  {
5585  bvect64 bv_t;
5586  od.deserialize(bv_t, sbuf0.buf(), 0, set_OR);
5587  od.deserialize(bv_t, sbuf0.buf(), 0, set_XOR);
5588  auto cnt = bv_t.count();
5589  if (cnt)
5590  {
5591  std::cerr << "XOR Serialization intergity check failed!" << std::endl;
5592  assert(0); exit(1);
5593  }
5594  }
5595  {
5596  bvect64 bv_t;
5597  od.deserialize(bv_t, sbuf1.buf(), 0, set_OR);
5598  od.deserialize(bv_t, sbuf1.buf(), 0, set_XOR);
5599  auto cnt = bv_t.count();
5600  if (cnt)
5601  {
5602  std::cerr << "XOR Serialization intergity check failed!" << std::endl;
5603  assert(0); exit(1);
5604  }
5605  }
5606  {
5607  bvect64 bv_t;
5608  od.deserialize(bv_t, sbuf1.buf(), 0, set_OR);
5609  od.deserialize(bv_t, sbuf1.buf(), 0, set_SUB);
5610  auto cnt = bv_t.count();
5611  if (cnt)
5612  {
5613  std::cerr << "SUB Serialization intergity check failed!" << std::endl;
5614  assert(0); exit(1);
5615  }
5616  }
5617  {
5618  bvect64 bv_t;
5619  bm::deserialize(bv_t, sbuf0.buf());
5620  res = bv0.compare(bv_t);
5621  assert(res==0);
5622 
5623  bvect64 bv_t_c(bv_t);
5624 
5625  bm::deserialize(bv_t, sbuf1.buf());
5626  int cmp = bv_tc.compare(bv_t);
5627  if (cmp)
5628  {
5629  std::cerr << "Serialization intergity check failed!" << std::endl;
5630  assert(0); exit(1);
5631  }
5632  }
5633  cout << "\r" << i << "/" << repetitions << flush;
5634  } // for i
5635  cout << endl << "OK" << endl;;
5636  }
5637 
5638  cout << "\n-------------------------------------- DesrializationTest2() OK" << endl;
5639 }
5640 
5641 static
5643  bvect::size_type to,
5644  bvect::size_type step = 65536 / 10)
5645 {
5646  for (bvect::size_type i = from; true; i += step)
5647  {
5648  bv.set(i);
5649  if (to - step < i)
5650  break;
5651  }
5652 }
5653 
5654 static
5656 {
5657  cout << " ----------------------------------- SparseSerializationTest()" << endl;
5660  bm::serializer<bvect> bv_ser(tb);
5661  bm::serializer<bvect>::buffer sermem_buf;
5662  bm::serializer<bvect>::buffer sermem_buf_shifted;
5663 
5664  std::vector<std::pair<bvect::size_type, bvect::size_type> > ranges;
5665 
5666  ranges.push_back(std::make_pair(0, 65535 * 255));
5667  ranges.push_back(std::make_pair(0, 65535 * 255 * 2));
5668  ranges.push_back(std::make_pair(65535 * 5, 65535 * 255 * 2));
5669  ranges.push_back(std::make_pair(65535 * 255 / 2, 65535 * 255));
5670  ranges.push_back(std::make_pair(65535 * 255 / 2, 65535 * 255 * 2));
5671  ranges.push_back(std::make_pair(bm::id_max / 2 - 65535 * 255 / 2, bm::id_max / 2 + 65535 * 255 * 2));
5672  ranges.push_back(std::make_pair(bm::id_max / 2, bm::id_max / 2 + 65535 * 255 * 2));
5673  ranges.push_back(std::make_pair(bm::id_max - 65535 * 255 * 2, bm::id_max - 1));
5674 
5675  for (size_t k = 0; k < ranges.size(); ++k)
5676  {
5677  bvect::size_type from = ranges[k].first;
5678  bvect::size_type to = ranges[k].second;
5679 
5680  std::cout << " range [" << from << ", " << to << "]" << std::endl;
5681 
5682  for (unsigned i = 0; i < 2; ++i)
5683  {
5684  bvect bv, bv_shifted;
5685 
5686  generate_sparse_bv(bv, from, to, 65536 / 10);
5687  generate_sparse_bv(bv_shifted, from + 1, to + 1, 65536 / 10);
5688 
5689  //CheckRangeDeserial(bv, from, to);
5690 
5691  auto bv_cnt = bv.count();
5692 
5693  bv_ser.serialize(bv, sermem_buf, 0);
5694  bv_ser.serialize(bv_shifted, sermem_buf_shifted, 0);
5695 
5696  const bvect::size_type* cstat = bv_ser.get_compression_stat();
5697 
5698  {
5699  bvect::size_type sb_from = from / (65536 * 256);
5700  bvect::size_type sb_to = to / (65536 * 256);
5701  bvect::size_type sb_cnt = sb_to - sb_from + 1;
5702  assert(cstat[bm::set_sblock_bienc] == sb_cnt || cstat[bm::set_sblock_bienc] == sb_cnt - 1);
5703  }
5704 
5705  bvect bv2;
5706  bm::deserialize(bv2, sermem_buf.buf());
5707  bool eq = bv.equal(bv2);
5708  assert(eq);
5709 
5710  {
5711  bvect bv3;
5712  od.deserialize(bv3, sermem_buf.buf(), tb, set_OR);
5713  eq = bv3.equal(bv2);
5714  assert(eq);
5715  }
5716  {
5717  bvect bv3;
5718  od.deserialize(bv3, sermem_buf.buf(), tb, set_XOR);
5719  eq = bv3.equal(bv);
5720  assert(eq);
5721  od.deserialize(bv3, sermem_buf.buf(), tb, set_XOR);
5722  assert(bv3.count() == 0);