src/scan/ByteRange.bend
mylsm-lsm-store@0.6.0.0 · 129 lines · 0 definitions
1import Base
2import mylsm-lsm-store@0.6.0.0/src/Keys.bend as Keys
3import bend-kit-bytes@0.3.2.0/bytes.bend as Bytes
4
5# Reifies two independently owned copies of a byte buffer.
6def clone.pair(+len: U32, copied: Array<U32> & Array<U32>) -> Bytes.Bytes & Bytes.Bytes:
7 match copied:
8 case (left, right):
9 (Bytes.Bytes{len, left}, Bytes.Bytes{len, right})
10
11# Clones a byte buffer when range checks need both bounds.
12def clone.split(bytes: Bytes.Bytes) -> Bytes.Bytes & Bytes.Bytes:
13 match bytes:
14 case Bytes.Bytes{+len, buf}:
15 clone.pair(len, Bytes.copy.bytes(len, buf, Bytes.alloc(len), 0, 0))
16
17# Returns whether a key satisfies an optional inclusive lower bound.
18def lower.result(comparison: Bytes.Bytes & Bytes.Bytes & Cmp) -> Bool:
19 match comparison:
20 case (_, _, LT{}):
21 False{}
22 case _:
23 True{}
24
25# Checks an optional lower bound using the canonical byte comparator.
26def lower(key: Bytes.Bytes, bound: Maybe<&1, Bytes.Bytes>) -> Bool:
27 match bound:
28 case None{}:
29 True{}
30 case Some{value}:
31 lower.result(Keys.Bytes.cmp.with_inputs(key, value))
32
33# Returns whether a key sorts strictly below an optional upper bound.
34def upper.result(comparison: Bytes.Bytes & Bytes.Bytes & Cmp) -> Bool:
35 match comparison:
36 case (_, _, LT{}):
37 True{}
38 case _:
39 False{}
40
41# Checks an optional exclusive upper bound using byte order.
42def upper(key: Bytes.Bytes, bound: Maybe<&1, Bytes.Bytes>) -> Bool:
43 match bound:
44 case None{}:
45 True{}
46 case Some{value}:
47 upper.result(Keys.Bytes.cmp.with_inputs(key, value))
48
49def at_or_after_upper.result(comparison: Bytes.Bytes & Bytes.Bytes & Cmp) -> Bool:
50 match comparison:
51 case (_, _, LT{}): False{}
52 case _: True{}
53
54# Detects the first ordered key that cannot belong to a half-open range.
55def at_or_after_upper(key: Bytes.Bytes, bound: Maybe<&1, Bytes.Bytes>) -> Bool:
56 match bound:
57 case None{}: False{}
58 case Some{value}:
59 at_or_after_upper.result(Keys.Bytes.cmp.with_inputs(key, value))
60
61# Combines the lower and upper checks for a half-open range.
62def in_range.checked(lower_ok: Bool, upper_ok: Bool) -> Bool:
63 match lower_ok:
64 case True{}:
65 upper_ok
66 case False{}:
67 False{}
68
69# Checks a byte key against optional [lower, upper) bounds.
70def in_range.copies(
71 copies: Bytes.Bytes & Bytes.Bytes,
72 lower_bound: Maybe<&1, Bytes.Bytes>,
73 upper_bound: Maybe<&1, Bytes.Bytes>
74) -> Bool:
75 match copies:
76 case (lower_key, upper_key):
77 in_range.checked(lower(lower_key, lower_bound), upper(upper_key, upper_bound))
78
79# Checks a byte key against optional [lower, upper) bounds.
80def in_range(
81 key: Bytes.Bytes,
82 lower_bound: Maybe<&1, Bytes.Bytes>,
83 upper_bound: Maybe<&1, Bytes.Bytes>
84) -> Bool:
85 in_range.copies(clone.split(key), lower_bound, upper_bound)
86
87# Returns the equality component while consuming both preserved buffers.
88def prefix.equal(result: Bytes.Bytes & Bytes.Bytes & Bool) -> Bool:
89 match result:
90 case (_, _, equal):
91 equal
92
93# Compares a bounded key prefix with the requested bytes.
94def prefix.slice.result(
95 prefix: Bytes.Bytes,
96 pair: Bytes.Bytes & Bytes.Bytes
97) -> Bool:
98 match pair:
99 case (_, sliced):
100 prefix.equal(Bytes.eq(sliced, prefix))
101
102# Slices exactly the requested prefix length and compares the resulting bytes.
103def prefix.slice(key: Bytes.Bytes, prefix: Bytes.Bytes, +prefix_len: U32) -> Bool:
104 prefix.slice.result(prefix, Bytes.slice(key, 0, prefix_len))
105
106# Rejects prefixes longer than the key before slicing.
107def prefix.length.checked(
108 key: Bytes.Bytes,
109 prefix: Bytes.Bytes,
110 +prefix_len: U32,
111 +key_len: U32
112) -> Bool:
113 Bool.pick(Bool, U32.is_le(prefix_len, key_len),
114 prefix.slice(key, prefix, prefix_len), False{})
115
116# Unpacks measured key and prefix lengths before comparison.
117def prefix.lengths(
118 key_pair: Bytes.Bytes & U32,
119 prefix_pair: Bytes.Bytes & U32
120) -> Bool:
121 match key_pair:
122 case (key, key_len):
123 match prefix_pair:
124 case (prefix, prefix_len):
125 prefix.length.checked(key, prefix, prefix_len, key_len)
126
127# Checks whether a byte key begins with the exact byte prefix.
128def has_prefix(key: Bytes.Bytes, prefix: Bytes.Bytes) -> Bool:
129 prefix.lengths(Bytes.length(key), Bytes.length(prefix))