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