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.util.Bytes;
30  
31  import com.google.common.primitives.Longs;
32  
33  /**
34   * Compare two HBase cells.  Do not use this method comparing <code>-ROOT-</code> or
35   * <code>hbase:meta</code> cells.  Cells from these tables need a specialized comparator, one that
36   * takes account of the special formatting of the row where we have commas to delimit table from
37   * regionname, from row.  See KeyValue for how it has a special comparator to do hbase:meta cells
38   * and yet another for -ROOT-.
39   * While using this comparator for {{@link #compareRows(Cell, Cell)} et al, the hbase:meta cells format
40   * should be taken into consideration, for which the instance of this comparator 
41   * should be used.  In all other cases the static APIs in this comparator would be enough
42   */
43  @edu.umd.cs.findbugs.annotations.SuppressWarnings(
44      value="UNKNOWN",
45      justification="Findbugs doesn't like the way we are negating the result of a compare in below")
46  @InterfaceAudience.Private
47  @InterfaceStability.Evolving
48  public class CellComparator implements Comparator<Cell>, Serializable {
49    static final Log LOG = LogFactory.getLog(CellComparator.class);
50    private static final long serialVersionUID = -8760041766259623329L;
51  
52    /**
53     * Comparator for plain key/values; i.e. non-catalog table key/values. Works on Key portion
54     * of KeyValue only.
55     */
56    public static final CellComparator COMPARATOR = new CellComparator();
57    /**
58     * A {@link CellComparator} for <code>hbase:meta</code> catalog table
59     * {@link KeyValue}s.
60     */
61    public static final CellComparator META_COMPARATOR = new MetaCellComparator();
62  
63    @Override
64    public int compare(Cell a, Cell b) {
65      return compare(a, b, false);
66    }
67  
68    /**
69     * Compares only the key portion of a cell. It does not include the sequence id/mvcc of the
70     * cell 
71     * @param left
72     * @param right
73     * @return an int greater than 0 if left &gt; than right
74     *                lesser than 0 if left &lt; than right
75     *                equal to 0 if left is equal to right
76     */
77    public final int compareKeyIgnoresMvcc(Cell left, Cell right) {
78      return compare(left, right, true);
79    }
80  
81    /**
82     * Used when a cell needs to be compared with a key byte[] such as cases of
83     * finding the index from the index block, bloom keys from the bloom blocks
84     * This byte[] is expected to be serialized in the KeyValue serialization format
85     * If the KeyValue (Cell's) serialization format changes this method cannot be used.
86     * @param left the cell to be compared
87     * @param key the serialized key part of a KeyValue
88     * @param offset the offset in the key byte[]
89     * @param length the length of the key byte[]
90     * @return an int greater than 0 if left is greater than right
91     *                lesser than 0 if left is lesser than right
92     *                equal to 0 if left is equal to right
93     * TODO : We will be moving over to 
94     * compare(Cell, Cell) so that the key is also converted to a cell
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    * TODO : Handle BB cases here
136    * @param left the left cell
137    * @param right the right cell
138    * @return 0 if both cells are equal, 1 if left cell is bigger than right, -1 otherwise
139    */
140   public final static int compareColumns(final Cell left, final Cell right) {
141     int lfoffset = left.getFamilyOffset();
142     int rfoffset = right.getFamilyOffset();
143     int lclength = left.getQualifierLength();
144     int rclength = right.getQualifierLength();
145     int lfamilylength = left.getFamilyLength();
146     int rfamilylength = right.getFamilyLength();
147     int diff = compareFamilies(left.getFamilyArray(), lfoffset, lfamilylength,
148         right.getFamilyArray(), rfoffset, rfamilylength);
149     if (diff != 0) {
150       return diff;
151     } else {
152       return compareQualifiers(left.getQualifierArray(), left.getQualifierOffset(), lclength,
153           right.getQualifierArray(), right.getQualifierOffset(), rclength);
154     }
155   }
156 
157   /**
158    * Compares the family and qualifier part of the cell
159    * We explicitly pass the offset and length details of the cells to avoid
160    * re-parsing of the offset and length from the cell. Used only internally.
161    * @param left
162    * @param lfamilyOffset
163    * @param lfamilylength
164    * @param lqualOffset
165    * @param lQualLength
166    * @param right
167    * @param rfamilyOffset
168    * @param rfamilylength
169    * @param rqualOffset
170    * @param rqualLength
171    * @return 0 if both cells are equal, 1 if left cell is bigger than right, -1 otherwise
172    */
173   private final static int compareColumns(final Cell left, int lfamilyOffset, int lfamilylength,
174       int lqualOffset, int lQualLength, final Cell right, final int rfamilyOffset,
175       final int rfamilylength, final int rqualOffset, int rqualLength) {
176     int diff = compareFamilies(left.getFamilyArray(), lfamilyOffset, lfamilylength,
177         right.getFamilyArray(), rfamilyOffset, rfamilylength);
178     if (diff != 0) {
179       return diff;
180     } else {
181       return compareQualifiers(left.getQualifierArray(), lqualOffset, lQualLength,
182           right.getQualifierArray(), rqualOffset, rqualLength);
183     }
184   }
185   
186   /**
187    * Compares the family and qualifier part of a cell with a serialized Key value byte[]
188    * We explicitly pass the offset and length details of the cells to avoid
189    * re-parsing of the offset and length from the cell. Used only internally.
190    * @param left the cell to be compared
191    * @param lfamilyOffset
192    * @param lfamilylength
193    * @param lqualOffset
194    * @param lQualLength
195    * @param right the serialized key value byte array to be compared
196    * @param rfamilyOffset
197    * @param rfamilylength
198    * @param rqualOffset
199    * @param rqualLength
200    * @return 0 if both cells are equal, 1 if left cell is bigger than right, -1 otherwise
201    */
202   private final static int compareColumns(final Cell left, final int lfamilyOffset,
203       final int lfamilylength, final int lqualOffset, final int lQualLength, final byte[] right,
204       final int rfamilyOffset, final int rfamilylength, final int rqualOffset,
205       final int rqualLength) {
206     int diff = compareFamilies(left.getFamilyArray(), lfamilyOffset, lfamilylength, right,
207         rfamilyOffset, rfamilylength);
208     if (diff != 0) {
209       return diff;
210     } else {
211       return compareQualifiers(left.getQualifierArray(), lqualOffset, lQualLength, right,
212           rqualOffset, rqualLength);
213     }
214   }
215 
216   /**
217    * Compare the families of left and right cell
218    * TODO : Handle BB cases here
219    * @param left
220    * @param right
221    * @return 0 if both cells are equal, 1 if left cell is bigger than right, -1 otherwise
222    */
223   public final static int compareFamilies(Cell left, Cell right) {
224     return compareFamilies(left.getFamilyArray(), left.getFamilyOffset(), left.getFamilyLength(),
225         right.getFamilyArray(), right.getFamilyOffset(), right.getFamilyLength());
226   }
227 
228   /**
229    * We explicitly pass the offset and length details of the cells to avoid
230    * re-parsing of the offset and length from the cell. Used only internally.
231    * @param left
232    * @param lOffset
233    * @param lLength
234    * @param right
235    * @param rOffset
236    * @param rLength
237    * @return 0 if both cells are equal, 1 if left cell is bigger than right, -1 otherwise
238    */
239   private final static int compareFamilies(Cell left, int lOffset, int lLength, Cell right,
240       int rOffset, int rLength) {
241     return compareFamilies(left.getFamilyArray(), lOffset, lLength, right.getFamilyArray(),
242         rOffset, rLength);
243   }
244 
245   private final static int compareFamilies(Cell left, int lOffset, int lLength, byte[] right,
246       int rOffset, int rLength) {
247     return compareFamilies(left.getFamilyArray(), lOffset, lLength, right, rOffset, rLength);
248   }
249 
250   private final static int compareFamilies(byte[] leftFamily, int lFamOffset, int lFamLength,
251       byte[] rightFamily, int rFamOffset, int rFamLen) {
252     return Bytes.compareTo(leftFamily, lFamOffset, lFamLength, rightFamily, rFamOffset, rFamLen);
253   }
254 
255   /**
256    * Compare the qualifiers part of the left and right cells.
257    * TODO : Handle BB cases here
258    * @param left
259    * @param right
260    * @return 0 if both cells are equal, 1 if left cell is bigger than right, -1 otherwise
261    */
262   public final static int compareQualifiers(Cell left, Cell right) {
263     return compareQualifiers(left.getQualifierArray(), left.getQualifierOffset(),
264         left.getQualifierLength(), right.getQualifierArray(), right.getQualifierOffset(),
265         right.getQualifierLength());
266   }
267 
268  /**
269   * We explicitly pass the offset and length details of the cells to avoid
270   * re-parsing of the offset and length from the cell. Used only internally.
271   * @param left
272   * @param lOffset
273   * @param lLength
274   * @param right
275   * @param rOffset
276   * @param rLength
277   * @return 0 if both cells are equal, 1 if left cell is bigger than right, -1 otherwise
278   */
279   private final static int compareQualifiers(Cell left, int lOffset, int lLength, Cell right,
280       int rOffset, int rLength) {
281     return compareQualifiers(left.getQualifierArray(), lOffset,
282         lLength, right.getQualifierArray(), rOffset,
283         rLength);
284   }
285 
286   /**
287    * We explicitly pass the offset and length details of the cells to avoid
288    * re-parsing of the offset and length from the cell. Used only internally.
289    * @param left
290    * @param lOffset
291    * @param lLength
292    * @param right
293    * @param rOffset
294    * @param rLength
295    * @return 0 if both cells are equal, 1 if left cell is bigger than right, -1 otherwise
296    */
297   private final static int compareQualifiers(Cell left, int lOffset, int lLength, byte[] right,
298       int rOffset, int rLength) {
299     return compareQualifiers(left.getQualifierArray(), lOffset,
300         lLength, right, rOffset,
301         rLength);
302   }
303 
304   private static int compareQualifiers(byte[] leftCol, int lColOffset, int lColLength,
305       byte[] rightCol, int rColOffset, int rColLength) {
306     return Bytes.compareTo(leftCol, lColOffset, lColLength, rightCol, rColOffset, rColLength);
307   }
308 
309   /**
310    * Compare columnFamily, qualifier, timestamp, and key type (everything
311    * except the row). This method is used both in the normal comparator and
312    * the "same-prefix" comparator. Note that we are assuming that row portions
313    * of both KVs have already been parsed and found identical, and we don't
314    * validate that assumption here.
315    * TODO :  we will have to handle BB cases here
316    * @param commonPrefix
317    *          the length of the common prefix of the two key-values being
318    *          compared, including row length and row
319    */
320   private final int compareWithoutRow(Cell left,
321       byte[] right, int roffset, int rlength, short rowlength) {
322     /***
323      * KeyValue Format and commonLength:
324      * |_keyLen_|_valLen_|_rowLen_|_rowKey_|_famiLen_|_fami_|_Quali_|....
325      * ------------------|-------commonLength--------|--------------
326      */
327     int commonLength = KeyValue.ROW_LENGTH_SIZE + KeyValue.FAMILY_LENGTH_SIZE + rowlength;
328 
329     // commonLength + TIMESTAMP_TYPE_SIZE
330     int commonLengthWithTSAndType = KeyValue.TIMESTAMP_TYPE_SIZE + commonLength;
331     // ColumnFamily + Qualifier length.
332     int lcolumnlength = left.getFamilyLength() + left.getQualifierLength();
333     int rcolumnlength = rlength - commonLengthWithTSAndType;
334 
335     byte ltype = left.getTypeByte();
336     byte rtype = right[roffset + (rlength - 1)];
337 
338     // If the column is not specified, the "minimum" key type appears the
339     // latest in the sorted order, regardless of the timestamp. This is used
340     // for specifying the last key/value in a given row, because there is no
341     // "lexicographically last column" (it would be infinitely long). The
342     // "maximum" key type does not need this behavior.
343     if (lcolumnlength == 0 && ltype == Type.Minimum.getCode()) {
344       // left is "bigger", i.e. it appears later in the sorted order
345       return 1;
346     }
347     if (rcolumnlength == 0 && rtype == Type.Minimum.getCode()) {
348       return -1;
349     }
350 
351     int lfamilyoffset = left.getFamilyOffset();
352     int rfamilyoffset = commonLength + roffset;
353 
354     // Column family length.
355     int lfamilylength = left.getFamilyLength();
356     int rfamilylength = right[rfamilyoffset - 1];
357     // If left family size is not equal to right family size, we need not
358     // compare the qualifiers.
359     boolean sameFamilySize = (lfamilylength == rfamilylength);
360     if (!sameFamilySize) {
361       // comparing column family is enough.
362       return compareFamilies(left, lfamilyoffset, lfamilylength, right,
363           rfamilyoffset, rfamilylength);
364     }
365     // Compare family & qualifier together.
366     // Families are same. Compare on qualifiers.
367     int lQualOffset = left.getQualifierOffset();
368     int lQualLength = left.getQualifierLength();
369     int comparison = compareColumns(left, lfamilyoffset, lfamilylength, lQualOffset, lQualLength,
370         right, rfamilyoffset, rfamilylength, rfamilyoffset + rfamilylength,
371         (rcolumnlength - rfamilylength));
372     if (comparison != 0) {
373       return comparison;
374     }
375 
376     // //
377     // Next compare timestamps.
378     long rtimestamp = Bytes.toLong(right, roffset + (rlength - KeyValue.TIMESTAMP_TYPE_SIZE));
379     int compare = compareTimestamps(left.getTimestamp(), rtimestamp);
380     if (compare != 0) {
381       return compare;
382     }
383 
384     // Compare types. Let the delete types sort ahead of puts; i.e. types
385     // of higher numbers sort before those of lesser numbers. Maximum (255)
386     // appears ahead of everything, and minimum (0) appears after
387     // everything.
388     return (0xff & rtype) - (0xff & ltype);
389   }
390 
391   /**
392    * Compares the rows of the left and right cell
393    * For the hbase:meta case the 
394    * ({@link #compareRows(byte[], int, int, byte[], int, int)} is overridden such
395    * that it can handle the hbase:meta cells. The caller should ensure using the 
396    * appropriate comparator for hbase:meta
397    * TODO : Handle BB cases here
398    * @param left
399    * @param right
400    * @return 0 if both cells are equal, 1 if left cell is bigger than right, -1 otherwise
401    */
402   public int compareRows(final Cell left, final Cell right) {
403     return Bytes.compareTo(left.getRowArray(), left.getRowOffset(), left.getRowLength(),
404         right.getRowArray(), right.getRowOffset(), right.getRowLength());
405   }
406 
407   /**
408    * Compares the row part of the cell with a simple plain byte[] like the
409    * stopRow in Scan. This should be used with context where for hbase:meta
410    * cells the {{@link #META_COMPARATOR} should be used
411    *
412    * @param left
413    *          the cell to be compared
414    * @param right
415    *          the kv serialized byte[] to be compared with
416    * @param roffset
417    *          the offset in the byte[]
418    * @param rlength
419    *          the length in the byte[]
420    * @return 0 if both cell and the byte[] are equal, 1 if the cell is bigger
421    *         than byte[], -1 otherwise
422    */
423   public int compareRows(Cell left, byte[] right, int roffset,
424       int rlength) {
425     // TODO : for BB based cells all the hasArray based checks would happen
426     // here. But we may have
427     // to end up in multiple APIs accepting byte[] and BBs
428     return Bytes.compareTo(left.getRowArray(), left.getRowOffset(), left.getRowLength(), right,
429         roffset, rlength);
430   }
431 
432   private static int compareWithoutRow(final Cell left, final Cell right) {
433     // If the column is not specified, the "minimum" key type appears the
434     // latest in the sorted order, regardless of the timestamp. This is used
435     // for specifying the last key/value in a given row, because there is no
436     // "lexicographically last column" (it would be infinitely long). The
437     // "maximum" key type does not need this behavior.
438     // Copied from KeyValue. This is bad in that we can't do memcmp w/ special rules like this.
439     int lFamLength = left.getFamilyLength();
440     int rFamLength = right.getFamilyLength();
441     int lQualLength = left.getQualifierLength();
442     int rQualLength = right.getQualifierLength();
443     if (lFamLength + lQualLength == 0
444           && left.getTypeByte() == Type.Minimum.getCode()) {
445       // left is "bigger", i.e. it appears later in the sorted order
446       return 1;
447     }
448     if (rFamLength + rQualLength == 0
449         && right.getTypeByte() == Type.Minimum.getCode()) {
450       return -1;
451     }
452     boolean sameFamilySize = (lFamLength == rFamLength);
453     int lFamOffset = left.getFamilyOffset();
454     int rFamOffset = right.getFamilyOffset();
455     if (!sameFamilySize) {
456       // comparing column family is enough.
457       return compareFamilies(left, lFamOffset, lFamLength, right, rFamOffset, rFamLength);
458     }
459     // Families are same. Compare on qualifiers.
460     int lQualOffset = left.getQualifierOffset();
461     int rQualOffset = right.getQualifierOffset();
462     int diff = compareColumns(left, lFamOffset, lFamLength, lQualOffset, lQualLength, right,
463         rFamOffset, rFamLength, rQualOffset, rQualLength);
464     if (diff != 0) return diff;
465 
466     diff = compareTimestamps(left, right);
467     if (diff != 0) return diff;
468 
469     // Compare types. Let the delete types sort ahead of puts; i.e. types
470     // of higher numbers sort before those of lesser numbers. Maximum (255)
471     // appears ahead of everything, and minimum (0) appears after
472     // everything.
473     return (0xff & right.getTypeByte()) - (0xff & left.getTypeByte());
474   }
475 
476   /**
477    * Compares cell's timestamps in DESCENDING order.
478    * The below older timestamps sorting ahead of newer timestamps looks
479    * wrong but it is intentional. This way, newer timestamps are first
480    * found when we iterate over a memstore and newer versions are the
481    * first we trip over when reading from a store file.
482    * @return 1 if left's timestamp &lt; right's timestamp
483    *         -1 if left's timestamp &gt; right's timestamp
484    *         0 if both timestamps are equal
485    */
486   public static int compareTimestamps(final Cell left, final Cell right) {
487     return compareTimestamps(left.getTimestamp(), right.getTimestamp());
488   }
489 
490   /**
491    * Used to compare two cells based on the column hint provided. This is specifically
492    * used when we need to optimize the seeks based on the next indexed key. This is an
493    * advance usage API specifically needed for some optimizations.
494    * @param nextIndexedCell the next indexed cell 
495    * @param currentCell the cell to be compared
496    * @param foff the family offset of the currentCell
497    * @param flen the family length of the currentCell
498    * @param colHint the column hint provided - could be null
499    * @param coff the offset of the column hint if provided, if not offset of the currentCell's
500    * qualifier
501    * @param clen the length of the column hint if provided, if not length of the currentCell's
502    * qualifier
503    * @param ts the timestamp to be seeked
504    * @param type the type to be seeked
505    * @return an int based on the given column hint
506    * TODO : To be moved out of here because this is a special API used in scan
507    * optimization.
508    */
509   // compare a key against row/fam/qual/ts/type
510   public final int compareKeyBasedOnColHint(Cell nextIndexedCell, Cell currentCell, int foff,
511       int flen, byte[] colHint, int coff, int clen, long ts, byte type) {
512     int compare = compareRows(nextIndexedCell, currentCell);
513     if (compare != 0) {
514       return compare;
515     }
516     // If the column is not specified, the "minimum" key type appears the
517     // latest in the sorted order, regardless of the timestamp. This is used
518     // for specifying the last key/value in a given row, because there is no
519     // "lexicographically last column" (it would be infinitely long). The
520     // "maximum" key type does not need this behavior.
521     if (nextIndexedCell.getFamilyLength() + nextIndexedCell.getQualifierLength() == 0
522         && nextIndexedCell.getTypeByte() == Type.Minimum.getCode()) {
523       // left is "bigger", i.e. it appears later in the sorted order
524       return 1;
525     }
526     int qualLen = currentCell.getQualifierLength();
527     if (flen + clen == 0 && type == Type.Minimum.getCode()) {
528       return -1;
529     }
530 
531     compare = compareFamilies(nextIndexedCell, nextIndexedCell.getFamilyOffset(),
532         nextIndexedCell.getFamilyLength(), currentCell, currentCell.getFamilyOffset(),
533         flen);
534     if (compare != 0) {
535       return compare;
536     }
537     if (colHint == null) {
538       compare = compareQualifiers(nextIndexedCell, nextIndexedCell.getQualifierOffset(),
539           nextIndexedCell.getQualifierLength(), currentCell, currentCell.getQualifierOffset(),
540           qualLen);
541     } else {
542       compare = compareQualifiers(nextIndexedCell, nextIndexedCell.getQualifierOffset(),
543           nextIndexedCell.getQualifierLength(), colHint, coff, clen);
544     }
545     if (compare != 0) {
546       return compare;
547     }
548     // Next compare timestamps.
549     compare = compareTimestamps(nextIndexedCell.getTimestamp(), ts);
550     if (compare != 0) {
551       return compare;
552     }
553 
554     // Compare types. Let the delete types sort ahead of puts; i.e. types
555     // of higher numbers sort before those of lesser numbers. Maximum (255)
556     // appears ahead of everything, and minimum (0) appears after
557     // everything.
558     return (0xff & type) - (0xff & nextIndexedCell.getTypeByte());
559   }
560 
561   /**
562    * Compares timestamps in DESCENDING order.
563    * The below older timestamps sorting ahead of newer timestamps looks
564    * wrong but it is intentional. This way, newer timestamps are first
565    * found when we iterate over a memstore and newer versions are the
566    * first we trip over when reading from a store file.
567    * @return 1 if left timestamp &lt; right timestamp
568    *         -1 if left timestamp &gt; right timestamp
569    *         0 if both timestamps are equal
570    */
571   public static int compareTimestamps(final long ltimestamp, final long rtimestamp) {
572     if (ltimestamp < rtimestamp) {
573       return 1;
574     } else if (ltimestamp > rtimestamp) {
575       return -1;
576     }
577     return 0;
578   }
579 
580   /**
581    * Comparator that compares row component only of a Cell
582    */
583   public static class RowComparator extends CellComparator {
584     @Override
585     public int compare(Cell a, Cell b) {
586       return compareRows(a, b);
587     }
588   }
589 
590   /**
591    * A {@link CellComparator} for <code>hbase:meta</code> catalog table
592    * {@link KeyValue}s.
593    */
594   public static class MetaCellComparator extends CellComparator {
595 
596     @Override
597     public int compareRows(final Cell left, final Cell right) {
598       return compareRows(left.getRowArray(), left.getRowOffset(), left.getRowLength(),
599           right.getRowArray(), right.getRowOffset(), right.getRowLength());
600     }
601 
602     @Override
603     public int compareRows(Cell left, byte[] right, int roffset, int rlength) {
604       return compareRows(left.getRowArray(), left.getRowOffset(), left.getRowLength(), right,
605           roffset, rlength);
606     }
607 
608     private int compareRows(byte[] left, int loffset, int llength, byte[] right, int roffset,
609         int rlength) {
610       int leftDelimiter = Bytes.searchDelimiterIndex(left, loffset, llength, HConstants.DELIMITER);
611       int rightDelimiter = Bytes
612           .searchDelimiterIndex(right, roffset, rlength, HConstants.DELIMITER);
613       // Compare up to the delimiter
614       int lpart = (leftDelimiter < 0 ? llength : leftDelimiter - loffset);
615       int rpart = (rightDelimiter < 0 ? rlength : rightDelimiter - roffset);
616       int result = Bytes.compareTo(left, loffset, lpart, right, roffset, rpart);
617       if (result != 0) {
618         return result;
619       } else {
620         if (leftDelimiter < 0 && rightDelimiter >= 0) {
621           return -1;
622         } else if (rightDelimiter < 0 && leftDelimiter >= 0) {
623           return 1;
624         } else if (leftDelimiter < 0 && rightDelimiter < 0) {
625           return 0;
626         }
627       }
628       // Compare middle bit of the row.
629       // Move past delimiter
630       leftDelimiter++;
631       rightDelimiter++;
632       int leftFarDelimiter = Bytes.searchDelimiterIndexInReverse(left, leftDelimiter, llength
633           - (leftDelimiter - loffset), HConstants.DELIMITER);
634       int rightFarDelimiter = Bytes.searchDelimiterIndexInReverse(right, rightDelimiter, rlength
635           - (rightDelimiter - roffset), HConstants.DELIMITER);
636       // Now compare middlesection of row.
637       lpart = (leftFarDelimiter < 0 ? llength + loffset : leftFarDelimiter) - leftDelimiter;
638       rpart = (rightFarDelimiter < 0 ? rlength + roffset : rightFarDelimiter) - rightDelimiter;
639       result = Bytes.compareTo(left, leftDelimiter, lpart, right, rightDelimiter, rpart);
640       if (result != 0) {
641         return result;
642       } else {
643         if (leftDelimiter < 0 && rightDelimiter >= 0) {
644           return -1;
645         } else if (rightDelimiter < 0 && leftDelimiter >= 0) {
646           return 1;
647         } else if (leftDelimiter < 0 && rightDelimiter < 0) {
648           return 0;
649         }
650       }
651       // Compare last part of row, the rowid.
652       leftFarDelimiter++;
653       rightFarDelimiter++;
654       result = Bytes.compareTo(left, leftFarDelimiter, llength - (leftFarDelimiter - loffset),
655           right, rightFarDelimiter, rlength - (rightFarDelimiter - roffset));
656       return result;
657     }
658   }
659 }