Line data Source code
1 : // Copyright 2022 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 : // FilterFunc defines a transform from the input Span into the output Span. The 8 : // function returns true if the Span should be returned by the iterator, and 9 : // false if the Span should be skipped. The FilterFunc is permitted to mutate 10 : // the output Span, for example, to elice certain keys, or update the Span's 11 : // bounds if so desired. The output Span's Keys slice may be reused to reduce 12 : // allocations. 13 : type FilterFunc func(in *Span, out *Span) (keep bool) 14 : 15 : // filteringIter is a FragmentIterator that uses a FilterFunc to select which 16 : // Spans from the input iterator are returned in the output. 17 : // 18 : // A note on Span lifetimes: as the FilterFunc reuses a Span with a mutable 19 : // slice of Keys to reduce allocations, Spans returned by this iterator are only 20 : // valid until the next relative or absolute positioning method is called. 21 : type filteringIter struct { 22 : iter FragmentIterator 23 : filterFn FilterFunc 24 : 25 : // span is a mutable Span passed to the filterFn. The filterFn is free to 26 : // mutate this Span. The slice of Keys in the Span is reused with every call 27 : // to the filterFn. 28 : span Span 29 : } 30 : 31 : var _ FragmentIterator = (*filteringIter)(nil) 32 : 33 : // Filter returns a new filteringIter that will filter the Spans from the 34 : // provided child iterator using the provided FilterFunc. 35 2 : func Filter(iter FragmentIterator, filter FilterFunc) FragmentIterator { 36 2 : return &filteringIter{iter: iter, filterFn: filter} 37 2 : } 38 : 39 : // SeekGE implements FragmentIterator. 40 2 : func (i *filteringIter) SeekGE(key []byte) *Span { 41 2 : return i.filter(i.iter.SeekGE(key), +1) 42 2 : } 43 : 44 : // SeekLT implements FragmentIterator. 45 2 : func (i *filteringIter) SeekLT(key []byte) *Span { 46 2 : return i.filter(i.iter.SeekLT(key), -1) 47 2 : } 48 : 49 : // First implements FragmentIterator. 50 2 : func (i *filteringIter) First() *Span { 51 2 : return i.filter(i.iter.First(), +1) 52 2 : } 53 : 54 : // Last implements FragmentIterator. 55 2 : func (i *filteringIter) Last() *Span { 56 2 : return i.filter(i.iter.Last(), -1) 57 2 : } 58 : 59 : // Next implements FragmentIterator. 60 2 : func (i *filteringIter) Next() *Span { 61 2 : return i.filter(i.iter.Next(), +1) 62 2 : } 63 : 64 : // Prev implements FragmentIterator. 65 2 : func (i *filteringIter) Prev() *Span { 66 2 : return i.filter(i.iter.Prev(), -1) 67 2 : } 68 : 69 : // Error implements FragmentIterator. 70 2 : func (i *filteringIter) Error() error { 71 2 : return i.iter.Error() 72 2 : } 73 : 74 : // Close implements FragmentIterator. 75 2 : func (i *filteringIter) Close() error { 76 2 : return i.iter.Close() 77 2 : } 78 : 79 : // filter uses the filterFn (if configured) to filter and possibly mutate the 80 : // given Span. If the current Span is to be skipped, the iterator continues 81 : // iterating in the given direction until it lands on a Span that should be 82 : // returned, or the iterator becomes invalid. 83 2 : func (i *filteringIter) filter(span *Span, dir int8) *Span { 84 2 : if i.filterFn == nil { 85 1 : return span 86 1 : } 87 2 : for i.Error() == nil && span != nil { 88 2 : if keep := i.filterFn(span, &i.span); keep { 89 2 : return &i.span 90 2 : } 91 2 : if dir == +1 { 92 2 : span = i.iter.Next() 93 2 : } else { 94 2 : span = i.iter.Prev() 95 2 : } 96 : } 97 2 : return span 98 : }