summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorLuke Shumaker <lukeshu@lukeshu.com>2023-02-04 02:35:24 -0700
committerLuke Shumaker <lukeshu@lukeshu.com>2023-02-04 20:53:23 -0700
commita55b390d0c14aac4ac4d482ea147bd83841efb46 (patch)
treed544d7d7efff0525878031527bdd2306c19ee803
parentef60daef395b20b67042c011f5b2a1131049e275 (diff)
rebuildmappings: Use a binary-search when looking up the SumForAddr
-rw-r--r--lib/btrfsprogs/btrfsinspect/rebuildmappings/sumrunwithgaps.go24
1 files changed, 15 insertions, 9 deletions
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 {