1 /* 2 * Copyright (C) 2008 Google Inc. 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 com.google.common.annotations.GwtCompatible; 20 import com.google.common.collect.ImmutableSet.ArrayImmutableSet; 21 import com.google.common.collect.ImmutableSet.TransformedImmutableSet; 22 23 import static com.google.common.base.Preconditions.checkNotNull; 24 25 /** 26 * Implementation of {@link ImmutableMap} with two or more entries. 27 * 28 * @author Jesse Wilson 29 * @author Kevin Bourrillion 30 */ 31 @GwtCompatible(serializable = true) 32 final class RegularImmutableMap<K, V> extends ImmutableMap<K, V> { 33 34 private final transient Entry<K, V>[] entries; // entries in insertion order 35 private final transient Object[] table; // alternating keys and values 36 // 'and' with an int then shift to get a table index 37 private final transient int mask; 38 private final transient int keySetHashCode; 39 40 RegularImmutableMap(Entry<?, ?>... immutableEntries) { 41 // each of our 6 callers carefully put only Entry<K, V>s into the array! 42 // checkNotNull for GWT. 43 @SuppressWarnings("unchecked") 44 Entry<K, V>[] tmp = (Entry<K, V>[]) checkNotNull(immutableEntries); 45 this.entries = tmp; 46 47 int tableSize = Hashing.chooseTableSize(immutableEntries.length); 48 table = new Object[tableSize * 2]; 49 mask = tableSize - 1; 50 51 int keySetHashCodeMutable = 0; 52 for (Entry<K, V> entry : this.entries) { 53 checkNotNull(entry); // checkNotNull for GWT. 54 K key = checkNotNull(entry.getKey()); // checkNotNull for GWT. 55 int keyHashCode = key.hashCode(); 56 for (int i = Hashing.smear(keyHashCode); true; i++) { 57 int index = (i & mask) * 2; 58 Object existing = table[index]; 59 if (existing == null) { 60 V value = checkNotNull(entry.getValue()); // checkNotNull for GWT. 61 table[index] = key; 62 table[index + 1] = value; 63 keySetHashCodeMutable += keyHashCode; 64 break; 65 } else if (existing.equals(key)) { 66 throw new IllegalArgumentException("duplicate key: " + key); 67 } 68 } 69 } 70 keySetHashCode = keySetHashCodeMutable; 71 } 72 73 @Override public V get(Object key) { 74 if (key == null) { 75 return null; 76 } 77 for (int i = Hashing.smear(key.hashCode()); true; i++) { 78 int index = (i & mask) * 2; 79 Object candidate = table[index]; 80 if (candidate == null) { 81 return null; 82 } 83 if (candidate.equals(key)) { 84 // we're careful to store only V's at odd indices 85 @SuppressWarnings("unchecked") 86 V value = (V) table[index + 1]; 87 return value; 88 } 89 } 90 } 91 92 public int size() { 93 return entries.length; 94 } 95 96 @Override public boolean isEmpty() { 97 return false; 98 } 99 100 @Override public boolean containsValue(Object value) { 101 if (value == null) { 102 return false; 103 } 104 for (Entry<K, V> entry : entries) { 105 if (entry.getValue().equals(value)) { 106 return true; 107 } 108 } 109 return false; 110 } 111 112 // TODO: Serialization of the map views should serialize the map, and 113 // deserialization should call entrySet(), keySet(), or values() on the 114 // deserialized map. The views are serializable since the Immutable* classes 115 // are. 116 117 private transient ImmutableSet<Entry<K, V>> entrySet; 118 119 @Override public ImmutableSet<Entry<K, V>> entrySet() { 120 ImmutableSet<Entry<K, V>> es = entrySet; 121 return (es == null) ? (entrySet = new EntrySet<K, V>(this)) : es; 122 } 123 124 @SuppressWarnings("serial") // uses writeReplace(), not default serialization 125 private static class EntrySet<K, V> extends ArrayImmutableSet<Entry<K, V>> { 126 final transient RegularImmutableMap<K, V> map; 127 128 EntrySet(RegularImmutableMap<K, V> map) { 129 super(map.entries); 130 this.map = map; 131 } 132 133 @Override public boolean contains(Object target) { 134 if (target instanceof Entry) { 135 Entry<?, ?> entry = (Entry<?, ?>) target; 136 V mappedValue = map.get(entry.getKey()); 137 return mappedValue != null && mappedValue.equals(entry.getValue()); 138 } 139 return false; 140 } 141 } 142 143 private transient ImmutableSet<K> keySet; 144 145 @Override public ImmutableSet<K> keySet() { 146 ImmutableSet<K> ks = keySet; 147 return (ks == null) ? (keySet = new KeySet<K, V>(this)) : ks; 148 } 149 150 @SuppressWarnings("serial") // uses writeReplace(), not default serialization 151 private static class KeySet<K, V> 152 extends TransformedImmutableSet<Entry<K, V>, K> { 153 final RegularImmutableMap<K, V> map; 154 155 KeySet(RegularImmutableMap<K, V> map) { 156 super(map.entries, map.keySetHashCode); 157 this.map = map; 158 } 159 160 @Override K transform(Entry<K, V> element) { 161 return element.getKey(); 162 } 163 164 @Override public boolean contains(Object target) { 165 return map.containsKey(target); 166 } 167 } 168 169 private transient ImmutableCollection<V> values; 170 171 @Override public ImmutableCollection<V> values() { 172 ImmutableCollection<V> v = values; 173 return (v == null) ? (values = new Values<V>(this)) : v; 174 } 175 176 @SuppressWarnings("serial") // uses writeReplace(), not default serialization 177 private static class Values<V> extends ImmutableCollection<V> { 178 final RegularImmutableMap<?, V> map; 179 180 Values(RegularImmutableMap<?, V> map) { 181 this.map = map; 182 } 183 184 public int size() { 185 return map.entries.length; 186 } 187 188 @Override public UnmodifiableIterator<V> iterator() { 189 return new AbstractIterator<V>() { 190 int index = 0; 191 @Override protected V computeNext() { 192 return (index < map.entries.length) 193 ? map.entries[index++].getValue() 194 : endOfData(); 195 } 196 }; 197 } 198 199 @Override public boolean contains(Object target) { 200 return map.containsValue(target); 201 } 202 } 203 204 @Override public String toString() { 205 StringBuilder result = new StringBuilder(size() * 16).append('{'); 206 Collections2.standardJoiner.appendTo(result, entries); 207 return result.append('}').toString(); 208 } 209 210 // This class is never actually serialized directly, but we have to make the 211 // warning go away (and suppressing would suppress for all nested classes too) 212 private static final long serialVersionUID = 0; 213 } 214