You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@hbase.apache.org by nd...@apache.org on 2014/10/10 03:29:44 UTC
git commit: HBASE-12183 FuzzyRowFilter doesn't support reverse scans
Repository: hbase
Updated Branches:
refs/heads/master 5420b4c78 -> 712dad814
HBASE-12183 FuzzyRowFilter doesn't support reverse scans
Project: http://git-wip-us.apache.org/repos/asf/hbase/repo
Commit: http://git-wip-us.apache.org/repos/asf/hbase/commit/712dad81
Tree: http://git-wip-us.apache.org/repos/asf/hbase/tree/712dad81
Diff: http://git-wip-us.apache.org/repos/asf/hbase/diff/712dad81
Branch: refs/heads/master
Commit: 712dad814c481a9e377bd3629fbc3c3fda7fbd10
Parents: 5420b4c
Author: Nick Dimiduk <nd...@apache.org>
Authored: Thu Oct 9 14:48:55 2014 -0700
Committer: Nick Dimiduk <nd...@apache.org>
Committed: Thu Oct 9 18:27:22 2014 -0700
----------------------------------------------------------------------
.../hadoop/hbase/filter/FuzzyRowFilter.java | 150 +++++++++--
.../hadoop/hbase/filter/TestFuzzyRowFilter.java | 267 ++++++++++++++++---
2 files changed, 357 insertions(+), 60 deletions(-)
----------------------------------------------------------------------
http://git-wip-us.apache.org/repos/asf/hbase/blob/712dad81/hbase-client/src/main/java/org/apache/hadoop/hbase/filter/FuzzyRowFilter.java
----------------------------------------------------------------------
diff --git a/hbase-client/src/main/java/org/apache/hadoop/hbase/filter/FuzzyRowFilter.java b/hbase-client/src/main/java/org/apache/hadoop/hbase/filter/FuzzyRowFilter.java
index dbfd995..3971330 100644
--- a/hbase-client/src/main/java/org/apache/hadoop/hbase/filter/FuzzyRowFilter.java
+++ b/hbase-client/src/main/java/org/apache/hadoop/hbase/filter/FuzzyRowFilter.java
@@ -21,6 +21,7 @@ import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
+import com.google.common.annotations.VisibleForTesting;
import org.apache.hadoop.hbase.classification.InterfaceAudience;
import org.apache.hadoop.hbase.classification.InterfaceStability;
import org.apache.hadoop.hbase.Cell;
@@ -69,6 +70,16 @@ public class FuzzyRowFilter extends FilterBase {
private boolean done = false;
public FuzzyRowFilter(List<Pair<byte[], byte[]>> fuzzyKeysData) {
+ Pair<byte[], byte[]> p;
+ for (int i = 0; i < fuzzyKeysData.size(); i++) {
+ p = fuzzyKeysData.get(i);
+ if (p.getFirst().length != p.getSecond().length) {
+ Pair<String, String> readable = new Pair<String, String>(
+ Bytes.toStringBinary(p.getFirst()),
+ Bytes.toStringBinary(p.getSecond()));
+ throw new IllegalArgumentException("Fuzzy pair lengths do not match: " + readable);
+ }
+ }
this.fuzzyKeysData = fuzzyKeysData;
}
@@ -78,8 +89,8 @@ public class FuzzyRowFilter extends FilterBase {
// assigning "worst" result first and looking for better options
SatisfiesCode bestOption = SatisfiesCode.NO_NEXT;
for (Pair<byte[], byte[]> fuzzyData : fuzzyKeysData) {
- SatisfiesCode satisfiesCode = satisfies(c.getRowArray(), c.getRowOffset(),
- c.getRowLength(), fuzzyData.getFirst(), fuzzyData.getSecond());
+ SatisfiesCode satisfiesCode = satisfies(isReversed(), c.getRowArray(), c.getRowOffset(),
+ c.getRowLength(), fuzzyData.getFirst(), fuzzyData.getSecond());
if (satisfiesCode == SatisfiesCode.YES) {
return ReturnCode.INCLUDE;
}
@@ -103,26 +114,30 @@ public class FuzzyRowFilter extends FilterBase {
byte[] nextRowKey = null;
// Searching for the "smallest" row key that satisfies at least one fuzzy row key
for (Pair<byte[], byte[]> fuzzyData : fuzzyKeysData) {
- byte[] nextRowKeyCandidate = getNextForFuzzyRule(currentCell.getRowArray(),
+ byte[] nextRowKeyCandidate = getNextForFuzzyRule(isReversed(), currentCell.getRowArray(),
currentCell.getRowOffset(), currentCell.getRowLength(), fuzzyData.getFirst(),
- fuzzyData.getSecond());
+ fuzzyData.getSecond());
if (nextRowKeyCandidate == null) {
continue;
}
- if (nextRowKey == null || Bytes.compareTo(nextRowKeyCandidate, nextRowKey) < 0) {
+ if (nextRowKey == null ||
+ (reversed && Bytes.compareTo(nextRowKeyCandidate, nextRowKey) > 0) ||
+ (!reversed && Bytes.compareTo(nextRowKeyCandidate, nextRowKey) < 0)) {
nextRowKey = nextRowKeyCandidate;
}
}
- if (nextRowKey == null) {
- // SHOULD NEVER happen
+ if (!reversed && nextRowKey == null) {
+ // Should never happen for forward scanners; logic in filterKeyValue should return NO_NEXT.
+ // Can happen in reversed scanner when currentKV is just before the next possible match; in
+ // this case, fall back on scanner simply calling KeyValueHeap.next()
// TODO: is there a better way than throw exception? (stop the scanner?)
throw new IllegalStateException("No next row key that satisfies fuzzy exists when"
+ " getNextKeyHint() is invoked." + " Filter: " + this.toString() + " currentKV: "
+ currentCell);
}
- return KeyValueUtil.createFirstOnRow(nextRowKey);
+ return nextRowKey == null ? null : KeyValueUtil.createFirstOnRow(nextRowKey);
}
@Override
@@ -186,26 +201,33 @@ public class FuzzyRowFilter extends FilterBase {
// Utility methods
static enum SatisfiesCode {
- // row satisfies fuzzy rule
+ /** row satisfies fuzzy rule */
YES,
- // row doesn't satisfy fuzzy rule, but there's possible greater row that does
+ /** row doesn't satisfy fuzzy rule, but there's possible greater row that does */
NEXT_EXISTS,
- // row doesn't satisfy fuzzy rule and there's no greater row that does
+ /** row doesn't satisfy fuzzy rule and there's no greater row that does */
NO_NEXT
}
- static SatisfiesCode satisfies(byte[] row,
- byte[] fuzzyKeyBytes, byte[] fuzzyKeyMeta) {
- return satisfies(row, 0, row.length, fuzzyKeyBytes, fuzzyKeyMeta);
+ @VisibleForTesting
+ static SatisfiesCode satisfies(byte[] row, byte[] fuzzyKeyBytes, byte[] fuzzyKeyMeta) {
+ return satisfies(false, row, 0, row.length, fuzzyKeyBytes, fuzzyKeyMeta);
+ }
+
+ @VisibleForTesting
+ static SatisfiesCode satisfies(boolean reverse, byte[] row, byte[] fuzzyKeyBytes,
+ byte[] fuzzyKeyMeta) {
+ return satisfies(reverse, row, 0, row.length, fuzzyKeyBytes, fuzzyKeyMeta);
}
- private static SatisfiesCode satisfies(byte[] row, int offset, int length,
+ private static SatisfiesCode satisfies(boolean reverse, byte[] row, int offset, int length,
byte[] fuzzyKeyBytes, byte[] fuzzyKeyMeta) {
if (row == null) {
// do nothing, let scan to proceed
return SatisfiesCode.YES;
}
+ Order order = Order.orderFor(reverse);
boolean nextRowKeyCandidateExists = false;
for (int i = 0; i < fuzzyKeyMeta.length && i < length; i++) {
@@ -222,7 +244,13 @@ public class FuzzyRowFilter extends FilterBase {
// this row and which satisfies the fuzzy rule. Otherwise there's no such byte array:
// this row is simply bigger than any byte array that satisfies the fuzzy rule
boolean rowByteLessThanFixed = (row[i + offset] & 0xFF) < (fuzzyKeyBytes[i] & 0xFF);
- return rowByteLessThanFixed ? SatisfiesCode.NEXT_EXISTS : SatisfiesCode.NO_NEXT;
+ if (rowByteLessThanFixed && !reverse) {
+ return SatisfiesCode.NEXT_EXISTS;
+ } else if (!rowByteLessThanFixed && reverse) {
+ return SatisfiesCode.NEXT_EXISTS;
+ } else {
+ return SatisfiesCode.NO_NEXT;
+ }
}
// Second, checking if this position is not fixed and byte value is not the biggest. In this
@@ -231,7 +259,7 @@ public class FuzzyRowFilter extends FilterBase {
// (see the code of getNextForFuzzyRule below) by one.
// Note: if non-fixed byte is already at biggest value, this doesn't allow us to say there's
// bigger one that satisfies the rule as it can't be increased.
- if (fuzzyKeyMeta[i] == 1 && !isMax(fuzzyKeyBytes[i])) {
+ if (fuzzyKeyMeta[i] == 1 && !order.isMax(fuzzyKeyBytes[i])) {
nextRowKeyCandidateExists = true;
}
}
@@ -239,19 +267,77 @@ public class FuzzyRowFilter extends FilterBase {
return SatisfiesCode.YES;
}
- private static boolean isMax(byte fuzzyKeyByte) {
- return (fuzzyKeyByte & 0xFF) == 255;
+ @VisibleForTesting
+ static byte[] getNextForFuzzyRule(byte[] row, byte[] fuzzyKeyBytes, byte[] fuzzyKeyMeta) {
+ return getNextForFuzzyRule(false, row, 0, row.length, fuzzyKeyBytes, fuzzyKeyMeta);
}
- static byte[] getNextForFuzzyRule(byte[] row, byte[] fuzzyKeyBytes, byte[] fuzzyKeyMeta) {
- return getNextForFuzzyRule(row, 0, row.length, fuzzyKeyBytes, fuzzyKeyMeta);
+ @VisibleForTesting
+ static byte[] getNextForFuzzyRule(boolean reverse, byte[] row, byte[] fuzzyKeyBytes,
+ byte[] fuzzyKeyMeta) {
+ return getNextForFuzzyRule(reverse, row, 0, row.length, fuzzyKeyBytes, fuzzyKeyMeta);
+ }
+
+ /** Abstracts directional comparisons based on scan direction. */
+ private enum Order {
+ ASC {
+ public boolean lt(int lhs, int rhs) {
+ return lhs < rhs;
+ }
+ public boolean gt(int lhs, int rhs) {
+ return lhs > rhs;
+ }
+ public byte inc(byte val) {
+ // TODO: what about over/underflow?
+ return (byte) (val + 1);
+ }
+ public boolean isMax(byte val) {
+ return val == (byte) 0xff;
+ }
+ public byte min() {
+ return 0;
+ }
+ },
+ DESC {
+ public boolean lt(int lhs, int rhs) {
+ return lhs > rhs;
+ }
+ public boolean gt(int lhs, int rhs) {
+ return lhs < rhs;
+ }
+ public byte inc(byte val) {
+ // TODO: what about over/underflow?
+ return (byte) (val - 1);
+ }
+ public boolean isMax(byte val) {
+ return val == 0;
+ }
+ public byte min() {
+ return (byte) 0xFF;
+ }
+ };
+
+ public static Order orderFor(boolean reverse) {
+ return reverse ? DESC : ASC;
+ }
+
+ /** Returns true when {@code lhs < rhs}. */
+ public abstract boolean lt(int lhs, int rhs);
+ /** Returns true when {@code lhs > rhs}. */
+ public abstract boolean gt(int lhs, int rhs);
+ /** Returns {@code val} incremented by 1. */
+ public abstract byte inc(byte val);
+ /** Return true when {@code val} is the maximum value */
+ public abstract boolean isMax(byte val);
+ /** Return the minimum value according to this ordering scheme. */
+ public abstract byte min();
}
/**
* @return greater byte array than given (row) which satisfies the fuzzy rule if it exists,
* null otherwise
*/
- private static byte[] getNextForFuzzyRule(byte[] row, int offset, int length,
+ private static byte[] getNextForFuzzyRule(boolean reverse, byte[] row, int offset, int length,
byte[] fuzzyKeyBytes, byte[] fuzzyKeyMeta) {
// To find out the next "smallest" byte array that satisfies fuzzy rule and "greater" than
// the given one we do the following:
@@ -263,24 +349,32 @@ public class FuzzyRowFilter extends FilterBase {
// values than otherwise.
byte[] result = Arrays.copyOf(fuzzyKeyBytes,
length > fuzzyKeyBytes.length ? length : fuzzyKeyBytes.length);
+ if (reverse && length > fuzzyKeyBytes.length) {
+ // we need trailing 0xff's instead of trailing 0x00's
+ for (int i = fuzzyKeyBytes.length; i < result.length; i++) {
+ result[i] = (byte) 0xFF;
+ }
+ }
int toInc = -1;
+ final Order order = Order.orderFor(reverse);
boolean increased = false;
for (int i = 0; i < result.length; i++) {
if (i >= fuzzyKeyMeta.length || fuzzyKeyMeta[i] == 1) {
result[i] = row[offset + i];
- if (!isMax(row[i])) {
+ if (!order.isMax(row[i])) {
// this is "non-fixed" position and is not at max value, hence we can increase it
toInc = i;
}
} else if (i < fuzzyKeyMeta.length && fuzzyKeyMeta[i] == 0) {
- if ((row[i + offset] & 0xFF) < (fuzzyKeyBytes[i] & 0xFF)) {
+ if (order.lt((row[i + offset] & 0xFF), (fuzzyKeyBytes[i] & 0xFF))) {
// if setting value for any fixed position increased the original array,
// we are OK
increased = true;
break;
}
- if ((row[i + offset] & 0xFF) > (fuzzyKeyBytes[i] & 0xFF)) {
+
+ if (order.gt((row[i + offset] & 0xFF), (fuzzyKeyBytes[i] & 0xFF))) {
// if setting value for any fixed position makes array "smaller", then just stop:
// in case we found some non-fixed position to increase we will do it, otherwise
// there's no "next" row key that satisfies fuzzy rule and "greater" than given row
@@ -293,13 +387,13 @@ public class FuzzyRowFilter extends FilterBase {
if (toInc < 0) {
return null;
}
- result[toInc]++;
+ result[toInc] = order.inc(result[toInc]);
// Setting all "non-fixed" positions to zeroes to the right of the one we increased so
// that found "next" row key is the smallest possible
for (int i = toInc + 1; i < result.length; i++) {
if (i >= fuzzyKeyMeta.length || fuzzyKeyMeta[i] == 1) {
- result[i] = 0;
+ result[i] = order.min();
}
}
}
@@ -308,7 +402,6 @@ public class FuzzyRowFilter extends FilterBase {
}
/**
- * @param other
* @return true if and only if the fields of the filter that are serialized
* are equal to the corresponding fields in other. Used for testing.
*/
@@ -328,5 +421,4 @@ public class FuzzyRowFilter extends FilterBase {
}
return true;
}
-
}
http://git-wip-us.apache.org/repos/asf/hbase/blob/712dad81/hbase-server/src/test/java/org/apache/hadoop/hbase/filter/TestFuzzyRowFilter.java
----------------------------------------------------------------------
diff --git a/hbase-server/src/test/java/org/apache/hadoop/hbase/filter/TestFuzzyRowFilter.java b/hbase-server/src/test/java/org/apache/hadoop/hbase/filter/TestFuzzyRowFilter.java
index 4eb53bb..3ec1351 100644
--- a/hbase-server/src/test/java/org/apache/hadoop/hbase/filter/TestFuzzyRowFilter.java
+++ b/hbase-server/src/test/java/org/apache/hadoop/hbase/filter/TestFuzzyRowFilter.java
@@ -19,6 +19,7 @@ package org.apache.hadoop.hbase.filter;
import org.apache.hadoop.hbase.testclassification.FilterTests;
import org.apache.hadoop.hbase.testclassification.SmallTests;
+import org.apache.hadoop.hbase.util.Bytes;
import org.junit.Assert;
import org.junit.Test;
import org.junit.experimental.categories.Category;
@@ -26,150 +27,230 @@ import org.junit.experimental.categories.Category;
@Category({FilterTests.class, SmallTests.class})
public class TestFuzzyRowFilter {
@Test
- public void testSatisfies() {
+ public void testSatisfiesForward() {
Assert.assertEquals(FuzzyRowFilter.SatisfiesCode.NEXT_EXISTS,
- FuzzyRowFilter.satisfies(new byte[]{1, (byte) -128, 0, 0, 1}, // row to check
+ FuzzyRowFilter.satisfies(false,
+ new byte[]{1, (byte) -128, 0, 0, 1}, // row to check
new byte[]{1, 0, 1}, // fuzzy row
new byte[]{0, 1, 0})); // mask
Assert.assertEquals(FuzzyRowFilter.SatisfiesCode.YES,
- FuzzyRowFilter.satisfies(new byte[]{1, (byte) -128, 1, 0, 1},
+ FuzzyRowFilter.satisfies(false,
+ new byte[]{1, (byte) -128, 1, 0, 1},
new byte[]{1, 0, 1},
new byte[]{0, 1, 0}));
Assert.assertEquals(FuzzyRowFilter.SatisfiesCode.NEXT_EXISTS,
- FuzzyRowFilter.satisfies(new byte[]{1, (byte) -128, 2, 0, 1},
+ FuzzyRowFilter.satisfies(false,
+ new byte[]{1, (byte) -128, 2, 0, 1},
new byte[]{1, 0, 1},
new byte[]{0, 1, 0}));
Assert.assertEquals(FuzzyRowFilter.SatisfiesCode.NO_NEXT,
- FuzzyRowFilter.satisfies(new byte[]{2, 3, 1, 1, 1},
+ FuzzyRowFilter.satisfies(false,
+ new byte[]{2, 3, 1, 1, 1},
new byte[]{1, 0, 1},
new byte[]{0, 1, 0}));
Assert.assertEquals(FuzzyRowFilter.SatisfiesCode.YES,
- FuzzyRowFilter.satisfies(new byte[]{1, 2, 1, 3, 3},
+ FuzzyRowFilter.satisfies(false,
+ new byte[]{1, 2, 1, 3, 3},
new byte[]{1, 2, 0, 3},
new byte[]{0, 0, 1, 0}));
Assert.assertEquals(FuzzyRowFilter.SatisfiesCode.NEXT_EXISTS,
- FuzzyRowFilter.satisfies(new byte[]{1, 1, 1, 3, 0}, // row to check
+ FuzzyRowFilter.satisfies(false,
+ new byte[]{1, 1, 1, 3, 0}, // row to check
new byte[]{1, 2, 0, 3}, // fuzzy row
new byte[]{0, 0, 1, 0})); // mask
Assert.assertEquals(FuzzyRowFilter.SatisfiesCode.NEXT_EXISTS,
- FuzzyRowFilter.satisfies(new byte[]{1, 1, 1, 3, 0},
+ FuzzyRowFilter.satisfies(false,
+ new byte[]{1, 1, 1, 3, 0},
new byte[]{1, (byte) 245, 0, 3},
new byte[]{0, 0, 1, 0}));
Assert.assertEquals(FuzzyRowFilter.SatisfiesCode.NO_NEXT,
- FuzzyRowFilter.satisfies(new byte[]{1, (byte) 245, 1, 3, 0},
+ FuzzyRowFilter.satisfies(false,
+ new byte[]{1, (byte) 245, 1, 3, 0},
new byte[]{1, 1, 0, 3},
new byte[]{0, 0, 1, 0}));
Assert.assertEquals(FuzzyRowFilter.SatisfiesCode.NO_NEXT,
- FuzzyRowFilter.satisfies(new byte[]{1, 3, 1, 3, 0},
+ FuzzyRowFilter.satisfies(false,
+ new byte[]{1, 3, 1, 3, 0},
new byte[]{1, 2, 0, 3},
new byte[]{0, 0, 1, 0}));
Assert.assertEquals(FuzzyRowFilter.SatisfiesCode.NO_NEXT,
- FuzzyRowFilter.satisfies(new byte[]{2, 1, 1, 1, 0},
+ FuzzyRowFilter.satisfies(false,
+ new byte[]{2, 1, 1, 1, 0},
new byte[]{1, 2, 0, 3},
new byte[]{0, 0, 1, 0}));
Assert.assertEquals(FuzzyRowFilter.SatisfiesCode.NEXT_EXISTS,
- FuzzyRowFilter.satisfies(new byte[]{1, 2, 1, 0, 1},
+ FuzzyRowFilter.satisfies(false,
+ new byte[]{1, 2, 1, 0, 1},
new byte[]{0, 1, 2},
new byte[]{1, 0, 0}));
}
@Test
- public void testGetNextForFuzzyRule() {
- assertNext(
+ public void testSatisfiesReverse() {
+ Assert.assertEquals(FuzzyRowFilter.SatisfiesCode.NO_NEXT,
+ FuzzyRowFilter.satisfies(true,
+ new byte[]{1, (byte) -128, 0, 0, 1}, // row to check
+ new byte[]{1, 0, 1}, // fuzzy row
+ new byte[]{0, 1, 0})); // mask
+
+ Assert.assertEquals(FuzzyRowFilter.SatisfiesCode.YES,
+ FuzzyRowFilter.satisfies(true,
+ new byte[]{1, (byte) -128, 1, 0, 1},
+ new byte[]{1, 0, 1},
+ new byte[]{0, 1, 0}));
+
+ Assert.assertEquals(FuzzyRowFilter.SatisfiesCode.NEXT_EXISTS,
+ FuzzyRowFilter.satisfies(true,
+ new byte[]{1, (byte) -128, 2, 0, 1},
+ new byte[]{1, 0, 1},
+ new byte[]{0, 1, 0}));
+
+ Assert.assertEquals(FuzzyRowFilter.SatisfiesCode.NEXT_EXISTS,
+ FuzzyRowFilter.satisfies(true,
+ new byte[]{2, 3, 1, 1, 1},
+ new byte[]{1, 0, 1},
+ new byte[]{0, 1, 0}));
+
+ Assert.assertEquals(FuzzyRowFilter.SatisfiesCode.YES,
+ FuzzyRowFilter.satisfies(true,
+ new byte[]{1, 2, 1, 3, 3},
+ new byte[]{1, 2, 0, 3},
+ new byte[]{0, 0, 1, 0}));
+
+ Assert.assertEquals(FuzzyRowFilter.SatisfiesCode.NO_NEXT,
+ FuzzyRowFilter.satisfies(true,
+ new byte[]{1, 1, 1, 3, 0}, // row to check
+ new byte[]{1, 2, 0, 3}, // fuzzy row
+ new byte[]{0, 0, 1, 0})); // mask
+
+ Assert.assertEquals(FuzzyRowFilter.SatisfiesCode.NO_NEXT,
+ FuzzyRowFilter.satisfies(true,
+ new byte[]{1, 1, 1, 3, 0},
+ new byte[]{1, (byte) 245, 0, 3},
+ new byte[]{0, 0, 1, 0}));
+
+ Assert.assertEquals(FuzzyRowFilter.SatisfiesCode.NEXT_EXISTS,
+ FuzzyRowFilter.satisfies(true,
+ new byte[]{1, (byte) 245, 1, 3, 0},
+ new byte[]{1, 1, 0, 3},
+ new byte[]{0, 0, 1, 0}));
+
+ Assert.assertEquals(FuzzyRowFilter.SatisfiesCode.NEXT_EXISTS,
+ FuzzyRowFilter.satisfies(true,
+ new byte[]{1, 3, 1, 3, 0},
+ new byte[]{1, 2, 0, 3},
+ new byte[]{0, 0, 1, 0}));
+
+ Assert.assertEquals(FuzzyRowFilter.SatisfiesCode.NEXT_EXISTS,
+ FuzzyRowFilter.satisfies(true,
+ new byte[]{2, 1, 1, 1, 0},
+ new byte[]{1, 2, 0, 3},
+ new byte[]{0, 0, 1, 0}));
+
+ Assert.assertEquals(FuzzyRowFilter.SatisfiesCode.NEXT_EXISTS,
+ FuzzyRowFilter.satisfies(true,
+ new byte[]{1, 2, 1, 0, 1},
+ new byte[]{0, 1, 2},
+ new byte[]{1, 0, 0}));
+ }
+
+ @Test
+ public void testGetNextForFuzzyRuleForward() {
+ assertNext(false,
new byte[]{0, 1, 2}, // fuzzy row
new byte[]{1, 0, 0}, // mask
new byte[]{1, 2, 1, 0, 1}, // current
new byte[]{2, 1, 2, 0, 0}); // expected next
- assertNext(
+ assertNext(false,
new byte[]{0, 1, 2}, // fuzzy row
new byte[]{1, 0, 0}, // mask
new byte[]{1, 1, 2, 0, 1}, // current
new byte[]{1, 1, 2, 0, 2}); // expected next
- assertNext(
+ assertNext(false,
new byte[]{0, 1, 0, 2, 0}, // fuzzy row
new byte[]{1, 0, 1, 0, 1}, // mask
new byte[]{1, 0, 2, 0, 1}, // current
new byte[]{1, 1, 0, 2, 0}); // expected next
- assertNext(
+ assertNext(false,
new byte[]{1, 0, 1},
new byte[]{0, 1, 0},
new byte[]{1, (byte) 128, 2, 0, 1},
new byte[]{1, (byte) 129, 1, 0, 0});
- assertNext(
+ assertNext(false,
new byte[]{0, 1, 0, 1},
new byte[]{1, 0, 1, 0},
new byte[]{5, 1, 0, 1},
new byte[]{5, 1, 1, 1});
- assertNext(
+ assertNext(false,
new byte[]{0, 1, 0, 1},
new byte[]{1, 0, 1, 0},
new byte[]{5, 1, 0, 1, 1},
new byte[]{5, 1, 0, 1, 2});
- assertNext(
+ assertNext(false,
new byte[]{0, 1, 0, 0}, // fuzzy row
new byte[]{1, 0, 1, 1}, // mask
new byte[]{5, 1, (byte) 255, 1}, // current
new byte[]{5, 1, (byte) 255, 2}); // expected next
- assertNext(
+ assertNext(false,
new byte[]{0, 1, 0, 1}, // fuzzy row
new byte[]{1, 0, 1, 0}, // mask
new byte[]{5, 1, (byte) 255, 1}, // current
new byte[]{6, 1, 0, 1}); // expected next
- assertNext(
+ assertNext(false,
new byte[]{0, 1, 0, 1}, // fuzzy row
new byte[]{1, 0, 1, 0}, // mask
new byte[]{5, 1, (byte) 255, 0}, // current
new byte[]{5, 1, (byte) 255, 1}); // expected next
- assertNext(
+ assertNext(false,
new byte[]{5, 1, 1, 0},
new byte[]{0, 0, 1, 1},
new byte[]{5, 1, (byte) 255, 1},
new byte[]{5, 1, (byte) 255, 2});
- assertNext(
+ assertNext(false,
new byte[]{1, 1, 1, 1},
new byte[]{0, 0, 1, 1},
new byte[]{1, 1, 2, 2},
new byte[]{1, 1, 2, 3});
- assertNext(
+ assertNext(false,
new byte[]{1, 1, 1, 1},
new byte[]{0, 0, 1, 1},
new byte[]{1, 1, 3, 2},
new byte[]{1, 1, 3, 3});
- assertNext(
+ assertNext(false,
new byte[]{1, 1, 1, 1},
new byte[]{1, 1, 1, 1},
new byte[]{1, 1, 2, 3},
new byte[]{1, 1, 2, 4});
- assertNext(
+ assertNext(false,
new byte[]{1, 1, 1, 1},
new byte[]{1, 1, 1, 1},
new byte[]{1, 1, 3, 2},
new byte[]{1, 1, 3, 3});
- assertNext(
+ assertNext(false,
new byte[]{1, 1, 0, 0},
new byte[]{0, 0, 1, 1},
new byte[]{0, 1, 3, 2},
@@ -194,9 +275,133 @@ public class TestFuzzyRowFilter {
new byte[]{0, 0, 1, 0}));
}
- private void assertNext(byte[] fuzzyRow, byte[] mask, byte[] current, byte[] expected) {
- byte[] nextForFuzzyRule = FuzzyRowFilter.getNextForFuzzyRule(current, fuzzyRow, mask);
- Assert.assertArrayEquals(expected, nextForFuzzyRule);
+ @Test
+ public void testGetNextForFuzzyRuleReverse() {
+ assertNext(true,
+ new byte[]{0, 1, 2}, // fuzzy row
+ new byte[]{1, 0, 0}, // mask
+ new byte[]{1, 2, 1, 0, 1}, // current
+ // TODO: should be {1, 1, 3} ?
+ new byte[]{1, 1, 2, (byte) 0xFF, (byte) 0xFF}); // expected next
+
+ assertNext(true,
+ new byte[]{0, 1, 0, 2, 0}, // fuzzy row
+ new byte[]{1, 0, 1, 0, 1}, // mask
+ new byte[]{1, 2, 1, 3, 1}, // current
+ // TODO: should be {1, 1, 1, 3} ?
+ new byte[]{1, 1, 0, 2, 0}); // expected next
+
+ assertNext(true,
+ new byte[]{1, 0, 1},
+ new byte[]{0, 1, 0},
+ new byte[]{1, (byte) 128, 2, 0, 1},
+ // TODO: should be {1, (byte) 128, 2} ?
+ new byte[]{1, (byte) 128, 1, (byte) 0xFF, (byte) 0xFF});
+
+ assertNext(true,
+ new byte[]{0, 1, 0, 1},
+ new byte[]{1, 0, 1, 0},
+ new byte[]{5, 1, 0, 2, 1},
+ // TODO: should be {5, 1, 0, 2} ?
+ new byte[]{5, 1, 0, 1, (byte) 0xFF});
+
+ assertNext(true,
+ new byte[]{0, 1, 0, 0}, // fuzzy row
+ new byte[]{1, 0, 1, 1}, // mask
+ new byte[]{5, 1, (byte) 255, 1}, // current
+ new byte[]{5, 1, (byte) 255, 0}); // expected next
+
+ assertNext(true,
+ new byte[]{0, 1, 0, 1}, // fuzzy row
+ new byte[]{1, 0, 1, 0}, // mask
+ new byte[]{5, 1, 0, 1}, // current
+ new byte[]{4, 1, (byte) 255, 1}); // expected next
+
+ assertNext(true,
+ new byte[]{0, 1, 0, 1}, // fuzzy row
+ new byte[]{1, 0, 1, 0}, // mask
+ new byte[]{5, 1, (byte) 255, 0}, // current
+ new byte[]{5, 1, (byte) 254, 1}); // expected next
+
+ assertNext(true,
+ new byte[]{1, 1, 0, 0},
+ new byte[]{0, 0, 1, 1},
+ new byte[]{2, 1, 3, 2},
+ // TODO: should be {1, 0} ?
+ new byte[]{1, 1, 0, 0});
+
+ assertNext(true,
+ new byte[]{1, 0, 1}, // fuzzy row
+ new byte[]{0, 1, 0}, // mask
+ new byte[]{2, 3, 1, 1, 1}, // row to check
+ // TODO: should be {1, (byte) 0xFF, 2} ?
+ new byte[]{1, 0, 1, (byte) 0xFF, (byte) 0xFF});
+
+ assertNext(true,
+ new byte[]{1, 1, 0, 3},
+ new byte[]{0, 0, 1, 0},
+ new byte[]{1, (byte) 245, 1, 3, 0},
+ // TODO: should be {1, 1, (byte) 255, 4} ?
+ new byte[]{1, 1, 0, 3, (byte) 0xFF});
+
+ assertNext(true,
+ new byte[]{1, 2, 0, 3},
+ new byte[]{0, 0, 1, 0},
+ new byte[]{1, 3, 1, 3, 0},
+ // TODO: should be 1, 2, (byte) 255, 4 ?
+ new byte[]{1, 2, 0, 3, (byte) 0xFF});
+
+ assertNext(true,
+ new byte[]{1, 2, 0, 3},
+ new byte[]{0, 0, 1, 0},
+ new byte[]{2, 1, 1, 1, 0},
+ // TODO: should be {1, 2, (byte) 255, 4} ?
+ new byte[]{1, 2, 0, 3, (byte) 0xFF});
+
+ assertNext(true,
+ // TODO: should be null?
+ new byte[]{1, 0, 1},
+ new byte[]{0, 1, 0},
+ new byte[]{1, (byte) 128, 2},
+ new byte[]{1, (byte) 128, 1});
+
+ assertNext(true,
+ // TODO: should be null?
+ new byte[]{0, 1, 0, 1},
+ new byte[]{1, 0, 1, 0},
+ new byte[]{5, 1, 0, 2},
+ new byte[]{5, 1, 0, 1});
+
+ assertNext(true,
+ // TODO: should be null?
+ new byte[]{5, 1, 1, 0},
+ new byte[]{0, 0, 1, 1},
+ new byte[]{5, 1, (byte) 0xFF, 1},
+ new byte[]{5, 1, (byte) 0xFF, 0});
+
+ assertNext(true,
+ // TODO: should be null?
+ new byte[]{1, 1, 1, 1},
+ new byte[]{0, 0, 1, 1},
+ new byte[]{1, 1, 2, 2},
+ new byte[]{1, 1, 2, 1});
+
+ assertNext(true,
+ // TODO: should be null?
+ new byte[]{1, 1, 1, 1},
+ new byte[]{1, 1, 1, 1},
+ new byte[]{1, 1, 2, 3},
+ new byte[]{1, 1, 2, 2});
+
+ Assert.assertNull(FuzzyRowFilter.getNextForFuzzyRule(true,
+ new byte[]{1, 1, 1, 3, 0},
+ new byte[]{1, 2, 0, 3},
+ new byte[]{0, 0, 1, 0}));
}
+ private static void assertNext(boolean reverse, byte[] fuzzyRow, byte[] mask, byte[] current,
+ byte[] expected) {
+ byte[] nextForFuzzyRule = FuzzyRowFilter.getNextForFuzzyRule(reverse, current, fuzzyRow, mask);
+ Assert.assertEquals(Bytes.toStringBinary(expected), Bytes.toStringBinary(nextForFuzzyRule));
+ }
}