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