src/libswift_udp/tests/binstest2.cpp

   1 /*
   2  *  binstest2.cpp
   3  *  serp++
   4  *
   5  *  Created by Victor Grishchenko on 3/22/09.
   6  *  Copyright 2009-2012 TECHNISCHE UNIVERSITEIT DELFT. All rights reserved.
   7  *
   8  */
   9 #include "binmap.h"
  10 #include "binheap.h"
  11
  12 #include <time.h>
  13 #include <set>
  14 #include <gtest/gtest.h>
  15
  16
  17 using namespace swift;
  18
  19 /*
  20 TEST(BinsTest,Routines) {
  21
  22     uint32_t cell = (3<<10) | (3<<14) | (3<<0);
  23     uint16_t correct = (1<<5) | (1<<7) | (1<<0);
  24     uint16_t joined  = binmap_t::join32to16(cell);
  25     EXPECT_EQ(correct,joined);
  26
  27     uint32_t split = binmap_t::split16to32(correct);
  28     EXPECT_EQ(cell,split);
  29
  30     EXPECT_EQ(binmap_t::NOJOIN,binmap_t::join32to16(cell|4));
  31
  32 }
  33 */
  34
  35
  36 TEST(BinsTest,SetGet) {
  37
  38     binmap_t bs;
  39     bin_t b3(1,0), b2(0,1), b4(0,2), b6(1,1), b7(2,0);
  40     bs.set(b3);
  41     //bs.dump("set done");
  42     EXPECT_TRUE(bs.is_filled(b3));
  43     //bs.dump("set checkd");
  44     EXPECT_TRUE(bs.is_filled(b2));
  45     //bs.dump("get b2 done");
  46     EXPECT_TRUE(bs.is_filled(b3));
  47     //bs.dump("get b3 done");
  48     EXPECT_TRUE(bs.is_empty(b4));
  49     EXPECT_TRUE(bs.is_empty(b6));
  50     EXPECT_FALSE(bs.is_filled(b7));
  51     EXPECT_FALSE(bs.is_empty(b7));
  52     EXPECT_TRUE(bs.is_filled(b3));
  53     bs.set(bin_t(1,1));
  54     EXPECT_TRUE(bs.is_filled(bin_t(2,0)));
  55
  56 }
  57
  58 /*
  59 TEST(BinsTest,Iterator) {
  60     binmap_t b;
  61     b.set(bin_t(3,1));
  62     iterator i(&b,bin_t(0,0),false);
  63     while (!i.solid())
  64         i.left();
  65     EXPECT_EQ(bin_t(3,0),i.bin());
  66     EXPECT_EQ(false,i.deep());
  67     EXPECT_EQ(true,i.solid());
  68     EXPECT_EQ(binmap_t::EMPTY,*i);
  69     i.next();
  70     EXPECT_EQ(bin_t(3,1),i.bin());
  71     EXPECT_EQ(false,i.deep());
  72     EXPECT_EQ(true,i.solid());
  73     EXPECT_EQ(binmap_t::FILLED,*i);
  74     i.next();
  75     EXPECT_TRUE(i.end());
  76 }
  77 */
  78
  79 TEST(BinsTest,Chess) {
  80     binmap_t chess16;
  81     for(int i=0; i<16; i++) {
  82         if (i&1) {
  83             chess16.set(bin_t(0,i));
  84         } else {
  85             chess16.reset(bin_t(0,i));
  86         }
  87     }
  88
  89     for(int i=0; i<16; i++) {
  90         if (i&1) {
  91             EXPECT_TRUE(chess16.is_filled(bin_t(0,i)));
  92         } else {
  93             EXPECT_TRUE(chess16.is_empty(bin_t(0,i)));
  94         }
  95     }
  96     EXPECT_FALSE(chess16.is_empty(bin_t(4,0)));
  97     for(int i=0; i<16; i+=2)
  98         chess16.set(bin_t(0,i));
  99     EXPECT_TRUE(chess16.is_filled(bin_t(4,0)));
 100     EXPECT_TRUE(chess16.is_filled(bin_t(2,3)));
 101
 102     chess16.set(bin_t(4,1));
 103     EXPECT_TRUE(chess16.is_filled(bin_t(5,0)));
 104 }
 105
 106 TEST(BinsTest,Staircase) {
 107
 108     const int TOPLAYR = 44;
 109     binmap_t staircase;
 110     for(int i=0;i<TOPLAYR;i++)
 111         staircase.set(bin_t(i,1));
 112
 113     EXPECT_FALSE(staircase.is_filled(bin_t(TOPLAYR,0)));
 114     EXPECT_FALSE(staircase.is_empty(bin_t(TOPLAYR,0)));
 115
 116     staircase.set(bin_t(0,0));
 117     EXPECT_TRUE(staircase.is_filled(bin_t(TOPLAYR,0)));
 118
 119 }
 120
 121 TEST(BinsTest,Hole) {
 122
 123     binmap_t hole;
 124     hole.set(bin_t(8,0));
 125     hole.reset(bin_t(6,1));
 126     hole.reset(bin_t(6,2));
 127     EXPECT_TRUE(hole.is_filled(bin_t(6,0)));
 128     EXPECT_TRUE(hole.is_filled(bin_t(6,3)));
 129     EXPECT_FALSE(hole.is_filled(bin_t(8,0)));
 130     EXPECT_FALSE(hole.is_empty(bin_t(8,0)));
 131     EXPECT_TRUE(hole.is_empty(bin_t(6,1)));
 132
 133 }
 134
 135 TEST(BinsTest,Find){
 136
 137     binmap_t hole;
 138     hole.set(bin_t(4,0));
 139     hole.reset(bin_t(1,1));
 140     hole.reset(bin_t(0,7));
 141     bin_t f = hole.find_empty().base_left();
 142     EXPECT_EQ(bin_t(0,2),f);
 143
 144 }
 145
 146 /*
 147 TEST(BinsTest,Stripes) {
 148
 149     binmap_t zebra;
 150     zebra.set(bin_t(5,0));
 151     zebra.reset(bin_t(3,1));
 152     zebra.reset(bin_t(1,12));
 153     zebra.reset(bin_t(1,14));
 154     int count;
 155     uint64_t *stripes = zebra.get_stripes(count);
 156     EXPECT_EQ(9,count);
 157     EXPECT_EQ(0,stripes[0]);
 158     EXPECT_EQ(0,stripes[1]);
 159     EXPECT_EQ(8,stripes[2]);
 160     EXPECT_EQ(16,stripes[3]);
 161     EXPECT_EQ(24,stripes[4]);
 162     EXPECT_EQ(26,stripes[5]);
 163     EXPECT_EQ(28,stripes[6]);
 164     EXPECT_EQ(30,stripes[7]);
 165     EXPECT_EQ(32,stripes[8]);
 166     free(stripes);
 167
 168 }
 169 */
 170 /*
 171 TEST(BinsTest,StripesAgg) {
 172
 173     binmap_t zebra;
 174     zebra.set(bin_t(0,1));
 175     zebra.set(bin_t(0,2));
 176     int count;
 177     uint64_t *stripes = zebra.get_stripes(count);
 178     EXPECT_EQ(3,count);
 179     EXPECT_EQ(0,stripes[0]);
 180     EXPECT_EQ(1,stripes[1]);
 181     EXPECT_EQ(3,stripes[2]);
 182     free(stripes);
 183
 184 }
 185 */
 186
 187 TEST(BinsTest,Alloc) {
 188
 189     binmap_t b;
 190     b.set(bin_t(1,0));
 191     b.set(bin_t(1,1));
 192     b.reset(bin_t(1,0));
 193     b.reset(bin_t(1,1));
 194     EXPECT_EQ(1,b.cells_number());
 195
 196 }
 197
 198 /*
 199 TEST(BinsTest,Remove) {
 200
 201     binmap_t b;
 202     b.set(bin_t(5,0));
 203     binmap_t c;
 204     c.set(bin_t(2,0));
 205     c.set(bin_t(2,2));
 206     b.remove(c);
 207     EXPECT_TRUE(b.is_empty(bin_t(2,0)));
 208     EXPECT_TRUE(b.is_filled(bin_t(2,1)));
 209     EXPECT_TRUE(b.is_empty(bin_t(2,2)));
 210     EXPECT_TRUE(b.is_filled(bin_t(2,3)));
 211     EXPECT_TRUE(b.is_filled(bin_t(4,1)));
 212
 213     binmap_t b16, b1024, b8192;
 214     b16.set(bin_t(3,1));
 215     b1024.set(bin_t(3,1));
 216     b1024.set(bin_t(4,2));
 217     b1024.set(bin_t(8,3));
 218     b8192.set(bin_t(8,3));
 219     b8192.set(bin_t(10,7));
 220
 221     b1024.remove(b16);
 222     b1024.remove(b8192);
 223
 224     EXPECT_TRUE(b1024.is_empty(bin_t(3,1)));
 225     EXPECT_TRUE(b1024.is_empty(bin_t(5,0)));
 226     EXPECT_TRUE(b1024.is_empty(bin_t(9,1)));
 227     EXPECT_TRUE(b1024.is_empty(bin_t(12,1)));
 228     EXPECT_TRUE(b1024.is_filled(bin_t(4,2)));
 229
 230     b8192.set(bin_t(2,3));
 231     b16.remove(b8192);
 232     EXPECT_TRUE(b16.is_empty(bin_t(2,3)));
 233     EXPECT_TRUE(b16.is_filled(bin_t(2,2)));
 234
 235 }
 236 */
 237
 238 TEST(BinsTest,FindFiltered) {
 239
 240     binmap_t data, filter;
 241     data.set(bin_t(2,0));
 242     data.set(bin_t(2,2));
 243     data.set(bin_t(1,7));
 244     filter.set(bin_t(4,0));
 245     filter.reset(bin_t(2,1));
 246     filter.reset(bin_t(1,4));
 247     filter.reset(bin_t(0,13));
 248
 249     bin_t x = binmap_t::find_complement(data, filter, bin_t(4,0), 0);
 250     EXPECT_EQ(bin_t(0,12),x);
 251
 252 }
 253
 254
 255 TEST(BinsTest, Cover) {
 256
 257     binmap_t b;
 258     b.set(bin_t(2,0));
 259     b.set(bin_t(4,1));
 260     EXPECT_EQ(bin_t(4,1),b.cover(bin_t(0,30)));
 261     EXPECT_EQ(bin_t(2,0),b.cover(bin_t(0,3)));
 262     EXPECT_EQ(bin_t(2,0),b.cover(bin_t(2,0)));
 263     //binmap_t c;
 264     //EXPECT_EQ(bin64_t::ALL,b.cover(bin64_t(0,30)));
 265
 266 }
 267
 268
 269 TEST(BinsTest,FindFiltered2) {
 270
 271     binmap_t data, filter;
 272     for(int i=0; i<1024; i+=2)
 273         data.set(bin_t(0,i));
 274     for(int j=0; j<1024; j+=2)
 275         filter.set(bin_t(0,j));
 276     data.reset(bin_t(0,500));
 277     EXPECT_EQ(bin_t(0,500),binmap_t::find_complement(data, filter, bin_t(10,0), 0).base_left());
 278     data.set(bin_t(0,500));
 279     EXPECT_EQ(bin_t::NONE,binmap_t::find_complement(data, filter, bin_t(10,0), 0).base_left());
 280
 281 }
 282
 283 TEST(BinsTest,CopyRange) {
 284     binmap_t data, add;
 285     data.set(bin_t(2,0));
 286     data.set(bin_t(2,2));
 287     data.set(bin_t(1,7));
 288     add.set(bin_t(2,1));
 289     add.set(bin_t(1,4));
 290     add.set(bin_t(0,13));
 291     add.set(bin_t(5,118));
 292     binmap_t::copy(data, add, bin_t(3,0));
 293     EXPECT_FALSE(data.is_empty(bin_t(3,0)));
 294     EXPECT_FALSE(data.is_filled(bin_t(3,0)));
 295     EXPECT_TRUE(data.is_empty(bin_t(2,0)));
 296     EXPECT_TRUE(data.is_filled(bin_t(2,1)));
 297     EXPECT_TRUE(data.is_empty(bin_t(1,6)));
 298     EXPECT_TRUE(data.is_filled(bin_t(1,7)));
 299 }
 300
 301 /*
 302 TEST(BinsTest, Mass) {
 303     binmap_t b;
 304     b.set(bin_t(6,0));
 305     b.reset(bin_t(0,0));
 306     EXPECT_EQ(63,b.mass());
 307     EXPECT_FALSE(b.is_empty());
 308     b.clear();
 309     EXPECT_TRUE(b.is_empty());
 310     EXPECT_EQ(0,b.mass());
 311
 312     binmap_t b50;
 313     for(int i=0; i<50; i++)
 314         b50.set(bin_t(4,i*2));
 315     EXPECT_EQ(50<<4,b50.mass());
 316 }
 317 */
 318
 319 /*
 320 TEST(BinsTest,Twist) {
 321     binmap_t b;
 322     b.set(bin_t(3,2));
 323     EXPECT_TRUE(b.is_filled(bin_t(3,2)));
 324     EXPECT_TRUE(b.is_empty(bin_t(3,3)));
 325     b.twist(1<<3);
 326     EXPECT_TRUE(b.is_filled(bin_t(3,3)));
 327     EXPECT_TRUE(b.is_empty(bin_t(3,2)));
 328     bin_t tw = b.find(bin_t(5,0),binmap_t::FILLED);
 329     while (tw.base_length()>(1<<3))
 330         tw = tw.left();
 331     tw = tw.twisted(1<<3);
 332     EXPECT_EQ(bin_t(3,2),tw);
 333     b.twist(0);
 334     EXPECT_TRUE(b.is_filled(bin_t(3,2)));
 335     EXPECT_TRUE(b.is_empty(bin_t(3,3)));
 336 }
 337 */
 338
 339 TEST(BinsTest,SeqLength) {
 340     binmap_t b;
 341     b.set(bin_t(3,0));
 342     b.set(bin_t(1,4));
 343     b.set(bin_t(0,10));
 344     b.set(bin_t(3,2));
 345     EXPECT_EQ(11,b.find_empty().base_offset());
 346 }
 347
 348 TEST(BinsTest,EmptyFilled) {
 349     // 1112 3312  2111 ....
 350     binmap_t b;
 351
 352     EXPECT_TRUE(b.is_empty(bin_t::ALL));
 353
 354     b.set(bin_t(1,0));
 355     b.set(bin_t(0,2));
 356     b.set(bin_t(0,6));
 357     b.set(bin_t(1,5));
 358     b.set(bin_t(0,9));
 359
 360     EXPECT_FALSE(b.is_empty(bin_t::ALL));
 361
 362     EXPECT_TRUE(b.is_empty(bin_t(2,3)));
 363     EXPECT_FALSE(b.is_filled(bin_t(2,3)));
 364     //EXPECT_TRUE(b.is_solid(bin_t(2,3),binmap_t::MIXED));
 365     EXPECT_TRUE(b.is_filled(bin_t(1,0)));
 366     EXPECT_TRUE(b.is_filled(bin_t(1,5)));
 367     EXPECT_FALSE(b.is_filled(bin_t(1,3)));
 368
 369     b.set(bin_t(0,3));
 370     b.set(bin_t(0,7));
 371     b.set(bin_t(0,8));
 372
 373     EXPECT_TRUE(b.is_filled(bin_t(2,0)));
 374     EXPECT_TRUE(b.is_filled(bin_t(2,2)));
 375     EXPECT_FALSE(b.is_filled(bin_t(2,1)));
 376
 377     b.set(bin_t(1,2));
 378     EXPECT_TRUE(b.is_filled(bin_t(2,1)));
 379 }
 380
 381 TEST(BinheapTest,Eat) {
 382
 383     binheap b;
 384     b.push(bin_t(0,1));
 385     b.push(bin_t(0,3));
 386     b.push(bin_t(2,0));
 387     b.push(bin_t(2,4));
 388
 389     EXPECT_EQ(bin_t(2,0),b.pop());
 390     EXPECT_EQ(bin_t(2,4),b.pop());
 391     EXPECT_EQ(bin_t::NONE,b.pop());
 392
 393     for (int i=0; i<64; i++) {
 394         b.push(bin_t(0,i));
 395     }
 396     b.push(bin_t(5,0));
 397     EXPECT_EQ(bin_t(5,0),b.pop());
 398     for (int i=32; i<64; i++)
 399         EXPECT_EQ(bin_t(0,i),b.pop());
 400 }
 401
 402 /*TEST(BinsTest,RangeOpTest) {
 403     binmap_t a, b;
 404     a.set(bin_t(0,0));
 405     a.set(bin_t(0,2));
 406     b.set(bin_t(0,1));
 407     b.set(bin_t(0,3));
 408     a.range_or(b,bin_t(1,0));
 409     EXPECT_TRUE(a.is_filled(bin_t(1,0)));
 410     EXPECT_FALSE(a.is_filled(bin_t(1,1)));
 411
 412     binmap_t f, s;
 413     f.set(bin_t(3,0));
 414     s.set(bin_t(0,1));
 415     s.set(bin_t(0,4));
 416     f.range_remove(s,bin_t(2,1));
 417
 418     EXPECT_TRUE(f.is_filled(bin_t(2,0)));
 419     EXPECT_FALSE(f.is_filled(bin_t(0,4)));
 420     EXPECT_TRUE(f.is_filled(bin_t(0,5)));
 421
 422     binmap_t z, x;
 423     z.set(bin_t(1,0));
 424     z.set(bin_t(1,2));
 425     x.set(bin_t(0,1));
 426     x.set(bin_t(0,1));
 427 }
 428 */
 429
 430 /*
 431 TEST(BinsTest,CoarseBitmap) {
 432     binmap_t b;
 433     b.set(bin_t(4,0));
 434     union {uint16_t i16[2]; uint32_t i32;};
 435     b.to_coarse_bitmap(i16,bin_t(5,0),0);
 436     EXPECT_EQ((1<<16)-1,i32);
 437
 438     b.set(bin_t(14,0));
 439     i32=0;
 440     b.to_coarse_bitmap(i16,bin_t(15,0),10);
 441     EXPECT_EQ((1<<16)-1,i32);
 442
 443     binmap_t rough;
 444     rough.set(bin_t(1,0));
 445     rough.set(bin_t(0,2));
 446     i32=0;
 447     rough.to_coarse_bitmap(i16,bin_t(6,0),1);
 448     EXPECT_EQ(1,i32);
 449
 450     binmap_t ladder;
 451     ladder.set(bin_t(6,2));
 452     ladder.set(bin_t(5,2));
 453     ladder.set(bin_t(4,2));
 454     ladder.set(bin_t(3,2));
 455     ladder.set(bin_t(2,2));
 456     ladder.set(bin_t(1,2));
 457     ladder.set(bin_t(0,2));
 458     i32=0;
 459     ladder.to_coarse_bitmap(i16,bin_t(8,0),3);
 460     EXPECT_EQ(0x00ff0f34,i32);
 461
 462     binmap_t bin;
 463     bin.set(bin_t(3,0));
 464     bin.set(bin_t(0,8));
 465     i32 = 0;
 466     bin.to_coarse_bitmap(i16,bin_t(4,0),0);
 467     EXPECT_EQ((1<<9)-1,i32);
 468
 469     i32 = 0;
 470     bin.to_coarse_bitmap(i16,bin_t(7,0),3);
 471     EXPECT_EQ(1,i32);
 472
 473     i32 = 0;
 474     bin.to_coarse_bitmap(i16,bin_t(4,0),3);
 475     EXPECT_EQ(1,i32);
 476
 477     i32 = 0;
 478     bin.to_coarse_bitmap(i16,bin_t(2,0),1);
 479     EXPECT_EQ(3,i32&3);
 480
 481     uint64_t bigint;
 482     bigint = 0;
 483     binmap_t bm;
 484     bm.set(bin_t(6,0));
 485     bm.to_coarse_bitmap((uint16_t*)&bigint,bin_t(6,0),0);
 486     EXPECT_EQ( 0xffffffffffffffffULL, bigint );
 487
 488 }
 489 */
 490
 491 /*TEST(BinsTest,AddSub) {
 492         binmap_t b;
 493         b|=15;
 494         b-=1;
 495         ASSERT_TRUE(b.contains(2));
 496         ASSERT_TRUE(b.contains(14));
 497         ASSERT_FALSE(b.contains(3));
 498         ASSERT_FALSE(b.contains(22));
 499         ASSERT_TRUE(b.contains(12));
 500         b-=13;
 501         ASSERT_FALSE(b.contains(12));
 502         ASSERT_FALSE(b.contains(14));
 503         ASSERT_FALSE(b.contains(11));
 504         ASSERT_TRUE(b.contains(10));
 505 }
 506
 507
 508 TEST(BinsTest,Peaks) {
 509         bin::vec peaks = bin::peaks(11);
 510         ASSERT_EQ(3,peaks.size());
 511         ASSERT_EQ(15,peaks[0]);
 512         ASSERT_EQ(18,peaks[1]);
 513         ASSERT_EQ(19,peaks[2]);
 514 }
 515
 516 TEST(BinsTest,Performance) {
 517         binmap_t b;
 518         std::set<int> s;
 519         clock_t start, end;
 520         double b_time, s_time;
 521         int b_size, s_size;
 522
 523         start = clock();
 524         for(int i=1; i<(1<<20); i++)
 525                 b |= bin(i);
 526         //b_size = b.bits.size();
 527         end = clock();
 528         b_time = ((double) (end - start)) / CLOCKS_PER_SEC;
 529         //ASSERT_EQ(1,b.bits.size());
 530
 531         start = clock();
 532         for(int i=1; i<(1<<20); i++)
 533                 s.insert(i);
 534         s_size = s.size();
 535         end = clock();
 536         s_time = ((double) (end - start)) / CLOCKS_PER_SEC;
 537
 538         printf("bins: %f (%i), set: %f (%i)\n",b_time,b_size,s_time,s_size);
 539 }*/
 540
 541 int main (int argc, char** argv) {
 542         testing::InitGoogleTest(&argc, argv);
 543         return RUN_ALL_TESTS();
 544 }