diff options
| author | Luke Shumaker <lukeshu@lukeshu.com> | 2023-02-28 14:05:27 -0700 |
|---|---|---|
| committer | Luke Shumaker <lukeshu@lukeshu.com> | 2023-03-14 19:45:07 -0600 |
| commit | 8c8c6c27552f8554ba014c34d684cb90538ef65b (patch) | |
| tree | f3a53ed194e29b516b52770e4949a1e508fad6a7 /lib/btrfsprogs/btrfsinspect/rebuildmappings/kmp_test.go | |
| parent | 34bf167ef33c57b4d6767273f1d265971a4693b9 (diff) | |
Move files around [ci-skip]
Diffstat (limited to 'lib/btrfsprogs/btrfsinspect/rebuildmappings/kmp_test.go')
| -rw-r--r-- | lib/btrfsprogs/btrfsinspect/rebuildmappings/kmp_test.go | 126 |
1 files changed, 0 insertions, 126 deletions
diff --git a/lib/btrfsprogs/btrfsinspect/rebuildmappings/kmp_test.go b/lib/btrfsprogs/btrfsinspect/rebuildmappings/kmp_test.go deleted file mode 100644 index acec9b8..0000000 --- a/lib/btrfsprogs/btrfsinspect/rebuildmappings/kmp_test.go +++ /dev/null @@ -1,126 +0,0 @@ -// Copyright (C) 2022-2023 Luke Shumaker <lukeshu@lukeshu.com> -// -// SPDX-License-Identifier: GPL-2.0-or-later - -package rebuildmappings - -import ( - "bytes" - "testing" - - "github.com/stretchr/testify/assert" - "github.com/stretchr/testify/require" - - "git.lukeshu.com/btrfs-progs-ng/lib/diskio" -) - -type bytePattern[K ~int64 | ~int] []byte - -var _ kmpPattern[int, byte] = bytePattern[int]{} - -// PatLen implements kmpPattern. -func (s bytePattern[K]) PatLen() K { - return K(len(s)) -} - -// PatGet implements kmpPattern. -func (s bytePattern[K]) PatGet(i K) (byte, bool) { - chr := s[int(i)] - if chr == '.' { - return 0, false - } - return chr, true -} - -func TestBuildKMPTable(t *testing.T) { - t.Parallel() - substr := bytePattern[int64]([]byte("ababaa")) - table := buildKMPTable[int64, byte](substr) - require.Equal(t, - []int64{0, 0, 1, 2, 3, 1}, - table) - for j, val := range table { - matchLen := j + 1 - assert.Equalf(t, substr[:val], substr[matchLen-int(val):matchLen], - "for table[%d]=%d", j, val) - } -} - -func FuzzBuildKMPTable(f *testing.F) { - f.Add([]byte("ababaa")) - f.Fuzz(func(t *testing.T, substr []byte) { - table := buildKMPTable[int64, byte](bytePattern[int64](substr)) - require.Equal(t, len(substr), len(table), "length") - for j, val := range table { - matchLen := j + 1 - assert.Equalf(t, substr[:val], substr[matchLen-int(val):matchLen], - "for table[%d]=%d", j, val) - } - }) -} - -func NaiveIndexAll(str, substr []byte) []int64 { - var matches []int64 - for i := range str { - if bytes.HasPrefix(str[i:], substr) { - matches = append(matches, int64(i)) - } - } - return matches -} - -func FuzzIndexAll(f *testing.F) { - f.Fuzz(func(t *testing.T, str, substr []byte) { - if len(substr) == 0 { - t.Skip() - } - t.Logf("str =%q", str) - t.Logf("substr=%q", substr) - exp := NaiveIndexAll(str, substr) - act := indexAll[int64, byte]( - diskio.SliceSequence[int64, byte](str), - bytePattern[int64](substr)) - assert.Equal(t, exp, act) - }) -} - -func TestKMPWildcard(t *testing.T) { - t.Parallel() - type testcase struct { - InStr string - InSubstr string - ExpMatches []int64 - } - testcases := map[string]testcase{ - "trivial-bar": { - InStr: "foo_bar", - InSubstr: "foo.ba.", - ExpMatches: []int64{0}, - }, - "trival-baz": { - InStr: "foo-baz", - InSubstr: "foo.ba.", - ExpMatches: []int64{0}, - }, - "suffix": { - InStr: "foobarbaz", - InSubstr: "...baz", - ExpMatches: []int64{3}, - }, - "overlap": { - InStr: "foobarbar", - InSubstr: "...bar", - ExpMatches: []int64{0, 3}, - }, - } - for tcName, tc := range testcases { - tc := tc - t.Run(tcName, func(t *testing.T) { - t.Parallel() - matches := indexAll[int64, byte]( - diskio.StringSequence[int64](tc.InStr), - bytePattern[int64](tc.InSubstr)) - assert.Equal(t, tc.ExpMatches, matches) - }) - } -} |