src/MergeIter.bend

mylsm-lsm-store@0.3.2.0 · 67 lines · 6 definitions

1import Base
2import mylsm-lsm-store@0.3.2.0/src/Keys.bend as Keys
3import mylsm-lsm-store@0.3.2.0/src/MemTable.bend as MemTable
4import mylsm-lsm-store@0.3.2.0/src/Sstable.bend as Sstable
5import mylsm-lsm-store@0.3.2.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
14def scan_put2(pair: (String & String) & Cmp, +val: String, acc: List<&2, MemTable.Entry>) -> List<&2, MemTable.Entry>:
15  match pair:
16    case ((k3, _), c):
17      match c:
18        case LT{}:
19          Con{MemTable.Entry{k3, Some{val}}, acc}
20        case EQ{}:
21          acc
22        case GT{}:
23          acc
24
25def scan_put(pair: (String & String) & Cmp, +hi: String, +val: String, acc: List<&2, MemTable.Entry>) -> List<&2, MemTable.Entry>:
26  match pair:
27    case ((k2, _), c):
28      match c:
29        case LT{}:
30          acc
31        case EQ{}:
32          scan_put2(String.cmp(k2, hi), val, acc)
33        case GT{}:
34          scan_put2(String.cmp(k2, hi), val, acc)
35
36def scan_go(fuel: Nat, +lo: String, +hi: String, acc: List<&2, MemTable.Entry>, xs: List<&2, MemTable.Entry>) -> List<&2, MemTable.Entry>:
37  match fuel:
38    case 0n:
39      List.reverse(&2, MemTable.Entry, acc)
40    case 1n+f:
41      match xs:
42        case Nil{}:
43          List.reverse(&2, MemTable.Entry, acc)
44        case Con{MemTable.Entry{key, val}, t}:
45          match val:
46            case None{}:
47              scan_go(f, lo, hi, acc, t)
48            case Some{v}:
49              scan_go(f, lo, hi, scan_put(String.cmp(key, lo), hi, v, acc), t)
50
51# Newest-first concat: memtable entries, then each level's tables in order.
52def flatten(mem: List<&2, MemTable.Entry>, levels: List<&2, List<&2, MemTable.Entry>>) -> List<&2, MemTable.Entry>:
53  match levels:
54    case Nil{}:
55      mem
56    case Con{h, t}:
57      List.append(&2, MemTable.Entry, mem, List.concat(&2, MemTable.Entry, Con{h, t}))
58
59# Full merge: sorted, unique, newest version wins each key.
60def merge(mem: List<&2, MemTable.Entry>, levels: List<&2, List<&2, MemTable.Entry>>) -> List<&2, MemTable.Entry>:
61  SortedRun.sort_newest(flatten(mem, levels))
62
63# Range scan over a merged run: lo <= key < hi, tombstones dropped.
64def scan(+merged: List<&2, MemTable.Entry>, lo: String, hi: String) -> List<&2, MemTable.Entry>:
65  scan_go(List.length(&2, MemTable.Entry, merged), lo, hi, Nil{}, merged)
66
67# --- Closed-vector laws live in laws/MergeIter.bend (spec laws 4, 5, 10) ---