bytes,internal/bytealg: eliminate HashStrBytes,HashStrRevBytes using …

…generics

The logic of HashStrBytes, HashStrRevBytes and HashStr, HashStrRev,
are exactly the same, except that the types are different.

Since the bootstrap toolchain is bumped to 1.20, we can eliminate them
by using generics.

Change-Id: I4336b1cab494ba963f09646c169b45f6b1ee62e3
GitHub-Last-Rev: b11a2bf9476d54bed4bd18a3f9269b5c95a66d67
GitHub-Pull-Request: golang/go#63766
Reviewed-on: https://go-review.googlesource.com/c/go/+/538175
Reviewed-by: Keith Randall <khr@golang.org>
Reviewed-by: David Chase <drchase@google.com>
Reviewed-by: Keith Randall <khr@google.com>
Auto-Submit: Keith Randall <khr@golang.org>
LUCI-TryBot-Result: Go LUCI <golang-scoped@luci-project-accounts.iam.gserviceaccount.com>

diff --git a/src/bytes/bytes.go b/src/bytes/bytes.go
index 9ee66cae4e11f1c6e43af0b3989b754f0f39ff92..95afb30b40ca2d14c06a3681b195d3d006ce035d 100644 (file)
--- a/src/bytes/bytes.go
+++ b/src/bytes/bytes.go
@@ -122,7 +122,7 @@ func LastIndex(s, sep []byte) int {
                return -1
        }
        // Rabin-Karp search from the end of the string
-       hashss, pow := bytealg.HashStrRevBytes(sep)
+       hashss, pow := bytealg.HashStrRev(sep)
        last := len(s) - n
        var h uint32
        for i := len(s) - 1; i >= last; i-- {

diff --git a/src/internal/bytealg/bytealg.go b/src/internal/bytealg/bytealg.go
index 28f2742c0e8e31360e7472268ae34057f1ff9e46..ae4b8b48d2eaa385e9ed4339e6ec58fc1abf4ddd 100644 (file)
--- a/src/internal/bytealg/bytealg.go
+++ b/src/internal/bytealg/bytealg.go
@@ -24,33 +24,16 @@ const (
 // If MaxLen is not 0, make sure MaxLen >= 4.
 var MaxLen int
 
-// FIXME: the logic of HashStrBytes, HashStrRevBytes, IndexRabinKarpBytes and HashStr, HashStrRev,
-// IndexRabinKarp are exactly the same, except that the types are different. Can we eliminate
-// three of them without causing allocation?
+// FIXME: the logic of IndexRabinKarpBytes and IndexRabinKarp are exactly the same,
+// except that the types are different.
+// Can we eliminate one of them without causing allocation?
 
 // PrimeRK is the prime base used in Rabin-Karp algorithm.
 const PrimeRK = 16777619
 
-// HashStrBytes returns the hash and the appropriate multiplicative
-// factor for use in Rabin-Karp algorithm.
-func HashStrBytes(sep []byte) (uint32, uint32) {
-       hash := uint32(0)
-       for i := 0; i < len(sep); i++ {
-               hash = hash*PrimeRK + uint32(sep[i])
-       }
-       var pow, sq uint32 = 1, PrimeRK
-       for i := len(sep); i > 0; i >>= 1 {
-               if i&1 != 0 {
-                       pow *= sq
-               }
-               sq *= sq
-       }
-       return hash, pow
-}
-
 // HashStr returns the hash and the appropriate multiplicative
 // factor for use in Rabin-Karp algorithm.
-func HashStr(sep string) (uint32, uint32) {
+func HashStr[T string | []byte](sep T) (uint32, uint32) {
        hash := uint32(0)
        for i := 0; i < len(sep); i++ {
                hash = hash*PrimeRK + uint32(sep[i])
@@ -65,26 +48,9 @@ func HashStr(sep string) (uint32, uint32) {
        return hash, pow
 }
 
-// HashStrRevBytes returns the hash of the reverse of sep and the
-// appropriate multiplicative factor for use in Rabin-Karp algorithm.
-func HashStrRevBytes(sep []byte) (uint32, uint32) {
-       hash := uint32(0)
-       for i := len(sep) - 1; i >= 0; i-- {
-               hash = hash*PrimeRK + uint32(sep[i])
-       }
-       var pow, sq uint32 = 1, PrimeRK
-       for i := len(sep); i > 0; i >>= 1 {
-               if i&1 != 0 {
-                       pow *= sq
-               }
-               sq *= sq
-       }
-       return hash, pow
-}
-
 // HashStrRev returns the hash of the reverse of sep and the
 // appropriate multiplicative factor for use in Rabin-Karp algorithm.
-func HashStrRev(sep string) (uint32, uint32) {
+func HashStrRev[T string | []byte](sep T) (uint32, uint32) {
        hash := uint32(0)
        for i := len(sep) - 1; i >= 0; i-- {
                hash = hash*PrimeRK + uint32(sep[i])
@@ -103,7 +69,7 @@ func HashStrRev(sep string) (uint32, uint32) {
 // first occurrence of substr in s, or -1 if not present.
 func IndexRabinKarpBytes(s, sep []byte) int {
        // Rabin-Karp search
-       hashsep, pow := HashStrBytes(sep)
+       hashsep, pow := HashStr(sep)
        n := len(sep)
        var h uint32
        for i := 0; i < n; i++ {