5 * Created by Victor Grishchenko on 3/22/09.
6 * Copyright 2009-2012 TECHNISCHE UNIVERSITEIT DELFT. All rights reserved.
8 * ==========================
9 * Extended by Arno and Riccardo to hunt a bug in find_complement() with
17 #include <gtest/gtest.h>
20 using namespace swift;
23 TEST(BinsTest,FindFiltered) {
25 binmap_t data, filter;
29 filter.set(bin_t(4,0));
30 filter.reset(bin_t(2,1));
31 filter.reset(bin_t(1,4));
32 filter.reset(bin_t(0,13));
34 bin_t x = binmap_t::find_complement(data, filter, bin_t(4,0), 0);
35 EXPECT_EQ(bin_t(0,12),x);
39 TEST(BinsTest,FindFiltered1b) {
41 binmap_t data, filter;
45 filter.set(bin_t(4,0));
46 filter.reset(bin_t(2,1));
47 filter.reset(bin_t(1,4));
48 filter.reset(bin_t(0,13));
53 fprintf(stderr,"Searching 0,12 from %s ", s.base_left().str(binstr ) );
54 fprintf(stderr,"to %s\n", s.base_right().str(binstr ) );
56 bin_t x = binmap_t::find_complement(data, filter, s, 0);
57 EXPECT_EQ(bin_t(0,12),x);
62 TEST(BinsTest,FindFiltered1c) {
64 binmap_t data, filter;
69 filter.set(bin_t(4,0));
70 filter.reset(bin_t(2,1));
71 filter.reset(bin_t(1,4));
72 //filter.reset(bin_t(0,13));
77 fprintf(stderr,"Searching 0,12x from %s ", s.base_left().str(binstr ) );
78 fprintf(stderr,"to %s\n", s.base_right().str(binstr ) );
80 bin_t x = binmap_t::find_complement(data, filter, s, 0);
81 EXPECT_EQ(bin_t(0,12),x);
86 TEST(BinsTest,FindFiltered2) {
88 binmap_t data, filter;
89 for(int i=0; i<1024; i+=2)
91 for(int j=0; j<1024; j+=2)
92 filter.set(bin_t(0,j));
94 fprintf(stderr,"test: width %d\n", filter.cells_number() );
95 fprintf(stderr,"test: empty %llu\n", filter.find_empty().toUInt() );
98 data.reset(bin_t(0,500));
99 EXPECT_EQ(bin_t(0,500),binmap_t::find_complement(data, filter, bin_t(10,0), 0).base_left());
100 data.set(bin_t(0,500));
101 EXPECT_EQ(bin_t::NONE,binmap_t::find_complement(data, filter, bin_t(10,0), 0).base_left());
106 // Range is strict subtree
107 TEST(BinsTest,FindFiltered3) {
109 binmap_t data, filter;
110 for(int i=0; i<1024; i+=2)
111 data.set(bin_t(0,i));
112 for(int j=0; j<1024; j+=2)
113 filter.set(bin_t(0,j));
114 data.reset(bin_t(0,500));
115 EXPECT_EQ(bin_t(0,500),binmap_t::find_complement(data, filter, bin_t(9,0), 0).base_left());
116 data.set(bin_t(0,500));
117 EXPECT_EQ(bin_t::NONE,binmap_t::find_complement(data, filter, bin_t(9,0), 0).base_left());
123 TEST(BinsTest,FindFiltered4) {
125 binmap_t data, filter;
126 for(int i=0; i<1036; i+=2)
127 data.set(bin_t(0,i));
128 for(int j=0; j<1036; j+=2)
129 filter.set(bin_t(0,j));
130 data.reset(bin_t(0,500));
131 EXPECT_EQ(bin_t(0,500),binmap_t::find_complement(data, filter, bin_t(9,0), 0).base_left());
132 data.set(bin_t(0,500));
133 EXPECT_EQ(bin_t::NONE,binmap_t::find_complement(data, filter, bin_t(9,0), 0).base_left());
137 // Make 8 bin hole in 1036 tree
139 TEST(BinsTest,FindFiltered5) {
141 binmap_t data, filter;
142 for(int i=0; i<1036; i++) //completely full
143 data.set(bin_t(0,i));
144 for(int j=0; j<1036; j++)
145 filter.set(bin_t(0,j));
147 for (int j=496; j<=503; j++)
148 data.reset(bin_t(0,j));
150 EXPECT_EQ(bin_t(3,62),binmap_t::find_complement(data, filter, bin_t(9,0), 0) );
151 EXPECT_EQ(bin_t(0,496),binmap_t::find_complement(data, filter, bin_t(9,0), 0).base_left());
155 // Use simple example tree from RFC
156 TEST(BinsTest,FindFiltered6) {
158 binmap_t data, filter;
159 for(int i=0; i<14; i+=2) //completely full example tree
161 for(int j=0; j<14; j+=2)
162 filter.set(bin_t(j));
164 for (int j=4; j<=6; j+=2) // reset leaves 4 and 6 (int)
165 data.reset(bin_t(j));
167 EXPECT_EQ(bin_t(1,1),binmap_t::find_complement(data, filter, bin_t(2,0), 0) );
168 EXPECT_EQ(bin_t(0,2),binmap_t::find_complement(data, filter, bin_t(2,0), 0).base_left());
172 // diff in right tree, range is left tree
173 TEST(BinsTest,FindFiltered7) {
175 binmap_t data, filter;
176 for(int i=0; i<14; i+=2) //completely full example tree
178 data.reset(bin_t(4)); // clear 4
179 for(int j=0; j<14; j+=2)
180 filter.set(bin_t(j));
181 filter.reset(bin_t(4));
183 for (int j=8; j<=10; j+=2) // make diff out of range
184 data.reset(bin_t(j));
186 EXPECT_EQ(bin_t::NONE,binmap_t::find_complement(data, filter, bin_t(2,0), 0) );
187 EXPECT_EQ(bin_t::NONE,binmap_t::find_complement(data, filter, bin_t(2,0), 0).base_left());
192 // diff in left tree, range is right tree
193 TEST(BinsTest,FindFiltered8) {
195 binmap_t data, filter;
196 for(int i=0; i<14; i+=2) //completely full example tree
198 data.reset(bin_t(4)); // clear 4
199 for(int j=0; j<14; j+=2)
200 filter.set(bin_t(j));
201 filter.reset(bin_t(4));
203 for (int j=4; j<=6; j+=2) // make diff out of range
204 data.reset(bin_t(j));
206 EXPECT_EQ(bin_t::NONE,binmap_t::find_complement(data, filter, bin_t(2,1), 0) );
207 EXPECT_EQ(bin_t::NONE,binmap_t::find_complement(data, filter, bin_t(2,1), 0).base_left());
211 // reverse empty/full
212 TEST(BinsTest,FindFiltered9) {
214 binmap_t data, filter;
215 for(int i=0; i<14; i+=2) //completely empty example tree
216 data.reset(bin_t(i));
217 data.set(bin_t(4)); // clear 4
218 for(int j=0; j<14; j+=2)
219 filter.reset(bin_t(j));
220 filter.set(bin_t(4));
222 for (int j=4; j<=6; j+=2) // make diff out of range
225 EXPECT_EQ(bin_t::NONE,binmap_t::find_complement(data, filter, bin_t(2,1), 0) );
226 EXPECT_EQ(bin_t::NONE,binmap_t::find_complement(data, filter, bin_t(2,1), 0).base_left());
230 // Make 8 bin hole in 999 tree, left subtree
232 TEST(BinsTest,FindFiltered10) {
234 binmap_t data, filter;
235 for(int i=0; i<999; i++) //completely full
236 data.set(bin_t(0,i));
237 for(int j=0; j<999; j++)
238 filter.set(bin_t(0,j));
240 for (int j=496; j<=503; j++)
241 data.reset(bin_t(0,j));
243 EXPECT_EQ(bin_t(3,62),binmap_t::find_complement(data, filter, bin_t(9,0), 0) );
244 EXPECT_EQ(bin_t(0,496),binmap_t::find_complement(data, filter, bin_t(9,0), 0).base_left());
248 // Make 8 bin hole in 999 tree, right subtree, does not start a 8-bin substree
249 TEST(BinsTest,FindFiltered11) {
251 binmap_t data, filter;
252 for(int i=0; i<999; i++) //completely full
253 data.set(bin_t(0,i));
254 for(int j=0; j<999; j++)
255 filter.set(bin_t(0,j));
257 for (int j=514; j<=521; j++)
258 data.reset(bin_t(0,j));
260 EXPECT_EQ(bin_t(1,257),binmap_t::find_complement(data, filter, bin_t(9,1), 0) );
261 EXPECT_EQ(bin_t(0,514),binmap_t::find_complement(data, filter, bin_t(9,1), 0).base_left());
264 // Make 8 bin hole in 999 tree, move hole
265 TEST(BinsTest,FindFiltered12) {
267 binmap_t data, filter;
268 for(int i=0; i<999; i++) //completely full
269 data.set(bin_t(0,i));
270 for(int j=0; j<999; j++)
271 filter.set(bin_t(0,j));
273 for (int x=0; x<999-8; x++)
275 fprintf(stderr,"x%u ", x);
276 for (int j=x; j<=x+7; j++)
277 data.reset(bin_t(0,j));
279 int subtree = (x <= 511) ? 0 : 1;
280 EXPECT_EQ(bin_t(0,x),binmap_t::find_complement(data, filter, bin_t(9,subtree), 0).base_left());
283 for (int j=x; j<=x+7; j++) {
284 data.set(bin_t(0,j));
290 // Make 8 bin hole in sparse 999 tree, move hole
291 TEST(BinsTest,FindFiltered13) {
293 binmap_t data, filter;
294 for(int i=0; i<999; i+=2) // sparse
295 data.set(bin_t(0,i));
296 for(int j=0; j<999; j+=2)
297 filter.set(bin_t(0,j));
299 for (int x=0; x<999-8; x++)
301 fprintf(stderr,"x%u ", x);
302 for (int j=x; j<=x+7; j++)
303 data.reset(bin_t(0,j));
305 int y = (x % 2) ? x+1 : x;
306 int subtree = (x <= 511) ? 0 : 1;
308 EXPECT_EQ(bin_t(0,y),binmap_t::find_complement(data, filter, bin_t(9,0), 0).base_left());
309 else if (x == 511) // sparse bitmap 101010101..., so actual diff in next subtree
310 EXPECT_EQ(bin_t::NONE,binmap_t::find_complement(data, filter, bin_t(9,0), 0).base_left());
312 EXPECT_EQ(bin_t(0,y),binmap_t::find_complement(data, filter, bin_t(9,1), 0).base_left());
315 for(int i=0; i<999; i+=2) // sparse
316 data.set(bin_t(0,i));
321 // Make 8 bin hole in sparse 999 tree, move hole
322 TEST(BinsTest,FindFiltered14) {
324 binmap_t data, filter;
325 for(int i=0; i<999; i+=2) // sparse
326 data.set(bin_t(0,i));
327 for(int j=0; j<999; j+=2)
328 filter.set(bin_t(0,j));
331 filter.set(bin_t(0,995));
333 for (int x=0; x<999-8; x++)
335 fprintf(stderr,"x%u ", x);
336 for (int j=x; j<=x+7; j++)
337 data.reset(bin_t(0,j));
339 int y = (x % 2) ? x+1 : x;
340 int subtree = (x <= 511) ? 0 : 1;
342 EXPECT_EQ(bin_t(0,y),binmap_t::find_complement(data, filter, bin_t(9,0), 0).base_left());
343 else if (x == 511) // sparse bitmap 101010101..., so actual diff in next subtree
344 EXPECT_EQ(bin_t::NONE,binmap_t::find_complement(data, filter, bin_t(9,0), 0).base_left());
346 EXPECT_EQ(bin_t(0,y),binmap_t::find_complement(data, filter, bin_t(9,1), 0).base_left());
349 for(int i=0; i<999; i+=2) // sparse
350 data.set(bin_t(0,i));
356 // Make holes at 292, problematic in a specific experiment
357 TEST(BinsTest,FindFiltered15) {
359 binmap_t data, filter;
360 for(int i=0; i<999; i++) // completely full
361 data.set(bin_t(0,i));
362 for(int j=0; j<999; j++)
363 filter.set(bin_t(0,j));
365 data.reset(bin_t(292));
366 data.reset(bin_t(296));
367 data.reset(bin_t(514));
368 data.reset(bin_t(998));
370 EXPECT_EQ(bin_t(292),binmap_t::find_complement(data, filter, bin_t(9,0), 0).base_left());
375 // VOD like. Make first hole at 292.
376 TEST(BinsTest,FindFiltered16) {
378 binmap_t data, filter;
379 for(int i=0; i<292/2; i++) // prefix full
380 data.set(bin_t(0,i));
381 for(int i=147; i<999; i+=21) // postfix sparse
383 for (int x=0; x<8; x++)
384 data.set(bin_t(0,i+x));
387 for(int j=0; j<999; j++)
388 filter.set(bin_t(0,j));
390 EXPECT_EQ(bin_t(292),binmap_t::find_complement(data, filter, bin_t(9,0), 0).base_left());
394 // VOD like. Make first hole at 292.
395 TEST(BinsTest,FindFiltered17) {
397 binmap_t offer, ack_hint_out;
398 for(int i=0; i<999; i++) // offer completely full
399 offer.set(bin_t(0,i));
401 for(int i=0; i<292/2; i++) // request prefix full
402 ack_hint_out.set(bin_t(0,i));
403 for(int i=147; i<999; i+=21) // request postfix sparse
405 for (int x=0; x<8; x++)
406 ack_hint_out.set(bin_t(0,i+x));
411 // report the first bin we find
413 bin_t::uint_t twist = 0;
414 bin_t hint = bin_t::NONE;
415 while (hint.is_none() && layer <10)
419 bin_t curr = bin_t(layer++,0);
421 binmap_t::copy(binmap, ack_hint_out, curr);
422 hint = binmap_t::find_complement(binmap, offer, twist);
426 EXPECT_EQ(bin_t(292),hint);
430 // VOD like. Make first hole at 292. Twisting + patching holes
431 TEST(BinsTest,FindFiltered19) {
433 binmap_t offer, ack_hint_out;
434 for(int i=0; i<999; i++) // offer completely full
435 offer.set(bin_t(0,i));
437 for(int i=0; i<292/2; i++) // request prefix full
438 ack_hint_out.set(bin_t(0,i));
439 for(int i=147; i<999; i+=21) // request postfix sparse
441 for (int x=0; x<8; x++)
442 ack_hint_out.set(bin_t(0,i+x));
448 bin_t::uint_t twist = 0;
449 bin_t hint = bin_t::NONE;
450 while (!hint.contains(bin_t(292)))
456 bin_t curr = bin_t(layer,0);
461 binmap_t::copy(binmap, ack_hint_out, curr);
462 hint = binmap_t::find_complement(binmap, offer, twist);
465 fprintf(stderr,"Found alt ");
469 ack_hint_out.set(hint);
472 char binstr[32],binstr2[32];
473 EXPECT_EQ(bin_t(292),hint);
477 void create_ack_hint_out(binmap_t &ack_hint_out)
479 ack_hint_out.clear();
480 for(int i=0; i<292/2; i++) // request prefix full
481 ack_hint_out.set(bin_t(0,i));
482 for(int i=147; i<999; i+=21) // request postfix sparse
484 for (int x=0; x<8; x++)
485 ack_hint_out.set(bin_t(0,i+x));
491 // VOD like. Make first hole at 292. Twisting + patching holes. Stalled
492 // at Playbackpos, looking increasingly higher layers.
493 TEST(BinsTest,FindFiltered20) {
495 binmap_t offer, ack_hint_out;
496 for(int i=0; i<999; i++) // offer completely full
497 offer.set(bin_t(0,i));
499 create_ack_hint_out(ack_hint_out);
504 bin_t::uint_t twist = 0;
505 bin_t hint = bin_t::NONE;
507 for (layer=0; layer<=9; layer++)
509 fprintf(stderr,"Layer %d\n", layer );
510 while (!hint.contains(bin_t(292)))
516 bin_t curr = bin_t(0,292/2);
517 for (int p=0; p<layer; p++)
518 curr = curr.parent();
521 binmap_t::copy(binmap, ack_hint_out, curr);
522 hint = binmap_t::find_complement(binmap, offer, twist);
525 fprintf(stderr,"Found alt %s ", hint.str(binstr) );
529 ack_hint_out.set(hint);
531 create_ack_hint_out(ack_hint_out);
534 EXPECT_EQ(bin_t(292),hint);
538 void DoFindFilteredRiccardo(bin_t::uint_t twist)
540 binmap_t data, filter;
542 for(int i=0; i<1024; i+=2)
543 filter.set(bin_t(0,i));
551 fprintf(stderr,"Setting from %s ", s.base_left().str(binstr ) );
552 fprintf(stderr,"to %s\n", s.base_right().str(binstr ) );
555 fprintf(stderr,"Searching 0,6 from %s ", s.base_left().str(binstr ) );
556 fprintf(stderr,"to %s\n", s.base_right().str(binstr ) );
558 bin_t got = binmap_t::find_complement(data, filter, s, twist).base_left();
559 EXPECT_EQ(bin_t(0,6),got);
560 EXPECT_EQ(true,s.contains(got));
567 fprintf(stderr,"Setting from %s ", s.base_left().str(binstr ) );
568 fprintf(stderr,"to %s\n", s.base_right().str(binstr ) );
571 fprintf(stderr,"Searching 0,18 from %s ", s.base_left().str(binstr ) );
572 fprintf(stderr,"to %s\n", s.base_right().str(binstr ) );
574 got = binmap_t::find_complement(data, filter, s, twist).base_left();
575 EXPECT_EQ(bin_t(0,18),got);
576 EXPECT_EQ(true,s.contains(got));
583 fprintf(stderr,"Setting from %s ", s.base_left().str(binstr ) );
584 fprintf(stderr,"to %s\n", s.base_right().str(binstr ) );
587 fprintf(stderr,"Searching 0,162 from %s ", s.base_left().str(binstr ) );
588 fprintf(stderr,"to %s\n", s.base_right().str(binstr ) );
590 got = binmap_t::find_complement(data, filter, s, twist).base_left();
591 EXPECT_EQ(bin_t(0,162),got);
592 EXPECT_EQ(true,s.contains(got));
599 fprintf(stderr,"Setting from %s ", s.base_left().str(binstr ) );
600 fprintf(stderr,"to %s\n", s.base_right().str(binstr ) );
603 fprintf(stderr,"Searching 0,168 from %s ", s.base_left().str(binstr ) );
604 fprintf(stderr,"to %s\n", s.base_right().str(binstr ) );
606 got = binmap_t::find_complement(data, filter, s, twist).base_left();
607 EXPECT_EQ(bin_t(0,170),got);
608 EXPECT_EQ(true,s.contains(got));
615 fprintf(stderr,"Setting from %s ", s.base_left().str(binstr ) );
616 fprintf(stderr,"to %s\n", s.base_right().str(binstr ) );
619 fprintf(stderr,"Searching 0,174 from %s ", s.base_left().str(binstr ) );
620 fprintf(stderr,"to %s\n", s.base_right().str(binstr ) );
622 got = binmap_t::find_complement(data, filter, s, twist).base_left();
623 EXPECT_EQ(bin_t(0,174),got);
624 EXPECT_EQ(true,s.contains(got));
631 fprintf(stderr,"Setting from %s ", s.base_left().str(binstr ) );
632 fprintf(stderr,"to %s\n", s.base_right().str(binstr ) );
636 fprintf(stderr,"Searching 0,182 from %s ", s.base_left().str(binstr ) );
637 fprintf(stderr,"to %s\n", s.base_right().str(binstr ) );
639 got = binmap_t::find_complement(data, filter, s, twist).base_left();
640 EXPECT_EQ(bin_t(0,182),got);
641 EXPECT_EQ(true,s.contains(got));
648 fprintf(stderr,"Setting from %s ", s.base_left().str(binstr ) );
649 fprintf(stderr,"to %s\n", s.base_right().str(binstr ) );
652 fprintf(stderr,"Searching 0,184 from %s ", s.base_left().str(binstr ) );
653 fprintf(stderr,"to %s\n", s.base_right().str(binstr ) );
655 got = binmap_t::find_complement(data, filter, s, twist).base_left();
656 EXPECT_EQ(bin_t(0,186),got);
657 EXPECT_EQ(true,s.contains(got));
664 fprintf(stderr,"Setting from %s ", s.base_left().str(binstr ) );
665 fprintf(stderr,"to %s\n", s.base_right().str(binstr ) );
668 fprintf(stderr,"Searching 0,188 from %s ", s.base_left().str(binstr ) );
669 fprintf(stderr,"to %s\n", s.base_right().str(binstr ) );
671 got = binmap_t::find_complement(data, filter, s, twist).base_left();
672 EXPECT_EQ(bin_t(0,190),got);
673 EXPECT_EQ(true,s.contains(got));
677 TEST(BinsTest,FindFilteredRiccardo3) {
679 DoFindFilteredRiccardo(0);
683 TEST(BinsTest,FindFilteredRiccardo3Twist) {
685 DoFindFilteredRiccardo( rand() );
693 int main (int argc, char** argv) {
694 testing::InitGoogleTest(&argc, argv);
695 return RUN_ALL_TESTS();