View Javadoc

1   /*
2    * Licensed to the Apache Software Foundation (ASF) under one
3    * or more contributor license agreements.  See the NOTICE file
4    * distributed with this work for additional information
5    * regarding copyright ownership.  The ASF licenses this file
6    * to you under the Apache License, Version 2.0 (the
7    * "License"); you may not use this file except in compliance
8    * with the License.  You may obtain a copy of the License at
9    *
10   *     http://www.apache.org/licenses/LICENSE-2.0
11   *
12   * Unless required by applicable law or agreed to in writing, software
13   * distributed under the License is distributed on an "AS IS" BASIS,
14   * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
15   * See the License for the specific language governing permissions and
16   * limitations under the License.
17   */
18  
19  package org.apache.hadoop.hbase;
20  
21  import java.io.Serializable;
22  import java.util.Comparator;
23  
24  import org.apache.commons.logging.Log;
25  import org.apache.commons.logging.LogFactory;
26  import org.apache.hadoop.hbase.KeyValue.Type;
27  import org.apache.hadoop.hbase.classification.InterfaceAudience;
28  import org.apache.hadoop.hbase.classification.InterfaceStability;
29  import org.apache.hadoop.hbase.filter.ByteArrayComparable;
30  import org.apache.hadoop.hbase.util.ByteBufferUtils;
31  import org.apache.hadoop.hbase.util.Bytes;
32  
33  import com.google.common.primitives.Longs;
34  
35  /**
36   * Compare two HBase cells.  Do not use this method comparing <code>-ROOT-</code> or
37   * <code>hbase:meta</code> cells.  Cells from these tables need a specialized comparator, one that
38   * takes account of the special formatting of the row where we have commas to delimit table from
39   * regionname, from row.  See KeyValue for how it has a special comparator to do hbase:meta cells
40   * and yet another for -ROOT-.
41   * While using this comparator for {{@link #compareRows(Cell, Cell)} et al, the hbase:meta cells
42   * format should be taken into consideration, for which the instance of this comparator
43   * should be used.  In all other cases the static APIs in this comparator would be enough
44   */
45  @edu.umd.cs.findbugs.annotations.SuppressWarnings(
46      value="UNKNOWN",
47      justification="Findbugs doesn't like the way we are negating the result of a compare in below")
48  @InterfaceAudience.Private
49  @InterfaceStability.Evolving
50  public class CellComparator implements Comparator<Cell>, Serializable {
51    static final Log LOG = LogFactory.getLog(CellComparator.class);
52    private static final long serialVersionUID = -8760041766259623329L;
53  
54    /**
55     * Comparator for plain key/values; i.e. non-catalog table key/values. Works on Key portion
56     * of KeyValue only.
57     */
58    public static final CellComparator COMPARATOR = new CellComparator();
59    /**
60     * A {@link CellComparator} for <code>hbase:meta</code> catalog table
61     * {@link KeyValue}s.
62     */
63    public static final CellComparator META_COMPARATOR = new MetaCellComparator();
64  
65    @Override
66    public int compare(Cell a, Cell b) {
67      return compare(a, b, false);
68    }
69  
70    /**
71     * Compares only the key portion of a cell. It does not include the sequence id/mvcc of the
72     * cell 
73     * @param left
74     * @param right
75     * @return an int greater than 0 if left &gt; than right
76     *                lesser than 0 if left &lt; than right
77     *                equal to 0 if left is equal to right
78     */
79    public final int compareKeyIgnoresMvcc(Cell left, Cell right) {
80      return compare(left, right, true);
81    }
82  
83    /**
84     * Used when a cell needs to be compared with a key byte[] such as cases of
85     * finding the index from the index block, bloom keys from the bloom blocks
86     * This byte[] is expected to be serialized in the KeyValue serialization format
87     * If the KeyValue (Cell's) serialization format changes this method cannot be used.
88     * @param left the cell to be compared
89     * @param key the serialized key part of a KeyValue
90     * @param offset the offset in the key byte[]
91     * @param length the length of the key byte[]
92     * @return an int greater than 0 if left is greater than right
93     *                lesser than 0 if left is lesser than right
94     *                equal to 0 if left is equal to right
95     */
96    public final int compare(Cell left, byte[] key, int offset, int length) {
97      // row
98      short rrowlength = Bytes.toShort(key, offset);
99      int c = compareRows(left, key, offset + Bytes.SIZEOF_SHORT, rrowlength);
100     if (c != 0) return c;
101 
102     // Compare the rest of the two KVs without making any assumptions about
103     // the common prefix. This function will not compare rows anyway, so we
104     // don't need to tell it that the common prefix includes the row.
105     return compareWithoutRow(left, key, offset, length, rrowlength);
106   }
107 
108   /**
109    * Compare cells.
110    * @param a
111    * @param b
112    * @param ignoreSequenceid True if we are to compare the key portion only and ignore
113    * the sequenceid. Set to false to compare key and consider sequenceid.
114    * @return 0 if equal, -1 if a &lt; b, and +1 if a &gt; b.
115    */
116   private final int compare(final Cell a, final Cell b, boolean ignoreSequenceid) {
117     // row
118     int c = compareRows(a, b);
119     if (c != 0) return c;
120 
121     c = compareWithoutRow(a, b);
122     if(c != 0) return c;
123 
124     if (!ignoreSequenceid) {
125       // Negate following comparisons so later edits show up first
126       // mvccVersion: later sorts first
127       return Longs.compare(b.getSequenceId(), a.getSequenceId());
128     } else {
129       return c;
130     }
131   }
132 
133   /**
134    * Compares the family and qualifier part of the cell
135    * @param left the left cell
136    * @param right the right cell
137    * @return 0 if both cells are equal, 1 if left cell is bigger than right, -1 otherwise
138    */
139   public final static int compareColumns(final Cell left, final Cell right) {
140     int diff = compareFamilies(left, right);
141     if (diff != 0) {
142       return diff;
143     }
144     return compareQualifiers(left, right);
145   }
146 
147   private final static int compareColumns(Cell left, byte[] right, int rfoffset, int rflength,
148       int rqoffset, int rqlength) {
149     int diff = compareFamilies(left, right, rfoffset, rflength);
150     if (diff != 0)
151       return diff;
152     return compareQualifiers(left, right, rqoffset, rqlength);
153   }
154 
155   /**
156    * Compare the families of left and right cell
157    * @param left
158    * @param right
159    * @return 0 if both cells are equal, 1 if left cell is bigger than right, -1 otherwise
160    */
161   public final static int compareFamilies(Cell left, Cell right) {
162     if (left instanceof ByteBufferedCell && right instanceof ByteBufferedCell) {
163       return ByteBufferUtils.compareTo(((ByteBufferedCell) left).getFamilyByteBuffer(),
164           ((ByteBufferedCell) left).getFamilyPosition(), left.getFamilyLength(),
165           ((ByteBufferedCell) right).getFamilyByteBuffer(),
166           ((ByteBufferedCell) right).getFamilyPosition(), right.getFamilyLength());
167     }
168     if (left instanceof ByteBufferedCell) {
169       return ByteBufferUtils.compareTo(((ByteBufferedCell) left).getFamilyByteBuffer(),
170           ((ByteBufferedCell) left).getFamilyPosition(), left.getFamilyLength(),
171           right.getFamilyArray(), right.getFamilyOffset(), right.getFamilyLength());
172     }
173     if (right instanceof ByteBufferedCell) {
174       // Notice how we flip the order of the compare here. We used to negate the return value but
175       // see what FindBugs says
176       // http://findbugs.sourceforge.net/bugDescriptions.html#RV_NEGATING_RESULT_OF_COMPARETO
177       // It suggest flipping the order to get same effect and 'safer'.
178       return ByteBufferUtils.compareTo(
179           left.getFamilyArray(), left.getFamilyOffset(), left.getFamilyLength(),
180           ((ByteBufferedCell)right).getFamilyByteBuffer(),
181           ((ByteBufferedCell)right).getFamilyPosition(), right.getFamilyLength());
182     }
183     return Bytes.compareTo(left.getFamilyArray(), left.getFamilyOffset(), left.getFamilyLength(),
184         right.getFamilyArray(), right.getFamilyOffset(), right.getFamilyLength());
185   }
186 
187   private final static int compareFamilies(Cell left, byte[] right, int roffset, int rlength) {
188     if (left instanceof ByteBufferedCell) {
189       return ByteBufferUtils.compareTo(((ByteBufferedCell) left).getFamilyByteBuffer(),
190           ((ByteBufferedCell) left).getFamilyPosition(), left.getFamilyLength(), right,
191           roffset, rlength);
192     }
193     return Bytes.compareTo(left.getFamilyArray(), left.getFamilyOffset(), left.getFamilyLength(),
194         right, roffset, rlength);
195   }
196 
197   /**
198    * Compare the qualifiers part of the left and right cells.
199    * @param left
200    * @param right
201    * @return 0 if both cells are equal, 1 if left cell is bigger than right, -1 otherwise
202    */
203   public final static int compareQualifiers(Cell left, Cell right) {
204     if (left instanceof ByteBufferedCell && right instanceof ByteBufferedCell) {
205       return ByteBufferUtils
206           .compareTo(((ByteBufferedCell) left).getQualifierByteBuffer(),
207               ((ByteBufferedCell) left).getQualifierPosition(),
208               left.getQualifierLength(), ((ByteBufferedCell) right).getQualifierByteBuffer(),
209               ((ByteBufferedCell) right).getQualifierPosition(),
210               right.getQualifierLength());
211     }
212     if (left instanceof ByteBufferedCell) {
213       return ByteBufferUtils.compareTo(((ByteBufferedCell) left).getQualifierByteBuffer(),
214           ((ByteBufferedCell) left).getQualifierPosition(), left.getQualifierLength(),
215           right.getQualifierArray(), right.getQualifierOffset(), right.getQualifierLength());
216     }
217     if (right instanceof ByteBufferedCell) {
218       // Notice how we flip the order of the compare here. We used to negate the return value but
219       // see what FindBugs says
220       // http://findbugs.sourceforge.net/bugDescriptions.html#RV_NEGATING_RESULT_OF_COMPARETO
221       // It suggest flipping the order to get same effect and 'safer'.
222       return ByteBufferUtils.compareTo(left.getQualifierArray(),
223           left.getQualifierOffset(), left.getQualifierLength(),
224           ((ByteBufferedCell)right).getQualifierByteBuffer(),
225           ((ByteBufferedCell)right).getQualifierPosition(), right.getQualifierLength());
226     }
227     return Bytes.compareTo(left.getQualifierArray(), left.getQualifierOffset(),
228         left.getQualifierLength(), right.getQualifierArray(), right.getQualifierOffset(),
229         right.getQualifierLength());
230   }
231 
232   public final static int compareQualifiers(Cell left, byte[] right, int rOffset, int rLength) {
233     if (left instanceof ByteBufferedCell) {
234       return ByteBufferUtils.compareTo(((ByteBufferedCell) left).getQualifierByteBuffer(),
235           ((ByteBufferedCell) left).getQualifierPosition(), left.getQualifierLength(),
236           right, rOffset, rLength);
237     }
238     return Bytes.compareTo(left.getQualifierArray(), left.getQualifierOffset(),
239         left.getQualifierLength(), right, rOffset, rLength);
240   }
241 
242   /**
243    * Compare columnFamily, qualifier, timestamp, and key type (everything
244    * except the row). This method is used both in the normal comparator and
245    * the "same-prefix" comparator. Note that we are assuming that row portions
246    * of both KVs have already been parsed and found identical, and we don't
247    * validate that assumption here.
248    * @param commonPrefix
249    *          the length of the common prefix of the two key-values being
250    *          compared, including row length and row
251    */
252   private final int compareWithoutRow(Cell left,
253       byte[] right, int roffset, int rlength, short rowlength) {
254     /***
255      * KeyValue Format and commonLength:
256      * |_keyLen_|_valLen_|_rowLen_|_rowKey_|_famiLen_|_fami_|_Quali_|....
257      * ------------------|-------commonLength--------|--------------
258      */
259     int commonLength = KeyValue.ROW_LENGTH_SIZE + KeyValue.FAMILY_LENGTH_SIZE + rowlength;
260 
261     // commonLength + TIMESTAMP_TYPE_SIZE
262     int commonLengthWithTSAndType = KeyValue.TIMESTAMP_TYPE_SIZE + commonLength;
263     // ColumnFamily + Qualifier length.
264     int lcolumnlength = left.getFamilyLength() + left.getQualifierLength();
265     int rcolumnlength = rlength - commonLengthWithTSAndType;
266 
267     byte ltype = left.getTypeByte();
268     byte rtype = right[roffset + (rlength - 1)];
269 
270     // If the column is not specified, the "minimum" key type appears the
271     // latest in the sorted order, regardless of the timestamp. This is used
272     // for specifying the last key/value in a given row, because there is no
273     // "lexicographically last column" (it would be infinitely long). The
274     // "maximum" key type does not need this behavior.
275     if (lcolumnlength == 0 && ltype == Type.Minimum.getCode()) {
276       // left is "bigger", i.e. it appears later in the sorted order
277       return 1;
278     }
279     if (rcolumnlength == 0 && rtype == Type.Minimum.getCode()) {
280       return -1;
281     }
282 
283     int rfamilyoffset = commonLength + roffset;
284 
285     // Column family length.
286     int lfamilylength = left.getFamilyLength();
287     int rfamilylength = right[rfamilyoffset - 1];
288     // If left family size is not equal to right family size, we need not
289     // compare the qualifiers.
290     boolean sameFamilySize = (lfamilylength == rfamilylength);
291     if (!sameFamilySize) {
292       // comparing column family is enough.
293       return compareFamilies(left, right, rfamilyoffset, rfamilylength);
294     }
295     // Compare family & qualifier together.
296     // Families are same. Compare on qualifiers.
297     int comparison = compareColumns(left, right, rfamilyoffset, rfamilylength, rfamilyoffset
298         + rfamilylength, (rcolumnlength - rfamilylength));
299     if (comparison != 0) {
300       return comparison;
301     }
302 
303     // //
304     // Next compare timestamps.
305     long rtimestamp = Bytes.toLong(right, roffset + (rlength - KeyValue.TIMESTAMP_TYPE_SIZE));
306     int compare = compareTimestamps(left.getTimestamp(), rtimestamp);
307     if (compare != 0) {
308       return compare;
309     }
310 
311     // Compare types. Let the delete types sort ahead of puts; i.e. types
312     // of higher numbers sort before those of lesser numbers. Maximum (255)
313     // appears ahead of everything, and minimum (0) appears after
314     // everything.
315     return (0xff & rtype) - (0xff & ltype);
316   }
317 
318   /**
319    * Compares the rows of the left and right cell.
320    * For the hbase:meta case this method is overridden such that it can handle hbase:meta cells.
321    * The caller should ensure using the appropriate comparator for hbase:meta.
322    * @param left
323    * @param right
324    * @return 0 if both cells are equal, 1 if left cell is bigger than right, -1 otherwise
325    */
326   public int compareRows(final Cell left, final Cell right) {
327     // left and right can be exactly the same at the beginning of a row
328     if (left == right) {
329       return 0;
330     }
331     if (left instanceof ByteBufferedCell && right instanceof ByteBufferedCell) {
332       return ByteBufferUtils.compareTo(((ByteBufferedCell) left).getRowByteBuffer(),
333           ((ByteBufferedCell) left).getRowPosition(), left.getRowLength(),
334           ((ByteBufferedCell) right).getRowByteBuffer(),
335           ((ByteBufferedCell) right).getRowPosition(), right.getRowLength());
336     }
337     if (left instanceof ByteBufferedCell) {
338       return ByteBufferUtils.compareTo(((ByteBufferedCell) left).getRowByteBuffer(),
339           ((ByteBufferedCell) left).getRowPosition(), left.getRowLength(),
340           right.getRowArray(), right.getRowOffset(), right.getRowLength());
341     }
342     if (right instanceof ByteBufferedCell) {
343       // Notice how we flip the order of the compare here. We used to negate the return value but
344       // see what FindBugs says
345       // http://findbugs.sourceforge.net/bugDescriptions.html#RV_NEGATING_RESULT_OF_COMPARETO
346       // It suggest flipping the order to get same effect and 'safer'.
347       return ByteBufferUtils.compareTo(left.getRowArray(), left.getRowOffset(), left.getRowLength(),
348           ((ByteBufferedCell)right).getRowByteBuffer(),
349           ((ByteBufferedCell)right).getRowPosition(), right.getRowLength());
350     }
351     return Bytes.compareTo(left.getRowArray(), left.getRowOffset(), left.getRowLength(),
352         right.getRowArray(), right.getRowOffset(), right.getRowLength());
353   }
354 
355   /**
356    * Compares the row part of the cell with a simple plain byte[] like the
357    * stopRow in Scan. This should be used with context where for hbase:meta
358    * cells the {{@link #META_COMPARATOR} should be used
359    *
360    * @param left
361    *          the cell to be compared
362    * @param right
363    *          the kv serialized byte[] to be compared with
364    * @param roffset
365    *          the offset in the byte[]
366    * @param rlength
367    *          the length in the byte[]
368    * @return 0 if both cell and the byte[] are equal, 1 if the cell is bigger
369    *         than byte[], -1 otherwise
370    */
371   public int compareRows(Cell left, byte[] right, int roffset, int rlength) {
372     if (left instanceof ByteBufferedCell) {
373       return ByteBufferUtils.compareTo(((ByteBufferedCell) left).getRowByteBuffer(),
374           ((ByteBufferedCell) left).getRowPosition(), left.getRowLength(), right,
375           roffset, rlength);
376     }
377     return Bytes.compareTo(left.getRowArray(), left.getRowOffset(), left.getRowLength(), right,
378         roffset, rlength);
379   }
380 
381   public static int compareWithoutRow(final Cell left, final Cell right) {
382     // If the column is not specified, the "minimum" key type appears the
383     // latest in the sorted order, regardless of the timestamp. This is used
384     // for specifying the last key/value in a given row, because there is no
385     // "lexicographically last column" (it would be infinitely long). The
386     // "maximum" key type does not need this behavior.
387     // Copied from KeyValue. This is bad in that we can't do memcmp w/ special rules like this.
388     int lFamLength = left.getFamilyLength();
389     int rFamLength = right.getFamilyLength();
390     int lQualLength = left.getQualifierLength();
391     int rQualLength = right.getQualifierLength();
392     if (lFamLength + lQualLength == 0
393           && left.getTypeByte() == Type.Minimum.getCode()) {
394       // left is "bigger", i.e. it appears later in the sorted order
395       return 1;
396     }
397     if (rFamLength + rQualLength == 0
398         && right.getTypeByte() == Type.Minimum.getCode()) {
399       return -1;
400     }
401     if (lFamLength != rFamLength) {
402       // comparing column family is enough.
403       return compareFamilies(left, right);
404     }
405     // Compare cf:qualifier
406     int diff = compareColumns(left, right);
407     if (diff != 0) return diff;
408 
409     diff = compareTimestamps(left, right);
410     if (diff != 0) return diff;
411 
412     // Compare types. Let the delete types sort ahead of puts; i.e. types
413     // of higher numbers sort before those of lesser numbers. Maximum (255)
414     // appears ahead of everything, and minimum (0) appears after
415     // everything.
416     return (0xff & right.getTypeByte()) - (0xff & left.getTypeByte());
417   }
418 
419   /**
420    * Compares cell's timestamps in DESCENDING order.
421    * The below older timestamps sorting ahead of newer timestamps looks
422    * wrong but it is intentional. This way, newer timestamps are first
423    * found when we iterate over a memstore and newer versions are the
424    * first we trip over when reading from a store file.
425    * @return 1 if left's timestamp &lt; right's timestamp
426    *         -1 if left's timestamp &gt; right's timestamp
427    *         0 if both timestamps are equal
428    */
429   public static int compareTimestamps(final Cell left, final Cell right) {
430     return compareTimestamps(left.getTimestamp(), right.getTimestamp());
431   }
432 
433   /**
434    * Used to compare two cells based on the column hint provided. This is specifically
435    * used when we need to optimize the seeks based on the next indexed key. This is an
436    * advanced usage API specifically needed for some optimizations.
437    * @param nextIndexedCell the next indexed cell 
438    * @param currentCell the cell to be compared
439    * @param foff the family offset of the currentCell
440    * @param flen the family length of the currentCell
441    * @param colHint the column hint provided - could be null
442    * @param coff the offset of the column hint if provided, if not offset of the currentCell's
443    * qualifier
444    * @param clen the length of the column hint if provided, if not length of the currentCell's
445    * qualifier
446    * @param ts the timestamp to be seeked
447    * @param type the type to be seeked
448    * @return an int based on the given column hint
449    * TODO : To be moved out of here because this is a special API used in scan
450    * optimization.
451    */
452   // compare a key against row/fam/qual/ts/type
453   public final int compareKeyBasedOnColHint(Cell nextIndexedCell, Cell currentCell, int foff,
454       int flen, byte[] colHint, int coff, int clen, long ts, byte type) {
455     int compare = compareRows(nextIndexedCell, currentCell);
456     if (compare != 0) {
457       return compare;
458     }
459     // If the column is not specified, the "minimum" key type appears the
460     // latest in the sorted order, regardless of the timestamp. This is used
461     // for specifying the last key/value in a given row, because there is no
462     // "lexicographically last column" (it would be infinitely long). The
463     // "maximum" key type does not need this behavior.
464     if (nextIndexedCell.getFamilyLength() + nextIndexedCell.getQualifierLength() == 0
465         && nextIndexedCell.getTypeByte() == Type.Minimum.getCode()) {
466       // left is "bigger", i.e. it appears later in the sorted order
467       return 1;
468     }
469     if (flen + clen == 0 && type == Type.Minimum.getCode()) {
470       return -1;
471     }
472 
473     compare = compareFamilies(nextIndexedCell, currentCell);
474     if (compare != 0) {
475       return compare;
476     }
477     if (colHint == null) {
478       compare = compareQualifiers(nextIndexedCell, currentCell);
479     } else {
480       compare = compareQualifiers(nextIndexedCell, colHint, coff, clen);
481     }
482     if (compare != 0) {
483       return compare;
484     }
485     // Next compare timestamps.
486     compare = compareTimestamps(nextIndexedCell.getTimestamp(), ts);
487     if (compare != 0) {
488       return compare;
489     }
490 
491     // Compare types. Let the delete types sort ahead of puts; i.e. types
492     // of higher numbers sort before those of lesser numbers. Maximum (255)
493     // appears ahead of everything, and minimum (0) appears after
494     // everything.
495     return (0xff & type) - (0xff & nextIndexedCell.getTypeByte());
496   }
497 
498   /**
499    * Compares timestamps in DESCENDING order.
500    * The below older timestamps sorting ahead of newer timestamps looks
501    * wrong but it is intentional. This way, newer timestamps are first
502    * found when we iterate over a memstore and newer versions are the
503    * first we trip over when reading from a store file.
504    * @return 1 if left timestamp &lt; right timestamp
505    *         -1 if left timestamp &gt; right timestamp
506    *         0 if both timestamps are equal
507    */
508   public static int compareTimestamps(final long ltimestamp, final long rtimestamp) {
509     if (ltimestamp < rtimestamp) {
510       return 1;
511     } else if (ltimestamp > rtimestamp) {
512       return -1;
513     }
514     return 0;
515   }
516 
517   /**
518    * Compare cell's row against given comparator
519    * @param cell
520    * @param comparator
521    * @return result comparing cell's row
522    */
523   public static int compareRow(Cell cell, ByteArrayComparable comparator) {
524     if (cell instanceof ByteBufferedCell) {
525       return comparator.compareTo(((ByteBufferedCell) cell).getRowByteBuffer(),
526           ((ByteBufferedCell) cell).getRowPosition(), cell.getRowLength());
527     }
528     return comparator.compareTo(cell.getRowArray(), cell.getRowOffset(), cell.getRowLength());
529   }
530 
531   /**
532    * Compare cell's column family against given comparator
533    * @param cell
534    * @param comparator
535    * @return result comparing cell's column family
536    */
537   public static int compareFamily(Cell cell, ByteArrayComparable comparator) {
538     if (cell instanceof ByteBufferedCell) {
539       return comparator.compareTo(((ByteBufferedCell) cell).getFamilyByteBuffer(),
540           ((ByteBufferedCell) cell).getFamilyPosition(), cell.getFamilyLength());
541     }
542     return comparator.compareTo(cell.getFamilyArray(), cell.getFamilyOffset(),
543         cell.getFamilyLength());
544   }
545 
546   /**
547    * Compare cell's qualifier against given comparator
548    * @param cell
549    * @param comparator
550    * @return result comparing cell's qualifier
551    */
552   public static int compareQualifier(Cell cell, ByteArrayComparable comparator) {
553     if (cell instanceof ByteBufferedCell) {
554       return comparator.compareTo(((ByteBufferedCell) cell).getQualifierByteBuffer(),
555           ((ByteBufferedCell) cell).getQualifierPosition(), cell.getQualifierLength());
556     }
557     return comparator.compareTo(cell.getQualifierArray(), cell.getQualifierOffset(),
558         cell.getQualifierLength());
559   }
560 
561   /**
562    * Compare cell's value against given comparator
563    * @param cell
564    * @param comparator
565    * @return result comparing cell's value
566    */
567   public static int compareValue(Cell cell, ByteArrayComparable comparator) {
568     if (cell instanceof ByteBufferedCell) {
569       return comparator.compareTo(((ByteBufferedCell) cell).getValueByteBuffer(),
570           ((ByteBufferedCell) cell).getValuePosition(), cell.getValueLength());
571     }
572     return comparator.compareTo(cell.getValueArray(), cell.getValueOffset(), cell.getValueLength());
573   }
574 
575   /**
576    * Comparator that compares row component only of a Cell
577    */
578   public static class RowComparator extends CellComparator {
579     @Override
580     public int compare(Cell a, Cell b) {
581       return compareRows(a, b);
582     }
583   }
584 
585   /**
586    * A {@link CellComparator} for <code>hbase:meta</code> catalog table
587    * {@link KeyValue}s.
588    */
589   public static class MetaCellComparator extends CellComparator {
590 
591     @Override
592     public int compareRows(final Cell left, final Cell right) {
593       return compareRows(left.getRowArray(), left.getRowOffset(), left.getRowLength(),
594           right.getRowArray(), right.getRowOffset(), right.getRowLength());
595     }
596 
597     @Override
598     public int compareRows(Cell left, byte[] right, int roffset, int rlength) {
599       return compareRows(left.getRowArray(), left.getRowOffset(), left.getRowLength(), right,
600           roffset, rlength);
601     }
602 
603     private int compareRows(byte[] left, int loffset, int llength, byte[] right, int roffset,
604         int rlength) {
605       int leftDelimiter = Bytes.searchDelimiterIndex(left, loffset, llength, HConstants.DELIMITER);
606       int rightDelimiter = Bytes
607           .searchDelimiterIndex(right, roffset, rlength, HConstants.DELIMITER);
608       // Compare up to the delimiter
609       int lpart = (leftDelimiter < 0 ? llength : leftDelimiter - loffset);
610       int rpart = (rightDelimiter < 0 ? rlength : rightDelimiter - roffset);
611       int result = Bytes.compareTo(left, loffset, lpart, right, roffset, rpart);
612       if (result != 0) {
613         return result;
614       } else {
615         if (leftDelimiter < 0 && rightDelimiter >= 0) {
616           return -1;
617         } else if (rightDelimiter < 0 && leftDelimiter >= 0) {
618           return 1;
619         } else if (leftDelimiter < 0 && rightDelimiter < 0) {
620           return 0;
621         }
622       }
623       // Compare middle bit of the row.
624       // Move past delimiter
625       leftDelimiter++;
626       rightDelimiter++;
627       int leftFarDelimiter = Bytes.searchDelimiterIndexInReverse(left, leftDelimiter, llength
628           - (leftDelimiter - loffset), HConstants.DELIMITER);
629       int rightFarDelimiter = Bytes.searchDelimiterIndexInReverse(right, rightDelimiter, rlength
630           - (rightDelimiter - roffset), HConstants.DELIMITER);
631       // Now compare middlesection of row.
632       lpart = (leftFarDelimiter < 0 ? llength + loffset : leftFarDelimiter) - leftDelimiter;
633       rpart = (rightFarDelimiter < 0 ? rlength + roffset : rightFarDelimiter) - rightDelimiter;
634       result = Bytes.compareTo(left, leftDelimiter, lpart, right, rightDelimiter, rpart);
635       if (result != 0) {
636         return result;
637       } else {
638         if (leftDelimiter < 0 && rightDelimiter >= 0) {
639           return -1;
640         } else if (rightDelimiter < 0 && leftDelimiter >= 0) {
641           return 1;
642         } else if (leftDelimiter < 0 && rightDelimiter < 0) {
643           return 0;
644         }
645       }
646       // Compare last part of row, the rowid.
647       leftFarDelimiter++;
648       rightFarDelimiter++;
649       result = Bytes.compareTo(left, leftFarDelimiter, llength - (leftFarDelimiter - loffset),
650           right, rightFarDelimiter, rlength - (rightFarDelimiter - roffset));
651       return result;
652     }
653   }
654 }