From 8c1a627e5cf1621cf44387b13d9a0631e44236ae Mon Sep 17 00:00:00 2001 From: Rob Pike Date: Wed, 18 Nov 2009 19:23:08 -0800 Subject: [PATCH] add bytes.IndexByte; common case we can make fast later. also pick off the special case in strings.Index. don't want strings.IndexByte because the call site will very rarely need to allocate and we can handle the test in the code itself. bytes.IndexByte can avoid a common allocation. R=rsc CC=golang-dev https://golang.org/cl/156091 --- src/pkg/bytes/bytes.go | 10 +++++ src/pkg/bytes/bytes_test.go | 76 +++++++++++++++++++++++++-------- src/pkg/strings/strings.go | 18 ++++++++ src/pkg/strings/strings_test.go | 9 ++++ 4 files changed, 96 insertions(+), 17 deletions(-) diff --git a/src/pkg/bytes/bytes.go b/src/pkg/bytes/bytes.go index 2739c5a3fe..171fa3d1bc 100644 --- a/src/pkg/bytes/bytes.go +++ b/src/pkg/bytes/bytes.go @@ -98,6 +98,16 @@ func Index(s, sep []byte) int { return -1; } +// IndexByte returns the index of the first instance of c in s, or -1 if c is not present in s. +func IndexByte(s []byte, c byte) int { + for i, b := range s { + if b == c { + return i + } + } + 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 []byte) int { n := len(sep); diff --git a/src/pkg/bytes/bytes_test.go b/src/pkg/bytes/bytes_test.go index 1b197e1dfb..b7f8262931 100644 --- a/src/pkg/bytes/bytes_test.go +++ b/src/pkg/bytes/bytes_test.go @@ -39,41 +39,83 @@ var faces = "☺☻☹" var commas = "1,2,3,4" var dots = "1....2....3....4" -type CompareTest struct { +type BinOpTest struct { a string; b string; - cmp int; + i int; } -var comparetests = []CompareTest{ - CompareTest{"", "", 0}, - CompareTest{"a", "", 1}, - CompareTest{"", "a", -1}, - CompareTest{"abc", "abc", 0}, - CompareTest{"ab", "abc", -1}, - CompareTest{"abc", "ab", 1}, - CompareTest{"x", "ab", 1}, - CompareTest{"ab", "x", -1}, - CompareTest{"x", "a", 1}, - CompareTest{"b", "x", -1}, +var comparetests = []BinOpTest{ + BinOpTest{"", "", 0}, + BinOpTest{"a", "", 1}, + BinOpTest{"", "a", -1}, + BinOpTest{"abc", "abc", 0}, + BinOpTest{"ab", "abc", -1}, + BinOpTest{"abc", "ab", 1}, + BinOpTest{"x", "ab", 1}, + BinOpTest{"ab", "x", -1}, + BinOpTest{"x", "a", 1}, + BinOpTest{"b", "x", -1}, } func TestCompare(t *testing.T) { - for i := 0; i < len(comparetests); i++ { - tt := comparetests[i]; + for _, tt := range comparetests { a := strings.Bytes(tt.a); b := strings.Bytes(tt.b); cmp := Compare(a, b); eql := Equal(a, b); - if cmp != tt.cmp { + if cmp != tt.i { t.Errorf(`Compare(%q, %q) = %v`, tt.a, tt.b, cmp) } - if eql != (tt.cmp == 0) { + if eql != (tt.i == 0) { t.Errorf(`Equal(%q, %q) = %v`, tt.a, tt.b, eql) } } } +var indextests = []BinOpTest{ + BinOpTest{"", "", 0}, + BinOpTest{"a", "", 0}, + BinOpTest{"", "a", -1}, + BinOpTest{"abc", "abc", 0}, + BinOpTest{"ab", "abc", -1}, + BinOpTest{"abc", "bc", 1}, + BinOpTest{"x", "ab", -1}, + // one-byte tests for IndexByte + BinOpTest{"ab", "x", -1}, + BinOpTest{"", "a", -1}, + BinOpTest{"x", "a", -1}, + BinOpTest{"x", "x", 0}, + BinOpTest{"abc", "a", 0}, + BinOpTest{"abc", "b", 1}, + BinOpTest{"abc", "c", 2}, + BinOpTest{"abc", "x", -1}, +} + +func TestIndex(t *testing.T) { + for _, tt := range indextests { + a := strings.Bytes(tt.a); + b := strings.Bytes(tt.b); + pos := Index(a, b); + if pos != tt.i { + t.Errorf(`Index(%q, %q) = %v`, tt.a, tt.b, pos) + } + } +} + +func TestIndexByte(t *testing.T) { + for _, tt := range indextests { + if len(tt.b) != 1 { + continue + } + a := strings.Bytes(tt.a); + b := tt.b[0]; + pos := IndexByte(a, b); + if pos != tt.i { + t.Errorf(`IndexByte(%q, '%c') = %v`, tt.a, b, pos) + } + } +} type ExplodeTest struct { s string; diff --git a/src/pkg/strings/strings.go b/src/pkg/strings/strings.go index 7ccfc5ca84..fb3070a1a5 100644 --- a/src/pkg/strings/strings.go +++ b/src/pkg/strings/strings.go @@ -56,6 +56,15 @@ func Index(s, sep string) int { return 0 } c := sep[0]; + if n == 1 { + // special case worth making fast + for i := 0; i < len(s); i++ { + if s[i] == c { + return i + } + } + return -1; + } for i := 0; i+n <= len(s); i++ { if s[i] == c && (n == 1 || s[i:i+n] == sep) { return i @@ -71,6 +80,15 @@ func LastIndex(s, sep string) int { return len(s) } c := sep[0]; + if n == 1 { + // special case worth making fast + for i := len(s) - 1; i >= 0; i-- { + if s[i] == c { + return i + } + } + return -1; + } for i := len(s) - n; i >= 0; i-- { if s[i] == c && (n == 1 || s[i:i+n] == sep) { return i diff --git a/src/pkg/strings/strings_test.go b/src/pkg/strings/strings_test.go index 0073f0d0ea..1171db224e 100644 --- a/src/pkg/strings/strings_test.go +++ b/src/pkg/strings/strings_test.go @@ -46,6 +46,14 @@ var indexTests = []IndexTest{ IndexTest{"foo", "", 0}, IndexTest{"foo", "o", 1}, IndexTest{"abcABCabc", "A", 3}, + // cases with one byte strings - test special case in Index() + IndexTest{"", "a", -1}, + IndexTest{"x", "a", -1}, + IndexTest{"x", "x", 0}, + IndexTest{"abc", "a", 0}, + IndexTest{"abc", "b", 1}, + IndexTest{"abc", "c", 2}, + IndexTest{"abc", "x", -1}, } var lastIndexTests = []IndexTest{ @@ -54,6 +62,7 @@ var lastIndexTests = []IndexTest{ IndexTest{"", "foo", -1}, IndexTest{"fo", "foo", -1}, IndexTest{"foo", "foo", 0}, + IndexTest{"foo", "f", 0}, IndexTest{"oofofoofooo", "f", 7}, IndexTest{"oofofoofooo", "foo", 7}, IndexTest{"barfoobarfoo", "foo", 9}, -- 2.50.0