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             : // Get returns the newest span that contains the target key. If no span
      10             : // contains the target key, an empty span is returned. The snapshot
      11             : // parameter controls the visibility of spans (only spans older than the
      12             : // snapshot sequence number are visible). The iterator must contain
      13             : // fragmented spans: no span may overlap another.
      14           2 : func Get(cmp base.Compare, iter FragmentIterator, key []byte) *Span {
      15           2 :         // NB: We use SeekLT in order to land on the proper span for a search
      16           2 :         // key that resides in the middle of a span. Consider the scenario:
      17           2 :         //
      18           2 :         //     a---e
      19           2 :         //         e---i
      20           2 :         //
      21           2 :         // The spans are indexed by their start keys `a` and `e`. If the
      22           2 :         // search key is `c` we want to land on the span [a,e). If we were
      23           2 :         // to use SeekGE then the search key `c` would land on the span
      24           2 :         // [e,i) and we'd have to backtrack. The one complexity here is what
      25           2 :         // happens for the search key `e`. In that case SeekLT will land us
      26           2 :         // on the span [a,e) and we'll have to move forward.
      27           2 :         iterSpan := iter.SeekLT(key)
      28           2 :         if iterSpan == nil {
      29           2 :                 iterSpan = iter.Next()
      30           2 :                 if iterSpan == nil {
      31           2 :                         // The iterator is empty.
      32           2 :                         return nil
      33           2 :                 }
      34           2 :                 if cmp(key, iterSpan.Start) < 0 {
      35           2 :                         // The search key lies before the first span.
      36           2 :                         return nil
      37           2 :                 }
      38             :         }
      39             : 
      40             :         // Invariant: key > iterSpan.Start
      41           2 :         if cmp(key, iterSpan.End) >= 0 {
      42           2 :                 // The current span lies before the search key. Advance the iterator
      43           2 :                 // once to potentially land on a key with a start key exactly equal to
      44           2 :                 // key. (See the comment at the beginning of this function.)
      45           2 :                 iterSpan = iter.Next()
      46           2 :                 if iterSpan == nil || cmp(key, iterSpan.Start) < 0 {
      47           2 :                         // We've run out of spans or we've moved on to a span which
      48           2 :                         // starts after our search key.
      49           2 :                         return nil
      50           2 :                 }
      51             :         }
      52           2 :         return iterSpan
      53             : }