View Javadoc

1   /**
2    * Licensed to the Apache Software Foundation (ASF) under one
3    * or more contributor license agreements.  See the NOTICE file
4    * distributed with this work for additional information
5    * regarding copyright ownership.  The ASF licenses this file
6    * to you under the Apache License, Version 2.0 (the
7    * "License"); you may not use this file except in compliance
8    * with the License.  You may obtain a copy of the License at
9    *
10   *     http://www.apache.org/licenses/LICENSE-2.0
11   *
12   * Unless required by applicable law or agreed to in writing, software
13   * distributed under the License is distributed on an "AS IS" BASIS,
14   * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
15   * See the License for the specific language governing permissions and
16   * limitations under the License.
17   */
18  
19  package org.apache.hadoop.hbase.io.util;
20  
21  import static org.junit.Assert.*;
22  
23  import java.math.BigInteger;
24  import java.util.Arrays;
25  import java.util.Random;
26  
27  import org.apache.hadoop.hbase.HConstants;
28  import org.apache.hadoop.hbase.SmallTests;
29  import org.apache.hadoop.hbase.util.Bytes;
30  import org.junit.Before;
31  import org.junit.Test;
32  import org.junit.experimental.categories.Category;
33  
34  /**
35   * Tests LRUDictionary
36   */
37  @Category(SmallTests.class)
38  public class TestLRUDictionary {
39    LRUDictionary testee;
40  
41    @Before
42    public void setUp() throws Exception {
43      testee = new LRUDictionary();
44      testee.init(Short.MAX_VALUE);
45    }
46  
47    @Test
48    public void TestContainsNothing() {
49      assertTrue(isDictionaryEmpty(testee));
50    }
51  
52    /**
53     * Assert can't add empty array.
54     */
55    @Test
56    public void testPassingEmptyArrayToFindEntry() {
57      assertEquals(Dictionary.NOT_IN_DICTIONARY,
58        testee.findEntry(HConstants.EMPTY_BYTE_ARRAY, 0, 0));
59      assertEquals(Dictionary.NOT_IN_DICTIONARY,
60        testee.addEntry(HConstants.EMPTY_BYTE_ARRAY, 0, 0));
61    }
62  
63    @Test
64    public void testPassingSameArrayToAddEntry() {
65      // Add random predefined byte array, in this case a random byte array from
66      // HConstants.  Assert that when we add, we get new index.  Thats how it
67      // works.
68      int len = HConstants.CATALOG_FAMILY.length;
69      int index = testee.addEntry(HConstants.CATALOG_FAMILY, 0, len);
70      assertFalse(index == testee.addEntry(HConstants.CATALOG_FAMILY, 0, len));
71      assertFalse(index == testee.addEntry(HConstants.CATALOG_FAMILY, 0, len));
72    }
73  
74    @Test
75    public void testBasic() {
76      Random rand = new Random();
77      byte[] testBytes = new byte[10];
78      rand.nextBytes(testBytes);
79  
80      // Verify that our randomly generated array doesn't exist in the dictionary
81      assertEquals(testee.findEntry(testBytes, 0, testBytes.length), -1);
82  
83      // now since we looked up an entry, we should have added it to the
84      // dictionary, so it isn't empty
85  
86      assertFalse(isDictionaryEmpty(testee));
87  
88      // Check if we can find it using findEntry
89      short t = testee.findEntry(testBytes, 0, testBytes.length);
90  
91      // Making sure we do find what we're looking for
92      assertTrue(t != -1);
93  
94      byte[] testBytesCopy = new byte[20];
95  
96      Bytes.putBytes(testBytesCopy, 10, testBytes, 0, testBytes.length);
97  
98      // copy byte arrays, make sure that we check that equal byte arrays are
99      // 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     assertTrue(testee.findEntry(BigInteger.ZERO.toByteArray(), 0,
121         BigInteger.ZERO.toByteArray().length) != -1);
122 
123     // check for an element we know isn't there
124     assertTrue(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     assertTrue(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     assertTrue(testee.findEntry(BigInteger.ZERO.toByteArray(), 0,
134       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       assertTrue(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       assertTrue(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 }