1/* 2 * Copyright (C) 2008 The Guava 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 17package com.google.common.collect; 18 19import static com.google.common.base.Preconditions.checkArgument; 20 21import com.google.common.annotations.GwtCompatible; 22import com.google.common.collect.ImmutableSet.ArrayImmutableSet; 23import com.google.common.collect.ImmutableSet.TransformedImmutableSet; 24 25import javax.annotation.Nullable; 26import javax.annotation.concurrent.Immutable; 27 28/** 29 * Implementation of {@link ImmutableMap} with two or more entries. 30 * 31 * @author Jesse Wilson 32 * @author Kevin Bourrillion 33 * @author Gregory Kick 34 */ 35@GwtCompatible(serializable = true, emulated = true) 36final class RegularImmutableMap<K, V> extends ImmutableMap<K, V> { 37 38 // entries in insertion order 39 private final transient LinkedEntry<K, V>[] entries; 40 // array of linked lists of entries 41 private final transient LinkedEntry<K, V>[] table; 42 // 'and' with an int to get a table index 43 private final transient int mask; 44 private final transient int keySetHashCode; 45 46 // TODO(gak): investigate avoiding the creation of ImmutableEntries since we 47 // re-copy them anyway. 48 RegularImmutableMap(Entry<?, ?>... immutableEntries) { 49 int size = immutableEntries.length; 50 entries = createEntryArray(size); 51 52 int tableSize = chooseTableSize(size); 53 table = createEntryArray(tableSize); 54 mask = tableSize - 1; 55 56 int keySetHashCodeMutable = 0; 57 for (int entryIndex = 0; entryIndex < size; entryIndex++) { 58 // each of our 6 callers carefully put only Entry<K, V>s into the array! 59 @SuppressWarnings("unchecked") 60 Entry<K, V> entry = (Entry<K, V>) immutableEntries[entryIndex]; 61 K key = entry.getKey(); 62 int keyHashCode = key.hashCode(); 63 keySetHashCodeMutable += keyHashCode; 64 int tableIndex = Hashing.smear(keyHashCode) & mask; 65 @Nullable LinkedEntry<K, V> existing = table[tableIndex]; 66 // prepend, not append, so the entries can be immutable 67 LinkedEntry<K, V> linkedEntry = 68 newLinkedEntry(key, entry.getValue(), existing); 69 table[tableIndex] = linkedEntry; 70 entries[entryIndex] = linkedEntry; 71 while (existing != null) { 72 checkArgument(!key.equals(existing.getKey()), "duplicate key: %s", key); 73 existing = existing.next(); 74 } 75 } 76 keySetHashCode = keySetHashCodeMutable; 77 } 78 79 private static int chooseTableSize(int size) { 80 // least power of 2 greater than size 81 int tableSize = Integer.highestOneBit(size) << 1; 82 checkArgument(tableSize > 0, "table too large: %s", size); 83 return tableSize; 84 } 85 86 /** 87 * Creates a {@link LinkedEntry} array to hold parameterized entries. The 88 * result must never be upcast back to LinkedEntry[] (or Object[], etc.), or 89 * allowed to escape the class. 90 */ 91 @SuppressWarnings("unchecked") // Safe as long as the javadocs are followed 92 private LinkedEntry<K, V>[] createEntryArray(int size) { 93 return new LinkedEntry[size]; 94 } 95 96 private static <K, V> LinkedEntry<K, V> newLinkedEntry(K key, V value, 97 @Nullable LinkedEntry<K, V> next) { 98 return (next == null) 99 ? new TerminalEntry<K, V>(key, value) 100 : new NonTerminalEntry<K, V>(key, value, next); 101 } 102 103 private interface LinkedEntry<K, V> extends Entry<K, V> { 104 /** Returns the next entry in the list or {@code null} if none exists. */ 105 @Nullable LinkedEntry<K, V> next(); 106 } 107 108 /** {@code LinkedEntry} implementation that has a next value. */ 109 @Immutable 110 @SuppressWarnings("serial") // this class is never serialized 111 private static final class NonTerminalEntry<K, V> 112 extends ImmutableEntry<K, V> implements LinkedEntry<K, V> { 113 final LinkedEntry<K, V> next; 114 115 NonTerminalEntry(K key, V value, LinkedEntry<K, V> next) { 116 super(key, value); 117 this.next = next; 118 } 119 120 @Override public LinkedEntry<K, V> next() { 121 return next; 122 } 123 } 124 125 /** 126 * {@code LinkedEntry} implementation that serves as the last entry in the 127 * list. I.e. no next entry 128 */ 129 @Immutable 130 @SuppressWarnings("serial") // this class is never serialized 131 private static final class TerminalEntry<K, V> extends ImmutableEntry<K, V> 132 implements LinkedEntry<K, V> { 133 TerminalEntry(K key, V value) { 134 super(key, value); 135 } 136 137 @Nullable @Override public LinkedEntry<K, V> next() { 138 return null; 139 } 140 } 141 142 @Override public V get(@Nullable Object key) { 143 if (key == null) { 144 return null; 145 } 146 int index = Hashing.smear(key.hashCode()) & mask; 147 for (LinkedEntry<K, V> entry = table[index]; 148 entry != null; 149 entry = entry.next()) { 150 K candidateKey = entry.getKey(); 151 152 /* 153 * Assume that equals uses the == optimization when appropriate, and that 154 * it would check hash codes as an optimization when appropriate. If we 155 * did these things, it would just make things worse for the most 156 * performance-conscious users. 157 */ 158 if (key.equals(candidateKey)) { 159 return entry.getValue(); 160 } 161 } 162 return null; 163 } 164 165 @Override 166 public int size() { 167 return entries.length; 168 } 169 170 @Override public boolean isEmpty() { 171 return false; 172 } 173 174 @Override public boolean containsValue(@Nullable Object value) { 175 if (value == null) { 176 return false; 177 } 178 for (Entry<K, V> entry : entries) { 179 if (entry.getValue().equals(value)) { 180 return true; 181 } 182 } 183 return false; 184 } 185 186 @Override boolean isPartialView() { 187 return false; 188 } 189 190 private transient ImmutableSet<Entry<K, V>> entrySet; 191 192 @Override public ImmutableSet<Entry<K, V>> entrySet() { 193 ImmutableSet<Entry<K, V>> es = entrySet; 194 return (es == null) ? (entrySet = new EntrySet<K, V>(this)) : es; 195 } 196 197 @SuppressWarnings("serial") // uses writeReplace(), not default serialization 198 private static class EntrySet<K, V> extends ArrayImmutableSet<Entry<K, V>> { 199 final transient RegularImmutableMap<K, V> map; 200 201 EntrySet(RegularImmutableMap<K, V> map) { 202 super(map.entries); 203 this.map = map; 204 } 205 206 @Override public boolean contains(Object target) { 207 if (target instanceof Entry) { 208 Entry<?, ?> entry = (Entry<?, ?>) target; 209 V mappedValue = map.get(entry.getKey()); 210 return mappedValue != null && mappedValue.equals(entry.getValue()); 211 } 212 return false; 213 } 214 } 215 216 private transient ImmutableSet<K> keySet; 217 218 @Override public ImmutableSet<K> keySet() { 219 ImmutableSet<K> ks = keySet; 220 return (ks == null) ? (keySet = new KeySet<K, V>(this)) : ks; 221 } 222 223 @SuppressWarnings("serial") // uses writeReplace(), not default serialization 224 private static class KeySet<K, V> 225 extends TransformedImmutableSet<Entry<K, V>, K> { 226 final RegularImmutableMap<K, V> map; 227 228 KeySet(RegularImmutableMap<K, V> map) { 229 super(map.entries, map.keySetHashCode); 230 this.map = map; 231 } 232 233 @Override K transform(Entry<K, V> element) { 234 return element.getKey(); 235 } 236 237 @Override public boolean contains(Object target) { 238 return map.containsKey(target); 239 } 240 241 @Override boolean isPartialView() { 242 return true; 243 } 244 } 245 246 private transient ImmutableCollection<V> values; 247 248 @Override public ImmutableCollection<V> values() { 249 ImmutableCollection<V> v = values; 250 return (v == null) ? (values = new Values<V>(this)) : v; 251 } 252 253 @SuppressWarnings("serial") // uses writeReplace(), not default serialization 254 private static class Values<V> extends ImmutableCollection<V> { 255 final RegularImmutableMap<?, V> map; 256 257 Values(RegularImmutableMap<?, V> map) { 258 this.map = map; 259 } 260 261 @Override 262 public int size() { 263 return map.entries.length; 264 } 265 266 @Override public UnmodifiableIterator<V> iterator() { 267 return new AbstractIndexedListIterator<V>(map.entries.length) { 268 @Override protected V get(int index) { 269 return map.entries[index].getValue(); 270 } 271 }; 272 } 273 274 @Override public boolean contains(Object target) { 275 return map.containsValue(target); 276 } 277 278 @Override boolean isPartialView() { 279 return true; 280 } 281 } 282 283 @Override public String toString() { 284 StringBuilder result 285 = Collections2.newStringBuilderForCollection(size()).append('{'); 286 Collections2.STANDARD_JOINER.appendTo(result, entries); 287 return result.append('}').toString(); 288 } 289 290 // This class is never actually serialized directly, but we have to make the 291 // warning go away (and suppressing would suppress for all nested classes too) 292 private static final long serialVersionUID = 0; 293} 294