001/*
002 * Licensed to the Apache Software Foundation (ASF) under one
003 * or more contributor license agreements.  See the NOTICE file
004 * distributed with this work for additional information
005 * regarding copyright ownership.  The ASF licenses this file
006 * to you under the Apache License, Version 2.0 (the
007 * "License"); you may not use this file except in compliance
008 * with the License.  You may obtain a copy of the License at
009 *
010 *     http://www.apache.org/licenses/LICENSE-2.0
011 *
012 * Unless required by applicable law or agreed to in writing, software
013 * distributed under the License is distributed on an "AS IS" BASIS,
014 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
015 * See the License for the specific language governing permissions and
016 * limitations under the License.
017 */
018package org.apache.hadoop.hbase;
019
020import static org.apache.hadoop.hbase.HConstants.EMPTY_BYTE_ARRAY;
021import static org.apache.hadoop.hbase.Tag.TAG_LENGTH_SIZE;
022
023import java.io.DataOutput;
024import java.io.DataOutputStream;
025import java.io.IOException;
026import java.io.OutputStream;
027import java.math.BigDecimal;
028import java.nio.ByteBuffer;
029import java.util.ArrayList;
030import java.util.Iterator;
031import java.util.List;
032import java.util.Optional;
033import org.apache.hadoop.hbase.filter.ByteArrayComparable;
034import org.apache.hadoop.hbase.io.HeapSize;
035import org.apache.hadoop.hbase.io.TagCompressionContext;
036import org.apache.hadoop.hbase.io.util.Dictionary;
037import org.apache.hadoop.hbase.io.util.StreamUtils;
038import org.apache.hadoop.hbase.util.ByteBufferUtils;
039import org.apache.hadoop.hbase.util.ByteRange;
040import org.apache.hadoop.hbase.util.Bytes;
041import org.apache.hadoop.hbase.util.ClassSize;
042import org.apache.yetus.audience.InterfaceAudience;
043
044import org.apache.hbase.thirdparty.com.google.common.annotations.VisibleForTesting;
045
046/**
047 * Utility methods helpful slinging {@link Cell} instances. It has more powerful and
048 * rich set of APIs than those in {@link CellUtil} for internal usage.
049 */
050@InterfaceAudience.Private
051public final class PrivateCellUtil {
052
053  /**
054   * Private constructor to keep this class from being instantiated.
055   */
056  private PrivateCellUtil() {
057  }
058
059  /******************* ByteRange *******************************/
060
061  public static ByteRange fillRowRange(Cell cell, ByteRange range) {
062    return range.set(cell.getRowArray(), cell.getRowOffset(), cell.getRowLength());
063  }
064
065  public static ByteRange fillFamilyRange(Cell cell, ByteRange range) {
066    return range.set(cell.getFamilyArray(), cell.getFamilyOffset(), cell.getFamilyLength());
067  }
068
069  public static ByteRange fillQualifierRange(Cell cell, ByteRange range) {
070    return range.set(cell.getQualifierArray(), cell.getQualifierOffset(),
071      cell.getQualifierLength());
072  }
073
074  public static ByteRange fillValueRange(Cell cell, ByteRange range) {
075    return range.set(cell.getValueArray(), cell.getValueOffset(), cell.getValueLength());
076  }
077
078  public static ByteRange fillTagRange(Cell cell, ByteRange range) {
079    return range.set(cell.getTagsArray(), cell.getTagsOffset(), cell.getTagsLength());
080  }
081
082  /********************* misc *************************************/
083
084  public static byte getRowByte(Cell cell, int index) {
085    if (cell instanceof ByteBufferExtendedCell) {
086      return ((ByteBufferExtendedCell) cell).getRowByteBuffer()
087          .get(((ByteBufferExtendedCell) cell).getRowPosition() + index);
088    }
089    return cell.getRowArray()[cell.getRowOffset() + index];
090  }
091
092  public static byte getQualifierByte(Cell cell, int index) {
093    if (cell instanceof ByteBufferExtendedCell) {
094      return ((ByteBufferExtendedCell) cell).getQualifierByteBuffer()
095          .get(((ByteBufferExtendedCell) cell).getQualifierPosition() + index);
096    }
097    return cell.getQualifierArray()[cell.getQualifierOffset() + index];
098  }
099
100  public static ByteBuffer getValueBufferShallowCopy(Cell cell) {
101    ByteBuffer buffer =
102        ByteBuffer.wrap(cell.getValueArray(), cell.getValueOffset(), cell.getValueLength());
103    return buffer;
104  }
105
106  /**
107   * @return A new cell which is having the extra tags also added to it.
108   */
109  public static Cell createCell(Cell cell, List<Tag> tags) {
110    return createCell(cell, TagUtil.fromList(tags));
111  }
112
113  /**
114   * @return A new cell which is having the extra tags also added to it.
115   */
116  public static Cell createCell(Cell cell, byte[] tags) {
117    if (cell instanceof ByteBufferExtendedCell) {
118      return new TagRewriteByteBufferExtendedCell((ByteBufferExtendedCell) cell, tags);
119    }
120    return new TagRewriteCell(cell, tags);
121  }
122
123  public static Cell createCell(Cell cell, byte[] value, byte[] tags) {
124    if (cell instanceof ByteBufferExtendedCell) {
125      return new ValueAndTagRewriteByteBufferExtendedCell((ByteBufferExtendedCell) cell,
126          value, tags);
127    }
128    return new ValueAndTagRewriteCell(cell, value, tags);
129  }
130
131  /**
132   * This can be used when a Cell has to change with addition/removal of one or more tags. This is
133   * an efficient way to do so in which only the tags bytes part need to recreated and copied. All
134   * other parts, refer to the original Cell.
135   */
136  static class TagRewriteCell implements ExtendedCell {
137    protected Cell cell;
138    protected byte[] tags;
139    private static final int HEAP_SIZE_OVERHEAD = ClassSize.OBJECT + 2 * ClassSize.REFERENCE;
140
141    /**
142     * @param cell The original Cell which it rewrites
143     * @param tags the tags bytes. The array suppose to contain the tags bytes alone.
144     */
145    public TagRewriteCell(Cell cell, byte[] tags) {
146      assert cell instanceof ExtendedCell;
147      assert tags != null;
148      this.cell = cell;
149      this.tags = tags;
150      // tag offset will be treated as 0 and length this.tags.length
151      if (this.cell instanceof TagRewriteCell) {
152        // Cleaning the ref so that the byte[] can be GCed
153        ((TagRewriteCell) this.cell).tags = null;
154      }
155    }
156
157    @Override
158    public byte[] getRowArray() {
159      return cell.getRowArray();
160    }
161
162    @Override
163    public int getRowOffset() {
164      return cell.getRowOffset();
165    }
166
167    @Override
168    public short getRowLength() {
169      return cell.getRowLength();
170    }
171
172    @Override
173    public byte[] getFamilyArray() {
174      return cell.getFamilyArray();
175    }
176
177    @Override
178    public int getFamilyOffset() {
179      return cell.getFamilyOffset();
180    }
181
182    @Override
183    public byte getFamilyLength() {
184      return cell.getFamilyLength();
185    }
186
187    @Override
188    public byte[] getQualifierArray() {
189      return cell.getQualifierArray();
190    }
191
192    @Override
193    public int getQualifierOffset() {
194      return cell.getQualifierOffset();
195    }
196
197    @Override
198    public int getQualifierLength() {
199      return cell.getQualifierLength();
200    }
201
202    @Override
203    public long getTimestamp() {
204      return cell.getTimestamp();
205    }
206
207    @Override
208    public byte getTypeByte() {
209      return cell.getTypeByte();
210    }
211
212    @Override
213    public long getSequenceId() {
214      return cell.getSequenceId();
215    }
216
217    @Override
218    public byte[] getValueArray() {
219      return cell.getValueArray();
220    }
221
222    @Override
223    public int getValueOffset() {
224      return cell.getValueOffset();
225    }
226
227    @Override
228    public int getValueLength() {
229      return cell.getValueLength();
230    }
231
232    @Override
233    public byte[] getTagsArray() {
234      return this.tags;
235    }
236
237    @Override
238    public int getTagsOffset() {
239      return 0;
240    }
241
242    @Override
243    public int getTagsLength() {
244      if (null == this.tags) {
245        // Nulled out tags array optimization in constructor
246        return 0;
247      }
248      return this.tags.length;
249    }
250
251    @Override
252    public long heapSize() {
253      long sum = HEAP_SIZE_OVERHEAD + estimatedSizeOfCell(cell);
254      if (this.tags != null) {
255        sum += ClassSize.sizeOf(this.tags);
256      }
257      return sum;
258    }
259
260    @Override
261    public void setTimestamp(long ts) throws IOException {
262      // The incoming cell is supposed to be ExtendedCell type.
263      PrivateCellUtil.setTimestamp(cell, ts);
264    }
265
266    @Override
267    public void setTimestamp(byte[] ts) throws IOException {
268      // The incoming cell is supposed to be ExtendedCell type.
269      PrivateCellUtil.setTimestamp(cell, ts);
270    }
271
272    @Override
273    public void setSequenceId(long seqId) throws IOException {
274      // The incoming cell is supposed to be ExtendedCell type.
275      PrivateCellUtil.setSequenceId(cell, seqId);
276    }
277
278    @Override
279    public int write(OutputStream out, boolean withTags) throws IOException {
280      int len = ((ExtendedCell) this.cell).write(out, false);
281      if (withTags && this.tags != null) {
282        // Write the tagsLength 2 bytes
283        out.write((byte) (0xff & (this.tags.length >> 8)));
284        out.write((byte) (0xff & this.tags.length));
285        out.write(this.tags);
286        len += KeyValue.TAGS_LENGTH_SIZE + this.tags.length;
287      }
288      return len;
289    }
290
291    @Override
292    public int getSerializedSize(boolean withTags) {
293      int len = ((ExtendedCell) this.cell).getSerializedSize(false);
294      if (withTags && this.tags != null) {
295        len += KeyValue.TAGS_LENGTH_SIZE + this.tags.length;
296      }
297      return len;
298    }
299
300    @Override
301    public void write(ByteBuffer buf, int offset) {
302      offset = KeyValueUtil.appendTo(this.cell, buf, offset, false);
303      int tagsLen = this.tags == null ? 0 : this.tags.length;
304      if (tagsLen > 0) {
305        offset = ByteBufferUtils.putAsShort(buf, offset, tagsLen);
306        ByteBufferUtils.copyFromArrayToBuffer(buf, offset, this.tags, 0, tagsLen);
307      }
308    }
309
310    @Override
311    public ExtendedCell deepClone() {
312      Cell clonedBaseCell = ((ExtendedCell) this.cell).deepClone();
313      return new TagRewriteCell(clonedBaseCell, this.tags);
314    }
315  }
316
317  static class TagRewriteByteBufferExtendedCell extends ByteBufferExtendedCell {
318
319    protected ByteBufferExtendedCell cell;
320    protected byte[] tags;
321    private static final int HEAP_SIZE_OVERHEAD = ClassSize.OBJECT + 2 * ClassSize.REFERENCE;
322
323    /**
324     * @param cell The original ByteBufferExtendedCell which it rewrites
325     * @param tags the tags bytes. The array suppose to contain the tags bytes alone.
326     */
327    public TagRewriteByteBufferExtendedCell(ByteBufferExtendedCell cell, byte[] tags) {
328      assert tags != null;
329      this.cell = cell;
330      this.tags = tags;
331      // tag offset will be treated as 0 and length this.tags.length
332      if (this.cell instanceof TagRewriteByteBufferExtendedCell) {
333        // Cleaning the ref so that the byte[] can be GCed
334        ((TagRewriteByteBufferExtendedCell) this.cell).tags = null;
335      }
336    }
337
338    @Override
339    public byte[] getRowArray() {
340      return this.cell.getRowArray();
341    }
342
343    @Override
344    public int getRowOffset() {
345      return this.cell.getRowOffset();
346    }
347
348    @Override
349    public short getRowLength() {
350      return this.cell.getRowLength();
351    }
352
353    @Override
354    public byte[] getFamilyArray() {
355      return this.cell.getFamilyArray();
356    }
357
358    @Override
359    public int getFamilyOffset() {
360      return this.cell.getFamilyOffset();
361    }
362
363    @Override
364    public byte getFamilyLength() {
365      return this.cell.getFamilyLength();
366    }
367
368    @Override
369    public byte[] getQualifierArray() {
370      return this.cell.getQualifierArray();
371    }
372
373    @Override
374    public int getQualifierOffset() {
375      return this.cell.getQualifierOffset();
376    }
377
378    @Override
379    public int getQualifierLength() {
380      return this.cell.getQualifierLength();
381    }
382
383    @Override
384    public long getTimestamp() {
385      return this.cell.getTimestamp();
386    }
387
388    @Override
389    public byte getTypeByte() {
390      return this.cell.getTypeByte();
391    }
392
393    @Override
394    public long getSequenceId() {
395      return this.cell.getSequenceId();
396    }
397
398    @Override
399    public byte[] getValueArray() {
400      return this.cell.getValueArray();
401    }
402
403    @Override
404    public int getValueOffset() {
405      return this.cell.getValueOffset();
406    }
407
408    @Override
409    public int getValueLength() {
410      return this.cell.getValueLength();
411    }
412
413    @Override
414    public byte[] getTagsArray() {
415      return this.tags;
416    }
417
418    @Override
419    public int getTagsOffset() {
420      return 0;
421    }
422
423    @Override
424    public int getTagsLength() {
425      if (null == this.tags) {
426        // Nulled out tags array optimization in constructor
427        return 0;
428      }
429      return this.tags.length;
430    }
431
432    @Override
433    public void setSequenceId(long seqId) throws IOException {
434      PrivateCellUtil.setSequenceId(this.cell, seqId);
435    }
436
437    @Override
438    public void setTimestamp(long ts) throws IOException {
439      PrivateCellUtil.setTimestamp(this.cell, ts);
440    }
441
442    @Override
443    public void setTimestamp(byte[] ts) throws IOException {
444      PrivateCellUtil.setTimestamp(this.cell, ts);
445    }
446
447    @Override
448    public long heapSize() {
449      long sum = HEAP_SIZE_OVERHEAD + estimatedSizeOfCell(cell);
450      // this.tags is on heap byte[]
451      if (this.tags != null) {
452        sum += ClassSize.sizeOf(this.tags);
453      }
454      return sum;
455    }
456
457    @Override
458    public int write(OutputStream out, boolean withTags) throws IOException {
459      int len = ((ExtendedCell) this.cell).write(out, false);
460      if (withTags && this.tags != null) {
461        // Write the tagsLength 2 bytes
462        out.write((byte) (0xff & (this.tags.length >> 8)));
463        out.write((byte) (0xff & this.tags.length));
464        out.write(this.tags);
465        len += KeyValue.TAGS_LENGTH_SIZE + this.tags.length;
466      }
467      return len;
468    }
469
470    @Override
471    public int getSerializedSize(boolean withTags) {
472      int len = ((ExtendedCell) this.cell).getSerializedSize(false);
473      if (withTags && this.tags != null) {
474        len += KeyValue.TAGS_LENGTH_SIZE + this.tags.length;
475      }
476      return len;
477    }
478
479    @Override
480    public void write(ByteBuffer buf, int offset) {
481      offset = KeyValueUtil.appendTo(this.cell, buf, offset, false);
482      int tagsLen = this.tags == null ? 0 : this.tags.length;
483      if (tagsLen > 0) {
484        offset = ByteBufferUtils.putAsShort(buf, offset, tagsLen);
485        ByteBufferUtils.copyFromArrayToBuffer(buf, offset, this.tags, 0, tagsLen);
486      }
487    }
488
489    @Override
490    public ExtendedCell deepClone() {
491      Cell clonedBaseCell = ((ExtendedCell) this.cell).deepClone();
492      if (clonedBaseCell instanceof ByteBufferExtendedCell) {
493        return new TagRewriteByteBufferExtendedCell((ByteBufferExtendedCell) clonedBaseCell,
494            this.tags);
495      }
496      return new TagRewriteCell(clonedBaseCell, this.tags);
497    }
498
499    @Override
500    public ByteBuffer getRowByteBuffer() {
501      return this.cell.getRowByteBuffer();
502    }
503
504    @Override
505    public int getRowPosition() {
506      return this.cell.getRowPosition();
507    }
508
509    @Override
510    public ByteBuffer getFamilyByteBuffer() {
511      return this.cell.getFamilyByteBuffer();
512    }
513
514    @Override
515    public int getFamilyPosition() {
516      return this.cell.getFamilyPosition();
517    }
518
519    @Override
520    public ByteBuffer getQualifierByteBuffer() {
521      return this.cell.getQualifierByteBuffer();
522    }
523
524    @Override
525    public int getQualifierPosition() {
526      return this.cell.getQualifierPosition();
527    }
528
529    @Override
530    public ByteBuffer getValueByteBuffer() {
531      return this.cell.getValueByteBuffer();
532    }
533
534    @Override
535    public int getValuePosition() {
536      return this.cell.getValuePosition();
537    }
538
539    @Override
540    public ByteBuffer getTagsByteBuffer() {
541      return this.tags == null ? HConstants.EMPTY_BYTE_BUFFER : ByteBuffer.wrap(this.tags);
542    }
543
544    @Override
545    public int getTagsPosition() {
546      return 0;
547    }
548  }
549
550  static class ValueAndTagRewriteCell extends TagRewriteCell {
551
552    protected byte[] value;
553
554    public ValueAndTagRewriteCell(Cell cell, byte[] value, byte[] tags) {
555      super(cell, tags);
556      this.value = value;
557    }
558
559    @Override
560    public byte[] getValueArray() {
561      return this.value;
562    }
563
564    @Override
565    public int getValueOffset() {
566      return 0;
567    }
568
569    @Override
570    public int getValueLength() {
571      return this.value == null ? 0 : this.value.length;
572    }
573
574    @Override
575    public long heapSize() {
576      long sum = ClassSize.REFERENCE + super.heapSize();
577      if (this.value != null) {
578        sum += ClassSize.sizeOf(this.value);
579      }
580      return sum;
581    }
582
583    @Override
584    public int write(OutputStream out, boolean withTags) throws IOException {
585      return write(out, withTags, this.cell, this.value, this.tags);
586    }
587
588    /**
589     * Made into a static method so as to reuse the logic within
590     * ValueAndTagRewriteByteBufferExtendedCell
591     */
592    static int write(OutputStream out, boolean withTags, Cell cell, byte[] value, byte[] tags)
593        throws IOException {
594      int valLen = value == null ? 0 : value.length;
595      ByteBufferUtils.putInt(out, KeyValueUtil.keyLength(cell));// Key length
596      ByteBufferUtils.putInt(out, valLen);// Value length
597      int len = 2 * Bytes.SIZEOF_INT;
598      len += writeFlatKey(cell, out);// Key
599      if (valLen > 0) {
600        out.write(value);// Value
601      }
602      len += valLen;
603      if (withTags && tags != null) {
604        // Write the tagsLength 2 bytes
605        out.write((byte) (0xff & (tags.length >> 8)));
606        out.write((byte) (0xff & tags.length));
607        out.write(tags);
608        len += KeyValue.TAGS_LENGTH_SIZE + tags.length;
609      }
610      return len;
611    }
612
613    @Override
614    public int getSerializedSize(boolean withTags) {
615      return super.getSerializedSize(withTags) - this.cell.getValueLength() + this.value.length;
616    }
617
618    @Override
619    public void write(ByteBuffer buf, int offset) {
620      write(buf, offset, this.cell, this.value, this.tags);
621    }
622
623    /**
624     * Made into a static method so as to reuse the logic
625     * within ValueAndTagRewriteByteBufferExtendedCell
626     */
627    static void write(ByteBuffer buf, int offset, Cell cell, byte[] value, byte[] tags) {
628      offset = ByteBufferUtils.putInt(buf, offset, KeyValueUtil.keyLength(cell));// Key length
629      offset = ByteBufferUtils.putInt(buf, offset, value.length);// Value length
630      offset = KeyValueUtil.appendKeyTo(cell, buf, offset);
631      ByteBufferUtils.copyFromArrayToBuffer(buf, offset, value, 0, value.length);
632      offset += value.length;
633      int tagsLen = tags == null ? 0 : tags.length;
634      if (tagsLen > 0) {
635        offset = ByteBufferUtils.putAsShort(buf, offset, tagsLen);
636        ByteBufferUtils.copyFromArrayToBuffer(buf, offset, tags, 0, tagsLen);
637      }
638    }
639
640    @Override
641    public ExtendedCell deepClone() {
642      Cell clonedBaseCell = ((ExtendedCell) this.cell).deepClone();
643      return new ValueAndTagRewriteCell(clonedBaseCell, this.value, this.tags);
644    }
645  }
646
647  static class ValueAndTagRewriteByteBufferExtendedCell extends TagRewriteByteBufferExtendedCell {
648
649    protected byte[] value;
650
651    public ValueAndTagRewriteByteBufferExtendedCell(ByteBufferExtendedCell cell,
652        byte[] value, byte[] tags) {
653      super(cell, tags);
654      this.value = value;
655    }
656
657    @Override
658    public byte[] getValueArray() {
659      return this.value;
660    }
661
662    @Override
663    public int getValueOffset() {
664      return 0;
665    }
666
667    @Override
668    public int getValueLength() {
669      return this.value == null ? 0 : this.value.length;
670    }
671
672    @Override
673    public ByteBuffer getValueByteBuffer() {
674      return ByteBuffer.wrap(this.value);
675    }
676
677    @Override
678    public int getValuePosition() {
679      return 0;
680    }
681
682    @Override
683    public long heapSize() {
684      long sum = ClassSize.REFERENCE + super.heapSize();
685      if (this.value != null) {
686        sum += ClassSize.sizeOf(this.value);
687      }
688      return sum;
689    }
690
691    @Override
692    public int write(OutputStream out, boolean withTags) throws IOException {
693      return ValueAndTagRewriteCell.write(out, withTags, this.cell, this.value, this.tags);
694    }
695
696    @Override
697    public int getSerializedSize(boolean withTags) {
698      return super.getSerializedSize(withTags) - this.cell.getValueLength() + this.value.length;
699    }
700
701    @Override
702    public void write(ByteBuffer buf, int offset) {
703      ValueAndTagRewriteCell.write(buf, offset, this.cell, this.value, this.tags);
704    }
705
706    @Override
707    public ExtendedCell deepClone() {
708      Cell clonedBaseCell = ((ExtendedCell) this.cell).deepClone();
709      if (clonedBaseCell instanceof ByteBufferExtendedCell) {
710        return new ValueAndTagRewriteByteBufferExtendedCell(
711            (ByteBufferExtendedCell) clonedBaseCell, this.value, this.tags);
712      }
713      return new ValueAndTagRewriteCell(clonedBaseCell, this.value, this.tags);
714    }
715  }
716
717  public static boolean matchingRows(final Cell left, final byte[] buf, final int offset,
718      final int length) {
719    if (left instanceof ByteBufferExtendedCell) {
720      return ByteBufferUtils.equals(((ByteBufferExtendedCell) left).getRowByteBuffer(),
721          ((ByteBufferExtendedCell) left).getRowPosition(), left.getRowLength(),
722          buf, offset, length);
723    }
724    return Bytes.equals(left.getRowArray(), left.getRowOffset(), left.getRowLength(), buf, offset,
725        length);
726  }
727
728  public static boolean matchingFamily(final Cell left, final byte[] buf, final int offset,
729      final int length) {
730    if (left instanceof ByteBufferExtendedCell) {
731      return ByteBufferUtils.equals(((ByteBufferExtendedCell) left).getFamilyByteBuffer(),
732          ((ByteBufferExtendedCell) left).getFamilyPosition(), left.getFamilyLength(),
733          buf, offset, length);
734    }
735    return Bytes.equals(left.getFamilyArray(), left.getFamilyOffset(), left.getFamilyLength(), buf,
736      offset, length);
737  }
738
739  /**
740   * Finds if the qualifier part of the cell and the KV serialized byte[] are equal
741   * @param left the cell with which we need to match the qualifier
742   * @param buf the serialized keyvalue format byte[]
743   * @param offset the offset of the qualifier in the byte[]
744   * @param length the length of the qualifier in the byte[]
745   * @return true if the qualifier matches, false otherwise
746   */
747  public static boolean matchingQualifier(final Cell left, final byte[] buf, final int offset,
748      final int length) {
749    if (buf == null) {
750      return left.getQualifierLength() == 0;
751    }
752    if (left instanceof ByteBufferExtendedCell) {
753      return ByteBufferUtils.equals(((ByteBufferExtendedCell) left).getQualifierByteBuffer(),
754          ((ByteBufferExtendedCell) left).getQualifierPosition(), left.getQualifierLength(),
755          buf, offset, length);
756    }
757    return Bytes.equals(left.getQualifierArray(), left.getQualifierOffset(),
758      left.getQualifierLength(), buf, offset, length);
759  }
760
761  public static boolean matchingColumn(final Cell left, final byte[] fam, final int foffset,
762      final int flength, final byte[] qual, final int qoffset, final int qlength) {
763    if (!matchingFamily(left, fam, foffset, flength)) {
764      return false;
765    }
766    return matchingQualifier(left, qual, qoffset, qlength);
767  }
768
769  public static boolean matchingValue(final Cell left, final Cell right, int lvlength,
770      int rvlength) {
771    if (left instanceof ByteBufferExtendedCell && right instanceof ByteBufferExtendedCell) {
772      return ByteBufferUtils.equals(((ByteBufferExtendedCell) left).getValueByteBuffer(),
773          ((ByteBufferExtendedCell) left).getValuePosition(), lvlength,
774          ((ByteBufferExtendedCell) right).getValueByteBuffer(),
775          ((ByteBufferExtendedCell) right).getValuePosition(), rvlength);
776    }
777    if (left instanceof ByteBufferExtendedCell) {
778      return ByteBufferUtils.equals(((ByteBufferExtendedCell) left).getValueByteBuffer(),
779          ((ByteBufferExtendedCell) left).getValuePosition(), lvlength, right.getValueArray(),
780          right.getValueOffset(), rvlength);
781    }
782    if (right instanceof ByteBufferExtendedCell) {
783      return ByteBufferUtils.equals(((ByteBufferExtendedCell) right).getValueByteBuffer(),
784          ((ByteBufferExtendedCell) right).getValuePosition(), rvlength, left.getValueArray(),
785          left.getValueOffset(), lvlength);
786    }
787    return Bytes
788        .equals(left.getValueArray(), left.getValueOffset(), lvlength, right.getValueArray(),
789            right.getValueOffset(), rvlength);
790  }
791
792  public static boolean matchingType(Cell a, Cell b) {
793    return a.getTypeByte() == b.getTypeByte();
794  }
795
796  /**
797   * @return True if a delete type, a {@link KeyValue.Type#Delete} or a {KeyValue.Type#DeleteFamily}
798   *         or a {@link KeyValue.Type#DeleteColumn} KeyValue type.
799   */
800  public static boolean isDelete(final byte type) {
801    return KeyValue.Type.Delete.getCode() <= type && type <= KeyValue.Type.DeleteFamily.getCode();
802  }
803
804  /**
805   * @return True if this cell is a {@link KeyValue.Type#Delete} type.
806   */
807  public static boolean isDeleteType(Cell cell) {
808    return cell.getTypeByte() == KeyValue.Type.Delete.getCode();
809  }
810
811  public static boolean isDeleteFamily(final Cell cell) {
812    return cell.getTypeByte() == KeyValue.Type.DeleteFamily.getCode();
813  }
814
815  public static boolean isDeleteFamilyVersion(final Cell cell) {
816    return cell.getTypeByte() == KeyValue.Type.DeleteFamilyVersion.getCode();
817  }
818
819  public static boolean isDeleteColumns(final Cell cell) {
820    return cell.getTypeByte() == KeyValue.Type.DeleteColumn.getCode();
821  }
822
823  public static boolean isDeleteColumnVersion(final Cell cell) {
824    return cell.getTypeByte() == KeyValue.Type.Delete.getCode();
825  }
826
827  /**
828   * @return True if this cell is a delete family or column type.
829   */
830  public static boolean isDeleteColumnOrFamily(Cell cell) {
831    int t = cell.getTypeByte();
832    return t == KeyValue.Type.DeleteColumn.getCode() || t == KeyValue.Type.DeleteFamily.getCode();
833  }
834
835  public static byte[] cloneTags(Cell cell) {
836    byte[] output = new byte[cell.getTagsLength()];
837    copyTagsTo(cell, output, 0);
838    return output;
839  }
840
841  /**
842   * Copies the tags info into the tag portion of the cell
843   * @param cell
844   * @param destination
845   * @param destinationOffset
846   * @return position after tags
847   */
848  public static int copyTagsTo(Cell cell, byte[] destination, int destinationOffset) {
849    int tlen = cell.getTagsLength();
850    if (cell instanceof ByteBufferExtendedCell) {
851      ByteBufferUtils
852        .copyFromBufferToArray(destination, ((ByteBufferExtendedCell) cell).getTagsByteBuffer(),
853          ((ByteBufferExtendedCell) cell).getTagsPosition(), destinationOffset, tlen);
854    } else {
855      System
856        .arraycopy(cell.getTagsArray(), cell.getTagsOffset(), destination, destinationOffset, tlen);
857    }
858    return destinationOffset + tlen;
859  }
860
861  /**
862   * Copies the tags info into the tag portion of the cell
863   * @param cell
864   * @param destination
865   * @param destinationOffset
866   * @return the position after tags
867   */
868  public static int copyTagsTo(Cell cell, ByteBuffer destination, int destinationOffset) {
869    int tlen = cell.getTagsLength();
870    if (cell instanceof ByteBufferExtendedCell) {
871      ByteBufferUtils.copyFromBufferToBuffer(((ByteBufferExtendedCell) cell).getTagsByteBuffer(),
872        destination, ((ByteBufferExtendedCell) cell).getTagsPosition(), destinationOffset, tlen);
873    } else {
874      ByteBufferUtils.copyFromArrayToBuffer(destination, destinationOffset, cell.getTagsArray(),
875        cell.getTagsOffset(), tlen);
876    }
877    return destinationOffset + tlen;
878  }
879
880  /**
881   * @param cell The Cell
882   * @return Tags in the given Cell as a List
883   */
884  public static List<Tag> getTags(Cell cell) {
885    List<Tag> tags = new ArrayList<>();
886    Iterator<Tag> tagsItr = tagsIterator(cell);
887    while (tagsItr.hasNext()) {
888      tags.add(tagsItr.next());
889    }
890    return tags;
891  }
892
893  /**
894   * Retrieve Cell's first tag, matching the passed in type
895   * @param cell The Cell
896   * @param type Type of the Tag to retrieve
897   * @return null if there is no tag of the passed in tag type
898   */
899  public static Optional<Tag> getTag(Cell cell, byte type) {
900    boolean bufferBacked = cell instanceof ByteBufferExtendedCell;
901    int length = cell.getTagsLength();
902    int offset =
903      bufferBacked ? ((ByteBufferExtendedCell) cell).getTagsPosition() : cell.getTagsOffset();
904    int pos = offset;
905    while (pos < offset + length) {
906      int tagLen;
907      if (bufferBacked) {
908        ByteBuffer tagsBuffer = ((ByteBufferExtendedCell) cell).getTagsByteBuffer();
909        tagLen = ByteBufferUtils.readAsInt(tagsBuffer, pos, TAG_LENGTH_SIZE);
910        if (ByteBufferUtils.toByte(tagsBuffer, pos + TAG_LENGTH_SIZE) == type) {
911          return Optional.of(new ByteBufferTag(tagsBuffer, pos, tagLen + TAG_LENGTH_SIZE));
912        }
913      } else {
914        tagLen = Bytes.readAsInt(cell.getTagsArray(), pos, TAG_LENGTH_SIZE);
915        if (cell.getTagsArray()[pos + TAG_LENGTH_SIZE] == type) {
916          return Optional
917            .of(new ArrayBackedTag(cell.getTagsArray(), pos, tagLen + TAG_LENGTH_SIZE));
918        }
919      }
920      pos += TAG_LENGTH_SIZE + tagLen;
921    }
922    return Optional.empty();
923  }
924
925  /**
926   * Util method to iterate through the tags in the given cell.
927   * @param cell The Cell over which tags iterator is needed.
928   * @return iterator for the tags
929   */
930  public static Iterator<Tag> tagsIterator(final Cell cell) {
931    final int tagsLength = cell.getTagsLength();
932    // Save an object allocation where we can
933    if (tagsLength == 0) {
934      return TagUtil.EMPTY_TAGS_ITR;
935    }
936    if (cell instanceof ByteBufferExtendedCell) {
937      return tagsIterator(((ByteBufferExtendedCell) cell).getTagsByteBuffer(),
938        ((ByteBufferExtendedCell) cell).getTagsPosition(), tagsLength);
939    }
940    return CellUtil.tagsIterator(cell.getTagsArray(), cell.getTagsOffset(), cell.getTagsLength());
941  }
942
943  public static Iterator<Tag> tagsIterator(final ByteBuffer tags, final int offset,
944      final int length) {
945    return new Iterator<Tag>() {
946      private int pos = offset;
947      private int endOffset = offset + length - 1;
948
949      @Override
950      public boolean hasNext() {
951        return this.pos < endOffset;
952      }
953
954      @Override
955      public Tag next() {
956        if (hasNext()) {
957          int curTagLen = ByteBufferUtils.readAsInt(tags, this.pos, Tag.TAG_LENGTH_SIZE);
958          Tag tag = new ByteBufferTag(tags, pos, curTagLen + Tag.TAG_LENGTH_SIZE);
959          this.pos += Bytes.SIZEOF_SHORT + curTagLen;
960          return tag;
961        }
962        return null;
963      }
964
965      @Override
966      public void remove() {
967        throw new UnsupportedOperationException();
968      }
969    };
970  }
971
972  /**
973   * Returns true if the first range start1...end1 overlaps with the second range start2...end2,
974   * assuming the byte arrays represent row keys
975   */
976  public static boolean overlappingKeys(final byte[] start1, final byte[] end1, final byte[] start2,
977      final byte[] end2) {
978    return (end2.length == 0 || start1.length == 0 || Bytes.compareTo(start1, end2) < 0)
979        && (end1.length == 0 || start2.length == 0 || Bytes.compareTo(start2, end1) < 0);
980  }
981
982  /**
983   * Write rowkey excluding the common part.
984   * @param cell
985   * @param rLen
986   * @param commonPrefix
987   * @param out
988   * @throws IOException
989   */
990  public static void writeRowKeyExcludingCommon(Cell cell, short rLen, int commonPrefix,
991      DataOutputStream out) throws IOException {
992    if (commonPrefix == 0) {
993      out.writeShort(rLen);
994    } else if (commonPrefix == 1) {
995      out.writeByte((byte) rLen);
996      commonPrefix--;
997    } else {
998      commonPrefix -= KeyValue.ROW_LENGTH_SIZE;
999    }
1000    if (rLen > commonPrefix) {
1001      writeRowSkippingBytes(out, cell, rLen, commonPrefix);
1002    }
1003  }
1004
1005  /**
1006   * Writes the row from the given cell to the output stream excluding the common prefix
1007   * @param out The dataoutputstream to which the data has to be written
1008   * @param cell The cell whose contents has to be written
1009   * @param rlength the row length
1010   * @throws IOException
1011   */
1012  public static void writeRowSkippingBytes(DataOutputStream out, Cell cell, short rlength,
1013      int commonPrefix) throws IOException {
1014    if (cell instanceof ByteBufferExtendedCell) {
1015      ByteBufferUtils
1016          .copyBufferToStream((DataOutput) out, ((ByteBufferExtendedCell) cell).getRowByteBuffer(),
1017              ((ByteBufferExtendedCell) cell).getRowPosition() + commonPrefix,
1018              rlength - commonPrefix);
1019    } else {
1020      out.write(cell.getRowArray(), cell.getRowOffset() + commonPrefix, rlength - commonPrefix);
1021    }
1022  }
1023
1024  /**
1025   * Find length of common prefix in keys of the cells, considering key as byte[] if serialized in
1026   * {@link KeyValue}. The key format is &lt;2 bytes rk len&gt;&lt;rk&gt;&lt;1 byte cf
1027   * len&gt;&lt;cf&gt;&lt;qualifier&gt;&lt;8 bytes timestamp&gt;&lt;1 byte type&gt;
1028   * @param c1 the cell
1029   * @param c2 the cell
1030   * @param bypassFamilyCheck when true assume the family bytes same in both cells. Pass it as true
1031   *          when dealing with Cells in same CF so as to avoid some checks
1032   * @param withTsType when true check timestamp and type bytes also.
1033   * @return length of common prefix
1034   */
1035  public static int findCommonPrefixInFlatKey(Cell c1, Cell c2, boolean bypassFamilyCheck,
1036    boolean withTsType) {
1037    // Compare the 2 bytes in RK length part
1038    short rLen1 = c1.getRowLength();
1039    short rLen2 = c2.getRowLength();
1040    int commonPrefix = KeyValue.ROW_LENGTH_SIZE;
1041    if (rLen1 != rLen2) {
1042      // early out when the RK length itself is not matching
1043      return ByteBufferUtils
1044        .findCommonPrefix(Bytes.toBytes(rLen1), 0, KeyValue.ROW_LENGTH_SIZE, Bytes.toBytes(rLen2),
1045          0, KeyValue.ROW_LENGTH_SIZE);
1046    }
1047    // Compare the RKs
1048    int rkCommonPrefix = 0;
1049    if (c1 instanceof ByteBufferExtendedCell && c2 instanceof ByteBufferExtendedCell) {
1050      rkCommonPrefix = ByteBufferUtils
1051        .findCommonPrefix(((ByteBufferExtendedCell) c1).getRowByteBuffer(),
1052          ((ByteBufferExtendedCell) c1).getRowPosition(), rLen1,
1053          ((ByteBufferExtendedCell) c2).getRowByteBuffer(),
1054          ((ByteBufferExtendedCell) c2).getRowPosition(), rLen2);
1055    } else {
1056      // There cannot be a case where one cell is BBCell and other is KeyValue. This flow comes
1057      // either
1058      // in flush or compactions. In flushes both cells are KV and in case of compaction it will be
1059      // either
1060      // KV or BBCell
1061      rkCommonPrefix = ByteBufferUtils
1062        .findCommonPrefix(c1.getRowArray(), c1.getRowOffset(), rLen1, c2.getRowArray(),
1063          c2.getRowOffset(), rLen2);
1064    }
1065    commonPrefix += rkCommonPrefix;
1066    if (rkCommonPrefix != rLen1) {
1067      // Early out when RK is not fully matching.
1068      return commonPrefix;
1069    }
1070    // Compare 1 byte CF length part
1071    byte fLen1 = c1.getFamilyLength();
1072    if (bypassFamilyCheck) {
1073      // This flag will be true when caller is sure that the family will be same for both the cells
1074      // Just make commonPrefix to increment by the family part
1075      commonPrefix += KeyValue.FAMILY_LENGTH_SIZE + fLen1;
1076    } else {
1077      byte fLen2 = c2.getFamilyLength();
1078      if (fLen1 != fLen2) {
1079        // early out when the CF length itself is not matching
1080        return commonPrefix;
1081      }
1082      // CF lengths are same so there is one more byte common in key part
1083      commonPrefix += KeyValue.FAMILY_LENGTH_SIZE;
1084      // Compare the CF names
1085      int fCommonPrefix;
1086      if (c1 instanceof ByteBufferExtendedCell && c2 instanceof ByteBufferExtendedCell) {
1087        fCommonPrefix = ByteBufferUtils
1088          .findCommonPrefix(((ByteBufferExtendedCell) c1).getFamilyByteBuffer(),
1089            ((ByteBufferExtendedCell) c1).getFamilyPosition(), fLen1,
1090            ((ByteBufferExtendedCell) c2).getFamilyByteBuffer(),
1091            ((ByteBufferExtendedCell) c2).getFamilyPosition(), fLen2);
1092      } else {
1093        fCommonPrefix = ByteBufferUtils
1094          .findCommonPrefix(c1.getFamilyArray(), c1.getFamilyOffset(), fLen1, c2.getFamilyArray(),
1095            c2.getFamilyOffset(), fLen2);
1096      }
1097      commonPrefix += fCommonPrefix;
1098      if (fCommonPrefix != fLen1) {
1099        return commonPrefix;
1100      }
1101    }
1102    // Compare the Qualifiers
1103    int qLen1 = c1.getQualifierLength();
1104    int qLen2 = c2.getQualifierLength();
1105    int qCommon;
1106    if (c1 instanceof ByteBufferExtendedCell && c2 instanceof ByteBufferExtendedCell) {
1107      qCommon = ByteBufferUtils
1108        .findCommonPrefix(((ByteBufferExtendedCell) c1).getQualifierByteBuffer(),
1109          ((ByteBufferExtendedCell) c1).getQualifierPosition(), qLen1,
1110          ((ByteBufferExtendedCell) c2).getQualifierByteBuffer(),
1111          ((ByteBufferExtendedCell) c2).getQualifierPosition(), qLen2);
1112    } else {
1113      qCommon = ByteBufferUtils
1114        .findCommonPrefix(c1.getQualifierArray(), c1.getQualifierOffset(), qLen1,
1115          c2.getQualifierArray(), c2.getQualifierOffset(), qLen2);
1116    }
1117    commonPrefix += qCommon;
1118    if (!withTsType || Math.max(qLen1, qLen2) != qCommon) {
1119      return commonPrefix;
1120    }
1121    // Compare the timestamp parts
1122    int tsCommonPrefix = ByteBufferUtils
1123      .findCommonPrefix(Bytes.toBytes(c1.getTimestamp()), 0, KeyValue.TIMESTAMP_SIZE,
1124        Bytes.toBytes(c2.getTimestamp()), 0, KeyValue.TIMESTAMP_SIZE);
1125    commonPrefix += tsCommonPrefix;
1126    if (tsCommonPrefix != KeyValue.TIMESTAMP_SIZE) {
1127      return commonPrefix;
1128    }
1129    // Compare the type
1130    if (c1.getTypeByte() == c2.getTypeByte()) {
1131      commonPrefix += KeyValue.TYPE_SIZE;
1132    }
1133    return commonPrefix;
1134  }
1135
1136  /**
1137   * Used to compare two cells based on the column hint provided. This is specifically used when we
1138   * need to optimize the seeks based on the next indexed key. This is an advanced usage API
1139   * specifically needed for some optimizations.
1140   * @param nextIndexedCell the next indexed cell
1141   * @param currentCell the cell to be compared
1142   * @param foff the family offset of the currentCell
1143   * @param flen the family length of the currentCell
1144   * @param colHint the column hint provided - could be null
1145   * @param coff the offset of the column hint if provided, if not offset of the currentCell's
1146   *          qualifier
1147   * @param clen the length of the column hint if provided, if not length of the currentCell's
1148   *          qualifier
1149   * @param ts the timestamp to be seeked
1150   * @param type the type to be seeked
1151   * @return an int based on the given column hint TODO : To be moved out of here because this is a
1152   *         special API used in scan optimization.
1153   */
1154  // compare a key against row/fam/qual/ts/type
1155  public static final int compareKeyBasedOnColHint(CellComparator comparator, Cell nextIndexedCell,
1156      Cell currentCell, int foff, int flen, byte[] colHint, int coff, int clen, long ts,
1157      byte type) {
1158    int compare = comparator.compareRows(nextIndexedCell, currentCell);
1159    if (compare != 0) {
1160      return compare;
1161    }
1162    // If the column is not specified, the "minimum" key type appears the
1163    // latest in the sorted order, regardless of the timestamp. This is used
1164    // for specifying the last key/value in a given row, because there is no
1165    // "lexicographically last column" (it would be infinitely long). The
1166    // "maximum" key type does not need this behavior.
1167    if (nextIndexedCell.getFamilyLength() + nextIndexedCell.getQualifierLength() == 0
1168        && nextIndexedCell.getTypeByte() == KeyValue.Type.Minimum.getCode()) {
1169      // left is "bigger", i.e. it appears later in the sorted order
1170      return 1;
1171    }
1172    if (flen + clen == 0 && type == KeyValue.Type.Minimum.getCode()) {
1173      return -1;
1174    }
1175
1176    compare = comparator.compareFamilies(nextIndexedCell, currentCell);
1177    if (compare != 0) {
1178      return compare;
1179    }
1180    if (colHint == null) {
1181      compare = comparator.compareQualifiers(nextIndexedCell, currentCell);
1182    } else {
1183      compare = CellUtil.compareQualifiers(nextIndexedCell, colHint, coff, clen);
1184    }
1185    if (compare != 0) {
1186      return compare;
1187    }
1188    // Next compare timestamps.
1189    compare = comparator.compareTimestamps(nextIndexedCell.getTimestamp(), ts);
1190    if (compare != 0) {
1191      return compare;
1192    }
1193
1194    // Compare types. Let the delete types sort ahead of puts; i.e. types
1195    // of higher numbers sort before those of lesser numbers. Maximum (255)
1196    // appears ahead of everything, and minimum (0) appears after
1197    // everything.
1198    return (0xff & type) - (0xff & nextIndexedCell.getTypeByte());
1199  }
1200
1201  /**
1202   * Compares only the key portion of a cell. It does not include the sequence id/mvcc of the cell
1203   * @param left
1204   * @param right
1205   * @return an int greater than 0 if left &gt; than right lesser than 0 if left &lt; than right
1206   *         equal to 0 if left is equal to right
1207   */
1208  public static final int compareKeyIgnoresMvcc(CellComparator comparator, Cell left, Cell right) {
1209    return ((CellComparatorImpl) comparator).compare(left, right, true);
1210  }
1211
1212  /**
1213   * Compare cell's row against given comparator
1214   * @param cell
1215   * @param comparator
1216   * @return result comparing cell's row
1217   */
1218  public static int compareRow(Cell cell, ByteArrayComparable comparator) {
1219    if (cell instanceof ByteBufferExtendedCell) {
1220      return comparator.compareTo(((ByteBufferExtendedCell) cell).getRowByteBuffer(),
1221        ((ByteBufferExtendedCell) cell).getRowPosition(), cell.getRowLength());
1222    }
1223    return comparator.compareTo(cell.getRowArray(), cell.getRowOffset(), cell.getRowLength());
1224  }
1225
1226  /**
1227   * Compare cell's column family against given comparator
1228   * @param cell
1229   * @param comparator
1230   * @return result comparing cell's column family
1231   */
1232  public static int compareFamily(Cell cell, ByteArrayComparable comparator) {
1233    if (cell instanceof ByteBufferExtendedCell) {
1234      return comparator.compareTo(((ByteBufferExtendedCell) cell).getFamilyByteBuffer(),
1235        ((ByteBufferExtendedCell) cell).getFamilyPosition(), cell.getFamilyLength());
1236    }
1237    return comparator.compareTo(cell.getFamilyArray(), cell.getFamilyOffset(),
1238      cell.getFamilyLength());
1239  }
1240
1241  /**
1242   * Compare cell's qualifier against given comparator
1243   * @param cell
1244   * @param comparator
1245   * @return result comparing cell's qualifier
1246   */
1247  public static int compareQualifier(Cell cell, ByteArrayComparable comparator) {
1248    if (cell instanceof ByteBufferExtendedCell) {
1249      return comparator.compareTo(((ByteBufferExtendedCell) cell).getQualifierByteBuffer(),
1250        ((ByteBufferExtendedCell) cell).getQualifierPosition(), cell.getQualifierLength());
1251    }
1252    return comparator.compareTo(cell.getQualifierArray(), cell.getQualifierOffset(),
1253      cell.getQualifierLength());
1254  }
1255
1256  public static Cell.Type toType(byte type) {
1257    KeyValue.Type codeToType = KeyValue.Type.codeToType(type);
1258    switch (codeToType) {
1259      case Put: return Cell.Type.Put;
1260      case Delete: return Cell.Type.Delete;
1261      case DeleteColumn: return Cell.Type.DeleteColumn;
1262      case DeleteFamily: return Cell.Type.DeleteFamily;
1263      case DeleteFamilyVersion: return Cell.Type.DeleteFamilyVersion;
1264      default: throw new UnsupportedOperationException("Invalid type of cell "+type);
1265    }
1266  }
1267
1268  public static KeyValue.Type toTypeByte(Cell.Type type) {
1269    switch (type) {
1270      case Put: return KeyValue.Type.Put;
1271      case Delete: return KeyValue.Type.Delete;
1272      case DeleteColumn: return KeyValue.Type.DeleteColumn;
1273      case DeleteFamilyVersion: return KeyValue.Type.DeleteFamilyVersion;
1274      case DeleteFamily: return KeyValue.Type.DeleteFamily;
1275      default: throw new UnsupportedOperationException("Unsupported data type:" + type);
1276    }
1277  }
1278
1279  /**
1280   * Compare cell's value against given comparator
1281   * @param cell
1282   * @param comparator
1283   * @return result comparing cell's value
1284   */
1285  public static int compareValue(Cell cell, ByteArrayComparable comparator) {
1286    if (cell instanceof ByteBufferExtendedCell) {
1287      return comparator.compareTo(((ByteBufferExtendedCell) cell).getValueByteBuffer(),
1288        ((ByteBufferExtendedCell) cell).getValuePosition(), cell.getValueLength());
1289    }
1290    return comparator.compareTo(cell.getValueArray(), cell.getValueOffset(), cell.getValueLength());
1291  }
1292
1293  /**
1294   * These cells are used in reseeks/seeks to improve the read performance. They are not real cells
1295   * that are returned back to the clients
1296   */
1297  private static abstract class EmptyCell implements ExtendedCell {
1298
1299    @Override
1300    public void setSequenceId(long seqId) {
1301      // Fake cells don't need seqId, so leaving it as a noop.
1302    }
1303
1304    @Override
1305    public void setTimestamp(long ts) {
1306      // Fake cells can't be changed timestamp, so leaving it as a noop.
1307    }
1308
1309    @Override
1310    public void setTimestamp(byte[] ts) {
1311      // Fake cells can't be changed timestamp, so leaving it as a noop.
1312    }
1313
1314    @Override
1315    public byte[] getRowArray() {
1316      return EMPTY_BYTE_ARRAY;
1317    }
1318
1319    @Override
1320    public int getRowOffset() {
1321      return 0;
1322    }
1323
1324    @Override
1325    public short getRowLength() {
1326      return 0;
1327    }
1328
1329    @Override
1330    public byte[] getFamilyArray() {
1331      return EMPTY_BYTE_ARRAY;
1332    }
1333
1334    @Override
1335    public int getFamilyOffset() {
1336      return 0;
1337    }
1338
1339    @Override
1340    public byte getFamilyLength() {
1341      return 0;
1342    }
1343
1344    @Override
1345    public byte[] getQualifierArray() {
1346      return EMPTY_BYTE_ARRAY;
1347    }
1348
1349    @Override
1350    public int getQualifierOffset() {
1351      return 0;
1352    }
1353
1354    @Override
1355    public int getQualifierLength() {
1356      return 0;
1357    }
1358
1359    @Override
1360    public long getSequenceId() {
1361      return 0;
1362    }
1363
1364    @Override
1365    public byte[] getValueArray() {
1366      return EMPTY_BYTE_ARRAY;
1367    }
1368
1369    @Override
1370    public int getValueOffset() {
1371      return 0;
1372    }
1373
1374    @Override
1375    public int getValueLength() {
1376      return 0;
1377    }
1378
1379    @Override
1380    public byte[] getTagsArray() {
1381      return EMPTY_BYTE_ARRAY;
1382    }
1383
1384    @Override
1385    public int getTagsOffset() {
1386      return 0;
1387    }
1388
1389    @Override
1390    public int getTagsLength() {
1391      return 0;
1392    }
1393  }
1394
1395  /**
1396   * These cells are used in reseeks/seeks to improve the read performance. They are not real cells
1397   * that are returned back to the clients
1398   */
1399  private static abstract class EmptyByteBufferExtendedCell extends ByteBufferExtendedCell {
1400
1401    @Override
1402    public void setSequenceId(long seqId) {
1403      // Fake cells don't need seqId, so leaving it as a noop.
1404    }
1405
1406    @Override
1407    public void setTimestamp(long ts) {
1408      // Fake cells can't be changed timestamp, so leaving it as a noop.
1409    }
1410
1411    @Override
1412    public void setTimestamp(byte[] ts) {
1413      // Fake cells can't be changed timestamp, so leaving it as a noop.
1414    }
1415
1416    @Override
1417    public byte[] getRowArray() {
1418      return CellUtil.cloneRow(this);
1419    }
1420
1421    @Override
1422    public int getRowOffset() {
1423      return 0;
1424    }
1425
1426    @Override
1427    public short getRowLength() {
1428      return 0;
1429    }
1430
1431    @Override
1432    public byte[] getFamilyArray() {
1433      return CellUtil.cloneFamily(this);
1434    }
1435
1436    @Override
1437    public int getFamilyOffset() {
1438      return 0;
1439    }
1440
1441    @Override
1442    public byte getFamilyLength() {
1443      return 0;
1444    }
1445
1446    @Override
1447    public byte[] getQualifierArray() {
1448      return CellUtil.cloneQualifier(this);
1449    }
1450
1451    @Override
1452    public int getQualifierOffset() {
1453      return 0;
1454    }
1455
1456    @Override
1457    public int getQualifierLength() {
1458      return 0;
1459    }
1460
1461    @Override
1462    public long getSequenceId() {
1463      return 0;
1464    }
1465
1466    @Override
1467    public byte[] getValueArray() {
1468      return CellUtil.cloneValue(this);
1469    }
1470
1471    @Override
1472    public int getValueOffset() {
1473      return 0;
1474    }
1475
1476    @Override
1477    public int getValueLength() {
1478      return 0;
1479    }
1480
1481    @Override
1482    public byte[] getTagsArray() {
1483      return CellUtil.cloneTags(this);
1484    }
1485
1486    @Override
1487    public int getTagsOffset() {
1488      return 0;
1489    }
1490
1491    @Override
1492    public int getTagsLength() {
1493      return 0;
1494    }
1495
1496    @Override
1497    public ByteBuffer getRowByteBuffer() {
1498      return HConstants.EMPTY_BYTE_BUFFER;
1499    }
1500
1501    @Override
1502    public int getRowPosition() {
1503      return 0;
1504    }
1505
1506    @Override
1507    public ByteBuffer getFamilyByteBuffer() {
1508      return HConstants.EMPTY_BYTE_BUFFER;
1509    }
1510
1511    @Override
1512    public int getFamilyPosition() {
1513      return 0;
1514    }
1515
1516    @Override
1517    public ByteBuffer getQualifierByteBuffer() {
1518      return HConstants.EMPTY_BYTE_BUFFER;
1519    }
1520
1521    @Override
1522    public int getQualifierPosition() {
1523      return 0;
1524    }
1525
1526    @Override
1527    public ByteBuffer getTagsByteBuffer() {
1528      return HConstants.EMPTY_BYTE_BUFFER;
1529    }
1530
1531    @Override
1532    public int getTagsPosition() {
1533      return 0;
1534    }
1535
1536    @Override
1537    public ByteBuffer getValueByteBuffer() {
1538      return HConstants.EMPTY_BYTE_BUFFER;
1539    }
1540
1541    @Override
1542    public int getValuePosition() {
1543      return 0;
1544    }
1545  }
1546
1547  private static class FirstOnRowCell extends EmptyCell {
1548    private static final int FIXED_HEAPSIZE =
1549        ClassSize.OBJECT // object
1550      + ClassSize.REFERENCE // row array
1551      + Bytes.SIZEOF_INT // row offset
1552      + Bytes.SIZEOF_SHORT;  // row length
1553    private final byte[] rowArray;
1554    private final int roffset;
1555    private final short rlength;
1556
1557    public FirstOnRowCell(final byte[] row, int roffset, short rlength) {
1558      this.rowArray = row;
1559      this.roffset = roffset;
1560      this.rlength = rlength;
1561    }
1562
1563    @Override
1564    public long heapSize() {
1565      return ClassSize.align(FIXED_HEAPSIZE)
1566          // array overhead
1567          + (rlength == 0 ? ClassSize.sizeOfByteArray(rlength) : rlength);
1568    }
1569
1570    @Override
1571    public byte[] getRowArray() {
1572      return this.rowArray;
1573    }
1574
1575    @Override
1576    public int getRowOffset() {
1577      return this.roffset;
1578    }
1579
1580    @Override
1581    public short getRowLength() {
1582      return this.rlength;
1583    }
1584
1585    @Override
1586    public long getTimestamp() {
1587      return HConstants.LATEST_TIMESTAMP;
1588    }
1589
1590    @Override
1591    public byte getTypeByte() {
1592      return KeyValue.Type.Maximum.getCode();
1593    }
1594
1595    @Override
1596    public Type getType() {
1597      throw new UnsupportedOperationException();
1598    }
1599  }
1600
1601  private static class FirstOnRowByteBufferExtendedCell extends EmptyByteBufferExtendedCell {
1602    private static final int FIXED_OVERHEAD =
1603        ClassSize.OBJECT // object
1604        + ClassSize.REFERENCE // row buffer
1605        + Bytes.SIZEOF_INT // row offset
1606        + Bytes.SIZEOF_SHORT; // row length
1607    private final ByteBuffer rowBuff;
1608    private final int roffset;
1609    private final short rlength;
1610
1611    public FirstOnRowByteBufferExtendedCell(final ByteBuffer row, int roffset, short rlength) {
1612      this.rowBuff = row;
1613      this.roffset = roffset;
1614      this.rlength = rlength;
1615    }
1616
1617    @Override
1618    public long heapSize() {
1619      if (this.rowBuff.hasArray()) {
1620        return ClassSize.align(FIXED_OVERHEAD + rlength);
1621      }
1622      return ClassSize.align(FIXED_OVERHEAD);
1623    }
1624
1625    @Override
1626    public ByteBuffer getRowByteBuffer() {
1627      return this.rowBuff;
1628    }
1629
1630    @Override
1631    public int getRowPosition() {
1632      return this.roffset;
1633    }
1634
1635    @Override
1636    public short getRowLength() {
1637      return this.rlength;
1638    }
1639
1640    @Override
1641    public long getTimestamp() {
1642      return HConstants.LATEST_TIMESTAMP;
1643    }
1644
1645    @Override
1646    public byte getTypeByte() {
1647      return KeyValue.Type.Maximum.getCode();
1648    }
1649
1650    @Override
1651    public Type getType() {
1652      throw new UnsupportedOperationException();
1653    }
1654  }
1655
1656  private static class LastOnRowByteBufferExtendedCell extends EmptyByteBufferExtendedCell {
1657    private static final int FIXED_OVERHEAD =
1658        ClassSize.OBJECT // object
1659      + ClassSize.REFERENCE // rowBuff
1660      + Bytes.SIZEOF_INT // roffset
1661      + Bytes.SIZEOF_SHORT; // rlength
1662    private final ByteBuffer rowBuff;
1663    private final int roffset;
1664    private final short rlength;
1665
1666    public LastOnRowByteBufferExtendedCell(final ByteBuffer row, int roffset, short rlength) {
1667      this.rowBuff = row;
1668      this.roffset = roffset;
1669      this.rlength = rlength;
1670    }
1671
1672    @Override
1673    public long heapSize() {
1674      if (this.rowBuff.hasArray()) {
1675        return ClassSize.align(FIXED_OVERHEAD + rlength);
1676      }
1677      return ClassSize.align(FIXED_OVERHEAD);
1678    }
1679
1680    @Override
1681    public ByteBuffer getRowByteBuffer() {
1682      return this.rowBuff;
1683    }
1684
1685    @Override
1686    public int getRowPosition() {
1687      return this.roffset;
1688    }
1689
1690    @Override
1691    public short getRowLength() {
1692      return this.rlength;
1693    }
1694
1695    @Override
1696    public long getTimestamp() {
1697      return HConstants.OLDEST_TIMESTAMP;
1698    }
1699
1700    @Override
1701    public byte getTypeByte() {
1702      return KeyValue.Type.Minimum.getCode();
1703    }
1704
1705    @Override
1706    public Type getType() {
1707      throw new UnsupportedOperationException();
1708    }
1709  }
1710
1711  private static class FirstOnRowColByteBufferExtendedCell
1712      extends FirstOnRowByteBufferExtendedCell {
1713    private static final int FIXED_OVERHEAD =
1714        FirstOnRowByteBufferExtendedCell.FIXED_OVERHEAD
1715        + ClassSize.REFERENCE * 2 // family buffer and column buffer
1716        + Bytes.SIZEOF_INT * 3 // famOffset, colOffset, colLength
1717        + Bytes.SIZEOF_BYTE; // famLength
1718    private final ByteBuffer famBuff;
1719    private final int famOffset;
1720    private final byte famLength;
1721    private final ByteBuffer colBuff;
1722    private final int colOffset;
1723    private final int colLength;
1724
1725    public FirstOnRowColByteBufferExtendedCell(final ByteBuffer row, int roffset, short rlength,
1726        final ByteBuffer famBuff, final int famOffset, final byte famLength, final ByteBuffer col,
1727        final int colOffset, final int colLength) {
1728      super(row, roffset, rlength);
1729      this.famBuff = famBuff;
1730      this.famOffset = famOffset;
1731      this.famLength = famLength;
1732      this.colBuff = col;
1733      this.colOffset = colOffset;
1734      this.colLength = colLength;
1735    }
1736
1737    @Override
1738    public long heapSize() {
1739      if (famBuff.hasArray() && colBuff.hasArray()) {
1740        return ClassSize.align(FIXED_OVERHEAD + famLength + colLength);
1741      } else if (famBuff.hasArray()) {
1742        return ClassSize.align(FIXED_OVERHEAD + famLength);
1743      } else if (colBuff.hasArray()) {
1744        return ClassSize.align(FIXED_OVERHEAD + colLength);
1745      } else {
1746        return ClassSize.align(FIXED_OVERHEAD);
1747      }
1748    }
1749
1750    @Override
1751    public ByteBuffer getFamilyByteBuffer() {
1752      return this.famBuff;
1753    }
1754
1755    @Override
1756    public int getFamilyPosition() {
1757      return this.famOffset;
1758    }
1759
1760    @Override
1761    public byte getFamilyLength() {
1762      return famLength;
1763    }
1764
1765    @Override
1766    public ByteBuffer getQualifierByteBuffer() {
1767      return this.colBuff;
1768    }
1769
1770    @Override
1771    public int getQualifierPosition() {
1772      return this.colOffset;
1773    }
1774
1775    @Override
1776    public int getQualifierLength() {
1777      return this.colLength;
1778    }
1779  }
1780
1781  private static class FirstOnRowColCell extends FirstOnRowCell {
1782    private static final long FIXED_HEAPSIZE =
1783        FirstOnRowCell.FIXED_HEAPSIZE
1784      + Bytes.SIZEOF_BYTE // flength
1785      + Bytes.SIZEOF_INT * 3 // foffset, qoffset, qlength
1786      + ClassSize.REFERENCE * 2; // fArray, qArray
1787    private final byte[] fArray;
1788    private final int foffset;
1789    private final byte flength;
1790    private final byte[] qArray;
1791    private final int qoffset;
1792    private final int qlength;
1793
1794    public FirstOnRowColCell(byte[] rArray, int roffset, short rlength, byte[] fArray, int foffset,
1795        byte flength, byte[] qArray, int qoffset, int qlength) {
1796      super(rArray, roffset, rlength);
1797      this.fArray = fArray;
1798      this.foffset = foffset;
1799      this.flength = flength;
1800      this.qArray = qArray;
1801      this.qoffset = qoffset;
1802      this.qlength = qlength;
1803    }
1804
1805    @Override
1806    public long heapSize() {
1807      return ClassSize.align(FIXED_HEAPSIZE)
1808          // array overhead
1809          + (flength == 0 ? ClassSize.sizeOfByteArray(flength) : flength)
1810          + (qlength == 0 ? ClassSize.sizeOfByteArray(qlength) : qlength);
1811    }
1812
1813    @Override
1814    public byte[] getFamilyArray() {
1815      return this.fArray;
1816    }
1817
1818    @Override
1819    public int getFamilyOffset() {
1820      return this.foffset;
1821    }
1822
1823    @Override
1824    public byte getFamilyLength() {
1825      return this.flength;
1826    }
1827
1828    @Override
1829    public byte[] getQualifierArray() {
1830      return this.qArray;
1831    }
1832
1833    @Override
1834    public int getQualifierOffset() {
1835      return this.qoffset;
1836    }
1837
1838    @Override
1839    public int getQualifierLength() {
1840      return this.qlength;
1841    }
1842  }
1843
1844  private static class FirstOnRowColTSCell extends FirstOnRowColCell {
1845    private static final long FIXED_HEAPSIZE =
1846        FirstOnRowColCell.FIXED_HEAPSIZE
1847            + Bytes.SIZEOF_LONG; // ts
1848    private long ts;
1849
1850    public FirstOnRowColTSCell(byte[] rArray, int roffset, short rlength, byte[] fArray,
1851        int foffset, byte flength, byte[] qArray, int qoffset, int qlength, long ts) {
1852      super(rArray, roffset, rlength, fArray, foffset, flength, qArray, qoffset, qlength);
1853      this.ts = ts;
1854    }
1855
1856    @Override
1857    public long getTimestamp() {
1858      return this.ts;
1859    }
1860
1861    @Override
1862    public long heapSize() {
1863      return ClassSize.align(FIXED_HEAPSIZE);
1864    }
1865  }
1866
1867  private static class FirstOnRowColTSByteBufferExtendedCell
1868      extends FirstOnRowColByteBufferExtendedCell {
1869    private static final int FIXED_OVERHEAD =
1870        FirstOnRowColByteBufferExtendedCell.FIXED_OVERHEAD
1871            + Bytes.SIZEOF_LONG; // ts
1872    private long ts;
1873
1874    public FirstOnRowColTSByteBufferExtendedCell(ByteBuffer rBuffer, int roffset, short rlength,
1875        ByteBuffer fBuffer, int foffset, byte flength, ByteBuffer qBuffer, int qoffset, int qlength,
1876        long ts) {
1877      super(rBuffer, roffset, rlength, fBuffer, foffset, flength, qBuffer, qoffset, qlength);
1878      this.ts = ts;
1879    }
1880
1881    @Override
1882    public long getTimestamp() {
1883      return this.ts;
1884    }
1885
1886    @Override
1887    public long heapSize() {
1888      return ClassSize.align(FIXED_OVERHEAD + super.heapSize());
1889    }
1890  }
1891
1892  private static class LastOnRowCell extends EmptyCell {
1893    private static final int FIXED_OVERHEAD =
1894        ClassSize.OBJECT // object
1895      + ClassSize.REFERENCE // row array
1896      + Bytes.SIZEOF_INT // row offset
1897      + Bytes.SIZEOF_SHORT; // row length
1898    private final byte[] rowArray;
1899    private final int roffset;
1900    private final short rlength;
1901
1902    public LastOnRowCell(byte[] row, int roffset, short rlength) {
1903      this.rowArray = row;
1904      this.roffset = roffset;
1905      this.rlength = rlength;
1906    }
1907
1908    @Override
1909    public long heapSize() {
1910      return ClassSize.align(FIXED_OVERHEAD)
1911          // array overhead
1912          + (rlength == 0 ? ClassSize.sizeOfByteArray(rlength) : rlength);
1913    }
1914
1915    @Override
1916    public byte[] getRowArray() {
1917      return this.rowArray;
1918    }
1919
1920    @Override
1921    public int getRowOffset() {
1922      return this.roffset;
1923    }
1924
1925    @Override
1926    public short getRowLength() {
1927      return this.rlength;
1928    }
1929
1930    @Override
1931    public long getTimestamp() {
1932      return HConstants.OLDEST_TIMESTAMP;
1933    }
1934
1935    @Override
1936    public byte getTypeByte() {
1937      return KeyValue.Type.Minimum.getCode();
1938    }
1939
1940    @Override
1941    public Type getType() {
1942      throw new UnsupportedOperationException();
1943    }
1944  }
1945
1946  private static class LastOnRowColCell extends LastOnRowCell {
1947    private static final long FIXED_OVERHEAD = LastOnRowCell.FIXED_OVERHEAD
1948        + ClassSize.REFERENCE * 2 // fArray and qArray
1949        + Bytes.SIZEOF_INT * 3 // foffset, qoffset, qlength
1950        + Bytes.SIZEOF_BYTE; // flength
1951    private final byte[] fArray;
1952    private final int foffset;
1953    private final byte flength;
1954    private final byte[] qArray;
1955    private final int qoffset;
1956    private final int qlength;
1957
1958    public LastOnRowColCell(byte[] rArray, int roffset, short rlength, byte[] fArray, int foffset,
1959        byte flength, byte[] qArray, int qoffset, int qlength) {
1960      super(rArray, roffset, rlength);
1961      this.fArray = fArray;
1962      this.foffset = foffset;
1963      this.flength = flength;
1964      this.qArray = qArray;
1965      this.qoffset = qoffset;
1966      this.qlength = qlength;
1967    }
1968
1969    @Override
1970    public long heapSize() {
1971      return ClassSize.align(FIXED_OVERHEAD)
1972          // array overhead
1973          + (flength == 0 ? ClassSize.sizeOfByteArray(flength) : flength)
1974          + (qlength == 0 ? ClassSize.sizeOfByteArray(qlength) : qlength);
1975    }
1976
1977    @Override
1978    public byte[] getFamilyArray() {
1979      return this.fArray;
1980    }
1981
1982    @Override
1983    public int getFamilyOffset() {
1984      return this.foffset;
1985    }
1986
1987    @Override
1988    public byte getFamilyLength() {
1989      return this.flength;
1990    }
1991
1992    @Override
1993    public byte[] getQualifierArray() {
1994      return this.qArray;
1995    }
1996
1997    @Override
1998    public int getQualifierOffset() {
1999      return this.qoffset;
2000    }
2001
2002    @Override
2003    public int getQualifierLength() {
2004      return this.qlength;
2005    }
2006  }
2007
2008  private static class LastOnRowColByteBufferExtendedCell extends LastOnRowByteBufferExtendedCell {
2009    private static final int FIXED_OVERHEAD =
2010        LastOnRowByteBufferExtendedCell.FIXED_OVERHEAD
2011            + ClassSize.REFERENCE * 2 // fBuffer and qBuffer
2012            + Bytes.SIZEOF_INT * 3 // foffset, qoffset, qlength
2013            + Bytes.SIZEOF_BYTE; // flength
2014    private final ByteBuffer fBuffer;
2015    private final int foffset;
2016    private final byte flength;
2017    private final ByteBuffer qBuffer;
2018    private final int qoffset;
2019    private final int qlength;
2020
2021    public LastOnRowColByteBufferExtendedCell(ByteBuffer rBuffer, int roffset, short rlength,
2022        ByteBuffer fBuffer, int foffset, byte flength, ByteBuffer qBuffer, int qoffset,
2023        int qlength) {
2024      super(rBuffer, roffset, rlength);
2025      this.fBuffer = fBuffer;
2026      this.foffset = foffset;
2027      this.flength = flength;
2028      this.qBuffer = qBuffer;
2029      this.qoffset = qoffset;
2030      this.qlength = qlength;
2031    }
2032
2033    @Override
2034    public long heapSize() {
2035      if (fBuffer.hasArray() && qBuffer.hasArray()) {
2036        return ClassSize.align(FIXED_OVERHEAD + flength + qlength);
2037      } else if (fBuffer.hasArray()) {
2038        return ClassSize.align(FIXED_OVERHEAD + flength);
2039      } else if (qBuffer.hasArray()) {
2040        return ClassSize.align(FIXED_OVERHEAD + qlength);
2041      } else {
2042        return ClassSize.align(FIXED_OVERHEAD);
2043      }
2044    }
2045
2046    @Override
2047    public ByteBuffer getFamilyByteBuffer() {
2048      return this.fBuffer;
2049    }
2050
2051    @Override
2052    public int getFamilyPosition() {
2053      return this.foffset;
2054    }
2055
2056    @Override
2057    public byte getFamilyLength() {
2058      return this.flength;
2059    }
2060
2061    @Override
2062    public ByteBuffer getQualifierByteBuffer() {
2063      return this.qBuffer;
2064    }
2065
2066    @Override
2067    public int getQualifierPosition() {
2068      return this.qoffset;
2069    }
2070
2071    @Override
2072    public int getQualifierLength() {
2073      return this.qlength;
2074    }
2075  }
2076
2077  private static class FirstOnRowDeleteFamilyCell extends EmptyCell {
2078    private static final int FIXED_OVERHEAD =
2079        ClassSize.OBJECT // object
2080      + ClassSize.REFERENCE * 2 // fBuffer and qBuffer
2081      + Bytes.SIZEOF_INT * 3 // foffset, qoffset, qlength
2082      + Bytes.SIZEOF_BYTE; // flength
2083    private final byte[] row;
2084    private final byte[] fam;
2085
2086    public FirstOnRowDeleteFamilyCell(byte[] row, byte[] fam) {
2087      this.row = row;
2088      this.fam = fam;
2089    }
2090
2091    @Override
2092    public long heapSize() {
2093      return ClassSize.align(FIXED_OVERHEAD)
2094        // array overhead
2095        + (getRowLength() == 0 ? ClassSize.sizeOfByteArray(getRowLength()) : getRowLength())
2096        + (getFamilyLength() == 0 ?
2097          ClassSize.sizeOfByteArray(getFamilyLength()) : getFamilyLength());
2098    }
2099
2100    @Override
2101    public byte[] getRowArray() {
2102      return this.row;
2103    }
2104
2105    @Override
2106    public short getRowLength() {
2107      return (short) this.row.length;
2108    }
2109
2110    @Override
2111    public byte[] getFamilyArray() {
2112      return this.fam;
2113    }
2114
2115    @Override
2116    public byte getFamilyLength() {
2117      return (byte) this.fam.length;
2118    }
2119
2120    @Override
2121    public long getTimestamp() {
2122      return HConstants.LATEST_TIMESTAMP;
2123    }
2124
2125    @Override
2126    public byte getTypeByte() {
2127      return KeyValue.Type.DeleteFamily.getCode();
2128    }
2129
2130    @Override
2131    public Type getType() {
2132      return Type.DeleteFamily;
2133    }
2134  }
2135
2136  /**
2137   * Writes the Cell's key part as it would have serialized in a KeyValue. The format is &lt;2 bytes
2138   * rk len&gt;&lt;rk&gt;&lt;1 byte cf len&gt;&lt;cf&gt;&lt;qualifier&gt;&lt;8 bytes
2139   * timestamp&gt;&lt;1 byte type&gt;
2140   * @param cell
2141   * @param out
2142   * @throws IOException
2143   */
2144  public static void writeFlatKey(Cell cell, DataOutput out) throws IOException {
2145    short rowLen = cell.getRowLength();
2146    byte fLen = cell.getFamilyLength();
2147    int qLen = cell.getQualifierLength();
2148    // Using just one if/else loop instead of every time checking before writing every
2149    // component of cell
2150    if (cell instanceof ByteBufferExtendedCell) {
2151      out.writeShort(rowLen);
2152      ByteBufferUtils.copyBufferToStream(out, ((ByteBufferExtendedCell) cell).getRowByteBuffer(),
2153        ((ByteBufferExtendedCell) cell).getRowPosition(), rowLen);
2154      out.writeByte(fLen);
2155      ByteBufferUtils.copyBufferToStream(out, ((ByteBufferExtendedCell) cell).getFamilyByteBuffer(),
2156        ((ByteBufferExtendedCell) cell).getFamilyPosition(), fLen);
2157      ByteBufferUtils
2158        .copyBufferToStream(out, ((ByteBufferExtendedCell) cell).getQualifierByteBuffer(),
2159          ((ByteBufferExtendedCell) cell).getQualifierPosition(), qLen);
2160    } else {
2161      out.writeShort(rowLen);
2162      out.write(cell.getRowArray(), cell.getRowOffset(), rowLen);
2163      out.writeByte(fLen);
2164      out.write(cell.getFamilyArray(), cell.getFamilyOffset(), fLen);
2165      out.write(cell.getQualifierArray(), cell.getQualifierOffset(), qLen);
2166    }
2167    out.writeLong(cell.getTimestamp());
2168    out.writeByte(cell.getTypeByte());
2169  }
2170
2171  /**
2172   * Deep clones the given cell if the cell supports deep cloning
2173   * @param cell the cell to be cloned
2174   * @return the cloned cell
2175   * @throws CloneNotSupportedException
2176   */
2177  public static Cell deepClone(Cell cell) throws CloneNotSupportedException {
2178    if (cell instanceof ExtendedCell) {
2179      return ((ExtendedCell) cell).deepClone();
2180    }
2181    throw new CloneNotSupportedException();
2182  }
2183
2184  /**
2185   * Writes the cell to the given OutputStream
2186   * @param cell the cell to be written
2187   * @param out the outputstream
2188   * @param withTags if tags are to be written or not
2189   * @return the total bytes written
2190   * @throws IOException
2191   */
2192  public static int writeCell(Cell cell, OutputStream out, boolean withTags) throws IOException {
2193    if (cell instanceof ExtendedCell) {
2194      return ((ExtendedCell) cell).write(out, withTags);
2195    } else {
2196      ByteBufferUtils.putInt(out, estimatedSerializedSizeOfKey(cell));
2197      ByteBufferUtils.putInt(out, cell.getValueLength());
2198      writeFlatKey(cell, out);
2199      writeValue(out, cell, cell.getValueLength());
2200      int tagsLength = cell.getTagsLength();
2201      if (withTags) {
2202        byte[] len = new byte[Bytes.SIZEOF_SHORT];
2203        Bytes.putAsShort(len, 0, tagsLength);
2204        out.write(len);
2205        if (tagsLength > 0) {
2206          writeTags(out, cell, tagsLength);
2207        }
2208      }
2209      int lenWritten = (2 * Bytes.SIZEOF_INT) + estimatedSerializedSizeOfKey(cell)
2210          + cell.getValueLength();
2211      if (withTags) {
2212        lenWritten += Bytes.SIZEOF_SHORT + tagsLength;
2213      }
2214      return lenWritten;
2215    }
2216  }
2217
2218  /**
2219   * Writes a cell to the buffer at the given offset
2220   * @param cell the cell to be written
2221   * @param buf the buffer to which the cell has to be wrriten
2222   * @param offset the offset at which the cell should be written
2223   */
2224  public static void writeCellToBuffer(Cell cell, ByteBuffer buf, int offset) {
2225    if (cell instanceof ExtendedCell) {
2226      ((ExtendedCell) cell).write(buf, offset);
2227    } else {
2228      // Using the KVUtil
2229      byte[] bytes = KeyValueUtil.copyToNewByteArray(cell);
2230      ByteBufferUtils.copyFromArrayToBuffer(buf, offset, bytes, 0, bytes.length);
2231    }
2232  }
2233
2234  public static int writeFlatKey(Cell cell, OutputStream out) throws IOException {
2235    short rowLen = cell.getRowLength();
2236    byte fLen = cell.getFamilyLength();
2237    int qLen = cell.getQualifierLength();
2238    // Using just one if/else loop instead of every time checking before writing every
2239    // component of cell
2240    if (cell instanceof ByteBufferExtendedCell) {
2241      StreamUtils.writeShort(out, rowLen);
2242      ByteBufferUtils.copyBufferToStream(out, ((ByteBufferExtendedCell) cell).getRowByteBuffer(),
2243        ((ByteBufferExtendedCell) cell).getRowPosition(), rowLen);
2244      out.write(fLen);
2245      ByteBufferUtils.copyBufferToStream(out, ((ByteBufferExtendedCell) cell).getFamilyByteBuffer(),
2246        ((ByteBufferExtendedCell) cell).getFamilyPosition(), fLen);
2247      ByteBufferUtils
2248        .copyBufferToStream(out, ((ByteBufferExtendedCell) cell).getQualifierByteBuffer(),
2249          ((ByteBufferExtendedCell) cell).getQualifierPosition(), qLen);
2250    } else {
2251      StreamUtils.writeShort(out, rowLen);
2252      out.write(cell.getRowArray(), cell.getRowOffset(), rowLen);
2253      out.write(fLen);
2254      out.write(cell.getFamilyArray(), cell.getFamilyOffset(), fLen);
2255      out.write(cell.getQualifierArray(), cell.getQualifierOffset(), qLen);
2256    }
2257    StreamUtils.writeLong(out, cell.getTimestamp());
2258    out.write(cell.getTypeByte());
2259    return Bytes.SIZEOF_SHORT + rowLen + Bytes.SIZEOF_BYTE + fLen + qLen + Bytes.SIZEOF_LONG
2260      + Bytes.SIZEOF_BYTE;
2261  }
2262
2263  /**
2264   * Sets the given seqId to the cell. Marked as audience Private as of 1.2.0. Setting a Cell
2265   * sequenceid is an internal implementation detail not for general public use.
2266   * @param cell
2267   * @param seqId
2268   * @throws IOException when the passed cell is not of type {@link ExtendedCell}
2269   */
2270  public static void setSequenceId(Cell cell, long seqId) throws IOException {
2271    if (cell instanceof ExtendedCell) {
2272      ((ExtendedCell) cell).setSequenceId(seqId);
2273    } else {
2274      throw new IOException(new UnsupportedOperationException(
2275          "Cell is not of type " + ExtendedCell.class.getName()));
2276    }
2277  }
2278
2279  /**
2280   * Sets the given timestamp to the cell.
2281   * @param cell
2282   * @param ts
2283   * @throws IOException when the passed cell is not of type {@link ExtendedCell}
2284   */
2285  public static void setTimestamp(Cell cell, long ts) throws IOException {
2286    if (cell instanceof ExtendedCell) {
2287      ((ExtendedCell) cell).setTimestamp(ts);
2288    } else {
2289      throw new IOException(new UnsupportedOperationException(
2290          "Cell is not of type " + ExtendedCell.class.getName()));
2291    }
2292  }
2293
2294  /**
2295   * Sets the given timestamp to the cell.
2296   * @param cell
2297   * @param ts buffer containing the timestamp value
2298   * @throws IOException when the passed cell is not of type {@link ExtendedCell}
2299   */
2300  public static void setTimestamp(Cell cell, byte[] ts) throws IOException {
2301    if (cell instanceof ExtendedCell) {
2302      ((ExtendedCell) cell).setTimestamp(ts);
2303    } else {
2304      throw new IOException(new UnsupportedOperationException(
2305          "Cell is not of type " + ExtendedCell.class.getName()));
2306    }
2307  }
2308
2309  /**
2310   * Sets the given timestamp to the cell iff current timestamp is
2311   * {@link HConstants#LATEST_TIMESTAMP}.
2312   * @param cell
2313   * @param ts
2314   * @return True if cell timestamp is modified.
2315   * @throws IOException when the passed cell is not of type {@link ExtendedCell}
2316   */
2317  public static boolean updateLatestStamp(Cell cell, long ts) throws IOException {
2318    if (cell.getTimestamp() == HConstants.LATEST_TIMESTAMP) {
2319      setTimestamp(cell, ts);
2320      return true;
2321    }
2322    return false;
2323  }
2324
2325  /**
2326   * Sets the given timestamp to the cell iff current timestamp is
2327   * {@link HConstants#LATEST_TIMESTAMP}.
2328   * @param cell
2329   * @param ts buffer containing the timestamp value
2330   * @return True if cell timestamp is modified.
2331   * @throws IOException when the passed cell is not of type {@link ExtendedCell}
2332   */
2333  public static boolean updateLatestStamp(Cell cell, byte[] ts) throws IOException {
2334    if (cell.getTimestamp() == HConstants.LATEST_TIMESTAMP) {
2335      setTimestamp(cell, ts);
2336      return true;
2337    }
2338    return false;
2339  }
2340
2341  /**
2342   * Writes the row from the given cell to the output stream
2343   * @param out The outputstream to which the data has to be written
2344   * @param cell The cell whose contents has to be written
2345   * @param rlength the row length
2346   * @throws IOException
2347   */
2348  public static void writeRow(OutputStream out, Cell cell, short rlength) throws IOException {
2349    if (cell instanceof ByteBufferExtendedCell) {
2350      ByteBufferUtils.copyBufferToStream(out, ((ByteBufferExtendedCell) cell).getRowByteBuffer(),
2351        ((ByteBufferExtendedCell) cell).getRowPosition(), rlength);
2352    } else {
2353      out.write(cell.getRowArray(), cell.getRowOffset(), rlength);
2354    }
2355  }
2356
2357  /**
2358   * Writes the family from the given cell to the output stream
2359   * @param out The outputstream to which the data has to be written
2360   * @param cell The cell whose contents has to be written
2361   * @param flength the family length
2362   * @throws IOException
2363   */
2364  public static void writeFamily(OutputStream out, Cell cell, byte flength) throws IOException {
2365    if (cell instanceof ByteBufferExtendedCell) {
2366      ByteBufferUtils.copyBufferToStream(out, ((ByteBufferExtendedCell) cell).getFamilyByteBuffer(),
2367        ((ByteBufferExtendedCell) cell).getFamilyPosition(), flength);
2368    } else {
2369      out.write(cell.getFamilyArray(), cell.getFamilyOffset(), flength);
2370    }
2371  }
2372
2373  /**
2374   * Writes the qualifier from the given cell to the output stream
2375   * @param out The outputstream to which the data has to be written
2376   * @param cell The cell whose contents has to be written
2377   * @param qlength the qualifier length
2378   * @throws IOException
2379   */
2380  public static void writeQualifier(OutputStream out, Cell cell, int qlength) throws IOException {
2381    if (cell instanceof ByteBufferExtendedCell) {
2382      ByteBufferUtils
2383        .copyBufferToStream(out, ((ByteBufferExtendedCell) cell).getQualifierByteBuffer(),
2384          ((ByteBufferExtendedCell) cell).getQualifierPosition(), qlength);
2385    } else {
2386      out.write(cell.getQualifierArray(), cell.getQualifierOffset(), qlength);
2387    }
2388  }
2389
2390  /**
2391   * Writes the qualifier from the given cell to the output stream excluding the common prefix
2392   * @param out The dataoutputstream to which the data has to be written
2393   * @param cell The cell whose contents has to be written
2394   * @param qlength the qualifier length
2395   * @throws IOException
2396   */
2397  public static void writeQualifierSkippingBytes(DataOutputStream out, Cell cell, int qlength,
2398      int commonPrefix) throws IOException {
2399    if (cell instanceof ByteBufferExtendedCell) {
2400      ByteBufferUtils.copyBufferToStream((DataOutput) out,
2401          ((ByteBufferExtendedCell) cell).getQualifierByteBuffer(),
2402          ((ByteBufferExtendedCell) cell).getQualifierPosition() + commonPrefix,
2403          qlength - commonPrefix);
2404    } else {
2405      out.write(cell.getQualifierArray(), cell.getQualifierOffset() + commonPrefix,
2406          qlength - commonPrefix);
2407    }
2408  }
2409
2410  /**
2411   * Writes the value from the given cell to the output stream
2412   * @param out The outputstream to which the data has to be written
2413   * @param cell The cell whose contents has to be written
2414   * @param vlength the value length
2415   * @throws IOException
2416   */
2417  public static void writeValue(OutputStream out, Cell cell, int vlength) throws IOException {
2418    if (cell instanceof ByteBufferExtendedCell) {
2419      ByteBufferUtils.copyBufferToStream(out, ((ByteBufferExtendedCell) cell).getValueByteBuffer(),
2420        ((ByteBufferExtendedCell) cell).getValuePosition(), vlength);
2421    } else {
2422      out.write(cell.getValueArray(), cell.getValueOffset(), vlength);
2423    }
2424  }
2425
2426  /**
2427   * Writes the tag from the given cell to the output stream
2428   * @param out The outputstream to which the data has to be written
2429   * @param cell The cell whose contents has to be written
2430   * @param tagsLength the tag length
2431   * @throws IOException
2432   */
2433  public static void writeTags(OutputStream out, Cell cell, int tagsLength) throws IOException {
2434    if (cell instanceof ByteBufferExtendedCell) {
2435      ByteBufferUtils.copyBufferToStream(out, ((ByteBufferExtendedCell) cell).getTagsByteBuffer(),
2436        ((ByteBufferExtendedCell) cell).getTagsPosition(), tagsLength);
2437    } else {
2438      out.write(cell.getTagsArray(), cell.getTagsOffset(), tagsLength);
2439    }
2440  }
2441
2442  /**
2443   * special case for Cell.equals
2444   */
2445  public static boolean equalsIgnoreMvccVersion(Cell a, Cell b) {
2446    // row
2447    boolean res = CellUtil.matchingRows(a, b);
2448    if (!res) return res;
2449
2450    // family
2451    res = CellUtil.matchingColumn(a, b);
2452    if (!res) return res;
2453
2454    // timestamp: later sorts first
2455    if (!CellUtil.matchingTimestamp(a, b)) return false;
2456
2457    // type
2458    int c = (0xff & b.getTypeByte()) - (0xff & a.getTypeByte());
2459    if (c != 0) return false;
2460    else return true;
2461  }
2462
2463  /**
2464   * Converts the rowkey bytes of the given cell into an int value
2465   * @param cell
2466   * @return rowkey as int
2467   */
2468  public static int getRowAsInt(Cell cell) {
2469    if (cell instanceof ByteBufferExtendedCell) {
2470      return ByteBufferUtils.toInt(((ByteBufferExtendedCell) cell).getRowByteBuffer(),
2471        ((ByteBufferExtendedCell) cell).getRowPosition());
2472    }
2473    return Bytes.toInt(cell.getRowArray(), cell.getRowOffset());
2474  }
2475
2476  /**
2477   * Converts the value bytes of the given cell into a long value
2478   * @param cell
2479   * @return value as long
2480   */
2481  public static long getValueAsLong(Cell cell) {
2482    if (cell instanceof ByteBufferExtendedCell) {
2483      return ByteBufferUtils.toLong(((ByteBufferExtendedCell) cell).getValueByteBuffer(),
2484        ((ByteBufferExtendedCell) cell).getValuePosition());
2485    }
2486    return Bytes.toLong(cell.getValueArray(), cell.getValueOffset());
2487  }
2488
2489  /**
2490   * Converts the value bytes of the given cell into a int value
2491   * @param cell
2492   * @return value as int
2493   */
2494  public static int getValueAsInt(Cell cell) {
2495    if (cell instanceof ByteBufferExtendedCell) {
2496      return ByteBufferUtils.toInt(((ByteBufferExtendedCell) cell).getValueByteBuffer(),
2497        ((ByteBufferExtendedCell) cell).getValuePosition());
2498    }
2499    return Bytes.toInt(cell.getValueArray(), cell.getValueOffset());
2500  }
2501
2502  /**
2503   * Converts the value bytes of the given cell into a double value
2504   * @param cell
2505   * @return value as double
2506   */
2507  public static double getValueAsDouble(Cell cell) {
2508    if (cell instanceof ByteBufferExtendedCell) {
2509      return ByteBufferUtils.toDouble(((ByteBufferExtendedCell) cell).getValueByteBuffer(),
2510        ((ByteBufferExtendedCell) cell).getValuePosition());
2511    }
2512    return Bytes.toDouble(cell.getValueArray(), cell.getValueOffset());
2513  }
2514
2515  /**
2516   * Converts the value bytes of the given cell into a BigDecimal
2517   * @param cell
2518   * @return value as BigDecimal
2519   */
2520  public static BigDecimal getValueAsBigDecimal(Cell cell) {
2521    if (cell instanceof ByteBufferExtendedCell) {
2522      return ByteBufferUtils.toBigDecimal(((ByteBufferExtendedCell) cell).getValueByteBuffer(),
2523        ((ByteBufferExtendedCell) cell).getValuePosition(), cell.getValueLength());
2524    }
2525    return Bytes.toBigDecimal(cell.getValueArray(), cell.getValueOffset(), cell.getValueLength());
2526  }
2527
2528  /**
2529   * Compresses the tags to the given outputstream using the TagcompressionContext
2530   * @param out the outputstream to which the compression should happen
2531   * @param cell the cell which has tags
2532   * @param tagCompressionContext the TagCompressionContext
2533   * @throws IOException can throw IOException if the compression encounters issue
2534   */
2535  public static void compressTags(OutputStream out, Cell cell,
2536      TagCompressionContext tagCompressionContext) throws IOException {
2537    if (cell instanceof ByteBufferExtendedCell) {
2538      tagCompressionContext.compressTags(out, ((ByteBufferExtendedCell) cell).getTagsByteBuffer(),
2539        ((ByteBufferExtendedCell) cell).getTagsPosition(), cell.getTagsLength());
2540    } else {
2541      tagCompressionContext.compressTags(out, cell.getTagsArray(), cell.getTagsOffset(),
2542        cell.getTagsLength());
2543    }
2544  }
2545
2546  public static void compressRow(OutputStream out, Cell cell, Dictionary dict) throws IOException {
2547    if (cell instanceof ByteBufferExtendedCell) {
2548      Dictionary.write(out, ((ByteBufferExtendedCell) cell).getRowByteBuffer(),
2549        ((ByteBufferExtendedCell) cell).getRowPosition(), cell.getRowLength(), dict);
2550    } else {
2551      Dictionary.write(out, cell.getRowArray(), cell.getRowOffset(), cell.getRowLength(), dict);
2552    }
2553  }
2554
2555  public static void compressFamily(OutputStream out, Cell cell, Dictionary dict)
2556      throws IOException {
2557    if (cell instanceof ByteBufferExtendedCell) {
2558      Dictionary.write(out, ((ByteBufferExtendedCell) cell).getFamilyByteBuffer(),
2559        ((ByteBufferExtendedCell) cell).getFamilyPosition(), cell.getFamilyLength(), dict);
2560    } else {
2561      Dictionary.write(out, cell.getFamilyArray(), cell.getFamilyOffset(), cell.getFamilyLength(),
2562        dict);
2563    }
2564  }
2565
2566  public static void compressQualifier(OutputStream out, Cell cell, Dictionary dict)
2567      throws IOException {
2568    if (cell instanceof ByteBufferExtendedCell) {
2569      Dictionary.write(out, ((ByteBufferExtendedCell) cell).getQualifierByteBuffer(),
2570        ((ByteBufferExtendedCell) cell).getQualifierPosition(), cell.getQualifierLength(), dict);
2571    } else {
2572      Dictionary.write(out, cell.getQualifierArray(), cell.getQualifierOffset(),
2573        cell.getQualifierLength(), dict);
2574    }
2575  }
2576
2577  /**
2578   * Used when a cell needs to be compared with a key byte[] such as cases of finding the index from
2579   * the index block, bloom keys from the bloom blocks This byte[] is expected to be serialized in
2580   * the KeyValue serialization format If the KeyValue (Cell's) serialization format changes this
2581   * method cannot be used.
2582   * @param comparator the cell comparator
2583   * @param left the cell to be compared
2584   * @param key the serialized key part of a KeyValue
2585   * @param offset the offset in the key byte[]
2586   * @param length the length of the key byte[]
2587   * @return an int greater than 0 if left is greater than right lesser than 0 if left is lesser
2588   *         than right equal to 0 if left is equal to right
2589   */
2590  @VisibleForTesting
2591  public static final int compare(CellComparator comparator, Cell left, byte[] key, int offset,
2592      int length) {
2593    // row
2594    short rrowlength = Bytes.toShort(key, offset);
2595    int c = comparator.compareRows(left, key, offset + Bytes.SIZEOF_SHORT, rrowlength);
2596    if (c != 0) return c;
2597
2598    // Compare the rest of the two KVs without making any assumptions about
2599    // the common prefix. This function will not compare rows anyway, so we
2600    // don't need to tell it that the common prefix includes the row.
2601    return compareWithoutRow(comparator, left, key, offset, length, rrowlength);
2602  }
2603
2604  /**
2605   * Compare columnFamily, qualifier, timestamp, and key type (everything except the row). This
2606   * method is used both in the normal comparator and the "same-prefix" comparator. Note that we are
2607   * assuming that row portions of both KVs have already been parsed and found identical, and we
2608   * don't validate that assumption here.
2609   * @param commonPrefix the length of the common prefix of the two key-values being compared,
2610   *          including row length and row
2611   */
2612  static final int compareWithoutRow(CellComparator comparator, Cell left, byte[] right,
2613      int roffset, int rlength, short rowlength) {
2614    /***
2615     * KeyValue Format and commonLength:
2616     * |_keyLen_|_valLen_|_rowLen_|_rowKey_|_famiLen_|_fami_|_Quali_|....
2617     * ------------------|-------commonLength--------|--------------
2618     */
2619    int commonLength = KeyValue.ROW_LENGTH_SIZE + KeyValue.FAMILY_LENGTH_SIZE + rowlength;
2620
2621    // commonLength + TIMESTAMP_TYPE_SIZE
2622    int commonLengthWithTSAndType = KeyValue.TIMESTAMP_TYPE_SIZE + commonLength;
2623    // ColumnFamily + Qualifier length.
2624    int lcolumnlength = left.getFamilyLength() + left.getQualifierLength();
2625    int rcolumnlength = rlength - commonLengthWithTSAndType;
2626
2627    byte ltype = left.getTypeByte();
2628    byte rtype = right[roffset + (rlength - 1)];
2629
2630    // If the column is not specified, the "minimum" key type appears the
2631    // latest in the sorted order, regardless of the timestamp. This is used
2632    // for specifying the last key/value in a given row, because there is no
2633    // "lexicographically last column" (it would be infinitely long). The
2634    // "maximum" key type does not need this behavior.
2635    if (lcolumnlength == 0 && ltype == KeyValue.Type.Minimum.getCode()) {
2636      // left is "bigger", i.e. it appears later in the sorted order
2637      return 1;
2638    }
2639    if (rcolumnlength == 0 && rtype == KeyValue.Type.Minimum.getCode()) {
2640      return -1;
2641    }
2642
2643    int rfamilyoffset = commonLength + roffset;
2644
2645    // Column family length.
2646    int lfamilylength = left.getFamilyLength();
2647    int rfamilylength = right[rfamilyoffset - 1];
2648    // If left family size is not equal to right family size, we need not
2649    // compare the qualifiers.
2650    boolean sameFamilySize = (lfamilylength == rfamilylength);
2651    if (!sameFamilySize) {
2652      // comparing column family is enough.
2653      return CellUtil.compareFamilies(left, right, rfamilyoffset, rfamilylength);
2654    }
2655    // Compare family & qualifier together.
2656    // Families are same. Compare on qualifiers.
2657    int comparison = CellUtil.compareColumns(left, right, rfamilyoffset, rfamilylength,
2658      rfamilyoffset + rfamilylength, (rcolumnlength - rfamilylength));
2659    if (comparison != 0) {
2660      return comparison;
2661    }
2662
2663    // //
2664    // Next compare timestamps.
2665    long rtimestamp = Bytes.toLong(right, roffset + (rlength - KeyValue.TIMESTAMP_TYPE_SIZE));
2666    int compare = comparator.compareTimestamps(left.getTimestamp(), rtimestamp);
2667    if (compare != 0) {
2668      return compare;
2669    }
2670
2671    // Compare types. Let the delete types sort ahead of puts; i.e. types
2672    // of higher numbers sort before those of lesser numbers. Maximum (255)
2673    // appears ahead of everything, and minimum (0) appears after
2674    // everything.
2675    return (0xff & rtype) - (0xff & ltype);
2676  }
2677
2678  /**
2679   * @return An new cell is located following input cell. If both of type and timestamp are minimum,
2680   *         the input cell will be returned directly.
2681   */
2682  public static Cell createNextOnRowCol(Cell cell) {
2683    long ts = cell.getTimestamp();
2684    byte type = cell.getTypeByte();
2685    if (type != KeyValue.Type.Minimum.getCode()) {
2686      type = KeyValue.Type.values()[KeyValue.Type.codeToType(type).ordinal() - 1].getCode();
2687    } else if (ts != HConstants.OLDEST_TIMESTAMP) {
2688      ts = ts - 1;
2689      type = KeyValue.Type.Maximum.getCode();
2690    } else {
2691      return cell;
2692    }
2693    return createNextOnRowCol(cell, ts, type);
2694  }
2695
2696  static Cell createNextOnRowCol(Cell cell, long ts, byte type) {
2697    if (cell instanceof ByteBufferExtendedCell) {
2698      return new LastOnRowColByteBufferExtendedCell(
2699          ((ByteBufferExtendedCell) cell).getRowByteBuffer(),
2700          ((ByteBufferExtendedCell) cell).getRowPosition(), cell.getRowLength(),
2701          ((ByteBufferExtendedCell) cell).getFamilyByteBuffer(),
2702          ((ByteBufferExtendedCell) cell).getFamilyPosition(), cell.getFamilyLength(),
2703          ((ByteBufferExtendedCell) cell).getQualifierByteBuffer(),
2704          ((ByteBufferExtendedCell) cell).getQualifierPosition(), cell.getQualifierLength()) {
2705        @Override
2706        public long getTimestamp() {
2707          return ts;
2708        }
2709
2710        @Override
2711        public byte getTypeByte() {
2712          return type;
2713        }
2714      };
2715    }
2716    return new LastOnRowColCell(cell.getRowArray(), cell.getRowOffset(), cell.getRowLength(),
2717        cell.getFamilyArray(), cell.getFamilyOffset(), cell.getFamilyLength(),
2718        cell.getQualifierArray(), cell.getQualifierOffset(), cell.getQualifierLength()) {
2719      @Override
2720      public long getTimestamp() {
2721        return ts;
2722      }
2723
2724      @Override
2725      public byte getTypeByte() {
2726        return type;
2727      }
2728    };
2729  }
2730
2731  /**
2732   * Estimate based on keyvalue's serialization format in the RPC layer. Note that there is an extra
2733   * SIZEOF_INT added to the size here that indicates the actual length of the cell for cases where
2734   * cell's are serialized in a contiguous format (For eg in RPCs).
2735   * @param cell
2736   * @return Estimate of the <code>cell</code> size in bytes plus an extra SIZEOF_INT indicating the
2737   *         actual cell length.
2738   */
2739  public static int estimatedSerializedSizeOf(final Cell cell) {
2740    if (cell instanceof ExtendedCell) {
2741      return ((ExtendedCell) cell).getSerializedSize(true) + Bytes.SIZEOF_INT;
2742    }
2743
2744    return getSumOfCellElementLengths(cell) +
2745    // Use the KeyValue's infrastructure size presuming that another implementation would have
2746    // same basic cost.
2747        KeyValue.ROW_LENGTH_SIZE + KeyValue.FAMILY_LENGTH_SIZE +
2748        // Serialization is probably preceded by a length (it is in the KeyValueCodec at least).
2749        Bytes.SIZEOF_INT;
2750  }
2751
2752  /**
2753   * @param cell
2754   * @return Sum of the lengths of all the elements in a Cell; does not count in any infrastructure
2755   */
2756  private static int getSumOfCellElementLengths(final Cell cell) {
2757    return getSumOfCellKeyElementLengths(cell) + cell.getValueLength() + cell.getTagsLength();
2758  }
2759
2760  /**
2761   * @param cell
2762   * @return Sum of all elements that make up a key; does not include infrastructure, tags or
2763   *         values.
2764   */
2765  private static int getSumOfCellKeyElementLengths(final Cell cell) {
2766    return cell.getRowLength() + cell.getFamilyLength() + cell.getQualifierLength()
2767        + KeyValue.TIMESTAMP_TYPE_SIZE;
2768  }
2769
2770  /**
2771   * Calculates the serialized key size. We always serialize in the KeyValue's serialization format.
2772   * @param cell the cell for which the key size has to be calculated.
2773   * @return the key size
2774   */
2775  public static int estimatedSerializedSizeOfKey(final Cell cell) {
2776    if (cell instanceof KeyValue) return ((KeyValue) cell).getKeyLength();
2777    return cell.getRowLength() + cell.getFamilyLength() + cell.getQualifierLength()
2778        + KeyValue.KEY_INFRASTRUCTURE_SIZE;
2779  }
2780
2781  /**
2782   * This is an estimate of the heap space occupied by a cell. When the cell is of type
2783   * {@link HeapSize} we call {@link HeapSize#heapSize()} so cell can give a correct value. In other
2784   * cases we just consider the bytes occupied by the cell components ie. row, CF, qualifier,
2785   * timestamp, type, value and tags.
2786   * Note that this can be the JVM heap space (on-heap) or the OS heap (off-heap)
2787   * @param cell
2788   * @return estimate of the heap space
2789   */
2790  public static long estimatedSizeOfCell(final Cell cell) {
2791    if (cell instanceof HeapSize) {
2792      return ((HeapSize) cell).heapSize();
2793    }
2794    // TODO: Add sizing of references that hold the row, family, etc., arrays.
2795    return estimatedSerializedSizeOf(cell);
2796  }
2797
2798  /**
2799   * This method exists just to encapsulate how we serialize keys. To be replaced by a factory that
2800   * we query to figure what the Cell implementation is and then, what serialization engine to use
2801   * and further, how to serialize the key for inclusion in hfile index. TODO.
2802   * @param cell
2803   * @return The key portion of the Cell serialized in the old-school KeyValue way or null if passed
2804   *         a null <code>cell</code>
2805   */
2806  public static byte[] getCellKeySerializedAsKeyValueKey(final Cell cell) {
2807    if (cell == null) return null;
2808    byte[] b = new byte[KeyValueUtil.keyLength(cell)];
2809    KeyValueUtil.appendKeyTo(cell, b, 0);
2810    return b;
2811  }
2812
2813  /**
2814   * Create a Cell that is smaller than all other possible Cells for the given Cell's row.
2815   * @param cell
2816   * @return First possible Cell on passed Cell's row.
2817   */
2818  public static Cell createFirstOnRow(final Cell cell) {
2819    if (cell instanceof ByteBufferExtendedCell) {
2820      return new FirstOnRowByteBufferExtendedCell(
2821          ((ByteBufferExtendedCell) cell).getRowByteBuffer(),
2822          ((ByteBufferExtendedCell) cell).getRowPosition(), cell.getRowLength());
2823    }
2824    return new FirstOnRowCell(cell.getRowArray(), cell.getRowOffset(), cell.getRowLength());
2825  }
2826
2827  public static Cell createFirstOnRow(final byte[] row, int roffset, short rlength) {
2828    return new FirstOnRowCell(row, roffset, rlength);
2829  }
2830
2831  public static Cell createFirstOnRow(final byte[] row, final byte[] family, final byte[] col) {
2832    return createFirstOnRow(row, 0, (short) row.length, family, 0, (byte) family.length, col, 0,
2833        col.length);
2834  }
2835
2836  public static Cell createFirstOnRow(final byte[] row, int roffset, short rlength,
2837      final byte[] family, int foffset, byte flength, final byte[] col, int coffset, int clength) {
2838    return new FirstOnRowColCell(row, roffset, rlength, family, foffset, flength, col, coffset,
2839        clength);
2840  }
2841
2842  public static Cell createFirstOnRow(final byte[] row) {
2843    return createFirstOnRow(row, 0, (short) row.length);
2844  }
2845
2846  public static Cell createFirstOnRowFamily(Cell cell, byte[] fArray, int foff, int flen) {
2847    if (cell instanceof ByteBufferExtendedCell) {
2848      return new FirstOnRowColByteBufferExtendedCell(
2849        ((ByteBufferExtendedCell) cell).getRowByteBuffer(),
2850        ((ByteBufferExtendedCell) cell).getRowPosition(), cell.getRowLength(),
2851        ByteBuffer.wrap(fArray), foff, (byte) flen, HConstants.EMPTY_BYTE_BUFFER, 0, 0);
2852    }
2853    return new FirstOnRowColCell(cell.getRowArray(), cell.getRowOffset(), cell.getRowLength(),
2854      fArray, foff, (byte) flen, HConstants.EMPTY_BYTE_ARRAY, 0, 0);
2855  }
2856
2857  public static Cell createFirstOnRowCol(final Cell cell) {
2858    if (cell instanceof ByteBufferExtendedCell) {
2859      return new FirstOnRowColByteBufferExtendedCell(
2860          ((ByteBufferExtendedCell) cell).getRowByteBuffer(),
2861          ((ByteBufferExtendedCell) cell).getRowPosition(), cell.getRowLength(),
2862          HConstants.EMPTY_BYTE_BUFFER, 0, (byte) 0,
2863          ((ByteBufferExtendedCell) cell).getQualifierByteBuffer(),
2864          ((ByteBufferExtendedCell) cell).getQualifierPosition(), cell.getQualifierLength());
2865    }
2866    return new FirstOnRowColCell(cell.getRowArray(), cell.getRowOffset(), cell.getRowLength(),
2867        HConstants.EMPTY_BYTE_ARRAY, 0, (byte) 0, cell.getQualifierArray(),
2868        cell.getQualifierOffset(), cell.getQualifierLength());
2869  }
2870
2871  public static Cell createFirstOnNextRow(final Cell cell) {
2872    byte[] nextRow = new byte[cell.getRowLength() + 1];
2873    CellUtil.copyRowTo(cell, nextRow, 0);
2874    nextRow[nextRow.length - 1] = 0;// maybe not necessary
2875    return new FirstOnRowCell(nextRow, 0, (short) nextRow.length);
2876  }
2877
2878  /**
2879   * Create a Cell that is smaller than all other possible Cells for the given Cell's rk:cf and
2880   * passed qualifier.
2881   * @param cell
2882   * @param qArray
2883   * @param qoffest
2884   * @param qlength
2885   * @return Last possible Cell on passed Cell's rk:cf and passed qualifier.
2886   */
2887  public static Cell createFirstOnRowCol(final Cell cell, byte[] qArray, int qoffest, int qlength) {
2888    if (cell instanceof ByteBufferExtendedCell) {
2889      return new FirstOnRowColByteBufferExtendedCell(
2890          ((ByteBufferExtendedCell) cell).getRowByteBuffer(),
2891          ((ByteBufferExtendedCell) cell).getRowPosition(), cell.getRowLength(),
2892          ((ByteBufferExtendedCell) cell).getFamilyByteBuffer(),
2893          ((ByteBufferExtendedCell) cell).getFamilyPosition(), cell.getFamilyLength(),
2894          ByteBuffer.wrap(qArray), qoffest, qlength);
2895    }
2896    return new FirstOnRowColCell(cell.getRowArray(), cell.getRowOffset(), cell.getRowLength(),
2897        cell.getFamilyArray(), cell.getFamilyOffset(), cell.getFamilyLength(), qArray, qoffest,
2898        qlength);
2899  }
2900
2901  /**
2902   * Creates the first cell with the row/family/qualifier of this cell and the given timestamp. Uses
2903   * the "maximum" type that guarantees that the new cell is the lowest possible for this
2904   * combination of row, family, qualifier, and timestamp. This cell's own timestamp is ignored.
2905   * @param cell - cell
2906   * @param ts
2907   */
2908  public static Cell createFirstOnRowColTS(Cell cell, long ts) {
2909    if (cell instanceof ByteBufferExtendedCell) {
2910      return new FirstOnRowColTSByteBufferExtendedCell(
2911          ((ByteBufferExtendedCell) cell).getRowByteBuffer(),
2912          ((ByteBufferExtendedCell) cell).getRowPosition(), cell.getRowLength(),
2913          ((ByteBufferExtendedCell) cell).getFamilyByteBuffer(),
2914          ((ByteBufferExtendedCell) cell).getFamilyPosition(), cell.getFamilyLength(),
2915          ((ByteBufferExtendedCell) cell).getQualifierByteBuffer(),
2916          ((ByteBufferExtendedCell) cell).getQualifierPosition(), cell.getQualifierLength(), ts);
2917    }
2918    return new FirstOnRowColTSCell(cell.getRowArray(), cell.getRowOffset(), cell.getRowLength(),
2919        cell.getFamilyArray(), cell.getFamilyOffset(), cell.getFamilyLength(),
2920        cell.getQualifierArray(), cell.getQualifierOffset(), cell.getQualifierLength(), ts);
2921  }
2922
2923  /**
2924   * Create a Cell that is larger than all other possible Cells for the given Cell's row.
2925   * @param cell
2926   * @return Last possible Cell on passed Cell's row.
2927   */
2928  public static Cell createLastOnRow(final Cell cell) {
2929    if (cell instanceof ByteBufferExtendedCell) {
2930      return new LastOnRowByteBufferExtendedCell(((ByteBufferExtendedCell) cell).getRowByteBuffer(),
2931          ((ByteBufferExtendedCell) cell).getRowPosition(), cell.getRowLength());
2932    }
2933    return new LastOnRowCell(cell.getRowArray(), cell.getRowOffset(), cell.getRowLength());
2934  }
2935
2936  public static Cell createLastOnRow(final byte[] row) {
2937    return new LastOnRowCell(row, 0, (short) row.length);
2938  }
2939
2940  /**
2941   * Create a Cell that is larger than all other possible Cells for the given Cell's rk:cf:q. Used
2942   * in creating "fake keys" for the multi-column Bloom filter optimization to skip the row/column
2943   * we already know is not in the file.
2944   * @param cell
2945   * @return Last possible Cell on passed Cell's rk:cf:q.
2946   */
2947  public static Cell createLastOnRowCol(final Cell cell) {
2948    if (cell instanceof ByteBufferExtendedCell) {
2949      return new LastOnRowColByteBufferExtendedCell(
2950          ((ByteBufferExtendedCell) cell).getRowByteBuffer(),
2951          ((ByteBufferExtendedCell) cell).getRowPosition(), cell.getRowLength(),
2952          ((ByteBufferExtendedCell) cell).getFamilyByteBuffer(),
2953          ((ByteBufferExtendedCell) cell).getFamilyPosition(), cell.getFamilyLength(),
2954          ((ByteBufferExtendedCell) cell).getQualifierByteBuffer(),
2955          ((ByteBufferExtendedCell) cell).getQualifierPosition(), cell.getQualifierLength());
2956    }
2957    return new LastOnRowColCell(cell.getRowArray(), cell.getRowOffset(), cell.getRowLength(),
2958        cell.getFamilyArray(), cell.getFamilyOffset(), cell.getFamilyLength(),
2959        cell.getQualifierArray(), cell.getQualifierOffset(), cell.getQualifierLength());
2960  }
2961
2962  /**
2963   * Create a Delete Family Cell for the specified row and family that would be smaller than all
2964   * other possible Delete Family KeyValues that have the same row and family. Used for seeking.
2965   * @param row - row key (arbitrary byte array)
2966   * @param fam - family name
2967   * @return First Delete Family possible key on passed <code>row</code>.
2968   */
2969  public static Cell createFirstDeleteFamilyCellOnRow(final byte[] row, final byte[] fam) {
2970    return new FirstOnRowDeleteFamilyCell(row, fam);
2971  }
2972}