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, 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<>(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<>(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 @SuppressWarnings("CheckReturnValue") 88 @Test collisionLeaf_assertKeysDifferent()89 public void collisionLeaf_assertKeysDifferent() { 90 Key key1 = new Key(0); 91 try { 92 new CollisionLeaf<>(key1, new Object(), key1, new Object()); 93 throw new Error(); 94 } catch (AssertionError expected) { 95 } 96 } 97 98 @SuppressWarnings("CheckReturnValue") 99 @Test collisionLeaf_assertHashesSame()100 public void collisionLeaf_assertHashesSame() { 101 try { 102 new CollisionLeaf<>(new Key(0), new Object(), new Key(1), new Object()); 103 throw new Error(); 104 } catch (AssertionError expected) { 105 } 106 } 107 108 @Test collisionLeaf_insert()109 public void collisionLeaf_insert() { 110 Key key1 = new Key(0); 111 Key key2 = new Key(key1.hashCode()); 112 Key insertKey = new Key(1); 113 Object value1 = new Object(); 114 Object value2 = new Object(); 115 Object insertValue = new Object(); 116 CollisionLeaf<Key, Object> leaf = 117 new CollisionLeaf<>(key1, value1, key2, value2); 118 119 Node<Key, Object> ret = leaf.put(insertKey, insertValue, insertKey.hashCode(), 0); 120 assertTrue(ret instanceof CompressedIndex); 121 assertSame(value1, ret.get(key1, key1.hashCode(), 0)); 122 assertSame(value2, ret.get(key2, key2.hashCode(), 0)); 123 assertSame(insertValue, ret.get(insertKey, insertKey.hashCode(), 0)); 124 125 assertSame(value1, leaf.get(key1, key1.hashCode(), 0)); 126 assertSame(value2, leaf.get(key2, key2.hashCode(), 0)); 127 assertSame(null, leaf.get(insertKey, insertKey.hashCode(), 0)); 128 129 assertEquals(2, leaf.size()); 130 assertEquals(3, ret.size()); 131 } 132 133 @Test collisionLeaf_replace()134 public void collisionLeaf_replace() { 135 Key replaceKey = new Key(0); 136 Object originalValue = new Object(); 137 Key key = new Key(replaceKey.hashCode()); 138 Object value = new Object(); 139 CollisionLeaf<Key, Object> leaf = 140 new CollisionLeaf<>(replaceKey, originalValue, key, value); 141 Object replaceValue = new Object(); 142 Node<Key, Object> ret = leaf.put(replaceKey, replaceValue, replaceKey.hashCode(), 0); 143 assertTrue(ret instanceof CollisionLeaf); 144 assertSame(replaceValue, ret.get(replaceKey, replaceKey.hashCode(), 0)); 145 assertSame(value, ret.get(key, key.hashCode(), 0)); 146 147 assertSame(value, leaf.get(key, key.hashCode(), 0)); 148 assertSame(originalValue, leaf.get(replaceKey, replaceKey.hashCode(), 0)); 149 150 assertEquals(2, leaf.size()); 151 assertEquals(2, ret.size()); 152 } 153 154 @Test collisionLeaf_collision()155 public void collisionLeaf_collision() { 156 Key key1 = new Key(0); 157 Key key2 = new Key(key1.hashCode()); 158 Key key3 = new Key(key1.hashCode()); 159 Object value1 = new Object(); 160 Object value2 = new Object(); 161 Object value3 = new Object(); 162 CollisionLeaf<Key, Object> leaf = 163 new CollisionLeaf<>(key1, value1, key2, value2); 164 165 Node<Key, Object> ret = leaf.put(key3, value3, key3.hashCode(), 0); 166 assertTrue(ret instanceof CollisionLeaf); 167 assertSame(value1, ret.get(key1, key1.hashCode(), 0)); 168 assertSame(value2, ret.get(key2, key2.hashCode(), 0)); 169 assertSame(value3, ret.get(key3, key3.hashCode(), 0)); 170 171 assertSame(value1, leaf.get(key1, key1.hashCode(), 0)); 172 assertSame(value2, leaf.get(key2, key2.hashCode(), 0)); 173 assertSame(null, leaf.get(key3, key3.hashCode(), 0)); 174 175 assertEquals(2, leaf.size()); 176 assertEquals(3, ret.size()); 177 } 178 179 @Test compressedIndex_combine_differentIndexBit()180 public void compressedIndex_combine_differentIndexBit() { 181 final Key key1 = new Key(7); 182 final Key key2 = new Key(19); 183 final Object value1 = new Object(); 184 final Object value2 = new Object(); 185 Leaf<Key, Object> leaf1 = new Leaf<>(key1, value1); 186 Leaf<Key, Object> leaf2 = new Leaf<>(key2, value2); 187 class Verifier { 188 private void verify(Node<Key, Object> ret) { 189 CompressedIndex<Key, Object> collisionLeaf = (CompressedIndex<Key, Object>) ret; 190 assertEquals((1 << 7) | (1 << 19), collisionLeaf.bitmap); 191 assertEquals(2, collisionLeaf.values.length); 192 assertSame(value1, collisionLeaf.values[0].get(key1, key1.hashCode(), 0)); 193 assertSame(value2, collisionLeaf.values[1].get(key2, key2.hashCode(), 0)); 194 195 assertSame(value1, ret.get(key1, key1.hashCode(), 0)); 196 assertSame(value2, ret.get(key2, key2.hashCode(), 0)); 197 198 assertEquals(2, ret.size()); 199 } 200 } 201 202 Verifier verifier = new Verifier(); 203 verifier.verify(CompressedIndex.combine(leaf1, key1.hashCode(), leaf2, key2.hashCode(), 0)); 204 verifier.verify(CompressedIndex.combine(leaf2, key2.hashCode(), leaf1, key1.hashCode(), 0)); 205 206 assertEquals(1, leaf1.size()); 207 assertEquals(1, leaf2.size()); 208 } 209 210 @Test compressedIndex_combine_sameIndexBit()211 public void compressedIndex_combine_sameIndexBit() { 212 final Key key1 = new Key(17 << 5 | 1); // 5 bit regions: (17, 1) 213 final Key key2 = new Key(31 << 5 | 1); // 5 bit regions: (31, 1) 214 final Object value1 = new Object(); 215 final Object value2 = new Object(); 216 Leaf<Key, Object> leaf1 = new Leaf<>(key1, value1); 217 Leaf<Key, Object> leaf2 = new Leaf<>(key2, value2); 218 class Verifier { 219 private void verify(Node<Key, Object> ret) { 220 CompressedIndex<Key, Object> collisionInternal = (CompressedIndex<Key, Object>) ret; 221 assertEquals(1 << 1, collisionInternal.bitmap); 222 assertEquals(1, collisionInternal.values.length); 223 CompressedIndex<Key, Object> collisionLeaf = 224 (CompressedIndex<Key, Object>) collisionInternal.values[0]; 225 assertEquals((1 << 31) | (1 << 17), collisionLeaf.bitmap); 226 assertSame(value1, ret.get(key1, key1.hashCode(), 0)); 227 assertSame(value2, ret.get(key2, key2.hashCode(), 0)); 228 229 assertEquals(2, ret.size()); 230 } 231 } 232 233 Verifier verifier = new Verifier(); 234 verifier.verify(CompressedIndex.combine(leaf1, key1.hashCode(), leaf2, key2.hashCode, 0)); 235 verifier.verify(CompressedIndex.combine(leaf2, key2.hashCode(), leaf1, key1.hashCode, 0)); 236 237 assertEquals(1, leaf1.size()); 238 assertEquals(1, leaf2.size()); 239 } 240 241 /** 242 * A key with a settable hashcode. 243 */ 244 static final class Key { 245 private final int hashCode; 246 Key(int hashCode)247 Key(int hashCode) { 248 this.hashCode = hashCode; 249 } 250 251 @Override hashCode()252 public int hashCode() { 253 return hashCode; 254 } 255 256 @Override toString()257 public String toString() { 258 return String.format("Key(hashCode=%x)", hashCode); 259 } 260 } 261 } 262