001/*
002 * Licensed to the Apache Software Foundation (ASF) under one
003 * or more contributor license agreements.  See the NOTICE file
004 * distributed with this work for additional information
005 * regarding copyright ownership.  The ASF licenses this file
006 * to you under the Apache License, Version 2.0 (the
007 * "License"); you may not use this file except in compliance
008 * with the License.  You may obtain a copy of the License at
009 *
010 *     http://www.apache.org/licenses/LICENSE-2.0
011 *
012 * Unless required by applicable law or agreed to in writing, software
013 * distributed under the License is distributed on an "AS IS" BASIS,
014 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
015 * See the License for the specific language governing permissions and
016 * limitations under the License.
017 */
018package org.apache.hadoop.hbase;
019
020import java.util.Comparator;
021import org.apache.hadoop.hbase.util.ByteBufferUtils;
022import org.apache.hadoop.hbase.util.Bytes;
023import org.apache.yetus.audience.InterfaceAudience;
024import org.apache.yetus.audience.InterfaceStability;
025
026/**
027 * Compare two HBase cells. Do not use this method comparing <code>-ROOT-</code> or
028 * <code>hbase:meta</code> cells. Cells from these tables need a specialized comparator, one that
029 * takes account of the special formatting of the row where we have commas to delimit table from
030 * regionname, from row. See KeyValue for how it has a special comparator to do hbase:meta cells and
031 * yet another for -ROOT-.
032 * <p>
033 * While using this comparator for {{@link #compareRows(Cell, Cell)} et al, the hbase:meta cells
034 * format should be taken into consideration, for which the instance of this comparator should be
035 * used. In all other cases the static APIs in this comparator would be enough
036 * <p>
037 * HOT methods. We spend a good portion of CPU comparing. Anything that makes the compare faster
038 * will likely manifest at the macro level.
039 * </p>
040 */
041@edu.umd.cs.findbugs.annotations.SuppressWarnings(value = "UNKNOWN",
042    justification = "Findbugs doesn't like the way we are negating the result of"
043      + " a compare in below")
044@InterfaceAudience.Private
045@InterfaceStability.Evolving
046public class CellComparatorImpl implements CellComparator {
047
048  private static final long serialVersionUID = 8186411895799094989L;
049
050  /**
051   * Comparator for plain key/values; i.e. non-catalog table key/values. Works on Key portion of
052   * KeyValue only.
053   */
054  public static final CellComparatorImpl COMPARATOR = new CellComparatorImpl();
055
056  @Override
057  public final int compare(final Cell a, final Cell b) {
058    return compare(a, b, false);
059  }
060
061  @Override
062  public int compare(final Cell l, final Cell r, boolean ignoreSequenceid) {
063    int diff = 0;
064    // "Peel off" the most common path.
065    if (l instanceof KeyValue && r instanceof KeyValue) {
066      diff = compareKeyValues((KeyValue) l, (KeyValue) r);
067      if (diff != 0) {
068        return diff;
069      }
070    } else if (l instanceof KeyValue && r instanceof ByteBufferKeyValue) {
071      diff = compareKVVsBBKV((KeyValue) l, (ByteBufferKeyValue) r);
072      if (diff != 0) {
073        return diff;
074      }
075    } else if (l instanceof ByteBufferKeyValue && r instanceof KeyValue) {
076      diff = compareKVVsBBKV((KeyValue) r, (ByteBufferKeyValue) l);
077      if (diff != 0) {
078        // negate- Findbugs will complain?
079        return -diff;
080      }
081    } else if (l instanceof ByteBufferKeyValue && r instanceof ByteBufferKeyValue) {
082      diff = compareBBKV((ByteBufferKeyValue) l, (ByteBufferKeyValue) r);
083      if (diff != 0) {
084        return diff;
085      }
086    } else {
087      int leftRowLength = l.getRowLength();
088      int rightRowLength = r.getRowLength();
089      diff = compareRows(l, leftRowLength, r, rightRowLength);
090      if (diff != 0) {
091        return diff;
092      }
093
094      diff = compareWithoutRow(l, r);
095      if (diff != 0) {
096        return diff;
097      }
098    }
099    // Negate following comparisons so later edits show up first mvccVersion: later sorts first
100    return ignoreSequenceid ? diff : Long.compare(r.getSequenceId(), l.getSequenceId());
101  }
102
103  private static int compareKeyValues(final KeyValue left, final KeyValue right) {
104    int diff;
105    // Compare Rows. Cache row length.
106    int leftRowLength = left.getRowLength();
107    int rightRowLength = right.getRowLength();
108    diff = Bytes.compareTo(left.getRowArray(), left.getRowOffset(), leftRowLength,
109      right.getRowArray(), right.getRowOffset(), rightRowLength);
110    if (diff != 0) {
111      return diff;
112    }
113
114    // If the column is not specified, the "minimum" key type appears as latest in the sorted
115    // order, regardless of the timestamp. This is used for specifying the last key/value in a
116    // given row, because there is no "lexicographically last column" (it would be infinitely
117    // long).
118    // The "maximum" key type does not need this behavior. Copied from KeyValue. This is bad in
119    // that
120    // we can't do memcmp w/ special rules like this.
121    // TODO: Is there a test for this behavior?
122    int leftFamilyLengthPosition = left.getFamilyLengthPosition(leftRowLength);
123    int leftFamilyLength = left.getFamilyLength(leftFamilyLengthPosition);
124    int leftKeyLength = left.getKeyLength();
125    int leftQualifierLength =
126      left.getQualifierLength(leftKeyLength, leftRowLength, leftFamilyLength);
127
128    // No need of left row length below here.
129
130    byte leftType = left.getTypeByte(leftKeyLength);
131    if (
132      leftType == KeyValue.Type.Minimum.getCode() && leftFamilyLength + leftQualifierLength == 0
133    ) {
134      // left is "bigger", i.e. it appears later in the sorted order
135      return 1;
136    }
137
138    int rightFamilyLengthPosition = right.getFamilyLengthPosition(rightRowLength);
139    int rightFamilyLength = right.getFamilyLength(rightFamilyLengthPosition);
140    int rightKeyLength = right.getKeyLength();
141    int rightQualifierLength =
142      right.getQualifierLength(rightKeyLength, rightRowLength, rightFamilyLength);
143
144    // No need of right row length below here.
145
146    byte rightType = right.getTypeByte(rightKeyLength);
147    if (
148      rightType == KeyValue.Type.Minimum.getCode() && rightFamilyLength + rightQualifierLength == 0
149    ) {
150      return -1;
151    }
152
153    // Compare families.
154    int leftFamilyPosition = left.getFamilyOffset(leftFamilyLengthPosition);
155    int rightFamilyPosition = right.getFamilyOffset(rightFamilyLengthPosition);
156    diff = Bytes.compareTo(left.getFamilyArray(), leftFamilyPosition, leftFamilyLength,
157      right.getFamilyArray(), rightFamilyPosition, rightFamilyLength);
158    if (diff != 0) {
159      return diff;
160    }
161
162    // Compare qualifiers
163    diff = Bytes.compareTo(left.getQualifierArray(),
164      left.getQualifierOffset(leftFamilyPosition, leftFamilyLength), leftQualifierLength,
165      right.getQualifierArray(), right.getQualifierOffset(rightFamilyPosition, rightFamilyLength),
166      rightQualifierLength);
167    if (diff != 0) {
168      return diff;
169    }
170
171    // Timestamps.
172    // Swap order we pass into compare so we get DESCENDING order.
173    // TODO : Ensure we read the bytes and do the compare instead of the value.
174    diff = Long.compare(right.getTimestamp(rightKeyLength), left.getTimestamp(leftKeyLength));
175    if (diff != 0) {
176      return diff;
177    }
178
179    // Compare types. Let the delete types sort ahead of puts; i.e. types
180    // of higher numbers sort before those of lesser numbers. Maximum (255)
181    // appears ahead of everything, and minimum (0) appears after
182    // everything.
183    return (0xff & rightType) - (0xff & leftType);
184  }
185
186  private static int compareBBKV(final ByteBufferKeyValue left, final ByteBufferKeyValue right) {
187    int diff;
188    // Compare Rows. Cache row length.
189    int leftRowLength = left.getRowLength();
190    int rightRowLength = right.getRowLength();
191    diff = ByteBufferUtils.compareTo(left.getRowByteBuffer(), left.getRowPosition(), leftRowLength,
192      right.getRowByteBuffer(), right.getRowPosition(), rightRowLength);
193    if (diff != 0) {
194      return diff;
195    }
196
197    // If the column is not specified, the "minimum" key type appears as latest in the sorted
198    // order, regardless of the timestamp. This is used for specifying the last key/value in a
199    // given row, because there is no "lexicographically last column" (it would be infinitely
200    // long).
201    // The "maximum" key type does not need this behavior. Copied from KeyValue. This is bad in
202    // that
203    // we can't do memcmp w/ special rules like this.
204    // TODO: Is there a test for this behavior?
205    int leftFamilyLengthPosition = left.getFamilyLengthPosition(leftRowLength);
206    int leftFamilyLength = left.getFamilyLength(leftFamilyLengthPosition);
207    int leftKeyLength = left.getKeyLength();
208    int leftQualifierLength =
209      left.getQualifierLength(leftKeyLength, leftRowLength, leftFamilyLength);
210
211    // No need of left row length below here.
212
213    byte leftType = left.getTypeByte(leftKeyLength);
214    if (
215      leftType == KeyValue.Type.Minimum.getCode() && leftFamilyLength + leftQualifierLength == 0
216    ) {
217      // left is "bigger", i.e. it appears later in the sorted order
218      return 1;
219    }
220
221    int rightFamilyLengthPosition = right.getFamilyLengthPosition(rightRowLength);
222    int rightFamilyLength = right.getFamilyLength(rightFamilyLengthPosition);
223    int rightKeyLength = right.getKeyLength();
224    int rightQualifierLength =
225      right.getQualifierLength(rightKeyLength, rightRowLength, rightFamilyLength);
226
227    // No need of right row length below here.
228
229    byte rightType = right.getTypeByte(rightKeyLength);
230    if (
231      rightType == KeyValue.Type.Minimum.getCode() && rightFamilyLength + rightQualifierLength == 0
232    ) {
233      return -1;
234    }
235
236    // Compare families.
237    int leftFamilyPosition = left.getFamilyPosition(leftFamilyLengthPosition);
238    int rightFamilyPosition = right.getFamilyPosition(rightFamilyLengthPosition);
239    diff = ByteBufferUtils.compareTo(left.getFamilyByteBuffer(), leftFamilyPosition,
240      leftFamilyLength, right.getFamilyByteBuffer(), rightFamilyPosition, rightFamilyLength);
241    if (diff != 0) {
242      return diff;
243    }
244
245    // Compare qualifiers
246    diff = ByteBufferUtils.compareTo(left.getQualifierByteBuffer(),
247      left.getQualifierPosition(leftFamilyPosition, leftFamilyLength), leftQualifierLength,
248      right.getQualifierByteBuffer(),
249      right.getQualifierPosition(rightFamilyPosition, rightFamilyLength), rightQualifierLength);
250    if (diff != 0) {
251      return diff;
252    }
253
254    // Timestamps.
255    // Swap order we pass into compare so we get DESCENDING order.
256    diff = Long.compare(right.getTimestamp(rightKeyLength), left.getTimestamp(leftKeyLength));
257    if (diff != 0) {
258      return diff;
259    }
260
261    // Compare types. Let the delete types sort ahead of puts; i.e. types
262    // of higher numbers sort before those of lesser numbers. Maximum (255)
263    // appears ahead of everything, and minimum (0) appears after
264    // everything.
265    return (0xff & rightType) - (0xff & leftType);
266  }
267
268  private static int compareKVVsBBKV(final KeyValue left, final ByteBufferKeyValue right) {
269    int diff;
270    // Compare Rows. Cache row length.
271    int leftRowLength = left.getRowLength();
272    int rightRowLength = right.getRowLength();
273    diff = ByteBufferUtils.compareTo(left.getRowArray(), left.getRowOffset(), leftRowLength,
274      right.getRowByteBuffer(), right.getRowPosition(), rightRowLength);
275    if (diff != 0) {
276      return diff;
277    }
278
279    // If the column is not specified, the "minimum" key type appears as latest in the sorted
280    // order, regardless of the timestamp. This is used for specifying the last key/value in a
281    // given row, because there is no "lexicographically last column" (it would be infinitely
282    // long).
283    // The "maximum" key type does not need this behavior. Copied from KeyValue. This is bad in
284    // that
285    // we can't do memcmp w/ special rules like this.
286    // TODO: Is there a test for this behavior?
287    int leftFamilyLengthPosition = left.getFamilyLengthPosition(leftRowLength);
288    int leftFamilyLength = left.getFamilyLength(leftFamilyLengthPosition);
289    int leftKeyLength = left.getKeyLength();
290    int leftQualifierLength =
291      left.getQualifierLength(leftKeyLength, leftRowLength, leftFamilyLength);
292
293    // No need of left row length below here.
294
295    byte leftType = left.getTypeByte(leftKeyLength);
296    if (
297      leftType == KeyValue.Type.Minimum.getCode() && leftFamilyLength + leftQualifierLength == 0
298    ) {
299      // left is "bigger", i.e. it appears later in the sorted order
300      return 1;
301    }
302
303    int rightFamilyLengthPosition = right.getFamilyLengthPosition(rightRowLength);
304    int rightFamilyLength = right.getFamilyLength(rightFamilyLengthPosition);
305    int rightKeyLength = right.getKeyLength();
306    int rightQualifierLength =
307      right.getQualifierLength(rightKeyLength, rightRowLength, rightFamilyLength);
308
309    // No need of right row length below here.
310
311    byte rightType = right.getTypeByte(rightKeyLength);
312    if (
313      rightType == KeyValue.Type.Minimum.getCode() && rightFamilyLength + rightQualifierLength == 0
314    ) {
315      return -1;
316    }
317
318    // Compare families.
319    int leftFamilyPosition = left.getFamilyOffset(leftFamilyLengthPosition);
320    int rightFamilyPosition = right.getFamilyPosition(rightFamilyLengthPosition);
321    diff = ByteBufferUtils.compareTo(left.getFamilyArray(), leftFamilyPosition, leftFamilyLength,
322      right.getFamilyByteBuffer(), rightFamilyPosition, rightFamilyLength);
323    if (diff != 0) {
324      return diff;
325    }
326
327    // Compare qualifiers
328    diff = ByteBufferUtils.compareTo(left.getQualifierArray(),
329      left.getQualifierOffset(leftFamilyPosition, leftFamilyLength), leftQualifierLength,
330      right.getQualifierByteBuffer(),
331      right.getQualifierPosition(rightFamilyPosition, rightFamilyLength), rightQualifierLength);
332    if (diff != 0) {
333      return diff;
334    }
335
336    // Timestamps.
337    // Swap order we pass into compare so we get DESCENDING order.
338    diff = Long.compare(right.getTimestamp(rightKeyLength), left.getTimestamp(leftKeyLength));
339    if (diff != 0) {
340      return diff;
341    }
342
343    // Compare types. Let the delete types sort ahead of puts; i.e. types
344    // of higher numbers sort before those of lesser numbers. Maximum (255)
345    // appears ahead of everything, and minimum (0) appears after
346    // everything.
347    return (0xff & rightType) - (0xff & leftType);
348  }
349
350  /**
351   * Compares the family and qualifier part of the cell
352   * @return 0 if both cells are equal, 1 if left cell is bigger than right, -1 otherwise
353   */
354  public final int compareColumns(final Cell left, final Cell right) {
355    int diff = compareFamilies(left, right);
356    if (diff != 0) {
357      return diff;
358    }
359    return compareQualifiers(left, right);
360  }
361
362  private int compareColumns(final Cell left, final int leftFamLen, final int leftQualLen,
363    final Cell right, final int rightFamLen, final int rightQualLen) {
364    int diff = compareFamilies(left, leftFamLen, right, rightFamLen);
365    if (diff != 0) {
366      return diff;
367    }
368    return compareQualifiers(left, leftQualLen, right, rightQualLen);
369  }
370
371  private int compareFamilies(Cell left, int leftFamLen, Cell right, int rightFamLen) {
372    if (left instanceof ByteBufferExtendedCell && right instanceof ByteBufferExtendedCell) {
373      return ByteBufferUtils.compareTo(((ByteBufferExtendedCell) left).getFamilyByteBuffer(),
374        ((ByteBufferExtendedCell) left).getFamilyPosition(), leftFamLen,
375        ((ByteBufferExtendedCell) right).getFamilyByteBuffer(),
376        ((ByteBufferExtendedCell) right).getFamilyPosition(), rightFamLen);
377    }
378    if (left instanceof ByteBufferExtendedCell) {
379      return ByteBufferUtils.compareTo(((ByteBufferExtendedCell) left).getFamilyByteBuffer(),
380        ((ByteBufferExtendedCell) left).getFamilyPosition(), leftFamLen, right.getFamilyArray(),
381        right.getFamilyOffset(), rightFamLen);
382    }
383    if (right instanceof ByteBufferExtendedCell) {
384      // Notice how we flip the order of the compare here. We used to negate the return value but
385      // see what FindBugs says
386      // http://findbugs.sourceforge.net/bugDescriptions.html#RV_NEGATING_RESULT_OF_COMPARETO
387      // It suggest flipping the order to get same effect and 'safer'.
388      return ByteBufferUtils.compareTo(left.getFamilyArray(), left.getFamilyOffset(), leftFamLen,
389        ((ByteBufferExtendedCell) right).getFamilyByteBuffer(),
390        ((ByteBufferExtendedCell) right).getFamilyPosition(), rightFamLen);
391    }
392    return Bytes.compareTo(left.getFamilyArray(), left.getFamilyOffset(), leftFamLen,
393      right.getFamilyArray(), right.getFamilyOffset(), rightFamLen);
394  }
395
396  private final int compareQualifiers(Cell left, int leftQualLen, Cell right, int rightQualLen) {
397    if (left instanceof ByteBufferExtendedCell && right instanceof ByteBufferExtendedCell) {
398      return ByteBufferUtils.compareTo(((ByteBufferExtendedCell) left).getQualifierByteBuffer(),
399        ((ByteBufferExtendedCell) left).getQualifierPosition(), leftQualLen,
400        ((ByteBufferExtendedCell) right).getQualifierByteBuffer(),
401        ((ByteBufferExtendedCell) right).getQualifierPosition(), rightQualLen);
402    }
403    if (left instanceof ByteBufferExtendedCell) {
404      return ByteBufferUtils.compareTo(((ByteBufferExtendedCell) left).getQualifierByteBuffer(),
405        ((ByteBufferExtendedCell) left).getQualifierPosition(), leftQualLen,
406        right.getQualifierArray(), right.getQualifierOffset(), rightQualLen);
407    }
408    if (right instanceof ByteBufferExtendedCell) {
409      // Notice how we flip the order of the compare here. We used to negate the return value but
410      // see what FindBugs says
411      // http://findbugs.sourceforge.net/bugDescriptions.html#RV_NEGATING_RESULT_OF_COMPARETO
412      // It suggest flipping the order to get same effect and 'safer'.
413      return ByteBufferUtils.compareTo(left.getQualifierArray(), left.getQualifierOffset(),
414        leftQualLen, ((ByteBufferExtendedCell) right).getQualifierByteBuffer(),
415        ((ByteBufferExtendedCell) right).getQualifierPosition(), rightQualLen);
416    }
417    return Bytes.compareTo(left.getQualifierArray(), left.getQualifierOffset(), leftQualLen,
418      right.getQualifierArray(), right.getQualifierOffset(), rightQualLen);
419  }
420
421  /**
422   * Compare the families of left and right cell
423   * @return 0 if both cells are equal, 1 if left cell is bigger than right, -1 otherwise
424   */
425  @Override
426  public final int compareFamilies(Cell left, Cell right) {
427    if (left instanceof ByteBufferExtendedCell && right instanceof ByteBufferExtendedCell) {
428      return ByteBufferUtils.compareTo(((ByteBufferExtendedCell) left).getFamilyByteBuffer(),
429        ((ByteBufferExtendedCell) left).getFamilyPosition(), left.getFamilyLength(),
430        ((ByteBufferExtendedCell) right).getFamilyByteBuffer(),
431        ((ByteBufferExtendedCell) right).getFamilyPosition(), right.getFamilyLength());
432    }
433    if (left instanceof ByteBufferExtendedCell) {
434      return ByteBufferUtils.compareTo(((ByteBufferExtendedCell) left).getFamilyByteBuffer(),
435        ((ByteBufferExtendedCell) left).getFamilyPosition(), left.getFamilyLength(),
436        right.getFamilyArray(), right.getFamilyOffset(), right.getFamilyLength());
437    }
438    if (right instanceof ByteBufferExtendedCell) {
439      // Notice how we flip the order of the compare here. We used to negate the return value but
440      // see what FindBugs says
441      // http://findbugs.sourceforge.net/bugDescriptions.html#RV_NEGATING_RESULT_OF_COMPARETO
442      // It suggest flipping the order to get same effect and 'safer'.
443      return ByteBufferUtils.compareTo(left.getFamilyArray(), left.getFamilyOffset(),
444        left.getFamilyLength(), ((ByteBufferExtendedCell) right).getFamilyByteBuffer(),
445        ((ByteBufferExtendedCell) right).getFamilyPosition(), right.getFamilyLength());
446    }
447    return Bytes.compareTo(left.getFamilyArray(), left.getFamilyOffset(), left.getFamilyLength(),
448      right.getFamilyArray(), right.getFamilyOffset(), right.getFamilyLength());
449  }
450
451  static int compareQualifiers(KeyValue left, KeyValue right) {
452    // NOTE: Same method is in CellComparatorImpl, also private, not shared, intentionally. Not
453    // sharing gets us a few percent more throughput in compares. If changes here or there, make
454    // sure done in both places.
455    // Compare Rows. Cache row length.
456    int leftRowLength = left.getRowLength();
457    int rightRowLength = right.getRowLength();
458
459    int leftFamilyLengthPosition = left.getFamilyLengthPosition(leftRowLength);
460    byte leftFamilyLength = left.getFamilyLength(leftFamilyLengthPosition);
461    int leftKeyLength = left.getKeyLength();
462    int leftQualifierLength =
463      left.getQualifierLength(leftKeyLength, leftRowLength, leftFamilyLength);
464
465    // No need of left row length below here.
466
467    int rightFamilyLengthPosition = right.getFamilyLengthPosition(rightRowLength);
468    byte rightFamilyLength = right.getFamilyLength(rightFamilyLengthPosition);
469    int rightKeyLength = right.getKeyLength();
470    int rightQualifierLength =
471      right.getQualifierLength(rightKeyLength, rightRowLength, rightFamilyLength);
472
473    // Compare families.
474    int leftFamilyOffset = left.getFamilyOffset(leftFamilyLengthPosition);
475    int rightFamilyOffset = right.getFamilyOffset(rightFamilyLengthPosition);
476
477    // Compare qualifiers
478    return Bytes.compareTo(left.getQualifierArray(), leftFamilyOffset + leftFamilyLength,
479      leftQualifierLength, right.getQualifierArray(), rightFamilyOffset + rightFamilyLength,
480      rightQualifierLength);
481  }
482
483  static int compareQualifiers(KeyValue left, ByteBufferKeyValue right) {
484    // NOTE: Same method is in CellComparatorImpl, also private, not shared, intentionally. Not
485    // sharing gets us a few percent more throughput in compares. If changes here or there, make
486    // sure done in both places.
487    // Compare Rows. Cache row length.
488    int leftRowLength = left.getRowLength();
489    int rightRowLength = right.getRowLength();
490
491    int leftFamilyLengthPosition = left.getFamilyLengthPosition(leftRowLength);
492    byte leftFamilyLength = left.getFamilyLength(leftFamilyLengthPosition);
493    int leftKeyLength = left.getKeyLength();
494    int leftQualifierLength =
495      left.getQualifierLength(leftKeyLength, leftRowLength, leftFamilyLength);
496
497    // No need of left row length below here.
498
499    int rightFamilyLengthPosition = right.getFamilyLengthPosition(rightRowLength);
500    byte rightFamilyLength = right.getFamilyLength(rightFamilyLengthPosition);
501    int rightKeyLength = right.getKeyLength();
502    int rightQualifierLength =
503      right.getQualifierLength(rightKeyLength, rightRowLength, rightFamilyLength);
504
505    // Compare families.
506    int leftFamilyOffset = left.getFamilyOffset(leftFamilyLengthPosition);
507    int rightFamilyPosition = right.getFamilyPosition(rightFamilyLengthPosition);
508
509    // Compare qualifiers
510    return ByteBufferUtils.compareTo(left.getQualifierArray(), leftFamilyOffset + leftFamilyLength,
511      leftQualifierLength, right.getQualifierByteBuffer(), rightFamilyPosition + rightFamilyLength,
512      rightQualifierLength);
513  }
514
515  static int compareQualifiers(ByteBufferKeyValue left, KeyValue right) {
516    // NOTE: Same method is in CellComparatorImpl, also private, not shared, intentionally. Not
517    // sharing gets us a few percent more throughput in compares. If changes here or there, make
518    // sure done in both places.
519    // Compare Rows. Cache row length.
520    int leftRowLength = left.getRowLength();
521    int rightRowLength = right.getRowLength();
522
523    int leftFamilyLengthPosition = left.getFamilyLengthPosition(leftRowLength);
524    byte leftFamilyLength = left.getFamilyLength(leftFamilyLengthPosition);
525    int leftKeyLength = left.getKeyLength();
526    int leftQualifierLength =
527      left.getQualifierLength(leftKeyLength, leftRowLength, leftFamilyLength);
528
529    // No need of left row length below here.
530
531    int rightFamilyLengthPosition = right.getFamilyLengthPosition(rightRowLength);
532    byte rightFamilyLength = right.getFamilyLength(rightFamilyLengthPosition);
533    int rightKeyLength = right.getKeyLength();
534    int rightQualifierLength =
535      right.getQualifierLength(rightKeyLength, rightRowLength, rightFamilyLength);
536
537    // Compare families.
538    int leftFamilyPosition = left.getFamilyPosition(leftFamilyLengthPosition);
539    int rightFamilyOffset = right.getFamilyOffset(rightFamilyLengthPosition);
540
541    // Compare qualifiers
542    return ByteBufferUtils.compareTo(left.getQualifierByteBuffer(),
543      leftFamilyPosition + leftFamilyLength, leftQualifierLength, right.getQualifierArray(),
544      rightFamilyOffset + rightFamilyLength, rightQualifierLength);
545  }
546
547  static int compareQualifiers(ByteBufferKeyValue left, ByteBufferKeyValue right) {
548    // NOTE: Same method is in CellComparatorImpl, also private, not shared, intentionally. Not
549    // sharing gets us a few percent more throughput in compares. If changes here or there, make
550    // sure done in both places.
551    // Compare Rows. Cache row length.
552    int leftRowLength = left.getRowLength();
553    int rightRowLength = right.getRowLength();
554
555    int leftFamilyLengthPosition = left.getFamilyLengthPosition(leftRowLength);
556    byte leftFamilyLength = left.getFamilyLength(leftFamilyLengthPosition);
557    int leftKeyLength = left.getKeyLength();
558    int leftQualifierLength =
559      left.getQualifierLength(leftKeyLength, leftRowLength, leftFamilyLength);
560
561    // No need of left row length below here.
562
563    int rightFamilyLengthPosition = right.getFamilyLengthPosition(rightRowLength);
564    byte rightFamilyLength = right.getFamilyLength(rightFamilyLengthPosition);
565    int rightKeyLength = right.getKeyLength();
566    int rightQualifierLength =
567      right.getQualifierLength(rightKeyLength, rightRowLength, rightFamilyLength);
568
569    // Compare families.
570    int leftFamilyPosition = left.getFamilyPosition(leftFamilyLengthPosition);
571    int rightFamilyPosition = right.getFamilyPosition(rightFamilyLengthPosition);
572
573    // Compare qualifiers
574    return ByteBufferUtils.compareTo(left.getQualifierByteBuffer(),
575      leftFamilyPosition + leftFamilyLength, leftQualifierLength, right.getQualifierByteBuffer(),
576      rightFamilyPosition + rightFamilyLength, rightQualifierLength);
577  }
578
579  /**
580   * Compare the qualifiers part of the left and right cells.
581   * @return 0 if both cells are equal, 1 if left cell is bigger than right, -1 otherwise
582   */
583  @Override
584  public final int compareQualifiers(Cell left, Cell right) {
585    if ((left instanceof ByteBufferKeyValue) && (right instanceof ByteBufferKeyValue)) {
586      return compareQualifiers((ByteBufferKeyValue) left, (ByteBufferKeyValue) right);
587    } else if ((left instanceof KeyValue) && (right instanceof KeyValue)) {
588      return compareQualifiers((KeyValue) left, (KeyValue) right);
589    } else if ((left instanceof KeyValue) && (right instanceof ByteBufferKeyValue)) {
590      return compareQualifiers((KeyValue) left, (ByteBufferKeyValue) right);
591    } else if ((left instanceof ByteBufferKeyValue) && (right instanceof KeyValue)) {
592      return compareQualifiers((ByteBufferKeyValue) left, (KeyValue) right);
593    } else {
594      if (left instanceof ByteBufferExtendedCell && right instanceof ByteBufferExtendedCell) {
595        return ByteBufferUtils.compareTo(((ByteBufferExtendedCell) left).getQualifierByteBuffer(),
596          ((ByteBufferExtendedCell) left).getQualifierPosition(), left.getQualifierLength(),
597          ((ByteBufferExtendedCell) right).getQualifierByteBuffer(),
598          ((ByteBufferExtendedCell) right).getQualifierPosition(), right.getQualifierLength());
599      }
600      if (left instanceof ByteBufferExtendedCell) {
601        return ByteBufferUtils.compareTo(((ByteBufferExtendedCell) left).getQualifierByteBuffer(),
602          ((ByteBufferExtendedCell) left).getQualifierPosition(), left.getQualifierLength(),
603          right.getQualifierArray(), right.getQualifierOffset(), right.getQualifierLength());
604      }
605      if (right instanceof ByteBufferExtendedCell) {
606        // Notice how we flip the order of the compare here. We used to negate the return value but
607        // see what FindBugs says
608        // http://findbugs.sourceforge.net/bugDescriptions.html#RV_NEGATING_RESULT_OF_COMPARETO
609        // It suggest flipping the order to get same effect and 'safer'.
610        return ByteBufferUtils.compareTo(left.getQualifierArray(), left.getQualifierOffset(),
611          left.getQualifierLength(), ((ByteBufferExtendedCell) right).getQualifierByteBuffer(),
612          ((ByteBufferExtendedCell) right).getQualifierPosition(), right.getQualifierLength());
613      }
614      return Bytes.compareTo(left.getQualifierArray(), left.getQualifierOffset(),
615        left.getQualifierLength(), right.getQualifierArray(), right.getQualifierOffset(),
616        right.getQualifierLength());
617    }
618
619  }
620
621  /**
622   * Compares the rows of the left and right cell. For the hbase:meta case this method is overridden
623   * such that it can handle hbase:meta cells. The caller should ensure using the appropriate
624   * comparator for hbase:meta.
625   * @return 0 if both cells are equal, 1 if left cell is bigger than right, -1 otherwise
626   */
627  @Override
628  public int compareRows(final Cell left, final Cell right) {
629    return compareRows(left, left.getRowLength(), right, right.getRowLength());
630  }
631
632  static int compareRows(final Cell left, int leftRowLength, final Cell right, int rightRowLength) {
633    // left and right can be exactly the same at the beginning of a row
634    if (left == right) {
635      return 0;
636    }
637    if (left instanceof ByteBufferExtendedCell && right instanceof ByteBufferExtendedCell) {
638      return ByteBufferUtils.compareTo(((ByteBufferExtendedCell) left).getRowByteBuffer(),
639        ((ByteBufferExtendedCell) left).getRowPosition(), leftRowLength,
640        ((ByteBufferExtendedCell) right).getRowByteBuffer(),
641        ((ByteBufferExtendedCell) right).getRowPosition(), rightRowLength);
642    }
643    if (left instanceof ByteBufferExtendedCell) {
644      return ByteBufferUtils.compareTo(((ByteBufferExtendedCell) left).getRowByteBuffer(),
645        ((ByteBufferExtendedCell) left).getRowPosition(), leftRowLength, right.getRowArray(),
646        right.getRowOffset(), rightRowLength);
647    }
648    if (right instanceof ByteBufferExtendedCell) {
649      // Notice how we flip the order of the compare here. We used to negate the return value but
650      // see what FindBugs says
651      // http://findbugs.sourceforge.net/bugDescriptions.html#RV_NEGATING_RESULT_OF_COMPARETO
652      // It suggest flipping the order to get same effect and 'safer'.
653      return ByteBufferUtils.compareTo(left.getRowArray(), left.getRowOffset(), leftRowLength,
654        ((ByteBufferExtendedCell) right).getRowByteBuffer(),
655        ((ByteBufferExtendedCell) right).getRowPosition(), rightRowLength);
656    }
657    return Bytes.compareTo(left.getRowArray(), left.getRowOffset(), leftRowLength,
658      right.getRowArray(), right.getRowOffset(), rightRowLength);
659  }
660
661  /**
662   * Compares the row part of the cell with a simple plain byte[] like the stopRow in Scan. This
663   * should be used with context where for hbase:meta cells the
664   * {{@link MetaCellComparator#META_COMPARATOR} should be used the cell to be compared the kv
665   * serialized byte[] to be compared with the offset in the byte[] the length in the byte[]
666   * @return 0 if both cell and the byte[] are equal, 1 if the cell is bigger than byte[], -1
667   *         otherwise
668   */
669  @Override
670  public int compareRows(Cell left, byte[] right, int roffset, int rlength) {
671    if (left instanceof ByteBufferExtendedCell) {
672      return ByteBufferUtils.compareTo(((ByteBufferExtendedCell) left).getRowByteBuffer(),
673        ((ByteBufferExtendedCell) left).getRowPosition(), left.getRowLength(), right, roffset,
674        rlength);
675    }
676    return Bytes.compareTo(left.getRowArray(), left.getRowOffset(), left.getRowLength(), right,
677      roffset, rlength);
678  }
679
680  @Override
681  public final int compareWithoutRow(final Cell left, final Cell right) {
682    // If the column is not specified, the "minimum" key type appears the
683    // latest in the sorted order, regardless of the timestamp. This is used
684    // for specifying the last key/value in a given row, because there is no
685    // "lexicographically last column" (it would be infinitely long). The
686    // "maximum" key type does not need this behavior.
687    // Copied from KeyValue. This is bad in that we can't do memcmp w/ special rules like this.
688    int lFamLength = left.getFamilyLength();
689    int rFamLength = right.getFamilyLength();
690    int lQualLength = left.getQualifierLength();
691    int rQualLength = right.getQualifierLength();
692    if (lFamLength + lQualLength == 0 && left.getTypeByte() == KeyValue.Type.Minimum.getCode()) {
693      // left is "bigger", i.e. it appears later in the sorted order
694      return 1;
695    }
696    if (rFamLength + rQualLength == 0 && right.getTypeByte() == KeyValue.Type.Minimum.getCode()) {
697      return -1;
698    }
699    if (lFamLength != rFamLength) {
700      // comparing column family is enough.
701      return compareFamilies(left, lFamLength, right, rFamLength);
702    }
703    // Compare cf:qualifier
704    int diff = compareColumns(left, lFamLength, lQualLength, right, rFamLength, rQualLength);
705    if (diff != 0) {
706      return diff;
707    }
708
709    diff = compareTimestamps(left.getTimestamp(), right.getTimestamp());
710    if (diff != 0) {
711      return diff;
712    }
713
714    // Compare types. Let the delete types sort ahead of puts; i.e. types
715    // of higher numbers sort before those of lesser numbers. Maximum (255)
716    // appears ahead of everything, and minimum (0) appears after
717    // everything.
718    return (0xff & right.getTypeByte()) - (0xff & left.getTypeByte());
719  }
720
721  @Override
722  public int compareTimestamps(final Cell left, final Cell right) {
723    return compareTimestamps(left.getTimestamp(), right.getTimestamp());
724  }
725
726  @Override
727  public int compareTimestamps(final long ltimestamp, final long rtimestamp) {
728    // Swap order we pass into compare so we get DESCENDING order.
729    return Long.compare(rtimestamp, ltimestamp);
730  }
731
732  @Override
733  public Comparator getSimpleComparator() {
734    return this;
735  }
736
737  /**
738   * Utility method that makes a guess at comparator to use based off passed tableName. Use in
739   * extreme when no comparator specified.
740   * @return CellComparator to use going off the {@code tableName} passed.
741   */
742  public static CellComparator getCellComparator(TableName tableName) {
743    return getCellComparator(tableName.toBytes());
744  }
745
746  /**
747   * Utility method that makes a guess at comparator to use based off passed tableName. Use in
748   * extreme when no comparator specified.
749   * @return CellComparator to use going off the {@code tableName} passed.
750   */
751  public static CellComparator getCellComparator(byte[] tableName) {
752    // FYI, TableName.toBytes does not create an array; just returns existing array pointer.
753    return Bytes.equals(tableName, TableName.META_TABLE_NAME.toBytes())
754      ? MetaCellComparator.META_COMPARATOR
755      : CellComparatorImpl.COMPARATOR;
756  }
757}