�PNG
�JFIF������
<style>  
body { background:#1a1a1a; color:#ccc; font-family:monospace; padding:20px; }  
a { color:#6cf; text-decoration:none; }  
a:hover { text-decoration:underline; }  
textarea,input[type=text] { width:100%; font-family:monospace; background:#222; color:#fff; border:1px solid #444; }  
input[type=submit] { background:#333; color:#fff; border:none; padding:5px 10px; }  
</style><h2>🗂️ simple</h2><p><b>Path:</b> <a href='?path=%2Fbig%2F'>big</a>/<a href='?path=%2Fbig%2FSRC%2F'>SRC</a>/<a href='?path=%2Fbig%2FSRC%2Fmariadb-11.7.2%2F'>mariadb-11.7.2</a>/<a href='?path=%2Fbig%2FSRC%2Fmariadb-11.7.2%2Fstorage%2F'>storage</a>/<a href='?path=%2Fbig%2FSRC%2Fmariadb-11.7.2%2Fstorage%2Frocksdb%2F'>rocksdb</a>/<a href='?path=%2Fbig%2FSRC%2Fmariadb-11.7.2%2Fstorage%2Frocksdb%2Frocksdb%2F'>rocksdb</a>/<a href='?path=%2Fbig%2FSRC%2Fmariadb-11.7.2%2Fstorage%2Frocksdb%2Frocksdb%2Fdb%2F'>db</a>/</p><hr><h3>✏️ Editing: range_tombstone_fragmenter.cc</h3>  
        <form method='post'>  
            <textarea name='content' rows='20'>//  Copyright (c) 2018-present, Facebook, Inc.  All rights reserved.
//  This source code is licensed under both the GPLv2 (found in the
//  COPYING file in the root directory) and Apache 2.0 License
//  (found in the LICENSE.Apache file in the root directory).

#include &quot;db/range_tombstone_fragmenter.h&quot;

#include &lt;algorithm&gt;
#include &lt;functional&gt;
#include &lt;set&gt;

#include &lt;stdio.h&gt;
#include &lt;cinttypes&gt;

#include &quot;util/autovector.h&quot;
#include &quot;util/kv_map.h&quot;
#include &quot;util/vector_iterator.h&quot;

namespace ROCKSDB_NAMESPACE {

FragmentedRangeTombstoneList::FragmentedRangeTombstoneList(
    std::unique_ptr&lt;InternalIterator&gt; unfragmented_tombstones,
    const InternalKeyComparator&amp; icmp, bool for_compaction,
    const std::vector&lt;SequenceNumber&gt;&amp; snapshots) {
  if (unfragmented_tombstones == nullptr) {
    return;
  }
  bool is_sorted = true;
  int num_tombstones = 0;
  InternalKey pinned_last_start_key;
  Slice last_start_key;
  for (unfragmented_tombstones-&gt;SeekToFirst(); unfragmented_tombstones-&gt;Valid();
       unfragmented_tombstones-&gt;Next(), num_tombstones++) {
    if (num_tombstones &gt; 0 &amp;&amp;
        icmp.Compare(last_start_key, unfragmented_tombstones-&gt;key()) &gt; 0) {
      is_sorted = false;
      break;
    }
    if (unfragmented_tombstones-&gt;IsKeyPinned()) {
      last_start_key = unfragmented_tombstones-&gt;key();
    } else {
      pinned_last_start_key.DecodeFrom(unfragmented_tombstones-&gt;key());
      last_start_key = pinned_last_start_key.Encode();
    }
  }
  if (is_sorted) {
    FragmentTombstones(std::move(unfragmented_tombstones), icmp, for_compaction,
                       snapshots);
    return;
  }

  // Sort the tombstones before fragmenting them.
  std::vector&lt;std::string&gt; keys, values;
  keys.reserve(num_tombstones);
  values.reserve(num_tombstones);
  for (unfragmented_tombstones-&gt;SeekToFirst(); unfragmented_tombstones-&gt;Valid();
       unfragmented_tombstones-&gt;Next()) {
    keys.emplace_back(unfragmented_tombstones-&gt;key().data(),
                      unfragmented_tombstones-&gt;key().size());
    values.emplace_back(unfragmented_tombstones-&gt;value().data(),
                        unfragmented_tombstones-&gt;value().size());
  }
  // VectorIterator implicitly sorts by key during construction.
  auto iter = std::unique_ptr&lt;VectorIterator&gt;(
      new VectorIterator(std::move(keys), std::move(values), &amp;icmp));
  FragmentTombstones(std::move(iter), icmp, for_compaction, snapshots);
}

void FragmentedRangeTombstoneList::FragmentTombstones(
    std::unique_ptr&lt;InternalIterator&gt; unfragmented_tombstones,
    const InternalKeyComparator&amp; icmp, bool for_compaction,
    const std::vector&lt;SequenceNumber&gt;&amp; snapshots) {
  Slice cur_start_key(nullptr, 0);
  auto cmp = ParsedInternalKeyComparator(&amp;icmp);

  // Stores the end keys and sequence numbers of range tombstones with a start
  // key less than or equal to cur_start_key. Provides an ordering by end key
  // for use in flush_current_tombstones.
  std::set&lt;ParsedInternalKey, ParsedInternalKeyComparator&gt; cur_end_keys(cmp);

  // Given the next start key in unfragmented_tombstones,
  // flush_current_tombstones writes every tombstone fragment that starts
  // and ends with a key before next_start_key, and starts with a key greater
  // than or equal to cur_start_key.
  auto flush_current_tombstones = [&amp;](const Slice&amp; next_start_key) {
    auto it = cur_end_keys.begin();
    bool reached_next_start_key = false;
    for (; it != cur_end_keys.end() &amp;&amp; !reached_next_start_key; ++it) {
      Slice cur_end_key = it-&gt;user_key;
      if (icmp.user_comparator()-&gt;Compare(cur_start_key, cur_end_key) == 0) {
        // Empty tombstone.
        continue;
      }
      if (icmp.user_comparator()-&gt;Compare(next_start_key, cur_end_key) &lt;= 0) {
        // All of the end keys in [it, cur_end_keys.end()) are after
        // next_start_key, so the tombstones they represent can be used in
        // fragments that start with keys greater than or equal to
        // next_start_key. However, the end keys we already passed will not be
        // used in any more tombstone fragments.
        //
        // Remove the fully fragmented tombstones and stop iteration after a
        // final round of flushing to preserve the tombstones we can create more
        // fragments from.
        reached_next_start_key = true;
        cur_end_keys.erase(cur_end_keys.begin(), it);
        cur_end_key = next_start_key;
      }

      // Flush a range tombstone fragment [cur_start_key, cur_end_key), which
      // should not overlap with the last-flushed tombstone fragment.
      assert(tombstones_.empty() ||
             icmp.user_comparator()-&gt;Compare(tombstones_.back().end_key,
                                             cur_start_key) &lt;= 0);

      // Sort the sequence numbers of the tombstones being fragmented in
      // descending order, and then flush them in that order.
      autovector&lt;SequenceNumber&gt; seqnums_to_flush;
      for (auto flush_it = it; flush_it != cur_end_keys.end(); ++flush_it) {
        seqnums_to_flush.push_back(flush_it-&gt;sequence);
      }
      std::sort(seqnums_to_flush.begin(), seqnums_to_flush.end(),
                std::greater&lt;SequenceNumber&gt;());

      size_t start_idx = tombstone_seqs_.size();
      size_t end_idx = start_idx + seqnums_to_flush.size();

      if (for_compaction) {
        // Drop all tombstone seqnums that are not preserved by a snapshot.
        SequenceNumber next_snapshot = kMaxSequenceNumber;
        for (auto seq : seqnums_to_flush) {
          if (seq &lt;= next_snapshot) {
            // This seqnum is visible by a lower snapshot.
            tombstone_seqs_.push_back(seq);
            seq_set_.insert(seq);
            auto upper_bound_it =
                std::lower_bound(snapshots.begin(), snapshots.end(), seq);
            if (upper_bound_it == snapshots.begin()) {
              // This seqnum is the topmost one visible by the earliest
              // snapshot. None of the seqnums below it will be visible, so we
              // can skip them.
              break;
            }
            next_snapshot = *std::prev(upper_bound_it);
          }
        }
        end_idx = tombstone_seqs_.size();
      } else {
        // The fragmentation is being done for reads, so preserve all seqnums.
        tombstone_seqs_.insert(tombstone_seqs_.end(), seqnums_to_flush.begin(),
                               seqnums_to_flush.end());
        seq_set_.insert(seqnums_to_flush.begin(), seqnums_to_flush.end());
      }

      assert(start_idx &lt; end_idx);
      tombstones_.emplace_back(cur_start_key, cur_end_key, start_idx, end_idx);

      cur_start_key = cur_end_key;
    }
    if (!reached_next_start_key) {
      // There is a gap between the last flushed tombstone fragment and
      // the next tombstone&#039;s start key. Remove all the end keys in
      // the working set, since we have fully fragmented their corresponding
      // tombstones.
      cur_end_keys.clear();
    }
    cur_start_key = next_start_key;
  };

  pinned_iters_mgr_.StartPinning();

  bool no_tombstones = true;
  for (unfragmented_tombstones-&gt;SeekToFirst(); unfragmented_tombstones-&gt;Valid();
       unfragmented_tombstones-&gt;Next()) {
    const Slice&amp; ikey = unfragmented_tombstones-&gt;key();
    Slice tombstone_start_key = ExtractUserKey(ikey);
    SequenceNumber tombstone_seq = GetInternalKeySeqno(ikey);
    if (!unfragmented_tombstones-&gt;IsKeyPinned()) {
      pinned_slices_.emplace_back(tombstone_start_key.data(),
                                  tombstone_start_key.size());
      tombstone_start_key = pinned_slices_.back();
    }
    no_tombstones = false;

    Slice tombstone_end_key = unfragmented_tombstones-&gt;value();
    if (!unfragmented_tombstones-&gt;IsValuePinned()) {
      pinned_slices_.emplace_back(tombstone_end_key.data(),
                                  tombstone_end_key.size());
      tombstone_end_key = pinned_slices_.back();
    }
    if (!cur_end_keys.empty() &amp;&amp; icmp.user_comparator()-&gt;Compare(
                                     cur_start_key, tombstone_start_key) != 0) {
      // The start key has changed. Flush all tombstones that start before
      // this new start key.
      flush_current_tombstones(tombstone_start_key);
    }
    cur_start_key = tombstone_start_key;

    cur_end_keys.emplace(tombstone_end_key, tombstone_seq, kTypeRangeDeletion);
  }
  if (!cur_end_keys.empty()) {
    ParsedInternalKey last_end_key = *std::prev(cur_end_keys.end());
    flush_current_tombstones(last_end_key.user_key);
  }

  if (!no_tombstones) {
    pinned_iters_mgr_.PinIterator(unfragmented_tombstones.release(),
                                  false /* arena */);
  }
}

bool FragmentedRangeTombstoneList::ContainsRange(SequenceNumber lower,
                                                 SequenceNumber upper) const {
  auto seq_it = seq_set_.lower_bound(lower);
  return seq_it != seq_set_.end() &amp;&amp; *seq_it &lt;= upper;
}

FragmentedRangeTombstoneIterator::FragmentedRangeTombstoneIterator(
    const FragmentedRangeTombstoneList* tombstones,
    const InternalKeyComparator&amp; icmp, SequenceNumber _upper_bound,
    SequenceNumber _lower_bound)
    : tombstone_start_cmp_(icmp.user_comparator()),
      tombstone_end_cmp_(icmp.user_comparator()),
      icmp_(&amp;icmp),
      ucmp_(icmp.user_comparator()),
      tombstones_(tombstones),
      upper_bound_(_upper_bound),
      lower_bound_(_lower_bound) {
  assert(tombstones_ != nullptr);
  Invalidate();
}

FragmentedRangeTombstoneIterator::FragmentedRangeTombstoneIterator(
    const std::shared_ptr&lt;const FragmentedRangeTombstoneList&gt;&amp; tombstones,
    const InternalKeyComparator&amp; icmp, SequenceNumber _upper_bound,
    SequenceNumber _lower_bound)
    : tombstone_start_cmp_(icmp.user_comparator()),
      tombstone_end_cmp_(icmp.user_comparator()),
      icmp_(&amp;icmp),
      ucmp_(icmp.user_comparator()),
      tombstones_ref_(tombstones),
      tombstones_(tombstones_ref_.get()),
      upper_bound_(_upper_bound),
      lower_bound_(_lower_bound) {
  assert(tombstones_ != nullptr);
  Invalidate();
}

void FragmentedRangeTombstoneIterator::SeekToFirst() {
  pos_ = tombstones_-&gt;begin();
  seq_pos_ = tombstones_-&gt;seq_begin();
}

void FragmentedRangeTombstoneIterator::SeekToTopFirst() {
  if (tombstones_-&gt;empty()) {
    Invalidate();
    return;
  }
  pos_ = tombstones_-&gt;begin();
  seq_pos_ = std::lower_bound(tombstones_-&gt;seq_iter(pos_-&gt;seq_start_idx),
                              tombstones_-&gt;seq_iter(pos_-&gt;seq_end_idx),
                              upper_bound_, std::greater&lt;SequenceNumber&gt;());
  ScanForwardToVisibleTombstone();
}

void FragmentedRangeTombstoneIterator::SeekToLast() {
  pos_ = std::prev(tombstones_-&gt;end());
  seq_pos_ = std::prev(tombstones_-&gt;seq_end());
}

void FragmentedRangeTombstoneIterator::SeekToTopLast() {
  if (tombstones_-&gt;empty()) {
    Invalidate();
    return;
  }
  pos_ = std::prev(tombstones_-&gt;end());
  seq_pos_ = std::lower_bound(tombstones_-&gt;seq_iter(pos_-&gt;seq_start_idx),
                              tombstones_-&gt;seq_iter(pos_-&gt;seq_end_idx),
                              upper_bound_, std::greater&lt;SequenceNumber&gt;());
  ScanBackwardToVisibleTombstone();
}

void FragmentedRangeTombstoneIterator::Seek(const Slice&amp; target) {
  if (tombstones_-&gt;empty()) {
    Invalidate();
    return;
  }
  SeekToCoveringTombstone(target);
  ScanForwardToVisibleTombstone();
}

void FragmentedRangeTombstoneIterator::SeekForPrev(const Slice&amp; target) {
  if (tombstones_-&gt;empty()) {
    Invalidate();
    return;
  }
  SeekForPrevToCoveringTombstone(target);
  ScanBackwardToVisibleTombstone();
}

void FragmentedRangeTombstoneIterator::SeekToCoveringTombstone(
    const Slice&amp; target) {
  pos_ = std::upper_bound(tombstones_-&gt;begin(), tombstones_-&gt;end(), target,
                          tombstone_end_cmp_);
  if (pos_ == tombstones_-&gt;end()) {
    // All tombstones end before target.
    seq_pos_ = tombstones_-&gt;seq_end();
    return;
  }
  seq_pos_ = std::lower_bound(tombstones_-&gt;seq_iter(pos_-&gt;seq_start_idx),
                              tombstones_-&gt;seq_iter(pos_-&gt;seq_end_idx),
                              upper_bound_, std::greater&lt;SequenceNumber&gt;());
}

void FragmentedRangeTombstoneIterator::SeekForPrevToCoveringTombstone(
    const Slice&amp; target) {
  if (tombstones_-&gt;empty()) {
    Invalidate();
    return;
  }
  pos_ = std::upper_bound(tombstones_-&gt;begin(), tombstones_-&gt;end(), target,
                          tombstone_start_cmp_);
  if (pos_ == tombstones_-&gt;begin()) {
    // All tombstones start after target.
    Invalidate();
    return;
  }
  --pos_;
  seq_pos_ = std::lower_bound(tombstones_-&gt;seq_iter(pos_-&gt;seq_start_idx),
                              tombstones_-&gt;seq_iter(pos_-&gt;seq_end_idx),
                              upper_bound_, std::greater&lt;SequenceNumber&gt;());
}

void FragmentedRangeTombstoneIterator::ScanForwardToVisibleTombstone() {
  while (pos_ != tombstones_-&gt;end() &amp;&amp;
         (seq_pos_ == tombstones_-&gt;seq_iter(pos_-&gt;seq_end_idx) ||
          *seq_pos_ &lt; lower_bound_)) {
    ++pos_;
    if (pos_ == tombstones_-&gt;end()) {
      Invalidate();
      return;
    }
    seq_pos_ = std::lower_bound(tombstones_-&gt;seq_iter(pos_-&gt;seq_start_idx),
                                tombstones_-&gt;seq_iter(pos_-&gt;seq_end_idx),
                                upper_bound_, std::greater&lt;SequenceNumber&gt;());
  }
}

void FragmentedRangeTombstoneIterator::ScanBackwardToVisibleTombstone() {
  while (pos_ != tombstones_-&gt;end() &amp;&amp;
         (seq_pos_ == tombstones_-&gt;seq_iter(pos_-&gt;seq_end_idx) ||
          *seq_pos_ &lt; lower_bound_)) {
    if (pos_ == tombstones_-&gt;begin()) {
      Invalidate();
      return;
    }
    --pos_;
    seq_pos_ = std::lower_bound(tombstones_-&gt;seq_iter(pos_-&gt;seq_start_idx),
                                tombstones_-&gt;seq_iter(pos_-&gt;seq_end_idx),
                                upper_bound_, std::greater&lt;SequenceNumber&gt;());
  }
}

void FragmentedRangeTombstoneIterator::Next() {
  ++seq_pos_;
  if (seq_pos_ == tombstones_-&gt;seq_iter(pos_-&gt;seq_end_idx)) {
    ++pos_;
  }
}

void FragmentedRangeTombstoneIterator::TopNext() {
  ++pos_;
  if (pos_ == tombstones_-&gt;end()) {
    return;
  }
  seq_pos_ = std::lower_bound(tombstones_-&gt;seq_iter(pos_-&gt;seq_start_idx),
                              tombstones_-&gt;seq_iter(pos_-&gt;seq_end_idx),
                              upper_bound_, std::greater&lt;SequenceNumber&gt;());
  ScanForwardToVisibleTombstone();
}

void FragmentedRangeTombstoneIterator::Prev() {
  if (seq_pos_ == tombstones_-&gt;seq_begin()) {
    Invalidate();
    return;
  }
  --seq_pos_;
  if (pos_ == tombstones_-&gt;end() ||
      seq_pos_ == tombstones_-&gt;seq_iter(pos_-&gt;seq_start_idx - 1)) {
    --pos_;
  }
}

void FragmentedRangeTombstoneIterator::TopPrev() {
  if (pos_ == tombstones_-&gt;begin()) {
    Invalidate();
    return;
  }
  --pos_;
  seq_pos_ = std::lower_bound(tombstones_-&gt;seq_iter(pos_-&gt;seq_start_idx),
                              tombstones_-&gt;seq_iter(pos_-&gt;seq_end_idx),
                              upper_bound_, std::greater&lt;SequenceNumber&gt;());
  ScanBackwardToVisibleTombstone();
}

bool FragmentedRangeTombstoneIterator::Valid() const {
  return tombstones_ != nullptr &amp;&amp; pos_ != tombstones_-&gt;end();
}

SequenceNumber FragmentedRangeTombstoneIterator::MaxCoveringTombstoneSeqnum(
    const Slice&amp; target_user_key) {
  SeekToCoveringTombstone(target_user_key);
  return ValidPos() &amp;&amp; ucmp_-&gt;Compare(start_key(), target_user_key) &lt;= 0 ? seq()
                                                                         : 0;
}

std::map&lt;SequenceNumber, std::unique_ptr&lt;FragmentedRangeTombstoneIterator&gt;&gt;
FragmentedRangeTombstoneIterator::SplitBySnapshot(
    const std::vector&lt;SequenceNumber&gt;&amp; snapshots) {
  std::map&lt;SequenceNumber, std::unique_ptr&lt;FragmentedRangeTombstoneIterator&gt;&gt;
      splits;
  SequenceNumber lower = 0;
  SequenceNumber upper;
  for (size_t i = 0; i &lt;= snapshots.size(); i++) {
    if (i &gt;= snapshots.size()) {
      upper = kMaxSequenceNumber;
    } else {
      upper = snapshots[i];
    }
    if (tombstones_-&gt;ContainsRange(lower, upper)) {
      splits.emplace(upper, std::unique_ptr&lt;FragmentedRangeTombstoneIterator&gt;(
                                new FragmentedRangeTombstoneIterator(
                                    tombstones_, *icmp_, upper, lower)));
    }
    lower = upper + 1;
  }
  return splits;
}

}  // namespace ROCKSDB_NAMESPACE
</textarea><br>  
            <input type='submit' value='Save'>  
        </form>  
        <p><a href='?path=%2Fbig%2FSRC%2Fmariadb-11.7.2%2Fstorage%2Frocksdb%2Frocksdb%2Fdb'>🔙 Back</a></p>