11d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert/* 20888a09821a98ac0680fad765217302858e70fa4Paul Duffin* Copyright (C) 2008 The Guava Authors 31d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * 41d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * Licensed under the Apache License, Version 2.0 (the "License"); 51d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * you may not use this file except in compliance with the License. 61d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * You may obtain a copy of the License at 71d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * 81d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * http://www.apache.org/licenses/LICENSE-2.0 91d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * 101d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * Unless required by applicable law or agreed to in writing, software 111d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * distributed under the License is distributed on an "AS IS" BASIS, 121d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 131d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * See the License for the specific language governing permissions and 141d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * limitations under the License. 151d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert */ 161d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 171d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringertpackage com.google.common.collect; 181d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 190888a09821a98ac0680fad765217302858e70fa4Paul Duffinimport static com.google.common.collect.CollectPreconditions.checkEntryNotNull; 201d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 211d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringertimport com.google.common.annotations.GwtCompatible; 220888a09821a98ac0680fad765217302858e70fa4Paul Duffinimport com.google.common.collect.ImmutableMapEntry.TerminalEntry; 231d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 241d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringertimport javax.annotation.Nullable; 251d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 261d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert/** 271d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * Implementation of {@link ImmutableMap} with two or more entries. 281d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * 291d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * @author Jesse Wilson 301d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * @author Kevin Bourrillion 311d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * @author Gregory Kick 321d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert */ 331d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert@GwtCompatible(serializable = true, emulated = true) 341d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringertfinal class RegularImmutableMap<K, V> extends ImmutableMap<K, V> { 351d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 361d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert // entries in insertion order 370888a09821a98ac0680fad765217302858e70fa4Paul Duffin private final transient ImmutableMapEntry<K, V>[] entries; 381d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert // array of linked lists of entries 390888a09821a98ac0680fad765217302858e70fa4Paul Duffin private final transient ImmutableMapEntry<K, V>[] table; 401d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert // 'and' with an int to get a table index 411d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert private final transient int mask; 420888a09821a98ac0680fad765217302858e70fa4Paul Duffin 430888a09821a98ac0680fad765217302858e70fa4Paul Duffin RegularImmutableMap(TerminalEntry<?, ?>... theEntries) { 440888a09821a98ac0680fad765217302858e70fa4Paul Duffin this(theEntries.length, theEntries); 450888a09821a98ac0680fad765217302858e70fa4Paul Duffin } 460888a09821a98ac0680fad765217302858e70fa4Paul Duffin 470888a09821a98ac0680fad765217302858e70fa4Paul Duffin /** 480888a09821a98ac0680fad765217302858e70fa4Paul Duffin * Constructor for RegularImmutableMap that takes as input an array of {@code TerminalEntry} 490888a09821a98ac0680fad765217302858e70fa4Paul Duffin * entries. Assumes that these entries have already been checked for null. 500888a09821a98ac0680fad765217302858e70fa4Paul Duffin * 510888a09821a98ac0680fad765217302858e70fa4Paul Duffin * <p>This allows reuse of the entry objects from the array in the actual implementation. 520888a09821a98ac0680fad765217302858e70fa4Paul Duffin */ 530888a09821a98ac0680fad765217302858e70fa4Paul Duffin RegularImmutableMap(int size, TerminalEntry<?, ?>[] theEntries) { 541d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert entries = createEntryArray(size); 557dd252788645e940eada959bdde927426e2531c9Paul Duffin int tableSize = Hashing.closedTableSize(size, MAX_LOAD_FACTOR); 561d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert table = createEntryArray(tableSize); 571d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert mask = tableSize - 1; 581d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert for (int entryIndex = 0; entryIndex < size; entryIndex++) { 591d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @SuppressWarnings("unchecked") 600888a09821a98ac0680fad765217302858e70fa4Paul Duffin TerminalEntry<K, V> entry = (TerminalEntry<K, V>) theEntries[entryIndex]; 611d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert K key = entry.getKey(); 620888a09821a98ac0680fad765217302858e70fa4Paul Duffin int tableIndex = Hashing.smear(key.hashCode()) & mask; 630888a09821a98ac0680fad765217302858e70fa4Paul Duffin @Nullable ImmutableMapEntry<K, V> existing = table[tableIndex]; 641d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert // prepend, not append, so the entries can be immutable 650888a09821a98ac0680fad765217302858e70fa4Paul Duffin ImmutableMapEntry<K, V> newEntry = (existing == null) 660888a09821a98ac0680fad765217302858e70fa4Paul Duffin ? entry 670888a09821a98ac0680fad765217302858e70fa4Paul Duffin : new NonTerminalMapEntry<K, V>(entry, existing); 680888a09821a98ac0680fad765217302858e70fa4Paul Duffin table[tableIndex] = newEntry; 690888a09821a98ac0680fad765217302858e70fa4Paul Duffin entries[entryIndex] = newEntry; 700888a09821a98ac0680fad765217302858e70fa4Paul Duffin checkNoConflictInBucket(key, newEntry, existing); 711d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 721d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 730888a09821a98ac0680fad765217302858e70fa4Paul Duffin 747dd252788645e940eada959bdde927426e2531c9Paul Duffin /** 750888a09821a98ac0680fad765217302858e70fa4Paul Duffin * Constructor for RegularImmutableMap that makes no assumptions about the input entries. 761d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert */ 770888a09821a98ac0680fad765217302858e70fa4Paul Duffin RegularImmutableMap(Entry<?, ?>[] theEntries) { 780888a09821a98ac0680fad765217302858e70fa4Paul Duffin int size = theEntries.length; 790888a09821a98ac0680fad765217302858e70fa4Paul Duffin entries = createEntryArray(size); 800888a09821a98ac0680fad765217302858e70fa4Paul Duffin int tableSize = Hashing.closedTableSize(size, MAX_LOAD_FACTOR); 810888a09821a98ac0680fad765217302858e70fa4Paul Duffin table = createEntryArray(tableSize); 820888a09821a98ac0680fad765217302858e70fa4Paul Duffin mask = tableSize - 1; 830888a09821a98ac0680fad765217302858e70fa4Paul Duffin for (int entryIndex = 0; entryIndex < size; entryIndex++) { 840888a09821a98ac0680fad765217302858e70fa4Paul Duffin @SuppressWarnings("unchecked") // all our callers carefully put in only Entry<K, V>s 850888a09821a98ac0680fad765217302858e70fa4Paul Duffin Entry<K, V> entry = (Entry<K, V>) theEntries[entryIndex]; 860888a09821a98ac0680fad765217302858e70fa4Paul Duffin K key = entry.getKey(); 870888a09821a98ac0680fad765217302858e70fa4Paul Duffin V value = entry.getValue(); 880888a09821a98ac0680fad765217302858e70fa4Paul Duffin checkEntryNotNull(key, value); 890888a09821a98ac0680fad765217302858e70fa4Paul Duffin int tableIndex = Hashing.smear(key.hashCode()) & mask; 900888a09821a98ac0680fad765217302858e70fa4Paul Duffin @Nullable ImmutableMapEntry<K, V> existing = table[tableIndex]; 910888a09821a98ac0680fad765217302858e70fa4Paul Duffin // prepend, not append, so the entries can be immutable 920888a09821a98ac0680fad765217302858e70fa4Paul Duffin ImmutableMapEntry<K, V> newEntry = (existing == null) 930888a09821a98ac0680fad765217302858e70fa4Paul Duffin ? new TerminalEntry<K, V>(key, value) 940888a09821a98ac0680fad765217302858e70fa4Paul Duffin : new NonTerminalMapEntry<K, V>(key, value, existing); 950888a09821a98ac0680fad765217302858e70fa4Paul Duffin table[tableIndex] = newEntry; 960888a09821a98ac0680fad765217302858e70fa4Paul Duffin entries[entryIndex] = newEntry; 970888a09821a98ac0680fad765217302858e70fa4Paul Duffin checkNoConflictInBucket(key, newEntry, existing); 980888a09821a98ac0680fad765217302858e70fa4Paul Duffin } 991d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 1001d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 1010888a09821a98ac0680fad765217302858e70fa4Paul Duffin private void checkNoConflictInBucket( 1020888a09821a98ac0680fad765217302858e70fa4Paul Duffin K key, ImmutableMapEntry<K, V> entry, ImmutableMapEntry<K, V> bucketHead) { 1030888a09821a98ac0680fad765217302858e70fa4Paul Duffin for (; bucketHead != null; bucketHead = bucketHead.getNextInKeyBucket()) { 1040888a09821a98ac0680fad765217302858e70fa4Paul Duffin checkNoConflict(!key.equals(bucketHead.getKey()), "key", entry, bucketHead); 1050888a09821a98ac0680fad765217302858e70fa4Paul Duffin } 1061d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 1070888a09821a98ac0680fad765217302858e70fa4Paul Duffin 1080888a09821a98ac0680fad765217302858e70fa4Paul Duffin private static final class NonTerminalMapEntry<K, V> extends ImmutableMapEntry<K, V> { 1090888a09821a98ac0680fad765217302858e70fa4Paul Duffin private final ImmutableMapEntry<K, V> nextInKeyBucket; 1101d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 1110888a09821a98ac0680fad765217302858e70fa4Paul Duffin NonTerminalMapEntry(K key, V value, ImmutableMapEntry<K, V> nextInKeyBucket) { 1121d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert super(key, value); 1130888a09821a98ac0680fad765217302858e70fa4Paul Duffin this.nextInKeyBucket = nextInKeyBucket; 1141d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 1151d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 1160888a09821a98ac0680fad765217302858e70fa4Paul Duffin NonTerminalMapEntry(ImmutableMapEntry<K, V> contents, ImmutableMapEntry<K, V> nextInKeyBucket) { 1170888a09821a98ac0680fad765217302858e70fa4Paul Duffin super(contents); 1180888a09821a98ac0680fad765217302858e70fa4Paul Duffin this.nextInKeyBucket = nextInKeyBucket; 1191d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 1201d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 1210888a09821a98ac0680fad765217302858e70fa4Paul Duffin @Override 1220888a09821a98ac0680fad765217302858e70fa4Paul Duffin ImmutableMapEntry<K, V> getNextInKeyBucket() { 1230888a09821a98ac0680fad765217302858e70fa4Paul Duffin return nextInKeyBucket; 1241d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 1251d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 1260888a09821a98ac0680fad765217302858e70fa4Paul Duffin @Override 1277dd252788645e940eada959bdde927426e2531c9Paul Duffin @Nullable 1280888a09821a98ac0680fad765217302858e70fa4Paul Duffin ImmutableMapEntry<K, V> getNextInValueBucket() { 1291d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return null; 1301d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 1310888a09821a98ac0680fad765217302858e70fa4Paul Duffin 1321d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 1331d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 1340888a09821a98ac0680fad765217302858e70fa4Paul Duffin /** 1350888a09821a98ac0680fad765217302858e70fa4Paul Duffin * Closed addressing tends to perform well even with high load factors. 1360888a09821a98ac0680fad765217302858e70fa4Paul Duffin * Being conservative here ensures that the table is still likely to be 1370888a09821a98ac0680fad765217302858e70fa4Paul Duffin * relatively sparse (hence it misses fast) while saving space. 1380888a09821a98ac0680fad765217302858e70fa4Paul Duffin */ 1390888a09821a98ac0680fad765217302858e70fa4Paul Duffin private static final double MAX_LOAD_FACTOR = 1.2; 1400888a09821a98ac0680fad765217302858e70fa4Paul Duffin 1410888a09821a98ac0680fad765217302858e70fa4Paul Duffin /** 1420888a09821a98ac0680fad765217302858e70fa4Paul Duffin * Creates an {@code ImmutableMapEntry} array to hold parameterized entries. The 1430888a09821a98ac0680fad765217302858e70fa4Paul Duffin * result must never be upcast back to ImmutableMapEntry[] (or Object[], etc.), or 1440888a09821a98ac0680fad765217302858e70fa4Paul Duffin * allowed to escape the class. 1450888a09821a98ac0680fad765217302858e70fa4Paul Duffin */ 1460888a09821a98ac0680fad765217302858e70fa4Paul Duffin @SuppressWarnings("unchecked") // Safe as long as the javadocs are followed 1470888a09821a98ac0680fad765217302858e70fa4Paul Duffin private ImmutableMapEntry<K, V>[] createEntryArray(int size) { 1480888a09821a98ac0680fad765217302858e70fa4Paul Duffin return new ImmutableMapEntry[size]; 1490888a09821a98ac0680fad765217302858e70fa4Paul Duffin } 1500888a09821a98ac0680fad765217302858e70fa4Paul Duffin 1510888a09821a98ac0680fad765217302858e70fa4Paul Duffin @Override public V get(@Nullable Object key) { 1521d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert if (key == null) { 1531d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return null; 1541d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 1551d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert int index = Hashing.smear(key.hashCode()) & mask; 1560888a09821a98ac0680fad765217302858e70fa4Paul Duffin for (ImmutableMapEntry<K, V> entry = table[index]; 1570888a09821a98ac0680fad765217302858e70fa4Paul Duffin entry != null; 1580888a09821a98ac0680fad765217302858e70fa4Paul Duffin entry = entry.getNextInKeyBucket()) { 1591d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert K candidateKey = entry.getKey(); 1601d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 1611d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert /* 1621d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * Assume that equals uses the == optimization when appropriate, and that 1631d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * it would check hash codes as an optimization when appropriate. If we 1641d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * did these things, it would just make things worse for the most 1651d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * performance-conscious users. 1661d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert */ 1671d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert if (key.equals(candidateKey)) { 1681d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return entry.getValue(); 1691d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 1701d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 1711d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return null; 1721d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 1731d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 1740888a09821a98ac0680fad765217302858e70fa4Paul Duffin @Override 1751d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert public int size() { 1761d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return entries.length; 1771d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 1780888a09821a98ac0680fad765217302858e70fa4Paul Duffin 1790888a09821a98ac0680fad765217302858e70fa4Paul Duffin @Override boolean isPartialView() { 1801d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return false; 1811d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 1821d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 1837dd252788645e940eada959bdde927426e2531c9Paul Duffin @Override 1847dd252788645e940eada959bdde927426e2531c9Paul Duffin ImmutableSet<Entry<K, V>> createEntrySet() { 1857dd252788645e940eada959bdde927426e2531c9Paul Duffin return new EntrySet(); 186dbd967a6e5c96cc1a97c5521f88dc1564ba2f81bPaul Duffin } 187dbd967a6e5c96cc1a97c5521f88dc1564ba2f81bPaul Duffin 1880888a09821a98ac0680fad765217302858e70fa4Paul Duffin @SuppressWarnings("serial") // uses writeReplace(), not default serialization 1897dd252788645e940eada959bdde927426e2531c9Paul Duffin private class EntrySet extends ImmutableMapEntrySet<K, V> { 1900888a09821a98ac0680fad765217302858e70fa4Paul Duffin @Override ImmutableMap<K, V> map() { 1917dd252788645e940eada959bdde927426e2531c9Paul Duffin return RegularImmutableMap.this; 1921d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 193dbd967a6e5c96cc1a97c5521f88dc1564ba2f81bPaul Duffin 1947dd252788645e940eada959bdde927426e2531c9Paul Duffin @Override 1957dd252788645e940eada959bdde927426e2531c9Paul Duffin public UnmodifiableIterator<Entry<K, V>> iterator() { 1967dd252788645e940eada959bdde927426e2531c9Paul Duffin return asList().iterator(); 197dbd967a6e5c96cc1a97c5521f88dc1564ba2f81bPaul Duffin } 198dbd967a6e5c96cc1a97c5521f88dc1564ba2f81bPaul Duffin 1997dd252788645e940eada959bdde927426e2531c9Paul Duffin @Override 2007dd252788645e940eada959bdde927426e2531c9Paul Duffin ImmutableList<Entry<K, V>> createAsList() { 2017dd252788645e940eada959bdde927426e2531c9Paul Duffin return new RegularImmutableAsList<Entry<K, V>>(this, entries); 202dbd967a6e5c96cc1a97c5521f88dc1564ba2f81bPaul Duffin } 203dbd967a6e5c96cc1a97c5521f88dc1564ba2f81bPaul Duffin } 204dbd967a6e5c96cc1a97c5521f88dc1564ba2f81bPaul Duffin 2051d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert // This class is never actually serialized directly, but we have to make the 2061d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert // warning go away (and suppressing would suppress for all nested classes too) 2071d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert private static final long serialVersionUID = 0; 2081d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert} 209