Update Go library to last weekly.

From-SVN: r180552

3 files changed, 208 insertions, 5 deletions

diff --git a/libgo/go/index/suffixarray/qsufsort.go b/libgo/go/index/suffixarray/qsufsort.go
index 30c1104..c69be43 100644
--- a/libgo/go/index/suffixarray/qsufsort.go
+++ b/libgo/go/index/suffixarray/qsufsort.go
@@ -37,7 +37,7 @@ func qsufsort(data []byte) []int {
 	inv := initGroups(sa, data)
 
 	// the index starts 1-ordered
-	sufSortable := &suffixSortable{sa, inv, 1}
+	sufSortable := &suffixSortable{sa: sa, inv: inv, h: 1}
 
 	for sa[0] > -len(sa) { // until all suffixes are one big sorted group
 		// The suffixes are h-ordered, make them 2*h-ordered
@@ -135,6 +135,7 @@ type suffixSortable struct {
 	sa  []int
 	inv []int
 	h   int
+	buf []int // common scratch space
 }
 
 func (x *suffixSortable) Len() int           { return len(x.sa) }
@@ -142,7 +143,7 @@ func (x *suffixSortable) Less(i, j int) bool { return x.inv[x.sa[i]+x.h] < x.inv
 func (x *suffixSortable) Swap(i, j int)      { x.sa[i], x.sa[j] = x.sa[j], x.sa[i] }
 
 func (x *suffixSortable) updateGroups(offset int) {
-	bounds := make([]int, 0, 4)
+	bounds := x.buf[0:0]
 	group := x.inv[x.sa[0]+x.h]
 	for i := 1; i < len(x.sa); i++ {
 		if g := x.inv[x.sa[i]+x.h]; g > group {
@@ -151,6 +152,7 @@ func (x *suffixSortable) updateGroups(offset int) {
 		}
 	}
 	bounds = append(bounds, len(x.sa))
+	x.buf = bounds
 
 	// update the group numberings after all new groups are determined
 	prev := 0
diff --git a/libgo/go/index/suffixarray/suffixarray.go b/libgo/go/index/suffixarray/suffixarray.go
index 82e98d2..174460c 100644
--- a/libgo/go/index/suffixarray/suffixarray.go
+++ b/libgo/go/index/suffixarray/suffixarray.go
@@ -18,6 +18,9 @@ package suffixarray
 
 import (
 	"bytes"
+	"encoding/binary"
+	"io"
+	"os"
 	"regexp"
 	"sort"
 )
@@ -25,7 +28,7 @@ import (
 // Index implements a suffix array for fast substring search.
 type Index struct {
 	data []byte
-	sa   []int // suffix array for data
+	sa   []int // suffix array for data; len(sa) == len(data)
 }
 
 // New creates a new Index for data.
@@ -34,6 +37,129 @@ func New(data []byte) *Index {
 	return &Index{data, qsufsort(data)}
 }
 
+// writeInt writes an int x to w using buf to buffer the write.
+func writeInt(w io.Writer, buf []byte, x int) os.Error {
+	binary.PutVarint(buf, int64(x))
+	_, err := w.Write(buf[0:binary.MaxVarintLen64])
+	return err
+}
+
+// readInt reads an int x from r using buf to buffer the read and returns x.
+func readInt(r io.Reader, buf []byte) (int, os.Error) {
+	_, err := io.ReadFull(r, buf[0:binary.MaxVarintLen64]) // ok to continue with error
+	x, _ := binary.Varint(buf)
+	return int(x), err
+}
+
+// writeSlice writes data[:n] to w and returns n.
+// It uses buf to buffer the write.
+func writeSlice(w io.Writer, buf []byte, data []int) (n int, err os.Error) {
+	// encode as many elements as fit into buf
+	p := binary.MaxVarintLen64
+	for ; n < len(data) && p+binary.MaxVarintLen64 <= len(buf); n++ {
+		p += binary.PutUvarint(buf[p:], uint64(data[n]))
+	}
+
+	// update buffer size
+	binary.PutVarint(buf, int64(p))
+
+	// write buffer
+	_, err = w.Write(buf[0:p])
+	return
+}
+
+// readSlice reads data[:n] from r and returns n.
+// It uses buf to buffer the read.
+func readSlice(r io.Reader, buf []byte, data []int) (n int, err os.Error) {
+	// read buffer size
+	var size int
+	size, err = readInt(r, buf)
+	if err != nil {
+		return
+	}
+
+	// read buffer w/o the size
+	if _, err = io.ReadFull(r, buf[binary.MaxVarintLen64:size]); err != nil {
+		return
+	}
+
+	// decode as many elements as present in buf
+	for p := binary.MaxVarintLen64; p < size; n++ {
+		x, w := binary.Uvarint(buf[p:])
+		data[n] = int(x)
+		p += w
+	}
+
+	return
+}
+
+const bufSize = 16 << 10 // reasonable for BenchmarkSaveRestore
+
+// Read reads the index from r into x; x must not be nil.
+func (x *Index) Read(r io.Reader) os.Error {
+	// buffer for all reads
+	buf := make([]byte, bufSize)
+
+	// read length
+	n, err := readInt(r, buf)
+	if err != nil {
+		return err
+	}
+
+	// allocate space
+	if 2*n < cap(x.data) || cap(x.data) < n {
+		// new data is significantly smaller or larger then
+		// existing buffers - allocate new ones
+		x.data = make([]byte, n)
+		x.sa = make([]int, n)
+	} else {
+		// re-use existing buffers
+		x.data = x.data[0:n]
+		x.sa = x.sa[0:n]
+	}
+
+	// read data
+	if _, err := io.ReadFull(r, x.data); err != nil {
+		return err
+	}
+
+	// read index
+	for sa := x.sa; len(sa) > 0; {
+		n, err := readSlice(r, buf, sa)
+		if err != nil {
+			return err
+		}
+		sa = sa[n:]
+	}
+	return nil
+}
+
+// Write writes the index x to w.
+func (x *Index) Write(w io.Writer) os.Error {
+	// buffer for all writes
+	buf := make([]byte, bufSize)
+
+	// write length
+	if err := writeInt(w, buf, len(x.data)); err != nil {
+		return err
+	}
+
+	// write data
+	if _, err := w.Write(x.data); err != nil {
+		return err
+	}
+
+	// write index
+	for sa := x.sa; len(sa) > 0; {
+		n, err := writeSlice(w, buf, sa)
+		if err != nil {
+			return err
+		}
+		sa = sa[n:]
+	}
+	return nil
+}
+
 // Bytes returns the data over which the index was created.
 // It must not be modified.
 //
@@ -65,9 +191,10 @@ func (x *Index) lookupAll(s []byte) []int {
 func (x *Index) Lookup(s []byte, n int) (result []int) {
 	if len(s) > 0 && n != 0 {
 		matches := x.lookupAll(s)
-		if len(matches) < n || n < 0 {
+		if n < 0 || len(matches) < n {
 			n = len(matches)
 		}
+		// 0 <= n <= len(matches)
 		if n > 0 {
 			result = make([]int, n)
 			copy(result, matches)
diff --git a/libgo/go/index/suffixarray/suffixarray_test.go b/libgo/go/index/suffixarray/suffixarray_test.go
index 0237485..f6b2f00 100644
--- a/libgo/go/index/suffixarray/suffixarray_test.go
+++ b/libgo/go/index/suffixarray/suffixarray_test.go
@@ -6,6 +6,7 @@ package suffixarray
 
 import (
 	"bytes"
+	"rand"
 	"regexp"
 	"sort"
 	"strings"
@@ -213,14 +214,44 @@ func (a *index) at(i int) []byte    { return a.data[a.sa[i]:] }
 
 func testConstruction(t *testing.T, tc *testCase, x *Index) {
 	if !sort.IsSorted((*index)(x)) {
-		t.Errorf("testConstruction failed %s", tc.name)
+		t.Errorf("failed testConstruction %s", tc.name)
 	}
 }
 
+func equal(x, y *Index) bool {
+	if !bytes.Equal(x.data, y.data) {
+		return false
+	}
+	for i, j := range x.sa {
+		if j != y.sa[i] {
+			return false
+		}
+	}
+	return true
+}
+
+// returns the serialized index size
+func testSaveRestore(t *testing.T, tc *testCase, x *Index) int {
+	var buf bytes.Buffer
+	if err := x.Write(&buf); err != nil {
+		t.Errorf("failed writing index %s (%s)", tc.name, err)
+	}
+	size := buf.Len()
+	var y Index
+	if err := y.Read(&buf); err != nil {
+		t.Errorf("failed reading index %s (%s)", tc.name, err)
+	}
+	if !equal(x, &y) {
+		t.Errorf("restored index doesn't match saved index %s", tc.name)
+	}
+	return size
+}
+
 func TestIndex(t *testing.T) {
 	for _, tc := range testCases {
 		x := New([]byte(tc.source))
 		testConstruction(t, &tc, x)
+		testSaveRestore(t, &tc, x)
 		testLookups(t, &tc, x, 0)
 		testLookups(t, &tc, x, 1)
 		testLookups(t, &tc, x, 10)
@@ -228,3 +259,46 @@ func TestIndex(t *testing.T) {
 		testLookups(t, &tc, x, -1)
 	}
 }
+
+// Of all possible inputs, the random bytes have the least amount of substring
+// repetition, and the repeated bytes have the most. For most algorithms,
+// the running time of every input will be between these two.
+func benchmarkNew(b *testing.B, random bool) {
+	b.StopTimer()
+	data := make([]byte, 1e6)
+	if random {
+		for i := range data {
+			data[i] = byte(rand.Intn(256))
+		}
+	}
+	b.StartTimer()
+	for i := 0; i < b.N; i++ {
+		New(data)
+	}
+}
+
+func BenchmarkNewIndexRandom(b *testing.B) {
+	benchmarkNew(b, true)
+}
+func BenchmarkNewIndexRepeat(b *testing.B) {
+	benchmarkNew(b, false)
+}
+
+func BenchmarkSaveRestore(b *testing.B) {
+	b.StopTimer()
+	r := rand.New(rand.NewSource(0x5a77a1)) // guarantee always same sequence
+	data := make([]byte, 10<<20)            // 10MB of data to index
+	for i := range data {
+		data[i] = byte(r.Intn(256))
+	}
+	x := New(data)
+	size := testSaveRestore(nil, nil, x)       // verify correctness
+	buf := bytes.NewBuffer(make([]byte, size)) // avoid growing
+	b.SetBytes(int64(size))
+	b.StartTimer()
+	for i := 0; i < b.N; i++ {
+		x.Write(buf)
+		var y Index
+		y.Read(buf)
+	}
+}