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 : }) 73 : }