1adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project/* 2adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * Licensed to the Apache Software Foundation (ASF) under one or more 3adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * contributor license agreements. See the NOTICE file distributed with 4adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * this work for additional information regarding copyright ownership. 5adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * The ASF licenses this file to You under the Apache License, Version 2.0 6adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * (the "License"); you may not use this file except in compliance with 7adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * the License. You may obtain a copy of the License at 8adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * 9adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * http://www.apache.org/licenses/LICENSE-2.0 10adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * 11adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * Unless required by applicable law or agreed to in writing, software 12adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * distributed under the License is distributed on an "AS IS" BASIS, 13adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 14adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * See the License for the specific language governing permissions and 15adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * limitations under the License. 16adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 17adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 18adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Projectpackage java.util; 19adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 20adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Projectimport java.lang.ref.ReferenceQueue; 21adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Projectimport java.lang.ref.WeakReference; 22adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 23adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project/** 24adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * WeakHashMap is an implementation of Map with keys which are WeakReferences. A 25adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * key/value mapping is removed when the key is no longer referenced. All 26adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * optional operations (adding and removing) are supported. Keys and values can 27adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * be any objects. Note that the garbage collector acts similar to a second 28adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * thread on this collection, possibly removing keys. 29f5597e626ecf7949d249dea08c1a2964d890ec11Jesse Wilson * 30f5597e626ecf7949d249dea08c1a2964d890ec11Jesse Wilson * @since 1.2 31adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * @see HashMap 32adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * @see WeakReference 33adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 34adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Projectpublic class WeakHashMap<K, V> extends AbstractMap<K, V> implements Map<K, V> { 35adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 36adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project private static final int DEFAULT_SIZE = 16; 37adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 38adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project private final ReferenceQueue<K> referenceQueue; 39adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 40adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project int elementCount; 41adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 42adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project Entry<K, V>[] elementData; 43adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 44adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project private final int loadFactor; 45adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 46adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project private int threshold; 47adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 48adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project volatile int modCount; 49adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 50adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project // Simple utility method to isolate unchecked cast for array creation 51adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project @SuppressWarnings("unchecked") 52adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project private static <K, V> Entry<K, V>[] newEntryArray(int size) { 53adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project return new Entry[size]; 54adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 55adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 56adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project private static final class Entry<K, V> extends WeakReference<K> implements 57adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project Map.Entry<K, V> { 581424a2a1a9fc53dc8b859a77c02c924d3dc2334dIan Rogers final int hash; 59adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 60adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project boolean isNull; 61adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 62adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project V value; 63adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 64adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project Entry<K, V> next; 65adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 66adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project interface Type<R, K, V> { 67adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project R get(Map.Entry<K, V> entry); 68adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 69adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 70adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project Entry(K key, V object, ReferenceQueue<K> queue) { 71adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project super(key, queue); 72adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project isNull = key == null; 731424a2a1a9fc53dc8b859a77c02c924d3dc2334dIan Rogers hash = isNull ? 0 : Collections.secondaryHash(key); 74adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project value = object; 75adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 76adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 77adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project public K getKey() { 78adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project return super.get(); 79adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 80adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 81adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project public V getValue() { 82adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project return value; 83adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 84adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 85adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project public V setValue(V object) { 86adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project V result = value; 87adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project value = object; 88adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project return result; 89adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 90adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 91adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project @Override 92adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project public boolean equals(Object other) { 93adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project if (!(other instanceof Map.Entry)) { 94adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project return false; 95adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 96adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project Map.Entry<?, ?> entry = (Map.Entry<?, ?>) other; 97adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project Object key = super.get(); 98adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project return (key == null ? key == entry.getKey() : key.equals(entry 99adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project .getKey())) 100adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project && (value == null ? value == entry.getValue() : value 101adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project .equals(entry.getValue())); 102adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 103adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 104adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project @Override 105adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project public int hashCode() { 106adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project return hash + (value == null ? 0 : value.hashCode()); 107adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 108adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 109adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project @Override 110adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project public String toString() { 111f33eae7e84eb6d3b0f4e86b59605bb3de73009f3Elliott Hughes return super.get() + "=" + value; 112adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 113adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 114adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 115adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project class HashIterator<R> implements Iterator<R> { 116adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project private int position = 0, expectedModCount; 117adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 118adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project private Entry<K, V> currentEntry, nextEntry; 119adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 120adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project private K nextKey; 121adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 122adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project final Entry.Type<R, K, V> type; 123adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 124adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project HashIterator(Entry.Type<R, K, V> type) { 125adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project this.type = type; 126adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project expectedModCount = modCount; 127adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 128adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 129adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project public boolean hasNext() { 130f5597e626ecf7949d249dea08c1a2964d890ec11Jesse Wilson if (nextEntry != null && (nextKey != null || nextEntry.isNull)) { 131adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project return true; 132adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 133adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project while (true) { 134adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project if (nextEntry == null) { 135adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project while (position < elementData.length) { 136adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project if ((nextEntry = elementData[position++]) != null) { 137adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project break; 138adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 139adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 140adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project if (nextEntry == null) { 141adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project return false; 142adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 143adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 144adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project // ensure key of next entry is not gc'ed 145adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project nextKey = nextEntry.get(); 146adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project if (nextKey != null || nextEntry.isNull) { 147adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project return true; 148adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 149adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project nextEntry = nextEntry.next; 150adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 151adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 152adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 153adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project public R next() { 154adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project if (expectedModCount == modCount) { 155adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project if (hasNext()) { 156adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project currentEntry = nextEntry; 157adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project nextEntry = currentEntry.next; 158adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project R result = type.get(currentEntry); 159adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project // free the key 160adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project nextKey = null; 161adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project return result; 162adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 163adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project throw new NoSuchElementException(); 164adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 165adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project throw new ConcurrentModificationException(); 166adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 167adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 168adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project public void remove() { 169adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project if (expectedModCount == modCount) { 170adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project if (currentEntry != null) { 171adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project removeEntry(currentEntry); 172adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project currentEntry = null; 173adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project expectedModCount++; 174adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project // cannot poll() as that would change the expectedModCount 175adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } else { 176adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project throw new IllegalStateException(); 177adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 178adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } else { 179adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project throw new ConcurrentModificationException(); 180adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 181adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 182adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 183adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 184adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 185adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * Constructs a new empty {@code WeakHashMap} instance. 186adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 187adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project public WeakHashMap() { 188adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project this(DEFAULT_SIZE); 189adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 190adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 191adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 192adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * Constructs a new {@code WeakHashMap} instance with the specified 193adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * capacity. 194f5597e626ecf7949d249dea08c1a2964d890ec11Jesse Wilson * 195adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * @param capacity 196adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * the initial capacity of this map. 197adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * @throws IllegalArgumentException 198adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * if the capacity is less than zero. 199adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 200adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project public WeakHashMap(int capacity) { 201cff1616012dc0d56c2da9af2b9b1183e76c7e044Elliott Hughes if (capacity < 0) { 202cff1616012dc0d56c2da9af2b9b1183e76c7e044Elliott Hughes throw new IllegalArgumentException("capacity < 0: " + capacity); 203adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 204cff1616012dc0d56c2da9af2b9b1183e76c7e044Elliott Hughes elementCount = 0; 205cff1616012dc0d56c2da9af2b9b1183e76c7e044Elliott Hughes elementData = newEntryArray(capacity == 0 ? 1 : capacity); 206cff1616012dc0d56c2da9af2b9b1183e76c7e044Elliott Hughes loadFactor = 7500; // Default load factor of 0.75 207cff1616012dc0d56c2da9af2b9b1183e76c7e044Elliott Hughes computeMaxSize(); 208cff1616012dc0d56c2da9af2b9b1183e76c7e044Elliott Hughes referenceQueue = new ReferenceQueue<K>(); 209adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 210adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 211adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 212adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * Constructs a new {@code WeakHashMap} instance with the specified capacity 213adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * and load factor. 214f5597e626ecf7949d249dea08c1a2964d890ec11Jesse Wilson * 215adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * @param capacity 216adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * the initial capacity of this map. 217adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * @param loadFactor 218adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * the initial load factor. 219adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * @throws IllegalArgumentException 220adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * if the capacity is less than zero or the load factor is less 221adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * or equal to zero. 222adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 223adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project public WeakHashMap(int capacity, float loadFactor) { 224cff1616012dc0d56c2da9af2b9b1183e76c7e044Elliott Hughes if (capacity < 0) { 225cff1616012dc0d56c2da9af2b9b1183e76c7e044Elliott Hughes throw new IllegalArgumentException("capacity < 0: " + capacity); 226adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 227cff1616012dc0d56c2da9af2b9b1183e76c7e044Elliott Hughes if (loadFactor <= 0) { 228cff1616012dc0d56c2da9af2b9b1183e76c7e044Elliott Hughes throw new IllegalArgumentException("loadFactor <= 0: " + loadFactor); 229cff1616012dc0d56c2da9af2b9b1183e76c7e044Elliott Hughes } 230cff1616012dc0d56c2da9af2b9b1183e76c7e044Elliott Hughes elementCount = 0; 231cff1616012dc0d56c2da9af2b9b1183e76c7e044Elliott Hughes elementData = newEntryArray(capacity == 0 ? 1 : capacity); 232cff1616012dc0d56c2da9af2b9b1183e76c7e044Elliott Hughes this.loadFactor = (int) (loadFactor * 10000); 233cff1616012dc0d56c2da9af2b9b1183e76c7e044Elliott Hughes computeMaxSize(); 234cff1616012dc0d56c2da9af2b9b1183e76c7e044Elliott Hughes referenceQueue = new ReferenceQueue<K>(); 235adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 236adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 237adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 238adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * Constructs a new {@code WeakHashMap} instance containing the mappings 239adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * from the specified map. 240f5597e626ecf7949d249dea08c1a2964d890ec11Jesse Wilson * 241adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * @param map 242adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * the mappings to add. 243adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 244adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project public WeakHashMap(Map<? extends K, ? extends V> map) { 245adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project this(map.size() < 6 ? 11 : map.size() * 2); 246adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project putAllImpl(map); 247adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 248adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 249adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 250adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * Removes all mappings from this map, leaving it empty. 251f5597e626ecf7949d249dea08c1a2964d890ec11Jesse Wilson * 252adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * @see #isEmpty() 253adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * @see #size() 254adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 255adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project @Override 256adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project public void clear() { 257adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project if (elementCount > 0) { 258adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project elementCount = 0; 259adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project Arrays.fill(elementData, null); 260adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project modCount++; 261adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project while (referenceQueue.poll() != null) { 262adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project // do nothing 263adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 264adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 265adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 266adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 267adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project private void computeMaxSize() { 268adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project threshold = (int) ((long) elementData.length * loadFactor / 10000); 269adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 270adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 271adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 272adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * Returns whether this map contains the specified key. 273f5597e626ecf7949d249dea08c1a2964d890ec11Jesse Wilson * 274adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * @param key 275adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * the key to search for. 276adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * @return {@code true} if this map contains the specified key, 277adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * {@code false} otherwise. 278adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 279adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project @Override 280adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project public boolean containsKey(Object key) { 281adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project return getEntry(key) != null; 282adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 283adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 284adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 285adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * Returns a set containing all of the mappings in this map. Each mapping is 286adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * an instance of {@link Map.Entry}. As the set is backed by this map, 287adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * changes in one will be reflected in the other. It does not support adding 288adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * operations. 289f5597e626ecf7949d249dea08c1a2964d890ec11Jesse Wilson * 290adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * @return a set of the mappings. 291adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 292adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project @Override 293adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project public Set<Map.Entry<K, V>> entrySet() { 294adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project poll(); 295adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project return new AbstractSet<Map.Entry<K, V>>() { 296adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project @Override 297adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project public int size() { 298adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project return WeakHashMap.this.size(); 299adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 300adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 301adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project @Override 302adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project public void clear() { 303adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project WeakHashMap.this.clear(); 304adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 305adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 306adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project @Override 307adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project public boolean remove(Object object) { 308adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project if (contains(object)) { 309adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project WeakHashMap.this 310adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project .remove(((Map.Entry<?, ?>) object).getKey()); 311adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project return true; 312adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 313adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project return false; 314adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 315adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 316adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project @Override 317adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project public boolean contains(Object object) { 318adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project if (object instanceof Map.Entry) { 319adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project Entry<?, ?> entry = getEntry(((Map.Entry<?, ?>) object) 320adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project .getKey()); 321adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project if (entry != null) { 322adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project Object key = entry.get(); 323adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project if (key != null || entry.isNull) { 324adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project return object.equals(entry); 325adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 326adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 327adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 328adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project return false; 329adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 330adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 331adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project @Override 332adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project public Iterator<Map.Entry<K, V>> iterator() { 333adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project return new HashIterator<Map.Entry<K, V>>( 334adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project new Entry.Type<Map.Entry<K, V>, K, V>() { 335adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project public Map.Entry<K, V> get(Map.Entry<K, V> entry) { 336adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project return entry; 337adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 338adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project }); 339adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 340adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project }; 341adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 342adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 343adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 344adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * Returns a set of the keys contained in this map. The set is backed by 345adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * this map so changes to one are reflected by the other. The set does not 346adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * support adding. 347f5597e626ecf7949d249dea08c1a2964d890ec11Jesse Wilson * 348adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * @return a set of the keys. 349adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 350adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project @Override 351adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project public Set<K> keySet() { 352adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project poll(); 353adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project if (keySet == null) { 354adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project keySet = new AbstractSet<K>() { 355adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project @Override 356adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project public boolean contains(Object object) { 357adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project return containsKey(object); 358adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 359adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 360adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project @Override 361adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project public int size() { 362adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project return WeakHashMap.this.size(); 363adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 364adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 365adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project @Override 366adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project public void clear() { 367adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project WeakHashMap.this.clear(); 368adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 369adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 370adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project @Override 371adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project public boolean remove(Object key) { 372adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project if (containsKey(key)) { 373adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project WeakHashMap.this.remove(key); 374adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project return true; 375adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 376adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project return false; 377adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 378adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 379adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project @Override 380adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project public Iterator<K> iterator() { 381adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project return new HashIterator<K>(new Entry.Type<K, K, V>() { 382adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project public K get(Map.Entry<K, V> entry) { 383adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project return entry.getKey(); 384adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 385adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project }); 386adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 387adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project }; 388adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 389adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project return keySet; 390adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 391adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 392adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 393adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * Returns a collection of the values contained in this map. The collection 394adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * is backed by this map so changes to one are reflected by the other. The 395adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * collection supports remove, removeAll, retainAll and clear operations, 396adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * and it does not support add or addAll operations. 397adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * <p> 398adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * This method returns a collection which is the subclass of 399adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * AbstractCollection. The iterator method of this subclass returns a 400adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * "wrapper object" over the iterator of map's entrySet(). The size method 401adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * wraps the map's size method and the contains method wraps the map's 402adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * containsValue method. 403adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * <p> 404adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * The collection is created when this method is called at first time and 405adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * returned in response to all subsequent calls. This method may return 406adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * different Collection when multiple calls to this method, since it has no 407adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * synchronization performed. 408f5597e626ecf7949d249dea08c1a2964d890ec11Jesse Wilson * 409adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * @return a collection of the values contained in this map. 410adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 411adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project @Override 412adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project public Collection<V> values() { 413adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project poll(); 414adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project if (valuesCollection == null) { 415adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project valuesCollection = new AbstractCollection<V>() { 416adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project @Override 417adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project public int size() { 418adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project return WeakHashMap.this.size(); 419adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 420adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 421adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project @Override 422adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project public void clear() { 423adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project WeakHashMap.this.clear(); 424adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 425adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 426adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project @Override 427adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project public boolean contains(Object object) { 428adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project return containsValue(object); 429adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 430adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 431adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project @Override 432adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project public Iterator<V> iterator() { 433adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project return new HashIterator<V>(new Entry.Type<V, K, V>() { 434adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project public V get(Map.Entry<K, V> entry) { 435adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project return entry.getValue(); 436adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 437adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project }); 438adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 439adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project }; 440adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 441adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project return valuesCollection; 442adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 443adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 444adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 445adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * Returns the value of the mapping with the specified key. 446f5597e626ecf7949d249dea08c1a2964d890ec11Jesse Wilson * 447adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * @param key 448adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * the key. 449adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * @return the value of the mapping with the specified key, or {@code null} 450adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * if no mapping for the specified key is found. 451adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 452adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project @Override 453adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project public V get(Object key) { 454adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project poll(); 455adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project if (key != null) { 4561424a2a1a9fc53dc8b859a77c02c924d3dc2334dIan Rogers int index = (Collections.secondaryHash(key) & 0x7FFFFFFF) % elementData.length; 457adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project Entry<K, V> entry = elementData[index]; 458adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project while (entry != null) { 459adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project if (key.equals(entry.get())) { 460adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project return entry.value; 461adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 462adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project entry = entry.next; 463adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 464adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project return null; 465adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 466adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project Entry<K, V> entry = elementData[0]; 467adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project while (entry != null) { 468adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project if (entry.isNull) { 469adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project return entry.value; 470adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 471adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project entry = entry.next; 472adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 473adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project return null; 474adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 475adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 476adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project Entry<K, V> getEntry(Object key) { 477adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project poll(); 478adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project if (key != null) { 4791424a2a1a9fc53dc8b859a77c02c924d3dc2334dIan Rogers int index = (Collections.secondaryHash(key) & 0x7FFFFFFF) % elementData.length; 480adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project Entry<K, V> entry = elementData[index]; 481adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project while (entry != null) { 482adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project if (key.equals(entry.get())) { 483adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project return entry; 484adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 485adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project entry = entry.next; 486adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 487adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project return null; 488adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 489adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project Entry<K, V> entry = elementData[0]; 490adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project while (entry != null) { 491adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project if (entry.isNull) { 492adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project return entry; 493adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 494adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project entry = entry.next; 495adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 496adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project return null; 497adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 498adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 499adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 500adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * Returns whether this map contains the specified value. 501f5597e626ecf7949d249dea08c1a2964d890ec11Jesse Wilson * 502adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * @param value 503adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * the value to search for. 504adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * @return {@code true} if this map contains the specified value, 505adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * {@code false} otherwise. 506adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 507adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project @Override 508adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project public boolean containsValue(Object value) { 509adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project poll(); 510adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project if (value != null) { 511adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project for (int i = elementData.length; --i >= 0;) { 512adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project Entry<K, V> entry = elementData[i]; 513adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project while (entry != null) { 514adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project K key = entry.get(); 515adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project if ((key != null || entry.isNull) 516adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project && value.equals(entry.value)) { 517adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project return true; 518adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 519adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project entry = entry.next; 520adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 521adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 522adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } else { 523adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project for (int i = elementData.length; --i >= 0;) { 524adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project Entry<K, V> entry = elementData[i]; 525adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project while (entry != null) { 526adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project K key = entry.get(); 527adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project if ((key != null || entry.isNull) && entry.value == null) { 528adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project return true; 529adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 530adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project entry = entry.next; 531adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 532adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 533adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 534adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project return false; 535adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 536adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 537adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 538adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * Returns the number of elements in this map. 539f5597e626ecf7949d249dea08c1a2964d890ec11Jesse Wilson * 540adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * @return the number of elements in this map. 541adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 542adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project @Override 543adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project public boolean isEmpty() { 544adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project return size() == 0; 545adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 546adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 547adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project @SuppressWarnings("unchecked") 548adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project void poll() { 549adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project Entry<K, V> toRemove; 550adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project while ((toRemove = (Entry<K, V>) referenceQueue.poll()) != null) { 551adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project removeEntry(toRemove); 552adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 553adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 554adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 555adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project void removeEntry(Entry<K, V> toRemove) { 556adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project Entry<K, V> entry, last = null; 557adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project int index = (toRemove.hash & 0x7FFFFFFF) % elementData.length; 558adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project entry = elementData[index]; 559adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project // Ignore queued entries which cannot be found, the user could 560adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project // have removed them before they were queued, i.e. using clear() 561adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project while (entry != null) { 562adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project if (toRemove == entry) { 563adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project modCount++; 564adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project if (last == null) { 565adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project elementData[index] = entry.next; 566adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } else { 567adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project last.next = entry.next; 568adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 569adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project elementCount--; 570adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project break; 571adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 572adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project last = entry; 573adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project entry = entry.next; 574adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 575adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 576adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 577adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 578adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * Maps the specified key to the specified value. 579f5597e626ecf7949d249dea08c1a2964d890ec11Jesse Wilson * 580adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * @param key 581adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * the key. 582adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * @param value 583adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * the value. 584adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * @return the value of any previous mapping with the specified key or 585adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * {@code null} if there was no mapping. 586adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 587adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project @Override 588adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project public V put(K key, V value) { 589adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project poll(); 590adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project int index = 0; 591adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project Entry<K, V> entry; 592adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project if (key != null) { 5931424a2a1a9fc53dc8b859a77c02c924d3dc2334dIan Rogers index = (Collections.secondaryHash(key) & 0x7FFFFFFF) % elementData.length; 594adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project entry = elementData[index]; 595adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project while (entry != null && !key.equals(entry.get())) { 596adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project entry = entry.next; 597adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 598adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } else { 599adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project entry = elementData[0]; 600adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project while (entry != null && !entry.isNull) { 601adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project entry = entry.next; 602adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 603adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 604adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project if (entry == null) { 605adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project modCount++; 606adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project if (++elementCount > threshold) { 607adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project rehash(); 6081424a2a1a9fc53dc8b859a77c02c924d3dc2334dIan Rogers index = key == null ? 0 : (Collections.secondaryHash(key) & 0x7FFFFFFF) 609adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project % elementData.length; 610adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 611adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project entry = new Entry<K, V>(key, value, referenceQueue); 612adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project entry.next = elementData[index]; 613adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project elementData[index] = entry; 614adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project return null; 615adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 616adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project V result = entry.value; 617adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project entry.value = value; 618adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project return result; 619adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 620adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 621adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project private void rehash() { 622b5bde2fd72189192b52e726a2d606d70c3c8a34bElliott Hughes int length = elementData.length * 2; 623adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project if (length == 0) { 624adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project length = 1; 625adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 626adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project Entry<K, V>[] newData = newEntryArray(length); 627adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project for (int i = 0; i < elementData.length; i++) { 628adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project Entry<K, V> entry = elementData[i]; 629adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project while (entry != null) { 630adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project int index = entry.isNull ? 0 : (entry.hash & 0x7FFFFFFF) 631adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project % length; 632adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project Entry<K, V> next = entry.next; 633adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project entry.next = newData[index]; 634adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project newData[index] = entry; 635adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project entry = next; 636adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 637adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 638adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project elementData = newData; 639adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project computeMaxSize(); 640adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 641adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 642adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 643adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * Copies all the mappings in the given map to this map. These mappings will 644adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * replace all mappings that this map had for any of the keys currently in 645adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * the given map. 646f5597e626ecf7949d249dea08c1a2964d890ec11Jesse Wilson * 647adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * @param map 648adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * the map to copy mappings from. 649f5597e626ecf7949d249dea08c1a2964d890ec11Jesse Wilson * @throws NullPointerException 650f5597e626ecf7949d249dea08c1a2964d890ec11Jesse Wilson * if {@code map} is {@code null}. 651adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 652adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project @Override 653adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project public void putAll(Map<? extends K, ? extends V> map) { 654adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project putAllImpl(map); 655adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 656adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 657adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 658adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * Removes the mapping with the specified key from this map. 659f5597e626ecf7949d249dea08c1a2964d890ec11Jesse Wilson * 660adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * @param key 661adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * the key of the mapping to remove. 662adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * @return the value of the removed mapping or {@code null} if no mapping 663adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * for the specified key was found. 664adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 665adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project @Override 666adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project public V remove(Object key) { 667adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project poll(); 668adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project int index = 0; 669adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project Entry<K, V> entry, last = null; 670adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project if (key != null) { 6711424a2a1a9fc53dc8b859a77c02c924d3dc2334dIan Rogers index = (Collections.secondaryHash(key) & 0x7FFFFFFF) % elementData.length; 672adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project entry = elementData[index]; 673adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project while (entry != null && !key.equals(entry.get())) { 674adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project last = entry; 675adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project entry = entry.next; 676adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 677adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } else { 678adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project entry = elementData[0]; 679adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project while (entry != null && !entry.isNull) { 680adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project last = entry; 681adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project entry = entry.next; 682adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 683adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 684adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project if (entry != null) { 685adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project modCount++; 686adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project if (last == null) { 687adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project elementData[index] = entry.next; 688adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } else { 689adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project last.next = entry.next; 690adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 691adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project elementCount--; 692adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project return entry.value; 693adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 694adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project return null; 695adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 696adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 697adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 698adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * Returns the number of elements in this map. 699f5597e626ecf7949d249dea08c1a2964d890ec11Jesse Wilson * 700adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * @return the number of elements in this map. 701adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 702adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project @Override 703adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project public int size() { 704adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project poll(); 705adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project return elementCount; 706adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 707adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 708adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project private void putAllImpl(Map<? extends K, ? extends V> map) { 709adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project if (map.entrySet() != null) { 710adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project super.putAll(map); 711adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 712adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 713adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project} 714