View Javadoc

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