5 * Created by Victor Grishchenko on 3/22/09.
6 * Copyright 2009-2012 TECHNISCHE UNIVERSITEIT DELFT. All rights reserved.
14 #include <gtest/gtest.h>
17 using namespace swift;
20 TEST(BinsTest,Routines) {
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);
27 uint32_t split = binmap_t::split16to32(correct);
28 EXPECT_EQ(cell,split);
30 EXPECT_EQ(binmap_t::NOJOIN,binmap_t::join32to16(cell|4));
36 TEST(BinsTest,SetGet) {
39 bin_t b3(1,0), b2(0,1), b4(0,2), b6(1,1), b7(2,0);
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));
54 EXPECT_TRUE(bs.is_filled(bin_t(2,0)));
59 TEST(BinsTest,Iterator) {
62 iterator i(&b,bin_t(0,0),false);
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);
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);
79 TEST(BinsTest,Chess) {
81 for(int i=0; i<16; i++) {
83 chess16.set(bin_t(0,i));
85 chess16.reset(bin_t(0,i));
89 for(int i=0; i<16; i++) {
91 EXPECT_TRUE(chess16.is_filled(bin_t(0,i)));
93 EXPECT_TRUE(chess16.is_empty(bin_t(0,i)));
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)));
102 chess16.set(bin_t(4,1));
103 EXPECT_TRUE(chess16.is_filled(bin_t(5,0)));
106 TEST(BinsTest,Staircase) {
108 const int TOPLAYR = 44;
110 for(int i=0;i<TOPLAYR;i++)
111 staircase.set(bin_t(i,1));
113 EXPECT_FALSE(staircase.is_filled(bin_t(TOPLAYR,0)));
114 EXPECT_FALSE(staircase.is_empty(bin_t(TOPLAYR,0)));
116 staircase.set(bin_t(0,0));
117 EXPECT_TRUE(staircase.is_filled(bin_t(TOPLAYR,0)));
121 TEST(BinsTest,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)));
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);
147 TEST(BinsTest,Stripes) {
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));
155 uint64_t *stripes = zebra.get_stripes(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]);
171 TEST(BinsTest,StripesAgg) {
174 zebra.set(bin_t(0,1));
175 zebra.set(bin_t(0,2));
177 uint64_t *stripes = zebra.get_stripes(count);
179 EXPECT_EQ(0,stripes[0]);
180 EXPECT_EQ(1,stripes[1]);
181 EXPECT_EQ(3,stripes[2]);
187 TEST(BinsTest,Alloc) {
194 EXPECT_EQ(1,b.cells_number());
199 TEST(BinsTest,Remove) {
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)));
213 binmap_t b16, b1024, b8192;
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));
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)));
230 b8192.set(bin_t(2,3));
232 EXPECT_TRUE(b16.is_empty(bin_t(2,3)));
233 EXPECT_TRUE(b16.is_filled(bin_t(2,2)));
238 TEST(BinsTest,FindFiltered) {
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));
249 bin_t x = binmap_t::find_complement(data, filter, bin_t(4,0), 0);
250 EXPECT_EQ(bin_t(0,12),x);
255 TEST(BinsTest, Cover) {
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)));
264 //EXPECT_EQ(bin64_t::ALL,b.cover(bin64_t(0,30)));
269 TEST(BinsTest,FindFiltered2) {
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());
283 TEST(BinsTest,CopyRange) {
285 data.set(bin_t(2,0));
286 data.set(bin_t(2,2));
287 data.set(bin_t(1,7));
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)));
302 TEST(BinsTest, Mass) {
306 EXPECT_EQ(63,b.mass());
307 EXPECT_FALSE(b.is_empty());
309 EXPECT_TRUE(b.is_empty());
310 EXPECT_EQ(0,b.mass());
313 for(int i=0; i<50; i++)
314 b50.set(bin_t(4,i*2));
315 EXPECT_EQ(50<<4,b50.mass());
320 TEST(BinsTest,Twist) {
323 EXPECT_TRUE(b.is_filled(bin_t(3,2)));
324 EXPECT_TRUE(b.is_empty(bin_t(3,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))
331 tw = tw.twisted(1<<3);
332 EXPECT_EQ(bin_t(3,2),tw);
334 EXPECT_TRUE(b.is_filled(bin_t(3,2)));
335 EXPECT_TRUE(b.is_empty(bin_t(3,3)));
339 TEST(BinsTest,SeqLength) {
345 EXPECT_EQ(11,b.find_empty().base_offset());
348 TEST(BinsTest,EmptyFilled) {
349 // 1112 3312 2111 ....
352 EXPECT_TRUE(b.is_empty(bin_t::ALL));
360 EXPECT_FALSE(b.is_empty(bin_t::ALL));
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)));
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)));
378 EXPECT_TRUE(b.is_filled(bin_t(2,1)));
381 TEST(BinheapTest,Eat) {
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());
393 for (int i=0; i<64; i++) {
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());
402 /*TEST(BinsTest,RangeOpTest) {
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)));
416 f.range_remove(s,bin_t(2,1));
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)));
431 TEST(BinsTest,CoarseBitmap) {
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);
440 b.to_coarse_bitmap(i16,bin_t(15,0),10);
441 EXPECT_EQ((1<<16)-1,i32);
444 rough.set(bin_t(1,0));
445 rough.set(bin_t(0,2));
447 rough.to_coarse_bitmap(i16,bin_t(6,0),1);
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));
459 ladder.to_coarse_bitmap(i16,bin_t(8,0),3);
460 EXPECT_EQ(0x00ff0f34,i32);
466 bin.to_coarse_bitmap(i16,bin_t(4,0),0);
467 EXPECT_EQ((1<<9)-1,i32);
470 bin.to_coarse_bitmap(i16,bin_t(7,0),3);
474 bin.to_coarse_bitmap(i16,bin_t(4,0),3);
478 bin.to_coarse_bitmap(i16,bin_t(2,0),1);
485 bm.to_coarse_bitmap((uint16_t*)&bigint,bin_t(6,0),0);
486 EXPECT_EQ( 0xffffffffffffffffULL, bigint );
491 /*TEST(BinsTest,AddSub) {
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));
501 ASSERT_FALSE(b.contains(12));
502 ASSERT_FALSE(b.contains(14));
503 ASSERT_FALSE(b.contains(11));
504 ASSERT_TRUE(b.contains(10));
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]);
516 TEST(BinsTest,Performance) {
520 double b_time, s_time;
524 for(int i=1; i<(1<<20); i++)
526 //b_size = b.bits.size();
528 b_time = ((double) (end - start)) / CLOCKS_PER_SEC;
529 //ASSERT_EQ(1,b.bits.size());
532 for(int i=1; i<(1<<20); i++)
536 s_time = ((double) (end - start)) / CLOCKS_PER_SEC;
538 printf("bins: %f (%i), set: %f (%i)\n",b_time,b_size,s_time,s_size);
541 int main (int argc, char** argv) {
542 testing::InitGoogleTest(&argc, argv);
543 return RUN_ALL_TESTS();