src/scan/BlockRoutePolicy.bend
mylsm-lsm-store@0.6.0.0 · 61 lines · 0 definitions
1import Base
2import mylsm-lsm-store@0.6.0.0/src/Keys.bend as Keys
3import mylsm-lsm-store@0.6.0.0/src/coordinator/QueuePolicy.bend as QueuePolicy
4import bend-kit-bytes@0.3.2.0/bytes.bend as Bytes
5
6# Holds the binary-search interval and latest eligible block ordinal.
7type Search is Data:
8 Search{low: Nat, high: Nat, best: Nat}
9
10# Selects the lower or upper half of the separator search interval.
11type Move is Data:
12 SearchLower{}
13 SearchUpper{}
14
15def midpoint.copies(lows: Nat & Nat, high: Nat) -> Nat:
16 match lows:
17 case (offset, subtractor):
18 Nat.add(offset, Nat.div(Nat.sub(high, subtractor), 2n))
19
20# Chooses the midpoint of a half-open block-index interval.
21def midpoint(low: Nat, high: Nat) -> Nat:
22 midpoint.copies(QueuePolicy.nat.clone.pair(low), high)
23
24def move.order(is_less: Bool) -> Move:
25 match is_less:
26 case True{}: SearchLower{}
27 case False{}: SearchUpper{}
28
29# Compares the target key with one block's first-key separator.
30def move(target: Bytes.Bytes, separator: Bytes.Bytes) -> Move:
31 move.order(Cmp.is_lt(Keys.Bytes.cmp(target, separator)))
32
33def advance.lower(state: Search, mid: Nat) -> Search:
34 match state:
35 case Search{low, _, best}: Search{low, mid, best}
36
37def advance.upper.copies(state: Search, mids: Nat & Nat) -> Search:
38 match state:
39 case Search{_, high, _}:
40 match mids:
41 case (next_mid, candidate):
42 Search{Nat.add(next_mid, 1n), high, candidate}
43
44def advance.upper(state: Search, mid: Nat) -> Search:
45 advance.upper.copies(state, QueuePolicy.nat.clone.pair(mid))
46
47# Advances the interval and candidate after one separator comparison.
48def advance(state: Search, direction: Move, mid: Nat) -> Search:
49 match direction:
50 case SearchLower{}: advance.lower(state, mid)
51 case SearchUpper{}: advance.upper(state, mid)
52
53# Reports whether the half-open search interval remains nonempty.
54def active(state: Search) -> Bool:
55 match state:
56 case Search{low, high, _}: Nat.is_lt(low, high)
57
58# Returns the latest separator not greater than the target key.
59def selected_block(state: Search) -> Nat:
60 match state:
61 case Search{_, _, best}: best