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 17 package com.google.common.collect; 18 19 import static com.google.common.collect.CollectPreconditions.checkEntryNotNull; 20 21 import com.google.common.annotations.GwtCompatible; 22 import com.google.common.collect.ImmutableMapEntry.TerminalEntry; 23 24 import javax.annotation.Nullable; 25 26 /** 27 * Implementation of {@link ImmutableMap} with two or more entries. 28 * 29 * @author Jesse Wilson 30 * @author Kevin Bourrillion 31 * @author Gregory Kick 32 */ 33 @GwtCompatible(serializable = true, emulated = true) 34 final class RegularImmutableMap<K, V> extends ImmutableMap<K, V> { 35 36 // entries in insertion order 37 private final transient ImmutableMapEntry<K, V>[] entries; 38 // array of linked lists of entries 39 private final transient ImmutableMapEntry<K, V>[] table; 40 // 'and' with an int to get a table index 41 private final transient int mask; 42 43 RegularImmutableMap(TerminalEntry<?, ?>... theEntries) { 44 this(theEntries.length, theEntries); 45 } 46 47 /** 48 * Constructor for RegularImmutableMap that takes as input an array of {@code TerminalEntry} 49 * entries. Assumes that these entries have already been checked for null. 50 * 51 * <p>This allows reuse of the entry objects from the array in the actual implementation. 52 */ 53 RegularImmutableMap(int size, TerminalEntry<?, ?>[] theEntries) { 54 entries = createEntryArray(size); 55 int tableSize = Hashing.closedTableSize(size, MAX_LOAD_FACTOR); 56 table = createEntryArray(tableSize); 57 mask = tableSize - 1; 58 for (int entryIndex = 0; entryIndex < size; entryIndex++) { 59 @SuppressWarnings("unchecked") 60 TerminalEntry<K, V> entry = (TerminalEntry<K, V>) theEntries[entryIndex]; 61 K key = entry.getKey(); 62 int tableIndex = Hashing.smear(key.hashCode()) & mask; 63 @Nullable ImmutableMapEntry<K, V> existing = table[tableIndex]; 64 // prepend, not append, so the entries can be immutable 65 ImmutableMapEntry<K, V> newEntry = (existing == null) 66 ? entry 67 : new NonTerminalMapEntry<K, V>(entry, existing); 68 table[tableIndex] = newEntry; 69 entries[entryIndex] = newEntry; 70 checkNoConflictInBucket(key, newEntry, existing); 71 } 72 } 73 74 /** 75 * Constructor for RegularImmutableMap that makes no assumptions about the input entries. 76 */ 77 RegularImmutableMap(Entry<?, ?>[] theEntries) { 78 int size = theEntries.length; 79 entries = createEntryArray(size); 80 int tableSize = Hashing.closedTableSize(size, MAX_LOAD_FACTOR); 81 table = createEntryArray(tableSize); 82 mask = tableSize - 1; 83 for (int entryIndex = 0; entryIndex < size; entryIndex++) { 84 @SuppressWarnings("unchecked") // all our callers carefully put in only Entry<K, V>s 85 Entry<K, V> entry = (Entry<K, V>) theEntries[entryIndex]; 86 K key = entry.getKey(); 87 V value = entry.getValue(); 88 checkEntryNotNull(key, value); 89 int tableIndex = Hashing.smear(key.hashCode()) & mask; 90 @Nullable ImmutableMapEntry<K, V> existing = table[tableIndex]; 91 // prepend, not append, so the entries can be immutable 92 ImmutableMapEntry<K, V> newEntry = (existing == null) 93 ? new TerminalEntry<K, V>(key, value) 94 : new NonTerminalMapEntry<K, V>(key, value, existing); 95 table[tableIndex] = newEntry; 96 entries[entryIndex] = newEntry; 97 checkNoConflictInBucket(key, newEntry, existing); 98 } 99 } 100 101 private void checkNoConflictInBucket( 102 K key, ImmutableMapEntry<K, V> entry, ImmutableMapEntry<K, V> bucketHead) { 103 for (; bucketHead != null; bucketHead = bucketHead.getNextInKeyBucket()) { 104 checkNoConflict(!key.equals(bucketHead.getKey()), "key", entry, bucketHead); 105 } 106 } 107 108 private static final class NonTerminalMapEntry<K, V> extends ImmutableMapEntry<K, V> { 109 private final ImmutableMapEntry<K, V> nextInKeyBucket; 110 111 NonTerminalMapEntry(K key, V value, ImmutableMapEntry<K, V> nextInKeyBucket) { 112 super(key, value); 113 this.nextInKeyBucket = nextInKeyBucket; 114 } 115 116 NonTerminalMapEntry(ImmutableMapEntry<K, V> contents, ImmutableMapEntry<K, V> nextInKeyBucket) { 117 super(contents); 118 this.nextInKeyBucket = nextInKeyBucket; 119 } 120 121 @Override 122 ImmutableMapEntry<K, V> getNextInKeyBucket() { 123 return nextInKeyBucket; 124 } 125 126 @Override 127 @Nullable 128 ImmutableMapEntry<K, V> getNextInValueBucket() { 129 return null; 130 } 131 132 } 133 134 /** 135 * Closed addressing tends to perform well even with high load factors. 136 * Being conservative here ensures that the table is still likely to be 137 * relatively sparse (hence it misses fast) while saving space. 138 */ 139 private static final double MAX_LOAD_FACTOR = 1.2; 140 141 /** 142 * Creates an {@code ImmutableMapEntry} array to hold parameterized entries. The 143 * result must never be upcast back to ImmutableMapEntry[] (or Object[], etc.), or 144 * allowed to escape the class. 145 */ 146 @SuppressWarnings("unchecked") // Safe as long as the javadocs are followed 147 private ImmutableMapEntry<K, V>[] createEntryArray(int size) { 148 return new ImmutableMapEntry[size]; 149 } 150 151 @Override public V get(@Nullable Object key) { 152 if (key == null) { 153 return null; 154 } 155 int index = Hashing.smear(key.hashCode()) & mask; 156 for (ImmutableMapEntry<K, V> entry = table[index]; 157 entry != null; 158 entry = entry.getNextInKeyBucket()) { 159 K candidateKey = entry.getKey(); 160 161 /* 162 * Assume that equals uses the == optimization when appropriate, and that 163 * it would check hash codes as an optimization when appropriate. If we 164 * did these things, it would just make things worse for the most 165 * performance-conscious users. 166 */ 167 if (key.equals(candidateKey)) { 168 return entry.getValue(); 169 } 170 } 171 return null; 172 } 173 174 @Override 175 public int size() { 176 return entries.length; 177 } 178 179 @Override boolean isPartialView() { 180 return false; 181 } 182 183 @Override 184 ImmutableSet<Entry<K, V>> createEntrySet() { 185 return new EntrySet(); 186 } 187 188 @SuppressWarnings("serial") // uses writeReplace(), not default serialization 189 private class EntrySet extends ImmutableMapEntrySet<K, V> { 190 @Override ImmutableMap<K, V> map() { 191 return RegularImmutableMap.this; 192 } 193 194 @Override 195 public UnmodifiableIterator<Entry<K, V>> iterator() { 196 return asList().iterator(); 197 } 198 199 @Override 200 ImmutableList<Entry<K, V>> createAsList() { 201 return new RegularImmutableAsList<Entry<K, V>>(this, entries); 202 } 203 } 204 205 // This class is never actually serialized directly, but we have to make the 206 // warning go away (and suppressing would suppress for all nested classes too) 207 private static final long serialVersionUID = 0; 208 } 209