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,
043                                     new byte[]{1, (byte) -128, 1, 0, 1},
044                                     0, 5,
045                                     new byte[]{1, 0, 1},
046                                     new byte[]{0, 1, 0}));
047
048    Assert.assertEquals(FuzzyRowFilter.SatisfiesCode.NEXT_EXISTS,
049            FuzzyRowFilter.satisfiesNoUnsafe(false,
050                                     new byte[]{1, (byte) -128, 2, 0, 1},
051                                     0, 5,
052                                     new byte[]{1, 0, 1},
053                                     new byte[]{0, 1, 0}));
054
055
056    Assert.assertEquals(FuzzyRowFilter.SatisfiesCode.YES,
057            FuzzyRowFilter.satisfiesNoUnsafe(false,
058                                     new byte[]{1, 2, 1, 3, 3},
059                                     0, 5,
060                                     new byte[]{1, 2, 0, 3},
061                                     new byte[]{0, 0, 1, 0}));
062
063    Assert.assertEquals(FuzzyRowFilter.SatisfiesCode.NEXT_EXISTS,
064            FuzzyRowFilter.satisfiesNoUnsafe(false,
065                                     new byte[]{1, 1, 1, 3, 0}, // row to check
066                                     0, 5,
067                                     new byte[]{1, 2, 0, 3}, // fuzzy row
068                                     new byte[]{0, 0, 1, 0})); // mask
069
070    Assert.assertEquals(FuzzyRowFilter.SatisfiesCode.NEXT_EXISTS,
071            FuzzyRowFilter.satisfiesNoUnsafe(false,
072                                     new byte[]{1, 1, 1, 3, 0},
073                                     0, 5,
074                                     new byte[]{1, (byte) 245, 0, 3},
075                                     new byte[]{0, 0, 1, 0}));
076
077    Assert.assertEquals(FuzzyRowFilter.SatisfiesCode.NEXT_EXISTS,
078            FuzzyRowFilter.satisfiesNoUnsafe(false,
079                                     new byte[]{1, 2, 1, 0, 1},
080                                     0, 5,
081                                     new byte[]{0, 1, 2},
082                                     new byte[]{1, 0, 0}));
083  }
084
085  @Test
086  public void testSatisfiesForward() {
087
088    Assert.assertEquals(FuzzyRowFilter.SatisfiesCode.YES,
089            FuzzyRowFilter.satisfies(false,
090                                     new byte[]{1, (byte) -128, 1, 0, 1},
091                                     new byte[]{1, 0, 1},
092                                     new byte[]{-1, 0, -1}));
093
094    Assert.assertEquals(FuzzyRowFilter.SatisfiesCode.NEXT_EXISTS,
095            FuzzyRowFilter.satisfies(false,
096                                     new byte[]{1, (byte) -128, 2, 0, 1},
097                                     new byte[]{1, 0, 1},
098                                     new byte[]{-1, 0, -1}));
099
100
101    Assert.assertEquals(FuzzyRowFilter.SatisfiesCode.YES,
102            FuzzyRowFilter.satisfies(false,
103                                     new byte[]{1, 2, 1, 3, 3},
104                                     new byte[]{1, 2, 0, 3},
105                                     new byte[]{-1, -1, 0, -1}));
106
107    Assert.assertEquals(FuzzyRowFilter.SatisfiesCode.NEXT_EXISTS,
108            FuzzyRowFilter.satisfies(false,
109                                     new byte[]{1, 1, 1, 3, 0}, // row to check
110                                     new byte[]{1, 2, 0, 3}, // fuzzy row
111                                     new byte[]{-1, -1, 0, -1})); // mask
112
113    Assert.assertEquals(FuzzyRowFilter.SatisfiesCode.NEXT_EXISTS,
114            FuzzyRowFilter.satisfies(false,
115                                     new byte[]{1, 1, 1, 3, 0},
116                                     new byte[]{1, (byte) 245, 0, 3},
117                                     new byte[]{-1, -1, 0, -1}));
118
119    Assert.assertEquals(FuzzyRowFilter.SatisfiesCode.NEXT_EXISTS,
120            FuzzyRowFilter.satisfies(false,
121                                     new byte[]{1, 2, 1, 0, 1},
122                                     new byte[]{0, 1, 2},
123                                     new byte[]{0, -1, -1}));
124  }
125
126  @Test
127  public void testSatisfiesReverse() {
128    Assert.assertEquals(FuzzyRowFilter.SatisfiesCode.YES,
129      FuzzyRowFilter.satisfies(true,
130        new byte[]{1, (byte) -128, 1, 0, 1},
131        new byte[]{1, 0, 1},
132        new byte[]{-1, 0, -1}));
133
134    Assert.assertEquals(FuzzyRowFilter.SatisfiesCode.NEXT_EXISTS,
135      FuzzyRowFilter.satisfies(true,
136        new byte[]{1, (byte) -128, 2, 0, 1},
137        new byte[]{1, 0, 1},
138        new byte[]{-1, 0, -1}));
139
140    Assert.assertEquals(FuzzyRowFilter.SatisfiesCode.NEXT_EXISTS,
141      FuzzyRowFilter.satisfies(true,
142        new byte[]{2, 3, 1, 1, 1},
143        new byte[]{1, 0, 1},
144        new byte[]{-1, 0, -1}));
145
146    Assert.assertEquals(FuzzyRowFilter.SatisfiesCode.YES,
147      FuzzyRowFilter.satisfies(true,
148        new byte[]{1, 2, 1, 3, 3},
149        new byte[]{1, 2, 0, 3},
150        new byte[]{-1, -1, 0, -1}));
151
152    Assert.assertEquals(FuzzyRowFilter.SatisfiesCode.NEXT_EXISTS,
153      FuzzyRowFilter.satisfies(true,
154        new byte[]{1, (byte) 245, 1, 3, 0},
155        new byte[]{1, 1, 0, 3},
156        new byte[]{-1, -1, 0, -1}));
157
158    Assert.assertEquals(FuzzyRowFilter.SatisfiesCode.NEXT_EXISTS,
159      FuzzyRowFilter.satisfies(true,
160        new byte[]{1, 3, 1, 3, 0},
161        new byte[]{1, 2, 0, 3},
162        new byte[]{-1, -1, 0, -1}));
163
164    Assert.assertEquals(FuzzyRowFilter.SatisfiesCode.NEXT_EXISTS,
165      FuzzyRowFilter.satisfies(true,
166        new byte[]{2, 1, 1, 1, 0},
167        new byte[]{1, 2, 0, 3},
168        new byte[]{-1, -1, 0, -1}));
169
170    Assert.assertEquals(FuzzyRowFilter.SatisfiesCode.NEXT_EXISTS,
171      FuzzyRowFilter.satisfies(true,
172        new byte[]{1, 2, 1, 0, 1},
173        new byte[]{0, 1, 2},
174        new byte[]{0, -1, -1}));
175  }
176
177  @Test
178  public void testSatisfiesNoUnsafeReverse() {
179    Assert.assertEquals(FuzzyRowFilter.SatisfiesCode.YES,
180      FuzzyRowFilter.satisfiesNoUnsafe(true,
181        new byte[]{1, (byte) -128, 1, 0, 1},
182        0, 5,
183        new byte[]{1, 0, 1},
184        new byte[]{0, 1, 0}));
185
186    Assert.assertEquals(FuzzyRowFilter.SatisfiesCode.NEXT_EXISTS,
187      FuzzyRowFilter.satisfiesNoUnsafe(true,
188        new byte[]{1, (byte) -128, 2, 0, 1},
189        0, 5,
190        new byte[]{1, 0, 1},
191        new byte[]{0, 1, 0}));
192
193    Assert.assertEquals(FuzzyRowFilter.SatisfiesCode.NEXT_EXISTS,
194      FuzzyRowFilter.satisfiesNoUnsafe(true,
195        new byte[]{2, 3, 1, 1, 1},
196        0, 5,
197        new byte[]{1, 0, 1},
198        new byte[]{0, 1, 0}));
199
200    Assert.assertEquals(FuzzyRowFilter.SatisfiesCode.YES,
201      FuzzyRowFilter.satisfiesNoUnsafe(true,
202        new byte[]{1, 2, 1, 3, 3},
203        0, 5,
204        new byte[]{1, 2, 0, 3},
205        new byte[]{0, 0, 1, 0}));
206
207    Assert.assertEquals(FuzzyRowFilter.SatisfiesCode.NEXT_EXISTS,
208      FuzzyRowFilter.satisfiesNoUnsafe(true,
209        new byte[]{1, (byte) 245, 1, 3, 0},
210        0, 5,
211        new byte[]{1, 1, 0, 3},
212        new byte[]{0, 0, 1, 0}));
213
214    Assert.assertEquals(FuzzyRowFilter.SatisfiesCode.NEXT_EXISTS,
215      FuzzyRowFilter.satisfiesNoUnsafe(true,
216        new byte[]{1, 3, 1, 3, 0},
217        0, 5,
218        new byte[]{1, 2, 0, 3},
219        new byte[]{0, 0, 1, 0}));
220
221    Assert.assertEquals(FuzzyRowFilter.SatisfiesCode.NEXT_EXISTS,
222      FuzzyRowFilter.satisfiesNoUnsafe(true,
223        new byte[]{2, 1, 1, 1, 0},
224        0, 5,
225        new byte[]{1, 2, 0, 3},
226        new byte[]{0, 0, 1, 0}));
227
228    Assert.assertEquals(FuzzyRowFilter.SatisfiesCode.NEXT_EXISTS,
229      FuzzyRowFilter.satisfiesNoUnsafe(true,
230        new byte[]{1, 2, 1, 0, 1},
231        0, 5,
232        new byte[]{0, 1, 2},
233        new byte[]{1, 0, 0}));
234  }
235  @Test
236  public void testGetNextForFuzzyRuleForward() {
237    assertNext(false,
238            new byte[]{0, 1, 2}, // fuzzy row
239            new byte[]{0, -1, -1}, // mask
240            new byte[]{1, 2, 1, 0, 1}, // current
241            new byte[]{2, 1, 2}); // expected next
242
243    assertNext(false,
244            new byte[]{0, 1, 2}, // fuzzy row
245            new byte[]{0, -1, -1}, // mask
246            new byte[]{1, 1, 2, 0, 1}, // current
247            new byte[]{1, 1, 2, 0, 2}); // expected next
248
249    assertNext(false,
250            new byte[]{0, 1, 0, 2, 0}, // fuzzy row
251            new byte[]{0, -1, 0, -1, 0}, // mask
252            new byte[]{1, 0, 2, 0, 1}, // current
253            new byte[]{1, 1, 0, 2}); // expected next
254
255    assertNext(false,
256            new byte[]{1, 0, 1},
257            new byte[]{-1, 0, -1},
258            new byte[]{1, (byte) 128, 2, 0, 1},
259            new byte[]{1, (byte) 129, 1});
260
261    assertNext(false,
262            new byte[]{0, 1, 0, 1},
263            new byte[]{0, -1, 0, -1},
264            new byte[]{5, 1, 0, 1},
265            new byte[]{5, 1, 1, 1});
266
267    assertNext(false,
268            new byte[]{0, 1, 0, 1},
269            new byte[]{0, -1, 0, -1},
270            new byte[]{5, 1, 0, 1, 1},
271            new byte[]{5, 1, 0, 1, 2});
272
273    assertNext(false,
274            new byte[]{0, 1, 0, 0}, // fuzzy row
275            new byte[]{0, -1, 0, 0}, // mask
276            new byte[]{5, 1, (byte) 255, 1}, // current
277            new byte[]{5, 1, (byte) 255, 2}); // expected next
278
279    assertNext(false,
280            new byte[]{0, 1, 0, 1}, // fuzzy row
281            new byte[]{0, -1, 0, -1}, // mask
282            new byte[]{5, 1, (byte) 255, 1}, // current
283            new byte[]{6, 1, 0, 1}); // expected next
284
285    assertNext(false,
286            new byte[]{0, 1, 0, 1}, // fuzzy row
287            new byte[]{0, -1, 0, -1}, // mask
288            new byte[]{5, 1, (byte) 255, 0}, // current
289            new byte[]{5, 1, (byte) 255, 1}); // expected next
290
291    assertNext(false,
292            new byte[]{5, 1, 1, 0},
293            new byte[]{-1, -1, 0, 0},
294            new byte[]{5, 1, (byte) 255, 1},
295            new byte[]{5, 1, (byte) 255, 2});
296
297    assertNext(false,
298            new byte[]{1, 1, 1, 1},
299            new byte[]{-1, -1, 0, 0},
300            new byte[]{1, 1, 2, 2},
301            new byte[]{1, 1, 2, 3});
302
303    assertNext(false,
304            new byte[]{1, 1, 1, 1},
305            new byte[]{-1, -1, 0, 0},
306            new byte[]{1, 1, 3, 2},
307            new byte[]{1, 1, 3, 3});
308
309    assertNext(false,
310            new byte[]{1, 1, 1, 1},
311            new byte[]{0, 0, 0, 0},
312            new byte[]{1, 1, 2, 3},
313            new byte[]{1, 1, 2, 4});
314
315    assertNext(false,
316            new byte[]{1, 1, 1, 1},
317            new byte[]{0, 0, 0, 0},
318            new byte[]{1, 1, 3, 2},
319            new byte[]{1, 1, 3, 3});
320
321    assertNext(false,
322            new byte[]{1, 1, 0, 0},
323            new byte[]{-1, -1, 0, 0},
324            new byte[]{0, 1, 3, 2},
325            new byte[]{1, 1});
326
327    // No next for this one
328    Assert.assertNull(FuzzyRowFilter.getNextForFuzzyRule(
329            new byte[]{2, 3, 1, 1, 1}, // row to check
330            new byte[]{1, 0, 1}, // fuzzy row
331            new byte[]{-1, 0, -1})); // mask
332    Assert.assertNull(FuzzyRowFilter.getNextForFuzzyRule(
333            new byte[]{1, (byte) 245, 1, 3, 0},
334            new byte[]{1, 1, 0, 3},
335            new byte[]{-1, -1, 0, -1}));
336    Assert.assertNull(FuzzyRowFilter.getNextForFuzzyRule(
337            new byte[]{1, 3, 1, 3, 0},
338            new byte[]{1, 2, 0, 3},
339            new byte[]{-1, -1, 0, -1}));
340    Assert.assertNull(FuzzyRowFilter.getNextForFuzzyRule(
341            new byte[]{2, 1, 1, 1, 0},
342            new byte[]{1, 2, 0, 3},
343            new byte[]{-1, -1, 0, -1}));
344  }
345
346  @Test
347  public void testGetNextForFuzzyRuleReverse() {
348    assertNext(true,
349      new byte[]{0, 1, 2}, // fuzzy row
350      new byte[]{0, -1, -1}, // mask
351      new byte[]{1, 2, 1, 0, 1}, // current
352      // TODO: should be {1, 1, 3} ?
353      new byte[]{1, 1, 2, (byte) 0xFF, (byte) 0xFF}); // expected next
354
355    assertNext(true,
356      new byte[]{0, 1, 0, 2, 0}, // fuzzy row
357      new byte[]{0, -1, 0, -1, 0}, // mask
358      new byte[]{1, 2, 1, 3, 1}, // current
359      // TODO: should be {1, 1, 1, 3} ?
360      new byte[]{1, 1, 0, 2, 0}); // expected next
361
362    assertNext(true,
363      new byte[]{1, 0, 1},
364      new byte[]{-1, 0, -1},
365      new byte[]{1, (byte) 128, 2, 0, 1},
366      // TODO: should be {1, (byte) 128, 2} ?
367      new byte[]{1, (byte) 128, 1, (byte) 0xFF, (byte) 0xFF});
368
369    assertNext(true,
370      new byte[]{0, 1, 0, 1},
371      new byte[]{0, -1, 0, -1},
372      new byte[]{5, 1, 0, 2, 1},
373      // TODO: should be {5, 1, 0, 2} ?
374      new byte[]{5, 1, 0, 1, (byte) 0xFF});
375
376    assertNext(true,
377      new byte[]{0, 1, 0, 0}, // fuzzy row
378      new byte[]{0, -1, 0, 0}, // mask
379      new byte[]{5, 1, (byte) 255, 1}, // current
380      new byte[]{5, 1, (byte) 255, 0}); // expected next
381
382    assertNext(true,
383      new byte[]{0, 1, 0, 1}, // fuzzy row
384      new byte[]{0, -1, 0, -1}, // mask
385      new byte[]{5, 1, 0, 1}, // current
386      new byte[]{4, 1, (byte) 255, 1}); // expected next
387
388    assertNext(true,
389      new byte[]{0, 1, 0, 1}, // fuzzy row
390      new byte[]{0, -1, 0, -1}, // mask
391      new byte[]{5, 1, (byte) 255, 0}, // current
392      new byte[]{5, 1, (byte) 254, 1}); // expected next
393
394    assertNext(true,
395      new byte[]{1, 1, 0, 0},
396      new byte[]{-1, -1, 0, 0},
397      new byte[]{2, 1, 3, 2},
398      // TODO: should be {1, 0} ?
399      new byte[]{1, 1, 0, 0});
400
401    assertNext(true,
402      new byte[]{1, 0, 1}, // fuzzy row
403      new byte[]{-1, 0, -1}, // mask
404      new byte[]{2, 3, 1, 1, 1}, // row to check
405      // TODO: should be {1, (byte) 0xFF, 2} ?
406      new byte[]{1, 0, 1, (byte) 0xFF, (byte) 0xFF});
407
408    assertNext(true,
409      new byte[]{1, 1, 0, 3},
410      new byte[]{-1, -1, 0, -1},
411      new byte[]{1, (byte) 245, 1, 3, 0},
412      // TODO: should be {1, 1, (byte) 255, 4} ?
413      new byte[]{1, 1, 0, 3, (byte) 0xFF});
414
415    assertNext(true,
416      new byte[]{1, 2, 0, 3},
417      new byte[]{-1, -1, 0, -1},
418      new byte[]{1, 3, 1, 3, 0},
419      // TODO: should be 1, 2, (byte) 255, 4 ?
420      new byte[]{1, 2, 0, 3, (byte) 0xFF});
421
422    assertNext(true,
423      new byte[]{1, 2, 0, 3},
424      new byte[]{-1, -1, 0, -1},
425      new byte[]{2, 1, 1, 1, 0},
426      // TODO: should be {1, 2, (byte) 255, 4} ?
427      new byte[]{1, 2, 0, 3, (byte) 0xFF});
428
429    assertNext(true,
430      // TODO: should be null?
431      new byte[]{1, 0, 1},
432      new byte[]{-1, 0, -1},
433      new byte[]{1, (byte) 128, 2},
434      new byte[]{1, (byte) 128, 1});
435
436    assertNext(true,
437      // TODO: should be null?
438      new byte[]{0, 1, 0, 1},
439      new byte[]{0, -1, 0, -1},
440      new byte[]{5, 1, 0, 2},
441      new byte[]{5, 1, 0, 1});
442
443    assertNext(true,
444      // TODO: should be null?
445      new byte[]{5, 1, 1, 0},
446      new byte[]{-1, -1, 0, 0},
447      new byte[]{5, 1, (byte) 0xFF, 1},
448      new byte[]{5, 1, (byte) 0xFF, 0});
449
450    assertNext(true,
451      // TODO: should be null?
452      new byte[]{1, 1, 1, 1},
453      new byte[]{-1, -1, 0, 0},
454      new byte[]{1, 1, 2, 2},
455      new byte[]{1, 1, 2, 1});
456
457    assertNext(true,
458      // TODO: should be null?
459      new byte[]{1, 1, 1, 1},
460      new byte[]{0, 0, 0, 0},
461      new byte[]{1, 1, 2, 3},
462      new byte[]{1, 1, 2, 2});
463
464    Assert.assertNull(FuzzyRowFilter.getNextForFuzzyRule(true,
465      new byte[]{1, 1, 1, 3, 0},
466      new byte[]{1, 2, 0, 3},
467      new byte[]{-1, -1, 0, -1}));
468  }
469
470  private static void assertNext(boolean reverse, byte[] fuzzyRow, byte[] mask, byte[] current,
471      byte[] expected) {
472    KeyValue kv = KeyValueUtil.createFirstOnRow(current);
473    byte[] nextForFuzzyRule = FuzzyRowFilter.getNextForFuzzyRule(reverse, kv.getRowArray(),
474        kv.getRowOffset(), kv.getRowLength(), fuzzyRow, mask);
475    Assert.assertEquals(Bytes.toStringBinary(expected), Bytes.toStringBinary(nextForFuzzyRule));
476  }
477}