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