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  import org.apache.hadoop.hbase.nio.ByteBuff;
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    /*********************** construct ******************************/
65  
66    // pass in blockMeta so we can initialize buffers big enough for all cells in the block
67    public PrefixTreeArrayScanner(PrefixTreeBlockMeta blockMeta, int rowTreeDepth,
68        int rowBufferLength, int qualifierBufferLength, int tagsBufferLength) {
69      this.rowNodes = new RowNodeReader[rowTreeDepth];
70      for (int i = 0; i < rowNodes.length; ++i) {
71        rowNodes[i] = new RowNodeReader();
72      }
73      this.rowBuffer = new byte[rowBufferLength];
74      this.familyBuffer = new byte[PrefixTreeBlockMeta.MAX_FAMILY_LENGTH];
75      this.familyReader = new ColumnReader(familyBuffer, ColumnNodeType.FAMILY);
76      this.qualifierBuffer = new byte[qualifierBufferLength];
77      this.tagsBuffer = new byte[tagsBufferLength];
78      this.qualifierReader = new ColumnReader(qualifierBuffer, ColumnNodeType.QUALIFIER);
79      this.tagsReader = new ColumnReader(tagsBuffer, ColumnNodeType.TAGS);
80      this.timestampDecoder = new TimestampDecoder();
81      this.mvccVersionDecoder = new MvccVersionDecoder();
82    }
83  
84  
85    /**************** init helpers ***************************************/
86  
87    /**
88     * Call when first accessing a block.
89     * @return entirely new scanner if false
90     */
91    public boolean areBuffersBigEnough() {
92      if (rowNodes.length < blockMeta.getRowTreeDepth()) {
93        return false;
94      }
95      if (rowBuffer.length < blockMeta.getMaxRowLength()) {
96        return false;
97      }
98      if (qualifierBuffer.length < blockMeta.getMaxQualifierLength()) {
99        return false;
100     }
101     if(tagsBuffer.length < blockMeta.getMaxTagsLength()) {
102       return false;
103     }
104     return true;
105   }
106 
107   public void initOnBlock(PrefixTreeBlockMeta blockMeta, ByteBuff block,
108       boolean includeMvccVersion) {
109     this.block = block;
110     this.blockMeta = blockMeta;
111     this.familyOffset = familyBuffer.length;
112     this.familyReader.initOnBlock(blockMeta, block);
113     this.qualifierOffset = qualifierBuffer.length;
114     this.qualifierReader.initOnBlock(blockMeta, block);
115     this.tagsOffset = tagsBuffer.length;
116     this.tagsReader.initOnBlock(blockMeta, block);
117     this.timestampDecoder.initOnBlock(blockMeta, block);
118     this.mvccVersionDecoder.initOnBlock(blockMeta, block);
119     this.includeMvccVersion = includeMvccVersion;
120     resetToBeforeFirstEntry();
121   }
122 
123   // Does this have to be in the CellScanner Interface?  TODO
124   public void resetToBeforeFirstEntry() {
125     beforeFirst = true;
126     afterLast = false;
127     rowNodeStackIndex = -1;
128     currentRowNode = null;
129     rowLength = 0;
130     familyOffset = familyBuffer.length;
131     familyLength = 0;
132     qualifierOffset = blockMeta.getMaxQualifierLength();
133     qualifierLength = 0;
134     nubCellsRemain = false;
135     currentCellIndex = -1;
136     timestamp = -1L;
137     type = DEFAULT_TYPE;
138     absoluteValueOffset = 0;//use 0 vs -1 so the cell is valid when value hasn't been initialized
139     valueLength = 0;// had it at -1, but that causes null Cell to add up to the wrong length
140     tagsOffset = blockMeta.getMaxTagsLength();
141     tagsLength = 0;
142   }
143 
144   /**
145    * Call this before putting the scanner back into a pool so it doesn't hold the last used block
146    * in memory.
147    */
148   public void releaseBlockReference(){
149     block = null;
150   }
151 
152 
153   /********************** CellScanner **********************/
154 
155   @Override
156   public Cell current() {
157     if(isOutOfBounds()){
158       return null;
159     }
160     return (Cell)this;
161   }
162 
163   /******************* Object methods ************************/
164 
165   @Override
166   public boolean equals(Object obj) {
167     //trivial override to confirm intent (findbugs)
168     return super.equals(obj);
169   }
170 
171   @Override
172   public int hashCode() {
173     return super.hashCode();
174   }
175 
176   /**
177    * Override PrefixTreeCell.toString() with a check to see if the current cell is valid.
178    */
179   @Override
180   public String toString() {
181     Cell currentCell = current();
182     if(currentCell==null){
183       return "null";
184     }
185     return ((PrefixTreeCell)currentCell).getKeyValueString();
186   }
187 
188 
189   /******************* advance ***************************/
190 
191   public boolean positionAtFirstCell() {
192     reInitFirstNode();
193     return advance();
194   }
195 
196   @Override
197   public boolean advance() {
198     if (afterLast) {
199       return false;
200     }
201     if (!hasOccurrences()) {
202       resetToBeforeFirstEntry();
203     }
204     if (beforeFirst || isLastCellInRow()) {
205       nextRow();
206       if (afterLast) {
207         return false;
208       }
209     } else {
210       ++currentCellIndex;
211     }
212 
213     populateNonRowFields(currentCellIndex);
214     return true;
215   }
216 
217 
218   public boolean nextRow() {
219     nextRowInternal();
220     if (afterLast) {
221       return false;
222     }
223     populateNonRowFields(currentCellIndex);
224     return true;
225   }
226 
227 
228   /**
229    * This method is safe to call when the scanner is not on a fully valid row node, as in the case
230    * of a row token miss in the Searcher
231    * @return true if we are positioned on a valid row, false if past end of block
232    */
233   protected boolean nextRowInternal() {
234     if (afterLast) {
235       return false;
236     }
237     if (beforeFirst) {
238       initFirstNode();
239       if (currentRowNode.hasOccurrences()) {
240         if (currentRowNode.isNub()) {
241           nubCellsRemain = true;
242         }
243         currentCellIndex = 0;
244         return true;
245       }
246     }
247     if (currentRowNode.isLeaf()) {
248       discardCurrentRowNode(true);
249     }
250     while (!afterLast) {
251       if (nubCellsRemain) {
252         nubCellsRemain = false;
253       }
254       if (currentRowNode.hasMoreFanNodes()) {
255         followNextFan();
256         if (currentRowNode.hasOccurrences()) {
257           // found some values
258           currentCellIndex = 0;
259           return true;
260         }
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     block.get(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 comparator.compareKeyIgnoresMvcc(this, key);
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     this.block.asSubByteBuffer(this.absoluteValueOffset, valueLength, pair);
503   }
504 
505   /**************** getters ***************************/
506 
507   public PrefixTreeBlockMeta getBlockMeta() {
508     return blockMeta;
509   }
510 
511   public int getMaxRowTreeStackNodes() {
512     return rowNodes.length;
513   }
514 
515   public int getRowBufferLength() {
516     return rowBuffer.length;
517   }
518 
519   public int getQualifierBufferLength() {
520     return qualifierBuffer.length;
521   }
522 
523   public int getTagBufferLength() {
524     return tagsBuffer.length;
525   }
526 }