diff options
author | Luke Shumaker <lukeshu@lukeshu.com> | 2023-02-03 19:13:22 -0700 |
---|---|---|
committer | Luke Shumaker <lukeshu@lukeshu.com> | 2023-02-04 20:53:13 -0700 |
commit | 77f3c0d7cd21274d00984b72dfce05394d11bdd0 (patch) | |
tree | 1b48655cd25378c6c68a1cc2475eb8d9dcbc1ca7 /lib | |
parent | d36dec9dc7019d67e0acf12c52607110cc0edc62 (diff) |
Move KMP IndexAll from diskio to rebuildmappings
Diffstat (limited to 'lib')
9 files changed, 19 insertions, 17 deletions
diff --git a/lib/diskio/kmp.go b/lib/btrfsprogs/btrfsinspect/rebuildmappings/kmp.go index 6949aa4..eeaab0c 100644 --- a/lib/diskio/kmp.go +++ b/lib/btrfsprogs/btrfsinspect/rebuildmappings/kmp.go @@ -2,16 +2,18 @@ // // SPDX-License-Identifier: GPL-2.0-or-later -package diskio +package rebuildmappings import ( "errors" "io" + + "git.lukeshu.com/btrfs-progs-ng/lib/diskio" ) var ErrWildcard = errors.New("wildcard") -func kmpEq2[K ~int64, V comparable](aS Sequence[K, V], aI K, bS Sequence[K, V], bI K) bool { +func kmpEq2[K ~int64, V comparable](aS diskio.Sequence[K, V], aI K, bS diskio.Sequence[K, V], bI K) bool { aV, aErr := aS.Get(aI) bV, bErr := bS.Get(bI) if aErr != nil { @@ -38,7 +40,7 @@ func kmpEq2[K ~int64, V comparable](aS Sequence[K, V], aI K, bS Sequence[K, V], return aV == bV } -func kmpEq1[K ~int64, V comparable](aV V, bS Sequence[K, V], bI K) bool { +func kmpEq1[K ~int64, V comparable](aV V, bS diskio.Sequence[K, V], bI K) bool { bV, bErr := bS.Get(bI) if bErr != nil { //nolint:errorlint // The == is just a fast-path; we still fall back to errors.Is. @@ -53,7 +55,7 @@ func kmpEq1[K ~int64, V comparable](aV V, bS Sequence[K, V], bI K) bool { // buildKMPTable takes the string 'substr', and returns a table such // that 'table[matchLen-1]' is the largest value 'val' for which 'val < matchLen' and // 'substr[:val] == substr[matchLen-val:matchLen]'. -func buildKMPTable[K ~int64, V comparable](substr Sequence[K, V]) ([]K, error) { +func buildKMPTable[K ~int64, V comparable](substr diskio.Sequence[K, V]) ([]K, error) { var substrLen K for { //nolint:errorlint // The == is just a fast-path; we still fall back to errors.Is. @@ -102,14 +104,14 @@ func buildKMPTable[K ~int64, V comparable](substr Sequence[K, V]) ([]K, error) { // ErrWildcard for a position. // // Uses the Knuth-Morris-Pratt algorithm. -func IndexAll[K ~int64, V comparable](str, substr Sequence[K, V]) ([]K, error) { +func IndexAll[K ~int64, V comparable](str, substr diskio.Sequence[K, V]) ([]K, error) { table, err := buildKMPTable(substr) if err != nil { return nil, err } substrLen := K(len(table)) if substrLen == 0 { - panic(errors.New("diskio.IndexAll: empty substring")) + panic(errors.New("rebuildmappings.IndexAll: empty substring")) } var matches []K diff --git a/lib/diskio/kmp_test.go b/lib/btrfsprogs/btrfsinspect/rebuildmappings/kmp_test.go index 4d4b3be..910452a 100644 --- a/lib/diskio/kmp_test.go +++ b/lib/btrfsprogs/btrfsinspect/rebuildmappings/kmp_test.go @@ -2,7 +2,7 @@ // // SPDX-License-Identifier: GPL-2.0-or-later -package diskio +package rebuildmappings import ( "bytes" @@ -11,11 +11,13 @@ import ( "github.com/stretchr/testify/assert" "github.com/stretchr/testify/require" + + "git.lukeshu.com/btrfs-progs-ng/lib/diskio" ) func TestBuildKMPTable(t *testing.T) { t.Parallel() - substr := SliceSequence[int64, byte]([]byte("ababaa")) + substr := diskio.SliceSequence[int64, byte]([]byte("ababaa")) table, err := buildKMPTable[int64, byte](substr) require.NoError(t, err) require.Equal(t, @@ -31,7 +33,7 @@ func TestBuildKMPTable(t *testing.T) { func FuzzBuildKMPTable(f *testing.F) { f.Add([]byte("ababaa")) f.Fuzz(func(t *testing.T, substr []byte) { - table, err := buildKMPTable[int64, byte](SliceSequence[int64, byte](substr)) + table, err := buildKMPTable[int64, byte](diskio.SliceSequence[int64, byte](substr)) require.NoError(t, err) require.Equal(t, len(substr), len(table), "length") for j, val := range table { @@ -61,8 +63,8 @@ func FuzzIndexAll(f *testing.F) { t.Logf("substr=%q", substr) exp := NaiveIndexAll(str, substr) act, err := IndexAll[int64, byte]( - &ByteReaderSequence[int64]{R: bytes.NewReader(str)}, - SliceSequence[int64, byte](substr)) + &diskio.ByteReaderSequence[int64]{R: bytes.NewReader(str)}, + diskio.SliceSequence[int64, byte](substr)) assert.NoError(t, err) assert.Equal(t, exp, act) }) @@ -115,7 +117,7 @@ func TestKMPWildcard(t *testing.T) { t.Run(tcName, func(t *testing.T) { t.Parallel() matches, err := IndexAll[int64, byte]( - StringSequence[int64](tc.InStr), + diskio.StringSequence[int64](tc.InStr), RESeq(tc.InSubstr)) assert.NoError(t, err) assert.Equal(t, tc.ExpMatches, matches) diff --git a/lib/btrfsprogs/btrfsinspect/rebuildmappings/matchsums.go b/lib/btrfsprogs/btrfsinspect/rebuildmappings/matchsums.go index c38314a..eda37bd 100644 --- a/lib/btrfsprogs/btrfsinspect/rebuildmappings/matchsums.go +++ b/lib/btrfsprogs/btrfsinspect/rebuildmappings/matchsums.go @@ -14,7 +14,6 @@ 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/containers" - "git.lukeshu.com/btrfs-progs-ng/lib/diskio" "git.lukeshu.com/btrfs-progs-ng/lib/maps" ) @@ -37,7 +36,7 @@ func matchBlockGroupSums(ctx context.Context, var matches []btrfsvol.QualifiedPhysicalAddr if err := WalkUnmappedPhysicalRegions(ctx, physicalSums, regions, func(devID btrfsvol.DeviceID, region btrfssum.SumRun[btrfsvol.PhysicalAddr]) error { - rawMatches, err := diskio.IndexAll[int64, btrfssum.ShortSum](region, bgRun) + rawMatches, err := IndexAll[int64, btrfssum.ShortSum](region, bgRun) if err != nil { return err } diff --git a/lib/btrfsprogs/btrfsinspect/rebuildmappings/sumrunwithgaps.go b/lib/btrfsprogs/btrfsinspect/rebuildmappings/sumrunwithgaps.go index 8c1f3ed..d1064d8 100644 --- a/lib/btrfsprogs/btrfsinspect/rebuildmappings/sumrunwithgaps.go +++ b/lib/btrfsprogs/btrfsinspect/rebuildmappings/sumrunwithgaps.go @@ -14,7 +14,6 @@ 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/diskio" ) type SumRunWithGaps[Addr btrfsvol.IntAddr[Addr]] struct { @@ -63,7 +62,7 @@ func (sg SumRunWithGaps[Addr]) SumForAddr(addr Addr) (btrfssum.ShortSum, error) } for _, run := range sg.Runs { if run.Addr > addr { - return "", diskio.ErrWildcard + return "", ErrWildcard } if run.Addr.Add(run.Size()) <= addr { continue @@ -71,7 +70,7 @@ func (sg SumRunWithGaps[Addr]) SumForAddr(addr Addr) (btrfssum.ShortSum, error) off := int((addr-run.Addr)/btrfssum.BlockSize) * run.ChecksumSize return run.Sums[off : off+run.ChecksumSize], nil } - return "", diskio.ErrWildcard + return "", ErrWildcard } func (sg SumRunWithGaps[Addr]) Walk(ctx context.Context, fn func(Addr, btrfssum.ShortSum) error) error { diff --git a/lib/diskio/testdata/fuzz/FuzzIndexAll/593a5dd328ee86bac6820e3f98383aebadd2af3a22aa248546a228b08451c30d b/lib/btrfsprogs/btrfsinspect/rebuildmappings/testdata/fuzz/FuzzIndexAll/593a5dd328ee86bac6820e3f98383aebadd2af3a22aa248546a228b08451c30d index 9d14adf..9d14adf 100644 --- a/lib/diskio/testdata/fuzz/FuzzIndexAll/593a5dd328ee86bac6820e3f98383aebadd2af3a22aa248546a228b08451c30d +++ b/lib/btrfsprogs/btrfsinspect/rebuildmappings/testdata/fuzz/FuzzIndexAll/593a5dd328ee86bac6820e3f98383aebadd2af3a22aa248546a228b08451c30d diff --git a/lib/diskio/testdata/fuzz/FuzzIndexAll/6bd9babbebf7eb78814e1f3425bfa6ccd6bfd42824a26e8cbd63b5117934e600 b/lib/btrfsprogs/btrfsinspect/rebuildmappings/testdata/fuzz/FuzzIndexAll/6bd9babbebf7eb78814e1f3425bfa6ccd6bfd42824a26e8cbd63b5117934e600 index 269f061..269f061 100644 --- a/lib/diskio/testdata/fuzz/FuzzIndexAll/6bd9babbebf7eb78814e1f3425bfa6ccd6bfd42824a26e8cbd63b5117934e600 +++ b/lib/btrfsprogs/btrfsinspect/rebuildmappings/testdata/fuzz/FuzzIndexAll/6bd9babbebf7eb78814e1f3425bfa6ccd6bfd42824a26e8cbd63b5117934e600 diff --git a/lib/diskio/testdata/fuzz/FuzzIndexAll/84ed65595ad05a58e293dbf423c1a816b697e2763a29d7c37aa476d6eef6fd60 b/lib/btrfsprogs/btrfsinspect/rebuildmappings/testdata/fuzz/FuzzIndexAll/84ed65595ad05a58e293dbf423c1a816b697e2763a29d7c37aa476d6eef6fd60 index b8f1562..b8f1562 100644 --- a/lib/diskio/testdata/fuzz/FuzzIndexAll/84ed65595ad05a58e293dbf423c1a816b697e2763a29d7c37aa476d6eef6fd60 +++ b/lib/btrfsprogs/btrfsinspect/rebuildmappings/testdata/fuzz/FuzzIndexAll/84ed65595ad05a58e293dbf423c1a816b697e2763a29d7c37aa476d6eef6fd60 diff --git a/lib/diskio/testdata/fuzz/FuzzIndexAll/9be40f71bc49b1b5c3b8e08d58d0f69cc22aefb12fd9b5931e49ff0e41953738 b/lib/btrfsprogs/btrfsinspect/rebuildmappings/testdata/fuzz/FuzzIndexAll/9be40f71bc49b1b5c3b8e08d58d0f69cc22aefb12fd9b5931e49ff0e41953738 index be67506..be67506 100644 --- a/lib/diskio/testdata/fuzz/FuzzIndexAll/9be40f71bc49b1b5c3b8e08d58d0f69cc22aefb12fd9b5931e49ff0e41953738 +++ b/lib/btrfsprogs/btrfsinspect/rebuildmappings/testdata/fuzz/FuzzIndexAll/9be40f71bc49b1b5c3b8e08d58d0f69cc22aefb12fd9b5931e49ff0e41953738 diff --git a/lib/diskio/testdata/fuzz/FuzzIndexAll/e43317ec61b0da9627d7b2fc0237d369082a6bf5dfe39e05c113b42ff6218d5d b/lib/btrfsprogs/btrfsinspect/rebuildmappings/testdata/fuzz/FuzzIndexAll/e43317ec61b0da9627d7b2fc0237d369082a6bf5dfe39e05c113b42ff6218d5d index c3bfa37..c3bfa37 100644 --- a/lib/diskio/testdata/fuzz/FuzzIndexAll/e43317ec61b0da9627d7b2fc0237d369082a6bf5dfe39e05c113b42ff6218d5d +++ b/lib/btrfsprogs/btrfsinspect/rebuildmappings/testdata/fuzz/FuzzIndexAll/e43317ec61b0da9627d7b2fc0237d369082a6bf5dfe39e05c113b42ff6218d5d |