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.decode;
20
21 import org.apache.hadoop.classification.InterfaceAudience;
22 import org.apache.hadoop.hbase.Cell;
23 import org.apache.hadoop.hbase.CellUtil;
24 import org.apache.hadoop.hbase.codec.prefixtree.PrefixTreeBlockMeta;
25 import org.apache.hadoop.hbase.codec.prefixtree.scanner.CellScannerPosition;
26 import org.apache.hadoop.hbase.codec.prefixtree.scanner.CellSearcher;
27
28 import com.google.common.primitives.UnsignedBytes;
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44 @InterfaceAudience.Private
45 public class PrefixTreeArraySearcher extends PrefixTreeArrayReversibleScanner implements
46 CellSearcher {
47
48
49
50 public PrefixTreeArraySearcher(PrefixTreeBlockMeta blockMeta, int rowTreeDepth,
51 int rowBufferLength, int qualifierBufferLength, int tagsBufferLength) {
52 super(blockMeta, rowTreeDepth, rowBufferLength, qualifierBufferLength, tagsBufferLength);
53 }
54
55
56
57
58 @Override
59 public boolean positionAt(Cell key) {
60 return CellScannerPosition.AT == positionAtOrAfter(key);
61 }
62
63 @Override
64 public CellScannerPosition positionAtOrBefore(Cell key) {
65 reInitFirstNode();
66 int fanIndex = -1;
67
68 while(true){
69
70 int currentNodeDepth = rowLength;
71 int rowTokenComparison = compareToCurrentToken(key);
72 if(rowTokenComparison != 0){
73 return fixRowTokenMissReverse(rowTokenComparison);
74 }
75
76
77 if(rowMatchesAfterCurrentPosition(key)){
78 return positionAtQualifierTimestamp(key, true);
79 }
80
81
82 if(!currentRowNode.hasFan()){
83 if(hasOccurrences()){
84 populateLastNonRowFields();
85 return CellScannerPosition.BEFORE;
86 }else{
87
88 return fixRowFanMissReverse(0);
89 }
90 }
91
92
93 byte searchForByte = CellUtil.getRowByte(key, currentNodeDepth);
94 fanIndex = currentRowNode.whichFanNode(searchForByte);
95 if(fanIndex < 0){
96 int insertionPoint = -fanIndex;
97 return fixRowFanMissReverse(insertionPoint);
98 }
99
100 followFan(fanIndex);
101 }
102 }
103
104
105
106
107
108 @Override
109 public CellScannerPosition positionAtOrAfter(Cell key) {
110 reInitFirstNode();
111 int fanIndex = -1;
112
113 while(true){
114
115 int currentNodeDepth = rowLength;
116 int rowTokenComparison = compareToCurrentToken(key);
117 if(rowTokenComparison != 0){
118 return fixRowTokenMissForward(rowTokenComparison);
119 }
120
121
122 if(rowMatchesAfterCurrentPosition(key)){
123 return positionAtQualifierTimestamp(key, false);
124 }
125
126
127 if(!currentRowNode.hasFan()){
128 if(hasOccurrences()){
129 if (rowLength < key.getRowLength()) {
130 nextRow();
131 } else {
132 populateFirstNonRowFields();
133 }
134 return CellScannerPosition.AFTER;
135 }else{
136
137 return fixRowFanMissForward(0);
138 }
139 }
140
141
142 byte searchForByte = CellUtil.getRowByte(key, currentNodeDepth);
143 fanIndex = currentRowNode.whichFanNode(searchForByte);
144 if(fanIndex < 0){
145 int insertionPoint = -fanIndex;
146 return fixRowFanMissForward(insertionPoint);
147 }
148
149 followFan(fanIndex);
150 }
151 }
152
153 @Override
154 public boolean seekForwardTo(Cell key) {
155 if(currentPositionIsAfter(key)){
156
157 return false;
158 }
159 return positionAt(key);
160 }
161
162 @Override
163 public CellScannerPosition seekForwardToOrBefore(Cell key) {
164
165
166 if(currentPositionIsAfter(key)){
167
168 return CellScannerPosition.AFTER;
169 }
170
171 return positionAtOrBefore(key);
172 }
173
174 @Override
175 public CellScannerPosition seekForwardToOrAfter(Cell key) {
176
177
178 if(currentPositionIsAfter(key)){
179
180 return CellScannerPosition.AFTER;
181 }
182
183 return positionAtOrAfter(key);
184 }
185
186
187
188
189 @Override
190 public void positionAfterLastCell() {
191 resetToBeforeFirstEntry();
192 beforeFirst = false;
193 afterLast = true;
194 }
195
196
197
198
199 @Override
200 public boolean equals(Object obj) {
201
202 return super.equals(obj);
203 }
204
205
206
207
208 protected boolean currentPositionIsAfter(Cell cell){
209 return compareTo(cell) > 0;
210 }
211
212 protected CellScannerPosition positionAtQualifierTimestamp(Cell key, boolean beforeOnMiss) {
213 int minIndex = 0;
214 int maxIndex = currentRowNode.getLastCellIndex();
215 int diff;
216 while (true) {
217 int midIndex = (maxIndex + minIndex) / 2;
218 diff = populateNonRowFieldsAndCompareTo(midIndex, key);
219
220 if (diff == 0) {
221 return CellScannerPosition.AT;
222 } else if (minIndex == maxIndex) {
223 break;
224 } else if ((minIndex + 1) == maxIndex) {
225 diff = populateNonRowFieldsAndCompareTo(maxIndex, key);
226 if(diff > 0){
227 diff = populateNonRowFieldsAndCompareTo(minIndex, key);
228 }
229 break;
230 } else if (diff < 0) {
231 minIndex = currentCellIndex;
232 } else {
233 maxIndex = currentCellIndex;
234 }
235 }
236
237 if (diff == 0) {
238 return CellScannerPosition.AT;
239
240 } else if (diff < 0) {
241 if (beforeOnMiss) {
242 return CellScannerPosition.BEFORE;
243 }
244 if (advance()) {
245 return CellScannerPosition.AFTER;
246 }
247 return CellScannerPosition.AFTER_LAST;
248
249 } else {
250 if (!beforeOnMiss) {
251 return CellScannerPosition.AFTER;
252 }
253 if (previous()) {
254 return CellScannerPosition.BEFORE;
255 }
256 return CellScannerPosition.BEFORE_FIRST;
257 }
258 }
259
260
261
262
263
264
265 protected boolean rowMatchesAfterCurrentPosition(Cell key) {
266 if (!currentRowNode.hasOccurrences()) {
267 return false;
268 }
269 int thatRowLength = key.getRowLength();
270 if (rowLength != thatRowLength) {
271 return false;
272 }
273 return true;
274 }
275
276
277
278
279
280
281
282 protected int compareToCurrentToken(Cell key) {
283 int startIndex = rowLength - currentRowNode.getTokenLength();
284 int endIndexExclusive = startIndex + currentRowNode.getTokenLength();
285 for (int i = startIndex; i < endIndexExclusive; ++i) {
286 if (i >= key.getRowLength()) {
287 return -1;
288 }
289 byte keyByte = CellUtil.getRowByte(key, i);
290 byte thisByte = rowBuffer[i];
291 if (keyByte == thisByte) {
292 continue;
293 }
294 return UnsignedBytes.compare(keyByte, thisByte);
295 }
296 return 0;
297 }
298
299 protected void followLastFansUntilExhausted(){
300 while(currentRowNode.hasFan()){
301 followLastFan();
302 }
303 }
304
305
306
307
308
309
310
311
312 protected CellScannerPosition fixRowTokenMissReverse(int searcherIsAfterInputKey) {
313 if (searcherIsAfterInputKey < 0) {
314 boolean foundPreviousRow = previousRow(true);
315 if(foundPreviousRow){
316 populateLastNonRowFields();
317 return CellScannerPosition.BEFORE;
318 }else{
319 return CellScannerPosition.BEFORE_FIRST;
320 }
321
322 }else{
323 if(currentRowNode.hasOccurrences()){
324 populateFirstNonRowFields();
325 return CellScannerPosition.BEFORE;
326 }
327 boolean foundNextRow = nextRow();
328 if(foundNextRow){
329 return CellScannerPosition.AFTER;
330 }else{
331 return CellScannerPosition.AFTER_LAST;
332 }
333 }
334 }
335
336
337
338
339
340 protected CellScannerPosition fixRowTokenMissForward(int searcherIsAfterInputKey) {
341 if (searcherIsAfterInputKey < 0) {
342 if(currentRowNode.hasOccurrences()){
343 populateFirstNonRowFields();
344 return CellScannerPosition.AFTER;
345 }
346 boolean foundNextRow = nextRow();
347 if(foundNextRow){
348 return CellScannerPosition.AFTER;
349 }else{
350 return CellScannerPosition.AFTER_LAST;
351 }
352
353 }else{
354 discardCurrentRowNode(true);
355 boolean foundNextRow = nextRow();
356 if(foundNextRow){
357 return CellScannerPosition.AFTER;
358 }else{
359 return CellScannerPosition.AFTER_LAST;
360 }
361 }
362 }
363
364
365
366
367 protected CellScannerPosition fixRowFanMissReverse(int fanInsertionPoint){
368 if(fanInsertionPoint == 0){
369 boolean foundPreviousRow = previousRow(true);
370 if(foundPreviousRow){
371 populateLastNonRowFields();
372 return CellScannerPosition.BEFORE;
373 }
374 return CellScannerPosition.BEFORE_FIRST;
375 }
376
377
378 followFan(fanInsertionPoint - 1);
379 followLastFansUntilExhausted();
380 populateLastNonRowFields();
381 return CellScannerPosition.BEFORE;
382 }
383
384 protected CellScannerPosition fixRowFanMissForward(int fanInsertionPoint){
385 if(fanInsertionPoint >= currentRowNode.getFanOut()){
386 discardCurrentRowNode(true);
387 if (!nextRow()) {
388 return CellScannerPosition.AFTER_LAST;
389 } else {
390 return CellScannerPosition.AFTER;
391 }
392 }
393
394 followFan(fanInsertionPoint);
395 if(hasOccurrences()){
396 populateFirstNonRowFields();
397 return CellScannerPosition.AFTER;
398 }
399
400 if(nextRowInternal()){
401 populateFirstNonRowFields();
402 return CellScannerPosition.AFTER;
403
404 }else{
405 return CellScannerPosition.AFTER_LAST;
406 }
407 }
408
409 }