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.hbase.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 - 1;
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 - 1;
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 if (!currentRowNode.hasOccurrences() && rowLength >= key.getRowLength()) {
297 return -1;
298 }
299 return 0;
300 }
301
302 protected void followLastFansUntilExhausted(){
303 while(currentRowNode.hasFan()){
304 followLastFan();
305 }
306 }
307
308
309
310
311
312
313
314
315 protected CellScannerPosition fixRowTokenMissReverse(int searcherIsAfterInputKey) {
316 if (searcherIsAfterInputKey < 0) {
317 boolean foundPreviousRow = previousRow(true);
318 if(foundPreviousRow){
319 populateLastNonRowFields();
320 return CellScannerPosition.BEFORE;
321 }else{
322 return CellScannerPosition.BEFORE_FIRST;
323 }
324
325 }else{
326 if(currentRowNode.hasOccurrences()){
327 populateFirstNonRowFields();
328 return CellScannerPosition.BEFORE;
329 }
330 boolean foundNextRow = nextRow();
331 if(foundNextRow){
332 return CellScannerPosition.AFTER;
333 }else{
334 return CellScannerPosition.AFTER_LAST;
335 }
336 }
337 }
338
339
340
341
342
343 protected CellScannerPosition fixRowTokenMissForward(int searcherIsAfterInputKey) {
344 if (searcherIsAfterInputKey < 0) {
345 if(currentRowNode.hasOccurrences()){
346 populateFirstNonRowFields();
347 return CellScannerPosition.AFTER;
348 }
349 boolean foundNextRow = nextRow();
350 if(foundNextRow){
351 return CellScannerPosition.AFTER;
352 }else{
353 return CellScannerPosition.AFTER_LAST;
354 }
355
356 }else{
357 discardCurrentRowNode(true);
358 boolean foundNextRow = nextRow();
359 if(foundNextRow){
360 return CellScannerPosition.AFTER;
361 }else{
362 return CellScannerPosition.AFTER_LAST;
363 }
364 }
365 }
366
367
368
369
370 protected CellScannerPosition fixRowFanMissReverse(int fanInsertionPoint){
371 if(fanInsertionPoint == 0){
372 if (currentRowNode.hasOccurrences()) {
373 populateLastNonRowFields();
374 return CellScannerPosition.BEFORE;
375 }
376 boolean foundPreviousRow = previousRow(true);
377 if(foundPreviousRow){
378 populateLastNonRowFields();
379 return CellScannerPosition.BEFORE;
380 }
381 return CellScannerPosition.BEFORE_FIRST;
382 }
383
384
385 followFan(fanInsertionPoint - 1);
386 followLastFansUntilExhausted();
387 populateLastNonRowFields();
388 return CellScannerPosition.BEFORE;
389 }
390
391 protected CellScannerPosition fixRowFanMissForward(int fanInsertionPoint){
392 if(fanInsertionPoint >= currentRowNode.getFanOut()){
393 discardCurrentRowNode(true);
394 if (!nextRow()) {
395 return CellScannerPosition.AFTER_LAST;
396 } else {
397 return CellScannerPosition.AFTER;
398 }
399 }
400
401 followFan(fanInsertionPoint);
402 if(hasOccurrences()){
403 populateFirstNonRowFields();
404 return CellScannerPosition.AFTER;
405 }
406
407 if(nextRowInternal()){
408 populateFirstNonRowFields();
409 return CellScannerPosition.AFTER;
410
411 }else{
412 return CellScannerPosition.AFTER_LAST;
413 }
414 }
415
416 }