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