[dev.power64] code review 160200044: build: merge default into dev.power64

src/pkg/strings/strings.go

 // Copyright 2009 The Go Authors. All rights reserved.
 // Use of this source code is governed by a BSD-style
 // license that can be found in the LICENSE file.
 
 // Package strings implements simple functions to manipulate strings.
 package strings
 
 import (
         "unicode"
         "unicode/utf8"
@@ skipping 25 matching lines @@
         // add the rest, if there is any
         if cur < len(s) {
                 a[i] = s[cur:]
         }
         return a
 }
 
 // primeRK is the prime base used in Rabin-Karp algorithm.
 const primeRK = 16777619
 
-// hashstr returns the hash and the appropriate multiplicative
+// hashStr returns the hash and the appropriate multiplicative
 // factor for use in Rabin-Karp algorithm.
-func hashstr(sep string) (uint32, uint32) {
+func hashStr(sep string) (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
+}
+
+// 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) {
+        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
 }
@@ skipping 15 matching lines @@
                 }
                 return n
         case len(sep) > len(s):
                 return 0
         case len(sep) == len(s):
                 if sep == s {
                         return 1
                 }
                 return 0
         }
-        hashsep, pow := hashstr(sep)
+        // Rabin-Karp search
+        hashsep, pow := hashStr(sep)
         h := uint32(0)
         for i := 0; i < len(sep); i++ {
                 h = h*primeRK + uint32(s[i])
         }
         lastmatch := 0
         if h == hashsep && s[:len(sep)] == sep {
                 n++
                 lastmatch = len(sep)
         }
         for i := len(sep); i < len(s); {
@@ skipping 33 matching lines @@
         case n == 1:
                 return IndexByte(s, sep[0])
         case n == len(s):
                 if sep == s {
                         return 0
                 }
                 return -1
         case n > len(s):
                 return -1
         }
-        // Hash sep.
-        hashsep, pow := hashstr(sep)
+        // Rabin-Karp search
+        hashsep, pow := hashStr(sep)
         var h uint32
         for i := 0; i < n; i++ {
                 h = h*primeRK + uint32(s[i])
         }
         if h == hashsep && s[:n] == sep {
                 return 0
         }
         for i := n; i < len(s); {
                 h *= primeRK
                 h += uint32(s[i])
                 h -= pow * uint32(s[i-n])
                 i++
                 if h == hashsep && s[i-n:i] == sep {
                         return i - n
                 }
         }
         return -1
 }
 
 // LastIndex returns the index of the last instance of sep in s, or -1 if sep is not present in s.
 func LastIndex(s, sep string) int {
         n := len(sep)
-        if n == 0 {
+        switch {
+        case n == 0:
                 return len(s)
-        }
-        c := sep[0]
-        if n == 1 {
+        case n == 1:
                 // special case worth making fast
+                c := sep[0]
                 for i := len(s) - 1; i >= 0; i-- {
                         if s[i] == c {
                                 return i
                         }
                 }
                 return -1
-        }
-        // n > 1
-        for i := len(s) - n; i >= 0; i-- {
-                if s[i] == c && s[i:i+n] == sep {
+        case n == len(s):
+                if sep == s {
+                        return 0
+                }
+                return -1
+        case n > len(s):
+                return -1
+        }
+        // Rabin-Karp search from the end of the string
+        hashsep, pow := hashStrRev(sep)
+        last := len(s) - n
+        var h uint32
+        for i := len(s) - 1; i >= last; i-- {
+                h = h*primeRK + uint32(s[i])
+        }
+        if h == hashsep && s[last:] == sep {
+                return last
+        }
+        for i := last - 1; i >= 0; i-- {
+                h *= primeRK
+                h += uint32(s[i])
+                h -= pow * uint32(s[i+n])
+                if h == hashsep && s[i:i+n] == sep {
                         return i
                 }
         }
         return -1
 }
 
 // IndexRune returns the index of the first instance of the Unicode code point
 // r, or -1 if rune is not present in s.
 func IndexRune(s string, r rune) int {
         switch {
@@ skipping 436 matching lines @@
 // If s doesn't end with suffix, s is returned unchanged.
 func TrimSuffix(s, suffix string) string {
         if HasSuffix(s, suffix) {
                 return s[:len(s)-len(suffix)]
         }
         return s
 }
 
 // Replace returns a copy of the string s with the first n
 // non-overlapping instances of old replaced by new.
+// If old is empty, it matches at the beginning of the string
+// and after each UTF-8 sequence, yielding up to k+1 replacements
+// for a k-rune string.
 // If n < 0, there is no limit on the number of replacements.
 func Replace(s, old, new string, n int) string {
         if old == new || n == 0 {
                 return s // avoid allocation
         }
 
         // Compute number of replacements.
         if m := Count(s, old); m == 0 {
                 return s // avoid allocation
         } else if n < 0 || m < n {
@@ skipping 69 matching lines @@
                 }
                 if r == tr {
                         continue
                 }
                 return false
         }
 
         // One string is empty.  Are both?
         return s == t
 }