001/**
002 * Copyright The Apache Software Foundation
003 *
004 * Licensed to the Apache Software Foundation (ASF) under one
005 * or more contributor license agreements.  See the NOTICE file
006 * distributed with this work for additional information
007 * regarding copyright ownership.  The ASF licenses this file
008 * to you under the Apache License, Version 2.0 (the
009 * "License"); you may not use this file except in compliance
010 * with the License.  You may obtain a copy of the License at
011 *
012 *     http://www.apache.org/licenses/LICENSE-2.0
013 *
014 * Unless required by applicable law or agreed to in writing, software
015 * distributed under the License is distributed on an "AS IS" BASIS,
016 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
017 * See the License for the specific language governing permissions and
018 * limitations under the License.
019 */
020package org.apache.hadoop.hbase;
021
022import static org.apache.hadoop.hbase.util.Bytes.len;
023
024import java.io.DataInput;
025import java.io.DataOutput;
026import java.io.IOException;
027import java.io.OutputStream;
028import java.nio.ByteBuffer;
029import java.util.ArrayList;
030import java.util.Arrays;
031import java.util.HashMap;
032import java.util.Iterator;
033import java.util.List;
034import java.util.Map;
035import org.apache.hadoop.hbase.util.ByteBufferUtils;
036import org.apache.hadoop.hbase.util.Bytes;
037import org.apache.hadoop.hbase.util.ClassSize;
038import org.apache.hadoop.io.RawComparator;
039import org.apache.yetus.audience.InterfaceAudience;
040import org.slf4j.Logger;
041import org.slf4j.LoggerFactory;
042
043import org.apache.hbase.thirdparty.com.google.common.annotations.VisibleForTesting;
044
045/**
046 * An HBase Key/Value. This is the fundamental HBase Type.
047 * <p>
048 * HBase applications and users should use the Cell interface and avoid directly using KeyValue and
049 * member functions not defined in Cell.
050 * <p>
051 * If being used client-side, the primary methods to access individual fields are
052 * {@link #getRowArray()}, {@link #getFamilyArray()}, {@link #getQualifierArray()},
053 * {@link #getTimestamp()}, and {@link #getValueArray()}. These methods allocate new byte arrays
054 * and return copies. Avoid their use server-side.
055 * <p>
056 * Instances of this class are immutable. They do not implement Comparable but Comparators are
057 * provided. Comparators change with context, whether user table or a catalog table comparison. Its
058 * critical you use the appropriate comparator. There are Comparators for normal HFiles, Meta's
059 * Hfiles, and bloom filter keys.
060 * <p>
061 * KeyValue wraps a byte array and takes offsets and lengths into passed array at where to start
062 * interpreting the content as KeyValue. The KeyValue format inside a byte array is:
063 * <code>&lt;keylength&gt; &lt;valuelength&gt; &lt;key&gt; &lt;value&gt;</code> Key is further
064 * decomposed as: <code>&lt;rowlength&gt; &lt;row&gt; &lt;columnfamilylength&gt;
065 * &lt;columnfamily&gt; &lt;columnqualifier&gt;
066 * &lt;timestamp&gt; &lt;keytype&gt;</code> The <code>rowlength</code> maximum is
067 * <code>Short.MAX_SIZE</code>, column family length maximum is <code>Byte.MAX_SIZE</code>, and
068 * column qualifier + key length must be &lt; <code>Integer.MAX_SIZE</code>. The column does not
069 * contain the family/qualifier delimiter, {@link #COLUMN_FAMILY_DELIMITER}<br>
070 * KeyValue can optionally contain Tags. When it contains tags, it is added in the byte array after
071 * the value part. The format for this part is: <code>&lt;tagslength&gt;&lt;tagsbytes&gt;</code>.
072 * <code>tagslength</code> maximum is <code>Short.MAX_SIZE</code>. The <code>tagsbytes</code>
073 * contain one or more tags where as each tag is of the form
074 * <code>&lt;taglength&gt;&lt;tagtype&gt;&lt;tagbytes&gt;</code>. <code>tagtype</code> is one byte
075 * and <code>taglength</code> maximum is <code>Short.MAX_SIZE</code> and it includes 1 byte type
076 * length and actual tag bytes length.
077 */
078@InterfaceAudience.Private
079public class KeyValue implements ExtendedCell, Cloneable {
080  private static final ArrayList<Tag> EMPTY_ARRAY_LIST = new ArrayList<>();
081
082  private static final Logger LOG = LoggerFactory.getLogger(KeyValue.class);
083
084  public static final int FIXED_OVERHEAD = ClassSize.OBJECT + // the KeyValue object itself
085      ClassSize.REFERENCE + // pointer to "bytes"
086      2 * Bytes.SIZEOF_INT + // offset, length
087      Bytes.SIZEOF_LONG;// memstoreTS
088
089  /**
090   * Colon character in UTF-8
091   */
092  public static final char COLUMN_FAMILY_DELIMITER = ':';
093
094  public static final byte[] COLUMN_FAMILY_DELIM_ARRAY =
095    new byte[]{COLUMN_FAMILY_DELIMITER};
096
097  /**
098   * Comparator for plain key/values; i.e. non-catalog table key/values. Works on Key portion
099   * of KeyValue only.
100   * @deprecated Use {@link CellComparator#getInstance()} instead. Deprecated for hbase 2.0, remove for hbase 3.0.
101   */
102  @Deprecated
103  public static final KVComparator COMPARATOR = new KVComparator();
104  /**
105   * A {@link KVComparator} for <code>hbase:meta</code> catalog table
106   * {@link KeyValue}s.
107   * @deprecated Use {@link MetaCellComparator#META_COMPARATOR} instead.
108   *   Deprecated for hbase 2.0, remove for hbase 3.0.
109   */
110  @Deprecated
111  public static final KVComparator META_COMPARATOR = new MetaComparator();
112
113  /** Size of the key length field in bytes*/
114  public static final int KEY_LENGTH_SIZE = Bytes.SIZEOF_INT;
115
116  /** Size of the key type field in bytes */
117  public static final int TYPE_SIZE = Bytes.SIZEOF_BYTE;
118
119  /** Size of the row length field in bytes */
120  public static final int ROW_LENGTH_SIZE = Bytes.SIZEOF_SHORT;
121
122  /** Size of the family length field in bytes */
123  public static final int FAMILY_LENGTH_SIZE = Bytes.SIZEOF_BYTE;
124
125  /** Size of the timestamp field in bytes */
126  public static final int TIMESTAMP_SIZE = Bytes.SIZEOF_LONG;
127
128  // Size of the timestamp and type byte on end of a key -- a long + a byte.
129  public static final int TIMESTAMP_TYPE_SIZE = TIMESTAMP_SIZE + TYPE_SIZE;
130
131  // Size of the length shorts and bytes in key.
132  public static final int KEY_INFRASTRUCTURE_SIZE = ROW_LENGTH_SIZE
133      + FAMILY_LENGTH_SIZE + TIMESTAMP_TYPE_SIZE;
134
135  // How far into the key the row starts at. First thing to read is the short
136  // that says how long the row is.
137  public static final int ROW_OFFSET =
138    Bytes.SIZEOF_INT /*keylength*/ +
139    Bytes.SIZEOF_INT /*valuelength*/;
140
141  public static final int ROW_KEY_OFFSET = ROW_OFFSET + ROW_LENGTH_SIZE;
142
143  // Size of the length ints in a KeyValue datastructure.
144  public static final int KEYVALUE_INFRASTRUCTURE_SIZE = ROW_OFFSET;
145
146  /** Size of the tags length field in bytes */
147  public static final int TAGS_LENGTH_SIZE = Bytes.SIZEOF_SHORT;
148
149  public static final int KEYVALUE_WITH_TAGS_INFRASTRUCTURE_SIZE = ROW_OFFSET + TAGS_LENGTH_SIZE;
150
151  /**
152   * Computes the number of bytes that a <code>KeyValue</code> instance with the provided
153   * characteristics would take up for its underlying data structure.
154   *
155   * @param rlength row length
156   * @param flength family length
157   * @param qlength qualifier length
158   * @param vlength value length
159   *
160   * @return the <code>KeyValue</code> data structure length
161   */
162  public static long getKeyValueDataStructureSize(int rlength,
163      int flength, int qlength, int vlength) {
164    return KeyValue.KEYVALUE_INFRASTRUCTURE_SIZE
165        + getKeyDataStructureSize(rlength, flength, qlength) + vlength;
166  }
167
168  /**
169   * Computes the number of bytes that a <code>KeyValue</code> instance with the provided
170   * characteristics would take up for its underlying data structure.
171   *
172   * @param rlength row length
173   * @param flength family length
174   * @param qlength qualifier length
175   * @param vlength value length
176   * @param tagsLength total length of the tags
177   *
178   * @return the <code>KeyValue</code> data structure length
179   */
180  public static long getKeyValueDataStructureSize(int rlength, int flength, int qlength,
181      int vlength, int tagsLength) {
182    if (tagsLength == 0) {
183      return getKeyValueDataStructureSize(rlength, flength, qlength, vlength);
184    }
185    return KeyValue.KEYVALUE_WITH_TAGS_INFRASTRUCTURE_SIZE
186        + getKeyDataStructureSize(rlength, flength, qlength) + vlength + tagsLength;
187  }
188
189  /**
190   * Computes the number of bytes that a <code>KeyValue</code> instance with the provided
191   * characteristics would take up for its underlying data structure.
192   *
193   * @param klength key length
194   * @param vlength value length
195   * @param tagsLength total length of the tags
196   *
197   * @return the <code>KeyValue</code> data structure length
198   */
199  public static long getKeyValueDataStructureSize(int klength, int vlength, int tagsLength) {
200    if (tagsLength == 0) {
201      return (long) KeyValue.KEYVALUE_INFRASTRUCTURE_SIZE + klength + vlength;
202    }
203    return (long) KeyValue.KEYVALUE_WITH_TAGS_INFRASTRUCTURE_SIZE + klength + vlength + tagsLength;
204  }
205
206  /**
207   * Computes the number of bytes that a <code>KeyValue</code> instance with the provided
208   * characteristics would take up in its underlying data structure for the key.
209   *
210   * @param rlength row length
211   * @param flength family length
212   * @param qlength qualifier length
213   *
214   * @return the key data structure length
215   */
216  public static long getKeyDataStructureSize(int rlength, int flength, int qlength) {
217    return (long) KeyValue.KEY_INFRASTRUCTURE_SIZE + rlength + flength + qlength;
218  }
219
220  /**
221   * Key type.
222   * Has space for other key types to be added later.  Cannot rely on
223   * enum ordinals . They change if item is removed or moved.  Do our own codes.
224   */
225  public static enum Type {
226    Minimum((byte)0),
227    Put((byte)4),
228
229    Delete((byte)8),
230    DeleteFamilyVersion((byte)10),
231    DeleteColumn((byte)12),
232    DeleteFamily((byte)14),
233
234    // Maximum is used when searching; you look from maximum on down.
235    Maximum((byte)255);
236
237    private final byte code;
238
239    Type(final byte c) {
240      this.code = c;
241    }
242
243    public byte getCode() {
244      return this.code;
245    }
246
247    private static Type[] codeArray = new Type[256];
248
249    static {
250      for (Type t : Type.values()) {
251        codeArray[t.code & 0xff] = t;
252      }
253    }
254
255    /**
256     * True to indicate that the byte b is a valid type.
257     * @param b byte to check
258     * @return true or false
259     */
260    static boolean isValidType(byte b) {
261      return codeArray[b & 0xff] != null;
262    }
263
264    /**
265     * Cannot rely on enum ordinals . They change if item is removed or moved.
266     * Do our own codes.
267     * @param b
268     * @return Type associated with passed code.
269     */
270    public static Type codeToType(final byte b) {
271      Type t = codeArray[b & 0xff];
272      if (t != null) {
273        return t;
274      }
275      throw new RuntimeException("Unknown code " + b);
276    }
277  }
278
279  /**
280   * Lowest possible key.
281   * Makes a Key with highest possible Timestamp, empty row and column.  No
282   * key can be equal or lower than this one in memstore or in store file.
283   */
284  public static final KeyValue LOWESTKEY =
285    new KeyValue(HConstants.EMPTY_BYTE_ARRAY, HConstants.LATEST_TIMESTAMP);
286
287  ////
288  // KeyValue core instance fields.
289  protected byte [] bytes = null;  // an immutable byte array that contains the KV
290  protected int offset = 0;  // offset into bytes buffer KV starts at
291  protected int length = 0;  // length of the KV starting from offset.
292
293  /** Here be dragons **/
294
295  /**
296   * used to achieve atomic operations in the memstore.
297   */
298  @Override
299  public long getSequenceId() {
300    return seqId;
301  }
302
303  @Override
304  public void setSequenceId(long seqId) {
305    this.seqId = seqId;
306  }
307
308  // multi-version concurrency control version.  default value is 0, aka do not care.
309  private long seqId = 0;
310
311  /** Dragon time over, return to normal business */
312
313
314  /** Writable Constructor -- DO NOT USE */
315  public KeyValue() {}
316
317  /**
318   * Creates a KeyValue from the start of the specified byte array.
319   * Presumes <code>bytes</code> content is formatted as a KeyValue blob.
320   * @param bytes byte array
321   */
322  public KeyValue(final byte [] bytes) {
323    this(bytes, 0);
324  }
325
326  /**
327   * Creates a KeyValue from the specified byte array and offset.
328   * Presumes <code>bytes</code> content starting at <code>offset</code> is
329   * formatted as a KeyValue blob.
330   * @param bytes byte array
331   * @param offset offset to start of KeyValue
332   */
333  public KeyValue(final byte [] bytes, final int offset) {
334    this(bytes, offset, getLength(bytes, offset));
335  }
336
337  /**
338   * Creates a KeyValue from the specified byte array, starting at offset, and
339   * for length <code>length</code>.
340   * @param bytes byte array
341   * @param offset offset to start of the KeyValue
342   * @param length length of the KeyValue
343   */
344  public KeyValue(final byte[] bytes, final int offset, final int length) {
345    KeyValueUtil.checkKeyValueBytes(bytes, offset, length, true);
346    this.bytes = bytes;
347    this.offset = offset;
348    this.length = length;
349  }
350
351  /**
352   * Creates a KeyValue from the specified byte array, starting at offset, and
353   * for length <code>length</code>.
354   *
355   * @param bytes  byte array
356   * @param offset offset to start of the KeyValue
357   * @param length length of the KeyValue
358   * @param ts
359   */
360  public KeyValue(final byte[] bytes, final int offset, final int length, long ts) {
361    this(bytes, offset, length, null, 0, 0, null, 0, 0, ts, Type.Maximum, null, 0, 0, null);
362  }
363
364  /** Constructors that build a new backing byte array from fields */
365
366  /**
367   * Constructs KeyValue structure filled with null value.
368   * Sets type to {@link KeyValue.Type#Maximum}
369   * @param row - row key (arbitrary byte array)
370   * @param timestamp
371   */
372  public KeyValue(final byte [] row, final long timestamp) {
373    this(row, null, null, timestamp, Type.Maximum, null);
374  }
375
376  /**
377   * Constructs KeyValue structure filled with null value.
378   * @param row - row key (arbitrary byte array)
379   * @param timestamp
380   */
381  public KeyValue(final byte [] row, final long timestamp, Type type) {
382    this(row, null, null, timestamp, type, null);
383  }
384
385  /**
386   * Constructs KeyValue structure filled with null value.
387   * Sets type to {@link KeyValue.Type#Maximum}
388   * @param row - row key (arbitrary byte array)
389   * @param family family name
390   * @param qualifier column qualifier
391   */
392  public KeyValue(final byte [] row, final byte [] family,
393      final byte [] qualifier) {
394    this(row, family, qualifier, HConstants.LATEST_TIMESTAMP, Type.Maximum);
395  }
396
397  /**
398   * Constructs KeyValue structure as a put filled with specified values and
399   * LATEST_TIMESTAMP.
400   * @param row - row key (arbitrary byte array)
401   * @param family family name
402   * @param qualifier column qualifier
403   */
404  public KeyValue(final byte [] row, final byte [] family,
405      final byte [] qualifier, final byte [] value) {
406    this(row, family, qualifier, HConstants.LATEST_TIMESTAMP, Type.Put, value);
407  }
408
409  /**
410   * Constructs KeyValue structure filled with specified values.
411   * @param row row key
412   * @param family family name
413   * @param qualifier column qualifier
414   * @param timestamp version timestamp
415   * @param type key type
416   * @throws IllegalArgumentException
417   */
418  public KeyValue(final byte[] row, final byte[] family,
419      final byte[] qualifier, final long timestamp, Type type) {
420    this(row, family, qualifier, timestamp, type, null);
421  }
422
423  /**
424   * Constructs KeyValue structure filled with specified values.
425   * @param row row key
426   * @param family family name
427   * @param qualifier column qualifier
428   * @param timestamp version timestamp
429   * @param value column value
430   * @throws IllegalArgumentException
431   */
432  public KeyValue(final byte[] row, final byte[] family,
433      final byte[] qualifier, final long timestamp, final byte[] value) {
434    this(row, family, qualifier, timestamp, Type.Put, value);
435  }
436
437  /**
438   * Constructs KeyValue structure filled with specified values.
439   * @param row row key
440   * @param family family name
441   * @param qualifier column qualifier
442   * @param timestamp version timestamp
443   * @param value column value
444   * @param tags tags
445   * @throws IllegalArgumentException
446   */
447  public KeyValue(final byte[] row, final byte[] family,
448      final byte[] qualifier, final long timestamp, final byte[] value,
449      final Tag[] tags) {
450    this(row, family, qualifier, timestamp, value, tags != null ? Arrays.asList(tags) : null);
451  }
452
453  /**
454   * Constructs KeyValue structure filled with specified values.
455   * @param row row key
456   * @param family family name
457   * @param qualifier column qualifier
458   * @param timestamp version timestamp
459   * @param value column value
460   * @param tags tags non-empty list of tags or null
461   * @throws IllegalArgumentException
462   */
463  public KeyValue(final byte[] row, final byte[] family,
464      final byte[] qualifier, final long timestamp, final byte[] value,
465      final List<Tag> tags) {
466    this(row, 0, row==null ? 0 : row.length,
467      family, 0, family==null ? 0 : family.length,
468      qualifier, 0, qualifier==null ? 0 : qualifier.length,
469      timestamp, Type.Put,
470      value, 0, value==null ? 0 : value.length, tags);
471  }
472
473  /**
474   * Constructs KeyValue structure filled with specified values.
475   * @param row row key
476   * @param family family name
477   * @param qualifier column qualifier
478   * @param timestamp version timestamp
479   * @param type key type
480   * @param value column value
481   * @throws IllegalArgumentException
482   */
483  public KeyValue(final byte[] row, final byte[] family,
484      final byte[] qualifier, final long timestamp, Type type,
485      final byte[] value) {
486    this(row, 0, len(row),   family, 0, len(family),   qualifier, 0, len(qualifier),
487        timestamp, type,   value, 0, len(value));
488  }
489
490  /**
491   * Constructs KeyValue structure filled with specified values.
492   * <p>
493   * Column is split into two fields, family and qualifier.
494   * @param row row key
495   * @param family family name
496   * @param qualifier column qualifier
497   * @param timestamp version timestamp
498   * @param type key type
499   * @param value column value
500   * @throws IllegalArgumentException
501   */
502  public KeyValue(final byte[] row, final byte[] family,
503      final byte[] qualifier, final long timestamp, Type type,
504      final byte[] value, final List<Tag> tags) {
505    this(row, family, qualifier, 0, qualifier==null ? 0 : qualifier.length,
506        timestamp, type, value, 0, value==null ? 0 : value.length, tags);
507  }
508
509  /**
510   * Constructs KeyValue structure filled with specified values.
511   * @param row row key
512   * @param family family name
513   * @param qualifier column qualifier
514   * @param timestamp version timestamp
515   * @param type key type
516   * @param value column value
517   * @throws IllegalArgumentException
518   */
519  public KeyValue(final byte[] row, final byte[] family,
520      final byte[] qualifier, final long timestamp, Type type,
521      final byte[] value, final byte[] tags) {
522    this(row, family, qualifier, 0, qualifier==null ? 0 : qualifier.length,
523        timestamp, type, value, 0, value==null ? 0 : value.length, tags);
524  }
525
526  /**
527   * Constructs KeyValue structure filled with specified values.
528   * @param row row key
529   * @param family family name
530   * @param qualifier column qualifier
531   * @param qoffset qualifier offset
532   * @param qlength qualifier length
533   * @param timestamp version timestamp
534   * @param type key type
535   * @param value column value
536   * @param voffset value offset
537   * @param vlength value length
538   * @throws IllegalArgumentException
539   */
540  public KeyValue(byte [] row, byte [] family,
541      byte [] qualifier, int qoffset, int qlength, long timestamp, Type type,
542      byte [] value, int voffset, int vlength, List<Tag> tags) {
543    this(row, 0, row==null ? 0 : row.length,
544        family, 0, family==null ? 0 : family.length,
545        qualifier, qoffset, qlength, timestamp, type,
546        value, voffset, vlength, tags);
547  }
548
549  /**
550   * @param row
551   * @param family
552   * @param qualifier
553   * @param qoffset
554   * @param qlength
555   * @param timestamp
556   * @param type
557   * @param value
558   * @param voffset
559   * @param vlength
560   * @param tags
561   */
562  public KeyValue(byte [] row, byte [] family,
563      byte [] qualifier, int qoffset, int qlength, long timestamp, Type type,
564      byte [] value, int voffset, int vlength, byte[] tags) {
565    this(row, 0, row==null ? 0 : row.length,
566        family, 0, family==null ? 0 : family.length,
567        qualifier, qoffset, qlength, timestamp, type,
568        value, voffset, vlength, tags, 0, tags==null ? 0 : tags.length);
569  }
570
571  /**
572   * Constructs KeyValue structure filled with specified values.
573   * <p>
574   * Column is split into two fields, family and qualifier.
575   * @param row row key
576   * @throws IllegalArgumentException
577   */
578  public KeyValue(final byte [] row, final int roffset, final int rlength,
579      final byte [] family, final int foffset, final int flength,
580      final byte [] qualifier, final int qoffset, final int qlength,
581      final long timestamp, final Type type,
582      final byte [] value, final int voffset, final int vlength) {
583    this(row, roffset, rlength, family, foffset, flength, qualifier, qoffset,
584      qlength, timestamp, type, value, voffset, vlength, null);
585  }
586
587  /**
588   * Constructs KeyValue structure filled with specified values. Uses the provided buffer as the
589   * data buffer.
590   * <p>
591   * Column is split into two fields, family and qualifier.
592   *
593   * @param buffer the bytes buffer to use
594   * @param boffset buffer offset
595   * @param row row key
596   * @param roffset row offset
597   * @param rlength row length
598   * @param family family name
599   * @param foffset family offset
600   * @param flength family length
601   * @param qualifier column qualifier
602   * @param qoffset qualifier offset
603   * @param qlength qualifier length
604   * @param timestamp version timestamp
605   * @param type key type
606   * @param value column value
607   * @param voffset value offset
608   * @param vlength value length
609   * @param tags non-empty list of tags or null
610   * @throws IllegalArgumentException an illegal value was passed or there is insufficient space
611   * remaining in the buffer
612   */
613  public KeyValue(byte [] buffer, final int boffset,
614      final byte [] row, final int roffset, final int rlength,
615      final byte [] family, final int foffset, final int flength,
616      final byte [] qualifier, final int qoffset, final int qlength,
617      final long timestamp, final Type type,
618      final byte [] value, final int voffset, final int vlength,
619      final Tag[] tags) {
620     this.bytes  = buffer;
621     this.length = writeByteArray(buffer, boffset,
622         row, roffset, rlength,
623         family, foffset, flength, qualifier, qoffset, qlength,
624        timestamp, type, value, voffset, vlength, tags);
625     this.offset = boffset;
626   }
627
628  /**
629   * Constructs KeyValue structure filled with specified values.
630   * <p>
631   * Column is split into two fields, family and qualifier.
632   * @param row row key
633   * @param roffset row offset
634   * @param rlength row length
635   * @param family family name
636   * @param foffset family offset
637   * @param flength family length
638   * @param qualifier column qualifier
639   * @param qoffset qualifier offset
640   * @param qlength qualifier length
641   * @param timestamp version timestamp
642   * @param type key type
643   * @param value column value
644   * @param voffset value offset
645   * @param vlength value length
646   * @param tags tags
647   * @throws IllegalArgumentException
648   */
649  public KeyValue(final byte [] row, final int roffset, final int rlength,
650      final byte [] family, final int foffset, final int flength,
651      final byte [] qualifier, final int qoffset, final int qlength,
652      final long timestamp, final Type type,
653      final byte [] value, final int voffset, final int vlength,
654      final List<Tag> tags) {
655    this.bytes = createByteArray(row, roffset, rlength,
656        family, foffset, flength, qualifier, qoffset, qlength,
657        timestamp, type, value, voffset, vlength, tags);
658    this.length = bytes.length;
659    this.offset = 0;
660  }
661
662  /**
663   * @param row
664   * @param roffset
665   * @param rlength
666   * @param family
667   * @param foffset
668   * @param flength
669   * @param qualifier
670   * @param qoffset
671   * @param qlength
672   * @param timestamp
673   * @param type
674   * @param value
675   * @param voffset
676   * @param vlength
677   * @param tags
678   */
679  public KeyValue(final byte [] row, final int roffset, final int rlength,
680      final byte [] family, final int foffset, final int flength,
681      final byte [] qualifier, final int qoffset, final int qlength,
682      final long timestamp, final Type type,
683      final byte [] value, final int voffset, final int vlength,
684      final byte[] tags, final int tagsOffset, final int tagsLength) {
685    this.bytes = createByteArray(row, roffset, rlength,
686        family, foffset, flength, qualifier, qoffset, qlength,
687        timestamp, type, value, voffset, vlength, tags, tagsOffset, tagsLength);
688    this.length = bytes.length;
689    this.offset = 0;
690  }
691
692  /**
693   * Constructs an empty KeyValue structure, with specified sizes.
694   * This can be used to partially fill up KeyValues.
695   * <p>
696   * Column is split into two fields, family and qualifier.
697   * @param rlength row length
698   * @param flength family length
699   * @param qlength qualifier length
700   * @param timestamp version timestamp
701   * @param type key type
702   * @param vlength value length
703   * @throws IllegalArgumentException
704   */
705  public KeyValue(final int rlength,
706      final int flength,
707      final int qlength,
708      final long timestamp, final Type type,
709      final int vlength) {
710    this(rlength, flength, qlength, timestamp, type, vlength, 0);
711  }
712
713  /**
714   * Constructs an empty KeyValue structure, with specified sizes.
715   * This can be used to partially fill up KeyValues.
716   * <p>
717   * Column is split into two fields, family and qualifier.
718   * @param rlength row length
719   * @param flength family length
720   * @param qlength qualifier length
721   * @param timestamp version timestamp
722   * @param type key type
723   * @param vlength value length
724   * @param tagsLength
725   * @throws IllegalArgumentException
726   */
727  public KeyValue(final int rlength,
728      final int flength,
729      final int qlength,
730      final long timestamp, final Type type,
731      final int vlength, final int tagsLength) {
732    this.bytes = createEmptyByteArray(rlength, flength, qlength, timestamp, type, vlength,
733        tagsLength);
734    this.length = bytes.length;
735    this.offset = 0;
736  }
737
738
739  public KeyValue(byte[] row, int roffset, int rlength,
740                  byte[] family, int foffset, int flength,
741                  ByteBuffer qualifier, long ts, Type type, ByteBuffer value, List<Tag> tags) {
742    this.bytes = createByteArray(row, roffset, rlength, family, foffset, flength,
743        qualifier, 0, qualifier == null ? 0 : qualifier.remaining(), ts, type,
744        value, 0, value == null ? 0 : value.remaining(), tags);
745    this.length = bytes.length;
746    this.offset = 0;
747  }
748
749  public KeyValue(Cell c) {
750    this(c.getRowArray(), c.getRowOffset(), c.getRowLength(),
751        c.getFamilyArray(), c.getFamilyOffset(), c.getFamilyLength(),
752        c.getQualifierArray(), c.getQualifierOffset(), c.getQualifierLength(),
753        c.getTimestamp(), Type.codeToType(c.getTypeByte()), c.getValueArray(), c.getValueOffset(),
754        c.getValueLength(), c.getTagsArray(), c.getTagsOffset(), c.getTagsLength());
755    this.seqId = c.getSequenceId();
756  }
757
758  /**
759   * Create an empty byte[] representing a KeyValue
760   * All lengths are preset and can be filled in later.
761   * @param rlength
762   * @param flength
763   * @param qlength
764   * @param timestamp
765   * @param type
766   * @param vlength
767   * @return The newly created byte array.
768   */
769  private static byte[] createEmptyByteArray(final int rlength, int flength,
770      int qlength, final long timestamp, final Type type, int vlength, int tagsLength) {
771    if (rlength > Short.MAX_VALUE) {
772      throw new IllegalArgumentException("Row > " + Short.MAX_VALUE);
773    }
774    if (flength > Byte.MAX_VALUE) {
775      throw new IllegalArgumentException("Family > " + Byte.MAX_VALUE);
776    }
777    // Qualifier length
778    if (qlength > Integer.MAX_VALUE - rlength - flength) {
779      throw new IllegalArgumentException("Qualifier > " + Integer.MAX_VALUE);
780    }
781    RawCell.checkForTagsLength(tagsLength);
782    // Key length
783    long longkeylength = getKeyDataStructureSize(rlength, flength, qlength);
784    if (longkeylength > Integer.MAX_VALUE) {
785      throw new IllegalArgumentException("keylength " + longkeylength + " > " +
786        Integer.MAX_VALUE);
787    }
788    int keylength = (int)longkeylength;
789    // Value length
790    if (vlength > HConstants.MAXIMUM_VALUE_LENGTH) { // FindBugs INT_VACUOUS_COMPARISON
791      throw new IllegalArgumentException("Valuer > " +
792          HConstants.MAXIMUM_VALUE_LENGTH);
793    }
794
795    // Allocate right-sized byte array.
796    byte[] bytes= new byte[(int) getKeyValueDataStructureSize(rlength, flength, qlength, vlength,
797        tagsLength)];
798    // Write the correct size markers
799    int pos = 0;
800    pos = Bytes.putInt(bytes, pos, keylength);
801    pos = Bytes.putInt(bytes, pos, vlength);
802    pos = Bytes.putShort(bytes, pos, (short)(rlength & 0x0000ffff));
803    pos += rlength;
804    pos = Bytes.putByte(bytes, pos, (byte)(flength & 0x0000ff));
805    pos += flength + qlength;
806    pos = Bytes.putLong(bytes, pos, timestamp);
807    pos = Bytes.putByte(bytes, pos, type.getCode());
808    pos += vlength;
809    if (tagsLength > 0) {
810      pos = Bytes.putAsShort(bytes, pos, tagsLength);
811    }
812    return bytes;
813  }
814
815  /**
816   * Checks the parameters passed to a constructor.
817   *
818   * @param row row key
819   * @param rlength row length
820   * @param family family name
821   * @param flength family length
822   * @param qlength qualifier length
823   * @param vlength value length
824   *
825   * @throws IllegalArgumentException an illegal value was passed
826   */
827  static void checkParameters(final byte [] row, final int rlength,
828      final byte [] family, int flength, int qlength, int vlength)
829          throws IllegalArgumentException {
830    if (rlength > Short.MAX_VALUE) {
831      throw new IllegalArgumentException("Row > " + Short.MAX_VALUE);
832    }
833    if (row == null) {
834      throw new IllegalArgumentException("Row is null");
835    }
836    // Family length
837    flength = family == null ? 0 : flength;
838    if (flength > Byte.MAX_VALUE) {
839      throw new IllegalArgumentException("Family > " + Byte.MAX_VALUE);
840    }
841    // Qualifier length
842    if (qlength > Integer.MAX_VALUE - rlength - flength) {
843      throw new IllegalArgumentException("Qualifier > " + Integer.MAX_VALUE);
844    }
845    // Key length
846    long longKeyLength = getKeyDataStructureSize(rlength, flength, qlength);
847    if (longKeyLength > Integer.MAX_VALUE) {
848      throw new IllegalArgumentException("keylength " + longKeyLength + " > " +
849          Integer.MAX_VALUE);
850    }
851    // Value length
852    if (vlength > HConstants.MAXIMUM_VALUE_LENGTH) { // FindBugs INT_VACUOUS_COMPARISON
853      throw new IllegalArgumentException("Value length " + vlength + " > " +
854          HConstants.MAXIMUM_VALUE_LENGTH);
855    }
856  }
857
858  /**
859   * Write KeyValue format into the provided byte array.
860   *
861   * @param buffer the bytes buffer to use
862   * @param boffset buffer offset
863   * @param row row key
864   * @param roffset row offset
865   * @param rlength row length
866   * @param family family name
867   * @param foffset family offset
868   * @param flength family length
869   * @param qualifier column qualifier
870   * @param qoffset qualifier offset
871   * @param qlength qualifier length
872   * @param timestamp version timestamp
873   * @param type key type
874   * @param value column value
875   * @param voffset value offset
876   * @param vlength value length
877   *
878   * @return The number of useful bytes in the buffer.
879   *
880   * @throws IllegalArgumentException an illegal value was passed or there is insufficient space
881   * remaining in the buffer
882   */
883  public static int writeByteArray(byte [] buffer, final int boffset,
884      final byte [] row, final int roffset, final int rlength,
885      final byte [] family, final int foffset, int flength,
886      final byte [] qualifier, final int qoffset, int qlength,
887      final long timestamp, final Type type,
888      final byte [] value, final int voffset, int vlength, Tag[] tags) {
889
890    checkParameters(row, rlength, family, flength, qlength, vlength);
891
892    // Calculate length of tags area
893    int tagsLength = 0;
894    if (tags != null && tags.length > 0) {
895      for (Tag t: tags) {
896        tagsLength += t.getValueLength() + Tag.INFRASTRUCTURE_SIZE;
897      }
898    }
899    RawCell.checkForTagsLength(tagsLength);
900    int keyLength = (int) getKeyDataStructureSize(rlength, flength, qlength);
901    int keyValueLength = (int) getKeyValueDataStructureSize(rlength, flength, qlength, vlength,
902        tagsLength);
903    if (keyValueLength > buffer.length - boffset) {
904      throw new IllegalArgumentException("Buffer size " + (buffer.length - boffset) + " < " +
905          keyValueLength);
906    }
907
908    // Write key, value and key row length.
909    int pos = boffset;
910    pos = Bytes.putInt(buffer, pos, keyLength);
911    pos = Bytes.putInt(buffer, pos, vlength);
912    pos = Bytes.putShort(buffer, pos, (short)(rlength & 0x0000ffff));
913    pos = Bytes.putBytes(buffer, pos, row, roffset, rlength);
914    pos = Bytes.putByte(buffer, pos, (byte) (flength & 0x0000ff));
915    if (flength != 0) {
916      pos = Bytes.putBytes(buffer, pos, family, foffset, flength);
917    }
918    if (qlength != 0) {
919      pos = Bytes.putBytes(buffer, pos, qualifier, qoffset, qlength);
920    }
921    pos = Bytes.putLong(buffer, pos, timestamp);
922    pos = Bytes.putByte(buffer, pos, type.getCode());
923    if (value != null && value.length > 0) {
924      pos = Bytes.putBytes(buffer, pos, value, voffset, vlength);
925    }
926    // Write the number of tags. If it is 0 then it means there are no tags.
927    if (tagsLength > 0) {
928      pos = Bytes.putAsShort(buffer, pos, tagsLength);
929      for (Tag t : tags) {
930        int tlen = t.getValueLength();
931        pos = Bytes.putAsShort(buffer, pos, tlen + Tag.TYPE_LENGTH_SIZE);
932        pos = Bytes.putByte(buffer, pos, t.getType());
933        Tag.copyValueTo(t, buffer, pos);
934        pos += tlen;
935      }
936    }
937    return keyValueLength;
938  }
939
940  /**
941   * Write KeyValue format into a byte array.
942   * @param row row key
943   * @param roffset row offset
944   * @param rlength row length
945   * @param family family name
946   * @param foffset family offset
947   * @param flength family length
948   * @param qualifier column qualifier
949   * @param qoffset qualifier offset
950   * @param qlength qualifier length
951   * @param timestamp version timestamp
952   * @param type key type
953   * @param value column value
954   * @param voffset value offset
955   * @param vlength value length
956   * @return The newly created byte array.
957   */
958  private static byte [] createByteArray(final byte [] row, final int roffset,
959      final int rlength, final byte [] family, final int foffset, int flength,
960      final byte [] qualifier, final int qoffset, int qlength,
961      final long timestamp, final Type type,
962      final byte [] value, final int voffset,
963      int vlength, byte[] tags, int tagsOffset, int tagsLength) {
964
965    checkParameters(row, rlength, family, flength, qlength, vlength);
966    RawCell.checkForTagsLength(tagsLength);
967    // Allocate right-sized byte array.
968    int keyLength = (int) getKeyDataStructureSize(rlength, flength, qlength);
969    byte[] bytes = new byte[(int) getKeyValueDataStructureSize(rlength, flength, qlength, vlength,
970      tagsLength)];
971    // Write key, value and key row length.
972    int pos = 0;
973    pos = Bytes.putInt(bytes, pos, keyLength);
974    pos = Bytes.putInt(bytes, pos, vlength);
975    pos = Bytes.putShort(bytes, pos, (short)(rlength & 0x0000ffff));
976    pos = Bytes.putBytes(bytes, pos, row, roffset, rlength);
977    pos = Bytes.putByte(bytes, pos, (byte)(flength & 0x0000ff));
978    if(flength != 0) {
979      pos = Bytes.putBytes(bytes, pos, family, foffset, flength);
980    }
981    if(qlength != 0) {
982      pos = Bytes.putBytes(bytes, pos, qualifier, qoffset, qlength);
983    }
984    pos = Bytes.putLong(bytes, pos, timestamp);
985    pos = Bytes.putByte(bytes, pos, type.getCode());
986    if (value != null && value.length > 0) {
987      pos = Bytes.putBytes(bytes, pos, value, voffset, vlength);
988    }
989    // Add the tags after the value part
990    if (tagsLength > 0) {
991      pos = Bytes.putAsShort(bytes, pos, tagsLength);
992      pos = Bytes.putBytes(bytes, pos, tags, tagsOffset, tagsLength);
993    }
994    return bytes;
995  }
996
997  /**
998   * @param qualifier can be a ByteBuffer or a byte[], or null.
999   * @param value can be a ByteBuffer or a byte[], or null.
1000   */
1001  private static byte [] createByteArray(final byte [] row, final int roffset,
1002      final int rlength, final byte [] family, final int foffset, int flength,
1003      final Object qualifier, final int qoffset, int qlength,
1004      final long timestamp, final Type type,
1005      final Object value, final int voffset, int vlength, List<Tag> tags) {
1006
1007    checkParameters(row, rlength, family, flength, qlength, vlength);
1008
1009    // Calculate length of tags area
1010    int tagsLength = 0;
1011    if (tags != null && !tags.isEmpty()) {
1012      for (Tag t : tags) {
1013        tagsLength += t.getValueLength() + Tag.INFRASTRUCTURE_SIZE;
1014      }
1015    }
1016    RawCell.checkForTagsLength(tagsLength);
1017    // Allocate right-sized byte array.
1018    int keyLength = (int) getKeyDataStructureSize(rlength, flength, qlength);
1019    byte[] bytes = new byte[(int) getKeyValueDataStructureSize(rlength, flength, qlength, vlength,
1020        tagsLength)];
1021
1022    // Write key, value and key row length.
1023    int pos = 0;
1024    pos = Bytes.putInt(bytes, pos, keyLength);
1025
1026    pos = Bytes.putInt(bytes, pos, vlength);
1027    pos = Bytes.putShort(bytes, pos, (short)(rlength & 0x0000ffff));
1028    pos = Bytes.putBytes(bytes, pos, row, roffset, rlength);
1029    pos = Bytes.putByte(bytes, pos, (byte)(flength & 0x0000ff));
1030    if(flength != 0) {
1031      pos = Bytes.putBytes(bytes, pos, family, foffset, flength);
1032    }
1033    if (qlength > 0) {
1034      if (qualifier instanceof ByteBuffer) {
1035        pos = Bytes.putByteBuffer(bytes, pos, (ByteBuffer) qualifier);
1036      } else {
1037        pos = Bytes.putBytes(bytes, pos, (byte[]) qualifier, qoffset, qlength);
1038      }
1039    }
1040    pos = Bytes.putLong(bytes, pos, timestamp);
1041    pos = Bytes.putByte(bytes, pos, type.getCode());
1042    if (vlength > 0) {
1043      if (value instanceof ByteBuffer) {
1044        pos = Bytes.putByteBuffer(bytes, pos, (ByteBuffer) value);
1045      } else {
1046        pos = Bytes.putBytes(bytes, pos, (byte[]) value, voffset, vlength);
1047      }
1048    }
1049    // Add the tags after the value part
1050    if (tagsLength > 0) {
1051      pos = Bytes.putAsShort(bytes, pos, tagsLength);
1052      for (Tag t : tags) {
1053        int tlen = t.getValueLength();
1054        pos = Bytes.putAsShort(bytes, pos, tlen + Tag.TYPE_LENGTH_SIZE);
1055        pos = Bytes.putByte(bytes, pos, t.getType());
1056        Tag.copyValueTo(t, bytes, pos);
1057        pos += tlen;
1058      }
1059    }
1060    return bytes;
1061  }
1062
1063  /**
1064   * Needed doing 'contains' on List.  Only compares the key portion, not the value.
1065   */
1066  @Override
1067  public boolean equals(Object other) {
1068    if (!(other instanceof Cell)) {
1069      return false;
1070    }
1071    return CellUtil.equals(this, (Cell)other);
1072  }
1073
1074  /**
1075   * In line with {@link #equals(Object)}, only uses the key portion, not the value.
1076   */
1077  @Override
1078  public int hashCode() {
1079    return calculateHashForKey(this);
1080  }
1081
1082  private int calculateHashForKey(Cell cell) {
1083    // pre-calculate the 3 hashes made of byte ranges
1084    int rowHash = Bytes.hashCode(cell.getRowArray(), cell.getRowOffset(), cell.getRowLength());
1085    int familyHash = Bytes.hashCode(cell.getFamilyArray(), cell.getFamilyOffset(),
1086        cell.getFamilyLength());
1087    int qualifierHash = Bytes.hashCode(cell.getQualifierArray(), cell.getQualifierOffset(),
1088        cell.getQualifierLength());
1089
1090    // combine the 6 sub-hashes
1091    int hash = 31 * rowHash + familyHash;
1092    hash = 31 * hash + qualifierHash;
1093    hash = 31 * hash + (int) cell.getTimestamp();
1094    hash = 31 * hash + cell.getTypeByte();
1095    return hash;
1096  }
1097
1098  //---------------------------------------------------------------------------
1099  //
1100  //  KeyValue cloning
1101  //
1102  //---------------------------------------------------------------------------
1103
1104  /**
1105   * Clones a KeyValue.  This creates a copy, re-allocating the buffer.
1106   * @return Fully copied clone of this KeyValue
1107   * @throws CloneNotSupportedException
1108   */
1109  @Override
1110  public KeyValue clone() throws CloneNotSupportedException {
1111    super.clone();
1112    byte [] b = new byte[this.length];
1113    System.arraycopy(this.bytes, this.offset, b, 0, this.length);
1114    KeyValue ret = new KeyValue(b, 0, b.length);
1115    // Important to clone the memstoreTS as well - otherwise memstore's
1116    // update-in-place methods (eg increment) will end up creating
1117    // new entries
1118    ret.setSequenceId(seqId);
1119    return ret;
1120  }
1121
1122  /**
1123   * Creates a shallow copy of this KeyValue, reusing the data byte buffer.
1124   * http://en.wikipedia.org/wiki/Object_copy
1125   * @return Shallow copy of this KeyValue
1126   */
1127  public KeyValue shallowCopy() {
1128    KeyValue shallowCopy = new KeyValue(this.bytes, this.offset, this.length);
1129    shallowCopy.setSequenceId(this.seqId);
1130    return shallowCopy;
1131  }
1132
1133  //---------------------------------------------------------------------------
1134  //
1135  //  String representation
1136  //
1137  //---------------------------------------------------------------------------
1138
1139  @Override
1140  public String toString() {
1141    if (this.bytes == null || this.bytes.length == 0) {
1142      return "empty";
1143    }
1144    return keyToString(this.bytes, this.offset + ROW_OFFSET, getKeyLength()) + "/vlen="
1145      + getValueLength() + "/seqid=" + seqId;
1146  }
1147
1148  /**
1149   * @param k Key portion of a KeyValue.
1150   * @return Key as a String, empty string if k is null.
1151   */
1152  public static String keyToString(final byte [] k) {
1153    if (k == null) {
1154      return "";
1155    }
1156    return keyToString(k, 0, k.length);
1157  }
1158
1159  /**
1160   * Produces a string map for this key/value pair. Useful for programmatic use
1161   * and manipulation of the data stored in an WALKey, for example, printing
1162   * as JSON. Values are left out due to their tendency to be large. If needed,
1163   * they can be added manually.
1164   *
1165   * @return the Map&lt;String,?&gt; containing data from this key
1166   */
1167  public Map<String, Object> toStringMap() {
1168    Map<String, Object> stringMap = new HashMap<>();
1169    stringMap.put("row", Bytes.toStringBinary(getRowArray(), getRowOffset(), getRowLength()));
1170    stringMap.put("family",
1171      Bytes.toStringBinary(getFamilyArray(), getFamilyOffset(), getFamilyLength()));
1172    stringMap.put("qualifier",
1173      Bytes.toStringBinary(getQualifierArray(), getQualifierOffset(), getQualifierLength()));
1174    stringMap.put("timestamp", getTimestamp());
1175    stringMap.put("vlen", getValueLength());
1176    Iterator<Tag> tags = getTags();
1177    if (tags != null) {
1178      List<String> tagsString = new ArrayList<String>();
1179      while (tags.hasNext()) {
1180        tagsString.add(tags.next().toString());
1181      }
1182      stringMap.put("tag", tagsString);
1183    }
1184    return stringMap;
1185  }
1186
1187  /**
1188   * Use for logging.
1189   * @param b Key portion of a KeyValue.
1190   * @param o Offset to start of key
1191   * @param l Length of key.
1192   * @return Key as a String.
1193   */
1194  public static String keyToString(final byte [] b, final int o, final int l) {
1195    if (b == null) return "";
1196    int rowlength = Bytes.toShort(b, o);
1197    String row = Bytes.toStringBinary(b, o + Bytes.SIZEOF_SHORT, rowlength);
1198    int columnoffset = o + Bytes.SIZEOF_SHORT + 1 + rowlength;
1199    int familylength = b[columnoffset - 1];
1200    int columnlength = l - ((columnoffset - o) + TIMESTAMP_TYPE_SIZE);
1201    String family = familylength == 0? "":
1202      Bytes.toStringBinary(b, columnoffset, familylength);
1203    String qualifier = columnlength == 0? "":
1204      Bytes.toStringBinary(b, columnoffset + familylength,
1205      columnlength - familylength);
1206    long timestamp = Bytes.toLong(b, o + (l - TIMESTAMP_TYPE_SIZE));
1207    String timestampStr = humanReadableTimestamp(timestamp);
1208    byte type = b[o + l - 1];
1209    return row + "/" + family +
1210      (family != null && family.length() > 0? ":" :"") +
1211      qualifier + "/" + timestampStr + "/" + Type.codeToType(type);
1212  }
1213
1214  public static String humanReadableTimestamp(final long timestamp) {
1215    if (timestamp == HConstants.LATEST_TIMESTAMP) {
1216      return "LATEST_TIMESTAMP";
1217    }
1218    if (timestamp == HConstants.OLDEST_TIMESTAMP) {
1219      return "OLDEST_TIMESTAMP";
1220    }
1221    return String.valueOf(timestamp);
1222  }
1223
1224  //---------------------------------------------------------------------------
1225  //
1226  //  Public Member Accessors
1227  //
1228  //---------------------------------------------------------------------------
1229
1230  /**
1231   * To be used only in tests where the Cells are clearly assumed to be of type KeyValue
1232   * and that we need access to the backing array to do some test case related assertions.
1233   * @return The byte array backing this KeyValue.
1234   */
1235  @VisibleForTesting
1236  public byte [] getBuffer() {
1237    return this.bytes;
1238  }
1239
1240  /**
1241   * @return Offset into {@link #getBuffer()} at which this KeyValue starts.
1242   */
1243  public int getOffset() {
1244    return this.offset;
1245  }
1246
1247  /**
1248   * @return Length of bytes this KeyValue occupies in {@link #getBuffer()}.
1249   */
1250  public int getLength() {
1251    return length;
1252  }
1253
1254  //---------------------------------------------------------------------------
1255  //
1256  //  Length and Offset Calculators
1257  //
1258  //---------------------------------------------------------------------------
1259
1260  /**
1261   * Determines the total length of the KeyValue stored in the specified
1262   * byte array and offset.  Includes all headers.
1263   * @param bytes byte array
1264   * @param offset offset to start of the KeyValue
1265   * @return length of entire KeyValue, in bytes
1266   */
1267  private static int getLength(byte [] bytes, int offset) {
1268    int klength = ROW_OFFSET + Bytes.toInt(bytes, offset);
1269    int vlength = Bytes.toInt(bytes, offset + Bytes.SIZEOF_INT);
1270    return klength + vlength;
1271  }
1272
1273  /**
1274   * @return Key offset in backing buffer..
1275   */
1276  public int getKeyOffset() {
1277    return this.offset + ROW_OFFSET;
1278  }
1279
1280  public String getKeyString() {
1281    return Bytes.toStringBinary(getBuffer(), getKeyOffset(), getKeyLength());
1282  }
1283
1284  /**
1285   * @return Length of key portion.
1286   */
1287  public int getKeyLength() {
1288    return Bytes.toInt(this.bytes, this.offset);
1289  }
1290
1291  /**
1292   * @return the backing array of the entire KeyValue (all KeyValue fields are in a single array)
1293   */
1294  @Override
1295  public byte[] getValueArray() {
1296    return bytes;
1297  }
1298
1299  /**
1300   * @return the value offset
1301   */
1302  @Override
1303  public int getValueOffset() {
1304    int voffset = getKeyOffset() + getKeyLength();
1305    return voffset;
1306  }
1307
1308  /**
1309   * @return Value length
1310   */
1311  @Override
1312  public int getValueLength() {
1313    int vlength = Bytes.toInt(this.bytes, this.offset + Bytes.SIZEOF_INT);
1314    return vlength;
1315  }
1316
1317  /**
1318   * @return the backing array of the entire KeyValue (all KeyValue fields are in a single array)
1319   */
1320  @Override
1321  public byte[] getRowArray() {
1322    return bytes;
1323  }
1324
1325  /**
1326   * @return Row offset
1327   */
1328  @Override
1329  public int getRowOffset() {
1330    return this.offset + ROW_KEY_OFFSET;
1331  }
1332
1333  /**
1334   * @return Row length
1335   */
1336  @Override
1337  public short getRowLength() {
1338    return Bytes.toShort(this.bytes, getKeyOffset());
1339  }
1340
1341  /**
1342   * @return the backing array of the entire KeyValue (all KeyValue fields are in a single array)
1343   */
1344  @Override
1345  public byte[] getFamilyArray() {
1346    return bytes;
1347  }
1348
1349  /**
1350   * @return Family offset
1351   */
1352  @Override
1353  public int getFamilyOffset() {
1354    return getFamilyOffset(getRowLength());
1355  }
1356
1357  /**
1358   * @return Family offset
1359   */
1360  private int getFamilyOffset(int rlength) {
1361    return this.offset + ROW_KEY_OFFSET + rlength + Bytes.SIZEOF_BYTE;
1362  }
1363
1364  /**
1365   * @return Family length
1366   */
1367  @Override
1368  public byte getFamilyLength() {
1369    return getFamilyLength(getFamilyOffset());
1370  }
1371
1372  /**
1373   * @return Family length
1374   */
1375  public byte getFamilyLength(int foffset) {
1376    return this.bytes[foffset-1];
1377  }
1378
1379  /**
1380   * @return the backing array of the entire KeyValue (all KeyValue fields are in a single array)
1381   */
1382  @Override
1383  public byte[] getQualifierArray() {
1384    return bytes;
1385  }
1386
1387  /**
1388   * @return Qualifier offset
1389   */
1390  @Override
1391  public int getQualifierOffset() {
1392    return getQualifierOffset(getFamilyOffset());
1393  }
1394
1395  /**
1396   * @return Qualifier offset
1397   */
1398  private int getQualifierOffset(int foffset) {
1399    return foffset + getFamilyLength(foffset);
1400  }
1401
1402  /**
1403   * @return Qualifier length
1404   */
1405  @Override
1406  public int getQualifierLength() {
1407    return getQualifierLength(getRowLength(),getFamilyLength());
1408  }
1409
1410  /**
1411   * @return Qualifier length
1412   */
1413  private int getQualifierLength(int rlength, int flength) {
1414    return getKeyLength() - (int) getKeyDataStructureSize(rlength, flength, 0);
1415  }
1416
1417  /**
1418   * @return Timestamp offset
1419   */
1420  public int getTimestampOffset() {
1421    return getTimestampOffset(getKeyLength());
1422  }
1423
1424  /**
1425   * @param keylength Pass if you have it to save on a int creation.
1426   * @return Timestamp offset
1427   */
1428  private int getTimestampOffset(final int keylength) {
1429    return getKeyOffset() + keylength - TIMESTAMP_TYPE_SIZE;
1430  }
1431
1432  /**
1433   * @return True if this KeyValue has a LATEST_TIMESTAMP timestamp.
1434   */
1435  public boolean isLatestTimestamp() {
1436    return Bytes.equals(getBuffer(), getTimestampOffset(), Bytes.SIZEOF_LONG,
1437      HConstants.LATEST_TIMESTAMP_BYTES, 0, Bytes.SIZEOF_LONG);
1438  }
1439
1440  /**
1441   * @param now Time to set into <code>this</code> IFF timestamp ==
1442   * {@link HConstants#LATEST_TIMESTAMP} (else, its a noop).
1443   * @return True is we modified this.
1444   */
1445  public boolean updateLatestStamp(final byte [] now) {
1446    if (this.isLatestTimestamp()) {
1447      int tsOffset = getTimestampOffset();
1448      System.arraycopy(now, 0, this.bytes, tsOffset, Bytes.SIZEOF_LONG);
1449      // clear cache or else getTimestamp() possibly returns an old value
1450      return true;
1451    }
1452    return false;
1453  }
1454
1455  @Override
1456  public void setTimestamp(long ts) {
1457    Bytes.putBytes(this.bytes, this.getTimestampOffset(), Bytes.toBytes(ts), 0, Bytes.SIZEOF_LONG);
1458  }
1459
1460  @Override
1461  public void setTimestamp(byte[] ts) {
1462    Bytes.putBytes(this.bytes, this.getTimestampOffset(), ts, 0, Bytes.SIZEOF_LONG);
1463  }
1464
1465  //---------------------------------------------------------------------------
1466  //
1467  //  Methods that return copies of fields
1468  //
1469  //---------------------------------------------------------------------------
1470
1471  /**
1472   * Do not use unless you have to. Used internally for compacting and testing. Use
1473   * {@link #getRowArray()}, {@link #getFamilyArray()}, {@link #getQualifierArray()}, and
1474   * {@link #getValueArray()} if accessing a KeyValue client-side.
1475   * @return Copy of the key portion only.
1476   */
1477  public byte [] getKey() {
1478    int keylength = getKeyLength();
1479    byte [] key = new byte[keylength];
1480    System.arraycopy(getBuffer(), getKeyOffset(), key, 0, keylength);
1481    return key;
1482  }
1483
1484  /**
1485   *
1486   * @return Timestamp
1487   */
1488  @Override
1489  public long getTimestamp() {
1490    return getTimestamp(getKeyLength());
1491  }
1492
1493  /**
1494   * @param keylength Pass if you have it to save on a int creation.
1495   * @return Timestamp
1496   */
1497  long getTimestamp(final int keylength) {
1498    int tsOffset = getTimestampOffset(keylength);
1499    return Bytes.toLong(this.bytes, tsOffset);
1500  }
1501
1502  /**
1503   * @return KeyValue.TYPE byte representation
1504   */
1505  @Override
1506  public byte getTypeByte() {
1507    return this.bytes[this.offset + getKeyLength() - 1 + ROW_OFFSET];
1508  }
1509
1510  /**
1511   * This returns the offset where the tag actually starts.
1512   */
1513  @Override
1514  public int getTagsOffset() {
1515    int tagsLen = getTagsLength();
1516    if (tagsLen == 0) {
1517      return this.offset + this.length;
1518    }
1519    return this.offset + this.length - tagsLen;
1520  }
1521
1522  /**
1523   * This returns the total length of the tag bytes
1524   */
1525  @Override
1526  public int getTagsLength() {
1527    int tagsLen = this.length - (getKeyLength() + getValueLength() + KEYVALUE_INFRASTRUCTURE_SIZE);
1528    if (tagsLen > 0) {
1529      // There are some Tag bytes in the byte[]. So reduce 2 bytes which is added to denote the tags
1530      // length
1531      tagsLen -= TAGS_LENGTH_SIZE;
1532    }
1533    return tagsLen;
1534  }
1535
1536  /**
1537   * @return the backing array of the entire KeyValue (all KeyValue fields are in a single array)
1538   */
1539  @Override
1540  public byte[] getTagsArray() {
1541    return bytes;
1542  }
1543
1544  /**
1545   * Creates a new KeyValue that only contains the key portion (the value is
1546   * set to be null).
1547   *
1548   * TODO only used by KeyOnlyFilter -- move there.
1549   * @param lenAsVal replace value with the actual value length (false=empty)
1550   */
1551  public KeyValue createKeyOnly(boolean lenAsVal) {
1552    // KV format:  <keylen:4><valuelen:4><key:keylen><value:valuelen>
1553    // Rebuild as: <keylen:4><0:4><key:keylen>
1554    int dataLen = lenAsVal? Bytes.SIZEOF_INT : 0;
1555    byte [] newBuffer = new byte[getKeyLength() + ROW_OFFSET + dataLen];
1556    System.arraycopy(this.bytes, this.offset, newBuffer, 0,
1557        Math.min(newBuffer.length,this.length));
1558    Bytes.putInt(newBuffer, Bytes.SIZEOF_INT, dataLen);
1559    if (lenAsVal) {
1560      Bytes.putInt(newBuffer, newBuffer.length - dataLen, this.getValueLength());
1561    }
1562    return new KeyValue(newBuffer);
1563  }
1564
1565  /**
1566   * @param b
1567   * @param delimiter
1568   * @return Index of delimiter having started from start of <code>b</code>
1569   * moving rightward.
1570   */
1571  public static int getDelimiter(final byte [] b, int offset, final int length,
1572      final int delimiter) {
1573    if (b == null) {
1574      throw new IllegalArgumentException("Passed buffer is null");
1575    }
1576    int result = -1;
1577    for (int i = offset; i < length + offset; i++) {
1578      if (b[i] == delimiter) {
1579        result = i;
1580        break;
1581      }
1582    }
1583    return result;
1584  }
1585
1586  /**
1587   * Find index of passed delimiter walking from end of buffer backwards.
1588   * @param b
1589   * @param delimiter
1590   * @return Index of delimiter
1591   */
1592  public static int getDelimiterInReverse(final byte [] b, final int offset,
1593      final int length, final int delimiter) {
1594    if (b == null) {
1595      throw new IllegalArgumentException("Passed buffer is null");
1596    }
1597    int result = -1;
1598    for (int i = (offset + length) - 1; i >= offset; i--) {
1599      if (b[i] == delimiter) {
1600        result = i;
1601        break;
1602      }
1603    }
1604    return result;
1605  }
1606
1607  /**
1608   * A {@link KVComparator} for <code>hbase:meta</code> catalog table
1609   * {@link KeyValue}s.
1610   * @deprecated : {@link MetaCellComparator#META_COMPARATOR} to be used.
1611   *   Deprecated for hbase 2.0, remove for hbase 3.0.
1612   */
1613  @Deprecated
1614  public static class MetaComparator extends KVComparator {
1615    /**
1616     * Compare key portion of a {@link KeyValue} for keys in <code>hbase:meta</code>
1617     * table.
1618     */
1619    @Override
1620    public int compare(final Cell left, final Cell right) {
1621      return PrivateCellUtil.compareKeyIgnoresMvcc(MetaCellComparator.META_COMPARATOR, left,
1622        right);
1623    }
1624
1625    @Override
1626    public int compareOnlyKeyPortion(Cell left, Cell right) {
1627      return compare(left, right);
1628    }
1629
1630    @Override
1631    public int compareRows(byte [] left, int loffset, int llength,
1632        byte [] right, int roffset, int rlength) {
1633      int leftDelimiter = getDelimiter(left, loffset, llength,
1634          HConstants.DELIMITER);
1635      int rightDelimiter = getDelimiter(right, roffset, rlength,
1636          HConstants.DELIMITER);
1637      // Compare up to the delimiter
1638      int lpart = (leftDelimiter < 0 ? llength :leftDelimiter - loffset);
1639      int rpart = (rightDelimiter < 0 ? rlength :rightDelimiter - roffset);
1640      int result = Bytes.compareTo(left, loffset, lpart, right, roffset, rpart);
1641      if (result != 0) {
1642        return result;
1643      } else {
1644        if (leftDelimiter < 0 && rightDelimiter >= 0) {
1645          return -1;
1646        } else if (rightDelimiter < 0 && leftDelimiter >= 0) {
1647          return 1;
1648        } else if (leftDelimiter < 0 && rightDelimiter < 0) {
1649          return 0;
1650        }
1651      }
1652      // Compare middle bit of the row.
1653      // Move past delimiter
1654      leftDelimiter++;
1655      rightDelimiter++;
1656      int leftFarDelimiter = getDelimiterInReverse(left, leftDelimiter,
1657          llength - (leftDelimiter - loffset), HConstants.DELIMITER);
1658      int rightFarDelimiter = getDelimiterInReverse(right,
1659          rightDelimiter, rlength - (rightDelimiter - roffset),
1660          HConstants.DELIMITER);
1661      // Now compare middlesection of row.
1662      lpart = (leftFarDelimiter < 0 ? llength + loffset: leftFarDelimiter) - leftDelimiter;
1663      rpart = (rightFarDelimiter < 0 ? rlength + roffset: rightFarDelimiter)- rightDelimiter;
1664      result = super.compareRows(left, leftDelimiter, lpart, right, rightDelimiter, rpart);
1665      if (result != 0) {
1666        return result;
1667      }  else {
1668        if (leftDelimiter < 0 && rightDelimiter >= 0) {
1669          return -1;
1670        } else if (rightDelimiter < 0 && leftDelimiter >= 0) {
1671          return 1;
1672        } else if (leftDelimiter < 0 && rightDelimiter < 0) {
1673          return 0;
1674        }
1675      }
1676      // Compare last part of row, the rowid.
1677      leftFarDelimiter++;
1678      rightFarDelimiter++;
1679      result = Bytes.compareTo(left, leftFarDelimiter, llength - (leftFarDelimiter - loffset),
1680          right, rightFarDelimiter, rlength - (rightFarDelimiter - roffset));
1681      return result;
1682    }
1683
1684    /**
1685     * Don't do any fancy Block Index splitting tricks.
1686     */
1687    @Override
1688    public byte[] getShortMidpointKey(final byte[] leftKey, final byte[] rightKey) {
1689      return Arrays.copyOf(rightKey, rightKey.length);
1690    }
1691
1692    /**
1693     * The HFileV2 file format's trailer contains this class name.  We reinterpret this and
1694     * instantiate the appropriate comparator.
1695     * TODO: With V3 consider removing this.
1696     * @return legacy class name for FileFileTrailer#comparatorClassName
1697     */
1698    @Override
1699    public String getLegacyKeyComparatorName() {
1700      return "org.apache.hadoop.hbase.KeyValue$MetaKeyComparator";
1701    }
1702
1703    @Override
1704    protected Object clone() throws CloneNotSupportedException {
1705      return new MetaComparator();
1706    }
1707
1708    /**
1709     * Override the row key comparison to parse and compare the meta row key parts.
1710     */
1711    @Override
1712    protected int compareRowKey(final Cell l, final Cell r) {
1713      byte[] left = l.getRowArray();
1714      int loffset = l.getRowOffset();
1715      int llength = l.getRowLength();
1716      byte[] right = r.getRowArray();
1717      int roffset = r.getRowOffset();
1718      int rlength = r.getRowLength();
1719      return compareRows(left, loffset, llength, right, roffset, rlength);
1720    }
1721  }
1722
1723  /**
1724   * Compare KeyValues.  When we compare KeyValues, we only compare the Key
1725   * portion.  This means two KeyValues with same Key but different Values are
1726   * considered the same as far as this Comparator is concerned.
1727   * @deprecated : Use {@link CellComparatorImpl}. Deprecated for hbase 2.0, remove for hbase 3.0.
1728   */
1729  @Deprecated
1730  public static class KVComparator implements RawComparator<Cell>, SamePrefixComparator<byte[]> {
1731
1732    /**
1733     * The HFileV2 file format's trailer contains this class name.  We reinterpret this and
1734     * instantiate the appropriate comparator.
1735     * TODO: With V3 consider removing this.
1736     * @return legacy class name for FileFileTrailer#comparatorClassName
1737     */
1738    public String getLegacyKeyComparatorName() {
1739      return "org.apache.hadoop.hbase.KeyValue$KeyComparator";
1740    }
1741
1742    @Override // RawComparator
1743    public int compare(byte[] l, int loff, int llen, byte[] r, int roff, int rlen) {
1744      return compareFlatKey(l,loff,llen, r,roff,rlen);
1745    }
1746
1747
1748    /**
1749     * Compares the only the user specified portion of a Key.  This is overridden by MetaComparator.
1750     * @param left
1751     * @param right
1752     * @return 0 if equal, &lt;0 if left smaller, &gt;0 if right smaller
1753     */
1754    protected int compareRowKey(final Cell left, final Cell right) {
1755      return CellComparatorImpl.COMPARATOR.compareRows(left, right);
1756    }
1757
1758    /**
1759     * Compares left to right assuming that left,loffset,llength and right,roffset,rlength are
1760     * full KVs laid out in a flat byte[]s.
1761     * @param left
1762     * @param loffset
1763     * @param llength
1764     * @param right
1765     * @param roffset
1766     * @param rlength
1767     * @return  0 if equal, &lt;0 if left smaller, &gt;0 if right smaller
1768     */
1769    public int compareFlatKey(byte[] left, int loffset, int llength,
1770        byte[] right, int roffset, int rlength) {
1771      // Compare row
1772      short lrowlength = Bytes.toShort(left, loffset);
1773      short rrowlength = Bytes.toShort(right, roffset);
1774      int compare = compareRows(left, loffset + Bytes.SIZEOF_SHORT,
1775          lrowlength, right, roffset + Bytes.SIZEOF_SHORT, rrowlength);
1776      if (compare != 0) {
1777        return compare;
1778      }
1779
1780      // Compare the rest of the two KVs without making any assumptions about
1781      // the common prefix. This function will not compare rows anyway, so we
1782      // don't need to tell it that the common prefix includes the row.
1783      return compareWithoutRow(0, left, loffset, llength, right, roffset,
1784          rlength, rrowlength);
1785    }
1786
1787    public int compareFlatKey(byte[] left, byte[] right) {
1788      return compareFlatKey(left, 0, left.length, right, 0, right.length);
1789    }
1790
1791    // compare a key against row/fam/qual/ts/type
1792    public int compareKey(Cell cell,
1793        byte[] row, int roff, int rlen,
1794        byte[] fam, int foff, int flen,
1795        byte[] col, int coff, int clen,
1796        long ts, byte type) {
1797
1798      int compare = compareRows(
1799        cell.getRowArray(), cell.getRowOffset(), cell.getRowLength(),
1800        row, roff, rlen);
1801      if (compare != 0) {
1802        return compare;
1803      }
1804      // If the column is not specified, the "minimum" key type appears the
1805      // latest in the sorted order, regardless of the timestamp. This is used
1806      // for specifying the last key/value in a given row, because there is no
1807      // "lexicographically last column" (it would be infinitely long). The
1808      // "maximum" key type does not need this behavior.
1809      if (cell.getFamilyLength() + cell.getQualifierLength() == 0
1810          && cell.getTypeByte() == Type.Minimum.getCode()) {
1811        // left is "bigger", i.e. it appears later in the sorted order
1812        return 1;
1813      }
1814      if (flen+clen == 0 && type == Type.Minimum.getCode()) {
1815        return -1;
1816      }
1817
1818      compare = compareFamilies(
1819        cell.getFamilyArray(), cell.getFamilyOffset(), cell.getFamilyLength(),
1820        fam, foff, flen);
1821      if (compare != 0) {
1822        return compare;
1823      }
1824      compare = compareColumns(
1825        cell.getQualifierArray(), cell.getQualifierOffset(), cell.getQualifierLength(),
1826        col, coff, clen);
1827      if (compare != 0) {
1828        return compare;
1829      }
1830      // Next compare timestamps.
1831      compare = compareTimestamps(cell.getTimestamp(), ts);
1832      if (compare != 0) {
1833        return compare;
1834      }
1835
1836      // Compare types. Let the delete types sort ahead of puts; i.e. types
1837      // of higher numbers sort before those of lesser numbers. Maximum (255)
1838      // appears ahead of everything, and minimum (0) appears after
1839      // everything.
1840      return (0xff & type) - (0xff & cell.getTypeByte());
1841    }
1842
1843    public int compareOnlyKeyPortion(Cell left, Cell right) {
1844      return PrivateCellUtil.compareKeyIgnoresMvcc(CellComparatorImpl.COMPARATOR, left, right);
1845    }
1846
1847    /**
1848     * Compares the Key of a cell -- with fields being more significant in this order:
1849     * rowkey, colfam/qual, timestamp, type, mvcc
1850     */
1851    @Override
1852    public int compare(final Cell left, final Cell right) {
1853      int compare = CellComparatorImpl.COMPARATOR.compare(left, right);
1854      return compare;
1855    }
1856
1857    public int compareTimestamps(final Cell left, final Cell right) {
1858      return CellComparatorImpl.COMPARATOR.compareTimestamps(left, right);
1859    }
1860
1861    /**
1862     * @param left
1863     * @param right
1864     * @return Result comparing rows.
1865     */
1866    public int compareRows(final Cell left, final Cell right) {
1867      return compareRows(left.getRowArray(),left.getRowOffset(), left.getRowLength(),
1868      right.getRowArray(), right.getRowOffset(), right.getRowLength());
1869    }
1870
1871    /**
1872     * Get the b[],o,l for left and right rowkey portions and compare.
1873     * @param left
1874     * @param loffset
1875     * @param llength
1876     * @param right
1877     * @param roffset
1878     * @param rlength
1879     * @return 0 if equal, &lt;0 if left smaller, &gt;0 if right smaller
1880     */
1881    public int compareRows(byte [] left, int loffset, int llength,
1882        byte [] right, int roffset, int rlength) {
1883      return Bytes.compareTo(left, loffset, llength, right, roffset, rlength);
1884    }
1885
1886    int compareColumns(final Cell left, final short lrowlength, final Cell right,
1887        final short rrowlength) {
1888      return CellComparatorImpl.COMPARATOR.compareColumns(left, right);
1889    }
1890
1891    protected int compareColumns(
1892        byte [] left, int loffset, int llength, final int lfamilylength,
1893        byte [] right, int roffset, int rlength, final int rfamilylength) {
1894      // Compare family portion first.
1895      int diff = Bytes.compareTo(left, loffset, lfamilylength,
1896        right, roffset, rfamilylength);
1897      if (diff != 0) {
1898        return diff;
1899      }
1900      // Compare qualifier portion
1901      return Bytes.compareTo(left, loffset + lfamilylength,
1902        llength - lfamilylength,
1903        right, roffset + rfamilylength, rlength - rfamilylength);
1904      }
1905
1906    static int compareTimestamps(final long ltimestamp, final long rtimestamp) {
1907      // The below older timestamps sorting ahead of newer timestamps looks
1908      // wrong but it is intentional. This way, newer timestamps are first
1909      // found when we iterate over a memstore and newer versions are the
1910      // first we trip over when reading from a store file.
1911      if (ltimestamp < rtimestamp) {
1912        return 1;
1913      } else if (ltimestamp > rtimestamp) {
1914        return -1;
1915      }
1916      return 0;
1917    }
1918
1919    /**
1920     * Overridden
1921     * @param commonPrefix
1922     * @param left
1923     * @param loffset
1924     * @param llength
1925     * @param right
1926     * @param roffset
1927     * @param rlength
1928     * @return 0 if equal, &lt;0 if left smaller, &gt;0 if right smaller
1929     */
1930    @Override // SamePrefixComparator
1931    public int compareIgnoringPrefix(int commonPrefix, byte[] left,
1932        int loffset, int llength, byte[] right, int roffset, int rlength) {
1933      // Compare row
1934      short lrowlength = Bytes.toShort(left, loffset);
1935      short rrowlength;
1936
1937      int comparisonResult = 0;
1938      if (commonPrefix < ROW_LENGTH_SIZE) {
1939        // almost nothing in common
1940        rrowlength = Bytes.toShort(right, roffset);
1941        comparisonResult = compareRows(left, loffset + ROW_LENGTH_SIZE,
1942            lrowlength, right, roffset + ROW_LENGTH_SIZE, rrowlength);
1943      } else { // the row length is the same
1944        rrowlength = lrowlength;
1945        if (commonPrefix < ROW_LENGTH_SIZE + rrowlength) {
1946          // The rows are not the same. Exclude the common prefix and compare
1947          // the rest of the two rows.
1948          int common = commonPrefix - ROW_LENGTH_SIZE;
1949          comparisonResult = compareRows(
1950              left, loffset + common + ROW_LENGTH_SIZE, lrowlength - common,
1951              right, roffset + common + ROW_LENGTH_SIZE, rrowlength - common);
1952        }
1953      }
1954      if (comparisonResult != 0) {
1955        return comparisonResult;
1956      }
1957
1958      assert lrowlength == rrowlength;
1959      return compareWithoutRow(commonPrefix, left, loffset, llength, right,
1960          roffset, rlength, lrowlength);
1961    }
1962
1963    /**
1964     * Compare columnFamily, qualifier, timestamp, and key type (everything
1965     * except the row). This method is used both in the normal comparator and
1966     * the "same-prefix" comparator. Note that we are assuming that row portions
1967     * of both KVs have already been parsed and found identical, and we don't
1968     * validate that assumption here.
1969     * @param commonPrefix
1970     *          the length of the common prefix of the two key-values being
1971     *          compared, including row length and row
1972     */
1973    private int compareWithoutRow(int commonPrefix, byte[] left, int loffset,
1974        int llength, byte[] right, int roffset, int rlength, short rowlength) {
1975      /***
1976       * KeyValue Format and commonLength:
1977       * |_keyLen_|_valLen_|_rowLen_|_rowKey_|_famiLen_|_fami_|_Quali_|....
1978       * ------------------|-------commonLength--------|--------------
1979       */
1980      int commonLength = ROW_LENGTH_SIZE + FAMILY_LENGTH_SIZE + rowlength;
1981
1982      // commonLength + TIMESTAMP_TYPE_SIZE
1983      int commonLengthWithTSAndType = TIMESTAMP_TYPE_SIZE + commonLength;
1984      // ColumnFamily + Qualifier length.
1985      int lcolumnlength = llength - commonLengthWithTSAndType;
1986      int rcolumnlength = rlength - commonLengthWithTSAndType;
1987
1988      byte ltype = left[loffset + (llength - 1)];
1989      byte rtype = right[roffset + (rlength - 1)];
1990
1991      // If the column is not specified, the "minimum" key type appears the
1992      // latest in the sorted order, regardless of the timestamp. This is used
1993      // for specifying the last key/value in a given row, because there is no
1994      // "lexicographically last column" (it would be infinitely long). The
1995      // "maximum" key type does not need this behavior.
1996      if (lcolumnlength == 0 && ltype == Type.Minimum.getCode()) {
1997        // left is "bigger", i.e. it appears later in the sorted order
1998        return 1;
1999      }
2000      if (rcolumnlength == 0 && rtype == Type.Minimum.getCode()) {
2001        return -1;
2002      }
2003
2004      int lfamilyoffset = commonLength + loffset;
2005      int rfamilyoffset = commonLength + roffset;
2006
2007      // Column family length.
2008      int lfamilylength = left[lfamilyoffset - 1];
2009      int rfamilylength = right[rfamilyoffset - 1];
2010      // If left family size is not equal to right family size, we need not
2011      // compare the qualifiers.
2012      boolean sameFamilySize = (lfamilylength == rfamilylength);
2013      int common = 0;
2014      if (commonPrefix > 0) {
2015        common = Math.max(0, commonPrefix - commonLength);
2016        if (!sameFamilySize) {
2017          // Common should not be larger than Math.min(lfamilylength,
2018          // rfamilylength).
2019          common = Math.min(common, Math.min(lfamilylength, rfamilylength));
2020        } else {
2021          common = Math.min(common, Math.min(lcolumnlength, rcolumnlength));
2022        }
2023      }
2024      if (!sameFamilySize) {
2025        // comparing column family is enough.
2026        return Bytes.compareTo(left, lfamilyoffset + common, lfamilylength
2027            - common, right, rfamilyoffset + common, rfamilylength - common);
2028      }
2029      // Compare family & qualifier together.
2030      final int comparison = Bytes.compareTo(left, lfamilyoffset + common,
2031          lcolumnlength - common, right, rfamilyoffset + common,
2032          rcolumnlength - common);
2033      if (comparison != 0) {
2034        return comparison;
2035      }
2036
2037      ////
2038      // Next compare timestamps.
2039      long ltimestamp = Bytes.toLong(left,
2040          loffset + (llength - TIMESTAMP_TYPE_SIZE));
2041      long rtimestamp = Bytes.toLong(right,
2042          roffset + (rlength - TIMESTAMP_TYPE_SIZE));
2043      int compare = compareTimestamps(ltimestamp, rtimestamp);
2044      if (compare != 0) {
2045        return compare;
2046      }
2047
2048      // Compare types. Let the delete types sort ahead of puts; i.e. types
2049      // of higher numbers sort before those of lesser numbers. Maximum (255)
2050      // appears ahead of everything, and minimum (0) appears after
2051      // everything.
2052      return (0xff & rtype) - (0xff & ltype);
2053    }
2054
2055    protected int compareFamilies(final byte[] left, final int loffset, final int lfamilylength,
2056        final byte[] right, final int roffset, final int rfamilylength) {
2057      int diff = Bytes.compareTo(left, loffset, lfamilylength, right, roffset, rfamilylength);
2058      return diff;
2059    }
2060
2061    protected int compareColumns(final byte[] left, final int loffset, final int lquallength,
2062        final byte[] right, final int roffset, final int rquallength) {
2063      int diff = Bytes.compareTo(left, loffset, lquallength, right, roffset, rquallength);
2064      return diff;
2065    }
2066    /**
2067     * Compares the row and column of two keyvalues for equality
2068     * @param left
2069     * @param right
2070     * @return True if same row and column.
2071     */
2072    public boolean matchingRowColumn(final Cell left,
2073        final Cell right) {
2074      short lrowlength = left.getRowLength();
2075      short rrowlength = right.getRowLength();
2076
2077      // TsOffset = end of column data. just comparing Row+CF length of each
2078      if ((left.getRowLength() + left.getFamilyLength() + left.getQualifierLength()) != (right
2079          .getRowLength() + right.getFamilyLength() + right.getQualifierLength())) {
2080        return false;
2081      }
2082
2083      if (!matchingRows(left, lrowlength, right, rrowlength)) {
2084        return false;
2085      }
2086
2087      int lfoffset = left.getFamilyOffset();
2088      int rfoffset = right.getFamilyOffset();
2089      int lclength = left.getQualifierLength();
2090      int rclength = right.getQualifierLength();
2091      int lfamilylength = left.getFamilyLength();
2092      int rfamilylength = right.getFamilyLength();
2093      int diff = compareFamilies(left.getFamilyArray(), lfoffset, lfamilylength,
2094          right.getFamilyArray(), rfoffset, rfamilylength);
2095      if (diff != 0) {
2096        return false;
2097      } else {
2098        diff = compareColumns(left.getQualifierArray(), left.getQualifierOffset(), lclength,
2099            right.getQualifierArray(), right.getQualifierOffset(), rclength);
2100        return diff == 0;
2101      }
2102    }
2103
2104    /**
2105     * Compares the row of two keyvalues for equality
2106     * @param left
2107     * @param right
2108     * @return True if rows match.
2109     */
2110    public boolean matchingRows(final Cell left, final Cell right) {
2111      short lrowlength = left.getRowLength();
2112      short rrowlength = right.getRowLength();
2113      return matchingRows(left, lrowlength, right, rrowlength);
2114    }
2115
2116    /**
2117     * @param left
2118     * @param lrowlength
2119     * @param right
2120     * @param rrowlength
2121     * @return True if rows match.
2122     */
2123    private boolean matchingRows(final Cell left, final short lrowlength,
2124        final Cell right, final short rrowlength) {
2125      return lrowlength == rrowlength &&
2126          matchingRows(left.getRowArray(), left.getRowOffset(), lrowlength,
2127              right.getRowArray(), right.getRowOffset(), rrowlength);
2128    }
2129
2130    /**
2131     * Compare rows. Just calls Bytes.equals, but it's good to have this encapsulated.
2132     * @param left Left row array.
2133     * @param loffset Left row offset.
2134     * @param llength Left row length.
2135     * @param right Right row array.
2136     * @param roffset Right row offset.
2137     * @param rlength Right row length.
2138     * @return Whether rows are the same row.
2139     */
2140    public boolean matchingRows(final byte [] left, final int loffset, final int llength,
2141        final byte [] right, final int roffset, final int rlength) {
2142      return Bytes.equals(left, loffset, llength, right, roffset, rlength);
2143    }
2144
2145    public byte[] calcIndexKey(byte[] lastKeyOfPreviousBlock, byte[] firstKeyInBlock) {
2146      byte[] fakeKey = getShortMidpointKey(lastKeyOfPreviousBlock, firstKeyInBlock);
2147      if (compareFlatKey(fakeKey, firstKeyInBlock) > 0) {
2148        LOG.error("Unexpected getShortMidpointKey result, fakeKey:"
2149            + Bytes.toStringBinary(fakeKey) + ", firstKeyInBlock:"
2150            + Bytes.toStringBinary(firstKeyInBlock));
2151        return firstKeyInBlock;
2152      }
2153      if (lastKeyOfPreviousBlock != null && compareFlatKey(lastKeyOfPreviousBlock, fakeKey) >= 0) {
2154        LOG.error("Unexpected getShortMidpointKey result, lastKeyOfPreviousBlock:" +
2155            Bytes.toStringBinary(lastKeyOfPreviousBlock) + ", fakeKey:" +
2156            Bytes.toStringBinary(fakeKey));
2157        return firstKeyInBlock;
2158      }
2159      return fakeKey;
2160    }
2161
2162    /**
2163     * This is a HFile block index key optimization.
2164     * @param leftKey
2165     * @param rightKey
2166     * @return 0 if equal, &lt;0 if left smaller, &gt;0 if right smaller
2167     * @deprecated Since 0.99.2;
2168     */
2169    @Deprecated
2170    public byte[] getShortMidpointKey(final byte[] leftKey, final byte[] rightKey) {
2171      if (rightKey == null) {
2172        throw new IllegalArgumentException("rightKey can not be null");
2173      }
2174      if (leftKey == null) {
2175        return Arrays.copyOf(rightKey, rightKey.length);
2176      }
2177      if (compareFlatKey(leftKey, rightKey) >= 0) {
2178        throw new IllegalArgumentException("Unexpected input, leftKey:" + Bytes.toString(leftKey)
2179          + ", rightKey:" + Bytes.toString(rightKey));
2180      }
2181
2182      short leftRowLength = Bytes.toShort(leftKey, 0);
2183      short rightRowLength = Bytes.toShort(rightKey, 0);
2184      int leftCommonLength = ROW_LENGTH_SIZE + FAMILY_LENGTH_SIZE + leftRowLength;
2185      int rightCommonLength = ROW_LENGTH_SIZE + FAMILY_LENGTH_SIZE + rightRowLength;
2186      int leftCommonLengthWithTSAndType = TIMESTAMP_TYPE_SIZE + leftCommonLength;
2187      int rightCommonLengthWithTSAndType = TIMESTAMP_TYPE_SIZE + rightCommonLength;
2188      int leftColumnLength = leftKey.length - leftCommonLengthWithTSAndType;
2189      int rightColumnLength = rightKey.length - rightCommonLengthWithTSAndType;
2190      // rows are equal
2191      if (leftRowLength == rightRowLength && compareRows(leftKey, ROW_LENGTH_SIZE, leftRowLength,
2192        rightKey, ROW_LENGTH_SIZE, rightRowLength) == 0) {
2193        // Compare family & qualifier together.
2194        int comparison = Bytes.compareTo(leftKey, leftCommonLength, leftColumnLength, rightKey,
2195          rightCommonLength, rightColumnLength);
2196        // same with "row + family + qualifier", return rightKey directly
2197        if (comparison == 0) {
2198          return Arrays.copyOf(rightKey, rightKey.length);
2199        }
2200        // "family + qualifier" are different, generate a faked key per rightKey
2201        byte[] newKey = Arrays.copyOf(rightKey, rightKey.length);
2202        Bytes.putLong(newKey, rightKey.length - TIMESTAMP_TYPE_SIZE, HConstants.LATEST_TIMESTAMP);
2203        Bytes.putByte(newKey, rightKey.length - TYPE_SIZE, Type.Maximum.getCode());
2204        return newKey;
2205      }
2206      // rows are different
2207      short minLength = leftRowLength < rightRowLength ? leftRowLength : rightRowLength;
2208      short diffIdx = 0;
2209      while (diffIdx < minLength
2210          && leftKey[ROW_LENGTH_SIZE + diffIdx] == rightKey[ROW_LENGTH_SIZE + diffIdx]) {
2211        diffIdx++;
2212      }
2213      byte[] newRowKey = null;
2214      if (diffIdx >= minLength) {
2215        // leftKey's row is prefix of rightKey's.
2216        newRowKey = new byte[diffIdx + 1];
2217        System.arraycopy(rightKey, ROW_LENGTH_SIZE, newRowKey, 0, diffIdx + 1);
2218      } else {
2219        int diffByte = leftKey[ROW_LENGTH_SIZE + diffIdx];
2220        if ((0xff & diffByte) < 0xff && (diffByte + 1) <
2221            (rightKey[ROW_LENGTH_SIZE + diffIdx] & 0xff)) {
2222          newRowKey = new byte[diffIdx + 1];
2223          System.arraycopy(leftKey, ROW_LENGTH_SIZE, newRowKey, 0, diffIdx);
2224          newRowKey[diffIdx] = (byte) (diffByte + 1);
2225        } else {
2226          newRowKey = new byte[diffIdx + 1];
2227          System.arraycopy(rightKey, ROW_LENGTH_SIZE, newRowKey, 0, diffIdx + 1);
2228        }
2229      }
2230      return new KeyValue(newRowKey, null, null, HConstants.LATEST_TIMESTAMP,
2231        Type.Maximum).getKey();
2232    }
2233
2234    @Override
2235    protected Object clone() throws CloneNotSupportedException {
2236      super.clone();
2237      return new KVComparator();
2238    }
2239
2240  }
2241
2242  /**
2243   * @param in Where to read bytes from.  Creates a byte array to hold the KeyValue
2244   * backing bytes copied from the steam.
2245   * @return KeyValue created by deserializing from <code>in</code> OR if we find a length
2246   * of zero, we will return null which can be useful marking a stream as done.
2247   * @throws IOException
2248   */
2249  public static KeyValue create(final DataInput in) throws IOException {
2250    return create(in.readInt(), in);
2251  }
2252
2253  /**
2254   * Create a KeyValue reading <code>length</code> from <code>in</code>
2255   * @param length
2256   * @param in
2257   * @return Created KeyValue OR if we find a length of zero, we will return null which
2258   * can be useful marking a stream as done.
2259   * @throws IOException
2260   */
2261  public static KeyValue create(int length, final DataInput in) throws IOException {
2262
2263    if (length <= 0) {
2264      if (length == 0) return null;
2265      throw new IOException("Failed read " + length + " bytes, stream corrupt?");
2266    }
2267
2268    // This is how the old Writables.readFrom used to deserialize.  Didn't even vint.
2269    byte [] bytes = new byte[length];
2270    in.readFully(bytes);
2271    return new KeyValue(bytes, 0, length);
2272  }
2273
2274  /**
2275   * Write out a KeyValue in the manner in which we used to when KeyValue was a Writable.
2276   * @param kv
2277   * @param out
2278   * @return Length written on stream
2279   * @throws IOException
2280   * @see #create(DataInput) for the inverse function
2281   */
2282  public static long write(final KeyValue kv, final DataOutput out) throws IOException {
2283    // This is how the old Writables write used to serialize KVs.  Need to figure way to make it
2284    // work for all implementations.
2285    int length = kv.getLength();
2286    out.writeInt(length);
2287    out.write(kv.getBuffer(), kv.getOffset(), length);
2288    return (long) length + Bytes.SIZEOF_INT;
2289  }
2290
2291  /**
2292   * Write out a KeyValue in the manner in which we used to when KeyValue was a Writable but do
2293   * not require a {@link DataOutput}, just take plain {@link OutputStream}
2294   * Named <code>oswrite</code> so does not clash with {@link #write(KeyValue, DataOutput)}
2295   * @param kv
2296   * @param out
2297   * @param withTags
2298   * @return Length written on stream
2299   * @throws IOException
2300   * @see #create(DataInput) for the inverse function
2301   * @see #write(KeyValue, DataOutput)
2302   * @see KeyValueUtil#oswrite(Cell, OutputStream, boolean)
2303   * @deprecated As of release 2.0.0, this will be removed in HBase 3.0.0.
2304   *             Instead use {@link #write(OutputStream, boolean)}
2305   */
2306  @Deprecated
2307  public static long oswrite(final KeyValue kv, final OutputStream out, final boolean withTags)
2308      throws IOException {
2309    ByteBufferUtils.putInt(out, kv.getSerializedSize(withTags));
2310    return (long) kv.write(out, withTags) + Bytes.SIZEOF_INT;
2311  }
2312
2313  @Override
2314  public int write(OutputStream out, boolean withTags) throws IOException {
2315    int len = getSerializedSize(withTags);
2316    out.write(this.bytes, this.offset, len);
2317    return len;
2318  }
2319
2320  @Override
2321  public int getSerializedSize(boolean withTags) {
2322    if (withTags) {
2323      return this.length;
2324    }
2325    return this.getKeyLength() + this.getValueLength() + KEYVALUE_INFRASTRUCTURE_SIZE;
2326  }
2327
2328  @Override
2329  public int getSerializedSize() {
2330    return this.length;
2331  }
2332
2333  @Override
2334  public void write(ByteBuffer buf, int offset) {
2335    ByteBufferUtils.copyFromArrayToBuffer(buf, offset, this.bytes, this.offset, this.length);
2336  }
2337
2338  /**
2339   * Avoids redundant comparisons for better performance.
2340   *
2341   * TODO get rid of this wart
2342   */
2343  public interface SamePrefixComparator<T> {
2344    /**
2345     * Compare two keys assuming that the first n bytes are the same.
2346     * @param commonPrefix How many bytes are the same.
2347     */
2348    int compareIgnoringPrefix(int commonPrefix, byte[] left, int loffset, int llength,
2349        byte[] right, int roffset, int rlength
2350    );
2351  }
2352
2353  /**
2354   * HeapSize implementation
2355   *
2356   * We do not count the bytes in the rowCache because it should be empty for a KeyValue in the
2357   * MemStore.
2358   */
2359  @Override
2360  public long heapSize() {
2361    /*
2362     * Deep object overhead for this KV consists of two parts. The first part is the KV object
2363     * itself, while the second part is the backing byte[]. We will only count the array overhead
2364     * from the byte[] only if this is the first KV in there.
2365     */
2366    return ClassSize.align(FIXED_OVERHEAD) +
2367        (offset == 0
2368          ? ClassSize.sizeOfByteArray(length)  // count both length and object overhead
2369          : length);                           // only count the number of bytes
2370  }
2371
2372  /**
2373   * A simple form of KeyValue that creates a keyvalue with only the key part of the byte[]
2374   * Mainly used in places where we need to compare two cells.  Avoids copying of bytes
2375   * In places like block index keys, we need to compare the key byte[] with a cell.
2376   * Hence create a Keyvalue(aka Cell) that would help in comparing as two cells
2377   */
2378  public static class KeyOnlyKeyValue extends KeyValue {
2379    private short rowLen = -1;
2380    public KeyOnlyKeyValue() {
2381
2382    }
2383    public KeyOnlyKeyValue(byte[] b) {
2384      this(b, 0, b.length);
2385    }
2386
2387    public KeyOnlyKeyValue(byte[] b, int offset, int length) {
2388      this.bytes = b;
2389      this.length = length;
2390      this.offset = offset;
2391      this.rowLen = Bytes.toShort(this.bytes, this.offset);
2392    }
2393
2394    public void set(KeyOnlyKeyValue keyOnlyKeyValue) {
2395      this.bytes = keyOnlyKeyValue.bytes;
2396      this.length = keyOnlyKeyValue.length;
2397      this.offset = keyOnlyKeyValue.offset;
2398      this.rowLen = keyOnlyKeyValue.rowLen;
2399    }
2400
2401    public void clear() {
2402      rowLen = -1;
2403      bytes = null;
2404      offset = 0;
2405      length = 0;
2406    }
2407
2408    @Override
2409    public int getKeyOffset() {
2410      return this.offset;
2411    }
2412
2413    /**
2414     * A setter that helps to avoid object creation every time and whenever
2415     * there is a need to create new KeyOnlyKeyValue.
2416     * @param key
2417     * @param offset
2418     * @param length
2419     */
2420    public void setKey(byte[] key, int offset, int length) {
2421      this.bytes = key;
2422      this.offset = offset;
2423      this.length = length;
2424      this.rowLen = Bytes.toShort(this.bytes, this.offset);
2425    }
2426
2427    @Override
2428    public byte[] getKey() {
2429      int keylength = getKeyLength();
2430      byte[] key = new byte[keylength];
2431      System.arraycopy(this.bytes, getKeyOffset(), key, 0, keylength);
2432      return key;
2433    }
2434
2435    @Override
2436    public byte[] getRowArray() {
2437      return bytes;
2438    }
2439
2440    @Override
2441    public int getRowOffset() {
2442      return getKeyOffset() + Bytes.SIZEOF_SHORT;
2443    }
2444
2445    @Override
2446    public byte[] getFamilyArray() {
2447      return bytes;
2448    }
2449
2450    @Override
2451    public byte getFamilyLength() {
2452      return this.bytes[getFamilyOffset() - 1];
2453    }
2454
2455    @Override
2456    public int getFamilyOffset() {
2457      return this.offset + Bytes.SIZEOF_SHORT + getRowLength() + Bytes.SIZEOF_BYTE;
2458    }
2459
2460    @Override
2461    public byte[] getQualifierArray() {
2462      return bytes;
2463    }
2464
2465    @Override
2466    public int getQualifierLength() {
2467      return getQualifierLength(getRowLength(), getFamilyLength());
2468    }
2469
2470    @Override
2471    public int getQualifierOffset() {
2472      return getFamilyOffset() + getFamilyLength();
2473    }
2474
2475    @Override
2476    public int getKeyLength() {
2477      return length;
2478    }
2479
2480    @Override
2481    public short getRowLength() {
2482      return rowLen;
2483    }
2484
2485    @Override
2486    public byte getTypeByte() {
2487      return this.bytes[this.offset + getKeyLength() - 1];
2488    }
2489
2490    private int getQualifierLength(int rlength, int flength) {
2491      return getKeyLength() - (int) getKeyDataStructureSize(rlength, flength, 0);
2492    }
2493
2494    @Override
2495    public long getTimestamp() {
2496      int tsOffset = getTimestampOffset();
2497      return Bytes.toLong(this.bytes, tsOffset);
2498    }
2499
2500    @Override
2501    public int getTimestampOffset() {
2502      return getKeyOffset() + getKeyLength() - TIMESTAMP_TYPE_SIZE;
2503    }
2504
2505    @Override
2506    public byte[] getTagsArray() {
2507      return HConstants.EMPTY_BYTE_ARRAY;
2508    }
2509
2510    @Override
2511    public int getTagsOffset() {
2512      return 0;
2513    }
2514
2515    @Override
2516    public byte[] getValueArray() {
2517      throw new IllegalArgumentException("KeyOnlyKeyValue does not work with values.");
2518    }
2519
2520    @Override
2521    public int getValueOffset() {
2522      throw new IllegalArgumentException("KeyOnlyKeyValue does not work with values.");
2523    }
2524
2525    @Override
2526    public int getValueLength() {
2527      throw new IllegalArgumentException("KeyOnlyKeyValue does not work with values.");
2528    }
2529
2530    @Override
2531    public int getTagsLength() {
2532      return 0;
2533    }
2534
2535    @Override
2536    public String toString() {
2537      if (this.bytes == null || this.bytes.length == 0) {
2538        return "empty";
2539      }
2540      return keyToString(this.bytes, this.offset, getKeyLength()) + "/vlen=0/mvcc=0";
2541    }
2542
2543    @Override
2544    public int hashCode() {
2545      return super.hashCode();
2546    }
2547
2548    @Override
2549    public boolean equals(Object other) {
2550      return super.equals(other);
2551    }
2552
2553    @Override
2554    public long heapSize() {
2555      return super.heapSize() + Bytes.SIZEOF_SHORT;
2556    }
2557
2558    @Override
2559    public int write(OutputStream out, boolean withTags) throws IOException {
2560      // This type of Cell is used only to maintain some internal states. We never allow this type
2561      // of Cell to be returned back over the RPC
2562      throw new IllegalStateException("A reader should never return this type of a Cell");
2563    }
2564  }
2565
2566  @Override
2567  public ExtendedCell deepClone() {
2568    byte[] copy = Bytes.copy(this.bytes, this.offset, this.length);
2569    KeyValue kv = new KeyValue(copy, 0, copy.length);
2570    kv.setSequenceId(this.getSequenceId());
2571    return kv;
2572  }
2573}