1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19 package org.apache.hadoop.hbase.codec.prefixtree.row;
20
21 import java.io.ByteArrayOutputStream;
22 import java.io.IOException;
23 import java.nio.ByteBuffer;
24 import java.util.Arrays;
25 import java.util.Collection;
26 import java.util.List;
27
28 import org.apache.hadoop.hbase.Cell;
29 import org.apache.hadoop.hbase.CellComparator;
30 import org.apache.hadoop.hbase.KeyValue;
31 import org.apache.hadoop.hbase.KeyValueUtil;
32 import org.apache.hadoop.hbase.testclassification.SmallTests;
33 import org.apache.hadoop.hbase.codec.prefixtree.decode.DecoderFactory;
34 import org.apache.hadoop.hbase.codec.prefixtree.encode.PrefixTreeEncoder;
35 import org.apache.hadoop.hbase.codec.prefixtree.row.data.TestRowDataSearchWithPrefix;
36 import org.apache.hadoop.hbase.codec.prefixtree.scanner.CellScannerPosition;
37 import org.apache.hadoop.hbase.codec.prefixtree.scanner.CellSearcher;
38 import org.apache.hadoop.hbase.util.CollectionUtils;
39 import org.junit.Assert;
40 import org.junit.Test;
41 import org.junit.experimental.categories.Category;
42 import org.junit.runner.RunWith;
43 import org.junit.runners.Parameterized;
44 import org.junit.runners.Parameterized.Parameters;
45
46 @Category(SmallTests.class)
47 @RunWith(Parameterized.class)
48 public class TestPrefixTreeSearcher {
49
50 protected static int BLOCK_START = 7;
51
52 @Parameters
53 public static Collection<Object[]> parameters() {
54 return new TestRowData.InMemory().getAllAsObjectArray();
55 }
56
57 protected TestRowData rows;
58 protected ByteBuffer block;
59
60 public TestPrefixTreeSearcher(TestRowData testRows) throws IOException {
61 this.rows = testRows;
62 ByteArrayOutputStream os = new ByteArrayOutputStream(1 << 20);
63 PrefixTreeEncoder kvBuilder = new PrefixTreeEncoder(os, true);
64 for (KeyValue kv : rows.getInputs()) {
65 kvBuilder.write(kv);
66 }
67 kvBuilder.flush();
68 byte[] outputBytes = os.toByteArray();
69 this.block = ByteBuffer.wrap(outputBytes);
70 }
71
72 @Test
73 public void testScanForwards() throws IOException {
74 CellSearcher searcher = null;
75 try {
76 searcher = DecoderFactory.checkOut(block, true);
77
78 int i = -1;
79 while (searcher.advance()) {
80 ++i;
81 KeyValue inputCell = rows.getInputs().get(i);
82 Cell outputCell = searcher.current();
83
84
85 Assert.assertEquals(inputCell, outputCell);
86 Assert.assertEquals(outputCell, inputCell);
87 Assert.assertTrue(CellComparator.equals(inputCell, outputCell));
88 }
89 Assert.assertEquals(rows.getInputs().size(), i + 1);
90 } finally {
91 DecoderFactory.checkIn(searcher);
92 }
93 }
94
95
96 @Test
97 public void testScanBackwards() throws IOException {
98 CellSearcher searcher = null;
99 try {
100 searcher = DecoderFactory.checkOut(block, true);
101 searcher.positionAfterLastCell();
102 int i = -1;
103 while (searcher.previous()) {
104 ++i;
105 int oppositeIndex = rows.getInputs().size() - i - 1;
106 KeyValue inputKv = rows.getInputs().get(oppositeIndex);
107 KeyValue outputKv = KeyValueUtil.copyToNewKeyValue(searcher.current());
108 Assert.assertEquals(inputKv, outputKv);
109 }
110 Assert.assertEquals(rows.getInputs().size(), i + 1);
111 } finally {
112 DecoderFactory.checkIn(searcher);
113 }
114 }
115
116
117 @Test
118 public void testRandomSeekHits() throws IOException {
119 CellSearcher searcher = null;
120 try {
121 searcher = DecoderFactory.checkOut(block, true);
122 for (KeyValue kv : rows.getInputs()) {
123 boolean hit = searcher.positionAt(kv);
124 Assert.assertTrue(hit);
125 Cell foundKv = searcher.current();
126 Assert.assertTrue(CellComparator.equals(kv, foundKv));
127 }
128 } finally {
129 DecoderFactory.checkIn(searcher);
130 }
131 }
132
133 @Test
134 public void testRandomSeekMisses() throws IOException {
135 CellSearcher searcher = null;
136 List<Integer> rowStartIndexes = rows.getRowStartIndexes();
137 try {
138 searcher = DecoderFactory.checkOut(block, true);
139
140
141 for(boolean beforeVsAfterOnMiss : new boolean[]{true, false}){
142 for (int i=0; i < rows.getInputs().size(); ++i) {
143 KeyValue kv = rows.getInputs().get(i);
144
145
146 KeyValue inputNextRow = KeyValueUtil.createFirstKeyInNextRow(kv);
147
148 CellScannerPosition position = beforeVsAfterOnMiss
149 ? searcher.positionAtOrBefore(inputNextRow)
150 : searcher.positionAtOrAfter(inputNextRow);
151 boolean isFirstInRow = rowStartIndexes.contains(i);
152 if(isFirstInRow){
153 int rowIndex = rowStartIndexes.indexOf(i);
154 if(rowIndex < rowStartIndexes.size() - 1){
155 if(beforeVsAfterOnMiss){
156 Assert.assertEquals(CellScannerPosition.BEFORE, position);
157 }else{
158 Assert.assertEquals(CellScannerPosition.AFTER, position);
159 }
160
161 int expectedInputIndex = beforeVsAfterOnMiss
162 ? rowStartIndexes.get(rowIndex + 1) - 1
163 : rowStartIndexes.get(rowIndex + 1);
164 Assert.assertEquals(rows.getInputs().get(expectedInputIndex), searcher.current());
165 }
166 }
167
168
169 KeyValue inputPreviousKv = KeyValueUtil.previousKey(kv);
170 boolean hit = searcher.positionAt(inputPreviousKv);
171 Assert.assertFalse(hit);
172 position = searcher.positionAtOrAfter(inputPreviousKv);
173 if(CollectionUtils.isLastIndex(rows.getInputs(), i)){
174 Assert.assertTrue(CellScannerPosition.AFTER_LAST == position);
175 }else{
176 Assert.assertTrue(CellScannerPosition.AFTER == position);
177
178
179
180 Assert.assertEquals(rows.getInputs().get(i+1), searcher.current());
181 }
182 }
183 }
184 } finally {
185 DecoderFactory.checkIn(searcher);
186 }
187 }
188
189
190 @Test
191 public void testRandomSeekIndividualAssertions() throws IOException {
192 CellSearcher searcher = null;
193 try {
194 searcher = DecoderFactory.checkOut(block, true);
195 rows.individualSearcherAssertions(searcher);
196 } finally {
197 DecoderFactory.checkIn(searcher);
198 }
199 }
200
201 @Test
202 public void testSeekWithPrefix() throws IOException {
203 if (!(rows instanceof TestRowDataSearchWithPrefix)) {
204 return;
205 }
206 CellSearcher searcher = null;
207 try {
208 searcher = DecoderFactory.checkOut(block, true);
209
210 KeyValue kv = rows.getInputs().get(1);
211 KeyValue firstKVOnRow = KeyValueUtil.createFirstOnRow(Arrays.copyOfRange(
212 kv.getRowArray(), kv.getRowOffset(),
213 kv.getRowOffset() + kv.getRowLength() / 2));
214 CellScannerPosition position = searcher.positionAtOrAfter(firstKVOnRow);
215 Assert.assertEquals(CellScannerPosition.AFTER, position);
216 Assert.assertEquals(kv, searcher.current());
217 } finally {
218 DecoderFactory.checkIn(searcher);
219 }
220 }
221 }