1 files changed, 167 insertions, 0 deletions
diff --git a/lib/btrfsprogs/btrfsinspect/rebuildmappings/sumrunwithgaps.go b/lib/btrfsprogs/btrfsinspect/rebuildmappings/sumrunwithgaps.go
new file mode 100644
index 0000000..f79e2be
--- /dev/null
+++ b/lib/btrfsprogs/btrfsinspect/rebuildmappings/sumrunwithgaps.go
@@ -0,0 +1,167 @@
+// Copyright (C) 2022-2023  Luke Shumaker <lukeshu@lukeshu.com>
+//
+// SPDX-License-Identifier: GPL-2.0-or-later
+
+package rebuildmappings
+
+import (
+	"context"
+	"fmt"
+	"io"
+	"math"
+
+	"git.lukeshu.com/go/lowmemjson"
+
+	"git.lukeshu.com/btrfs-progs-ng/lib/btrfs/btrfssum"
+	"git.lukeshu.com/btrfs-progs-ng/lib/btrfs/btrfsvol"
+	"git.lukeshu.com/btrfs-progs-ng/lib/slices"
+)
+
+type SumRunWithGaps[Addr btrfsvol.IntAddr[Addr]] struct {
+	// Store the start address and size, in order to facilitate
+	// leading and trailing gaps.
+	Addr Addr
+	Size btrfsvol.AddrDelta
+
+	Runs []btrfssum.SumRun[Addr]
+}
+
+var (
+	_ lowmemjson.Encodable = SumRunWithGaps[btrfsvol.LogicalAddr]{}
+	_ lowmemjson.Decodable = (*SumRunWithGaps[btrfsvol.LogicalAddr])(nil)
+)
+
+// PatLen implements kmpPattern[int, ShortSum].
+func (sg SumRunWithGaps[Addr]) PatLen() int {
+	return int(sg.Size / btrfssum.BlockSize)
+}
+
+func (sg SumRunWithGaps[Addr]) PctFull() float64 {
+	total := sg.PatLen()
+	var full int
+	for _, run := range sg.Runs {
+		full += run.SeqLen()
+	}
+	return float64(full) / float64(total)
+}
+
+func (sg SumRunWithGaps[Addr]) RunForAddr(addr Addr) (btrfssum.SumRun[Addr], Addr, bool) {
+	for _, run := range sg.Runs {
+		if run.Addr > addr {
+			return btrfssum.SumRun[Addr]{}, run.Addr, false
+		}
+		if run.Addr.Add(run.Size()) <= addr {
+			continue
+		}
+		return run, 0, true
+	}
+	return btrfssum.SumRun[Addr]{}, math.MaxInt64, false
+}
+
+func (sg SumRunWithGaps[Addr]) SumForAddr(addr Addr) (btrfssum.ShortSum, bool) {
+	if addr < sg.Addr || addr >= sg.Addr.Add(sg.Size) {
+		return "", false
+	}
+	runIdx, ok := slices.Search(sg.Runs, func(run btrfssum.SumRun[Addr]) int {
+		switch {
+		case addr < run.Addr:
+			return -1
+		case addr >= run.Addr.Add(run.Size()):
+			return 1
+		default:
+			return 0
+		}
+	})
+	if !ok {
+		return "", false
+	}
+	run := sg.Runs[runIdx]
+	off := int((addr-run.Addr)/btrfssum.BlockSize) * run.ChecksumSize
+	return run.Sums[off : off+run.ChecksumSize], true
+}
+
+func (sg SumRunWithGaps[Addr]) Walk(ctx context.Context, fn func(Addr, btrfssum.ShortSum) error) error {
+	for _, run := range sg.Runs {
+		if err := run.Walk(ctx, fn); err != nil {
+			return err
+		}
+	}
+	return nil
+}
+
+// PatGet implements kmpPattern[int, ShortSum].
+func (sg SumRunWithGaps[Addr]) PatGet(sumIdx int) (btrfssum.ShortSum, bool) {
+	addr := sg.Addr.Add(btrfsvol.AddrDelta(sumIdx) * btrfssum.BlockSize)
+	return sg.SumForAddr(addr)
+}
+
+func (sg SumRunWithGaps[Addr]) EncodeJSON(w io.Writer) error {
+	if _, err := fmt.Fprintf(w, `{"Addr":%d,"Size":%d,"Runs":[`, sg.Addr, sg.Size); err != nil {
+		return err
+	}
+	cur := sg.Addr
+	for i, run := range sg.Runs {
+		if i > 0 {
+			if _, err := w.Write([]byte{','}); err != nil {
+				return err
+			}
+		}
+		switch {
+		case run.Addr < cur:
+			return fmt.Errorf("invalid %T: addr went backwards: %v < %v", sg, run.Addr, cur)
+		case run.Addr > cur:
+			if _, err := fmt.Fprintf(w, `{"Gap":%d},`, run.Addr.Sub(cur)); err != nil {
+				return err
+			}
+			fallthrough
+		default:
+			if err := lowmemjson.NewEncoder(w).Encode(run); err != nil {
+				return err
+			}
+			cur = run.Addr.Add(run.Size())
+		}
+	}
+	end := sg.Addr.Add(sg.Size)
+	switch {
+	case end < cur:
+		return fmt.Errorf("invalid %T: addr went backwards: %v < %v", sg, end, cur)
+	case end > cur:
+		if _, err := fmt.Fprintf(w, `,{"Gap":%d}`, end.Sub(cur)); err != nil {
+			return err
+		}
+	}
+	if _, err := w.Write([]byte("]}")); err != nil {
+		return err
+	}
+	return nil
+}
+
+func (sg *SumRunWithGaps[Addr]) DecodeJSON(r io.RuneScanner) error {
+	*sg = SumRunWithGaps[Addr]{}
+	var name string
+	return lowmemjson.DecodeObject(r,
+		func(r io.RuneScanner) error {
+			return lowmemjson.NewDecoder(r).Decode(&name)
+		},
+		func(r io.RuneScanner) error {
+			switch name {
+			case "Addr":
+				return lowmemjson.NewDecoder(r).Decode(&sg.Addr)
+			case "Size":
+				return lowmemjson.NewDecoder(r).Decode(&sg.Size)
+			case "Runs":
+				return lowmemjson.DecodeArray(r, func(r io.RuneScanner) error {
+					var run btrfssum.SumRun[Addr]
+					if err := lowmemjson.NewDecoder(r).Decode(&run); err != nil {
+						return err
+					}
+					if run.ChecksumSize > 0 {
+						sg.Runs = append(sg.Runs, run)
+					}
+					return nil
+				})
+			default:
+				return fmt.Errorf("unknown key %q", name)
+			}
+		})
+}