View Javadoc

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