From a55b390d0c14aac4ac4d482ea147bd83841efb46 Mon Sep 17 00:00:00 2001
From: Luke Shumaker <lukeshu@lukeshu.com>
Date: Sat, 4 Feb 2023 02:35:24 -0700
Subject: rebuildmappings: Use a binary-search when looking up the SumForAddr

---
 .../btrfsinspect/rebuildmappings/sumrunwithgaps.go | 24 ++++++++++++++--------
 1 file changed, 15 insertions(+), 9 deletions(-)

(limited to 'lib/btrfsprogs/btrfsinspect/rebuildmappings/sumrunwithgaps.go')

diff --git a/lib/btrfsprogs/btrfsinspect/rebuildmappings/sumrunwithgaps.go b/lib/btrfsprogs/btrfsinspect/rebuildmappings/sumrunwithgaps.go
index e574540..f79e2be 100644
--- a/lib/btrfsprogs/btrfsinspect/rebuildmappings/sumrunwithgaps.go
+++ b/lib/btrfsprogs/btrfsinspect/rebuildmappings/sumrunwithgaps.go
@@ -14,6 +14,7 @@ import (
 
 	"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 {
@@ -61,17 +62,22 @@ func (sg SumRunWithGaps[Addr]) SumForAddr(addr Addr) (btrfssum.ShortSum, bool) {
 	if addr < sg.Addr || addr >= sg.Addr.Add(sg.Size) {
 		return "", false
 	}
-	for _, run := range sg.Runs {
-		if run.Addr > addr {
-			return "", false
-		}
-		if run.Addr.Add(run.Size()) <= addr {
-			continue
+	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
 		}
-		off := int((addr-run.Addr)/btrfssum.BlockSize) * run.ChecksumSize
-		return run.Sums[off : off+run.ChecksumSize], true
+	})
+	if !ok {
+		return "", false
 	}
-	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 {
-- 
cgit v1.2.3-2-g168b