| /* |
| * Copyright 2014 Google Inc. |
| * |
| * Licensed under the Apache License, Version 2.0 (the "License"); you may not |
| * use this file except in compliance with the License. You may obtain a copy of |
| * the License at |
| * |
| * http://www.apache.org/licenses/LICENSE-2.0 |
| * |
| * Unless required by applicable law or agreed to in writing, software |
| * distributed under the License is distributed on an "AS IS" BASIS, WITHOUT |
| * WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the |
| * License for the specific language governing permissions and limitations under |
| * the License. |
| */ |
| package java.util; |
| |
| import static java.util.ConcurrentModificationDetector.structureChanged; |
| |
| import java.util.AbstractMap.SimpleEntry; |
| import java.util.Map.Entry; |
| import javaemul.internal.ArrayHelper; |
| import javaemul.internal.JsUtils; |
| import javaemul.internal.NativeArray; |
| |
| /** |
| * A simple wrapper around JavaScriptObject to provide {@link java.util.Map}-like semantics for any |
| * key type. |
| * <p> |
| * Implementation notes: |
| * <p> |
| * A key's hashCode is the index in backingMap which should contain that key. Since several keys may |
| * have the same hash, each value in hashCodeMap is actually an array containing all entries whose |
| * keys share the same hash. |
| */ |
| class InternalHashCodeMap<K, V> implements Iterable<Entry<K, V>> { |
| |
| private final InternalJsMap<Object> backingMap = InternalJsMapFactory.newJsMap(); |
| private AbstractHashMap<K, V> host; |
| private int size; |
| |
| public InternalHashCodeMap(AbstractHashMap<K, V> host) { |
| this.host = host; |
| } |
| |
| public V put(K key, V value) { |
| int hashCode = hash(key); |
| Entry<K, V>[] chain = getChainOrEmpty(hashCode); |
| |
| if (chain.length == 0) { |
| // This is a new chain, put it to the map. |
| backingMap.set(hashCode, chain); |
| } else { |
| // Chain already exists, perhaps key also exists. |
| Entry<K, V> entry = findEntryInChain(key, chain); |
| if (entry != null) { |
| return entry.setValue(value); |
| } |
| } |
| chain[chain.length] = new SimpleEntry<K, V>(key, value); |
| size++; |
| structureChanged(host); |
| return null; |
| } |
| |
| public V remove(Object key) { |
| int hashCode = hash(key); |
| Entry<K, V>[] chain = getChainOrEmpty(hashCode); |
| for (int i = 0; i < chain.length; i++) { |
| Entry<K, V> entry = chain[i]; |
| if (host.equals(key, entry.getKey())) { |
| if (chain.length == 1) { |
| ArrayHelper.setLength(chain, 0); |
| // remove the whole array |
| backingMap.delete(hashCode); |
| } else { |
| // splice out the entry we're removing |
| ArrayHelper.removeFrom(chain, i, 1); |
| } |
| size--; |
| structureChanged(host); |
| return entry.getValue(); |
| } |
| } |
| return null; |
| } |
| |
| public Map.Entry<K, V> getEntry(Object key) { |
| return findEntryInChain(key, getChainOrEmpty(hash(key))); |
| } |
| |
| private Map.Entry<K, V> findEntryInChain(Object key, Entry<K, V>[] chain) { |
| for (Entry<K, V> entry : chain) { |
| if (host.equals(key, entry.getKey())) { |
| return entry; |
| } |
| } |
| return null; |
| } |
| |
| public int size() { |
| return size; |
| } |
| |
| @Override |
| public Iterator<Entry<K, V>> iterator() { |
| return new Iterator<Map.Entry<K, V>>() { |
| final InternalJsMap.Iterator<?> chains = backingMap.entries(); |
| int itemIndex = 0; |
| Entry<K, V>[] chain = newEntryChain(); |
| Entry<K, V> lastEntry = null; |
| |
| @Override |
| public boolean hasNext() { |
| if (itemIndex < chain.length) { |
| return true; |
| } |
| InternalJsMap.IteratorEntry<?> current = chains.next(); |
| if (!current.isDone()) { |
| // Move to the beginning of next chain |
| chain = JsUtils.uncheckedCast(current.getValue()); |
| itemIndex = 0; |
| return true; |
| } |
| return false; |
| } |
| |
| @Override |
| public Entry<K, V> next() { |
| lastEntry = chain[itemIndex++]; |
| return lastEntry; |
| } |
| |
| @Override |
| public void remove() { |
| InternalHashCodeMap.this.remove(lastEntry.getKey()); |
| // Unless we are in a new chain, all items have shifted so our itemIndex should as well... |
| if (itemIndex != 0) { |
| itemIndex--; |
| } |
| } |
| }; |
| } |
| |
| private Entry<K, V>[] getChainOrEmpty(int hashCode) { |
| Entry<K, V>[] chain = JsUtils.uncheckedCast(backingMap.get(hashCode)); |
| return chain == null ? newEntryChain() : chain; |
| } |
| |
| private Entry<K, V>[] newEntryChain() { |
| return JsUtils.uncheckedCast(new NativeArray()); |
| } |
| |
| /** |
| * Returns hash code of the key as calculated by {@link AbstractHashMap#getHashCode(Object)} but |
| * also handles null keys as well. |
| */ |
| private int hash(Object key) { |
| return host.getHashCode(key); |
| } |
| } |