]>
Commit | Line | Data |
---|---|---|
494da23a TL |
1 | // Copyright (c) 2018-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 | #include "db/range_tombstone_fragmenter.h" | |
7 | ||
8 | #include "db/db_test_util.h" | |
1e59de90 | 9 | #include "db/dbformat.h" |
494da23a | 10 | #include "rocksdb/comparator.h" |
f67539c2 | 11 | #include "test_util/testutil.h" |
1e59de90 | 12 | #include "util/vector_iterator.h" |
494da23a | 13 | |
f67539c2 | 14 | namespace ROCKSDB_NAMESPACE { |
494da23a TL |
15 | |
16 | class RangeTombstoneFragmenterTest : public testing::Test {}; | |
17 | ||
18 | namespace { | |
19 | ||
20 | static auto bytewise_icmp = InternalKeyComparator(BytewiseComparator()); | |
21 | ||
22 | std::unique_ptr<InternalIterator> MakeRangeDelIter( | |
23 | const std::vector<RangeTombstone>& range_dels) { | |
24 | std::vector<std::string> keys, values; | |
25 | for (const auto& range_del : range_dels) { | |
26 | auto key_and_value = range_del.Serialize(); | |
27 | keys.push_back(key_and_value.first.Encode().ToString()); | |
28 | values.push_back(key_and_value.second.ToString()); | |
29 | } | |
1e59de90 TL |
30 | return std::unique_ptr<VectorIterator>( |
31 | new VectorIterator(keys, values, &bytewise_icmp)); | |
494da23a TL |
32 | } |
33 | ||
34 | void CheckIterPosition(const RangeTombstone& tombstone, | |
35 | const FragmentedRangeTombstoneIterator* iter) { | |
36 | // Test InternalIterator interface. | |
37 | EXPECT_EQ(tombstone.start_key_, ExtractUserKey(iter->key())); | |
38 | EXPECT_EQ(tombstone.end_key_, iter->value()); | |
39 | EXPECT_EQ(tombstone.seq_, iter->seq()); | |
40 | ||
41 | // Test FragmentedRangeTombstoneIterator interface. | |
42 | EXPECT_EQ(tombstone.start_key_, iter->start_key()); | |
43 | EXPECT_EQ(tombstone.end_key_, iter->end_key()); | |
44 | EXPECT_EQ(tombstone.seq_, GetInternalKeySeqno(iter->key())); | |
45 | } | |
46 | ||
47 | void VerifyFragmentedRangeDels( | |
48 | FragmentedRangeTombstoneIterator* iter, | |
49 | const std::vector<RangeTombstone>& expected_tombstones) { | |
50 | iter->SeekToFirst(); | |
51 | for (size_t i = 0; i < expected_tombstones.size(); i++, iter->Next()) { | |
52 | ASSERT_TRUE(iter->Valid()); | |
53 | CheckIterPosition(expected_tombstones[i], iter); | |
54 | } | |
55 | EXPECT_FALSE(iter->Valid()); | |
56 | } | |
57 | ||
58 | void VerifyVisibleTombstones( | |
59 | FragmentedRangeTombstoneIterator* iter, | |
60 | const std::vector<RangeTombstone>& expected_tombstones) { | |
61 | iter->SeekToTopFirst(); | |
62 | for (size_t i = 0; i < expected_tombstones.size(); i++, iter->TopNext()) { | |
63 | ASSERT_TRUE(iter->Valid()); | |
64 | CheckIterPosition(expected_tombstones[i], iter); | |
65 | } | |
66 | EXPECT_FALSE(iter->Valid()); | |
67 | } | |
68 | ||
69 | struct SeekTestCase { | |
70 | Slice seek_target; | |
71 | RangeTombstone expected_position; | |
72 | bool out_of_range; | |
73 | }; | |
74 | ||
75 | void VerifySeek(FragmentedRangeTombstoneIterator* iter, | |
76 | const std::vector<SeekTestCase>& cases) { | |
77 | for (const auto& testcase : cases) { | |
78 | iter->Seek(testcase.seek_target); | |
79 | if (testcase.out_of_range) { | |
80 | ASSERT_FALSE(iter->Valid()); | |
81 | } else { | |
82 | ASSERT_TRUE(iter->Valid()); | |
83 | CheckIterPosition(testcase.expected_position, iter); | |
84 | } | |
85 | } | |
86 | } | |
87 | ||
88 | void VerifySeekForPrev(FragmentedRangeTombstoneIterator* iter, | |
89 | const std::vector<SeekTestCase>& cases) { | |
90 | for (const auto& testcase : cases) { | |
91 | iter->SeekForPrev(testcase.seek_target); | |
92 | if (testcase.out_of_range) { | |
93 | ASSERT_FALSE(iter->Valid()); | |
94 | } else { | |
95 | ASSERT_TRUE(iter->Valid()); | |
96 | CheckIterPosition(testcase.expected_position, iter); | |
97 | } | |
98 | } | |
99 | } | |
100 | ||
101 | struct MaxCoveringTombstoneSeqnumTestCase { | |
102 | Slice user_key; | |
103 | SequenceNumber result; | |
104 | }; | |
105 | ||
106 | void VerifyMaxCoveringTombstoneSeqnum( | |
107 | FragmentedRangeTombstoneIterator* iter, | |
108 | const std::vector<MaxCoveringTombstoneSeqnumTestCase>& cases) { | |
109 | for (const auto& testcase : cases) { | |
110 | EXPECT_EQ(testcase.result, | |
111 | iter->MaxCoveringTombstoneSeqnum(testcase.user_key)); | |
112 | } | |
113 | } | |
114 | ||
115 | } // anonymous namespace | |
116 | ||
117 | TEST_F(RangeTombstoneFragmenterTest, NonOverlappingTombstones) { | |
118 | auto range_del_iter = MakeRangeDelIter({{"a", "b", 10}, {"c", "d", 5}}); | |
119 | ||
120 | FragmentedRangeTombstoneList fragment_list(std::move(range_del_iter), | |
121 | bytewise_icmp); | |
122 | FragmentedRangeTombstoneIterator iter(&fragment_list, bytewise_icmp, | |
123 | kMaxSequenceNumber); | |
124 | ASSERT_EQ(0, iter.lower_bound()); | |
125 | ASSERT_EQ(kMaxSequenceNumber, iter.upper_bound()); | |
126 | VerifyFragmentedRangeDels(&iter, {{"a", "b", 10}, {"c", "d", 5}}); | |
127 | VerifyMaxCoveringTombstoneSeqnum(&iter, | |
128 | {{"", 0}, {"a", 10}, {"b", 0}, {"c", 5}}); | |
129 | } | |
130 | ||
131 | TEST_F(RangeTombstoneFragmenterTest, OverlappingTombstones) { | |
132 | auto range_del_iter = MakeRangeDelIter({{"a", "e", 10}, {"c", "g", 15}}); | |
133 | ||
134 | FragmentedRangeTombstoneList fragment_list(std::move(range_del_iter), | |
135 | bytewise_icmp); | |
136 | FragmentedRangeTombstoneIterator iter(&fragment_list, bytewise_icmp, | |
137 | kMaxSequenceNumber); | |
138 | ASSERT_EQ(0, iter.lower_bound()); | |
139 | ASSERT_EQ(kMaxSequenceNumber, iter.upper_bound()); | |
140 | VerifyFragmentedRangeDels( | |
141 | &iter, {{"a", "c", 10}, {"c", "e", 15}, {"c", "e", 10}, {"e", "g", 15}}); | |
142 | VerifyMaxCoveringTombstoneSeqnum(&iter, | |
143 | {{"a", 10}, {"c", 15}, {"e", 15}, {"g", 0}}); | |
144 | } | |
145 | ||
146 | TEST_F(RangeTombstoneFragmenterTest, ContiguousTombstones) { | |
147 | auto range_del_iter = MakeRangeDelIter( | |
148 | {{"a", "c", 10}, {"c", "e", 20}, {"c", "e", 5}, {"e", "g", 15}}); | |
149 | ||
150 | FragmentedRangeTombstoneList fragment_list(std::move(range_del_iter), | |
151 | bytewise_icmp); | |
152 | FragmentedRangeTombstoneIterator iter(&fragment_list, bytewise_icmp, | |
153 | kMaxSequenceNumber); | |
154 | ASSERT_EQ(0, iter.lower_bound()); | |
155 | ASSERT_EQ(kMaxSequenceNumber, iter.upper_bound()); | |
156 | VerifyFragmentedRangeDels( | |
157 | &iter, {{"a", "c", 10}, {"c", "e", 20}, {"c", "e", 5}, {"e", "g", 15}}); | |
158 | VerifyMaxCoveringTombstoneSeqnum(&iter, | |
159 | {{"a", 10}, {"c", 20}, {"e", 15}, {"g", 0}}); | |
160 | } | |
161 | ||
162 | TEST_F(RangeTombstoneFragmenterTest, RepeatedStartAndEndKey) { | |
163 | auto range_del_iter = | |
164 | MakeRangeDelIter({{"a", "c", 10}, {"a", "c", 7}, {"a", "c", 3}}); | |
165 | ||
166 | FragmentedRangeTombstoneList fragment_list(std::move(range_del_iter), | |
167 | bytewise_icmp); | |
168 | FragmentedRangeTombstoneIterator iter(&fragment_list, bytewise_icmp, | |
169 | kMaxSequenceNumber); | |
170 | ASSERT_EQ(0, iter.lower_bound()); | |
171 | ASSERT_EQ(kMaxSequenceNumber, iter.upper_bound()); | |
172 | VerifyFragmentedRangeDels(&iter, | |
173 | {{"a", "c", 10}, {"a", "c", 7}, {"a", "c", 3}}); | |
174 | VerifyMaxCoveringTombstoneSeqnum(&iter, {{"a", 10}, {"b", 10}, {"c", 0}}); | |
175 | } | |
176 | ||
177 | TEST_F(RangeTombstoneFragmenterTest, RepeatedStartKeyDifferentEndKeys) { | |
178 | auto range_del_iter = | |
179 | MakeRangeDelIter({{"a", "e", 10}, {"a", "g", 7}, {"a", "c", 3}}); | |
180 | ||
181 | FragmentedRangeTombstoneList fragment_list(std::move(range_del_iter), | |
182 | bytewise_icmp); | |
183 | FragmentedRangeTombstoneIterator iter(&fragment_list, bytewise_icmp, | |
184 | kMaxSequenceNumber); | |
185 | ASSERT_EQ(0, iter.lower_bound()); | |
186 | ASSERT_EQ(kMaxSequenceNumber, iter.upper_bound()); | |
187 | VerifyFragmentedRangeDels(&iter, {{"a", "c", 10}, | |
188 | {"a", "c", 7}, | |
189 | {"a", "c", 3}, | |
190 | {"c", "e", 10}, | |
191 | {"c", "e", 7}, | |
192 | {"e", "g", 7}}); | |
193 | VerifyMaxCoveringTombstoneSeqnum(&iter, | |
194 | {{"a", 10}, {"c", 10}, {"e", 7}, {"g", 0}}); | |
195 | } | |
196 | ||
197 | TEST_F(RangeTombstoneFragmenterTest, RepeatedStartKeyMixedEndKeys) { | |
198 | auto range_del_iter = MakeRangeDelIter({{"a", "c", 30}, | |
199 | {"a", "g", 20}, | |
200 | {"a", "e", 10}, | |
201 | {"a", "g", 7}, | |
202 | {"a", "c", 3}}); | |
203 | ||
204 | FragmentedRangeTombstoneList fragment_list(std::move(range_del_iter), | |
205 | bytewise_icmp); | |
206 | FragmentedRangeTombstoneIterator iter(&fragment_list, bytewise_icmp, | |
207 | kMaxSequenceNumber); | |
208 | ASSERT_EQ(0, iter.lower_bound()); | |
209 | ASSERT_EQ(kMaxSequenceNumber, iter.upper_bound()); | |
210 | VerifyFragmentedRangeDels(&iter, {{"a", "c", 30}, | |
211 | {"a", "c", 20}, | |
212 | {"a", "c", 10}, | |
213 | {"a", "c", 7}, | |
214 | {"a", "c", 3}, | |
215 | {"c", "e", 20}, | |
216 | {"c", "e", 10}, | |
217 | {"c", "e", 7}, | |
218 | {"e", "g", 20}, | |
219 | {"e", "g", 7}}); | |
220 | VerifyMaxCoveringTombstoneSeqnum(&iter, | |
221 | {{"a", 30}, {"c", 20}, {"e", 20}, {"g", 0}}); | |
222 | } | |
223 | ||
224 | TEST_F(RangeTombstoneFragmenterTest, OverlapAndRepeatedStartKey) { | |
225 | auto range_del_iter = MakeRangeDelIter({{"a", "e", 10}, | |
226 | {"c", "g", 8}, | |
227 | {"c", "i", 6}, | |
228 | {"j", "n", 4}, | |
229 | {"j", "l", 2}}); | |
230 | ||
231 | FragmentedRangeTombstoneList fragment_list(std::move(range_del_iter), | |
232 | bytewise_icmp); | |
233 | FragmentedRangeTombstoneIterator iter1(&fragment_list, bytewise_icmp, | |
234 | kMaxSequenceNumber); | |
235 | FragmentedRangeTombstoneIterator iter2(&fragment_list, bytewise_icmp, | |
236 | 9 /* upper_bound */); | |
237 | FragmentedRangeTombstoneIterator iter3(&fragment_list, bytewise_icmp, | |
238 | 7 /* upper_bound */); | |
239 | FragmentedRangeTombstoneIterator iter4(&fragment_list, bytewise_icmp, | |
240 | 5 /* upper_bound */); | |
241 | FragmentedRangeTombstoneIterator iter5(&fragment_list, bytewise_icmp, | |
242 | 3 /* upper_bound */); | |
243 | for (auto* iter : {&iter1, &iter2, &iter3, &iter4, &iter5}) { | |
244 | VerifyFragmentedRangeDels(iter, {{"a", "c", 10}, | |
245 | {"c", "e", 10}, | |
246 | {"c", "e", 8}, | |
247 | {"c", "e", 6}, | |
248 | {"e", "g", 8}, | |
249 | {"e", "g", 6}, | |
250 | {"g", "i", 6}, | |
251 | {"j", "l", 4}, | |
252 | {"j", "l", 2}, | |
253 | {"l", "n", 4}}); | |
254 | } | |
255 | ||
256 | ASSERT_EQ(0, iter1.lower_bound()); | |
257 | ASSERT_EQ(kMaxSequenceNumber, iter1.upper_bound()); | |
258 | VerifyVisibleTombstones(&iter1, {{"a", "c", 10}, | |
259 | {"c", "e", 10}, | |
260 | {"e", "g", 8}, | |
261 | {"g", "i", 6}, | |
262 | {"j", "l", 4}, | |
263 | {"l", "n", 4}}); | |
264 | VerifyMaxCoveringTombstoneSeqnum( | |
265 | &iter1, {{"a", 10}, {"c", 10}, {"e", 8}, {"i", 0}, {"j", 4}, {"m", 4}}); | |
266 | ||
267 | ASSERT_EQ(0, iter2.lower_bound()); | |
268 | ASSERT_EQ(9, iter2.upper_bound()); | |
269 | VerifyVisibleTombstones(&iter2, {{"c", "e", 8}, | |
270 | {"e", "g", 8}, | |
271 | {"g", "i", 6}, | |
272 | {"j", "l", 4}, | |
273 | {"l", "n", 4}}); | |
274 | VerifyMaxCoveringTombstoneSeqnum( | |
275 | &iter2, {{"a", 0}, {"c", 8}, {"e", 8}, {"i", 0}, {"j", 4}, {"m", 4}}); | |
276 | ||
277 | ASSERT_EQ(0, iter3.lower_bound()); | |
278 | ASSERT_EQ(7, iter3.upper_bound()); | |
279 | VerifyVisibleTombstones(&iter3, {{"c", "e", 6}, | |
280 | {"e", "g", 6}, | |
281 | {"g", "i", 6}, | |
282 | {"j", "l", 4}, | |
283 | {"l", "n", 4}}); | |
284 | VerifyMaxCoveringTombstoneSeqnum( | |
285 | &iter3, {{"a", 0}, {"c", 6}, {"e", 6}, {"i", 0}, {"j", 4}, {"m", 4}}); | |
286 | ||
287 | ASSERT_EQ(0, iter4.lower_bound()); | |
288 | ASSERT_EQ(5, iter4.upper_bound()); | |
289 | VerifyVisibleTombstones(&iter4, {{"j", "l", 4}, {"l", "n", 4}}); | |
290 | VerifyMaxCoveringTombstoneSeqnum( | |
291 | &iter4, {{"a", 0}, {"c", 0}, {"e", 0}, {"i", 0}, {"j", 4}, {"m", 4}}); | |
292 | ||
293 | ASSERT_EQ(0, iter5.lower_bound()); | |
294 | ASSERT_EQ(3, iter5.upper_bound()); | |
295 | VerifyVisibleTombstones(&iter5, {{"j", "l", 2}}); | |
296 | VerifyMaxCoveringTombstoneSeqnum( | |
297 | &iter5, {{"a", 0}, {"c", 0}, {"e", 0}, {"i", 0}, {"j", 2}, {"m", 0}}); | |
298 | } | |
299 | ||
300 | TEST_F(RangeTombstoneFragmenterTest, OverlapAndRepeatedStartKeyUnordered) { | |
301 | auto range_del_iter = MakeRangeDelIter({{"a", "e", 10}, | |
302 | {"j", "n", 4}, | |
303 | {"c", "i", 6}, | |
304 | {"c", "g", 8}, | |
305 | {"j", "l", 2}}); | |
306 | ||
307 | FragmentedRangeTombstoneList fragment_list(std::move(range_del_iter), | |
308 | bytewise_icmp); | |
309 | FragmentedRangeTombstoneIterator iter(&fragment_list, bytewise_icmp, | |
310 | 9 /* upper_bound */); | |
311 | ASSERT_EQ(0, iter.lower_bound()); | |
312 | ASSERT_EQ(9, iter.upper_bound()); | |
313 | VerifyFragmentedRangeDels(&iter, {{"a", "c", 10}, | |
314 | {"c", "e", 10}, | |
315 | {"c", "e", 8}, | |
316 | {"c", "e", 6}, | |
317 | {"e", "g", 8}, | |
318 | {"e", "g", 6}, | |
319 | {"g", "i", 6}, | |
320 | {"j", "l", 4}, | |
321 | {"j", "l", 2}, | |
322 | {"l", "n", 4}}); | |
323 | VerifyMaxCoveringTombstoneSeqnum( | |
324 | &iter, {{"a", 0}, {"c", 8}, {"e", 8}, {"i", 0}, {"j", 4}, {"m", 4}}); | |
325 | } | |
326 | ||
327 | TEST_F(RangeTombstoneFragmenterTest, OverlapAndRepeatedStartKeyForCompaction) { | |
328 | auto range_del_iter = MakeRangeDelIter({{"a", "e", 10}, | |
329 | {"j", "n", 4}, | |
330 | {"c", "i", 6}, | |
331 | {"c", "g", 8}, | |
332 | {"j", "l", 2}}); | |
333 | ||
334 | FragmentedRangeTombstoneList fragment_list( | |
335 | std::move(range_del_iter), bytewise_icmp, true /* for_compaction */, | |
336 | {} /* snapshots */); | |
337 | FragmentedRangeTombstoneIterator iter(&fragment_list, bytewise_icmp, | |
338 | kMaxSequenceNumber /* upper_bound */); | |
339 | VerifyFragmentedRangeDels(&iter, {{"a", "c", 10}, | |
340 | {"c", "e", 10}, | |
341 | {"e", "g", 8}, | |
342 | {"g", "i", 6}, | |
343 | {"j", "l", 4}, | |
344 | {"l", "n", 4}}); | |
345 | } | |
346 | ||
347 | TEST_F(RangeTombstoneFragmenterTest, | |
348 | OverlapAndRepeatedStartKeyForCompactionWithSnapshot) { | |
349 | auto range_del_iter = MakeRangeDelIter({{"a", "e", 10}, | |
350 | {"j", "n", 4}, | |
351 | {"c", "i", 6}, | |
352 | {"c", "g", 8}, | |
353 | {"j", "l", 2}}); | |
354 | ||
355 | FragmentedRangeTombstoneList fragment_list( | |
356 | std::move(range_del_iter), bytewise_icmp, true /* for_compaction */, | |
357 | {20, 9} /* upper_bounds */); | |
358 | FragmentedRangeTombstoneIterator iter(&fragment_list, bytewise_icmp, | |
359 | kMaxSequenceNumber /* upper_bound */); | |
360 | VerifyFragmentedRangeDels(&iter, {{"a", "c", 10}, | |
361 | {"c", "e", 10}, | |
362 | {"c", "e", 8}, | |
363 | {"e", "g", 8}, | |
364 | {"g", "i", 6}, | |
365 | {"j", "l", 4}, | |
366 | {"l", "n", 4}}); | |
367 | } | |
368 | ||
369 | TEST_F(RangeTombstoneFragmenterTest, IteratorSplitNoSnapshots) { | |
370 | auto range_del_iter = MakeRangeDelIter({{"a", "e", 10}, | |
371 | {"j", "n", 4}, | |
372 | {"c", "i", 6}, | |
373 | {"c", "g", 8}, | |
374 | {"j", "l", 2}}); | |
375 | ||
376 | FragmentedRangeTombstoneList fragment_list(std::move(range_del_iter), | |
377 | bytewise_icmp); | |
378 | FragmentedRangeTombstoneIterator iter(&fragment_list, bytewise_icmp, | |
379 | kMaxSequenceNumber /* upper_bound */); | |
380 | ||
381 | auto split_iters = iter.SplitBySnapshot({} /* snapshots */); | |
382 | ASSERT_EQ(1, split_iters.size()); | |
383 | ||
384 | auto* split_iter = split_iters[kMaxSequenceNumber].get(); | |
385 | ASSERT_EQ(0, split_iter->lower_bound()); | |
386 | ASSERT_EQ(kMaxSequenceNumber, split_iter->upper_bound()); | |
387 | VerifyVisibleTombstones(split_iter, {{"a", "c", 10}, | |
388 | {"c", "e", 10}, | |
389 | {"e", "g", 8}, | |
390 | {"g", "i", 6}, | |
391 | {"j", "l", 4}, | |
392 | {"l", "n", 4}}); | |
393 | } | |
394 | ||
395 | TEST_F(RangeTombstoneFragmenterTest, IteratorSplitWithSnapshots) { | |
396 | auto range_del_iter = MakeRangeDelIter({{"a", "e", 10}, | |
397 | {"j", "n", 4}, | |
398 | {"c", "i", 6}, | |
399 | {"c", "g", 8}, | |
400 | {"j", "l", 2}}); | |
401 | ||
402 | FragmentedRangeTombstoneList fragment_list(std::move(range_del_iter), | |
403 | bytewise_icmp); | |
404 | FragmentedRangeTombstoneIterator iter(&fragment_list, bytewise_icmp, | |
405 | kMaxSequenceNumber /* upper_bound */); | |
406 | ||
407 | auto split_iters = iter.SplitBySnapshot({3, 5, 7, 9} /* snapshots */); | |
408 | ASSERT_EQ(5, split_iters.size()); | |
409 | ||
410 | auto* split_iter1 = split_iters[3].get(); | |
411 | ASSERT_EQ(0, split_iter1->lower_bound()); | |
412 | ASSERT_EQ(3, split_iter1->upper_bound()); | |
413 | VerifyVisibleTombstones(split_iter1, {{"j", "l", 2}}); | |
414 | ||
415 | auto* split_iter2 = split_iters[5].get(); | |
416 | ASSERT_EQ(4, split_iter2->lower_bound()); | |
417 | ASSERT_EQ(5, split_iter2->upper_bound()); | |
418 | VerifyVisibleTombstones(split_iter2, {{"j", "l", 4}, {"l", "n", 4}}); | |
419 | ||
420 | auto* split_iter3 = split_iters[7].get(); | |
421 | ASSERT_EQ(6, split_iter3->lower_bound()); | |
422 | ASSERT_EQ(7, split_iter3->upper_bound()); | |
423 | VerifyVisibleTombstones(split_iter3, | |
424 | {{"c", "e", 6}, {"e", "g", 6}, {"g", "i", 6}}); | |
425 | ||
426 | auto* split_iter4 = split_iters[9].get(); | |
427 | ASSERT_EQ(8, split_iter4->lower_bound()); | |
428 | ASSERT_EQ(9, split_iter4->upper_bound()); | |
429 | VerifyVisibleTombstones(split_iter4, {{"c", "e", 8}, {"e", "g", 8}}); | |
430 | ||
431 | auto* split_iter5 = split_iters[kMaxSequenceNumber].get(); | |
432 | ASSERT_EQ(10, split_iter5->lower_bound()); | |
433 | ASSERT_EQ(kMaxSequenceNumber, split_iter5->upper_bound()); | |
434 | VerifyVisibleTombstones(split_iter5, {{"a", "c", 10}, {"c", "e", 10}}); | |
435 | } | |
436 | ||
437 | TEST_F(RangeTombstoneFragmenterTest, SeekStartKey) { | |
438 | // Same tombstones as OverlapAndRepeatedStartKey. | |
439 | auto range_del_iter = MakeRangeDelIter({{"a", "e", 10}, | |
440 | {"c", "g", 8}, | |
441 | {"c", "i", 6}, | |
442 | {"j", "n", 4}, | |
443 | {"j", "l", 2}}); | |
444 | ||
445 | FragmentedRangeTombstoneList fragment_list(std::move(range_del_iter), | |
446 | bytewise_icmp); | |
447 | ||
448 | FragmentedRangeTombstoneIterator iter1(&fragment_list, bytewise_icmp, | |
449 | kMaxSequenceNumber); | |
450 | VerifySeek( | |
451 | &iter1, | |
452 | {{"a", {"a", "c", 10}}, {"e", {"e", "g", 8}}, {"l", {"l", "n", 4}}}); | |
453 | VerifySeekForPrev( | |
454 | &iter1, | |
455 | {{"a", {"a", "c", 10}}, {"e", {"e", "g", 8}}, {"l", {"l", "n", 4}}}); | |
456 | ||
457 | FragmentedRangeTombstoneIterator iter2(&fragment_list, bytewise_icmp, | |
458 | 3 /* upper_bound */); | |
459 | VerifySeek(&iter2, {{"a", {"j", "l", 2}}, | |
460 | {"e", {"j", "l", 2}}, | |
461 | {"l", {}, true /* out of range */}}); | |
462 | VerifySeekForPrev(&iter2, {{"a", {}, true /* out of range */}, | |
463 | {"e", {}, true /* out of range */}, | |
464 | {"l", {"j", "l", 2}}}); | |
465 | } | |
466 | ||
467 | TEST_F(RangeTombstoneFragmenterTest, SeekCovered) { | |
468 | // Same tombstones as OverlapAndRepeatedStartKey. | |
469 | auto range_del_iter = MakeRangeDelIter({{"a", "e", 10}, | |
470 | {"c", "g", 8}, | |
471 | {"c", "i", 6}, | |
472 | {"j", "n", 4}, | |
473 | {"j", "l", 2}}); | |
474 | ||
475 | FragmentedRangeTombstoneList fragment_list(std::move(range_del_iter), | |
476 | bytewise_icmp); | |
477 | ||
478 | FragmentedRangeTombstoneIterator iter1(&fragment_list, bytewise_icmp, | |
479 | kMaxSequenceNumber); | |
480 | VerifySeek( | |
481 | &iter1, | |
482 | {{"b", {"a", "c", 10}}, {"f", {"e", "g", 8}}, {"m", {"l", "n", 4}}}); | |
483 | VerifySeekForPrev( | |
484 | &iter1, | |
485 | {{"b", {"a", "c", 10}}, {"f", {"e", "g", 8}}, {"m", {"l", "n", 4}}}); | |
486 | ||
487 | FragmentedRangeTombstoneIterator iter2(&fragment_list, bytewise_icmp, | |
488 | 3 /* upper_bound */); | |
489 | VerifySeek(&iter2, {{"b", {"j", "l", 2}}, | |
490 | {"f", {"j", "l", 2}}, | |
491 | {"m", {}, true /* out of range */}}); | |
492 | VerifySeekForPrev(&iter2, {{"b", {}, true /* out of range */}, | |
493 | {"f", {}, true /* out of range */}, | |
494 | {"m", {"j", "l", 2}}}); | |
495 | } | |
496 | ||
497 | TEST_F(RangeTombstoneFragmenterTest, SeekEndKey) { | |
498 | // Same tombstones as OverlapAndRepeatedStartKey. | |
499 | auto range_del_iter = MakeRangeDelIter({{"a", "e", 10}, | |
500 | {"c", "g", 8}, | |
501 | {"c", "i", 6}, | |
502 | {"j", "n", 4}, | |
503 | {"j", "l", 2}}); | |
504 | ||
505 | FragmentedRangeTombstoneList fragment_list(std::move(range_del_iter), | |
506 | bytewise_icmp); | |
507 | ||
508 | FragmentedRangeTombstoneIterator iter1(&fragment_list, bytewise_icmp, | |
509 | kMaxSequenceNumber); | |
510 | VerifySeek(&iter1, {{"c", {"c", "e", 10}}, | |
511 | {"g", {"g", "i", 6}}, | |
512 | {"i", {"j", "l", 4}}, | |
513 | {"n", {}, true /* out of range */}}); | |
514 | VerifySeekForPrev(&iter1, {{"c", {"c", "e", 10}}, | |
515 | {"g", {"g", "i", 6}}, | |
516 | {"i", {"g", "i", 6}}, | |
517 | {"n", {"l", "n", 4}}}); | |
518 | ||
519 | FragmentedRangeTombstoneIterator iter2(&fragment_list, bytewise_icmp, | |
520 | 3 /* upper_bound */); | |
521 | VerifySeek(&iter2, {{"c", {"j", "l", 2}}, | |
522 | {"g", {"j", "l", 2}}, | |
523 | {"i", {"j", "l", 2}}, | |
524 | {"n", {}, true /* out of range */}}); | |
525 | VerifySeekForPrev(&iter2, {{"c", {}, true /* out of range */}, | |
526 | {"g", {}, true /* out of range */}, | |
527 | {"i", {}, true /* out of range */}, | |
528 | {"n", {"j", "l", 2}}}); | |
529 | } | |
530 | ||
531 | TEST_F(RangeTombstoneFragmenterTest, SeekOutOfBounds) { | |
532 | // Same tombstones as OverlapAndRepeatedStartKey. | |
533 | auto range_del_iter = MakeRangeDelIter({{"a", "e", 10}, | |
534 | {"c", "g", 8}, | |
535 | {"c", "i", 6}, | |
536 | {"j", "n", 4}, | |
537 | {"j", "l", 2}}); | |
538 | ||
539 | FragmentedRangeTombstoneList fragment_list(std::move(range_del_iter), | |
540 | bytewise_icmp); | |
541 | ||
542 | FragmentedRangeTombstoneIterator iter(&fragment_list, bytewise_icmp, | |
543 | kMaxSequenceNumber); | |
544 | VerifySeek(&iter, {{"", {"a", "c", 10}}, {"z", {}, true /* out of range */}}); | |
545 | VerifySeekForPrev(&iter, | |
546 | {{"", {}, true /* out of range */}, {"z", {"l", "n", 4}}}); | |
547 | } | |
548 | ||
f67539c2 | 549 | } // namespace ROCKSDB_NAMESPACE |
494da23a TL |
550 | |
551 | int main(int argc, char** argv) { | |
1e59de90 | 552 | ROCKSDB_NAMESPACE::port::InstallStackTraceHandler(); |
494da23a TL |
553 | ::testing::InitGoogleTest(&argc, argv); |
554 | return RUN_ALL_TESTS(); | |
555 | } |