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 java.util.Arrays; 20 21 /** 22 * A persistent (copy-on-write) hash tree/trie. Collisions are handled 23 * linearly. Delete is not supported, but replacement is. The implementation 24 * favors simplicity and low memory allocation during insertion. Although the 25 * asymptotics are good, it is optimized for small sizes like less than 20; 26 * "unbelievably large" would be 100. 27 * 28 * <p>Inspired by popcnt-based compression seen in Ideal Hash Trees, Phil 29 * Bagwell (2000). The rest of the implementation is ignorant of/ignores the 30 * paper. 31 */ 32 final class PersistentHashArrayMappedTrie<K,V> { 33 private final Node<K,V> root; 34 35 PersistentHashArrayMappedTrie() { 36 this(null); 37 } 38 39 private PersistentHashArrayMappedTrie(Node<K,V> root) { 40 this.root = root; 41 } 42 43 public int size() { 44 if (root == null) { 45 return 0; 46 } 47 return root.size(); 48 } 49 50 /** 51 * Returns the value with the specified key, or {@code null} if it does not exist. 52 */ 53 public V get(K key) { 54 if (root == null) { 55 return null; 56 } 57 return root.get(key, key.hashCode(), 0); 58 } 59 60 /** 61 * Returns a new trie where the key is set to the specified value. 62 */ 63 public PersistentHashArrayMappedTrie<K,V> put(K key, V value) { 64 if (root == null) { 65 return new PersistentHashArrayMappedTrie<K,V>(new Leaf<K,V>(key, value)); 66 } else { 67 return new PersistentHashArrayMappedTrie<K,V>(root.put(key, value, key.hashCode(), 0)); 68 } 69 } 70 71 // Not actually annotated to avoid depending on guava 72 // @VisibleForTesting 73 static final class Leaf<K,V> implements Node<K,V> { 74 private final K key; 75 private final V value; 76 77 public Leaf(K key, V value) { 78 this.key = key; 79 this.value = value; 80 } 81 82 @Override 83 public int size() { 84 return 1; 85 } 86 87 @Override 88 public V get(K key, int hash, int bitsConsumed) { 89 if (this.key == key) { 90 return value; 91 } else { 92 return null; 93 } 94 } 95 96 @Override 97 public Node<K,V> put(K key, V value, int hash, int bitsConsumed) { 98 int thisHash = this.key.hashCode(); 99 if (thisHash != hash) { 100 // Insert 101 return CompressedIndex.combine( 102 new Leaf<K,V>(key, value), hash, this, thisHash, bitsConsumed); 103 } else if (this.key == key) { 104 // Replace 105 return new Leaf<K,V>(key, value); 106 } else { 107 // Hash collision 108 return new CollisionLeaf<K,V>(this.key, this.value, key, value); 109 } 110 } 111 112 @Override 113 public String toString() { 114 return String.format("Leaf(key=%s value=%s)", key, value); 115 } 116 } 117 118 // Not actually annotated to avoid depending on guava 119 // @VisibleForTesting 120 static final class CollisionLeaf<K,V> implements Node<K,V> { 121 // All keys must have same hash, but not have the same reference 122 private final K[] keys; 123 private final V[] values; 124 125 // Not actually annotated to avoid depending on guava 126 // @VisibleForTesting 127 @SuppressWarnings("unchecked") 128 CollisionLeaf(K key1, V value1, K key2, V value2) { 129 this((K[]) new Object[] {key1, key2}, (V[]) new Object[] {value1, value2}); 130 assert key1 != key2; 131 assert key1.hashCode() == key2.hashCode(); 132 } 133 134 private CollisionLeaf(K[] keys, V[] values) { 135 this.keys = keys; 136 this.values = values; 137 } 138 139 @Override 140 public int size() { 141 return values.length; 142 } 143 144 @Override 145 public V get(K key, int hash, int bitsConsumed) { 146 for (int i = 0; i < keys.length; i++) { 147 if (keys[i] == key) { 148 return values[i]; 149 } 150 } 151 return null; 152 } 153 154 @Override 155 public Node<K,V> put(K key, V value, int hash, int bitsConsumed) { 156 int thisHash = keys[0].hashCode(); 157 int keyIndex; 158 if (thisHash != hash) { 159 // Insert 160 return CompressedIndex.combine( 161 new Leaf<K,V>(key, value), hash, this, thisHash, bitsConsumed); 162 } else if ((keyIndex = indexOfKey(key)) != -1) { 163 // Replace 164 K[] newKeys = Arrays.copyOf(keys, keys.length); 165 V[] newValues = Arrays.copyOf(values, keys.length); 166 newKeys[keyIndex] = key; 167 newValues[keyIndex] = value; 168 return new CollisionLeaf<K,V>(newKeys, newValues); 169 } else { 170 // Yet another hash collision 171 K[] newKeys = Arrays.copyOf(keys, keys.length + 1); 172 V[] newValues = Arrays.copyOf(values, keys.length + 1); 173 newKeys[keys.length] = key; 174 newValues[keys.length] = value; 175 return new CollisionLeaf<K,V>(newKeys, newValues); 176 } 177 } 178 179 // -1 if not found 180 private int indexOfKey(K key) { 181 for (int i = 0; i < keys.length; i++) { 182 if (keys[i] == key) { 183 return i; 184 } 185 } 186 return -1; 187 } 188 189 @Override 190 public String toString() { 191 StringBuilder valuesSb = new StringBuilder(); 192 valuesSb.append("CollisionLeaf("); 193 for (int i = 0; i < values.length; i++) { 194 valuesSb.append("(key=").append(keys[i]).append(" value=").append(values[i]).append(") "); 195 } 196 return valuesSb.append(")").toString(); 197 } 198 } 199 200 // Not actually annotated to avoid depending on guava 201 // @VisibleForTesting 202 static final class CompressedIndex<K,V> implements Node<K,V> { 203 private static final int BITS = 5; 204 private static final int BITS_MASK = 0x1F; 205 206 final int bitmap; 207 final Node<K,V>[] values; 208 private final int size; 209 210 private CompressedIndex(int bitmap, Node<K,V>[] values, int size) { 211 this.bitmap = bitmap; 212 this.values = values; 213 this.size = size; 214 } 215 216 @Override 217 public int size() { 218 return size; 219 } 220 221 @Override 222 public V get(K key, int hash, int bitsConsumed) { 223 int indexBit = indexBit(hash, bitsConsumed); 224 if ((bitmap & indexBit) == 0) { 225 return null; 226 } 227 int compressedIndex = compressedIndex(indexBit); 228 return values[compressedIndex].get(key, hash, bitsConsumed + BITS); 229 } 230 231 @Override 232 public Node<K,V> put(K key, V value, int hash, int bitsConsumed) { 233 int indexBit = indexBit(hash, bitsConsumed); 234 int compressedIndex = compressedIndex(indexBit); 235 if ((bitmap & indexBit) == 0) { 236 // Insert 237 int newBitmap = bitmap | indexBit; 238 @SuppressWarnings("unchecked") 239 Node<K,V>[] newValues = (Node<K,V>[]) new Node<?,?>[values.length + 1]; 240 System.arraycopy(values, 0, newValues, 0, compressedIndex); 241 newValues[compressedIndex] = new Leaf<K,V>(key, value); 242 System.arraycopy( 243 values, 244 compressedIndex, 245 newValues, 246 compressedIndex + 1, 247 values.length - compressedIndex); 248 return new CompressedIndex<K,V>(newBitmap, newValues, size() + 1); 249 } else { 250 // Replace 251 Node<K,V>[] newValues = Arrays.copyOf(values, values.length); 252 newValues[compressedIndex] = 253 values[compressedIndex].put(key, value, hash, bitsConsumed + BITS); 254 int newSize = size(); 255 newSize += newValues[compressedIndex].size(); 256 newSize -= values[compressedIndex].size(); 257 return new CompressedIndex<K,V>(bitmap, newValues, newSize); 258 } 259 } 260 261 static <K,V> Node<K,V> combine( 262 Node<K,V> node1, int hash1, Node<K,V> node2, int hash2, int bitsConsumed) { 263 assert hash1 != hash2; 264 int indexBit1 = indexBit(hash1, bitsConsumed); 265 int indexBit2 = indexBit(hash2, bitsConsumed); 266 if (indexBit1 == indexBit2) { 267 Node<K,V> node = combine(node1, hash1, node2, hash2, bitsConsumed + BITS); 268 @SuppressWarnings("unchecked") 269 Node<K,V>[] values = (Node<K,V>[]) new Node<?,?>[] {node}; 270 return new CompressedIndex<K,V>(indexBit1, values, node.size()); 271 } else { 272 // Make node1 the smallest 273 if (uncompressedIndex(hash1, bitsConsumed) > uncompressedIndex(hash2, bitsConsumed)) { 274 Node<K,V> nodeCopy = node1; 275 node1 = node2; 276 node2 = nodeCopy; 277 } 278 @SuppressWarnings("unchecked") 279 Node<K,V>[] values = (Node<K,V>[]) new Node<?,?>[] {node1, node2}; 280 return new CompressedIndex<K,V>(indexBit1 | indexBit2, values, node1.size() + node2.size()); 281 } 282 } 283 284 @Override 285 public String toString() { 286 StringBuilder valuesSb = new StringBuilder(); 287 valuesSb.append("CompressedIndex(") 288 .append(String.format("bitmap=%s ", Integer.toBinaryString(bitmap))); 289 for (Node<K, V> value : values) { 290 valuesSb.append(value).append(" "); 291 } 292 return valuesSb.append(")").toString(); 293 } 294 295 private int compressedIndex(int indexBit) { 296 return Integer.bitCount(bitmap & (indexBit - 1)); 297 } 298 299 private static int uncompressedIndex(int hash, int bitsConsumed) { 300 return (hash >>> bitsConsumed) & BITS_MASK; 301 } 302 303 private static int indexBit(int hash, int bitsConsumed) { 304 int uncompressedIndex = uncompressedIndex(hash, bitsConsumed); 305 return 1 << uncompressedIndex; 306 } 307 } 308 309 interface Node<K,V> { 310 V get(K key, int hash, int bitsConsumed); 311 312 Node<K,V> put(K key, V value, int hash, int bitsConsumed); 313 314 int size(); 315 } 316 } 317