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