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