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