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