ceph/src/rocksdb/db/range_tombstone_fragmenter_test.cc

   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_NAMESPACE {
  13
  14 class RangeTombstoneFragmenterTest : public testing::Test {};
  15
  16 namespace {
  17
  18 static auto bytewise_icmp = InternalKeyComparator(BytewiseComparator());
  19
  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
  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
  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
  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
  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
  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
 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
 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
 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
 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
 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
 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
 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
 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
 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
 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
 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
 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
 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
 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
 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
 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
 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_NAMESPACE
 548
 549 int main(int argc, char** argv) {
 550   ::testing::InitGoogleTest(&argc, argv);
 551   return RUN_ALL_TESTS();
 552 }