src/MergeIter.bend source

src/MergeIter.bend on the hub · documented module

import Baseimport ./Keys.bend as Keysimport ./MemTable.bend as MemTableimport ./Sstable.bend as Sstableimport ./SortedRun.bend as SortedRun# Merge iterator (Task 6): concat sources (memtable newest-first, then# SSTables newest-level-first) and canonicalize with balanced stable merge;# first-inserted wins ties = newest wins). The range+tombstone filter is# pump+fuel+leaf: String.cmp hands both strings back beside the verdict,# so the key survives the keep/drop decision with no clone primitive.# Order of defs is load-bearing (Bend 2: only backward references).# Scan put2 for the sorted merge iterator.def scan_put2(pair: (String & String) & Cmp, +val: String, acc: List<&2, MemTable.Entry>) -> List<&2, MemTable.Entry>:  match pair:    case ((k3, _), c):      match c:        case LT{}:          Con{MemTable.Entry{k3, Some{val}}, acc}        case EQ{}:          acc        case GT{}:          acc# Scan put for the sorted merge iterator.def scan_put(  pair: (String & String) & Cmp,  +hi: String,  +val: String,  acc: List<&2, MemTable.Entry>) -> List<&2, MemTable.Entry>:  match pair:    case ((k2, _), c):      match c:        case LT{}:          acc        case EQ{}:          scan_put2(String.cmp(k2, hi), val, acc)        case GT{}:          scan_put2(String.cmp(k2, hi), val, acc)# Scan go for the sorted merge iterator.def scan_go(  fuel: Nat,  +lo: String,  +hi: String,  acc: List<&2, MemTable.Entry>,  xs: List<&2, MemTable.Entry>) -> List<&2, MemTable.Entry>:  match fuel:    case 0n:      List.reverse(&2, MemTable.Entry, acc)    case 1n+f:      match xs:        case Nil{}:          List.reverse(&2, MemTable.Entry, acc)        case Con{MemTable.Entry{key, val}, t}:          match val:            case None{}:              scan_go(f, lo, hi, acc, t)            case Some{v}:              scan_go(f, lo, hi, scan_put(String.cmp(key, lo), hi, v, acc), t)# Newest-first concat: memtable entries, then each level's tables in order.def flatten(mem: List<&2, MemTable.Entry>, levels: List<&2, List<&2, MemTable.Entry>>) -> List<&2, MemTable.Entry>:  match levels:    case Nil{}:      mem    case Con{h, t}:      List.append(&2, MemTable.Entry, mem, List.concat(&2, MemTable.Entry, Con{h, t}))# Full merge: sorted, unique, newest version wins each key.def merge(mem: List<&2, MemTable.Entry>, levels: List<&2, List<&2, MemTable.Entry>>) -> List<&2, MemTable.Entry>:  SortedRun.sort_newest(flatten(mem, levels))# Range scan over a merged run: lo <= key < hi, tombstones dropped.def scan(+merged: List<&2, MemTable.Entry>, lo: String, hi: String) -> List<&2, MemTable.Entry>:  scan_go(List.length(&2, MemTable.Entry, merged), lo, hi, Nil{}, merged)# --- Closed-vector laws live in laws/MergeIter.bend (spec laws 4, 5, 10) ---