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