Line data    Source code

       1             : // Copyright 2018 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             : // SeekLE seeks to the span that contains or is before the target key.
      10           2 : func SeekLE(cmp base.Compare, iter FragmentIterator, key []byte) *Span {
      11           2 :         // NB: We use SeekLT in order to land on the proper span for a search
      12           2 :         // key that resides in the middle of a span. Consider the scenario:
      13           2 :         //
      14           2 :         //     a---e
      15           2 :         //         e---i
      16           2 :         //
      17           2 :         // The spans are indexed by their start keys `a` and `e`. If the
      18           2 :         // search key is `c` we want to land on the span [a,e). If we were to
      19           2 :         // use SeekGE then the search key `c` would land on the span [e,i) and
      20           2 :         // we'd have to backtrack. The one complexity here is what happens for the
      21           2 :         // search key `e`. In that case SeekLT will land us on the span [a,e)
      22           2 :         // and we'll have to move forward.
      23           2 :         iterSpan := iter.SeekLT(key)
      24           2 : 
      25           2 :         if iterSpan == nil {
      26           2 :                 // Advance the iterator once to see if the next span has a start key
      27           2 :                 // equal to key.
      28           2 :                 iterSpan = iter.Next()
      29           2 :                 if iterSpan == nil || cmp(key, iterSpan.Start) < 0 {
      30           2 :                         // The iterator is exhausted or we've hit the next span.
      31           2 :                         return nil
      32           2 :                 }
      33           2 :         } else {
      34           2 :                 // Invariant: key > iterSpan.Start
      35           2 :                 if cmp(key, iterSpan.End) >= 0 {
      36           2 :                         // The current span lies entirely before the search key. Check to see if
      37           2 :                         // the next span contains the search key. If it doesn't, we'll backup
      38           2 :                         // and return to our earlier candidate.
      39           2 :                         iterSpan = iter.Next()
      40           2 :                         if iterSpan == nil || cmp(key, iterSpan.Start) < 0 {
      41           2 :                                 // The next span is past our search key or there is no next span. Go
      42           2 :                                 // back.
      43           2 :                                 iterSpan = iter.Prev()
      44           2 :                         }
      45             :                 }
      46             :         }
      47           2 :         return iterSpan
      48             : }