View Javadoc

1   /*
2    * Licensed to the Apache Software Foundation (ASF) under one
3    * or more contributor license agreements.  See the NOTICE file
4    * distributed with this work for additional information
5    * regarding copyright ownership.  The ASF licenses this file
6    * to you under the Apache License, Version 2.0 (the
7    * "License"); you may not use this file except in compliance
8    * with the License.  You may obtain a copy of the License at
9    *
10   *     http://www.apache.org/licenses/LICENSE-2.0
11   *
12   * Unless required by applicable law or agreed to in writing, software
13   * distributed under the License is distributed on an "AS IS" BASIS,
14   * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
15   * See the License for the specific language governing permissions and
16   * limitations under the License.
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.CellComparator;
24  import org.apache.hadoop.hbase.CellScanner;
25  import org.apache.hadoop.hbase.codec.prefixtree.PrefixTreeBlockMeta;
26  import org.apache.hadoop.hbase.codec.prefixtree.decode.column.ColumnReader;
27  import org.apache.hadoop.hbase.codec.prefixtree.decode.row.RowNodeReader;
28  import org.apache.hadoop.hbase.codec.prefixtree.decode.timestamp.MvccVersionDecoder;
29  import org.apache.hadoop.hbase.codec.prefixtree.decode.timestamp.TimestampDecoder;
30  import org.apache.hadoop.hbase.codec.prefixtree.encode.other.ColumnNodeType;
31  
32  /**
33   * Extends PtCell and manipulates its protected fields.  Could alternatively contain a PtCell and
34   * call get/set methods.
35   *
36   * This is an "Array" scanner to distinguish from a future "ByteBuffer" scanner.  This
37   * implementation requires that the bytes be in a normal java byte[] for performance.  The
38   * alternative ByteBuffer implementation would allow for accessing data in an off-heap ByteBuffer
39   * without copying the whole buffer on-heap.
40   */
41  @InterfaceAudience.Private
42  public class PrefixTreeArrayScanner extends PrefixTreeCell implements CellScanner {
43  
44    /***************** fields ********************************/
45  
46    protected PrefixTreeBlockMeta blockMeta;
47  
48    protected boolean beforeFirst;
49    protected boolean afterLast;
50  
51    protected RowNodeReader[] rowNodes;
52    protected int rowNodeStackIndex;
53  
54    protected RowNodeReader currentRowNode;
55    protected ColumnReader familyReader;
56    protected ColumnReader qualifierReader;
57    protected ColumnReader tagsReader;
58    protected TimestampDecoder timestampDecoder;
59    protected MvccVersionDecoder mvccVersionDecoder;
60  
61    protected boolean nubCellsRemain;
62    protected int currentCellIndex;
63    protected boolean movedToPrevious;
64  
65  
66    /*********************** construct ******************************/
67  
68    // pass in blockMeta so we can initialize buffers big enough for all cells in the block
69    public PrefixTreeArrayScanner(PrefixTreeBlockMeta blockMeta, int rowTreeDepth,
70        int rowBufferLength, int qualifierBufferLength, int tagsBufferLength) {
71      this.rowNodes = new RowNodeReader[rowTreeDepth];
72      for (int i = 0; i < rowNodes.length; ++i) {
73        rowNodes[i] = new RowNodeReader();
74      }
75      this.rowBuffer = new byte[rowBufferLength];
76      this.familyBuffer = new byte[PrefixTreeBlockMeta.MAX_FAMILY_LENGTH];
77      this.familyReader = new ColumnReader(familyBuffer, ColumnNodeType.FAMILY);
78      this.qualifierBuffer = new byte[qualifierBufferLength];
79      this.tagsBuffer = new byte[tagsBufferLength];
80      this.qualifierReader = new ColumnReader(qualifierBuffer, ColumnNodeType.QUALIFIER);
81      this.tagsReader = new ColumnReader(tagsBuffer, ColumnNodeType.TAGS);
82      this.timestampDecoder = new TimestampDecoder();
83      this.mvccVersionDecoder = new MvccVersionDecoder();
84    }
85  
86  
87    /**************** init helpers ***************************************/
88  
89    /**
90     * Call when first accessing a block.
91     * @return entirely new scanner if false
92     */
93    public boolean areBuffersBigEnough() {
94      if (rowNodes.length < blockMeta.getRowTreeDepth()) {
95        return false;
96      }
97      if (rowBuffer.length < blockMeta.getMaxRowLength()) {
98        return false;
99      }
100     if (qualifierBuffer.length < blockMeta.getMaxQualifierLength()) {
101       return false;
102     }
103     if(tagsBuffer.length < blockMeta.getMaxTagsLength()) {
104       return false;
105     }
106     return true;
107   }
108 
109   public void initOnBlock(PrefixTreeBlockMeta blockMeta, byte[] block,
110       boolean includeMvccVersion) {
111     this.block = block;
112     this.blockMeta = blockMeta;
113     this.familyOffset = familyBuffer.length;
114     this.familyReader.initOnBlock(blockMeta, block);
115     this.qualifierOffset = qualifierBuffer.length;
116     this.qualifierReader.initOnBlock(blockMeta, block);
117     this.tagsOffset = tagsBuffer.length;
118     this.tagsReader.initOnBlock(blockMeta, block);
119     this.timestampDecoder.initOnBlock(blockMeta, block);
120     this.mvccVersionDecoder.initOnBlock(blockMeta, block);
121     this.includeMvccVersion = includeMvccVersion;
122     resetToBeforeFirstEntry();
123   }
124 
125   // Does this have to be in the CellScanner Interface?  TODO
126   public void resetToBeforeFirstEntry() {
127     beforeFirst = true;
128     afterLast = false;
129     rowNodeStackIndex = -1;
130     currentRowNode = null;
131     rowLength = 0;
132     familyOffset = familyBuffer.length;
133     familyLength = 0;
134     qualifierOffset = blockMeta.getMaxQualifierLength();
135     qualifierLength = 0;
136     nubCellsRemain = false;
137     currentCellIndex = -1;
138     timestamp = -1L;
139     type = DEFAULT_TYPE;
140     absoluteValueOffset = 0;//use 0 vs -1 so the cell is valid when value hasn't been initialized
141     valueLength = 0;// had it at -1, but that causes null Cell to add up to the wrong length
142     tagsOffset = blockMeta.getMaxTagsLength();
143     tagsLength = 0;
144   }
145 
146   /**
147    * Call this before putting the scanner back into a pool so it doesn't hold the last used block
148    * in memory.
149    */
150   public void releaseBlockReference(){
151     block = null;
152   }
153 
154 
155   /********************** CellScanner **********************/
156 
157   @Override
158   public Cell current() {
159     if(isOutOfBounds()){
160       return null;
161     }
162     return (Cell)this;
163   }
164 
165   /******************* Object methods ************************/
166 
167   @Override
168   public boolean equals(Object obj) {
169     //trivial override to confirm intent (findbugs)
170     return super.equals(obj);
171   }
172 
173   @Override
174   public int hashCode() {
175     return super.hashCode();
176   }
177 
178   /**
179    * Override PrefixTreeCell.toString() with a check to see if the current cell is valid.
180    */
181   @Override
182   public String toString() {
183     Cell currentCell = current();
184     if(currentCell==null){
185       return "null";
186     }
187     return ((PrefixTreeCell)currentCell).getKeyValueString();
188   }
189 
190 
191   /******************* advance ***************************/
192 
193   public boolean positionAtFirstCell() {
194     reInitFirstNode();
195     return advance();
196   }
197 
198   @Override
199   public boolean advance() {
200     if (afterLast) {
201       return false;
202     }
203     if (!hasOccurrences()) {
204       resetToBeforeFirstEntry();
205     }
206     if (beforeFirst || isLastCellInRow()) {
207       nextRow();
208       if (afterLast) {
209         return false;
210       }
211     } else {
212       ++currentCellIndex;
213     }
214 
215     populateNonRowFields(currentCellIndex);
216     return true;
217   }
218 
219 
220   public boolean nextRow() {
221     nextRowInternal();
222     if (afterLast) {
223       return false;
224     }
225     populateNonRowFields(currentCellIndex);
226     return true;
227   }
228 
229 
230   /**
231    * This method is safe to call when the scanner is not on a fully valid row node, as in the case
232    * of a row token miss in the Searcher
233    * @return true if we are positioned on a valid row, false if past end of block
234    */
235   protected boolean nextRowInternal() {
236     if (afterLast) {
237       return false;
238     }
239     if (beforeFirst) {
240       initFirstNode();
241       if (currentRowNode.hasOccurrences()) {
242         if (currentRowNode.isNub()) {
243           nubCellsRemain = true;
244         }
245         currentCellIndex = 0;
246         return true;
247       }
248     }
249     if (currentRowNode.isLeaf()) {
250       discardCurrentRowNode(true);
251     }
252     while (!afterLast) {
253       if (nubCellsRemain) {
254         nubCellsRemain = false;
255       }
256       if (currentRowNode.hasMoreFanNodes()) {
257         followNextFan();
258         if (currentRowNode.hasOccurrences()) {
259           // found some values
260           currentCellIndex = 0;
261           return true;
262         }
263       } else {
264         if (movedToPrevious && currentRowNode.hasOccurrences()
265             && currentRowNode.getFanIndex() == getNextFanIndex()) {
266           followFan(getNextFanIndex());
267         } else {
268           discardCurrentRowNode(true);
269         }
270       }
271     }
272     return false;// went past the end
273   }
274 
275 
276   /**************** secondary traversal methods ******************************/
277 
278   protected void reInitFirstNode() {
279     resetToBeforeFirstEntry();
280     initFirstNode();
281   }
282 
283   protected void initFirstNode() {
284     int offsetIntoUnderlyingStructure = blockMeta.getAbsoluteRowOffset();
285     rowNodeStackIndex = 0;
286     currentRowNode = rowNodes[0];
287     currentRowNode.initOnBlock(blockMeta, block, offsetIntoUnderlyingStructure);
288     appendCurrentTokenToRowBuffer();
289     beforeFirst = false;
290   }
291 
292   protected void followFirstFan() {
293     followFan(0);
294   }
295 
296   protected void followPreviousFan() {
297     int nextFanPosition = currentRowNode.getFanIndex() - 1;
298     followFan(nextFanPosition);
299   }
300 
301   protected void followCurrentFan() {
302     int currentFanPosition = currentRowNode.getFanIndex();
303     followFan(currentFanPosition);
304   }
305 
306   protected int getNextFanIndex() {
307     return rowNodes[rowNodeStackIndex + 1].getFanIndex();
308   }
309 
310   protected void followNextFan() {
311     int nextFanPosition = currentRowNode.getFanIndex() + 1;
312     followFan(nextFanPosition);
313   }
314 
315   protected void followLastFan() {
316     followFan(currentRowNode.getLastFanIndex());
317   }
318 
319   protected void followFan(int fanIndex) {
320     currentRowNode.setFanIndex(fanIndex);
321     appendToRowBuffer(currentRowNode.getFanByte(fanIndex));
322 
323     int nextOffsetIntoUnderlyingStructure = currentRowNode.getOffset()
324         + currentRowNode.getNextNodeOffset(fanIndex, blockMeta);
325     ++rowNodeStackIndex;
326 
327     currentRowNode = rowNodes[rowNodeStackIndex];
328     currentRowNode.initOnBlock(blockMeta, block, nextOffsetIntoUnderlyingStructure);
329 
330     //TODO getToken is spewing garbage
331     appendCurrentTokenToRowBuffer();
332     if (currentRowNode.isNub()) {
333       nubCellsRemain = true;
334     }
335     currentCellIndex = 0;
336   }
337 
338   /**
339    * @param forwards which marker to set if we overflow
340    */
341   protected void discardCurrentRowNode(boolean forwards) {
342     RowNodeReader rowNodeBeingPopped = currentRowNode;
343     --rowNodeStackIndex;// pop it off the stack
344     if (rowNodeStackIndex < 0) {
345       currentRowNode = null;
346       if (forwards) {
347         markAfterLast();
348       } else {
349         markBeforeFirst();
350       }
351       return;
352     }
353     popFromRowBuffer(rowNodeBeingPopped);
354     currentRowNode = rowNodes[rowNodeStackIndex];
355   }
356 
357   protected void markBeforeFirst() {
358     beforeFirst = true;
359     afterLast = false;
360     currentRowNode = null;
361   }
362 
363   protected void markAfterLast() {
364     beforeFirst = false;
365     afterLast = true;
366     currentRowNode = null;
367   }
368 
369 
370   /***************** helper methods **************************/
371 
372   protected void appendCurrentTokenToRowBuffer() {
373     System.arraycopy(block, currentRowNode.getTokenArrayOffset(), rowBuffer, rowLength,
374       currentRowNode.getTokenLength());
375     rowLength += currentRowNode.getTokenLength();
376   }
377 
378   protected void appendToRowBuffer(byte b) {
379     rowBuffer[rowLength] = b;
380     ++rowLength;
381   }
382 
383   protected void popFromRowBuffer(RowNodeReader rowNodeBeingPopped) {
384     rowLength -= rowNodeBeingPopped.getTokenLength();
385     --rowLength; // pop the parent's fan byte
386   }
387 
388   protected boolean hasOccurrences() {
389     return currentRowNode != null && currentRowNode.hasOccurrences();
390   }
391 
392   protected boolean isBranch() {
393     return currentRowNode != null && !currentRowNode.hasOccurrences()
394         && currentRowNode.hasChildren();
395   }
396 
397   protected boolean isNub() {
398     return currentRowNode != null && currentRowNode.hasOccurrences()
399         && currentRowNode.hasChildren();
400   }
401 
402   protected boolean isLeaf() {
403     return currentRowNode != null && currentRowNode.hasOccurrences()
404         && !currentRowNode.hasChildren();
405   }
406 
407   //TODO expose this in a PrefixTreeScanner interface
408   public boolean isBeforeFirst(){
409     return beforeFirst;
410   }
411 
412   public boolean isAfterLast(){
413     return afterLast;
414   }
415 
416   protected boolean isOutOfBounds(){
417     return beforeFirst || afterLast;
418   }
419 
420   protected boolean isFirstCellInRow() {
421     return currentCellIndex == 0;
422   }
423 
424   protected boolean isLastCellInRow() {
425     return currentCellIndex == currentRowNode.getLastCellIndex();
426   }
427 
428 
429   /********************* fill in family/qualifier/ts/type/value ************/
430 
431   protected int populateNonRowFieldsAndCompareTo(int cellNum, Cell key) {
432     populateNonRowFields(cellNum);
433     return CellComparator.compare(this, key, true);
434   }
435 
436   protected void populateFirstNonRowFields() {
437     populateNonRowFields(0);
438   }
439 
440   protected void populatePreviousNonRowFields() {
441     populateNonRowFields(currentCellIndex - 1);
442   }
443 
444   protected void populateLastNonRowFields() {
445     populateNonRowFields(currentRowNode.getLastCellIndex());
446   }
447 
448   protected void populateNonRowFields(int cellIndex) {
449     currentCellIndex = cellIndex;
450     populateFamily();
451     populateQualifier();
452     // Read tags only if there are tags in the meta
453     if(blockMeta.getNumTagsBytes() != 0) {
454       populateTag();
455     }
456     populateTimestamp();
457     populateMvccVersion();
458     populateType();
459     populateValueOffsets();
460   }
461 
462   protected void populateFamily() {
463     int familyTreeIndex = currentRowNode.getFamilyOffset(currentCellIndex, blockMeta);
464     familyOffset = familyReader.populateBuffer(familyTreeIndex).getColumnOffset();
465     familyLength = familyReader.getColumnLength();
466   }
467 
468   protected void populateQualifier() {
469     int qualifierTreeIndex = currentRowNode.getColumnOffset(currentCellIndex, blockMeta);
470     qualifierOffset = qualifierReader.populateBuffer(qualifierTreeIndex).getColumnOffset();
471     qualifierLength = qualifierReader.getColumnLength();
472   }
473 
474   protected void populateTag() {
475     int tagTreeIndex = currentRowNode.getTagOffset(currentCellIndex, blockMeta);
476     tagsOffset = tagsReader.populateBuffer(tagTreeIndex).getColumnOffset();
477     tagsLength = tagsReader.getColumnLength();
478   }
479 
480   protected void populateTimestamp() {
481     if (blockMeta.isAllSameTimestamp()) {
482       timestamp = blockMeta.getMinTimestamp();
483     } else {
484       int timestampIndex = currentRowNode.getTimestampIndex(currentCellIndex, blockMeta);
485       timestamp = timestampDecoder.getLong(timestampIndex);
486     }
487   }
488 
489   protected void populateMvccVersion() {
490     if (blockMeta.isAllSameMvccVersion()) {
491       mvccVersion = blockMeta.getMinMvccVersion();
492     } else {
493       int mvccVersionIndex = currentRowNode.getMvccVersionIndex(currentCellIndex,
494         blockMeta);
495       mvccVersion = mvccVersionDecoder.getMvccVersion(mvccVersionIndex);
496     }
497   }
498 
499   protected void populateType() {
500     int typeInt;
501     if (blockMeta.isAllSameType()) {
502       typeInt = blockMeta.getAllTypes();
503     } else {
504       typeInt = currentRowNode.getType(currentCellIndex, blockMeta);
505     }
506     type = PrefixTreeCell.TYPES[typeInt];
507   }
508 
509   protected void populateValueOffsets() {
510     int offsetIntoValueSection = currentRowNode.getValueOffset(currentCellIndex, blockMeta);
511     absoluteValueOffset = blockMeta.getAbsoluteValueOffset() + offsetIntoValueSection;
512     valueLength = currentRowNode.getValueLength(currentCellIndex, blockMeta);
513   }
514 
515   /**************** getters ***************************/
516 
517   public byte[] getTreeBytes() {
518     return block;
519   }
520 
521   public PrefixTreeBlockMeta getBlockMeta() {
522     return blockMeta;
523   }
524 
525   public int getMaxRowTreeStackNodes() {
526     return rowNodes.length;
527   }
528 
529   public int getRowBufferLength() {
530     return rowBuffer.length;
531   }
532 
533   public int getQualifierBufferLength() {
534     return qualifierBuffer.length;
535   }
536 
537   public int getTagBufferLength() {
538     return tagsBuffer.length;
539   }
540 
541   public void setMovedToPreviousAsPartOfSeek(boolean movedToPrevious) {
542     this.movedToPrevious = movedToPrevious;
543   }
544 
545   public boolean hasMovedToPreviousAsPartOfSeek() {
546     return this.movedToPrevious;
547   }
548 
549 }