diff options
author | Luke Shumaker <lukeshu@lukeshu.com> | 2022-07-13 21:31:23 -0600 |
---|---|---|
committer | Luke Shumaker <lukeshu@lukeshu.com> | 2022-07-13 21:39:43 -0600 |
commit | 436e1681c9fcda246c6d84526fc79c87adc7b28d (patch) | |
tree | 75e52fb976c1666e50b32ab61043704f127a91f7 | |
parent | 72a458520fccafe4df8c02c811cb6f64a310616e (diff) |
Move lib/kmp to lib/diskio
-rw-r--r-- | lib/diskio/kmp.go (renamed from lib/kmp/kmp.go) | 12 | ||||
-rw-r--r-- | lib/diskio/kmp_test.go (renamed from lib/kmp/kmp_test.go) | 10 | ||||
-rw-r--r-- | lib/diskio/testdata/fuzz/FuzzFindAll/593a5dd328ee86bac6820e3f98383aebadd2af3a22aa248546a228b08451c30d (renamed from lib/kmp/testdata/fuzz/FuzzFindAll/593a5dd328ee86bac6820e3f98383aebadd2af3a22aa248546a228b08451c30d) | 0 | ||||
-rw-r--r-- | lib/diskio/testdata/fuzz/FuzzFindAll/6bd9babbebf7eb78814e1f3425bfa6ccd6bfd42824a26e8cbd63b5117934e600 (renamed from lib/kmp/testdata/fuzz/FuzzFindAll/6bd9babbebf7eb78814e1f3425bfa6ccd6bfd42824a26e8cbd63b5117934e600) | 0 | ||||
-rw-r--r-- | lib/diskio/testdata/fuzz/FuzzFindAll/84ed65595ad05a58e293dbf423c1a816b697e2763a29d7c37aa476d6eef6fd60 (renamed from lib/kmp/testdata/fuzz/FuzzFindAll/84ed65595ad05a58e293dbf423c1a816b697e2763a29d7c37aa476d6eef6fd60) | 0 | ||||
-rw-r--r-- | lib/diskio/testdata/fuzz/FuzzFindAll/9be40f71bc49b1b5c3b8e08d58d0f69cc22aefb12fd9b5931e49ff0e41953738 (renamed from lib/kmp/testdata/fuzz/FuzzFindAll/9be40f71bc49b1b5c3b8e08d58d0f69cc22aefb12fd9b5931e49ff0e41953738) | 0 | ||||
-rw-r--r-- | lib/diskio/testdata/fuzz/FuzzFindAll/e43317ec61b0da9627d7b2fc0237d369082a6bf5dfe39e05c113b42ff6218d5d (renamed from lib/kmp/testdata/fuzz/FuzzFindAll/e43317ec61b0da9627d7b2fc0237d369082a6bf5dfe39e05c113b42ff6218d5d) | 0 |
7 files changed, 12 insertions, 10 deletions
diff --git a/lib/kmp/kmp.go b/lib/diskio/kmp.go index 66b5516..4c0f531 100644 --- a/lib/kmp/kmp.go +++ b/lib/diskio/kmp.go @@ -2,17 +2,17 @@ // // SPDX-License-Identifier: GPL-2.0-or-later -package kmp +package diskio import ( "errors" "io" ) -// buildTable takes the string 'substr', and returns a table such +// 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 buildTable(substr []byte) []int { +func buildKMPTable(substr []byte) []int { table := make([]int, len(substr)) for j := range table { if j == 0 { @@ -38,11 +38,13 @@ func buildTable(substr []byte) []int { // occurances of 'substr' in the 'r' stream. // // Will panic if len(substr)==0. +// +// Uses the Knuth-Morris-Pratt algorithm. func FindAll(r io.ByteReader, substr []byte) ([]int64, error) { if len(substr) == 0 { - panic(errors.New("kmp.FindAll: empty substring")) + panic(errors.New("diskio.FindAll: empty substring")) } - table := buildTable(substr) + table := buildKMPTable(substr) var matches []int64 var curMatchBeg int64 diff --git a/lib/kmp/kmp_test.go b/lib/diskio/kmp_test.go index 6a11b50..6c6ef78 100644 --- a/lib/kmp/kmp_test.go +++ b/lib/diskio/kmp_test.go @@ -2,7 +2,7 @@ // // SPDX-License-Identifier: GPL-2.0-or-later -package kmp +package diskio import ( "bytes" @@ -11,9 +11,9 @@ import ( "github.com/stretchr/testify/assert" ) -func TestBuildTable(t *testing.T) { +func TestBuildKMPTable(t *testing.T) { substr := []byte("ababaa") - table := buildTable(substr) + table := buildKMPTable(substr) assert.Equal(t, []int{0, 0, 1, 2, 3, 1}, table) @@ -24,10 +24,10 @@ func TestBuildTable(t *testing.T) { } } -func FuzzBuildTable(f *testing.F) { +func FuzzBuildKMPTable(f *testing.F) { f.Add([]byte("ababaa")) f.Fuzz(func(t *testing.T, substr []byte) { - table := buildTable(substr) + table := buildKMPTable(substr) assert.Equal(t, len(substr), len(table), "length") for j, val := range table { matchLen := j + 1 diff --git a/lib/kmp/testdata/fuzz/FuzzFindAll/593a5dd328ee86bac6820e3f98383aebadd2af3a22aa248546a228b08451c30d b/lib/diskio/testdata/fuzz/FuzzFindAll/593a5dd328ee86bac6820e3f98383aebadd2af3a22aa248546a228b08451c30d index 9d14adf..9d14adf 100644 --- a/lib/kmp/testdata/fuzz/FuzzFindAll/593a5dd328ee86bac6820e3f98383aebadd2af3a22aa248546a228b08451c30d +++ b/lib/diskio/testdata/fuzz/FuzzFindAll/593a5dd328ee86bac6820e3f98383aebadd2af3a22aa248546a228b08451c30d diff --git a/lib/kmp/testdata/fuzz/FuzzFindAll/6bd9babbebf7eb78814e1f3425bfa6ccd6bfd42824a26e8cbd63b5117934e600 b/lib/diskio/testdata/fuzz/FuzzFindAll/6bd9babbebf7eb78814e1f3425bfa6ccd6bfd42824a26e8cbd63b5117934e600 index 269f061..269f061 100644 --- a/lib/kmp/testdata/fuzz/FuzzFindAll/6bd9babbebf7eb78814e1f3425bfa6ccd6bfd42824a26e8cbd63b5117934e600 +++ b/lib/diskio/testdata/fuzz/FuzzFindAll/6bd9babbebf7eb78814e1f3425bfa6ccd6bfd42824a26e8cbd63b5117934e600 diff --git a/lib/kmp/testdata/fuzz/FuzzFindAll/84ed65595ad05a58e293dbf423c1a816b697e2763a29d7c37aa476d6eef6fd60 b/lib/diskio/testdata/fuzz/FuzzFindAll/84ed65595ad05a58e293dbf423c1a816b697e2763a29d7c37aa476d6eef6fd60 index b8f1562..b8f1562 100644 --- a/lib/kmp/testdata/fuzz/FuzzFindAll/84ed65595ad05a58e293dbf423c1a816b697e2763a29d7c37aa476d6eef6fd60 +++ b/lib/diskio/testdata/fuzz/FuzzFindAll/84ed65595ad05a58e293dbf423c1a816b697e2763a29d7c37aa476d6eef6fd60 diff --git a/lib/kmp/testdata/fuzz/FuzzFindAll/9be40f71bc49b1b5c3b8e08d58d0f69cc22aefb12fd9b5931e49ff0e41953738 b/lib/diskio/testdata/fuzz/FuzzFindAll/9be40f71bc49b1b5c3b8e08d58d0f69cc22aefb12fd9b5931e49ff0e41953738 index be67506..be67506 100644 --- a/lib/kmp/testdata/fuzz/FuzzFindAll/9be40f71bc49b1b5c3b8e08d58d0f69cc22aefb12fd9b5931e49ff0e41953738 +++ b/lib/diskio/testdata/fuzz/FuzzFindAll/9be40f71bc49b1b5c3b8e08d58d0f69cc22aefb12fd9b5931e49ff0e41953738 diff --git a/lib/kmp/testdata/fuzz/FuzzFindAll/e43317ec61b0da9627d7b2fc0237d369082a6bf5dfe39e05c113b42ff6218d5d b/lib/diskio/testdata/fuzz/FuzzFindAll/e43317ec61b0da9627d7b2fc0237d369082a6bf5dfe39e05c113b42ff6218d5d index c3bfa37..c3bfa37 100644 --- a/lib/kmp/testdata/fuzz/FuzzFindAll/e43317ec61b0da9627d7b2fc0237d369082a6bf5dfe39e05c113b42ff6218d5d +++ b/lib/diskio/testdata/fuzz/FuzzFindAll/e43317ec61b0da9627d7b2fc0237d369082a6bf5dfe39e05c113b42ff6218d5d |