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 : // UserKeyBounds is a user key interval with an inclusive start boundary and
77 : // with an end boundary that can be either inclusive or exclusive.
78 : type UserKeyBounds struct {
79 : Start []byte
80 : End UserKeyBoundary
81 : }
82 :
83 : // UserKeyBoundsInclusive creates the bounds [start, end].
84 1 : func UserKeyBoundsInclusive(start []byte, end []byte) UserKeyBounds {
85 1 : return UserKeyBounds{
86 1 : Start: start,
87 1 : End: UserKeyInclusive(end),
88 1 : }
89 1 : }
90 :
91 : // UserKeyBoundsEndExclusive creates the bounds [start, end).
92 1 : func UserKeyBoundsEndExclusive(start []byte, end []byte) UserKeyBounds {
93 1 : return UserKeyBounds{
94 1 : Start: start,
95 1 : End: UserKeyExclusive(end),
96 1 : }
97 1 : }
98 :
99 : // UserKeyBoundsEndExclusiveIf creates either [start, end] or [start, end) bounds.
100 1 : func UserKeyBoundsEndExclusiveIf(start []byte, end []byte, exclusive bool) UserKeyBounds {
101 1 : return UserKeyBounds{
102 1 : Start: start,
103 1 : End: UserKeyExclusiveIf(end, exclusive),
104 1 : }
105 1 : }
106 :
107 : // UserKeyBoundsFromInternal creates the bounds
108 : // [smallest.UserKey, largest.UserKey] or [smallest.UserKey, largest.UserKey) if
109 : // largest is an exclusive sentinel.
110 : //
111 : // smallest must not be an exclusive sentinel.
112 1 : func UserKeyBoundsFromInternal(smallest, largest InternalKey) UserKeyBounds {
113 1 : if invariants.Enabled && smallest.IsExclusiveSentinel() {
114 0 : panic("smallest key is exclusive sentinel")
115 : }
116 1 : return UserKeyBoundsEndExclusiveIf(smallest.UserKey, largest.UserKey, largest.IsExclusiveSentinel())
117 : }
118 :
119 : // Valid returns true if the bounds contain at least a user key.
120 1 : func (b *UserKeyBounds) Valid(cmp Compare) bool {
121 1 : return b.End.IsUpperBoundFor(cmp, b.Start)
122 1 : }
123 :
124 : // Overlaps returns true if the bounds overlap.
125 1 : func (b *UserKeyBounds) Overlaps(cmp Compare, other *UserKeyBounds) bool {
126 1 : // There is no overlap iff one interval starts after the other ends.
127 1 : return other.End.IsUpperBoundFor(cmp, b.Start) && b.End.IsUpperBoundFor(cmp, other.Start)
128 1 : }
129 :
130 : // ContainsBounds returns true if b completely overlaps other.
131 1 : func (b *UserKeyBounds) ContainsBounds(cmp Compare, other *UserKeyBounds) bool {
132 1 : if cmp(b.Start, other.Start) > 0 {
133 1 : return false
134 1 : }
135 1 : c := cmp(other.End.Key, b.End.Key)
136 1 : return c < 0 || (c == 0 && (b.End.Kind == Inclusive || other.End.Kind == Exclusive))
137 : }
138 :
139 : // ContainsUserKey returns true if the user key is within the bounds.
140 1 : func (b *UserKeyBounds) ContainsUserKey(cmp Compare, userKey []byte) bool {
141 1 : return cmp(b.Start, userKey) <= 0 && b.End.IsUpperBoundFor(cmp, userKey)
142 1 : }
143 :
144 : // ContainsInternalKey returns true if the internal key is within the bounds.
145 1 : func (b *UserKeyBounds) ContainsInternalKey(cmp Compare, key InternalKey) bool {
146 1 : c := cmp(b.Start, key.UserKey)
147 1 : return (c < 0 || (c == 0 && !key.IsExclusiveSentinel())) &&
148 1 : b.End.IsUpperBoundForInternalKey(cmp, key)
149 1 : }
150 :
151 1 : func (b UserKeyBounds) String() string {
152 1 : return b.Format(DefaultFormatter)
153 1 : }
154 :
155 : // Format converts the bounds to a string of the form "[foo, bar]" or
156 : // "[foo, bar)", using the given key formatter.
157 1 : func (b UserKeyBounds) Format(fmtKey FormatKey) string {
158 1 : endC := ']'
159 1 : if b.End.Kind == Exclusive {
160 1 : endC = ')'
161 1 : }
162 1 : return fmt.Sprintf("[%s, %s%c", fmtKey(b.Start), fmtKey(b.End.Key), endC)
163 : }
|
