Line data Source code
1 : // Copyright 2019 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 (
8 : "github.com/cockroachdb/pebble/internal/base"
9 : "github.com/cockroachdb/pebble/internal/invariants"
10 : )
11 :
12 : // Truncate creates a new iterator where every span in the supplied iterator is
13 : // truncated to be contained within the given user key bounds.
14 : //
15 : // Note that fragment iterator Spans always have exclusive end-keys; if the
16 : // given bounds have an inclusive end key, then the input iterator must not
17 : // produce a span that contains that key. The only difference between bounds.End
18 : // being inclusive vs exclusive is this extra check.
19 1 : func Truncate(cmp base.Compare, iter FragmentIterator, bounds base.UserKeyBounds) FragmentIterator {
20 1 : return &truncatingIter{
21 1 : iter: iter,
22 1 : cmp: cmp,
23 1 : bounds: bounds,
24 1 : }
25 1 : }
26 :
27 : type truncatingIter struct {
28 : iter FragmentIterator
29 : cmp base.Compare
30 :
31 : bounds base.UserKeyBounds
32 :
33 : span Span
34 : }
35 :
36 : // SeekGE implements FragmentIterator.
37 1 : func (i *truncatingIter) SeekGE(key []byte) (*Span, error) {
38 1 : span, err := i.iter.SeekGE(key)
39 1 : if err != nil {
40 0 : return nil, err
41 0 : }
42 1 : span, spanBoundsChanged, err := i.nextSpanWithinBounds(span, +1)
43 1 : if err != nil {
44 0 : return nil, err
45 0 : }
46 : // nextSpanWithinBounds could return a span that's less than key, if the end
47 : // bound was truncated to end at a key less than or equal to `key`. Detect
48 : // this case and next/invalidate the iter.
49 1 : if spanBoundsChanged && i.cmp(span.End, key) <= 0 {
50 1 : return i.Next()
51 1 : }
52 1 : return span, nil
53 : }
54 :
55 : // SeekLT implements FragmentIterator.
56 1 : func (i *truncatingIter) SeekLT(key []byte) (*Span, error) {
57 1 : span, err := i.iter.SeekLT(key)
58 1 : if err != nil {
59 0 : return nil, err
60 0 : }
61 1 : span, spanBoundsChanged, err := i.nextSpanWithinBounds(span, -1)
62 1 : if err != nil {
63 0 : return nil, err
64 0 : }
65 : // nextSpanWithinBounds could return a span that's >= key, if the start bound
66 : // was truncated to start at a key greater than or equal to `key`. Detect this
67 : // case and prev/invalidate the iter.
68 1 : if spanBoundsChanged && i.cmp(span.Start, key) >= 0 {
69 1 : return i.Prev()
70 1 : }
71 1 : return span, nil
72 : }
73 :
74 : // First implements FragmentIterator.
75 1 : func (i *truncatingIter) First() (*Span, error) {
76 1 : span, err := i.iter.First()
77 1 : if err != nil {
78 0 : return nil, err
79 0 : }
80 1 : span, _, err = i.nextSpanWithinBounds(span, +1)
81 1 : return span, err
82 : }
83 :
84 : // Last implements FragmentIterator.
85 1 : func (i *truncatingIter) Last() (*Span, error) {
86 1 : span, err := i.iter.Last()
87 1 : if err != nil {
88 0 : return nil, err
89 0 : }
90 1 : span, _, err = i.nextSpanWithinBounds(span, -1)
91 1 : return span, err
92 : }
93 :
94 : // Next implements FragmentIterator.
95 1 : func (i *truncatingIter) Next() (*Span, error) {
96 1 : span, err := i.iter.Next()
97 1 : if err != nil {
98 0 : return nil, err
99 0 : }
100 1 : span, _, err = i.nextSpanWithinBounds(span, +1)
101 1 : return span, err
102 : }
103 :
104 : // Prev implements FragmentIterator.
105 1 : func (i *truncatingIter) Prev() (*Span, error) {
106 1 : span, err := i.iter.Prev()
107 1 : if err != nil {
108 0 : return nil, err
109 0 : }
110 1 : span, _, err = i.nextSpanWithinBounds(span, -1)
111 1 : return span, err
112 : }
113 :
114 : // Close implements FragmentIterator.
115 1 : func (i *truncatingIter) Close() error {
116 1 : return i.iter.Close()
117 1 : }
118 :
119 : // nextSpanWithinBounds returns the first span (starting with the given span and
120 : // advancing in the given direction) that intersects the bounds. It returns a
121 : // span that is entirely within the bounds; spanBoundsChanged indicates if the span
122 : // bounds had to be truncated.
123 : func (i *truncatingIter) nextSpanWithinBounds(
124 : span *Span, dir int8,
125 1 : ) (_ *Span, spanBoundsChanged bool, _ error) {
126 1 : var err error
127 1 : for span != nil {
128 1 : if i.bounds.End.Kind == base.Inclusive && span.Contains(i.cmp, i.bounds.End.Key) {
129 0 : err := base.AssertionFailedf("inclusive upper bound %q inside span %s", i.bounds.End.Key, span)
130 0 : if invariants.Enabled {
131 0 : panic(err)
132 : }
133 0 : return nil, false, err
134 : }
135 : // Intersect [span.Start, span.End) with [i.bounds.Start, i.bounds.End.Key).
136 1 : spanBoundsChanged = false
137 1 : start := span.Start
138 1 : if i.cmp(start, i.bounds.Start) < 0 {
139 1 : spanBoundsChanged = true
140 1 : start = i.bounds.Start
141 1 : }
142 1 : end := span.End
143 1 : if i.cmp(end, i.bounds.End.Key) > 0 {
144 1 : spanBoundsChanged = true
145 1 : end = i.bounds.End.Key
146 1 : }
147 1 : if !spanBoundsChanged {
148 1 : return span, false, nil
149 1 : }
150 1 : if i.cmp(start, end) < 0 {
151 1 : i.span = Span{
152 1 : Start: start,
153 1 : End: end,
154 1 : Keys: span.Keys,
155 1 : KeysOrder: span.KeysOrder,
156 1 : }
157 1 : return &i.span, true, nil
158 1 : }
159 : // Span is outside of bounds, find the next one.
160 1 : if dir == +1 {
161 1 : span, err = i.iter.Next()
162 1 : } else {
163 1 : span, err = i.iter.Prev()
164 1 : }
165 : }
166 : // NB: err may be nil or non-nil.
167 1 : return nil, false, err
168 : }
169 :
170 : // WrapChildren implements FragmentIterator.
171 0 : func (i *truncatingIter) WrapChildren(wrap WrapFn) {
172 0 : i.iter = wrap(i.iter)
173 0 : }
|
