src/MergeIter.bend
mylsm-lsm-store@0.4.0.0 · 81 lines · 0 definitions
1import Base
2import mylsm-lsm-store@0.4.0.0/src/Keys.bend as Keys
3import mylsm-lsm-store@0.4.0.0/src/MemTable.bend as MemTable
4import mylsm-lsm-store@0.4.0.0/src/Sstable.bend as Sstable
5import mylsm-lsm-store@0.4.0.0/src/SortedRun.bend as SortedRun
6
7# Merge iterator (Task 6): concat sources (memtable newest-first, then
8# SSTables newest-level-first) and canonicalize with balanced stable merge;
9# first-inserted wins ties = newest wins). The range+tombstone filter is
10# pump+fuel+leaf: String.cmp hands both strings back beside the verdict,
11# so the key survives the keep/drop decision with no clone primitive.
12# Order of defs is load-bearing (Bend 2: only backward references).
13
14# Scan put2 for the sorted merge iterator.
15def scan_put2(pair: (String & String) & Cmp, +val: String, acc: List<&2, MemTable.Entry>) -> List<&2, MemTable.Entry>:
16 match pair:
17 case ((k3, _), c):
18 match c:
19 case LT{}:
20 Con{MemTable.Entry{k3, Some{val}}, acc}
21 case EQ{}:
22 acc
23 case GT{}:
24 acc
25
26# Scan put for the sorted merge iterator.
27def scan_put(
28 pair: (String & String) & Cmp,
29 +hi: String,
30 +val: String,
31 acc: List<&2, MemTable.Entry>
32) -> List<&2, MemTable.Entry>:
33 match pair:
34 case ((k2, _), c):
35 match c:
36 case LT{}:
37 acc
38 case EQ{}:
39 scan_put2(String.cmp(k2, hi), val, acc)
40 case GT{}:
41 scan_put2(String.cmp(k2, hi), val, acc)
42
43# Scan go for the sorted merge iterator.
44def scan_go(
45 fuel: Nat,
46 +lo: String,
47 +hi: String,
48 acc: List<&2, MemTable.Entry>,
49 xs: List<&2, MemTable.Entry>
50) -> List<&2, MemTable.Entry>:
51 match fuel:
52 case 0n:
53 List.reverse(&2, MemTable.Entry, acc)
54 case 1n+f:
55 match xs:
56 case Nil{}:
57 List.reverse(&2, MemTable.Entry, acc)
58 case Con{MemTable.Entry{key, val}, t}:
59 match val:
60 case None{}:
61 scan_go(f, lo, hi, acc, t)
62 case Some{v}:
63 scan_go(f, lo, hi, scan_put(String.cmp(key, lo), hi, v, acc), t)
64
65# Newest-first concat: memtable entries, then each level's tables in order.
66def flatten(mem: List<&2, MemTable.Entry>, levels: List<&2, List<&2, MemTable.Entry>>) -> List<&2, MemTable.Entry>:
67 match levels:
68 case Nil{}:
69 mem
70 case Con{h, t}:
71 List.append(&2, MemTable.Entry, mem, List.concat(&2, MemTable.Entry, Con{h, t}))
72
73# Full merge: sorted, unique, newest version wins each key.
74def merge(mem: List<&2, MemTable.Entry>, levels: List<&2, List<&2, MemTable.Entry>>) -> List<&2, MemTable.Entry>:
75 SortedRun.sort_newest(flatten(mem, levels))
76
77# Range scan over a merged run: lo <= key < hi, tombstones dropped.
78def scan(+merged: List<&2, MemTable.Entry>, lo: String, hi: String) -> List<&2, MemTable.Entry>:
79 scan_go(List.length(&2, MemTable.Entry, merged), lo, hi, Nil{}, merged)
80
81# --- Closed-vector laws live in laws/MergeIter.bend (spec laws 4, 5, 10) ---