1 #include <gtest/gtest.h>
2 #include <stdlib.h>
3 #include <string.h>
4 #include <map>
5 #include <vector>
6 #include <iostream>
7 #include <algorithm>
8 #include <jellyfish/offsets_key_value.hpp>
9
10 namespace {
11 #ifndef UINT64_C
12 #define UINT64_C(x) ((uint64_t)x)
13 #endif
14
15 using namespace jellyfish;
16
17 // Tuple is {key_len, val_len, reprobe_len}. Actual reprobe value is computed from the reprobe_len.
18 class ComputeOffsetsTest : public ::testing::TestWithParam< ::std::tr1::tuple<int,int, int> >
19 {
20 public:
21 Offsets<uint64_t> offsets;
22
ComputeOffsetsTest()23 ComputeOffsetsTest() :
24 offsets(::std::tr1::get<0>(GetParam()), ::std::tr1::get<1>(GetParam()), (1 << ::std::tr1::get<2>(GetParam())) - 2)
25 { }
26
~ComputeOffsetsTest()27 ~ComputeOffsetsTest() { }
28 };
29
test_key_offsets(const Offsets<uint64_t>::offset_t * it,unsigned int k_len,const char * message)30 void test_key_offsets(const Offsets<uint64_t>::offset_t* it, unsigned int k_len, const char* message) {
31 SCOPED_TRACE(message);
32
33 unsigned int val_boff = (it->key.boff + k_len + 1 + (k_len - (bsizeof(uint64_t) - it->key.boff - 1)) / (bsizeof(uint64_t) - 1)) % bsizeof(uint64_t);
34 if(it->key.sb_mask1) { // key between two words
35 EXPECT_LT(sizeof(uint64_t), it->key.boff + k_len) <<
36 ": Key not between words, should not have mask2";
37 EXPECT_EQ(val_boff + (val_boff > 0), it->val.boff) <<
38 ": Invalid value offset";
39 if(it->val.boff == 0)
40 EXPECT_EQ((uint64_t)0, it->key.sb_mask2);
41 } else {
42 if(bsizeof(uint64_t) >= it->key.boff + k_len) {
43 EXPECT_EQ((it->key.boff + k_len) % bsizeof(uint64_t), it->val.boff) <<
44 ": Invalid value offset";
45 } else {
46 EXPECT_TRUE(val_boff % bsizeof(uint64_t) == 0) <<
47 ": Key between words, should have mask2";
48 }
49 }
50 EXPECT_EQ((uint64_t)1 << (it->key.boff - 1), it->key.lb_mask) <<
51 ": Invalid lb_mask";
52 if(it->key.sb_mask1) {
53 EXPECT_EQ(bsizeof(uint64_t) - it->key.boff - 1, it->key.shift) <<
54 ": invalid key shift";
55 EXPECT_EQ(it->key.boff == 1 ? 0 : (uint64_t)1 << (bsizeof(uint64_t) - it->key.boff + 1), 1 + (it->key.mask1 >> (it->key.boff - 1))) <<
56 ": invalid key mask";
57 EXPECT_EQ((uint64_t)1 << it->val.boff, 1 + it->key.mask2) <<
58 ": invalid key mask2";
59 EXPECT_EQ(bsizeof(uint64_t) - it->key.boff - 1, it->key.shift) <<
60 ": invalid key shift";
61 EXPECT_EQ((unsigned int)0, (k_len - (it->key.shift + it->key.cshift)) % (bsizeof(uint64_t) - 1)) <<
62 ": invalid sum of shift and cshift";
63 if(it->key.sb_mask2)
64 EXPECT_EQ(1 + it->key.mask2, (uint64_t)1 << (it->key.cshift + 1)) <<
65 ": invalid key cshift";
66 else
67 EXPECT_EQ((unsigned int)0, it->key.cshift);
68 EXPECT_EQ((uint64_t)1 << 63, it->key.sb_mask1) <<
69 ": invalid key key sb_mask1";
70 EXPECT_EQ(k_len - (bsizeof(uint64_t) - 1 - it->key.boff) >= bsizeof(uint64_t) - 1, it->key.full_words);
71 } else {
72 EXPECT_EQ(0u, it->key.shift) <<
73 ": key shift should be zero, no sb_mask";
74 EXPECT_EQ((uint64_t)1 << (k_len + 1), 1 + (it->key.mask1 >> (it->key.boff - 1))) <<
75 ": invalid key mask, no sb_mask";
76 EXPECT_EQ(0u, it->key.cshift) <<
77 ": key cshift should be zero, no sb_mask";
78 EXPECT_EQ(0u, it->key.sb_mask1 | it->key.sb_mask2) <<
79 ": set bit masks should be 0";
80 }
81 }
82
test_val_offsets(const Offsets<uint64_t>::offset_t * it,unsigned int v_len,const char * message)83 void test_val_offsets(const Offsets<uint64_t>::offset_t* it, unsigned int v_len, const char* message) {
84 SCOPED_TRACE(message);
85
86 if(it->val.mask2) {
87 EXPECT_TRUE(bsizeof(uint64_t) <= it->val.boff + v_len && (it->val.boff + v_len) % bsizeof(uint64_t) != 0) <<
88 ": val not between words, should not have mask2";
89 EXPECT_EQ(bsizeof(uint64_t) - it->val.boff, it->val.shift) <<
90 ": invalid val shift";
91 EXPECT_EQ((uint64_t)1 << (bsizeof(uint64_t) - it->val.boff), 1 + (it->val.mask1 >> it->val.boff)) <<
92 ": invalid val mask1";
93 EXPECT_EQ((uint64_t)1 << (it->val.boff + v_len - bsizeof(uint64_t)), 1 + it->val.mask2) <<
94 ": invalid val mask2";
95 } else {
96 EXPECT_TRUE(bsizeof(uint64_t) > it->val.boff + v_len ||
97 (bsizeof(uint64_t) <= it->val.boff + v_len && (it->val.boff + v_len) % bsizeof(uint64_t) == 0)) <<
98 ": val between words, should have mask2";
99 EXPECT_EQ(v_len, it->val.shift) <<
100 ": invalid val shift";
101 EXPECT_EQ(v_len == bsizeof(uint64_t) ? (uint64_t)0 : (uint64_t)1 << v_len, 1 + (it->val.mask1 >> it->val.boff)) <<
102 ": invalid val mask1";
103 }
104 EXPECT_EQ(v_len, it->val.shift + it->val.cshift);
105 }
106
TEST_P(ComputeOffsetsTest,CheckCoherency)107 TEST_P(ComputeOffsetsTest, CheckCoherency) {
108 const Offsets<uint64_t>::offset_t *it = NULL, *pit = NULL;
109 const Offsets<uint64_t>::offset_t *lit = NULL, *lpit = NULL;
110 unsigned int k_len = ::std::tr1::get<0>(GetParam());
111 unsigned int v_len = ::std::tr1::get<1>(GetParam());
112 unsigned int kv_len = k_len + v_len;
113 unsigned int lk_len = ::std::tr1::get<2>(GetParam());
114 unsigned int lv_len = std::min(kv_len - lk_len, (unsigned int)bsizeof(uint64_t));
115 unsigned int i = 0;
116
117 EXPECT_EQ(lk_len, this->offsets.reprobe_len());
118 EXPECT_EQ((uint64_t)1 << lk_len, this->offsets.reprobe_mask() + 1);
119 EXPECT_EQ(lv_len, this->offsets.lval_len());
120
121
122 for(i = 0; i < bsizeof(uint64_t); i++) {
123 SCOPED_TRACE(::testing::Message() << "key:" << k_len << " val:" << v_len << " i:" << i
124 << " lkey:" << lk_len << " lval:" << lv_len);
125 this->offsets.word_offset(i, &it, &lit, NULL);
126 if(i > 0) {
127 this->offsets.word_offset(i-1, &pit, &lpit, NULL);
128
129 EXPECT_GE(it->key.woff, pit->key.woff) << "Current key offset larger than previous";
130 EXPECT_GE(it->key.woff, pit->val.woff) << "Current key offset larger than previous val offset";
131 EXPECT_TRUE(it->key.woff != pit->key.woff || it->key.boff > pit->key.boff)
132 << "Key bit offset did not increase within a word";
133 EXPECT_EQ((pit->val.boff + v_len) % 64 + 1, it->key.boff) <<
134 ": Invalid jump of bit offset";
135 } // if(i > 0)
136 EXPECT_GE(it->val.woff, it->key.woff) << "Val offset larger than key offset";
137 EXPECT_TRUE(it->key.woff != it->val.woff || it->val.boff > it->key.boff)
138 << "Val bit offset did not increase within a word";
139
140 EXPECT_EQ(it->key.woff, lit->key.woff);
141 EXPECT_EQ(it->key.boff, lit->key.boff);
142 EXPECT_EQ(it->key.lb_mask, lit->key.lb_mask);
143
144 test_key_offsets(it, k_len, "Key offsets");
145 test_key_offsets(lit, lk_len, "Large key offsets");
146
147 test_val_offsets(it, v_len, "Val offsets");
148 test_val_offsets(lit, lv_len, "Large val offsets");
149
150 size_t next_bit = (it->val.boff + v_len) % bsizeof(uint64_t);
151 if(next_bit >= 62 || next_bit == 0)
152 break;
153 }
154
155 EXPECT_EQ(i + 1, this->offsets.block_len());
156 }
157
158 INSTANTIATE_TEST_CASE_P(OffsetsTest, ComputeOffsetsTest, ::testing::Combine(::testing::Range(8, 192, 2), // Key lengths
159 ::testing::Range(0, 64), // Val lengths
160 ::testing::Range(4, 9) // Reprobe lengths
161 ));
162 } // namespace {
163