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 org.apache.hadoop.hbase.HBaseClassTestRule;
021import org.apache.hadoop.hbase.KeyValue;
022import org.apache.hadoop.hbase.KeyValueUtil;
023import org.apache.hadoop.hbase.testclassification.FilterTests;
024import org.apache.hadoop.hbase.testclassification.SmallTests;
025import org.apache.hadoop.hbase.util.Bytes;
026import org.junit.Assert;
027import org.junit.ClassRule;
028import org.junit.Test;
029import org.junit.experimental.categories.Category;
030
031@Category({ FilterTests.class, SmallTests.class })
032public class TestFuzzyRowFilter {
033
034  @ClassRule
035  public static final HBaseClassTestRule CLASS_RULE =
036    HBaseClassTestRule.forClass(TestFuzzyRowFilter.class);
037
038  @Test
039  public void testSatisfiesNoUnsafeForward() {
040
041    Assert.assertEquals(FuzzyRowFilter.SatisfiesCode.YES,
042      FuzzyRowFilter.satisfiesNoUnsafe(false, new byte[] { 1, (byte) -128, 1, 0, 1 }, 0, 5,
043        new byte[] { 1, 0, 1 }, new byte[] { 0, 1, 0 }));
044
045    Assert.assertEquals(FuzzyRowFilter.SatisfiesCode.NEXT_EXISTS,
046      FuzzyRowFilter.satisfiesNoUnsafe(false, new byte[] { 1, (byte) -128, 2, 0, 1 }, 0, 5,
047        new byte[] { 1, 0, 1 }, new byte[] { 0, 1, 0 }));
048
049    Assert.assertEquals(FuzzyRowFilter.SatisfiesCode.YES, FuzzyRowFilter.satisfiesNoUnsafe(false,
050      new byte[] { 1, 2, 1, 3, 3 }, 0, 5, new byte[] { 1, 2, 0, 3 }, new byte[] { 0, 0, 1, 0 }));
051
052    Assert.assertEquals(FuzzyRowFilter.SatisfiesCode.NEXT_EXISTS,
053      FuzzyRowFilter.satisfiesNoUnsafe(false, new byte[] { 1, 1, 1, 3, 0 }, // row to check
054        0, 5, new byte[] { 1, 2, 0, 3 }, // fuzzy row
055        new byte[] { 0, 0, 1, 0 })); // mask
056
057    Assert.assertEquals(FuzzyRowFilter.SatisfiesCode.NEXT_EXISTS,
058      FuzzyRowFilter.satisfiesNoUnsafe(false, new byte[] { 1, 1, 1, 3, 0 }, 0, 5,
059        new byte[] { 1, (byte) 245, 0, 3 }, new byte[] { 0, 0, 1, 0 }));
060
061    Assert.assertEquals(FuzzyRowFilter.SatisfiesCode.NEXT_EXISTS, FuzzyRowFilter.satisfiesNoUnsafe(
062      false, new byte[] { 1, 2, 1, 0, 1 }, 0, 5, new byte[] { 0, 1, 2 }, new byte[] { 1, 0, 0 }));
063  }
064
065  @Test
066  public void testSatisfiesForward() {
067
068    Assert.assertEquals(FuzzyRowFilter.SatisfiesCode.YES, FuzzyRowFilter.satisfies(false,
069      new byte[] { 1, (byte) -128, 1, 0, 1 }, new byte[] { 1, 0, 1 }, new byte[] { -1, 0, -1 }));
070
071    Assert.assertEquals(FuzzyRowFilter.SatisfiesCode.NEXT_EXISTS, FuzzyRowFilter.satisfies(false,
072      new byte[] { 1, (byte) -128, 2, 0, 1 }, new byte[] { 1, 0, 1 }, new byte[] { -1, 0, -1 }));
073
074    Assert.assertEquals(FuzzyRowFilter.SatisfiesCode.YES, FuzzyRowFilter.satisfies(false,
075      new byte[] { 1, 2, 1, 3, 3 }, new byte[] { 1, 2, 0, 3 }, new byte[] { -1, -1, 0, -1 }));
076
077    Assert.assertEquals(FuzzyRowFilter.SatisfiesCode.NEXT_EXISTS,
078      FuzzyRowFilter.satisfies(false, new byte[] { 1, 1, 1, 3, 0 }, // row to check
079        new byte[] { 1, 2, 0, 3 }, // fuzzy row
080        new byte[] { -1, -1, 0, -1 })); // mask
081
082    Assert.assertEquals(FuzzyRowFilter.SatisfiesCode.NEXT_EXISTS,
083      FuzzyRowFilter.satisfies(false, new byte[] { 1, 1, 1, 3, 0 },
084        new byte[] { 1, (byte) 245, 0, 3 }, new byte[] { -1, -1, 0, -1 }));
085
086    Assert.assertEquals(FuzzyRowFilter.SatisfiesCode.NEXT_EXISTS, FuzzyRowFilter.satisfies(false,
087      new byte[] { 1, 2, 1, 0, 1 }, new byte[] { 0, 1, 2 }, new byte[] { 0, -1, -1 }));
088  }
089
090  @Test
091  public void testSatisfiesReverse() {
092    Assert.assertEquals(FuzzyRowFilter.SatisfiesCode.YES, FuzzyRowFilter.satisfies(true,
093      new byte[] { 1, (byte) -128, 1, 0, 1 }, new byte[] { 1, 0, 1 }, new byte[] { -1, 0, -1 }));
094
095    Assert.assertEquals(FuzzyRowFilter.SatisfiesCode.NEXT_EXISTS, FuzzyRowFilter.satisfies(true,
096      new byte[] { 1, (byte) -128, 2, 0, 1 }, new byte[] { 1, 0, 1 }, new byte[] { -1, 0, -1 }));
097
098    Assert.assertEquals(FuzzyRowFilter.SatisfiesCode.NEXT_EXISTS, FuzzyRowFilter.satisfies(true,
099      new byte[] { 2, 3, 1, 1, 1 }, new byte[] { 1, 0, 1 }, new byte[] { -1, 0, -1 }));
100
101    Assert.assertEquals(FuzzyRowFilter.SatisfiesCode.YES, FuzzyRowFilter.satisfies(true,
102      new byte[] { 1, 2, 1, 3, 3 }, new byte[] { 1, 2, 0, 3 }, new byte[] { -1, -1, 0, -1 }));
103
104    Assert.assertEquals(FuzzyRowFilter.SatisfiesCode.NEXT_EXISTS,
105      FuzzyRowFilter.satisfies(true, new byte[] { 1, (byte) 245, 1, 3, 0 },
106        new byte[] { 1, 1, 0, 3 }, new byte[] { -1, -1, 0, -1 }));
107
108    Assert.assertEquals(FuzzyRowFilter.SatisfiesCode.NEXT_EXISTS, FuzzyRowFilter.satisfies(true,
109      new byte[] { 1, 3, 1, 3, 0 }, new byte[] { 1, 2, 0, 3 }, new byte[] { -1, -1, 0, -1 }));
110
111    Assert.assertEquals(FuzzyRowFilter.SatisfiesCode.NEXT_EXISTS, FuzzyRowFilter.satisfies(true,
112      new byte[] { 2, 1, 1, 1, 0 }, new byte[] { 1, 2, 0, 3 }, new byte[] { -1, -1, 0, -1 }));
113
114    Assert.assertEquals(FuzzyRowFilter.SatisfiesCode.NEXT_EXISTS, FuzzyRowFilter.satisfies(true,
115      new byte[] { 1, 2, 1, 0, 1 }, new byte[] { 0, 1, 2 }, new byte[] { 0, -1, -1 }));
116  }
117
118  @Test
119  public void testSatisfiesNoUnsafeReverse() {
120    Assert.assertEquals(FuzzyRowFilter.SatisfiesCode.YES,
121      FuzzyRowFilter.satisfiesNoUnsafe(true, new byte[] { 1, (byte) -128, 1, 0, 1 }, 0, 5,
122        new byte[] { 1, 0, 1 }, new byte[] { 0, 1, 0 }));
123
124    Assert.assertEquals(FuzzyRowFilter.SatisfiesCode.NEXT_EXISTS,
125      FuzzyRowFilter.satisfiesNoUnsafe(true, new byte[] { 1, (byte) -128, 2, 0, 1 }, 0, 5,
126        new byte[] { 1, 0, 1 }, new byte[] { 0, 1, 0 }));
127
128    Assert.assertEquals(FuzzyRowFilter.SatisfiesCode.NEXT_EXISTS, FuzzyRowFilter.satisfiesNoUnsafe(
129      true, new byte[] { 2, 3, 1, 1, 1 }, 0, 5, new byte[] { 1, 0, 1 }, new byte[] { 0, 1, 0 }));
130
131    Assert.assertEquals(FuzzyRowFilter.SatisfiesCode.YES, FuzzyRowFilter.satisfiesNoUnsafe(true,
132      new byte[] { 1, 2, 1, 3, 3 }, 0, 5, new byte[] { 1, 2, 0, 3 }, new byte[] { 0, 0, 1, 0 }));
133
134    Assert.assertEquals(FuzzyRowFilter.SatisfiesCode.NEXT_EXISTS,
135      FuzzyRowFilter.satisfiesNoUnsafe(true, new byte[] { 1, (byte) 245, 1, 3, 0 }, 0, 5,
136        new byte[] { 1, 1, 0, 3 }, new byte[] { 0, 0, 1, 0 }));
137
138    Assert.assertEquals(FuzzyRowFilter.SatisfiesCode.NEXT_EXISTS,
139      FuzzyRowFilter.satisfiesNoUnsafe(true, new byte[] { 1, 3, 1, 3, 0 }, 0, 5,
140        new byte[] { 1, 2, 0, 3 }, new byte[] { 0, 0, 1, 0 }));
141
142    Assert.assertEquals(FuzzyRowFilter.SatisfiesCode.NEXT_EXISTS,
143      FuzzyRowFilter.satisfiesNoUnsafe(true, new byte[] { 2, 1, 1, 1, 0 }, 0, 5,
144        new byte[] { 1, 2, 0, 3 }, new byte[] { 0, 0, 1, 0 }));
145
146    Assert.assertEquals(FuzzyRowFilter.SatisfiesCode.NEXT_EXISTS, FuzzyRowFilter.satisfiesNoUnsafe(
147      true, new byte[] { 1, 2, 1, 0, 1 }, 0, 5, new byte[] { 0, 1, 2 }, new byte[] { 1, 0, 0 }));
148  }
149
150  @Test
151  public void testGetNextForFuzzyRuleForward() {
152    assertNext(false, new byte[] { 0, 1, 2 }, // fuzzy row
153      new byte[] { 0, -1, -1 }, // mask
154      new byte[] { 1, 2, 1, 0, 1 }, // current
155      new byte[] { 2, 1, 2 }); // expected next
156
157    assertNext(false, new byte[] { 0, 1, 2 }, // fuzzy row
158      new byte[] { 0, -1, -1 }, // mask
159      new byte[] { 1, 1, 2, 0, 1 }, // current
160      new byte[] { 1, 1, 2, 0, 2 }); // expected next
161
162    assertNext(false, new byte[] { 0, 1, 0, 2, 0 }, // fuzzy row
163      new byte[] { 0, -1, 0, -1, 0 }, // mask
164      new byte[] { 1, 0, 2, 0, 1 }, // current
165      new byte[] { 1, 1, 0, 2 }); // expected next
166
167    assertNext(false, new byte[] { 1, 0, 1 }, new byte[] { -1, 0, -1 },
168      new byte[] { 1, (byte) 128, 2, 0, 1 }, new byte[] { 1, (byte) 129, 1 });
169
170    assertNext(false, new byte[] { 0, 1, 0, 1 }, new byte[] { 0, -1, 0, -1 },
171      new byte[] { 5, 1, 0, 1 }, new byte[] { 5, 1, 1, 1 });
172
173    assertNext(false, new byte[] { 0, 1, 0, 1 }, new byte[] { 0, -1, 0, -1 },
174      new byte[] { 5, 1, 0, 1, 1 }, new byte[] { 5, 1, 0, 1, 2 });
175
176    assertNext(false, new byte[] { 0, 1, 0, 0 }, // fuzzy row
177      new byte[] { 0, -1, 0, 0 }, // mask
178      new byte[] { 5, 1, (byte) 255, 1 }, // current
179      new byte[] { 5, 1, (byte) 255, 2 }); // expected next
180
181    assertNext(false, new byte[] { 0, 1, 0, 1 }, // fuzzy row
182      new byte[] { 0, -1, 0, -1 }, // mask
183      new byte[] { 5, 1, (byte) 255, 1 }, // current
184      new byte[] { 6, 1, 0, 1 }); // expected next
185
186    assertNext(false, new byte[] { 0, 1, 0, 1 }, // fuzzy row
187      new byte[] { 0, -1, 0, -1 }, // mask
188      new byte[] { 5, 1, (byte) 255, 0 }, // current
189      new byte[] { 5, 1, (byte) 255, 1 }); // expected next
190
191    assertNext(false, new byte[] { 5, 1, 1, 0 }, new byte[] { -1, -1, 0, 0 },
192      new byte[] { 5, 1, (byte) 255, 1 }, new byte[] { 5, 1, (byte) 255, 2 });
193
194    assertNext(false, new byte[] { 1, 1, 1, 1 }, new byte[] { -1, -1, 0, 0 },
195      new byte[] { 1, 1, 2, 2 }, new byte[] { 1, 1, 2, 3 });
196
197    assertNext(false, new byte[] { 1, 1, 1, 1 }, new byte[] { -1, -1, 0, 0 },
198      new byte[] { 1, 1, 3, 2 }, new byte[] { 1, 1, 3, 3 });
199
200    assertNext(false, new byte[] { 1, 1, 1, 1 }, new byte[] { 0, 0, 0, 0 },
201      new byte[] { 1, 1, 2, 3 }, new byte[] { 1, 1, 2, 4 });
202
203    assertNext(false, new byte[] { 1, 1, 1, 1 }, new byte[] { 0, 0, 0, 0 },
204      new byte[] { 1, 1, 3, 2 }, new byte[] { 1, 1, 3, 3 });
205
206    assertNext(false, new byte[] { 1, 1, 0, 0 }, new byte[] { -1, -1, 0, 0 },
207      new byte[] { 0, 1, 3, 2 }, new byte[] { 1, 1 });
208
209    // No next for this one
210    Assert.assertNull(FuzzyRowFilter.getNextForFuzzyRule(new byte[] { 2, 3, 1, 1, 1 }, // row to
211                                                                                       // check
212      new byte[] { 1, 0, 1 }, // fuzzy row
213      new byte[] { -1, 0, -1 })); // mask
214    Assert.assertNull(FuzzyRowFilter.getNextForFuzzyRule(new byte[] { 1, (byte) 245, 1, 3, 0 },
215      new byte[] { 1, 1, 0, 3 }, new byte[] { -1, -1, 0, -1 }));
216    Assert.assertNull(FuzzyRowFilter.getNextForFuzzyRule(new byte[] { 1, 3, 1, 3, 0 },
217      new byte[] { 1, 2, 0, 3 }, new byte[] { -1, -1, 0, -1 }));
218    Assert.assertNull(FuzzyRowFilter.getNextForFuzzyRule(new byte[] { 2, 1, 1, 1, 0 },
219      new byte[] { 1, 2, 0, 3 }, new byte[] { -1, -1, 0, -1 }));
220  }
221
222  @Test
223  public void testGetNextForFuzzyRuleReverse() {
224    assertNext(true, new byte[] { 0, 1, 2 }, // fuzzy row
225      new byte[] { 0, -1, -1 }, // mask
226      new byte[] { 1, 2, 1, 0, 1 }, // current
227      // TODO: should be {1, 1, 3} ?
228      new byte[] { 1, 1, 2, (byte) 0xFF, (byte) 0xFF }); // expected next
229
230    assertNext(true, new byte[] { 0, 1, 0, 2, 0 }, // fuzzy row
231      new byte[] { 0, -1, 0, -1, 0 }, // mask
232      new byte[] { 1, 2, 1, 3, 1 }, // current
233      // TODO: should be {1, 1, 1, 3} ?
234      new byte[] { 1, 1, 0, 2, 0 }); // expected next
235
236    assertNext(true, new byte[] { 1, 0, 1 }, new byte[] { -1, 0, -1 },
237      new byte[] { 1, (byte) 128, 2, 0, 1 },
238      // TODO: should be {1, (byte) 128, 2} ?
239      new byte[] { 1, (byte) 128, 1, (byte) 0xFF, (byte) 0xFF });
240
241    assertNext(true, new byte[] { 0, 1, 0, 1 }, new byte[] { 0, -1, 0, -1 },
242      new byte[] { 5, 1, 0, 2, 1 },
243      // TODO: should be {5, 1, 0, 2} ?
244      new byte[] { 5, 1, 0, 1, (byte) 0xFF });
245
246    assertNext(true, new byte[] { 0, 1, 0, 0 }, // fuzzy row
247      new byte[] { 0, -1, 0, 0 }, // mask
248      new byte[] { 5, 1, (byte) 255, 1 }, // current
249      new byte[] { 5, 1, (byte) 255, 0 }); // expected next
250
251    assertNext(true, new byte[] { 0, 1, 0, 1 }, // fuzzy row
252      new byte[] { 0, -1, 0, -1 }, // mask
253      new byte[] { 5, 1, 0, 1 }, // current
254      new byte[] { 4, 1, (byte) 255, 1 }); // expected next
255
256    assertNext(true, new byte[] { 0, 1, 0, 1 }, // fuzzy row
257      new byte[] { 0, -1, 0, -1 }, // mask
258      new byte[] { 5, 1, (byte) 255, 0 }, // current
259      new byte[] { 5, 1, (byte) 254, 1 }); // expected next
260
261    assertNext(true, new byte[] { 1, 1, 0, 0 }, new byte[] { -1, -1, 0, 0 },
262      new byte[] { 2, 1, 3, 2 },
263      // TODO: should be {1, 0} ?
264      new byte[] { 1, 1, 0, 0 });
265
266    assertNext(true, new byte[] { 1, 0, 1 }, // fuzzy row
267      new byte[] { -1, 0, -1 }, // mask
268      new byte[] { 2, 3, 1, 1, 1 }, // row to check
269      // TODO: should be {1, (byte) 0xFF, 2} ?
270      new byte[] { 1, 0, 1, (byte) 0xFF, (byte) 0xFF });
271
272    assertNext(true, new byte[] { 1, 1, 0, 3 }, new byte[] { -1, -1, 0, -1 },
273      new byte[] { 1, (byte) 245, 1, 3, 0 },
274      // TODO: should be {1, 1, (byte) 255, 4} ?
275      new byte[] { 1, 1, 0, 3, (byte) 0xFF });
276
277    assertNext(true, new byte[] { 1, 2, 0, 3 }, new byte[] { -1, -1, 0, -1 },
278      new byte[] { 1, 3, 1, 3, 0 },
279      // TODO: should be 1, 2, (byte) 255, 4 ?
280      new byte[] { 1, 2, 0, 3, (byte) 0xFF });
281
282    assertNext(true, new byte[] { 1, 2, 0, 3 }, new byte[] { -1, -1, 0, -1 },
283      new byte[] { 2, 1, 1, 1, 0 },
284      // TODO: should be {1, 2, (byte) 255, 4} ?
285      new byte[] { 1, 2, 0, 3, (byte) 0xFF });
286
287    assertNext(true,
288      // TODO: should be null?
289      new byte[] { 1, 0, 1 }, new byte[] { -1, 0, -1 }, new byte[] { 1, (byte) 128, 2 },
290      new byte[] { 1, (byte) 128, 1 });
291
292    assertNext(true,
293      // TODO: should be null?
294      new byte[] { 0, 1, 0, 1 }, new byte[] { 0, -1, 0, -1 }, new byte[] { 5, 1, 0, 2 },
295      new byte[] { 5, 1, 0, 1 });
296
297    assertNext(true,
298      // TODO: should be null?
299      new byte[] { 5, 1, 1, 0 }, new byte[] { -1, -1, 0, 0 }, new byte[] { 5, 1, (byte) 0xFF, 1 },
300      new byte[] { 5, 1, (byte) 0xFF, 0 });
301
302    assertNext(true,
303      // TODO: should be null?
304      new byte[] { 1, 1, 1, 1 }, new byte[] { -1, -1, 0, 0 }, new byte[] { 1, 1, 2, 2 },
305      new byte[] { 1, 1, 2, 1 });
306
307    assertNext(true,
308      // TODO: should be null?
309      new byte[] { 1, 1, 1, 1 }, new byte[] { 0, 0, 0, 0 }, new byte[] { 1, 1, 2, 3 },
310      new byte[] { 1, 1, 2, 2 });
311
312    Assert.assertNull(FuzzyRowFilter.getNextForFuzzyRule(true, new byte[] { 1, 1, 1, 3, 0 },
313      new byte[] { 1, 2, 0, 3 }, new byte[] { -1, -1, 0, -1 }));
314  }
315
316  private static void assertNext(boolean reverse, byte[] fuzzyRow, byte[] mask, byte[] current,
317    byte[] expected) {
318    KeyValue kv = KeyValueUtil.createFirstOnRow(current);
319    byte[] nextForFuzzyRule = FuzzyRowFilter.getNextForFuzzyRule(reverse, kv.getRowArray(),
320      kv.getRowOffset(), kv.getRowLength(), fuzzyRow, mask);
321    Assert.assertEquals(Bytes.toStringBinary(expected), Bytes.toStringBinary(nextForFuzzyRule));
322  }
323}