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 1 : func Filter(iter FragmentIterator, filter FilterFunc) FragmentIterator { 36 1 : return &filteringIter{iter: iter, filterFn: filter} 37 1 : } 38 : 39 : // SeekGE implements FragmentIterator. 40 1 : func (i *filteringIter) SeekGE(key []byte) *Span { 41 1 : return i.filter(i.iter.SeekGE(key), +1) 42 1 : } 43 : 44 : // SeekLT implements FragmentIterator. 45 1 : func (i *filteringIter) SeekLT(key []byte) *Span { 46 1 : return i.filter(i.iter.SeekLT(key), -1) 47 1 : } 48 : 49 : // First implements FragmentIterator. 50 1 : func (i *filteringIter) First() *Span { 51 1 : return i.filter(i.iter.First(), +1) 52 1 : } 53 : 54 : // Last implements FragmentIterator. 55 1 : func (i *filteringIter) Last() *Span { 56 1 : return i.filter(i.iter.Last(), -1) 57 1 : } 58 : 59 : // Next implements FragmentIterator. 60 1 : func (i *filteringIter) Next() *Span { 61 1 : return i.filter(i.iter.Next(), +1) 62 1 : } 63 : 64 : // Prev implements FragmentIterator. 65 1 : func (i *filteringIter) Prev() *Span { 66 1 : return i.filter(i.iter.Prev(), -1) 67 1 : } 68 : 69 : // Error implements FragmentIterator. 70 1 : func (i *filteringIter) Error() error { 71 1 : return i.iter.Error() 72 1 : } 73 : 74 : // Close implements FragmentIterator. 75 1 : func (i *filteringIter) Close() error { 76 1 : return i.iter.Close() 77 1 : } 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 1 : func (i *filteringIter) filter(span *Span, dir int8) *Span { 84 1 : if i.filterFn == nil { 85 0 : return span 86 0 : } 87 1 : for i.Error() == nil && span != nil { 88 1 : if keep := i.filterFn(span, &i.span); keep { 89 1 : return &i.span 90 1 : } 91 1 : if dir == +1 { 92 1 : span = i.iter.Next() 93 1 : } else { 94 1 : span = i.iter.Prev() 95 1 : } 96 : } 97 1 : return span 98 : }