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