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