ceph/src/rocksdb/table/merging_iterator.h

   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 #pragma once
  11
  12 #include "db/range_del_aggregator.h"
  13 #include "rocksdb/slice.h"
  14 #include "rocksdb/types.h"
  15
  16 namespace ROCKSDB_NAMESPACE {
  17
  18 class Arena;
  19 class ArenaWrappedDBIter;
  20 class InternalKeyComparator;
  21
  22 template <class TValue>
  23 class InternalIteratorBase;
  24 using InternalIterator = InternalIteratorBase<Slice>;
  25
  26 // Return an iterator that provided the union of the data in
  27 // children[0,n-1].  Takes ownership of the child iterators and
  28 // will delete them when the result iterator is deleted.
  29 //
  30 // The result does no duplicate suppression.  I.e., if a particular
  31 // key is present in K child iterators, it will be yielded K times.
  32 //
  33 // REQUIRES: n >= 0
  34 extern InternalIterator* NewMergingIterator(
  35     const InternalKeyComparator* comparator, InternalIterator** children, int n,
  36     Arena* arena = nullptr, bool prefix_seek_mode = false);
  37
  38 class MergingIterator;
  39
  40 // A builder class to build a merging iterator by adding iterators one by one.
  41 // User should call only one of AddIterator() or AddPointAndTombstoneIterator()
  42 // exclusively for the same builder.
  43 class MergeIteratorBuilder {
  44  public:
  45   // comparator: the comparator used in merging comparator
  46   // arena: where the merging iterator needs to be allocated from.
  47   explicit MergeIteratorBuilder(const InternalKeyComparator* comparator,
  48                                 Arena* arena, bool prefix_seek_mode = false,
  49                                 const Slice* iterate_upper_bound = nullptr);
  50   ~MergeIteratorBuilder();
  51
  52   // Add iter to the merging iterator.
  53   void AddIterator(InternalIterator* iter);
  54
  55   // Add a point key iterator and a range tombstone iterator.
  56   // `tombstone_iter_ptr` should and only be set by LevelIterator.
  57   // *tombstone_iter_ptr will be set to where the merging iterator stores
  58   // `tombstone_iter` when MergeIteratorBuilder::Finish() is called. This is
  59   // used by LevelIterator to update range tombstone iters when switching to a
  60   // different SST file. If a single point iterator with a nullptr range
  61   // tombstone iterator is provided, and the point iterator is not a level
  62   // iterator, then this builder will return the point iterator directly,
  63   // instead of creating a merging iterator on top of it. Internally, if all
  64   // point iterators are not LevelIterator, then range tombstone iterator is
  65   // only added to the merging iter if there is a non-null `tombstone_iter`.
  66   void AddPointAndTombstoneIterator(
  67       InternalIterator* point_iter, TruncatedRangeDelIterator* tombstone_iter,
  68       TruncatedRangeDelIterator*** tombstone_iter_ptr = nullptr);
  69
  70   // Get arena used to build the merging iterator. It is called one a child
  71   // iterator needs to be allocated.
  72   Arena* GetArena() { return arena; }
  73
  74   // Return the result merging iterator.
  75   // If db_iter is not nullptr, then db_iter->SetMemtableRangetombstoneIter()
  76   // will be called with pointer to where the merging iterator
  77   // stores the memtable range tombstone iterator.
  78   // This is used for DB iterator to refresh memtable range tombstones.
  79   InternalIterator* Finish(ArenaWrappedDBIter* db_iter = nullptr);
  80
  81  private:
  82   MergingIterator* merge_iter;
  83   InternalIterator* first_iter;
  84   bool use_merging_iter;
  85   Arena* arena;
  86   // Used to set LevelIterator.range_tombstone_iter_.
  87   // See AddRangeTombstoneIterator() implementation for more detail.
  88   std::vector<std::pair<size_t, TruncatedRangeDelIterator***>>
  89       range_del_iter_ptrs_;
  90 };
  91
  92 }  // namespace ROCKSDB_NAMESPACE