View Javadoc

1   /**
2    * Copyright 2009 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 java.io.DataInput;
23  import java.io.DataOutput;
24  import java.io.IOException;
25  import java.nio.ByteBuffer;
26  import java.util.Comparator;
27  import java.util.HashMap;
28  import java.util.Map;
29  
30  import com.google.common.primitives.Longs;
31  import org.apache.commons.logging.Log;
32  import org.apache.commons.logging.LogFactory;
33  import org.apache.hadoop.hbase.io.HeapSize;
34  import org.apache.hadoop.hbase.io.hfile.HFile;
35  import org.apache.hadoop.hbase.util.Bytes;
36  import org.apache.hadoop.hbase.util.ClassSize;
37  import org.apache.hadoop.io.RawComparator;
38  import org.apache.hadoop.io.Writable;
39  
40  /**
41   * An HBase Key/Value.
42   *
43   * <p>If being used client-side, the primary methods to access individual fields
44   * are {@link #getRow()}, {@link #getFamily()}, {@link #getQualifier()},
45   * {@link #getTimestamp()}, and {@link #getValue()}.  These methods allocate new
46   * byte arrays and return copies so they should be avoided server-side.
47   *
48   * <p>Instances of this class are immutable.  They are not
49   * comparable but Comparators are provided.  Comparators change with context,
50   * whether user table or a catalog table comparison context.  Its
51   * important that you use the appropriate comparator comparing rows in
52   * particular.  There are Comparators for KeyValue instances and then for
53   * just the Key portion of a KeyValue used mostly in {@link HFile}.
54   *
55   * <p>KeyValue wraps a byte array and has offset and length for passed array
56   * at where to start interpreting the content as a KeyValue blob.  The KeyValue
57   * blob format inside the byte array is:
58   * <code>&lt;keylength> &lt;valuelength> &lt;key> &lt;value></code>
59   * Key is decomposed as:
60   * <code>&lt;rowlength> &lt;row> &lt;columnfamilylength> &lt;columnfamily> &lt;columnqualifier> &lt;timestamp> &lt;keytype></code>
61   * Rowlength maximum is Short.MAX_SIZE, column family length maximum is
62   * Byte.MAX_SIZE, and column qualifier + key length must be < Integer.MAX_SIZE.
63   * The column does not contain the family/qualifier delimiter.
64   *
65   * <p>TODO: Group Key-only comparators and operations into a Key class, just
66   * for neatness sake, if can figure what to call it.
67   */
68  public class KeyValue implements Writable, HeapSize {
69    static final Log LOG = LogFactory.getLog(KeyValue.class);
70  
71    /**
72     * Colon character in UTF-8
73     */
74    public static final char COLUMN_FAMILY_DELIMITER = ':';
75  
76    public static final byte[] COLUMN_FAMILY_DELIM_ARRAY =
77      new byte[]{COLUMN_FAMILY_DELIMITER};
78  
79    /**
80     * Comparator for plain key/values; i.e. non-catalog table key/values.
81     */
82    public static KVComparator COMPARATOR = new KVComparator();
83  
84    /**
85     * Comparator for plain key; i.e. non-catalog table key.  Works on Key portion
86     * of KeyValue only.
87     */
88    public static KeyComparator KEY_COMPARATOR = new KeyComparator();
89  
90    /**
91     * A {@link KVComparator} for <code>.META.</code> catalog table
92     * {@link KeyValue}s.
93     */
94    public static KVComparator META_COMPARATOR = new MetaComparator();
95  
96    /**
97     * A {@link KVComparator} for <code>.META.</code> catalog table
98     * {@link KeyValue} keys.
99     */
100   public static KeyComparator META_KEY_COMPARATOR = new MetaKeyComparator();
101 
102   /**
103    * A {@link KVComparator} for <code>-ROOT-</code> catalog table
104    * {@link KeyValue}s.
105    */
106   public static KVComparator ROOT_COMPARATOR = new RootComparator();
107 
108   /**
109    * A {@link KVComparator} for <code>-ROOT-</code> catalog table
110    * {@link KeyValue} keys.
111    */
112   public static KeyComparator ROOT_KEY_COMPARATOR = new RootKeyComparator();
113 
114   /**
115    * Get the appropriate row comparator for the specified table.
116    *
117    * Hopefully we can get rid of this, I added this here because it's replacing
118    * something in HSK.  We should move completely off of that.
119    *
120    * @param tableName  The table name.
121    * @return The comparator.
122    */
123   public static KeyComparator getRowComparator(byte [] tableName) {
124     if(Bytes.equals(HTableDescriptor.ROOT_TABLEDESC.getName(),tableName)) {
125       return ROOT_COMPARATOR.getRawComparator();
126     }
127     if(Bytes.equals(HTableDescriptor.META_TABLEDESC.getName(), tableName)) {
128       return META_COMPARATOR.getRawComparator();
129     }
130     return COMPARATOR.getRawComparator();
131   }
132 
133   // Size of the timestamp and type byte on end of a key -- a long + a byte.
134   public static final int TIMESTAMP_TYPE_SIZE =
135     Bytes.SIZEOF_LONG /* timestamp */ +
136     Bytes.SIZEOF_BYTE /*keytype*/;
137 
138   // Size of the length shorts and bytes in key.
139   public static final int KEY_INFRASTRUCTURE_SIZE =
140     Bytes.SIZEOF_SHORT /*rowlength*/ +
141     Bytes.SIZEOF_BYTE /*columnfamilylength*/ +
142     TIMESTAMP_TYPE_SIZE;
143 
144   // How far into the key the row starts at. First thing to read is the short
145   // that says how long the row is.
146   public static final int ROW_OFFSET =
147     Bytes.SIZEOF_INT /*keylength*/ +
148     Bytes.SIZEOF_INT /*valuelength*/;
149 
150   // Size of the length ints in a KeyValue datastructure.
151   public static final int KEYVALUE_INFRASTRUCTURE_SIZE = ROW_OFFSET;
152 
153   /**
154    * Key type.
155    * Has space for other key types to be added later.  Cannot rely on
156    * enum ordinals . They change if item is removed or moved.  Do our own codes.
157    */
158   public static enum Type {
159     Minimum((byte)0),
160     Put((byte)4),
161 
162     Delete((byte)8),
163     DeleteColumn((byte)12),
164     DeleteFamily((byte)14),
165 
166     // Maximum is used when searching; you look from maximum on down.
167     Maximum((byte)255);
168 
169     private final byte code;
170 
171     Type(final byte c) {
172       this.code = c;
173     }
174 
175     public byte getCode() {
176       return this.code;
177     }
178 
179     /**
180      * Cannot rely on enum ordinals . They change if item is removed or moved.
181      * Do our own codes.
182      * @param b
183      * @return Type associated with passed code.
184      */
185     public static Type codeToType(final byte b) {
186       for (Type t : Type.values()) {
187         if (t.getCode() == b) {
188           return t;
189         }
190       }
191       throw new RuntimeException("Unknown code " + b);
192     }
193   }
194 
195   /**
196    * Lowest possible key.
197    * Makes a Key with highest possible Timestamp, empty row and column.  No
198    * key can be equal or lower than this one in memstore or in store file.
199    */
200   public static final KeyValue LOWESTKEY =
201     new KeyValue(HConstants.EMPTY_BYTE_ARRAY, HConstants.LATEST_TIMESTAMP);
202 
203   private byte [] bytes = null;
204   private int offset = 0;
205   private int length = 0;
206 
207   // the row cached
208   private byte [] rowCache = null;
209 
210 
211   /** Here be dragons **/
212 
213   // used to achieve atomic operations in the memstore.
214   public long getMemstoreTS() {
215     return memstoreTS;
216   }
217 
218   public void setMemstoreTS(long memstoreTS) {
219     this.memstoreTS = memstoreTS;
220   }
221 
222   // default value is 0, aka DNC
223   private long memstoreTS = 0;
224 
225   /** Dragon time over, return to normal business */
226 
227 
228   /** Writable Constructor -- DO NOT USE */
229   public KeyValue() {}
230 
231   /**
232    * Creates a KeyValue from the start of the specified byte array.
233    * Presumes <code>bytes</code> content is formatted as a KeyValue blob.
234    * @param bytes byte array
235    */
236   public KeyValue(final byte [] bytes) {
237     this(bytes, 0);
238   }
239 
240   /**
241    * Creates a KeyValue from the specified byte array and offset.
242    * Presumes <code>bytes</code> content starting at <code>offset</code> is
243    * formatted as a KeyValue blob.
244    * @param bytes byte array
245    * @param offset offset to start of KeyValue
246    */
247   public KeyValue(final byte [] bytes, final int offset) {
248     this(bytes, offset, getLength(bytes, offset));
249   }
250 
251   /**
252    * Creates a KeyValue from the specified byte array, starting at offset, and
253    * for length <code>length</code>.
254    * @param bytes byte array
255    * @param offset offset to start of the KeyValue
256    * @param length length of the KeyValue
257    */
258   public KeyValue(final byte [] bytes, final int offset, final int length) {
259     this.bytes = bytes;
260     this.offset = offset;
261     this.length = length;
262   }
263 
264   /** Constructors that build a new backing byte array from fields */
265 
266   /**
267    * Constructs KeyValue structure filled with null value.
268    * Sets type to {@link KeyValue.Type#Maximum}
269    * @param row - row key (arbitrary byte array)
270    * @param timestamp
271    */
272   public KeyValue(final byte [] row, final long timestamp) {
273     this(row, timestamp, Type.Maximum);
274   }
275 
276   /**
277    * Constructs KeyValue structure filled with null value.
278    * @param row - row key (arbitrary byte array)
279    * @param timestamp
280    */
281   public KeyValue(final byte [] row, final long timestamp, Type type) {
282     this(row, null, null, timestamp, type, null);
283   }
284 
285   /**
286    * Constructs KeyValue structure filled with null value.
287    * Sets type to {@link KeyValue.Type#Maximum}
288    * @param row - row key (arbitrary byte array)
289    * @param family family name
290    * @param qualifier column qualifier
291    */
292   public KeyValue(final byte [] row, final byte [] family,
293       final byte [] qualifier) {
294     this(row, family, qualifier, HConstants.LATEST_TIMESTAMP, Type.Maximum);
295   }
296 
297   /**
298    * Constructs KeyValue structure filled with null value.
299    * @param row - row key (arbitrary byte array)
300    * @param family family name
301    * @param qualifier column qualifier
302    */
303   public KeyValue(final byte [] row, final byte [] family,
304       final byte [] qualifier, final byte [] value) {
305     this(row, family, qualifier, HConstants.LATEST_TIMESTAMP, Type.Put, value);
306   }
307 
308   /**
309    * Constructs KeyValue structure filled with specified values.
310    * @param row row key
311    * @param family family name
312    * @param qualifier column qualifier
313    * @param timestamp version timestamp
314    * @param type key type
315    * @throws IllegalArgumentException
316    */
317   public KeyValue(final byte[] row, final byte[] family,
318       final byte[] qualifier, final long timestamp, Type type) {
319     this(row, family, qualifier, timestamp, type, null);
320   }
321 
322   /**
323    * Constructs KeyValue structure filled with specified values.
324    * @param row row key
325    * @param family family name
326    * @param qualifier column qualifier
327    * @param timestamp version timestamp
328    * @param value column value
329    * @throws IllegalArgumentException
330    */
331   public KeyValue(final byte[] row, final byte[] family,
332       final byte[] qualifier, final long timestamp, final byte[] value) {
333     this(row, family, qualifier, timestamp, Type.Put, value);
334   }
335 
336   /**
337    * Constructs KeyValue structure filled with specified values.
338    * @param row row key
339    * @param family family name
340    * @param qualifier column qualifier
341    * @param timestamp version timestamp
342    * @param type key type
343    * @param value column value
344    * @throws IllegalArgumentException
345    */
346   public KeyValue(final byte[] row, final byte[] family,
347       final byte[] qualifier, final long timestamp, Type type,
348       final byte[] value) {
349     this(row, family, qualifier, 0, qualifier==null ? 0 : qualifier.length,
350         timestamp, type, value, 0, value==null ? 0 : value.length);
351   }
352 
353   /**
354    * Constructs KeyValue structure filled with specified values.
355    * @param row row key
356    * @param family family name
357    * @param qualifier column qualifier
358    * @param qoffset qualifier offset
359    * @param qlength qualifier length
360    * @param timestamp version timestamp
361    * @param type key type
362    * @param value column value
363    * @param voffset value offset
364    * @param vlength value length
365    * @throws IllegalArgumentException
366    */
367   public KeyValue(byte [] row, byte [] family,
368       byte [] qualifier, int qoffset, int qlength, long timestamp, Type type,
369       byte [] value, int voffset, int vlength) {
370     this(row, 0, row==null ? 0 : row.length,
371         family, 0, family==null ? 0 : family.length,
372         qualifier, qoffset, qlength, timestamp, type,
373         value, voffset, vlength);
374   }
375 
376   /**
377    * Constructs KeyValue structure filled with specified values.
378    * <p>
379    * Column is split into two fields, family and qualifier.
380    * @param row row key
381    * @param roffset row offset
382    * @param rlength row length
383    * @param family family name
384    * @param foffset family offset
385    * @param flength family length
386    * @param qualifier column qualifier
387    * @param qoffset qualifier offset
388    * @param qlength qualifier length
389    * @param timestamp version timestamp
390    * @param type key type
391    * @param value column value
392    * @param voffset value offset
393    * @param vlength value length
394    * @throws IllegalArgumentException
395    */
396   public KeyValue(final byte [] row, final int roffset, final int rlength,
397       final byte [] family, final int foffset, final int flength,
398       final byte [] qualifier, final int qoffset, final int qlength,
399       final long timestamp, final Type type,
400       final byte [] value, final int voffset, final int vlength) {
401     this.bytes = createByteArray(row, roffset, rlength,
402         family, foffset, flength, qualifier, qoffset, qlength,
403         timestamp, type, value, voffset, vlength);
404     this.length = bytes.length;
405     this.offset = 0;
406   }
407 
408   /**
409    * Write KeyValue format into a byte array.
410    *
411    * @param row row key
412    * @param roffset row offset
413    * @param rlength row length
414    * @param family family name
415    * @param foffset family offset
416    * @param flength family length
417    * @param qualifier column qualifier
418    * @param qoffset qualifier offset
419    * @param qlength qualifier length
420    * @param timestamp version timestamp
421    * @param type key type
422    * @param value column value
423    * @param voffset value offset
424    * @param vlength value length
425    * @return The newly created byte array.
426    */
427   static byte [] createByteArray(final byte [] row, final int roffset,
428       final int rlength, final byte [] family, final int foffset, int flength,
429       final byte [] qualifier, final int qoffset, int qlength,
430       final long timestamp, final Type type,
431       final byte [] value, final int voffset, int vlength) {
432     if (rlength > Short.MAX_VALUE) {
433       throw new IllegalArgumentException("Row > " + Short.MAX_VALUE);
434     }
435     if (row == null) {
436       throw new IllegalArgumentException("Row is null");
437     }
438     // Family length
439     flength = family == null ? 0 : flength;
440     if (flength > Byte.MAX_VALUE) {
441       throw new IllegalArgumentException("Family > " + Byte.MAX_VALUE);
442     }
443     // Qualifier length
444     qlength = qualifier == null ? 0 : qlength;
445     if (qlength > Integer.MAX_VALUE - rlength - flength) {
446       throw new IllegalArgumentException("Qualifier > " + Integer.MAX_VALUE);
447     }
448     // Key length
449     long longkeylength = KEY_INFRASTRUCTURE_SIZE + rlength + flength + qlength;
450     if (longkeylength > Integer.MAX_VALUE) {
451       throw new IllegalArgumentException("keylength " + longkeylength + " > " +
452         Integer.MAX_VALUE);
453     }
454     int keylength = (int)longkeylength;
455     // Value length
456     vlength = value == null? 0 : vlength;
457     if (vlength > HConstants.MAXIMUM_VALUE_LENGTH) { // FindBugs INT_VACUOUS_COMPARISON
458       throw new IllegalArgumentException("Valuer > " +
459           HConstants.MAXIMUM_VALUE_LENGTH);
460     }
461 
462     // Allocate right-sized byte array.
463     byte [] bytes = new byte[KEYVALUE_INFRASTRUCTURE_SIZE + keylength + vlength];
464     // Write key, value and key row length.
465     int pos = 0;
466     pos = Bytes.putInt(bytes, pos, keylength);
467     pos = Bytes.putInt(bytes, pos, vlength);
468     pos = Bytes.putShort(bytes, pos, (short)(rlength & 0x0000ffff));
469     pos = Bytes.putBytes(bytes, pos, row, roffset, rlength);
470     pos = Bytes.putByte(bytes, pos, (byte)(flength & 0x0000ff));
471     if(flength != 0) {
472       pos = Bytes.putBytes(bytes, pos, family, foffset, flength);
473     }
474     if(qlength != 0) {
475       pos = Bytes.putBytes(bytes, pos, qualifier, qoffset, qlength);
476     }
477     pos = Bytes.putLong(bytes, pos, timestamp);
478     pos = Bytes.putByte(bytes, pos, type.getCode());
479     if (value != null && value.length > 0) {
480       pos = Bytes.putBytes(bytes, pos, value, voffset, vlength);
481     }
482     return bytes;
483   }
484 
485   /**
486    * Write KeyValue format into a byte array.
487    * <p>
488    * Takes column in the form <code>family:qualifier</code>
489    * @param row - row key (arbitrary byte array)
490    * @param roffset
491    * @param rlength
492    * @param column
493    * @param coffset
494    * @param clength
495    * @param timestamp
496    * @param type
497    * @param value
498    * @param voffset
499    * @param vlength
500    * @return The newly created byte array.
501    */
502   static byte [] createByteArray(final byte [] row, final int roffset,
503         final int rlength,
504       final byte [] column, final int coffset, int clength,
505       final long timestamp, final Type type,
506       final byte [] value, final int voffset, int vlength) {
507     // If column is non-null, figure where the delimiter is at.
508     int delimiteroffset = 0;
509     if (column != null && column.length > 0) {
510       delimiteroffset = getFamilyDelimiterIndex(column, coffset, clength);
511       if (delimiteroffset > Byte.MAX_VALUE) {
512         throw new IllegalArgumentException("Family > " + Byte.MAX_VALUE);
513       }
514     } else {
515       return createByteArray(row,roffset,rlength,null,0,0,null,0,0,timestamp,
516           type,value,voffset,vlength);
517     }
518     int flength = delimiteroffset-coffset;
519     int qlength = clength - flength - 1;
520     return createByteArray(row, roffset, rlength, column, coffset,
521         flength, column, delimiteroffset+1, qlength, timestamp, type,
522         value, voffset, vlength);
523   }
524 
525   // Needed doing 'contains' on List.  Only compares the key portion, not the
526   // value.
527   public boolean equals(Object other) {
528     if (!(other instanceof KeyValue)) {
529       return false;
530     }
531     KeyValue kv = (KeyValue)other;
532     // Comparing bytes should be fine doing equals test.  Shouldn't have to
533     // worry about special .META. comparators doing straight equals.
534     boolean result = Bytes.BYTES_RAWCOMPARATOR.compare(getBuffer(),
535         getKeyOffset(), getKeyLength(),
536       kv.getBuffer(), kv.getKeyOffset(), kv.getKeyLength()) == 0;
537     return result;
538   }
539 
540   public int hashCode() {
541     byte[] b = getBuffer();
542     int start = getOffset(), end = getOffset() + getLength();
543     int h = b[start++];
544     for (int i = start; i < end; i++) {
545       h = (h * 13) ^ b[i];
546     }
547     return h;
548   }
549 
550   //---------------------------------------------------------------------------
551   //
552   //  KeyValue cloning
553   //
554   //---------------------------------------------------------------------------
555 
556   /**
557    * Clones a KeyValue.  This creates a copy, re-allocating the buffer.
558    * @return Fully copied clone of this KeyValue
559    */
560   public KeyValue clone() {
561     byte [] b = new byte[this.length];
562     System.arraycopy(this.bytes, this.offset, b, 0, this.length);
563     KeyValue ret = new KeyValue(b, 0, b.length);
564     // Important to clone the memstoreTS as well - otherwise memstore's
565     // update-in-place methods (eg increment) will end up creating
566     // new entries
567     ret.setMemstoreTS(memstoreTS);
568     return ret;
569   }
570 
571   //---------------------------------------------------------------------------
572   //
573   //  String representation
574   //
575   //---------------------------------------------------------------------------
576 
577   public String toString() {
578     if (this.bytes == null || this.bytes.length == 0) {
579       return "empty";
580     }
581     return keyToString(this.bytes, this.offset + ROW_OFFSET, getKeyLength()) +
582       "/vlen=" + getValueLength();
583   }
584 
585   /**
586    * @param k Key portion of a KeyValue.
587    * @return Key as a String.
588    */
589   public static String keyToString(final byte [] k) {
590     return keyToString(k, 0, k.length);
591   }
592 
593   /**
594    * Use for logging.
595    * @param b Key portion of a KeyValue.
596    * @param o Offset to start of key
597    * @param l Length of key.
598    * @return Key as a String.
599    */
600   /**
601    * Produces a string map for this key/value pair. Useful for programmatic use
602    * and manipulation of the data stored in an HLogKey, for example, printing 
603    * as JSON. Values are left out due to their tendency to be large. If needed, 
604    * they can be added manually.
605    * 
606    * @return the Map<String,?> containing data from this key
607    */
608   public Map<String, Object> toStringMap() {
609     Map<String, Object> stringMap = new HashMap<String, Object>();
610     stringMap.put("row", Bytes.toStringBinary(getRow()));
611     stringMap.put("family", Bytes.toStringBinary(getFamily()));
612     stringMap.put("qualifier", Bytes.toStringBinary(getQualifier()));
613     stringMap.put("timestamp", getTimestamp());
614     return stringMap;
615   }
616 
617   public static String keyToString(final byte [] b, final int o, final int l) {
618     if (b == null) return "";
619     int rowlength = Bytes.toShort(b, o);
620     String row = Bytes.toStringBinary(b, o + Bytes.SIZEOF_SHORT, rowlength);
621     int columnoffset = o + Bytes.SIZEOF_SHORT + 1 + rowlength;
622     int familylength = b[columnoffset - 1];
623     int columnlength = l - ((columnoffset - o) + TIMESTAMP_TYPE_SIZE);
624     String family = familylength == 0? "":
625       Bytes.toStringBinary(b, columnoffset, familylength);
626     String qualifier = columnlength == 0? "":
627       Bytes.toStringBinary(b, columnoffset + familylength,
628       columnlength - familylength);
629     long timestamp = Bytes.toLong(b, o + (l - TIMESTAMP_TYPE_SIZE));
630     byte type = b[o + l - 1];
631 //    return row + "/" + family +
632 //      (family != null && family.length() > 0? COLUMN_FAMILY_DELIMITER: "") +
633 //      qualifier + "/" + timestamp + "/" + Type.codeToType(type);
634     return row + "/" + family +
635       (family != null && family.length() > 0? ":" :"") +
636       qualifier + "/" + timestamp + "/" + Type.codeToType(type);
637   }
638 
639   //---------------------------------------------------------------------------
640   //
641   //  Public Member Accessors
642   //
643   //---------------------------------------------------------------------------
644 
645   /**
646    * @return The byte array backing this KeyValue.
647    */
648   public byte [] getBuffer() {
649     return this.bytes;
650   }
651 
652   /**
653    * @return Offset into {@link #getBuffer()} at which this KeyValue starts.
654    */
655   public int getOffset() {
656     return this.offset;
657   }
658 
659   /**
660    * @return Length of bytes this KeyValue occupies in {@link #getBuffer()}.
661    */
662   public int getLength() {
663     return length;
664   }
665 
666   //---------------------------------------------------------------------------
667   //
668   //  Length and Offset Calculators
669   //
670   //---------------------------------------------------------------------------
671 
672   /**
673    * Determines the total length of the KeyValue stored in the specified
674    * byte array and offset.  Includes all headers.
675    * @param bytes byte array
676    * @param offset offset to start of the KeyValue
677    * @return length of entire KeyValue, in bytes
678    */
679   private static int getLength(byte [] bytes, int offset) {
680     return (2 * Bytes.SIZEOF_INT) +
681         Bytes.toInt(bytes, offset) +
682         Bytes.toInt(bytes, offset + Bytes.SIZEOF_INT);
683   }
684 
685   /**
686    * @return Key offset in backing buffer..
687    */
688   public int getKeyOffset() {
689     return this.offset + ROW_OFFSET;
690   }
691 
692   public String getKeyString() {
693     return Bytes.toStringBinary(getBuffer(), getKeyOffset(), getKeyLength());
694   }
695 
696   /**
697    * @return Length of key portion.
698    */
699   private int keyLength = 0;
700 
701   public int getKeyLength() {
702     if (keyLength == 0) {
703       keyLength = Bytes.toInt(this.bytes, this.offset);
704     }
705     return keyLength;
706   }
707 
708   /**
709    * @return Value offset
710    */
711   public int getValueOffset() {
712     return getKeyOffset() + getKeyLength();
713   }
714 
715   /**
716    * @return Value length
717    */
718   public int getValueLength() {
719     return Bytes.toInt(this.bytes, this.offset + Bytes.SIZEOF_INT);
720   }
721 
722   /**
723    * @return Row offset
724    */
725   public int getRowOffset() {
726     return getKeyOffset() + Bytes.SIZEOF_SHORT;
727   }
728 
729   /**
730    * @return Row length
731    */
732   public short getRowLength() {
733     return Bytes.toShort(this.bytes, getKeyOffset());
734   }
735 
736   /**
737    * @return Family offset
738    */
739   public int getFamilyOffset() {
740     return getFamilyOffset(getRowLength());
741   }
742 
743   /**
744    * @return Family offset
745    */
746   public int getFamilyOffset(int rlength) {
747     return this.offset + ROW_OFFSET + Bytes.SIZEOF_SHORT + rlength + Bytes.SIZEOF_BYTE;
748   }
749 
750   /**
751    * @return Family length
752    */
753   public byte getFamilyLength() {
754     return getFamilyLength(getFamilyOffset());
755   }
756 
757   /**
758    * @return Family length
759    */
760   public byte getFamilyLength(int foffset) {
761     return this.bytes[foffset-1];
762   }
763 
764   /**
765    * @return Qualifier offset
766    */
767   public int getQualifierOffset() {
768     return getQualifierOffset(getFamilyOffset());
769   }
770 
771   /**
772    * @return Qualifier offset
773    */
774   public int getQualifierOffset(int foffset) {
775     return foffset + getFamilyLength(foffset);
776   }
777 
778   /**
779    * @return Qualifier length
780    */
781   public int getQualifierLength() {
782     return getQualifierLength(getRowLength(),getFamilyLength());
783   }
784 
785   /**
786    * @return Qualifier length
787    */
788   public int getQualifierLength(int rlength, int flength) {
789     return getKeyLength() -
790       (KEY_INFRASTRUCTURE_SIZE + rlength + flength);
791   }
792 
793   /**
794    * @return Column (family + qualifier) length
795    */
796   public int getTotalColumnLength() {
797     int rlength = getRowLength();
798     int foffset = getFamilyOffset(rlength);
799     return getTotalColumnLength(rlength,foffset);
800   }
801 
802   /**
803    * @return Column (family + qualifier) length
804    */
805   public int getTotalColumnLength(int rlength, int foffset) {
806     int flength = getFamilyLength(foffset);
807     int qlength = getQualifierLength(rlength,flength);
808     return flength + qlength;
809   }
810 
811   /**
812    * @return Timestamp offset
813    */
814   public int getTimestampOffset() {
815     return getTimestampOffset(getKeyLength());
816   }
817 
818   /**
819    * @param keylength Pass if you have it to save on a int creation.
820    * @return Timestamp offset
821    */
822   public int getTimestampOffset(final int keylength) {
823     return getKeyOffset() + keylength - TIMESTAMP_TYPE_SIZE;
824   }
825 
826   /**
827    * @return True if this KeyValue has a LATEST_TIMESTAMP timestamp.
828    */
829   public boolean isLatestTimestamp() {
830     return  Bytes.compareTo(getBuffer(), getTimestampOffset(), Bytes.SIZEOF_LONG,
831       HConstants.LATEST_TIMESTAMP_BYTES, 0, Bytes.SIZEOF_LONG) == 0;
832   }
833 
834   /**
835    * @param now Time to set into <code>this</code> IFF timestamp ==
836    * {@link HConstants#LATEST_TIMESTAMP} (else, its a noop).
837    * @return True is we modified this.
838    */
839   public boolean updateLatestStamp(final byte [] now) {
840     if (this.isLatestTimestamp()) {
841       int tsOffset = getTimestampOffset();
842       System.arraycopy(now, 0, this.bytes, tsOffset, Bytes.SIZEOF_LONG);
843       return true;
844     }
845     return false;
846   }
847 
848   //---------------------------------------------------------------------------
849   //
850   //  Methods that return copies of fields
851   //
852   //---------------------------------------------------------------------------
853 
854   /**
855    * Do not use unless you have to.  Used internally for compacting and testing.
856    *
857    * Use {@link #getRow()}, {@link #getFamily()}, {@link #getQualifier()}, and
858    * {@link #getValue()} if accessing a KeyValue client-side.
859    * @return Copy of the key portion only.
860    */
861   public byte [] getKey() {
862     int keylength = getKeyLength();
863     byte [] key = new byte[keylength];
864     System.arraycopy(getBuffer(), getKeyOffset(), key, 0, keylength);
865     return key;
866   }
867 
868   /**
869    * Returns value in a new byte array.
870    * Primarily for use client-side. If server-side, use
871    * {@link #getBuffer()} with appropriate offsets and lengths instead to
872    * save on allocations.
873    * @return Value in a new byte array.
874    */
875   public byte [] getValue() {
876     int o = getValueOffset();
877     int l = getValueLength();
878     byte [] result = new byte[l];
879     System.arraycopy(getBuffer(), o, result, 0, l);
880     return result;
881   }
882 
883   /**
884    * Primarily for use client-side.  Returns the row of this KeyValue in a new
885    * byte array.<p>
886    *
887    * If server-side, use {@link #getBuffer()} with appropriate offsets and
888    * lengths instead.
889    * @return Row in a new byte array.
890    */
891   public byte [] getRow() {
892     if (rowCache == null) {
893       int o = getRowOffset();
894       short l = getRowLength();
895       rowCache = new byte[l];
896       System.arraycopy(getBuffer(), o, rowCache, 0, l);
897     }
898     return rowCache;
899   }
900 
901   /**
902    *
903    * @return Timestamp
904    */
905   private long timestampCache = -1;
906   public long getTimestamp() {
907     if (timestampCache == -1) {
908       timestampCache = getTimestamp(getKeyLength());
909     }
910     return timestampCache;
911   }
912 
913   /**
914    * @param keylength Pass if you have it to save on a int creation.
915    * @return Timestamp
916    */
917   long getTimestamp(final int keylength) {
918     int tsOffset = getTimestampOffset(keylength);
919     return Bytes.toLong(this.bytes, tsOffset);
920   }
921 
922   /**
923    * @return Type of this KeyValue.
924    */
925   public byte getType() {
926     return getType(getKeyLength());
927   }
928 
929   /**
930    * @param keylength Pass if you have it to save on a int creation.
931    * @return Type of this KeyValue.
932    */
933   byte getType(final int keylength) {
934     return this.bytes[this.offset + keylength - 1 + ROW_OFFSET];
935   }
936 
937   /**
938    * @return True if a delete type, a {@link KeyValue.Type#Delete} or
939    * a {KeyValue.Type#DeleteFamily} or a {@link KeyValue.Type#DeleteColumn}
940    * KeyValue type.
941    */
942   public boolean isDelete() {
943     int t = getType();
944     return Type.Delete.getCode() <= t && t <= Type.DeleteFamily.getCode();
945   }
946 
947   /**
948    * @return True if this KV is a {@link KeyValue.Type#Delete} type.
949    */
950   public boolean isDeleteType() {
951     return getType() == Type.Delete.getCode();
952   }
953 
954   /**
955    * @return True if this KV is a delete family type.
956    */
957   public boolean isDeleteFamily() {
958     return getType() == Type.DeleteFamily.getCode();
959   }
960 
961   /**
962    *
963    * @return True if this KV is a delete family or column type.
964    */
965   public boolean isDeleteColumnOrFamily() {
966     int t = getType();
967     return t == Type.DeleteColumn.getCode() || t == Type.DeleteFamily.getCode();
968   }
969 
970   /**
971    * Primarily for use client-side.  Returns the family of this KeyValue in a
972    * new byte array.<p>
973    *
974    * If server-side, use {@link #getBuffer()} with appropriate offsets and
975    * lengths instead.
976    * @return Returns family. Makes a copy.
977    */
978   public byte [] getFamily() {
979     int o = getFamilyOffset();
980     int l = getFamilyLength(o);
981     byte [] result = new byte[l];
982     System.arraycopy(this.bytes, o, result, 0, l);
983     return result;
984   }
985 
986   /**
987    * Primarily for use client-side.  Returns the column qualifier of this
988    * KeyValue in a new byte array.<p>
989    *
990    * If server-side, use {@link #getBuffer()} with appropriate offsets and
991    * lengths instead.
992    * Use {@link #getBuffer()} with appropriate offsets and lengths instead.
993    * @return Returns qualifier. Makes a copy.
994    */
995   public byte [] getQualifier() {
996     int o = getQualifierOffset();
997     int l = getQualifierLength();
998     byte [] result = new byte[l];
999     System.arraycopy(this.bytes, o, result, 0, l);
1000     return result;
1001   }
1002 
1003   //---------------------------------------------------------------------------
1004   //
1005   //  KeyValue splitter
1006   //
1007   //---------------------------------------------------------------------------
1008 
1009   /**
1010    * Utility class that splits a KeyValue buffer into separate byte arrays.
1011    * <p>
1012    * Should get rid of this if we can, but is very useful for debugging.
1013    */
1014   public static class SplitKeyValue {
1015     private byte [][] split;
1016     SplitKeyValue() {
1017       this.split = new byte[6][];
1018     }
1019     public void setRow(byte [] value) { this.split[0] = value; }
1020     public void setFamily(byte [] value) { this.split[1] = value; }
1021     public void setQualifier(byte [] value) { this.split[2] = value; }
1022     public void setTimestamp(byte [] value) { this.split[3] = value; }
1023     public void setType(byte [] value) { this.split[4] = value; }
1024     public void setValue(byte [] value) { this.split[5] = value; }
1025     public byte [] getRow() { return this.split[0]; }
1026     public byte [] getFamily() { return this.split[1]; }
1027     public byte [] getQualifier() { return this.split[2]; }
1028     public byte [] getTimestamp() { return this.split[3]; }
1029     public byte [] getType() { return this.split[4]; }
1030     public byte [] getValue() { return this.split[5]; }
1031   }
1032 
1033   public SplitKeyValue split() {
1034     SplitKeyValue split = new SplitKeyValue();
1035     int splitOffset = this.offset;
1036     int keyLen = Bytes.toInt(bytes, splitOffset);
1037     splitOffset += Bytes.SIZEOF_INT;
1038     int valLen = Bytes.toInt(bytes, splitOffset);
1039     splitOffset += Bytes.SIZEOF_INT;
1040     short rowLen = Bytes.toShort(bytes, splitOffset);
1041     splitOffset += Bytes.SIZEOF_SHORT;
1042     byte [] row = new byte[rowLen];
1043     System.arraycopy(bytes, splitOffset, row, 0, rowLen);
1044     splitOffset += rowLen;
1045     split.setRow(row);
1046     byte famLen = bytes[splitOffset];
1047     splitOffset += Bytes.SIZEOF_BYTE;
1048     byte [] family = new byte[famLen];
1049     System.arraycopy(bytes, splitOffset, family, 0, famLen);
1050     splitOffset += famLen;
1051     split.setFamily(family);
1052     int colLen = keyLen -
1053       (rowLen + famLen + Bytes.SIZEOF_SHORT + Bytes.SIZEOF_BYTE +
1054       Bytes.SIZEOF_LONG + Bytes.SIZEOF_BYTE);
1055     byte [] qualifier = new byte[colLen];
1056     System.arraycopy(bytes, splitOffset, qualifier, 0, colLen);
1057     splitOffset += colLen;
1058     split.setQualifier(qualifier);
1059     byte [] timestamp = new byte[Bytes.SIZEOF_LONG];
1060     System.arraycopy(bytes, splitOffset, timestamp, 0, Bytes.SIZEOF_LONG);
1061     splitOffset += Bytes.SIZEOF_LONG;
1062     split.setTimestamp(timestamp);
1063     byte [] type = new byte[1];
1064     type[0] = bytes[splitOffset];
1065     splitOffset += Bytes.SIZEOF_BYTE;
1066     split.setType(type);
1067     byte [] value = new byte[valLen];
1068     System.arraycopy(bytes, splitOffset, value, 0, valLen);
1069     split.setValue(value);
1070     return split;
1071   }
1072 
1073   //---------------------------------------------------------------------------
1074   //
1075   //  Compare specified fields against those contained in this KeyValue
1076   //
1077   //---------------------------------------------------------------------------
1078 
1079   /**
1080    * @param family
1081    * @return True if matching families.
1082    */
1083   public boolean matchingFamily(final byte [] family) {
1084     return matchingFamily(family, 0, family.length);
1085   }
1086 
1087   public boolean matchingFamily(final byte[] family, int offset, int length) {
1088     if (this.length == 0 || this.bytes.length == 0) {
1089       return false;
1090     }
1091     return Bytes.compareTo(family, offset, length,
1092         this.bytes, getFamilyOffset(), getFamilyLength()) == 0;
1093   }
1094 
1095   public boolean matchingFamily(final KeyValue other) {
1096     return matchingFamily(other.getBuffer(), other.getFamilyOffset(),
1097         other.getFamilyLength());
1098   }
1099 
1100   /**
1101    * @param qualifier
1102    * @return True if matching qualifiers.
1103    */
1104   public boolean matchingQualifier(final byte [] qualifier) {
1105     return matchingQualifier(qualifier, 0, qualifier.length);
1106   }
1107 
1108   public boolean matchingQualifier(final byte [] qualifier, int offset, int length) {
1109     return Bytes.compareTo(qualifier, offset, length,
1110         this.bytes, getQualifierOffset(), getQualifierLength()) == 0;
1111   }
1112 
1113   public boolean matchingQualifier(final KeyValue other) {
1114     return matchingQualifier(other.getBuffer(), other.getQualifierOffset(),
1115         other.getQualifierLength());
1116   }
1117 
1118   public boolean matchingRow(final byte [] row) {
1119     return matchingRow(row, 0, row.length);
1120   }
1121 
1122   public boolean matchingRow(final byte[] row, int offset, int length) {
1123     return Bytes.compareTo(row, offset, length,
1124         this.bytes, getRowOffset(), getRowLength()) == 0;
1125   }
1126 
1127   public boolean matchingRow(KeyValue other) {
1128     return matchingRow(other.getBuffer(), other.getRowOffset(),
1129         other.getRowLength());
1130   }
1131 
1132   /**
1133    * @param column Column minus its delimiter
1134    * @return True if column matches.
1135    */
1136   public boolean matchingColumnNoDelimiter(final byte [] column) {
1137     int rl = getRowLength();
1138     int o = getFamilyOffset(rl);
1139     int fl = getFamilyLength(o);
1140     int l = fl + getQualifierLength(rl,fl);
1141     return Bytes.compareTo(column, 0, column.length, this.bytes, o, l) == 0;
1142   }
1143 
1144   /**
1145    *
1146    * @param family column family
1147    * @param qualifier column qualifier
1148    * @return True if column matches
1149    */
1150   public boolean matchingColumn(final byte[] family, final byte[] qualifier) {
1151     int rl = getRowLength();
1152     int o = getFamilyOffset(rl);
1153     int fl = getFamilyLength(o);
1154     int ql = getQualifierLength(rl,fl);
1155     if (Bytes.compareTo(family, 0, family.length, this.bytes, o, family.length)
1156         != 0) {
1157       return false;
1158     }
1159     if (qualifier == null || qualifier.length == 0) {
1160       if (ql == 0) {
1161         return true;
1162       }
1163       return false;
1164     }
1165     return Bytes.compareTo(qualifier, 0, qualifier.length,
1166         this.bytes, o + fl, ql) == 0;
1167   }
1168 
1169   /**
1170    * @param left
1171    * @param loffset
1172    * @param llength
1173    * @param lfamilylength Offset of family delimiter in left column.
1174    * @param right
1175    * @param roffset
1176    * @param rlength
1177    * @param rfamilylength Offset of family delimiter in right column.
1178    * @return The result of the comparison.
1179    */
1180   static int compareColumns(final byte [] left, final int loffset,
1181       final int llength, final int lfamilylength,
1182       final byte [] right, final int roffset, final int rlength,
1183       final int rfamilylength) {
1184     // Compare family portion first.
1185     int diff = Bytes.compareTo(left, loffset, lfamilylength,
1186       right, roffset, rfamilylength);
1187     if (diff != 0) {
1188       return diff;
1189     }
1190     // Compare qualifier portion
1191     return Bytes.compareTo(left, loffset + lfamilylength,
1192       llength - lfamilylength,
1193       right, roffset + rfamilylength, rlength - rfamilylength);
1194   }
1195 
1196   /**
1197    * @return True if non-null row and column.
1198    */
1199   public boolean nonNullRowAndColumn() {
1200     return getRowLength() > 0 && !isEmptyColumn();
1201   }
1202 
1203   /**
1204    * @return True if column is empty.
1205    */
1206   public boolean isEmptyColumn() {
1207     return getQualifierLength() == 0;
1208   }
1209 
1210   /**
1211    * Converts this KeyValue to only contain the key portion (the value is
1212    * changed to be null).  This method does a full copy of the backing byte
1213    * array and does not modify the original byte array of this KeyValue.
1214    * <p>
1215    * This method is used by <code>KeyOnlyFilter</code> and is an advanced feature of
1216    * KeyValue, proceed with caution.
1217    * @param lenAsVal replace value with the actual value length (false=empty)
1218    */
1219   public void convertToKeyOnly(boolean lenAsVal) {
1220     // KV format:  <keylen:4><valuelen:4><key:keylen><value:valuelen>
1221     // Rebuild as: <keylen:4><0:4><key:keylen>
1222     int dataLen = lenAsVal? Bytes.SIZEOF_INT : 0;
1223     byte [] newBuffer = new byte[getKeyLength() + (2 * Bytes.SIZEOF_INT) + dataLen];
1224     System.arraycopy(this.bytes, this.offset, newBuffer, 0, 
1225         Math.min(newBuffer.length,this.length));
1226     Bytes.putInt(newBuffer, Bytes.SIZEOF_INT, dataLen);
1227     if (lenAsVal) {
1228       Bytes.putInt(newBuffer, newBuffer.length - dataLen, this.getValueLength());
1229     }
1230     this.bytes = newBuffer;
1231     this.offset = 0;
1232     this.length = newBuffer.length;
1233   }
1234 
1235   /**
1236    * Splits a column in family:qualifier form into separate byte arrays.
1237    * <p>
1238    * Not recommend to be used as this is old-style API.
1239    * @param c  The column.
1240    * @return The parsed column.
1241    */
1242   public static byte [][] parseColumn(byte [] c) {
1243     final int index = getDelimiter(c, 0, c.length, COLUMN_FAMILY_DELIMITER);
1244     if (index == -1) {
1245       // If no delimiter, return array of size 1
1246       return new byte [][] { c };
1247     } else if(index == c.length - 1) {
1248       // Only a family, return array size 1
1249       byte [] family = new byte[c.length-1];
1250       System.arraycopy(c, 0, family, 0, family.length);
1251       return new byte [][] { family };
1252     }
1253     // Family and column, return array size 2
1254     final byte [][] result = new byte [2][];
1255     result[0] = new byte [index];
1256     System.arraycopy(c, 0, result[0], 0, index);
1257     final int len = c.length - (index + 1);
1258     result[1] = new byte[len];
1259     System.arraycopy(c, index + 1 /*Skip delimiter*/, result[1], 0,
1260       len);
1261     return result;
1262   }
1263 
1264   /**
1265    * Makes a column in family:qualifier form from separate byte arrays.
1266    * <p>
1267    * Not recommended for usage as this is old-style API.
1268    * @param family
1269    * @param qualifier
1270    * @return family:qualifier
1271    */
1272   public static byte [] makeColumn(byte [] family, byte [] qualifier) {
1273     return Bytes.add(family, COLUMN_FAMILY_DELIM_ARRAY, qualifier);
1274   }
1275 
1276   /**
1277    * @param b
1278    * @return Index of the family-qualifier colon delimiter character in passed
1279    * buffer.
1280    */
1281   public static int getFamilyDelimiterIndex(final byte [] b, final int offset,
1282       final int length) {
1283     return getRequiredDelimiter(b, offset, length, COLUMN_FAMILY_DELIMITER);
1284   }
1285 
1286   private static int getRequiredDelimiter(final byte [] b,
1287       final int offset, final int length, final int delimiter) {
1288     int index = getDelimiter(b, offset, length, delimiter);
1289     if (index < 0) {
1290       throw new IllegalArgumentException("No " + (char)delimiter + " in <" +
1291         Bytes.toString(b) + ">" + ", length=" + length + ", offset=" + offset);
1292     }
1293     return index;
1294   }
1295 
1296   static int getRequiredDelimiterInReverse(final byte [] b,
1297       final int offset, final int length, final int delimiter) {
1298     int index = getDelimiterInReverse(b, offset, length, delimiter);
1299     if (index < 0) {
1300       throw new IllegalArgumentException("No " + delimiter + " in <" +
1301         Bytes.toString(b) + ">" + ", length=" + length + ", offset=" + offset);
1302     }
1303     return index;
1304   }
1305 
1306   /**
1307    * @param b
1308    * @param delimiter
1309    * @return Index of delimiter having started from start of <code>b</code>
1310    * moving rightward.
1311    */
1312   public static int getDelimiter(final byte [] b, int offset, final int length,
1313       final int delimiter) {
1314     if (b == null) {
1315       throw new NullPointerException();
1316     }
1317     int result = -1;
1318     for (int i = offset; i < length + offset; i++) {
1319       if (b[i] == delimiter) {
1320         result = i;
1321         break;
1322       }
1323     }
1324     return result;
1325   }
1326 
1327   /**
1328    * Find index of passed delimiter walking from end of buffer backwards.
1329    * @param b
1330    * @param delimiter
1331    * @return Index of delimiter
1332    */
1333   public static int getDelimiterInReverse(final byte [] b, final int offset,
1334       final int length, final int delimiter) {
1335     if (b == null) {
1336       throw new NullPointerException();
1337     }
1338     int result = -1;
1339     for (int i = (offset + length) - 1; i >= offset; i--) {
1340       if (b[i] == delimiter) {
1341         result = i;
1342         break;
1343       }
1344     }
1345     return result;
1346   }
1347 
1348   /**
1349    * A {@link KVComparator} for <code>-ROOT-</code> catalog table
1350    * {@link KeyValue}s.
1351    */
1352   public static class RootComparator extends MetaComparator {
1353     private final KeyComparator rawcomparator = new RootKeyComparator();
1354 
1355     public KeyComparator getRawComparator() {
1356       return this.rawcomparator;
1357     }
1358 
1359     @Override
1360     protected Object clone() throws CloneNotSupportedException {
1361       return new RootComparator();
1362     }
1363   }
1364 
1365   /**
1366    * A {@link KVComparator} for <code>.META.</code> catalog table
1367    * {@link KeyValue}s.
1368    */
1369   public static class MetaComparator extends KVComparator {
1370     private final KeyComparator rawcomparator = new MetaKeyComparator();
1371 
1372     public KeyComparator getRawComparator() {
1373       return this.rawcomparator;
1374     }
1375 
1376     @Override
1377     protected Object clone() throws CloneNotSupportedException {
1378       return new MetaComparator();
1379     }
1380   }
1381 
1382   /**
1383    * Compare KeyValues.  When we compare KeyValues, we only compare the Key
1384    * portion.  This means two KeyValues with same Key but different Values are
1385    * considered the same as far as this Comparator is concerned.
1386    * Hosts a {@link KeyComparator}.
1387    */
1388   public static class KVComparator implements java.util.Comparator<KeyValue> {
1389     private final KeyComparator rawcomparator = new KeyComparator();
1390 
1391     /**
1392      * @return RawComparator that can compare the Key portion of a KeyValue.
1393      * Used in hfile where indices are the Key portion of a KeyValue.
1394      */
1395     public KeyComparator getRawComparator() {
1396       return this.rawcomparator;
1397     }
1398 
1399     public int compare(final KeyValue left, final KeyValue right) {
1400       int ret = getRawComparator().compare(left.getBuffer(),
1401           left.getOffset() + ROW_OFFSET, left.getKeyLength(),
1402           right.getBuffer(), right.getOffset() + ROW_OFFSET,
1403           right.getKeyLength());
1404       if (ret != 0) return ret;
1405       // Negate this comparison so later edits show up first
1406       return -Longs.compare(left.getMemstoreTS(), right.getMemstoreTS());
1407     }
1408 
1409     public int compareTimestamps(final KeyValue left, final KeyValue right) {
1410       return compareTimestamps(left, left.getKeyLength(), right,
1411         right.getKeyLength());
1412     }
1413 
1414     int compareTimestamps(final KeyValue left, final int lkeylength,
1415         final KeyValue right, final int rkeylength) {
1416       // Compare timestamps
1417       long ltimestamp = left.getTimestamp(lkeylength);
1418       long rtimestamp = right.getTimestamp(rkeylength);
1419       return getRawComparator().compareTimestamps(ltimestamp, rtimestamp);
1420     }
1421 
1422     /**
1423      * @param left
1424      * @param right
1425      * @return Result comparing rows.
1426      */
1427     public int compareRows(final KeyValue left, final KeyValue right) {
1428       return compareRows(left, left.getRowLength(), right,
1429           right.getRowLength());
1430     }
1431 
1432     /**
1433      * @param left
1434      * @param lrowlength Length of left row.
1435      * @param right
1436      * @param rrowlength Length of right row.
1437      * @return Result comparing rows.
1438      */
1439     public int compareRows(final KeyValue left, final short lrowlength,
1440         final KeyValue right, final short rrowlength) {
1441       return getRawComparator().compareRows(left.getBuffer(),
1442           left.getRowOffset(), lrowlength,
1443         right.getBuffer(), right.getRowOffset(), rrowlength);
1444     }
1445 
1446     /**
1447      * @param left
1448      * @param row - row key (arbitrary byte array)
1449      * @return RawComparator
1450      */
1451     public int compareRows(final KeyValue left, final byte [] row) {
1452       return getRawComparator().compareRows(left.getBuffer(),
1453           left.getRowOffset(), left.getRowLength(), row, 0, row.length);
1454     }
1455 
1456     public int compareRows(byte [] left, int loffset, int llength,
1457         byte [] right, int roffset, int rlength) {
1458       return getRawComparator().compareRows(left, loffset, llength,
1459         right, roffset, rlength);
1460     }
1461 
1462     public int compareColumns(final KeyValue left, final byte [] right,
1463         final int roffset, final int rlength, final int rfamilyoffset) {
1464       int offset = left.getFamilyOffset();
1465       int length = left.getFamilyLength() + left.getQualifierLength();
1466       return getRawComparator().compareColumns(left.getBuffer(), offset, length,
1467         left.getFamilyLength(offset),
1468         right, roffset, rlength, rfamilyoffset);
1469     }
1470 
1471     int compareColumns(final KeyValue left, final short lrowlength,
1472         final KeyValue right, final short rrowlength) {
1473       int lfoffset = left.getFamilyOffset(lrowlength);
1474       int rfoffset = right.getFamilyOffset(rrowlength);
1475       int lclength = left.getTotalColumnLength(lrowlength,lfoffset);
1476       int rclength = right.getTotalColumnLength(rrowlength, rfoffset);
1477       int lfamilylength = left.getFamilyLength(lfoffset);
1478       int rfamilylength = right.getFamilyLength(rfoffset);
1479       return getRawComparator().compareColumns(left.getBuffer(), lfoffset,
1480           lclength, lfamilylength,
1481         right.getBuffer(), rfoffset, rclength, rfamilylength);
1482     }
1483 
1484     /**
1485      * Compares the row and column of two keyvalues for equality
1486      * @param left
1487      * @param right
1488      * @return True if same row and column.
1489      */
1490     public boolean matchingRowColumn(final KeyValue left,
1491         final KeyValue right) {
1492       short lrowlength = left.getRowLength();
1493       short rrowlength = right.getRowLength();
1494       // TsOffset = end of column data. just comparing Row+CF length of each
1495       return ((left.getTimestampOffset() - left.getOffset()) == 
1496               (right.getTimestampOffset() - right.getOffset())) &&
1497         matchingRows(left, lrowlength, right, rrowlength) &&
1498         compareColumns(left, lrowlength, right, rrowlength) == 0;
1499     }
1500 
1501     /**
1502      * @param left
1503      * @param right
1504      * @return True if rows match.
1505      */
1506     public boolean matchingRows(final KeyValue left, final byte [] right) {
1507       return compareRows(left, right) == 0;
1508     }
1509 
1510     /**
1511      * Compares the row of two keyvalues for equality
1512      * @param left
1513      * @param right
1514      * @return True if rows match.
1515      */
1516     public boolean matchingRows(final KeyValue left, final KeyValue right) {
1517       short lrowlength = left.getRowLength();
1518       short rrowlength = right.getRowLength();
1519       return matchingRows(left, lrowlength, right, rrowlength);
1520     }
1521 
1522     /**
1523      * @param left
1524      * @param lrowlength
1525      * @param right
1526      * @param rrowlength
1527      * @return True if rows match.
1528      */
1529     public boolean matchingRows(final KeyValue left, final short lrowlength,
1530         final KeyValue right, final short rrowlength) {
1531       return lrowlength == rrowlength &&
1532         compareRows(left, lrowlength, right, rrowlength) == 0;
1533     }
1534 
1535     public boolean matchingRows(final byte [] left, final int loffset,
1536         final int llength,
1537         final byte [] right, final int roffset, final int rlength) {
1538       int compare = compareRows(left, loffset, llength,
1539           right, roffset, rlength);
1540       if (compare != 0) {
1541         return false;
1542       }
1543       return true;
1544     }
1545 
1546     /**
1547      * Compares the row and timestamp of two keys
1548      * Was called matchesWithoutColumn in HStoreKey.
1549      * @param right Key to compare against.
1550      * @return True if same row and timestamp is greater than the timestamp in
1551      * <code>right</code>
1552      */
1553     public boolean matchingRowsGreaterTimestamp(final KeyValue left,
1554         final KeyValue right) {
1555       short lrowlength = left.getRowLength();
1556       short rrowlength = right.getRowLength();
1557       if (!matchingRows(left, lrowlength, right, rrowlength)) {
1558         return false;
1559       }
1560       return left.getTimestamp() >= right.getTimestamp();
1561     }
1562 
1563     @Override
1564     protected Object clone() throws CloneNotSupportedException {
1565       return new KVComparator();
1566     }
1567 
1568     /**
1569      * @return Comparator that ignores timestamps; useful counting versions.
1570      */
1571     public KVComparator getComparatorIgnoringTimestamps() {
1572       KVComparator c = null;
1573       try {
1574         c = (KVComparator)this.clone();
1575         c.getRawComparator().ignoreTimestamp = true;
1576       } catch (CloneNotSupportedException e) {
1577         LOG.error("Not supported", e);
1578       }
1579       return c;
1580     }
1581 
1582     /**
1583      * @return Comparator that ignores key type; useful checking deletes
1584      */
1585     public KVComparator getComparatorIgnoringType() {
1586       KVComparator c = null;
1587       try {
1588         c = (KVComparator)this.clone();
1589         c.getRawComparator().ignoreType = true;
1590       } catch (CloneNotSupportedException e) {
1591         LOG.error("Not supported", e);
1592       }
1593       return c;
1594     }
1595   }
1596 
1597   /**
1598    * Creates a KeyValue that is last on the specified row id. That is,
1599    * every other possible KeyValue for the given row would compareTo()
1600    * less than the result of this call.
1601    * @param row row key
1602    * @return Last possible KeyValue on passed <code>row</code>
1603    */
1604   public static KeyValue createLastOnRow(final byte[] row) {
1605     return new KeyValue(row, null, null, HConstants.LATEST_TIMESTAMP, Type.Minimum);
1606   }
1607 
1608   /**
1609    * Create a KeyValue that is smaller than all other possible KeyValues
1610    * for the given row. That is any (valid) KeyValue on 'row' would sort
1611    * _after_ the result.
1612    *
1613    * @param row - row key (arbitrary byte array)
1614    * @return First possible KeyValue on passed <code>row</code>
1615    */
1616   public static KeyValue createFirstOnRow(final byte [] row) {
1617     return createFirstOnRow(row, HConstants.LATEST_TIMESTAMP);
1618   }
1619 
1620   /**
1621    * Creates a KeyValue that is smaller than all other KeyValues that
1622    * are older than the passed timestamp.
1623    * @param row - row key (arbitrary byte array)
1624    * @param ts - timestamp
1625    * @return First possible key on passed <code>row</code> and timestamp.
1626    */
1627   public static KeyValue createFirstOnRow(final byte [] row,
1628       final long ts) {
1629     return new KeyValue(row, null, null, ts, Type.Maximum);
1630   }
1631 
1632   /**
1633    * @param row - row key (arbitrary byte array)
1634    * @param c column - {@link #parseColumn(byte[])} is called to split
1635    * the column.
1636    * @param ts - timestamp
1637    * @return First possible key on passed <code>row</code>, column and timestamp
1638    * @deprecated
1639    */
1640   public static KeyValue createFirstOnRow(final byte [] row, final byte [] c,
1641       final long ts) {
1642     byte [][] split = parseColumn(c);
1643     return new KeyValue(row, split[0], split[1], ts, Type.Maximum);
1644   }
1645 
1646   /**
1647    * Create a KeyValue for the specified row, family and qualifier that would be
1648    * smaller than all other possible KeyValues that have the same row,family,qualifier.
1649    * Used for seeking.
1650    * @param row - row key (arbitrary byte array)
1651    * @param family - family name
1652    * @param qualifier - column qualifier
1653    * @return First possible key on passed <code>row</code>, and column.
1654    */
1655   public static KeyValue createFirstOnRow(final byte [] row, final byte [] family,
1656       final byte [] qualifier) {
1657     return new KeyValue(row, family, qualifier, HConstants.LATEST_TIMESTAMP, Type.Maximum);
1658   }
1659 
1660   /**
1661    * @param row - row key (arbitrary byte array)
1662    * @param f - family name
1663    * @param q - column qualifier
1664    * @param ts - timestamp
1665    * @return First possible key on passed <code>row</code>, column and timestamp
1666    */
1667   public static KeyValue createFirstOnRow(final byte [] row, final byte [] f,
1668       final byte [] q, final long ts) {
1669     return new KeyValue(row, f, q, ts, Type.Maximum);
1670   }
1671 
1672   /**
1673    * Create a KeyValue for the specified row, family and qualifier that would be
1674    * smaller than all other possible KeyValues that have the same row,
1675    * family, qualifier.
1676    * Used for seeking.
1677    * @param row row key
1678    * @param roffset row offset
1679    * @param rlength row length
1680    * @param family family name
1681    * @param foffset family offset
1682    * @param flength family length
1683    * @param qualifier column qualifier
1684    * @param qoffset qualifier offset
1685    * @param qlength qualifier length
1686    * @return First possible key on passed Row, Family, Qualifier.
1687    */
1688   public static KeyValue createFirstOnRow(final byte [] row,
1689       final int roffset, final int rlength, final byte [] family,
1690       final int foffset, final int flength, final byte [] qualifier,
1691       final int qoffset, final int qlength) {
1692     return new KeyValue(row, roffset, rlength, family,
1693         foffset, flength, qualifier, qoffset, qlength,
1694         HConstants.LATEST_TIMESTAMP, Type.Maximum, null, 0, 0);
1695   }
1696 
1697   /**
1698    * Create a KeyValue for the specified row, family and qualifier that would be
1699    * larger than or equal to all other possible KeyValues that have the same
1700    * row, family, qualifier.
1701    * Used for reseeking.
1702    * @param row row key
1703    * @param roffset row offset
1704    * @param rlength row length
1705    * @param family family name
1706    * @param foffset family offset
1707    * @param flength family length
1708    * @param qualifier column qualifier
1709    * @param qoffset qualifier offset
1710    * @param qlength qualifier length
1711    * @return Last possible key on passed row, family, qualifier.
1712    */
1713   public static KeyValue createLastOnRow(final byte [] row,
1714       final int roffset, final int rlength, final byte [] family,
1715       final int foffset, final int flength, final byte [] qualifier,
1716       final int qoffset, final int qlength) {
1717     return new KeyValue(row, roffset, rlength, family,
1718         foffset, flength, qualifier, qoffset, qlength,
1719         HConstants.OLDEST_TIMESTAMP, Type.Minimum, null, 0, 0);
1720   }
1721 
1722   /**
1723    * @param b
1724    * @return A KeyValue made of a byte array that holds the key-only part.
1725    * Needed to convert hfile index members to KeyValues.
1726    */
1727   public static KeyValue createKeyValueFromKey(final byte [] b) {
1728     return createKeyValueFromKey(b, 0, b.length);
1729   }
1730 
1731   /**
1732    * @param bb
1733    * @return A KeyValue made of a byte buffer that holds the key-only part.
1734    * Needed to convert hfile index members to KeyValues.
1735    */
1736   public static KeyValue createKeyValueFromKey(final ByteBuffer bb) {
1737     return createKeyValueFromKey(bb.array(), bb.arrayOffset(), bb.limit());
1738   }
1739 
1740   /**
1741    * @param b
1742    * @param o
1743    * @param l
1744    * @return A KeyValue made of a byte array that holds the key-only part.
1745    * Needed to convert hfile index members to KeyValues.
1746    */
1747   public static KeyValue createKeyValueFromKey(final byte [] b, final int o,
1748       final int l) {
1749     byte [] newb = new byte[b.length + ROW_OFFSET];
1750     System.arraycopy(b, o, newb, ROW_OFFSET, l);
1751     Bytes.putInt(newb, 0, b.length);
1752     Bytes.putInt(newb, Bytes.SIZEOF_INT, 0);
1753     return new KeyValue(newb);
1754   }
1755 
1756   /**
1757    * Compare key portion of a {@link KeyValue} for keys in <code>-ROOT-<code>
1758    * table.
1759    */
1760   public static class RootKeyComparator extends MetaKeyComparator {
1761     public int compareRows(byte [] left, int loffset, int llength,
1762         byte [] right, int roffset, int rlength) {
1763       // Rows look like this: .META.,ROW_FROM_META,RID
1764       //        LOG.info("ROOT " + Bytes.toString(left, loffset, llength) +
1765       //          "---" + Bytes.toString(right, roffset, rlength));
1766       final int metalength = 7; // '.META.' length
1767       int lmetaOffsetPlusDelimiter = loffset + metalength;
1768       int leftFarDelimiter = getDelimiterInReverse(left,
1769           lmetaOffsetPlusDelimiter,
1770           llength - metalength, HRegionInfo.DELIMITER);
1771       int rmetaOffsetPlusDelimiter = roffset + metalength;
1772       int rightFarDelimiter = getDelimiterInReverse(right,
1773           rmetaOffsetPlusDelimiter, rlength - metalength,
1774           HRegionInfo.DELIMITER);
1775       if (leftFarDelimiter < 0 && rightFarDelimiter >= 0) {
1776         // Nothing between .META. and regionid.  Its first key.
1777         return -1;
1778       } else if (rightFarDelimiter < 0 && leftFarDelimiter >= 0) {
1779         return 1;
1780       } else if (leftFarDelimiter < 0 && rightFarDelimiter < 0) {
1781         return 0;
1782       }
1783       int result = super.compareRows(left, lmetaOffsetPlusDelimiter,
1784           leftFarDelimiter - lmetaOffsetPlusDelimiter,
1785           right, rmetaOffsetPlusDelimiter,
1786           rightFarDelimiter - rmetaOffsetPlusDelimiter);
1787       if (result != 0) {
1788         return result;
1789       }
1790       // Compare last part of row, the rowid.
1791       leftFarDelimiter++;
1792       rightFarDelimiter++;
1793       result = compareRowid(left, leftFarDelimiter,
1794           llength - (leftFarDelimiter - loffset),
1795           right, rightFarDelimiter, rlength - (rightFarDelimiter - roffset));
1796       return result;
1797     }
1798   }
1799 
1800   /**
1801    * Comparator that compares row component only of a KeyValue.
1802    */
1803   public static class RowComparator implements Comparator<KeyValue> {
1804     final KVComparator comparator;
1805 
1806     public RowComparator(final KVComparator c) {
1807       this.comparator = c;
1808     }
1809 
1810     public int compare(KeyValue left, KeyValue right) {
1811       return comparator.compareRows(left, right);
1812     }
1813   }
1814 
1815   /**
1816    * Compare key portion of a {@link KeyValue} for keys in <code>.META.</code>
1817    * table.
1818    */
1819   public static class MetaKeyComparator extends KeyComparator {
1820     public int compareRows(byte [] left, int loffset, int llength,
1821         byte [] right, int roffset, int rlength) {
1822       //        LOG.info("META " + Bytes.toString(left, loffset, llength) +
1823       //          "---" + Bytes.toString(right, roffset, rlength));
1824       int leftDelimiter = getDelimiter(left, loffset, llength,
1825           HRegionInfo.DELIMITER);
1826       int rightDelimiter = getDelimiter(right, roffset, rlength,
1827           HRegionInfo.DELIMITER);
1828       if (leftDelimiter < 0 && rightDelimiter >= 0) {
1829         // Nothing between .META. and regionid.  Its first key.
1830         return -1;
1831       } else if (rightDelimiter < 0 && leftDelimiter >= 0) {
1832         return 1;
1833       } else if (leftDelimiter < 0 && rightDelimiter < 0) {
1834         return 0;
1835       }
1836       // Compare up to the delimiter
1837       int result = Bytes.compareTo(left, loffset, leftDelimiter - loffset,
1838           right, roffset, rightDelimiter - roffset);
1839       if (result != 0) {
1840         return result;
1841       }
1842       // Compare middle bit of the row.
1843       // Move past delimiter
1844       leftDelimiter++;
1845       rightDelimiter++;
1846       int leftFarDelimiter = getRequiredDelimiterInReverse(left, leftDelimiter,
1847           llength - (leftDelimiter - loffset), HRegionInfo.DELIMITER);
1848       int rightFarDelimiter = getRequiredDelimiterInReverse(right,
1849           rightDelimiter, rlength - (rightDelimiter - roffset),
1850           HRegionInfo.DELIMITER);
1851       // Now compare middlesection of row.
1852       result = super.compareRows(left, leftDelimiter,
1853           leftFarDelimiter - leftDelimiter, right, rightDelimiter,
1854           rightFarDelimiter - rightDelimiter);
1855       if (result != 0) {
1856         return result;
1857       }
1858       // Compare last part of row, the rowid.
1859       leftFarDelimiter++;
1860       rightFarDelimiter++;
1861       result = compareRowid(left, leftFarDelimiter,
1862           llength - (leftFarDelimiter - loffset),
1863           right, rightFarDelimiter, rlength - (rightFarDelimiter - roffset));
1864       return result;
1865     }
1866 
1867     protected int compareRowid(byte[] left, int loffset, int llength,
1868         byte[] right, int roffset, int rlength) {
1869       return Bytes.compareTo(left, loffset, llength, right, roffset, rlength);
1870     }
1871   }
1872 
1873   /**
1874    * Compare key portion of a {@link KeyValue}.
1875    */
1876   public static class KeyComparator implements RawComparator<byte []> {
1877     volatile boolean ignoreTimestamp = false;
1878     volatile boolean ignoreType = false;
1879 
1880     public int compare(byte[] left, int loffset, int llength, byte[] right,
1881         int roffset, int rlength) {
1882       // Compare row
1883       short lrowlength = Bytes.toShort(left, loffset);
1884       short rrowlength = Bytes.toShort(right, roffset);
1885       int compare = compareRows(left, loffset + Bytes.SIZEOF_SHORT,
1886           lrowlength,
1887           right, roffset + Bytes.SIZEOF_SHORT, rrowlength);
1888       if (compare != 0) {
1889         return compare;
1890       }
1891 
1892       // Compare column family.  Start compare past row and family length.
1893       int lcolumnoffset = Bytes.SIZEOF_SHORT + lrowlength + 1 + loffset;
1894       int rcolumnoffset = Bytes.SIZEOF_SHORT + rrowlength + 1 + roffset;
1895       int lcolumnlength = llength - TIMESTAMP_TYPE_SIZE -
1896         (lcolumnoffset - loffset);
1897       int rcolumnlength = rlength - TIMESTAMP_TYPE_SIZE -
1898         (rcolumnoffset - roffset);
1899 
1900       // if row matches, and no column in the 'left' AND put type is 'minimum',
1901       // then return that left is larger than right.
1902 
1903       // This supports 'last key on a row' - the magic is if there is no column in the
1904       // left operand, and the left operand has a type of '0' - magical value,
1905       // then we say the left is bigger.  This will let us seek to the last key in
1906       // a row.
1907 
1908       byte ltype = left[loffset + (llength - 1)];
1909       byte rtype = right[roffset + (rlength - 1)];
1910 
1911       if (lcolumnlength == 0 && ltype == Type.Minimum.getCode()) {
1912         return 1; // left is bigger.
1913       }
1914       if (rcolumnlength == 0 && rtype == Type.Minimum.getCode()) {
1915         return -1;
1916       }
1917 
1918       // TODO the family and qualifier should be compared separately
1919       compare = Bytes.compareTo(left, lcolumnoffset, lcolumnlength, right,
1920           rcolumnoffset, rcolumnlength);
1921       if (compare != 0) {
1922         return compare;
1923       }
1924 
1925       if (!this.ignoreTimestamp) {
1926         // Get timestamps.
1927         long ltimestamp = Bytes.toLong(left,
1928             loffset + (llength - TIMESTAMP_TYPE_SIZE));
1929         long rtimestamp = Bytes.toLong(right,
1930             roffset + (rlength - TIMESTAMP_TYPE_SIZE));
1931         compare = compareTimestamps(ltimestamp, rtimestamp);
1932         if (compare != 0) {
1933           return compare;
1934         }
1935       }
1936 
1937       if (!this.ignoreType) {
1938         // Compare types. Let the delete types sort ahead of puts; i.e. types
1939         // of higher numbers sort before those of lesser numbers
1940         return (0xff & rtype) - (0xff & ltype);
1941       }
1942       return 0;
1943     }
1944 
1945     public int compare(byte[] left, byte[] right) {
1946       return compare(left, 0, left.length, right, 0, right.length);
1947     }
1948 
1949     public int compareRows(byte [] left, int loffset, int llength,
1950         byte [] right, int roffset, int rlength) {
1951       return Bytes.compareTo(left, loffset, llength, right, roffset, rlength);
1952     }
1953 
1954     protected int compareColumns(
1955         byte [] left, int loffset, int llength, final int lfamilylength,
1956         byte [] right, int roffset, int rlength, final int rfamilylength) {
1957       return KeyValue.compareColumns(left, loffset, llength, lfamilylength,
1958         right, roffset, rlength, rfamilylength);
1959     }
1960 
1961     int compareTimestamps(final long ltimestamp, final long rtimestamp) {
1962       // The below older timestamps sorting ahead of newer timestamps looks
1963       // wrong but it is intentional. This way, newer timestamps are first
1964       // found when we iterate over a memstore and newer versions are the
1965       // first we trip over when reading from a store file.
1966       if (ltimestamp < rtimestamp) {
1967         return 1;
1968       } else if (ltimestamp > rtimestamp) {
1969         return -1;
1970       }
1971       return 0;
1972     }
1973   }
1974 
1975   // HeapSize
1976   public long heapSize() {
1977     return ClassSize.align(ClassSize.OBJECT + (2 * ClassSize.REFERENCE) +
1978         ClassSize.align(ClassSize.ARRAY) + ClassSize.align(length) +
1979         (3 * Bytes.SIZEOF_INT) +
1980         ClassSize.align(ClassSize.ARRAY) +
1981         (2 * Bytes.SIZEOF_LONG));
1982   }
1983 
1984   // this overload assumes that the length bytes have already been read,
1985   // and it expects the length of the KeyValue to be explicitly passed
1986   // to it.
1987   public void readFields(int length, final DataInput in) throws IOException {
1988     this.length = length;
1989     this.offset = 0;
1990     this.bytes = new byte[this.length];
1991     in.readFully(this.bytes, 0, this.length);
1992   }
1993 
1994   // Writable
1995   public void readFields(final DataInput in) throws IOException {
1996     int length = in.readInt();
1997     readFields(length, in);
1998   }
1999 
2000   public void write(final DataOutput out) throws IOException {
2001     out.writeInt(this.length);
2002     out.write(this.bytes, this.offset, this.length);
2003   }
2004 }