1// Copyright 2015, Joe Tsai. All rights reserved.
2// Use of this source code is governed by a BSD-style
3// license that can be found in the LICENSE.md file.
4
5package xflate
6
7import (
8	"bytes"
9	"math"
10	"reflect"
11	"testing"
12)
13
14func TestIndexRoundTrip(t *testing.T) {
15	vectors := []index{{
16		Records:  nil,
17		BackSize: 0,
18	}, {
19		Records:  []record{{10, 41, 1}, {52, 73, 1}, {84, 95, 1}},
20		BackSize: 1234,
21	}, {
22		Records:  []record{{162, 1024, 1}, {325, 2048, 1}, {524, 3072, 1}},
23		BackSize: 251,
24	}, {
25		Records:  []record{{math.MaxInt64, math.MaxInt64, 1}},
26		BackSize: math.MaxInt64,
27	}, {
28		Records:  []record{{5, 0, 1}, {10, 1, 1}, {15, 2, 1}, {math.MaxInt64, math.MaxInt64, 1}},
29		BackSize: 1337,
30	}}
31
32	for i, idx1 := range vectors {
33		var idx2 index
34		bb := new(bytes.Buffer)
35
36		// Write the encoded index.
37		var xw Writer
38		xw.wr = bb
39		if err := xw.encodeIndex(&idx1); err != nil {
40			t.Errorf("test %d, unexpected error: encodeIndex() = %v", i, err)
41		}
42
43		// Read the encoded index.
44		var xr Reader
45		xr.rd = bytes.NewReader(bb.Bytes())
46		idx2.IndexSize = idx1.IndexSize
47		if err := xr.decodeIndex(&idx2); err != nil {
48			t.Errorf("test %d, unexpected error: decodeIndex() = %v", i, err)
49		}
50
51		if !reflect.DeepEqual(idx1, idx2) {
52			t.Errorf("test %d, mismatching indexes:\ngot  %v\nwant %v", i, idx2, idx1)
53		}
54	}
55}
56
57func TestIndex(t *testing.T) {
58	var idx index
59
60	// Empty index.
61	if idx.LastRecord() != (record{}) {
62		t.Errorf("last record mismatch: got %v, want %v", idx.LastRecord(), record{})
63	}
64
65	// Append entries.
66	recs := []struct {
67		csize, rsize int64
68		ok           bool
69	}{
70		{0, 0, true},
71		{3, 5, true},
72		{31, 62, true},
73		{-1, 6, false},
74		{6, 13, true},
75		{math.MaxInt64, 3, false},
76	}
77	for _, v := range recs {
78		if ok := idx.AppendRecord(v.csize, v.rsize, 0); ok != v.ok {
79			t.Errorf("unexpected result: AppendRecord(%d, %d) = %v, want %v", v.csize, v.rsize, ok, v.ok)
80		}
81	}
82	if want := (record{40, 80, 0}); idx.LastRecord() != want {
83		t.Errorf("last record mismatch: got %v, want %v", idx.LastRecord(), want)
84	}
85
86	// Append indexes.
87	idxs := []struct {
88		idx index
89		ok  bool
90	}{
91		{index{Records: []record{}}, true},
92		{index{Records: []record{{1, 4, 1}, {3, 9, 2}, {13, 153, 3}}}, true},
93		{index{Records: []record{{1, 4, 4}, {3, 9, 5}, {13, 8, 6}}}, false},
94	}
95	for _, v := range idxs {
96		if ok := idx.AppendIndex(&v.idx); ok != v.ok {
97			t.Errorf("unexpected result: AppendIndex(%v) = %v, want %v", v.idx, ok, v.ok)
98		}
99	}
100	if want := (record{53, 233, 3}); idx.LastRecord() != want {
101		t.Errorf("last record mismatch: got %v, want %v", idx.LastRecord(), want)
102	}
103
104	// Final check.
105	want := index{Records: []record{
106		{0, 0, 0}, {3, 5, 0}, {34, 67, 0}, {40, 80, 0}, {41, 84, 1}, {43, 89, 2}, {53, 233, 3},
107	}}
108	if !reflect.DeepEqual(idx, want) {
109		t.Errorf("mismatching index:\ngot  %v\nwant %v", idx, want)
110	}
111}
112
113func TestIndexSearch(t *testing.T) {
114	type query struct {
115		offset     int64  // Input query
116		prev, curr record // Expected output
117	}
118	vectors := []struct {
119		idx index   // The index to query on
120		qs  []query // A list of query results
121	}{{
122		idx: index{},
123		qs: []query{
124			{0, record{}, record{}},
125			{5, record{}, record{}},
126		},
127	}, {
128		idx: index{Records: []record{{2, 14, 0}}},
129		qs: []query{
130			{0, record{0, 0, 0}, record{2, 14, 0}},
131			{5, record{0, 0, 0}, record{2, 14, 0}},
132			{13, record{0, 0, 0}, record{2, 14, 0}},
133			{14, record{2, 14, 0}, record{2, 14, 0}},
134			{15, record{2, 14, 0}, record{2, 14, 0}},
135		},
136	}, {
137		idx: index{Records: []record{{2, 14, 0}, {3, 17, 0}}},
138		qs: []query{
139			{0, record{0, 0, 0}, record{2, 14, 0}},
140			{5, record{0, 0, 0}, record{2, 14, 0}},
141			{13, record{0, 0, 0}, record{2, 14, 0}},
142			{14, record{2, 14, 0}, record{3, 17, 0}},
143			{15, record{2, 14, 0}, record{3, 17, 0}},
144			{16, record{2, 14, 0}, record{3, 17, 0}},
145			{17, record{3, 17, 0}, record{3, 17, 0}},
146			{18, record{3, 17, 0}, record{3, 17, 0}},
147		},
148	}, {
149		idx: index{Records: []record{{2, 14, 0}, {2, 14, 0}}},
150		qs: []query{
151			{0, record{0, 0, 0}, record{2, 14, 0}},
152			{13, record{0, 0, 0}, record{2, 14, 0}},
153			{14, record{2, 14, 0}, record{2, 14, 0}},
154			{15, record{2, 14, 0}, record{2, 14, 0}},
155		},
156	}, {
157		idx: index{Records: []record{
158			{17, 5, 0}, {30, 8, 0}, {41, 9, 0}, {53, 11, 0}, {66, 12, 0}, {80, 12, 0},
159			{95, 16, 0}, {111, 16, 0}, {128, 16, 0}, {146, 16, 0}, {165, 16, 0},
160			{185, 16, 0}, {206, 19, 0}, {228, 21, 0}, {251, 22, 0}, {275, 22, 0},
161		}},
162		qs: []query{
163			{0, record{0, 0, 0}, record{17, 5, 0}},
164			{9, record{41, 9, 0}, record{53, 11, 0}},
165			{10, record{41, 9, 0}, record{53, 11, 0}},
166			{11, record{53, 11, 0}, record{66, 12, 0}},
167			{15, record{80, 12, 0}, record{95, 16, 0}},
168			{16, record{185, 16, 0}, record{206, 19, 0}},
169			{17, record{185, 16, 0}, record{206, 19, 0}},
170			{22, record{275, 22, 0}, record{275, 22, 0}},
171			{100, record{275, 22, 0}, record{275, 22, 0}},
172		},
173	}}
174
175	for i, v := range vectors {
176		for j, q := range v.qs {
177			prev, curr := v.idx.GetRecords(v.idx.Search(q.offset))
178			if prev != q.prev || curr != q.curr {
179				t.Errorf("test %d, query %d, search result mismatch: Search(%d) = (%v %v), want (%v %v)",
180					i, j, q.offset, prev, curr, q.prev, q.curr)
181			}
182		}
183	}
184}
185