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.filter; 019 020import java.util.ArrayList; 021import java.util.Arrays; 022import java.util.Comparator; 023import java.util.List; 024import java.util.Objects; 025import java.util.PriorityQueue; 026import org.apache.hadoop.hbase.Cell; 027import org.apache.hadoop.hbase.CellComparator; 028import org.apache.hadoop.hbase.PrivateCellUtil; 029import org.apache.hadoop.hbase.exceptions.DeserializationException; 030import org.apache.hadoop.hbase.unsafe.HBasePlatformDependent; 031import org.apache.hadoop.hbase.util.Bytes; 032import org.apache.hadoop.hbase.util.Pair; 033import org.apache.yetus.audience.InterfaceAudience; 034 035import org.apache.hbase.thirdparty.com.google.protobuf.InvalidProtocolBufferException; 036import org.apache.hbase.thirdparty.com.google.protobuf.UnsafeByteOperations; 037 038import org.apache.hadoop.hbase.shaded.protobuf.generated.FilterProtos; 039import org.apache.hadoop.hbase.shaded.protobuf.generated.HBaseProtos.BytesBytesPair; 040 041/** 042 * This is optimized version of a standard FuzzyRowFilter Filters data based on fuzzy row key. 043 * Performs fast-forwards during scanning. It takes pairs (row key, fuzzy info) to match row keys. 044 * Where fuzzy info is a byte array with 0 or 1 as its values: 045 * <ul> 046 * <li>0 - means that this byte in provided row key is fixed, i.e. row key's byte at same position 047 * must match</li> 048 * <li>1 - means that this byte in provided row key is NOT fixed, i.e. row key's byte at this 049 * position can be different from the one in provided row key</li> 050 * </ul> 051 * Example: Let's assume row key format is userId_actionId_year_month. Length of userId is fixed and 052 * is 4, length of actionId is 2 and year and month are 4 and 2 bytes long respectively. Let's 053 * assume that we need to fetch all users that performed certain action (encoded as "99") in Jan of 054 * any year. Then the pair (row key, fuzzy info) would be the following: row key = "????_99_????_01" 055 * (one can use any value instead of "?") fuzzy info = 056 * "\x01\x01\x01\x01\x00\x00\x00\x00\x01\x01\x01\x01\x00\x00\x00" I.e. fuzzy info tells the matching 057 * mask is "????_99_????_01", where at ? can be any value. 058 */ 059@InterfaceAudience.Public 060public class FuzzyRowFilter extends FilterBase { 061 private static final boolean UNSAFE_UNALIGNED = HBasePlatformDependent.unaligned(); 062 private List<Pair<byte[], byte[]>> fuzzyKeysData; 063 private boolean done = false; 064 065 /** 066 * The index of a last successfully found matching fuzzy string (in fuzzyKeysData). We will start 067 * matching next KV with this one. If they do not match then we will return back to the one-by-one 068 * iteration over fuzzyKeysData. 069 */ 070 private int lastFoundIndex = -1; 071 072 /** 073 * Row tracker (keeps all next rows after SEEK_NEXT_USING_HINT was returned) 074 */ 075 private RowTracker tracker; 076 077 public FuzzyRowFilter(List<Pair<byte[], byte[]>> fuzzyKeysData) { 078 List<Pair<byte[], byte[]>> fuzzyKeyDataCopy = new ArrayList<>(fuzzyKeysData.size()); 079 080 for (Pair<byte[], byte[]> aFuzzyKeysData : fuzzyKeysData) { 081 if (aFuzzyKeysData.getFirst().length != aFuzzyKeysData.getSecond().length) { 082 Pair<String, String> readable = new Pair<>(Bytes.toStringBinary(aFuzzyKeysData.getFirst()), 083 Bytes.toStringBinary(aFuzzyKeysData.getSecond())); 084 throw new IllegalArgumentException("Fuzzy pair lengths do not match: " + readable); 085 } 086 087 Pair<byte[], byte[]> p = new Pair<>(); 088 // create a copy of pair bytes so that they are not modified by the filter. 089 p.setFirst(Arrays.copyOf(aFuzzyKeysData.getFirst(), aFuzzyKeysData.getFirst().length)); 090 p.setSecond(Arrays.copyOf(aFuzzyKeysData.getSecond(), aFuzzyKeysData.getSecond().length)); 091 092 // update mask ( 0 -> -1 (0xff), 1 -> 2) 093 p.setSecond(preprocessMask(p.getSecond())); 094 preprocessSearchKey(p); 095 096 fuzzyKeyDataCopy.add(p); 097 } 098 this.fuzzyKeysData = fuzzyKeyDataCopy; 099 this.tracker = new RowTracker(); 100 } 101 102 private void preprocessSearchKey(Pair<byte[], byte[]> p) { 103 if (!UNSAFE_UNALIGNED) { 104 // do nothing 105 return; 106 } 107 byte[] key = p.getFirst(); 108 byte[] mask = p.getSecond(); 109 for (int i = 0; i < mask.length; i++) { 110 // set non-fixed part of a search key to 0. 111 if (mask[i] == 2) { 112 key[i] = 0; 113 } 114 } 115 } 116 117 /** 118 * We need to preprocess mask array, as since we treat 2's as unfixed positions and -1 (0xff) as 119 * fixed positions 120 * @return mask array 121 */ 122 private byte[] preprocessMask(byte[] mask) { 123 if (!UNSAFE_UNALIGNED) { 124 // do nothing 125 return mask; 126 } 127 if (isPreprocessedMask(mask)) return mask; 128 for (int i = 0; i < mask.length; i++) { 129 if (mask[i] == 0) { 130 mask[i] = -1; // 0 -> -1 131 } else if (mask[i] == 1) { 132 mask[i] = 2;// 1 -> 2 133 } 134 } 135 return mask; 136 } 137 138 private boolean isPreprocessedMask(byte[] mask) { 139 for (int i = 0; i < mask.length; i++) { 140 if (mask[i] != -1 && mask[i] != 2) { 141 return false; 142 } 143 } 144 return true; 145 } 146 147 @Override 148 public ReturnCode filterCell(final Cell c) { 149 final int startIndex = lastFoundIndex >= 0 ? lastFoundIndex : 0; 150 final int size = fuzzyKeysData.size(); 151 for (int i = startIndex; i < size + startIndex; i++) { 152 final int index = i % size; 153 Pair<byte[], byte[]> fuzzyData = fuzzyKeysData.get(index); 154 // This shift is idempotent - always end up with 0 and -1 as mask values. 155 for (int j = 0; j < fuzzyData.getSecond().length; j++) { 156 fuzzyData.getSecond()[j] >>= 2; 157 } 158 SatisfiesCode satisfiesCode = satisfies(isReversed(), c.getRowArray(), c.getRowOffset(), 159 c.getRowLength(), fuzzyData.getFirst(), fuzzyData.getSecond()); 160 if (satisfiesCode == SatisfiesCode.YES) { 161 lastFoundIndex = index; 162 return ReturnCode.INCLUDE; 163 } 164 } 165 // NOT FOUND -> seek next using hint 166 lastFoundIndex = -1; 167 168 return ReturnCode.SEEK_NEXT_USING_HINT; 169 170 } 171 172 @Override 173 public Cell getNextCellHint(Cell currentCell) { 174 boolean result = tracker.updateTracker(currentCell); 175 if (result == false) { 176 done = true; 177 return null; 178 } 179 byte[] nextRowKey = tracker.nextRow(); 180 return PrivateCellUtil.createFirstOnRow(nextRowKey, 0, (short) nextRowKey.length); 181 } 182 183 /** 184 * If we have multiple fuzzy keys, row tracker should improve overall performance. It calculates 185 * all next rows (one per every fuzzy key) and put them (the fuzzy key is bundled) into a priority 186 * queue so that the smallest row key always appears at queue head, which helps to decide the 187 * "Next Cell Hint". As scanning going on, the number of candidate rows in the RowTracker will 188 * remain the size of fuzzy keys until some of the fuzzy keys won't possibly have matches any 189 * more. 190 */ 191 private class RowTracker { 192 private final PriorityQueue<Pair<byte[], Pair<byte[], byte[]>>> nextRows; 193 private boolean initialized = false; 194 195 RowTracker() { 196 nextRows = new PriorityQueue<>(fuzzyKeysData.size(), 197 new Comparator<Pair<byte[], Pair<byte[], byte[]>>>() { 198 @Override 199 public int compare(Pair<byte[], Pair<byte[], byte[]>> o1, 200 Pair<byte[], Pair<byte[], byte[]>> o2) { 201 return isReversed() 202 ? Bytes.compareTo(o2.getFirst(), o1.getFirst()) 203 : Bytes.compareTo(o1.getFirst(), o2.getFirst()); 204 } 205 }); 206 } 207 208 byte[] nextRow() { 209 if (nextRows.isEmpty()) { 210 throw new IllegalStateException("NextRows should not be empty, " 211 + "make sure to call nextRow() after updateTracker() return true"); 212 } else { 213 return nextRows.peek().getFirst(); 214 } 215 } 216 217 boolean updateTracker(Cell currentCell) { 218 if (!initialized) { 219 for (Pair<byte[], byte[]> fuzzyData : fuzzyKeysData) { 220 updateWith(currentCell, fuzzyData); 221 } 222 initialized = true; 223 } else { 224 while (!nextRows.isEmpty() && !lessThan(currentCell, nextRows.peek().getFirst())) { 225 Pair<byte[], Pair<byte[], byte[]>> head = nextRows.poll(); 226 Pair<byte[], byte[]> fuzzyData = head.getSecond(); 227 updateWith(currentCell, fuzzyData); 228 } 229 } 230 return !nextRows.isEmpty(); 231 } 232 233 boolean lessThan(Cell currentCell, byte[] nextRowKey) { 234 int compareResult = 235 CellComparator.getInstance().compareRows(currentCell, nextRowKey, 0, nextRowKey.length); 236 return (!isReversed() && compareResult < 0) || (isReversed() && compareResult > 0); 237 } 238 239 void updateWith(Cell currentCell, Pair<byte[], byte[]> fuzzyData) { 240 byte[] nextRowKeyCandidate = 241 getNextForFuzzyRule(isReversed(), currentCell.getRowArray(), currentCell.getRowOffset(), 242 currentCell.getRowLength(), fuzzyData.getFirst(), fuzzyData.getSecond()); 243 if (nextRowKeyCandidate != null) { 244 nextRows.add(new Pair<>(nextRowKeyCandidate, fuzzyData)); 245 } 246 } 247 248 } 249 250 @Override 251 public boolean filterAllRemaining() { 252 return done; 253 } 254 255 /** Returns The filter serialized using pb */ 256 @Override 257 public byte[] toByteArray() { 258 FilterProtos.FuzzyRowFilter.Builder builder = FilterProtos.FuzzyRowFilter.newBuilder(); 259 for (Pair<byte[], byte[]> fuzzyData : fuzzyKeysData) { 260 BytesBytesPair.Builder bbpBuilder = BytesBytesPair.newBuilder(); 261 bbpBuilder.setFirst(UnsafeByteOperations.unsafeWrap(fuzzyData.getFirst())); 262 bbpBuilder.setSecond(UnsafeByteOperations.unsafeWrap(fuzzyData.getSecond())); 263 builder.addFuzzyKeysData(bbpBuilder); 264 } 265 return builder.build().toByteArray(); 266 } 267 268 /** 269 * Parse a serialized representation of {@link FuzzyRowFilter} 270 * @param pbBytes A pb serialized {@link FuzzyRowFilter} instance 271 * @return An instance of {@link FuzzyRowFilter} made from <code>bytes</code> 272 * @throws DeserializationException if an error occurred 273 * @see #toByteArray 274 */ 275 public static FuzzyRowFilter parseFrom(final byte[] pbBytes) throws DeserializationException { 276 FilterProtos.FuzzyRowFilter proto; 277 try { 278 proto = FilterProtos.FuzzyRowFilter.parseFrom(pbBytes); 279 } catch (InvalidProtocolBufferException e) { 280 throw new DeserializationException(e); 281 } 282 int count = proto.getFuzzyKeysDataCount(); 283 ArrayList<Pair<byte[], byte[]>> fuzzyKeysData = new ArrayList<>(count); 284 for (int i = 0; i < count; ++i) { 285 BytesBytesPair current = proto.getFuzzyKeysData(i); 286 byte[] keyBytes = current.getFirst().toByteArray(); 287 byte[] keyMeta = current.getSecond().toByteArray(); 288 fuzzyKeysData.add(new Pair<>(keyBytes, keyMeta)); 289 } 290 return new FuzzyRowFilter(fuzzyKeysData); 291 } 292 293 @Override 294 public String toString() { 295 final StringBuilder sb = new StringBuilder(); 296 sb.append("FuzzyRowFilter"); 297 sb.append("{fuzzyKeysData="); 298 for (Pair<byte[], byte[]> fuzzyData : fuzzyKeysData) { 299 sb.append('{').append(Bytes.toStringBinary(fuzzyData.getFirst())).append(":"); 300 sb.append(Bytes.toStringBinary(fuzzyData.getSecond())).append('}'); 301 } 302 sb.append("}, "); 303 return sb.toString(); 304 } 305 306 // Utility methods 307 308 static enum SatisfiesCode { 309 /** row satisfies fuzzy rule */ 310 YES, 311 /** row doesn't satisfy fuzzy rule, but there's possible greater row that does */ 312 NEXT_EXISTS, 313 /** row doesn't satisfy fuzzy rule and there's no greater row that does */ 314 NO_NEXT 315 } 316 317 static SatisfiesCode satisfies(byte[] row, byte[] fuzzyKeyBytes, byte[] fuzzyKeyMeta) { 318 return satisfies(false, row, 0, row.length, fuzzyKeyBytes, fuzzyKeyMeta); 319 } 320 321 static SatisfiesCode satisfies(boolean reverse, byte[] row, byte[] fuzzyKeyBytes, 322 byte[] fuzzyKeyMeta) { 323 return satisfies(reverse, row, 0, row.length, fuzzyKeyBytes, fuzzyKeyMeta); 324 } 325 326 static SatisfiesCode satisfies(boolean reverse, byte[] row, int offset, int length, 327 byte[] fuzzyKeyBytes, byte[] fuzzyKeyMeta) { 328 329 if (!UNSAFE_UNALIGNED) { 330 return satisfiesNoUnsafe(reverse, row, offset, length, fuzzyKeyBytes, fuzzyKeyMeta); 331 } 332 333 if (row == null) { 334 // do nothing, let scan to proceed 335 return SatisfiesCode.YES; 336 } 337 length = Math.min(length, fuzzyKeyBytes.length); 338 int numWords = length / Bytes.SIZEOF_LONG; 339 340 int j = numWords << 3; // numWords * SIZEOF_LONG; 341 342 for (int i = 0; i < j; i += Bytes.SIZEOF_LONG) { 343 long fuzzyBytes = Bytes.toLong(fuzzyKeyBytes, i); 344 long fuzzyMeta = Bytes.toLong(fuzzyKeyMeta, i); 345 long rowValue = Bytes.toLong(row, offset + i); 346 if ((rowValue & fuzzyMeta) != fuzzyBytes) { 347 // We always return NEXT_EXISTS 348 return SatisfiesCode.NEXT_EXISTS; 349 } 350 } 351 352 int off = j; 353 354 if (length - off >= Bytes.SIZEOF_INT) { 355 int fuzzyBytes = Bytes.toInt(fuzzyKeyBytes, off); 356 int fuzzyMeta = Bytes.toInt(fuzzyKeyMeta, off); 357 int rowValue = Bytes.toInt(row, offset + off); 358 if ((rowValue & fuzzyMeta) != fuzzyBytes) { 359 // We always return NEXT_EXISTS 360 return SatisfiesCode.NEXT_EXISTS; 361 } 362 off += Bytes.SIZEOF_INT; 363 } 364 365 if (length - off >= Bytes.SIZEOF_SHORT) { 366 short fuzzyBytes = Bytes.toShort(fuzzyKeyBytes, off); 367 short fuzzyMeta = Bytes.toShort(fuzzyKeyMeta, off); 368 short rowValue = Bytes.toShort(row, offset + off); 369 if ((rowValue & fuzzyMeta) != fuzzyBytes) { 370 // We always return NEXT_EXISTS 371 // even if it does not (in this case getNextForFuzzyRule 372 // will return null) 373 return SatisfiesCode.NEXT_EXISTS; 374 } 375 off += Bytes.SIZEOF_SHORT; 376 } 377 378 if (length - off >= Bytes.SIZEOF_BYTE) { 379 int fuzzyBytes = fuzzyKeyBytes[off] & 0xff; 380 int fuzzyMeta = fuzzyKeyMeta[off] & 0xff; 381 int rowValue = row[offset + off] & 0xff; 382 if ((rowValue & fuzzyMeta) != fuzzyBytes) { 383 // We always return NEXT_EXISTS 384 return SatisfiesCode.NEXT_EXISTS; 385 } 386 } 387 return SatisfiesCode.YES; 388 } 389 390 static SatisfiesCode satisfiesNoUnsafe(boolean reverse, byte[] row, int offset, int length, 391 byte[] fuzzyKeyBytes, byte[] fuzzyKeyMeta) { 392 if (row == null) { 393 // do nothing, let scan to proceed 394 return SatisfiesCode.YES; 395 } 396 397 Order order = Order.orderFor(reverse); 398 boolean nextRowKeyCandidateExists = false; 399 400 for (int i = 0; i < fuzzyKeyMeta.length && i < length; i++) { 401 // First, checking if this position is fixed and not equals the given one 402 boolean byteAtPositionFixed = fuzzyKeyMeta[i] == 0; 403 boolean fixedByteIncorrect = byteAtPositionFixed && fuzzyKeyBytes[i] != row[i + offset]; 404 if (fixedByteIncorrect) { 405 // in this case there's another row that satisfies fuzzy rule and bigger than this row 406 if (nextRowKeyCandidateExists) { 407 return SatisfiesCode.NEXT_EXISTS; 408 } 409 410 // If this row byte is less than fixed then there's a byte array bigger than 411 // this row and which satisfies the fuzzy rule. Otherwise there's no such byte array: 412 // this row is simply bigger than any byte array that satisfies the fuzzy rule 413 boolean rowByteLessThanFixed = (row[i + offset] & 0xFF) < (fuzzyKeyBytes[i] & 0xFF); 414 if (rowByteLessThanFixed && !reverse) { 415 return SatisfiesCode.NEXT_EXISTS; 416 } else if (!rowByteLessThanFixed && reverse) { 417 return SatisfiesCode.NEXT_EXISTS; 418 } else { 419 return SatisfiesCode.NO_NEXT; 420 } 421 } 422 423 // Second, checking if this position is not fixed and byte value is not the biggest. In this 424 // case there's a byte array bigger than this row and which satisfies the fuzzy rule. To get 425 // bigger byte array that satisfies the rule we need to just increase this byte 426 // (see the code of getNextForFuzzyRule below) by one. 427 // Note: if non-fixed byte is already at biggest value, this doesn't allow us to say there's 428 // bigger one that satisfies the rule as it can't be increased. 429 if (fuzzyKeyMeta[i] == 1 && !order.isMax(fuzzyKeyBytes[i])) { 430 nextRowKeyCandidateExists = true; 431 } 432 } 433 return SatisfiesCode.YES; 434 } 435 436 static byte[] getNextForFuzzyRule(byte[] row, byte[] fuzzyKeyBytes, byte[] fuzzyKeyMeta) { 437 return getNextForFuzzyRule(false, row, 0, row.length, fuzzyKeyBytes, fuzzyKeyMeta); 438 } 439 440 static byte[] getNextForFuzzyRule(boolean reverse, byte[] row, byte[] fuzzyKeyBytes, 441 byte[] fuzzyKeyMeta) { 442 return getNextForFuzzyRule(reverse, row, 0, row.length, fuzzyKeyBytes, fuzzyKeyMeta); 443 } 444 445 /** Abstracts directional comparisons based on scan direction. */ 446 private enum Order { 447 ASC { 448 @Override 449 public boolean lt(int lhs, int rhs) { 450 return lhs < rhs; 451 } 452 453 @Override 454 public boolean gt(int lhs, int rhs) { 455 return lhs > rhs; 456 } 457 458 @Override 459 public byte inc(byte val) { 460 // TODO: what about over/underflow? 461 return (byte) (val + 1); 462 } 463 464 @Override 465 public boolean isMax(byte val) { 466 return val == (byte) 0xff; 467 } 468 469 @Override 470 public byte min() { 471 return 0; 472 } 473 }, 474 DESC { 475 @Override 476 public boolean lt(int lhs, int rhs) { 477 return lhs > rhs; 478 } 479 480 @Override 481 public boolean gt(int lhs, int rhs) { 482 return lhs < rhs; 483 } 484 485 @Override 486 public byte inc(byte val) { 487 // TODO: what about over/underflow? 488 return (byte) (val - 1); 489 } 490 491 @Override 492 public boolean isMax(byte val) { 493 return val == 0; 494 } 495 496 @Override 497 public byte min() { 498 return (byte) 0xFF; 499 } 500 }; 501 502 public static Order orderFor(boolean reverse) { 503 return reverse ? DESC : ASC; 504 } 505 506 /** Returns true when {@code lhs < rhs}. */ 507 public abstract boolean lt(int lhs, int rhs); 508 509 /** Returns true when {@code lhs > rhs}. */ 510 public abstract boolean gt(int lhs, int rhs); 511 512 /** Returns {@code val} incremented by 1. */ 513 public abstract byte inc(byte val); 514 515 /** Return true when {@code val} is the maximum value */ 516 public abstract boolean isMax(byte val); 517 518 /** Return the minimum value according to this ordering scheme. */ 519 public abstract byte min(); 520 } 521 522 /** 523 * @return greater byte array than given (row) which satisfies the fuzzy rule if it exists, null 524 * otherwise 525 */ 526 static byte[] getNextForFuzzyRule(boolean reverse, byte[] row, int offset, int length, 527 byte[] fuzzyKeyBytes, byte[] fuzzyKeyMeta) { 528 // To find out the next "smallest" byte array that satisfies fuzzy rule and "greater" than 529 // the given one we do the following: 530 // 1. setting values on all "fixed" positions to the values from fuzzyKeyBytes 531 // 2. if during the first step given row did not increase, then we increase the value at 532 // the first "non-fixed" position (where it is not maximum already) 533 534 // It is easier to perform this by using fuzzyKeyBytes copy and setting "non-fixed" position 535 // values than otherwise. 536 byte[] result = 537 Arrays.copyOf(fuzzyKeyBytes, length > fuzzyKeyBytes.length ? length : fuzzyKeyBytes.length); 538 if (reverse && length > fuzzyKeyBytes.length) { 539 // we need trailing 0xff's instead of trailing 0x00's 540 for (int i = fuzzyKeyBytes.length; i < result.length; i++) { 541 result[i] = (byte) 0xFF; 542 } 543 } 544 int toInc = -1; 545 final Order order = Order.orderFor(reverse); 546 547 boolean increased = false; 548 for (int i = 0; i < result.length; i++) { 549 if (i >= fuzzyKeyMeta.length || fuzzyKeyMeta[i] == 0 /* non-fixed */) { 550 result[i] = row[offset + i]; 551 if (!order.isMax(row[offset + i])) { 552 // this is "non-fixed" position and is not at max value, hence we can increase it 553 toInc = i; 554 } 555 } else if (i < fuzzyKeyMeta.length && fuzzyKeyMeta[i] == -1 /* fixed */) { 556 if (order.lt((row[i + offset] & 0xFF), (fuzzyKeyBytes[i] & 0xFF))) { 557 // if setting value for any fixed position increased the original array, 558 // we are OK 559 increased = true; 560 break; 561 } 562 563 if (order.gt((row[i + offset] & 0xFF), (fuzzyKeyBytes[i] & 0xFF))) { 564 // if setting value for any fixed position makes array "smaller", then just stop: 565 // in case we found some non-fixed position to increase we will do it, otherwise 566 // there's no "next" row key that satisfies fuzzy rule and "greater" than given row 567 break; 568 } 569 } 570 } 571 572 if (!increased) { 573 if (toInc < 0) { 574 return null; 575 } 576 result[toInc] = order.inc(result[toInc]); 577 578 // Setting all "non-fixed" positions to zeroes to the right of the one we increased so 579 // that found "next" row key is the smallest possible 580 for (int i = toInc + 1; i < result.length; i++) { 581 if (i >= fuzzyKeyMeta.length || fuzzyKeyMeta[i] == 0 /* non-fixed */) { 582 result[i] = order.min(); 583 } 584 } 585 } 586 587 return reverse ? result : trimTrailingZeroes(result, fuzzyKeyMeta, toInc); 588 } 589 590 /** 591 * For forward scanner, next cell hint should not contain any trailing zeroes unless they are part 592 * of fuzzyKeyMeta hint = '\x01\x01\x01\x00\x00' will skip valid row '\x01\x01\x01' 593 * @param toInc - position of incremented byte 594 * @return trimmed version of result 595 */ 596 597 private static byte[] trimTrailingZeroes(byte[] result, byte[] fuzzyKeyMeta, int toInc) { 598 int off = fuzzyKeyMeta.length >= result.length ? result.length - 1 : fuzzyKeyMeta.length - 1; 599 for (; off >= 0; off--) { 600 if (fuzzyKeyMeta[off] != 0) break; 601 } 602 if (off < toInc) off = toInc; 603 byte[] retValue = new byte[off + 1]; 604 System.arraycopy(result, 0, retValue, 0, retValue.length); 605 return retValue; 606 } 607 608 /** 609 * Returns true if and only if the fields of the filter that are serialized are equal to the 610 * corresponding fields in other. Used for testing. 611 */ 612 @Override 613 boolean areSerializedFieldsEqual(Filter o) { 614 if (o == this) { 615 return true; 616 } 617 if (!(o instanceof FuzzyRowFilter)) { 618 return false; 619 } 620 FuzzyRowFilter other = (FuzzyRowFilter) o; 621 if (this.fuzzyKeysData.size() != other.fuzzyKeysData.size()) return false; 622 for (int i = 0; i < fuzzyKeysData.size(); ++i) { 623 Pair<byte[], byte[]> thisData = this.fuzzyKeysData.get(i); 624 Pair<byte[], byte[]> otherData = other.fuzzyKeysData.get(i); 625 if ( 626 !(Bytes.equals(thisData.getFirst(), otherData.getFirst()) 627 && Bytes.equals(thisData.getSecond(), otherData.getSecond())) 628 ) { 629 return false; 630 } 631 } 632 return true; 633 } 634 635 @Override 636 public boolean equals(Object obj) { 637 return obj instanceof Filter && areSerializedFieldsEqual((Filter) obj); 638 } 639 640 @Override 641 public int hashCode() { 642 return Objects.hash(this.fuzzyKeysData); 643 } 644}