Line data    Source code

       1             : // Copyright 2019 The LevelDB-Go and Pebble Authors. All rights reserved. Use
       2             : // of this source code is governed by a BSD-style license that can be found in
       3             : // the LICENSE file.
       4             : 
       5             : package keyspan
       6             : 
       7             : import "github.com/cockroachdb/pebble/internal/base"
       8             : 
       9             : // Truncate creates a new iterator where every span in the supplied iterator is
      10             : // truncated to be contained within the range [lower, upper). If start and end
      11             : // are specified, filter out any spans that are completely outside those bounds.
      12             : func Truncate(
      13             :         cmp base.Compare,
      14             :         iter FragmentIterator,
      15             :         lower, upper []byte,
      16             :         start, end *base.InternalKey,
      17             :         panicOnUpperTruncate bool,
      18           1 : ) FragmentIterator {
      19           1 :         return Filter(iter, func(in *Span, out *Span) (keep bool) {
      20           1 :                 out.Start, out.End = in.Start, in.End
      21           1 :                 out.Keys = append(out.Keys[:0], in.Keys...)
      22           1 : 
      23           1 :                 // Ignore this span if it lies completely outside start, end. Note that
      24           1 :                 // end endInclusive indicated whether end is inclusive.
      25           1 :                 //
      26           1 :                 // The comparison between s.End and start is by user key only, as
      27           1 :                 // the span is exclusive at s.End, so comparing by user keys
      28           1 :                 // is sufficient.
      29           1 :                 if start != nil && cmp(in.End, start.UserKey) <= 0 {
      30           1 :                         return false
      31           1 :                 }
      32           1 :                 if end != nil {
      33           1 :                         v := cmp(in.Start, end.UserKey)
      34           1 :                         switch {
      35           1 :                         case v > 0:
      36           1 :                                 // Wholly outside the end bound. Skip it.
      37           1 :                                 return false
      38           1 :                         case v == 0:
      39           1 :                                 // This span begins at the same user key as `end`. Whether or
      40           1 :                                 // not any of the keys contained within the span are relevant is
      41           1 :                                 // dependent on Trailers. Any keys contained within the span
      42           1 :                                 // with trailers larger than end cover the small sliver of
      43           1 :                                 // keyspace between [k#inf, k#<end-seqnum>]. Since keys are
      44           1 :                                 // sorted descending by Trailer within the span, we need to find
      45           1 :                                 // the prefix of keys with larger trailers.
      46           1 :                                 for i := range in.Keys {
      47           1 :                                         if in.Keys[i].Trailer < end.Trailer {
      48           1 :                                                 out.Keys = out.Keys[:i]
      49           1 :                                                 break
      50             :                                         }
      51             :                                 }
      52           1 :                         default:
      53             :                                 // Wholly within the end bound. Keep it.
      54             :                         }
      55             :                 }
      56             : 
      57           1 :                 var truncated bool
      58           1 :                 // Truncate the bounds to lower and upper.
      59           1 :                 if cmp(in.Start, lower) < 0 {
      60           1 :                         out.Start = lower
      61           1 :                 }
      62           1 :                 if cmp(in.End, upper) > 0 {
      63           1 :                         truncated = true
      64           1 :                         out.End = upper
      65           1 :                 }
      66             : 
      67           1 :                 if panicOnUpperTruncate && truncated {
      68           0 :                         panic("pebble: upper bound should not be truncated")
      69             :                 }
      70             : 
      71           1 :                 return !out.Empty() && cmp(out.Start, out.End) < 0
      72             :         }, cmp)
      73             : }