1 /*
2  * Copyright 2017 The gRPC Authors
3  *
4  * Licensed under the Apache License, Version 2.0 (the "License");
5  * you may not use this file except in compliance with the License.
6  * You may obtain a copy of the License at
7  *
8  *     http://www.apache.org/licenses/LICENSE-2.0
9  *
10  * Unless required by applicable law or agreed to in writing, software
11  * distributed under the License is distributed on an "AS IS" BASIS,
12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13  * See the License for the specific language governing permissions and
14  * limitations under the License.
15  */
16 
17 package io.grpc;
18 
19 import static junit.framework.TestCase.assertTrue;
20 import static org.junit.Assert.assertEquals;
21 import static org.junit.Assert.assertSame;
22 
23 import io.grpc.PersistentHashArrayMappedTrie.CollisionLeaf;
24 import io.grpc.PersistentHashArrayMappedTrie.CompressedIndex;
25 import io.grpc.PersistentHashArrayMappedTrie.Leaf;
26 import io.grpc.PersistentHashArrayMappedTrie.Node;
27 import org.junit.Test;
28 import org.junit.runner.RunWith;
29 import org.junit.runners.JUnit4;
30 
31 @RunWith(JUnit4.class)
32 public class PersistentHashArrayMappedTrieTest {
33   @Test
leaf_replace()34   public void leaf_replace() {
35     Key key = new Key(0);
36     Object value1 = new Object();
37     Object value2 = new Object();
38     Leaf<Key, Object> leaf = new Leaf<Key, Object>(key, value1);
39     Node<Key, Object> ret = leaf.put(key, value2, key.hashCode(), 0);
40     assertTrue(ret instanceof Leaf);
41     assertSame(value2, ret.get(key, key.hashCode(), 0));
42 
43     assertSame(value1, leaf.get(key, key.hashCode(), 0));
44 
45     assertEquals(1, leaf.size());
46     assertEquals(1, ret.size());
47   }
48 
49   @Test
leaf_collision()50   public void leaf_collision() {
51     Key key1 = new Key(0);
52     Key key2 = new Key(0);
53     Object value1 = new Object();
54     Object value2 = new Object();
55     Leaf<Key, Object> leaf = new Leaf<Key, Object>(key1, value1);
56     Node<Key, Object> ret = leaf.put(key2, value2, key2.hashCode(), 0);
57     assertTrue(ret instanceof CollisionLeaf);
58     assertSame(value1, ret.get(key1, key1.hashCode(), 0));
59     assertSame(value2, ret.get(key2, key2.hashCode(), 0));
60 
61     assertSame(value1, leaf.get(key1, key1.hashCode(), 0));
62     assertSame(null, leaf.get(key2, key2.hashCode(), 0));
63 
64     assertEquals(1, leaf.size());
65     assertEquals(2, ret.size());
66   }
67 
68   @Test
leaf_insert()69   public void leaf_insert() {
70     Key key1 = new Key(0);
71     Key key2 = new Key(1);
72     Object value1 = new Object();
73     Object value2 = new Object();
74     Leaf<Key, Object> leaf = new Leaf<Key, Object>(key1, value1);
75     Node<Key, Object> ret = leaf.put(key2, value2, key2.hashCode(), 0);
76     assertTrue(ret instanceof CompressedIndex);
77     assertSame(value1, ret.get(key1, key1.hashCode(), 0));
78     assertSame(value2, ret.get(key2, key2.hashCode(), 0));
79 
80     assertSame(value1, leaf.get(key1, key1.hashCode(), 0));
81     assertSame(null, leaf.get(key2, key2.hashCode(), 0));
82 
83     assertEquals(1, leaf.size());
84     assertEquals(2, ret.size());
85   }
86 
87   @Test(expected = AssertionError.class)
collisionLeaf_assertKeysDifferent()88   public void collisionLeaf_assertKeysDifferent() {
89     Key key1 = new Key(0);
90     new CollisionLeaf<Key, Object>(key1, new Object(), key1, new Object());
91   }
92 
93   @Test(expected = AssertionError.class)
collisionLeaf_assertHashesSame()94   public void collisionLeaf_assertHashesSame() {
95     new CollisionLeaf<Key, Object>(new Key(0), new Object(), new Key(1), new Object());
96   }
97 
98   @Test
collisionLeaf_insert()99   public void collisionLeaf_insert() {
100     Key key1 = new Key(0);
101     Key key2 = new Key(key1.hashCode());
102     Key insertKey = new Key(1);
103     Object value1 = new Object();
104     Object value2 = new Object();
105     Object insertValue = new Object();
106     CollisionLeaf<Key, Object> leaf =
107         new CollisionLeaf<Key, Object>(key1, value1, key2, value2);
108 
109     Node<Key, Object> ret = leaf.put(insertKey, insertValue, insertKey.hashCode(), 0);
110     assertTrue(ret instanceof CompressedIndex);
111     assertSame(value1, ret.get(key1, key1.hashCode(), 0));
112     assertSame(value2, ret.get(key2, key2.hashCode(), 0));
113     assertSame(insertValue, ret.get(insertKey, insertKey.hashCode(), 0));
114 
115     assertSame(value1, leaf.get(key1, key1.hashCode(), 0));
116     assertSame(value2, leaf.get(key2, key2.hashCode(), 0));
117     assertSame(null, leaf.get(insertKey, insertKey.hashCode(), 0));
118 
119     assertEquals(2, leaf.size());
120     assertEquals(3, ret.size());
121   }
122 
123   @Test
collisionLeaf_replace()124   public void collisionLeaf_replace() {
125     Key replaceKey = new Key(0);
126     Object originalValue = new Object();
127     Key key = new Key(replaceKey.hashCode());
128     Object value = new Object();
129     CollisionLeaf<Key, Object> leaf =
130         new CollisionLeaf<Key, Object>(replaceKey, originalValue, key, value);
131     Object replaceValue = new Object();
132     Node<Key, Object> ret = leaf.put(replaceKey, replaceValue, replaceKey.hashCode(), 0);
133     assertTrue(ret instanceof CollisionLeaf);
134     assertSame(replaceValue, ret.get(replaceKey, replaceKey.hashCode(), 0));
135     assertSame(value, ret.get(key, key.hashCode(), 0));
136 
137     assertSame(value, leaf.get(key, key.hashCode(), 0));
138     assertSame(originalValue, leaf.get(replaceKey, replaceKey.hashCode(), 0));
139 
140     assertEquals(2, leaf.size());
141     assertEquals(2, ret.size());
142   }
143 
144   @Test
collisionLeaf_collision()145   public void collisionLeaf_collision() {
146     Key key1 = new Key(0);
147     Key key2 = new Key(key1.hashCode());
148     Key key3 = new Key(key1.hashCode());
149     Object value1 = new Object();
150     Object value2 = new Object();
151     Object value3 = new Object();
152     CollisionLeaf<Key, Object> leaf =
153         new CollisionLeaf<Key, Object>(key1, value1, key2, value2);
154 
155     Node<Key, Object> ret = leaf.put(key3, value3, key3.hashCode(), 0);
156     assertTrue(ret instanceof CollisionLeaf);
157     assertSame(value1, ret.get(key1, key1.hashCode(), 0));
158     assertSame(value2, ret.get(key2, key2.hashCode(), 0));
159     assertSame(value3, ret.get(key3, key3.hashCode(), 0));
160 
161     assertSame(value1, leaf.get(key1, key1.hashCode(), 0));
162     assertSame(value2, leaf.get(key2, key2.hashCode(), 0));
163     assertSame(null, leaf.get(key3, key3.hashCode(), 0));
164 
165     assertEquals(2, leaf.size());
166     assertEquals(3, ret.size());
167   }
168 
169   @Test
compressedIndex_combine_differentIndexBit()170   public void compressedIndex_combine_differentIndexBit() {
171     final Key key1 = new Key(7);
172     final Key key2 = new Key(19);
173     final Object value1 = new Object();
174     final Object value2 = new Object();
175     Leaf<Key, Object> leaf1 = new Leaf<Key, Object>(key1, value1);
176     Leaf<Key, Object> leaf2 = new Leaf<Key, Object>(key2, value2);
177     class Verifier {
178       private void verify(Node<Key, Object> ret) {
179         CompressedIndex<Key, Object> collisionLeaf = (CompressedIndex<Key, Object>) ret;
180         assertEquals((1 << 7) | (1 << 19), collisionLeaf.bitmap);
181         assertEquals(2, collisionLeaf.values.length);
182         assertSame(value1, collisionLeaf.values[0].get(key1, key1.hashCode(), 0));
183         assertSame(value2, collisionLeaf.values[1].get(key2, key2.hashCode(), 0));
184 
185         assertSame(value1, ret.get(key1, key1.hashCode(), 0));
186         assertSame(value2, ret.get(key2, key2.hashCode(), 0));
187 
188         assertEquals(2, ret.size());
189       }
190     }
191 
192     Verifier verifier = new Verifier();
193     verifier.verify(CompressedIndex.combine(leaf1, key1.hashCode(), leaf2, key2.hashCode(), 0));
194     verifier.verify(CompressedIndex.combine(leaf2, key2.hashCode(), leaf1, key1.hashCode(), 0));
195 
196     assertEquals(1, leaf1.size());
197     assertEquals(1, leaf2.size());
198   }
199 
200   @Test
compressedIndex_combine_sameIndexBit()201   public void compressedIndex_combine_sameIndexBit() {
202     final Key key1 = new Key(17 << 5 | 1); // 5 bit regions: (17, 1)
203     final Key key2 = new Key(31 << 5 | 1); // 5 bit regions: (31, 1)
204     final Object value1 = new Object();
205     final Object value2 = new Object();
206     Leaf<Key, Object> leaf1 = new Leaf<Key, Object>(key1, value1);
207     Leaf<Key, Object> leaf2 = new Leaf<Key, Object>(key2, value2);
208     class Verifier {
209       private void verify(Node<Key, Object> ret) {
210         CompressedIndex<Key, Object> collisionInternal = (CompressedIndex<Key, Object>) ret;
211         assertEquals(1 << 1, collisionInternal.bitmap);
212         assertEquals(1, collisionInternal.values.length);
213         CompressedIndex<Key, Object> collisionLeaf =
214             (CompressedIndex<Key, Object>) collisionInternal.values[0];
215         assertEquals((1 << 31) | (1 << 17), collisionLeaf.bitmap);
216         assertSame(value1, ret.get(key1, key1.hashCode(), 0));
217         assertSame(value2, ret.get(key2, key2.hashCode(), 0));
218 
219         assertEquals(2, ret.size());
220       }
221     }
222 
223     Verifier verifier = new Verifier();
224     verifier.verify(CompressedIndex.combine(leaf1, key1.hashCode(), leaf2, key2.hashCode, 0));
225     verifier.verify(CompressedIndex.combine(leaf2, key2.hashCode(), leaf1, key1.hashCode, 0));
226 
227     assertEquals(1, leaf1.size());
228     assertEquals(1, leaf2.size());
229   }
230 
231   /**
232    * A key with a settable hashcode.
233    */
234   static final class Key {
235     private final int hashCode;
236 
Key(int hashCode)237     Key(int hashCode) {
238       this.hashCode = hashCode;
239     }
240 
241     @Override
hashCode()242     public int hashCode() {
243       return hashCode;
244     }
245 
246     @Override
toString()247     public String toString() {
248       return String.format("Key(hashCode=%x)", hashCode);
249     }
250   }
251 }
252