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  import org.apache.hadoop.hbase.util.Bytes;
32  
33  /**
34   * Extends PtCell and manipulates its protected fields.  Could alternatively contain a PtCell and
35   * call get/set methods.
36   *
37   * This is an "Array" scanner to distinguish from a future "ByteBuffer" scanner.  This
38   * implementation requires that the bytes be in a normal java byte[] for performance.  The
39   * alternative ByteBuffer implementation would allow for accessing data in an off-heap ByteBuffer
40   * without copying the whole buffer on-heap.
41   */
42  @InterfaceAudience.Private
43  public class PrefixTreeArrayScanner extends PrefixTreeCell implements CellScanner {
44  
45    /***************** fields ********************************/
46  
47    protected PrefixTreeBlockMeta blockMeta;
48  
49    protected boolean beforeFirst;
50    protected boolean afterLast;
51  
52    protected RowNodeReader[] rowNodes;
53    protected int rowNodeStackIndex;
54  
55    protected RowNodeReader currentRowNode;
56    protected ColumnReader familyReader;
57    protected ColumnReader qualifierReader;
58    protected ColumnReader tagsReader;
59    protected TimestampDecoder timestampDecoder;
60    protected MvccVersionDecoder mvccVersionDecoder;
61  
62    protected boolean nubCellsRemain;
63    protected int currentCellIndex;
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           currentCellIndex = 0;
260           return true;
261         }// found some values
262       } else {
263         discardCurrentRowNode(true);
264       }
265     }
266     return false;// went past the end
267   }
268 
269 
270   /**************** secondary traversal methods ******************************/
271 
272   protected void reInitFirstNode() {
273     resetToBeforeFirstEntry();
274     initFirstNode();
275   }
276 
277   protected void initFirstNode() {
278     int offsetIntoUnderlyingStructure = blockMeta.getAbsoluteRowOffset();
279     rowNodeStackIndex = 0;
280     currentRowNode = rowNodes[0];
281     currentRowNode.initOnBlock(blockMeta, block, offsetIntoUnderlyingStructure);
282     appendCurrentTokenToRowBuffer();
283     beforeFirst = false;
284   }
285 
286   protected void followFirstFan() {
287     followFan(0);
288   }
289 
290   protected void followPreviousFan() {
291     int nextFanPosition = currentRowNode.getFanIndex() - 1;
292     followFan(nextFanPosition);
293   }
294 
295   protected void followCurrentFan() {
296     int currentFanPosition = currentRowNode.getFanIndex();
297     followFan(currentFanPosition);
298   }
299 
300   protected void followNextFan() {
301     int nextFanPosition = currentRowNode.getFanIndex() + 1;
302     followFan(nextFanPosition);
303   }
304 
305   protected void followLastFan() {
306     followFan(currentRowNode.getLastFanIndex());
307   }
308 
309   protected void followFan(int fanIndex) {
310     currentRowNode.setFanIndex(fanIndex);
311     appendToRowBuffer(currentRowNode.getFanByte(fanIndex));
312 
313     int nextOffsetIntoUnderlyingStructure = currentRowNode.getOffset()
314         + currentRowNode.getNextNodeOffset(fanIndex, blockMeta);
315     ++rowNodeStackIndex;
316 
317     currentRowNode = rowNodes[rowNodeStackIndex];
318     currentRowNode.initOnBlock(blockMeta, block, nextOffsetIntoUnderlyingStructure);
319 
320     //TODO getToken is spewing garbage
321     appendCurrentTokenToRowBuffer();
322     if (currentRowNode.isNub()) {
323       nubCellsRemain = true;
324     }
325     currentCellIndex = 0;
326   }
327 
328   /**
329    * @param forwards which marker to set if we overflow
330    */
331   protected void discardCurrentRowNode(boolean forwards) {
332     RowNodeReader rowNodeBeingPopped = currentRowNode;
333     --rowNodeStackIndex;// pop it off the stack
334     if (rowNodeStackIndex < 0) {
335       currentRowNode = null;
336       if (forwards) {
337         markAfterLast();
338       } else {
339         markBeforeFirst();
340       }
341       return;
342     }
343     popFromRowBuffer(rowNodeBeingPopped);
344     currentRowNode = rowNodes[rowNodeStackIndex];
345   }
346 
347   protected void markBeforeFirst() {
348     beforeFirst = true;
349     afterLast = false;
350     currentRowNode = null;
351   }
352 
353   protected void markAfterLast() {
354     beforeFirst = false;
355     afterLast = true;
356     currentRowNode = null;
357   }
358 
359 
360   /***************** helper methods **************************/
361 
362   protected void appendCurrentTokenToRowBuffer() {
363     System.arraycopy(block, currentRowNode.getTokenArrayOffset(), rowBuffer, rowLength, 
364       currentRowNode.getTokenLength());
365     rowLength += currentRowNode.getTokenLength();
366   }
367 
368   protected void appendToRowBuffer(byte b) {
369     rowBuffer[rowLength] = b;
370     ++rowLength;
371   }
372 
373   protected void popFromRowBuffer(RowNodeReader rowNodeBeingPopped) {
374     rowLength -= rowNodeBeingPopped.getTokenLength();
375     --rowLength; // pop the parent's fan byte
376   }
377 
378   protected boolean hasOccurrences() {
379     return currentRowNode != null && currentRowNode.hasOccurrences();
380   }
381 
382   protected boolean isBranch() {
383     return currentRowNode != null && !currentRowNode.hasOccurrences()
384         && currentRowNode.hasChildren();
385   }
386 
387   protected boolean isNub() {
388     return currentRowNode != null && currentRowNode.hasOccurrences()
389         && currentRowNode.hasChildren();
390   }
391 
392   protected boolean isLeaf() {
393     return currentRowNode != null && currentRowNode.hasOccurrences()
394         && !currentRowNode.hasChildren();
395   }
396 
397   //TODO expose this in a PrefixTreeScanner interface
398   public boolean isBeforeFirst(){
399     return beforeFirst;
400   }
401 
402   public boolean isAfterLast(){
403     return afterLast;
404   }
405 
406   protected boolean isOutOfBounds(){
407     return beforeFirst || afterLast;
408   }
409 
410   protected boolean isFirstCellInRow() {
411     return currentCellIndex == 0;
412   }
413 
414   protected boolean isLastCellInRow() {
415     return currentCellIndex == currentRowNode.getLastCellIndex();
416   }
417 
418 
419   /********************* fill in family/qualifier/ts/type/value ************/
420 
421   protected int populateNonRowFieldsAndCompareTo(int cellNum, Cell key) {
422     populateNonRowFields(cellNum);
423     return CellComparator.compareStatic(this, key);
424   }
425 
426   protected void populateFirstNonRowFields() {
427     populateNonRowFields(0);
428   }
429 
430   protected void populatePreviousNonRowFields() {
431     populateNonRowFields(currentCellIndex - 1);
432   }
433 
434   protected void populateLastNonRowFields() {
435     populateNonRowFields(currentRowNode.getLastCellIndex());
436   }
437 
438   protected void populateNonRowFields(int cellIndex) {
439     currentCellIndex = cellIndex;
440     populateFamily();
441     populateQualifier();
442     // Read tags only if there are tags in the meta
443     if(blockMeta.getNumTagsBytes() != 0) {
444       populateTag();
445     }
446     populateTimestamp();
447     populateMvccVersion();
448     populateType();
449     populateValueOffsets();
450   }
451 
452   protected void populateFamily() {
453     int familyTreeIndex = currentRowNode.getFamilyOffset(currentCellIndex, blockMeta);
454     familyOffset = familyReader.populateBuffer(familyTreeIndex).getColumnOffset();
455     familyLength = familyReader.getColumnLength();
456   }
457 
458   protected void populateQualifier() {
459     int qualifierTreeIndex = currentRowNode.getColumnOffset(currentCellIndex, blockMeta);
460     qualifierOffset = qualifierReader.populateBuffer(qualifierTreeIndex).getColumnOffset();
461     qualifierLength = qualifierReader.getColumnLength();
462   }
463 
464   protected void populateTag() {
465     int tagTreeIndex = currentRowNode.getTagOffset(currentCellIndex, blockMeta);
466     tagsOffset = tagsReader.populateBuffer(tagTreeIndex).getColumnOffset();
467     tagsLength = (short)tagsReader.getColumnLength();
468   }
469 
470   protected void populateTimestamp() {
471     if (blockMeta.isAllSameTimestamp()) {
472       timestamp = blockMeta.getMinTimestamp();
473     } else {
474       int timestampIndex = currentRowNode.getTimestampIndex(currentCellIndex, blockMeta);
475       timestamp = timestampDecoder.getLong(timestampIndex);
476     }
477   }
478 
479   protected void populateMvccVersion() {
480     if (blockMeta.isAllSameMvccVersion()) {
481       mvccVersion = blockMeta.getMinMvccVersion();
482     } else {
483       int mvccVersionIndex = currentRowNode.getMvccVersionIndex(currentCellIndex,
484         blockMeta);
485       mvccVersion = mvccVersionDecoder.getMvccVersion(mvccVersionIndex);
486     }
487   }
488 
489   protected void populateType() {
490     int typeInt;
491     if (blockMeta.isAllSameType()) {
492       typeInt = blockMeta.getAllTypes();
493     } else {
494       typeInt = currentRowNode.getType(currentCellIndex, blockMeta);
495     }
496     type = PrefixTreeCell.TYPES[typeInt];
497   }
498 
499   protected void populateValueOffsets() {
500     int offsetIntoValueSection = currentRowNode.getValueOffset(currentCellIndex, blockMeta);
501     absoluteValueOffset = blockMeta.getAbsoluteValueOffset() + offsetIntoValueSection;
502     valueLength = currentRowNode.getValueLength(currentCellIndex, blockMeta);
503   }
504 
505   /**************** getters ***************************/
506 
507   public byte[] getTreeBytes() {
508     return block;
509   }
510 
511   public PrefixTreeBlockMeta getBlockMeta() {
512     return blockMeta;
513   }
514 
515   public int getMaxRowTreeStackNodes() {
516     return rowNodes.length;
517   }
518 
519   public int getRowBufferLength() {
520     return rowBuffer.length;
521   }
522 
523   public int getQualifierBufferLength() {
524     return qualifierBuffer.length;
525   }
526 
527   public int getTagBufferLength() {
528     return tagsBuffer.length;
529   }
530 
531 }