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 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 = compareFamilies(left, leftFamilyPosition, leftFamilyLength, right, rightFamilyPosition, 157 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 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 = compareFamilies(left, leftFamilyPosition, leftFamilyLength, right, rightFamilyPosition, 240 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 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 = compareFamilies(left, leftFamilyPosition, leftFamilyLength, right, rightFamilyPosition, 322 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 /** 372 * This method will be overridden when we compare cells inner store to bypass family comparing. 373 */ 374 protected int compareFamilies(Cell left, int leftFamLen, Cell right, int rightFamLen) { 375 if (left instanceof ByteBufferExtendedCell && right instanceof ByteBufferExtendedCell) { 376 return ByteBufferUtils.compareTo(((ByteBufferExtendedCell) left).getFamilyByteBuffer(), 377 ((ByteBufferExtendedCell) left).getFamilyPosition(), leftFamLen, 378 ((ByteBufferExtendedCell) right).getFamilyByteBuffer(), 379 ((ByteBufferExtendedCell) right).getFamilyPosition(), rightFamLen); 380 } 381 if (left instanceof ByteBufferExtendedCell) { 382 return ByteBufferUtils.compareTo(((ByteBufferExtendedCell) left).getFamilyByteBuffer(), 383 ((ByteBufferExtendedCell) left).getFamilyPosition(), leftFamLen, right.getFamilyArray(), 384 right.getFamilyOffset(), rightFamLen); 385 } 386 if (right instanceof ByteBufferExtendedCell) { 387 // Notice how we flip the order of the compare here. We used to negate the return value but 388 // see what FindBugs says 389 // http://findbugs.sourceforge.net/bugDescriptions.html#RV_NEGATING_RESULT_OF_COMPARETO 390 // It suggest flipping the order to get same effect and 'safer'. 391 return ByteBufferUtils.compareTo(left.getFamilyArray(), left.getFamilyOffset(), leftFamLen, 392 ((ByteBufferExtendedCell) right).getFamilyByteBuffer(), 393 ((ByteBufferExtendedCell) right).getFamilyPosition(), rightFamLen); 394 } 395 return Bytes.compareTo(left.getFamilyArray(), left.getFamilyOffset(), leftFamLen, 396 right.getFamilyArray(), right.getFamilyOffset(), rightFamLen); 397 } 398 399 private final int compareQualifiers(Cell left, int leftQualLen, Cell right, int rightQualLen) { 400 if (left instanceof ByteBufferExtendedCell && right instanceof ByteBufferExtendedCell) { 401 return ByteBufferUtils.compareTo(((ByteBufferExtendedCell) left).getQualifierByteBuffer(), 402 ((ByteBufferExtendedCell) left).getQualifierPosition(), leftQualLen, 403 ((ByteBufferExtendedCell) right).getQualifierByteBuffer(), 404 ((ByteBufferExtendedCell) right).getQualifierPosition(), rightQualLen); 405 } 406 if (left instanceof ByteBufferExtendedCell) { 407 return ByteBufferUtils.compareTo(((ByteBufferExtendedCell) left).getQualifierByteBuffer(), 408 ((ByteBufferExtendedCell) left).getQualifierPosition(), leftQualLen, 409 right.getQualifierArray(), right.getQualifierOffset(), rightQualLen); 410 } 411 if (right instanceof ByteBufferExtendedCell) { 412 // Notice how we flip the order of the compare here. We used to negate the return value but 413 // see what FindBugs says 414 // http://findbugs.sourceforge.net/bugDescriptions.html#RV_NEGATING_RESULT_OF_COMPARETO 415 // It suggest flipping the order to get same effect and 'safer'. 416 return ByteBufferUtils.compareTo(left.getQualifierArray(), left.getQualifierOffset(), 417 leftQualLen, ((ByteBufferExtendedCell) right).getQualifierByteBuffer(), 418 ((ByteBufferExtendedCell) right).getQualifierPosition(), rightQualLen); 419 } 420 return Bytes.compareTo(left.getQualifierArray(), left.getQualifierOffset(), leftQualLen, 421 right.getQualifierArray(), right.getQualifierOffset(), rightQualLen); 422 } 423 424 /** 425 * Compare the families of left and right cell 426 * @return 0 if both cells are equal, 1 if left cell is bigger than right, -1 otherwise 427 */ 428 @Override 429 public final int compareFamilies(Cell left, Cell right) { 430 if (left instanceof ByteBufferExtendedCell && right instanceof ByteBufferExtendedCell) { 431 return ByteBufferUtils.compareTo(((ByteBufferExtendedCell) left).getFamilyByteBuffer(), 432 ((ByteBufferExtendedCell) left).getFamilyPosition(), left.getFamilyLength(), 433 ((ByteBufferExtendedCell) right).getFamilyByteBuffer(), 434 ((ByteBufferExtendedCell) right).getFamilyPosition(), right.getFamilyLength()); 435 } 436 if (left instanceof ByteBufferExtendedCell) { 437 return ByteBufferUtils.compareTo(((ByteBufferExtendedCell) left).getFamilyByteBuffer(), 438 ((ByteBufferExtendedCell) left).getFamilyPosition(), left.getFamilyLength(), 439 right.getFamilyArray(), right.getFamilyOffset(), right.getFamilyLength()); 440 } 441 if (right instanceof ByteBufferExtendedCell) { 442 // Notice how we flip the order of the compare here. We used to negate the return value but 443 // see what FindBugs says 444 // http://findbugs.sourceforge.net/bugDescriptions.html#RV_NEGATING_RESULT_OF_COMPARETO 445 // It suggest flipping the order to get same effect and 'safer'. 446 return ByteBufferUtils.compareTo(left.getFamilyArray(), left.getFamilyOffset(), 447 left.getFamilyLength(), ((ByteBufferExtendedCell) right).getFamilyByteBuffer(), 448 ((ByteBufferExtendedCell) right).getFamilyPosition(), right.getFamilyLength()); 449 } 450 return Bytes.compareTo(left.getFamilyArray(), left.getFamilyOffset(), left.getFamilyLength(), 451 right.getFamilyArray(), right.getFamilyOffset(), right.getFamilyLength()); 452 } 453 454 /** 455 * This method will be overridden when we compare cells inner store to bypass family comparing. 456 */ 457 protected int compareFamilies(KeyValue left, int leftFamilyPosition, int leftFamilyLength, 458 KeyValue right, int rightFamilyPosition, int rightFamilyLength) { 459 return Bytes.compareTo(left.getFamilyArray(), leftFamilyPosition, leftFamilyLength, 460 right.getFamilyArray(), rightFamilyPosition, rightFamilyLength); 461 } 462 463 /** 464 * This method will be overridden when we compare cells inner store to bypass family comparing. 465 */ 466 protected int compareFamilies(ByteBufferKeyValue left, int leftFamilyPosition, 467 int leftFamilyLength, ByteBufferKeyValue right, int rightFamilyPosition, 468 int rightFamilyLength) { 469 return ByteBufferUtils.compareTo(left.getFamilyByteBuffer(), leftFamilyPosition, 470 leftFamilyLength, right.getFamilyByteBuffer(), rightFamilyPosition, rightFamilyLength); 471 } 472 473 /** 474 * This method will be overridden when we compare cells inner store to bypass family comparing. 475 */ 476 protected int compareFamilies(KeyValue left, int leftFamilyPosition, int leftFamilyLength, 477 ByteBufferKeyValue right, int rightFamilyPosition, int rightFamilyLength) { 478 return ByteBufferUtils.compareTo(left.getFamilyArray(), leftFamilyPosition, leftFamilyLength, 479 right.getFamilyByteBuffer(), rightFamilyPosition, rightFamilyLength); 480 } 481 482 static int compareQualifiers(KeyValue left, KeyValue right) { 483 // NOTE: Same method is in CellComparatorImpl, also private, not shared, intentionally. Not 484 // sharing gets us a few percent more throughput in compares. If changes here or there, make 485 // sure done in both places. 486 // Compare Rows. Cache row length. 487 int leftRowLength = left.getRowLength(); 488 int rightRowLength = right.getRowLength(); 489 490 int leftFamilyLengthPosition = left.getFamilyLengthPosition(leftRowLength); 491 byte leftFamilyLength = left.getFamilyLength(leftFamilyLengthPosition); 492 int leftKeyLength = left.getKeyLength(); 493 int leftQualifierLength = 494 left.getQualifierLength(leftKeyLength, leftRowLength, leftFamilyLength); 495 496 // No need of left row length below here. 497 498 int rightFamilyLengthPosition = right.getFamilyLengthPosition(rightRowLength); 499 byte rightFamilyLength = right.getFamilyLength(rightFamilyLengthPosition); 500 int rightKeyLength = right.getKeyLength(); 501 int rightQualifierLength = 502 right.getQualifierLength(rightKeyLength, rightRowLength, rightFamilyLength); 503 504 // Compare families. 505 int leftFamilyOffset = left.getFamilyOffset(leftFamilyLengthPosition); 506 int rightFamilyOffset = right.getFamilyOffset(rightFamilyLengthPosition); 507 508 // Compare qualifiers 509 return Bytes.compareTo(left.getQualifierArray(), leftFamilyOffset + leftFamilyLength, 510 leftQualifierLength, right.getQualifierArray(), rightFamilyOffset + rightFamilyLength, 511 rightQualifierLength); 512 } 513 514 static int compareQualifiers(KeyValue left, ByteBufferKeyValue right) { 515 // NOTE: Same method is in CellComparatorImpl, also private, not shared, intentionally. Not 516 // sharing gets us a few percent more throughput in compares. If changes here or there, make 517 // sure done in both places. 518 // Compare Rows. Cache row length. 519 int leftRowLength = left.getRowLength(); 520 int rightRowLength = right.getRowLength(); 521 522 int leftFamilyLengthPosition = left.getFamilyLengthPosition(leftRowLength); 523 byte leftFamilyLength = left.getFamilyLength(leftFamilyLengthPosition); 524 int leftKeyLength = left.getKeyLength(); 525 int leftQualifierLength = 526 left.getQualifierLength(leftKeyLength, leftRowLength, leftFamilyLength); 527 528 // No need of left row length below here. 529 530 int rightFamilyLengthPosition = right.getFamilyLengthPosition(rightRowLength); 531 byte rightFamilyLength = right.getFamilyLength(rightFamilyLengthPosition); 532 int rightKeyLength = right.getKeyLength(); 533 int rightQualifierLength = 534 right.getQualifierLength(rightKeyLength, rightRowLength, rightFamilyLength); 535 536 // Compare families. 537 int leftFamilyOffset = left.getFamilyOffset(leftFamilyLengthPosition); 538 int rightFamilyPosition = right.getFamilyPosition(rightFamilyLengthPosition); 539 540 // Compare qualifiers 541 return ByteBufferUtils.compareTo(left.getQualifierArray(), leftFamilyOffset + leftFamilyLength, 542 leftQualifierLength, right.getQualifierByteBuffer(), rightFamilyPosition + rightFamilyLength, 543 rightQualifierLength); 544 } 545 546 static int compareQualifiers(ByteBufferKeyValue left, KeyValue right) { 547 // NOTE: Same method is in CellComparatorImpl, also private, not shared, intentionally. Not 548 // sharing gets us a few percent more throughput in compares. If changes here or there, make 549 // sure done in both places. 550 // Compare Rows. Cache row length. 551 int leftRowLength = left.getRowLength(); 552 int rightRowLength = right.getRowLength(); 553 554 int leftFamilyLengthPosition = left.getFamilyLengthPosition(leftRowLength); 555 byte leftFamilyLength = left.getFamilyLength(leftFamilyLengthPosition); 556 int leftKeyLength = left.getKeyLength(); 557 int leftQualifierLength = 558 left.getQualifierLength(leftKeyLength, leftRowLength, leftFamilyLength); 559 560 // No need of left row length below here. 561 562 int rightFamilyLengthPosition = right.getFamilyLengthPosition(rightRowLength); 563 byte rightFamilyLength = right.getFamilyLength(rightFamilyLengthPosition); 564 int rightKeyLength = right.getKeyLength(); 565 int rightQualifierLength = 566 right.getQualifierLength(rightKeyLength, rightRowLength, rightFamilyLength); 567 568 // Compare families. 569 int leftFamilyPosition = left.getFamilyPosition(leftFamilyLengthPosition); 570 int rightFamilyOffset = right.getFamilyOffset(rightFamilyLengthPosition); 571 572 // Compare qualifiers 573 return ByteBufferUtils.compareTo(left.getQualifierByteBuffer(), 574 leftFamilyPosition + leftFamilyLength, leftQualifierLength, right.getQualifierArray(), 575 rightFamilyOffset + rightFamilyLength, rightQualifierLength); 576 } 577 578 static int compareQualifiers(ByteBufferKeyValue left, ByteBufferKeyValue right) { 579 // NOTE: Same method is in CellComparatorImpl, also private, not shared, intentionally. Not 580 // sharing gets us a few percent more throughput in compares. If changes here or there, make 581 // sure done in both places. 582 // Compare Rows. Cache row length. 583 int leftRowLength = left.getRowLength(); 584 int rightRowLength = right.getRowLength(); 585 586 int leftFamilyLengthPosition = left.getFamilyLengthPosition(leftRowLength); 587 byte leftFamilyLength = left.getFamilyLength(leftFamilyLengthPosition); 588 int leftKeyLength = left.getKeyLength(); 589 int leftQualifierLength = 590 left.getQualifierLength(leftKeyLength, leftRowLength, leftFamilyLength); 591 592 // No need of left row length below here. 593 594 int rightFamilyLengthPosition = right.getFamilyLengthPosition(rightRowLength); 595 byte rightFamilyLength = right.getFamilyLength(rightFamilyLengthPosition); 596 int rightKeyLength = right.getKeyLength(); 597 int rightQualifierLength = 598 right.getQualifierLength(rightKeyLength, rightRowLength, rightFamilyLength); 599 600 // Compare families. 601 int leftFamilyPosition = left.getFamilyPosition(leftFamilyLengthPosition); 602 int rightFamilyPosition = right.getFamilyPosition(rightFamilyLengthPosition); 603 604 // Compare qualifiers 605 return ByteBufferUtils.compareTo(left.getQualifierByteBuffer(), 606 leftFamilyPosition + leftFamilyLength, leftQualifierLength, right.getQualifierByteBuffer(), 607 rightFamilyPosition + rightFamilyLength, rightQualifierLength); 608 } 609 610 /** 611 * Compare the qualifiers part of the left and right cells. 612 * @return 0 if both cells are equal, 1 if left cell is bigger than right, -1 otherwise 613 */ 614 @Override 615 public final int compareQualifiers(Cell left, Cell right) { 616 if ((left instanceof ByteBufferKeyValue) && (right instanceof ByteBufferKeyValue)) { 617 return compareQualifiers((ByteBufferKeyValue) left, (ByteBufferKeyValue) right); 618 } else if ((left instanceof KeyValue) && (right instanceof KeyValue)) { 619 return compareQualifiers((KeyValue) left, (KeyValue) right); 620 } else if ((left instanceof KeyValue) && (right instanceof ByteBufferKeyValue)) { 621 return compareQualifiers((KeyValue) left, (ByteBufferKeyValue) right); 622 } else if ((left instanceof ByteBufferKeyValue) && (right instanceof KeyValue)) { 623 return compareQualifiers((ByteBufferKeyValue) left, (KeyValue) right); 624 } else { 625 if (left instanceof ByteBufferExtendedCell && right instanceof ByteBufferExtendedCell) { 626 return ByteBufferUtils.compareTo(((ByteBufferExtendedCell) left).getQualifierByteBuffer(), 627 ((ByteBufferExtendedCell) left).getQualifierPosition(), left.getQualifierLength(), 628 ((ByteBufferExtendedCell) right).getQualifierByteBuffer(), 629 ((ByteBufferExtendedCell) right).getQualifierPosition(), right.getQualifierLength()); 630 } 631 if (left instanceof ByteBufferExtendedCell) { 632 return ByteBufferUtils.compareTo(((ByteBufferExtendedCell) left).getQualifierByteBuffer(), 633 ((ByteBufferExtendedCell) left).getQualifierPosition(), left.getQualifierLength(), 634 right.getQualifierArray(), right.getQualifierOffset(), right.getQualifierLength()); 635 } 636 if (right instanceof ByteBufferExtendedCell) { 637 // Notice how we flip the order of the compare here. We used to negate the return value but 638 // see what FindBugs says 639 // http://findbugs.sourceforge.net/bugDescriptions.html#RV_NEGATING_RESULT_OF_COMPARETO 640 // It suggest flipping the order to get same effect and 'safer'. 641 return ByteBufferUtils.compareTo(left.getQualifierArray(), left.getQualifierOffset(), 642 left.getQualifierLength(), ((ByteBufferExtendedCell) right).getQualifierByteBuffer(), 643 ((ByteBufferExtendedCell) right).getQualifierPosition(), right.getQualifierLength()); 644 } 645 return Bytes.compareTo(left.getQualifierArray(), left.getQualifierOffset(), 646 left.getQualifierLength(), right.getQualifierArray(), right.getQualifierOffset(), 647 right.getQualifierLength()); 648 } 649 650 } 651 652 /** 653 * Compares the rows of the left and right cell. For the hbase:meta case this method is overridden 654 * such that it can handle hbase:meta cells. The caller should ensure using the appropriate 655 * comparator for hbase:meta. 656 * @return 0 if both cells are equal, 1 if left cell is bigger than right, -1 otherwise 657 */ 658 @Override 659 public int compareRows(final Cell left, final Cell right) { 660 return compareRows(left, left.getRowLength(), right, right.getRowLength()); 661 } 662 663 static int compareRows(final Cell left, int leftRowLength, final Cell right, int rightRowLength) { 664 // left and right can be exactly the same at the beginning of a row 665 if (left == right) { 666 return 0; 667 } 668 if (left instanceof ByteBufferExtendedCell && right instanceof ByteBufferExtendedCell) { 669 return ByteBufferUtils.compareTo(((ByteBufferExtendedCell) left).getRowByteBuffer(), 670 ((ByteBufferExtendedCell) left).getRowPosition(), leftRowLength, 671 ((ByteBufferExtendedCell) right).getRowByteBuffer(), 672 ((ByteBufferExtendedCell) right).getRowPosition(), rightRowLength); 673 } 674 if (left instanceof ByteBufferExtendedCell) { 675 return ByteBufferUtils.compareTo(((ByteBufferExtendedCell) left).getRowByteBuffer(), 676 ((ByteBufferExtendedCell) left).getRowPosition(), leftRowLength, right.getRowArray(), 677 right.getRowOffset(), rightRowLength); 678 } 679 if (right instanceof ByteBufferExtendedCell) { 680 // Notice how we flip the order of the compare here. We used to negate the return value but 681 // see what FindBugs says 682 // http://findbugs.sourceforge.net/bugDescriptions.html#RV_NEGATING_RESULT_OF_COMPARETO 683 // It suggest flipping the order to get same effect and 'safer'. 684 return ByteBufferUtils.compareTo(left.getRowArray(), left.getRowOffset(), leftRowLength, 685 ((ByteBufferExtendedCell) right).getRowByteBuffer(), 686 ((ByteBufferExtendedCell) right).getRowPosition(), rightRowLength); 687 } 688 return Bytes.compareTo(left.getRowArray(), left.getRowOffset(), leftRowLength, 689 right.getRowArray(), right.getRowOffset(), rightRowLength); 690 } 691 692 /** 693 * Compares the row part of the cell with a simple plain byte[] like the stopRow in Scan. This 694 * should be used with context where for hbase:meta cells the 695 * {{@link MetaCellComparator#META_COMPARATOR} should be used the cell to be compared the kv 696 * serialized byte[] to be compared with the offset in the byte[] the length in the byte[] 697 * @return 0 if both cell and the byte[] are equal, 1 if the cell is bigger than byte[], -1 698 * otherwise 699 */ 700 @Override 701 public int compareRows(Cell left, byte[] right, int roffset, int rlength) { 702 if (left instanceof ByteBufferExtendedCell) { 703 return ByteBufferUtils.compareTo(((ByteBufferExtendedCell) left).getRowByteBuffer(), 704 ((ByteBufferExtendedCell) left).getRowPosition(), left.getRowLength(), right, roffset, 705 rlength); 706 } 707 return Bytes.compareTo(left.getRowArray(), left.getRowOffset(), left.getRowLength(), right, 708 roffset, rlength); 709 } 710 711 @Override 712 public final int compareWithoutRow(final Cell left, final Cell right) { 713 // If the column is not specified, the "minimum" key type appears the 714 // latest in the sorted order, regardless of the timestamp. This is used 715 // for specifying the last key/value in a given row, because there is no 716 // "lexicographically last column" (it would be infinitely long). The 717 // "maximum" key type does not need this behavior. 718 // Copied from KeyValue. This is bad in that we can't do memcmp w/ special rules like this. 719 int lFamLength = left.getFamilyLength(); 720 int rFamLength = right.getFamilyLength(); 721 int lQualLength = left.getQualifierLength(); 722 int rQualLength = right.getQualifierLength(); 723 if (lFamLength + lQualLength == 0 && left.getTypeByte() == KeyValue.Type.Minimum.getCode()) { 724 // left is "bigger", i.e. it appears later in the sorted order 725 return 1; 726 } 727 if (rFamLength + rQualLength == 0 && right.getTypeByte() == KeyValue.Type.Minimum.getCode()) { 728 return -1; 729 } 730 if (lFamLength != rFamLength) { 731 // comparing column family is enough. 732 return compareFamilies(left, lFamLength, right, rFamLength); 733 } 734 // Compare cf:qualifier 735 int diff = compareColumns(left, lFamLength, lQualLength, right, rFamLength, rQualLength); 736 if (diff != 0) { 737 return diff; 738 } 739 740 diff = compareTimestamps(left.getTimestamp(), right.getTimestamp()); 741 if (diff != 0) { 742 return diff; 743 } 744 745 // Compare types. Let the delete types sort ahead of puts; i.e. types 746 // of higher numbers sort before those of lesser numbers. Maximum (255) 747 // appears ahead of everything, and minimum (0) appears after 748 // everything. 749 return (0xff & right.getTypeByte()) - (0xff & left.getTypeByte()); 750 } 751 752 @Override 753 public int compareTimestamps(final Cell left, final Cell right) { 754 return compareTimestamps(left.getTimestamp(), right.getTimestamp()); 755 } 756 757 @Override 758 public int compareTimestamps(final long ltimestamp, final long rtimestamp) { 759 // Swap order we pass into compare so we get DESCENDING order. 760 return Long.compare(rtimestamp, ltimestamp); 761 } 762 763 @Override 764 public Comparator getSimpleComparator() { 765 return this; 766 } 767 768 /** 769 * Utility method that makes a guess at comparator to use based off passed tableName. Use in 770 * extreme when no comparator specified. 771 * @return CellComparator to use going off the {@code tableName} passed. 772 */ 773 public static CellComparator getCellComparator(TableName tableName) { 774 return getCellComparator(tableName.toBytes()); 775 } 776 777 /** 778 * Utility method that makes a guess at comparator to use based off passed tableName. Use in 779 * extreme when no comparator specified. 780 * @return CellComparator to use going off the {@code tableName} passed. 781 */ 782 public static CellComparator getCellComparator(byte[] tableName) { 783 // FYI, TableName.toBytes does not create an array; just returns existing array pointer. 784 return Bytes.equals(tableName, TableName.META_TABLE_NAME.toBytes()) 785 ? MetaCellComparator.META_COMPARATOR 786 : CellComparatorImpl.COMPARATOR; 787 } 788}