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