src/scan/BlockOrder.bend

mylsm-lsm-store@0.6.0.1 · 56 lines · 8 definitions

1import Base
2import mylsm-lsm-store@0.6.0.1/src/ByteMemTable.bend as ByteMemTable
3import mylsm-lsm-store@0.6.0.1/src/Keys.bend as Keys
4import bend-kit-bytes@0.3.2.0/bytes.bend as Bytes
5
6# Tracks strict ordering and the last key across decoded SST blocks.
7type State is Type:
8  State{valid: Bool, last_key: Maybe<&1, Bytes.Bytes>, count: Nat}
9
10# Starts a block-order check with the preceding block's last key.
11def empty(previous: Maybe<&1, Bytes.Bytes>) -> State:
12  State{True{}, previous, 0n}
13
14def compare.result(comparison: Bytes.Bytes & Bytes.Bytes & Cmp) -> Bool:
15  match comparison:
16    case (_, _, LT{}): True{}
17    case _: False{}
18
19# Requires each new key to sort strictly after the preceding key.
20def compare(previous: Maybe<&1, Bytes.Bytes>, key: Bytes.Bytes) -> Bool:
21  match previous:
22    case None{}: True{}
23    case Some{last}:
24      compare.result(Keys.Bytes.cmp.with_inputs(last, key))
25
26def advance.state(
27  previous: Maybe<&1, Bytes.Bytes>,
28  +count: Nat,
29  valid: Bool,
30  copies: Bytes.Bytes & Bytes.Bytes
31) -> State:
32  match copies:
33    case (for_compare, retained):
34      State{valid && compare(previous, for_compare), Some{retained},
35        Nat.add(count, 1n)}
36
37# Validates one entry and retains its key as the next comparison boundary.
38def advance(entry: ByteMemTable.Entry, state: State) -> State:
39  match entry:
40    case ByteMemTable.Entry{key, _}:
41      match state:
42        case State{valid, previous, count}:
43          advance.state(previous, count, valid,
44            ByteMemTable.bytes.clone(key))
45
46# Checks every ordered entry in a block and carries the final key forward.
47def go(entries: List<&1, ByteMemTable.Entry>, state: State) -> State:
48  match entries:
49    case Nil{}: state
50    case Con{entry, tail}:
51      go(tail, advance(entry, state))
52
53# Reports whether all keys seen so far were strictly ascending.
54def accepted(state: State) -> Bool:
55  match state:
56    case State{valid, _, _}: valid