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