hbase-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From ndimi...@apache.org
Subject git commit: HBASE-12183 FuzzyRowFilter doesn't support reverse scans
Date Fri, 10 Oct 2014 04:24:57 GMT
Repository: hbase
Updated Branches:
  refs/heads/0.98 f97f5a41f -> 386f36db8


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/386f36db
Tree: http://git-wip-us.apache.org/repos/asf/hbase/tree/386f36db
Diff: http://git-wip-us.apache.org/repos/asf/hbase/diff/386f36db

Branch: refs/heads/0.98
Commit: 386f36db8f2211e4c7b375c7b7e05853f09ecc2a
Parents: f97f5a4
Author: Nick Dimiduk <ndimiduk@apache.org>
Authored: Thu Oct 9 14:47:03 2014 -0700
Committer: Nick Dimiduk <ndimiduk@apache.org>
Committed: Thu Oct 9 21:21:16 2014 -0700

----------------------------------------------------------------------
 .../hadoop/hbase/filter/FuzzyRowFilter.java     | 146 ++++++++--
 .../hadoop/hbase/filter/TestFuzzyRowFilter.java | 267 ++++++++++++++++---
 2 files changed, 355 insertions(+), 58 deletions(-)
----------------------------------------------------------------------


http://git-wip-us.apache.org/repos/asf/hbase/blob/386f36db/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 bed32fc..2de6458 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
@@ -17,6 +17,7 @@
  */
 package org.apache.hadoop.hbase.filter;
 
+import com.google.common.annotations.VisibleForTesting;
 import org.apache.hadoop.hbase.util.ByteStringer;
 import com.google.protobuf.InvalidProtocolBufferException;
 
@@ -70,6 +71,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;
   }
 
@@ -84,7 +95,7 @@ public class FuzzyRowFilter extends FilterBase {
     SatisfiesCode bestOption = SatisfiesCode.NO_NEXT;
     for (Pair<byte[], byte[]> fuzzyData : fuzzyKeysData) {
       SatisfiesCode satisfiesCode =
-              satisfies(rowKey, fuzzyData.getFirst(), fuzzyData.getSecond());
+              satisfies(isReversed(), rowKey, fuzzyData.getFirst(), fuzzyData.getSecond());
       if (satisfiesCode == SatisfiesCode.YES) {
         return ReturnCode.INCLUDE;
       }
@@ -112,18 +123,22 @@ 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(rowKey,
+      byte[] nextRowKeyCandidate = getNextForFuzzyRule(isReversed(), rowKey,
               fuzzyData.getFirst(), 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." +
@@ -131,7 +146,7 @@ public class FuzzyRowFilter extends FilterBase {
                                          " currentKV: " + currentKV.toString());
     }
 
-    return KeyValue.createFirstOnRow(nextRowKey);
+    return nextRowKey == null ? null : KeyValue.createFirstOnRow(nextRowKey);
   }
 
   @Override
@@ -195,26 +210,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++) {
@@ -231,7 +253,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
@@ -240,7 +268,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;
       }
     }
@@ -248,19 +276,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:
@@ -272,24 +358,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
@@ -302,13 +396,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();
         }
       }
     }
@@ -317,7 +411,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.
    */
@@ -337,5 +430,4 @@ public class FuzzyRowFilter extends FilterBase {
     }
     return true;
   }
-
 }

http://git-wip-us.apache.org/repos/asf/hbase/blob/386f36db/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 504b670..9f83444 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
@@ -18,6 +18,7 @@
 package org.apache.hadoop.hbase.filter;
 
 import org.apache.hadoop.hbase.SmallTests;
+import org.apache.hadoop.hbase.util.Bytes;
 import org.junit.Assert;
 import org.junit.Test;
 import org.junit.experimental.categories.Category;
@@ -25,150 +26,230 @@ import org.junit.experimental.categories.Category;
 @Category(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},
@@ -193,9 +274,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));
+  }
 }


Mime
View raw message