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