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.io.util;
019
020import static org.junit.jupiter.api.Assertions.assertEquals;
021import static org.junit.jupiter.api.Assertions.assertFalse;
022import static org.junit.jupiter.api.Assertions.assertNotEquals;
023import static org.junit.jupiter.api.Assertions.assertTrue;
024
025import java.math.BigInteger;
026import java.util.Arrays;
027import org.apache.hadoop.hbase.HConstants;
028import org.apache.hadoop.hbase.testclassification.MiscTests;
029import org.apache.hadoop.hbase.testclassification.SmallTests;
030import org.apache.hadoop.hbase.util.Bytes;
031import org.junit.jupiter.api.BeforeEach;
032import org.junit.jupiter.api.Tag;
033import org.junit.jupiter.api.Test;
034
035/**
036 * Tests LRUDictionary
037 */
038@Tag(MiscTests.TAG)
039@Tag(SmallTests.TAG)
040public class TestLRUDictionary {
041
042  LRUDictionary testee;
043
044  @BeforeEach
045  public void setUp() throws Exception {
046    testee = new LRUDictionary();
047    testee.init(Short.MAX_VALUE);
048  }
049
050  @Test
051  public void TestContainsNothing() {
052    assertTrue(isDictionaryEmpty(testee));
053  }
054
055  /**
056   * Assert can't add empty array.
057   */
058  @Test
059  public void testPassingEmptyArrayToFindEntry() {
060    assertEquals(Dictionary.NOT_IN_DICTIONARY, testee.findEntry(HConstants.EMPTY_BYTE_ARRAY, 0, 0));
061    assertEquals(Dictionary.NOT_IN_DICTIONARY, testee.addEntry(HConstants.EMPTY_BYTE_ARRAY, 0, 0));
062  }
063
064  @Test
065  public void testPassingSameArrayToAddEntry() {
066    // Add random predefined byte array, in this case a random byte array from
067    // HConstants. Assert that when we add, we get new index. Thats how it
068    // works.
069    int len = HConstants.CATALOG_FAMILY.length;
070    int index = testee.addEntry(HConstants.CATALOG_FAMILY, 0, len);
071    assertNotEquals(index, testee.addEntry(HConstants.CATALOG_FAMILY, 0, len));
072    assertNotEquals(index, testee.addEntry(HConstants.CATALOG_FAMILY, 0, len));
073  }
074
075  @Test
076  public void testBasic() {
077    byte[] testBytes = new byte[10];
078    Bytes.random(testBytes);
079
080    // Verify that our randomly generated array doesn't exist in the dictionary
081    assertEquals(-1, testee.findEntry(testBytes, 0, testBytes.length));
082
083    // now since we looked up an entry, we should have added it to the
084    // dictionary, so it isn't empty
085
086    assertFalse(isDictionaryEmpty(testee));
087
088    // Check if we can find it using findEntry
089    short t = testee.findEntry(testBytes, 0, testBytes.length);
090
091    // Making sure we do find what we're looking for
092    assertNotEquals(t, -1);
093
094    byte[] testBytesCopy = new byte[20];
095
096    Bytes.putBytes(testBytesCopy, 10, testBytes, 0, testBytes.length);
097
098    // copy byte arrays, make sure that we check that equal byte arrays are
099    // equal without just checking the reference
100    assertEquals(testee.findEntry(testBytesCopy, 10, testBytes.length), t);
101
102    // make sure the entry retrieved is the same as the one put in
103    assertTrue(Arrays.equals(testBytes, testee.getEntry(t)));
104
105    testee.clear();
106
107    // making sure clear clears the dictionary
108    assertTrue(isDictionaryEmpty(testee));
109  }
110
111  @Test
112  public void TestLRUPolicy() {
113    // start by filling the dictionary up with byte arrays
114    for (int i = 0; i < Short.MAX_VALUE; i++) {
115      testee.findEntry(BigInteger.valueOf(i).toByteArray(), 0,
116        BigInteger.valueOf(i).toByteArray().length);
117    }
118
119    // check we have the first element added
120    assertNotEquals(
121      testee.findEntry(BigInteger.ZERO.toByteArray(), 0, BigInteger.ZERO.toByteArray().length), -1);
122
123    // check for an element we know isn't there
124    assertEquals(testee.findEntry(BigInteger.valueOf(Integer.MAX_VALUE).toByteArray(), 0,
125      BigInteger.valueOf(Integer.MAX_VALUE).toByteArray().length), -1);
126
127    // since we just checked for this element, it should be there now.
128    assertNotEquals(testee.findEntry(BigInteger.valueOf(Integer.MAX_VALUE).toByteArray(), 0,
129      BigInteger.valueOf(Integer.MAX_VALUE).toByteArray().length), -1);
130
131    // test eviction, that the least recently added or looked at element is
132    // evicted. We looked at ZERO so it should be in the dictionary still.
133    assertNotEquals(
134      testee.findEntry(BigInteger.ZERO.toByteArray(), 0, BigInteger.ZERO.toByteArray().length), -1);
135    // Now go from beyond 1 to the end.
136    for (int i = 1; i < Short.MAX_VALUE; i++) {
137      assertEquals(testee.findEntry(BigInteger.valueOf(i).toByteArray(), 0,
138        BigInteger.valueOf(i).toByteArray().length), -1);
139    }
140
141    // check we can find all of these.
142    for (int i = 0; i < Short.MAX_VALUE; i++) {
143      assertNotEquals(testee.findEntry(BigInteger.valueOf(i).toByteArray(), 0,
144        BigInteger.valueOf(i).toByteArray().length), -1);
145    }
146  }
147
148  static private boolean isDictionaryEmpty(LRUDictionary dict) {
149    try {
150      dict.getEntry((short) 0);
151      return false;
152    } catch (IndexOutOfBoundsException ioobe) {
153      return true;
154    }
155  }
156}