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