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