1 // Copyright (c) 2011-present, Facebook, Inc. All rights reserved.
2 // This source code is licensed under both the GPLv2 (found in the
3 // COPYING file in the root directory) and Apache 2.0 License
4 // (found in the LICENSE.Apache file in the root directory).
5 //
6 // Copyright (c) 2011 The LevelDB Authors. All rights reserved.
7 // Use of this source code is governed by a BSD-style license that can be
8 // found in the LICENSE file. See the AUTHORS file for names of contributors.
9
10 #include "db/dbformat.h"
11 #include "logging/logging.h"
12 #include "test_util/testharness.h"
13
14 namespace ROCKSDB_NAMESPACE {
15
IKey(const std::string & user_key,uint64_t seq,ValueType vt)16 static std::string IKey(const std::string& user_key,
17 uint64_t seq,
18 ValueType vt) {
19 std::string encoded;
20 AppendInternalKey(&encoded, ParsedInternalKey(user_key, seq, vt));
21 return encoded;
22 }
23
Shorten(const std::string & s,const std::string & l)24 static std::string Shorten(const std::string& s, const std::string& l) {
25 std::string result = s;
26 InternalKeyComparator(BytewiseComparator()).FindShortestSeparator(&result, l);
27 return result;
28 }
29
ShortSuccessor(const std::string & s)30 static std::string ShortSuccessor(const std::string& s) {
31 std::string result = s;
32 InternalKeyComparator(BytewiseComparator()).FindShortSuccessor(&result);
33 return result;
34 }
35
TestKey(const std::string & key,uint64_t seq,ValueType vt)36 static void TestKey(const std::string& key,
37 uint64_t seq,
38 ValueType vt) {
39 std::string encoded = IKey(key, seq, vt);
40
41 Slice in(encoded);
42 ParsedInternalKey decoded("", 0, kTypeValue);
43
44 ASSERT_TRUE(ParseInternalKey(in, &decoded));
45 ASSERT_EQ(key, decoded.user_key.ToString());
46 ASSERT_EQ(seq, decoded.sequence);
47 ASSERT_EQ(vt, decoded.type);
48
49 ASSERT_TRUE(!ParseInternalKey(Slice("bar"), &decoded));
50 }
51
52 class FormatTest : public testing::Test {};
53
TEST_F(FormatTest,InternalKey_EncodeDecode)54 TEST_F(FormatTest, InternalKey_EncodeDecode) {
55 const char* keys[] = { "", "k", "hello", "longggggggggggggggggggggg" };
56 const uint64_t seq[] = {
57 1, 2, 3,
58 (1ull << 8) - 1, 1ull << 8, (1ull << 8) + 1,
59 (1ull << 16) - 1, 1ull << 16, (1ull << 16) + 1,
60 (1ull << 32) - 1, 1ull << 32, (1ull << 32) + 1
61 };
62 for (unsigned int k = 0; k < sizeof(keys) / sizeof(keys[0]); k++) {
63 for (unsigned int s = 0; s < sizeof(seq) / sizeof(seq[0]); s++) {
64 TestKey(keys[k], seq[s], kTypeValue);
65 TestKey("hello", 1, kTypeDeletion);
66 }
67 }
68 }
69
TEST_F(FormatTest,InternalKeyShortSeparator)70 TEST_F(FormatTest, InternalKeyShortSeparator) {
71 // When user keys are same
72 ASSERT_EQ(IKey("foo", 100, kTypeValue),
73 Shorten(IKey("foo", 100, kTypeValue),
74 IKey("foo", 99, kTypeValue)));
75 ASSERT_EQ(IKey("foo", 100, kTypeValue),
76 Shorten(IKey("foo", 100, kTypeValue),
77 IKey("foo", 101, kTypeValue)));
78 ASSERT_EQ(IKey("foo", 100, kTypeValue),
79 Shorten(IKey("foo", 100, kTypeValue),
80 IKey("foo", 100, kTypeValue)));
81 ASSERT_EQ(IKey("foo", 100, kTypeValue),
82 Shorten(IKey("foo", 100, kTypeValue),
83 IKey("foo", 100, kTypeDeletion)));
84
85 // When user keys are misordered
86 ASSERT_EQ(IKey("foo", 100, kTypeValue),
87 Shorten(IKey("foo", 100, kTypeValue),
88 IKey("bar", 99, kTypeValue)));
89
90 // When user keys are different, but correctly ordered
91 ASSERT_EQ(IKey("g", kMaxSequenceNumber, kValueTypeForSeek),
92 Shorten(IKey("foo", 100, kTypeValue),
93 IKey("hello", 200, kTypeValue)));
94
95 ASSERT_EQ(IKey("ABC2", kMaxSequenceNumber, kValueTypeForSeek),
96 Shorten(IKey("ABC1AAAAA", 100, kTypeValue),
97 IKey("ABC2ABB", 200, kTypeValue)));
98
99 ASSERT_EQ(IKey("AAA2", kMaxSequenceNumber, kValueTypeForSeek),
100 Shorten(IKey("AAA1AAA", 100, kTypeValue),
101 IKey("AAA2AA", 200, kTypeValue)));
102
103 ASSERT_EQ(
104 IKey("AAA2", kMaxSequenceNumber, kValueTypeForSeek),
105 Shorten(IKey("AAA1AAA", 100, kTypeValue), IKey("AAA4", 200, kTypeValue)));
106
107 ASSERT_EQ(
108 IKey("AAA1B", kMaxSequenceNumber, kValueTypeForSeek),
109 Shorten(IKey("AAA1AAA", 100, kTypeValue), IKey("AAA2", 200, kTypeValue)));
110
111 ASSERT_EQ(IKey("AAA2", kMaxSequenceNumber, kValueTypeForSeek),
112 Shorten(IKey("AAA1AAA", 100, kTypeValue),
113 IKey("AAA2A", 200, kTypeValue)));
114
115 ASSERT_EQ(
116 IKey("AAA1", 100, kTypeValue),
117 Shorten(IKey("AAA1", 100, kTypeValue), IKey("AAA2", 200, kTypeValue)));
118
119 // When start user key is prefix of limit user key
120 ASSERT_EQ(IKey("foo", 100, kTypeValue),
121 Shorten(IKey("foo", 100, kTypeValue),
122 IKey("foobar", 200, kTypeValue)));
123
124 // When limit user key is prefix of start user key
125 ASSERT_EQ(IKey("foobar", 100, kTypeValue),
126 Shorten(IKey("foobar", 100, kTypeValue),
127 IKey("foo", 200, kTypeValue)));
128 }
129
TEST_F(FormatTest,InternalKeyShortestSuccessor)130 TEST_F(FormatTest, InternalKeyShortestSuccessor) {
131 ASSERT_EQ(IKey("g", kMaxSequenceNumber, kValueTypeForSeek),
132 ShortSuccessor(IKey("foo", 100, kTypeValue)));
133 ASSERT_EQ(IKey("\xff\xff", 100, kTypeValue),
134 ShortSuccessor(IKey("\xff\xff", 100, kTypeValue)));
135 }
136
TEST_F(FormatTest,IterKeyOperation)137 TEST_F(FormatTest, IterKeyOperation) {
138 IterKey k;
139 const char p[] = "abcdefghijklmnopqrstuvwxyz";
140 const char q[] = "0123456789";
141
142 ASSERT_EQ(std::string(k.GetUserKey().data(), k.GetUserKey().size()),
143 std::string(""));
144
145 k.TrimAppend(0, p, 3);
146 ASSERT_EQ(std::string(k.GetUserKey().data(), k.GetUserKey().size()),
147 std::string("abc"));
148
149 k.TrimAppend(1, p, 3);
150 ASSERT_EQ(std::string(k.GetUserKey().data(), k.GetUserKey().size()),
151 std::string("aabc"));
152
153 k.TrimAppend(0, p, 26);
154 ASSERT_EQ(std::string(k.GetUserKey().data(), k.GetUserKey().size()),
155 std::string("abcdefghijklmnopqrstuvwxyz"));
156
157 k.TrimAppend(26, q, 10);
158 ASSERT_EQ(std::string(k.GetUserKey().data(), k.GetUserKey().size()),
159 std::string("abcdefghijklmnopqrstuvwxyz0123456789"));
160
161 k.TrimAppend(36, q, 1);
162 ASSERT_EQ(std::string(k.GetUserKey().data(), k.GetUserKey().size()),
163 std::string("abcdefghijklmnopqrstuvwxyz01234567890"));
164
165 k.TrimAppend(26, q, 1);
166 ASSERT_EQ(std::string(k.GetUserKey().data(), k.GetUserKey().size()),
167 std::string("abcdefghijklmnopqrstuvwxyz0"));
168
169 // Size going up, memory allocation is triggered
170 k.TrimAppend(27, p, 26);
171 ASSERT_EQ(std::string(k.GetUserKey().data(), k.GetUserKey().size()),
172 std::string("abcdefghijklmnopqrstuvwxyz0"
173 "abcdefghijklmnopqrstuvwxyz"));
174 }
175
TEST_F(FormatTest,UpdateInternalKey)176 TEST_F(FormatTest, UpdateInternalKey) {
177 std::string user_key("abcdefghijklmnopqrstuvwxyz");
178 uint64_t new_seq = 0x123456;
179 ValueType new_val_type = kTypeDeletion;
180
181 std::string ikey;
182 AppendInternalKey(&ikey, ParsedInternalKey(user_key, 100U, kTypeValue));
183 size_t ikey_size = ikey.size();
184 UpdateInternalKey(&ikey, new_seq, new_val_type);
185 ASSERT_EQ(ikey_size, ikey.size());
186
187 Slice in(ikey);
188 ParsedInternalKey decoded;
189 ASSERT_TRUE(ParseInternalKey(in, &decoded));
190 ASSERT_EQ(user_key, decoded.user_key.ToString());
191 ASSERT_EQ(new_seq, decoded.sequence);
192 ASSERT_EQ(new_val_type, decoded.type);
193 }
194
TEST_F(FormatTest,RangeTombstoneSerializeEndKey)195 TEST_F(FormatTest, RangeTombstoneSerializeEndKey) {
196 RangeTombstone t("a", "b", 2);
197 InternalKey k("b", 3, kTypeValue);
198 const InternalKeyComparator cmp(BytewiseComparator());
199 ASSERT_LT(cmp.Compare(t.SerializeEndKey(), k), 0);
200 }
201
202 } // namespace ROCKSDB_NAMESPACE
203
main(int argc,char ** argv)204 int main(int argc, char** argv) {
205 ::testing::InitGoogleTest(&argc, argv);
206 return RUN_ALL_TESTS();
207 }
208