Line data Source code
1 : // Copyright 2024 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 base
6 :
7 : import (
8 : "fmt"
9 :
10 : "github.com/cockroachdb/pebble/internal/invariants"
11 : )
12 :
13 : // BoundaryKind indicates if a boundary is exclusive or inclusive.
14 : type BoundaryKind uint8
15 :
16 : // The two possible values of BoundaryKind.
17 : //
18 : // Note that we prefer Exclusive to be the zero value, so that zero
19 : // UserKeyBounds are not valid.
20 : const (
21 : Exclusive BoundaryKind = iota
22 : Inclusive
23 : )
24 :
25 : // UserKeyBoundary represents the endpoint of a bound which can be exclusive or
26 : // inclusive.
27 : type UserKeyBoundary struct {
28 : Key []byte
29 : Kind BoundaryKind
30 : }
31 :
32 : // UserKeyInclusive creates an inclusive user key boundary.
33 1 : func UserKeyInclusive(userKey []byte) UserKeyBoundary {
34 1 : return UserKeyBoundary{
35 1 : Key: userKey,
36 1 : Kind: Inclusive,
37 1 : }
38 1 : }
39 :
40 : // UserKeyExclusive creates an exclusive user key boundary.
41 1 : func UserKeyExclusive(userKey []byte) UserKeyBoundary {
42 1 : return UserKeyBoundary{
43 1 : Key: userKey,
44 1 : Kind: Exclusive,
45 1 : }
46 1 : }
47 :
48 : // UserKeyExclusiveIf creates a user key boundary which can be either inclusive
49 : // or exclusive.
50 1 : func UserKeyExclusiveIf(userKey []byte, exclusive bool) UserKeyBoundary {
51 1 : kind := Inclusive
52 1 : if exclusive {
53 1 : kind = Exclusive
54 1 : }
55 1 : return UserKeyBoundary{
56 1 : Key: userKey,
57 1 : Kind: kind,
58 1 : }
59 : }
60 :
61 : // IsUpperBoundFor returns true if the boundary is an upper bound for the key;
62 : // i.e. the key is less than the boundary key OR they are equal and the boundary
63 : // is inclusive.
64 1 : func (eb UserKeyBoundary) IsUpperBoundFor(cmp Compare, userKey []byte) bool {
65 1 : c := cmp(userKey, eb.Key)
66 1 : return c < 0 || (c == 0 && eb.Kind == Inclusive)
67 1 : }
68 :
69 : // IsUpperBoundForInternalKey returns true if boundary is an upper bound for the
70 : // given internal key.
71 1 : func (eb UserKeyBoundary) IsUpperBoundForInternalKey(cmp Compare, key InternalKey) bool {
72 1 : c := cmp(key.UserKey, eb.Key)
73 1 : return c < 0 || (c == 0 && (eb.Kind == Inclusive || key.IsExclusiveSentinel()))
74 1 : }
75 :
76 : // CompareUpperBounds compares two UserKeyBoundaries as upper bounds (e.g. when
77 : // they are used for UserKeyBounds.End).
78 1 : func (eb UserKeyBoundary) CompareUpperBounds(cmp Compare, other UserKeyBoundary) int {
79 1 : switch c := cmp(eb.Key, other.Key); {
80 1 : case c != 0:
81 1 : return c
82 1 : case eb.Kind == other.Kind:
83 1 : return 0
84 1 : case eb.Kind == Inclusive:
85 1 : // eb is inclusive, other is exclusive.
86 1 : return 1
87 1 : default:
88 1 : // eb is exclusive, other is inclusive.
89 1 : return -1
90 : }
91 : }
92 :
93 : // UserKeyBounds is a user key interval with an inclusive start boundary and
94 : // with an end boundary that can be either inclusive or exclusive.
95 : type UserKeyBounds struct {
96 : Start []byte
97 : End UserKeyBoundary
98 : }
99 :
100 : // UserKeyBoundsInclusive creates the bounds [start, end].
101 1 : func UserKeyBoundsInclusive(start []byte, end []byte) UserKeyBounds {
102 1 : return UserKeyBounds{
103 1 : Start: start,
104 1 : End: UserKeyInclusive(end),
105 1 : }
106 1 : }
107 :
108 : // UserKeyBoundsEndExclusive creates the bounds [start, end).
109 1 : func UserKeyBoundsEndExclusive(start []byte, end []byte) UserKeyBounds {
110 1 : return UserKeyBounds{
111 1 : Start: start,
112 1 : End: UserKeyExclusive(end),
113 1 : }
114 1 : }
115 :
116 : // UserKeyBoundsEndExclusiveIf creates either [start, end] or [start, end) bounds.
117 1 : func UserKeyBoundsEndExclusiveIf(start []byte, end []byte, exclusive bool) UserKeyBounds {
118 1 : return UserKeyBounds{
119 1 : Start: start,
120 1 : End: UserKeyExclusiveIf(end, exclusive),
121 1 : }
122 1 : }
123 :
124 : // UserKeyBoundsFromInternal creates the bounds
125 : // [smallest.UserKey, largest.UserKey] or [smallest.UserKey, largest.UserKey) if
126 : // largest is an exclusive sentinel.
127 : //
128 : // smallest must not be an exclusive sentinel.
129 1 : func UserKeyBoundsFromInternal(smallest, largest InternalKey) UserKeyBounds {
130 1 : if invariants.Enabled && smallest.IsExclusiveSentinel() {
131 0 : panic("smallest key is exclusive sentinel")
132 : }
133 1 : return UserKeyBoundsEndExclusiveIf(smallest.UserKey, largest.UserKey, largest.IsExclusiveSentinel())
134 : }
135 :
136 : // Valid returns true if the bounds contain at least a user key.
137 0 : func (b *UserKeyBounds) Valid(cmp Compare) bool {
138 0 : return b.End.IsUpperBoundFor(cmp, b.Start)
139 0 : }
140 :
141 : // Overlaps returns true if the bounds overlap.
142 1 : func (b *UserKeyBounds) Overlaps(cmp Compare, other *UserKeyBounds) bool {
143 1 : // There is no overlap iff one interval starts after the other ends.
144 1 : return other.End.IsUpperBoundFor(cmp, b.Start) && b.End.IsUpperBoundFor(cmp, other.Start)
145 1 : }
146 :
147 : // ContainsBounds returns true if b completely overlaps other.
148 1 : func (b *UserKeyBounds) ContainsBounds(cmp Compare, other *UserKeyBounds) bool {
149 1 : if cmp(b.Start, other.Start) > 0 {
150 1 : return false
151 1 : }
152 1 : return other.End.CompareUpperBounds(cmp, b.End) <= 0
153 : }
154 :
155 : // ContainsUserKey returns true if the user key is within the bounds.
156 0 : func (b *UserKeyBounds) ContainsUserKey(cmp Compare, userKey []byte) bool {
157 0 : return cmp(b.Start, userKey) <= 0 && b.End.IsUpperBoundFor(cmp, userKey)
158 0 : }
159 :
160 : // ContainsInternalKey returns true if the internal key is within the bounds.
161 1 : func (b *UserKeyBounds) ContainsInternalKey(cmp Compare, key InternalKey) bool {
162 1 : c := cmp(b.Start, key.UserKey)
163 1 : return (c < 0 || (c == 0 && !key.IsExclusiveSentinel())) &&
164 1 : b.End.IsUpperBoundForInternalKey(cmp, key)
165 1 : }
166 :
167 0 : func (b UserKeyBounds) String() string {
168 0 : return b.Format(DefaultFormatter)
169 0 : }
170 :
171 : // Format converts the bounds to a string of the form "[foo, bar]" or
172 : // "[foo, bar)", using the given key formatter.
173 0 : func (b UserKeyBounds) Format(fmtKey FormatKey) string {
174 0 : endC := ']'
175 0 : if b.End.Kind == Exclusive {
176 0 : endC = ')'
177 0 : }
178 0 : return fmt.Sprintf("[%s, %s%c", fmtKey(b.Start), fmtKey(b.End.Key), endC)
179 : }
|
