libgo/go/bytes/bytes_generic.go

   1 // Copyright 2015 The Go Authors. All rights reserved.
   2 // Use of this source code is governed by a BSD-style
   3 // license that can be found in the LICENSE file.
   4
   5 // -build !amd64,!s390x,!arm64
   6
   7 package bytes
   8
   9 // Index returns the index of the first instance of sep in s, or -1 if sep is not present in s.
  10 func Index(s, sep []byte) int {
  11         n := len(sep)
  12         switch {
  13         case n == 0:
  14                 return 0
  15         case n == 1:
  16                 return IndexByte(s, sep[0])
  17         case n == len(s):
  18                 if Equal(sep, s) {
  19                         return 0
  20                 }
  21                 return -1
  22         case n > len(s):
  23                 return -1
  24         }
  25         c := sep[0]
  26         i := 0
  27         fails := 0
  28         t := s[:len(s)-n+1]
  29         for i < len(t) {
  30                 if t[i] != c {
  31                         o := IndexByte(t[i:], c)
  32                         if o < 0 {
  33                                 break
  34                         }
  35                         i += o
  36                 }
  37                 if Equal(s[i:i+n], sep) {
  38                         return i
  39                 }
  40                 i++
  41                 fails++
  42                 if fails >= 4+i>>4 && i < len(t) {
  43                         // Give up on IndexByte, it isn't skipping ahead
  44                         // far enough to be better than Rabin-Karp.
  45                         // Experiments (using IndexPeriodic) suggest
  46                         // the cutover is about 16 byte skips.
  47                         // TODO: if large prefixes of sep are matching
  48                         // we should cutover at even larger average skips,
  49                         // because Equal becomes that much more expensive.
  50                         // This code does not take that effect into account.
  51                         j := indexRabinKarp(s[i:], sep)
  52                         if j < 0 {
  53                                 return -1
  54                         }
  55                         return i + j
  56                 }
  57         }
  58         return -1
  59 }
  60
  61 // Count counts the number of non-overlapping instances of sep in s.
  62 // If sep is an empty slice, Count returns 1 + the number of UTF-8-encoded code points in s.
  63 func Count(s, sep []byte) int {
  64         return countGeneric(s, sep)
  65 }