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