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