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.io.IOException; 21c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Blochimport java.io.InvalidObjectException; 22adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Projectimport java.io.ObjectInputStream; 23adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Projectimport java.io.ObjectOutputStream; 24c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Blochimport java.io.ObjectStreamField; 25adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Projectimport java.io.Serializable; 26adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 27adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project/** 28438d9883775e6ee31c097e2103a25571d2426cd9Elliott Hughes * Hashtable is a synchronized implementation of {@link Map}. All optional operations are supported. 29f33eae7e84eb6d3b0f4e86b59605bb3de73009f3Elliott Hughes * 30438d9883775e6ee31c097e2103a25571d2426cd9Elliott Hughes * <p>Neither keys nor values can be null. (Use {@code HashMap} or {@code LinkedHashMap} if you 31438d9883775e6ee31c097e2103a25571d2426cd9Elliott Hughes * need null keys or values.) 32f33eae7e84eb6d3b0f4e86b59605bb3de73009f3Elliott Hughes * 33c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch * @param <K> the type of keys maintained by this map 34c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch * @param <V> the type of mapped values 35438d9883775e6ee31c097e2103a25571d2426cd9Elliott Hughes * @see HashMap 36adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 37c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Blochpublic class Hashtable<K, V> extends Dictionary<K, V> 38c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch implements Map<K, V>, Cloneable, Serializable { 39c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch /** 40c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch * Min capacity (other than zero) for a Hashtable. Must be a power of two 41c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch * greater than 1 (and less than 1 << 30). 42c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch */ 43c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch private static final int MINIMUM_CAPACITY = 4; 44adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 45c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch /** 46c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch * Max capacity for a Hashtable. Must be a power of two >= MINIMUM_CAPACITY. 47c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch */ 48c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch private static final int MAXIMUM_CAPACITY = 1 << 30; 49adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 50c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch /** 51c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch * An empty table shared by all zero-capacity maps (typically from default 52c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch * constructor). It is never written to, and replaced on first put. Its size 53c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch * is set to half the minimum, so that the first resize will create a 54c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch * minimum-sized table. 55c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch */ 56c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch private static final Entry[] EMPTY_TABLE 57c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch = new HashtableEntry[MINIMUM_CAPACITY >>> 1]; 58adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 59c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch /** 60c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch * The default load factor. Note that this implementation ignores the 61c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch * load factor, but cannot do away with it entirely because it's 62438d9883775e6ee31c097e2103a25571d2426cd9Elliott Hughes * mentioned in the API. 63c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch * 64c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch * <p>Note that this constant has no impact on the behavior of the program, 65c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch * but it is emitted as part of the serialized form. The load factor of 66c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch * .75 is hardwired into the program, which uses cheap shifts in place of 67c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch * expensive division. 68c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch */ 69c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch private static final float DEFAULT_LOAD_FACTOR = .75F; 70adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 71c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch /** 72c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch * The hash table. 73c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch */ 74c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch private transient HashtableEntry<K, V>[] table; 75adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 76c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch /** 77c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch * The number of mappings in this hash map. 78c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch */ 79c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch private transient int size; 80adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 81c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch /** 82c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch * Incremented by "structural modifications" to allow (best effort) 83c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch * detection of concurrent modification. 84c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch */ 85c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch private transient int modCount; 86adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 87c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch /** 88c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch * The table is rehashed when its size exceeds this threshold. 89c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch * The value of this field is generally .75 * capacity, except when 90c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch * the capacity is zero, as described in the EMPTY_TABLE declaration 91c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch * above. 92c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch */ 93c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch private transient int threshold; 94adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 95c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch // Views - lazily initialized 96c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch private transient Set<K> keySet; 97c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch private transient Set<Entry<K, V>> entrySet; 98c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch private transient Collection<V> values; 99adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 100adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 101adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * Constructs a new {@code Hashtable} using the default capacity and load 102adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * factor. 103adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 104c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch @SuppressWarnings("unchecked") 105adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project public Hashtable() { 106c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch table = (HashtableEntry<K, V>[]) EMPTY_TABLE; 107c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch threshold = -1; // Forces first put invocation to replace EMPTY_TABLE 108adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 109adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 110adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 111adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * Constructs a new {@code Hashtable} using the specified capacity and the 112adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * default load factor. 113f5597e626ecf7949d249dea08c1a2964d890ec11Jesse Wilson * 114adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * @param capacity 115adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * the initial capacity. 116adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 117adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project public Hashtable(int capacity) { 118c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch if (capacity < 0) { 119c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch throw new IllegalArgumentException("Capacity: " + capacity); 120c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch } 121c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch 122c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch if (capacity == 0) { 123c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch @SuppressWarnings("unchecked") 124c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch HashtableEntry<K, V>[] tab = (HashtableEntry<K, V>[]) EMPTY_TABLE; 125c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch table = tab; 126c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch threshold = -1; // Forces first put() to replace EMPTY_TABLE 127c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch return; 128c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch } 129c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch 130c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch if (capacity < MINIMUM_CAPACITY) { 131c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch capacity = MINIMUM_CAPACITY; 132c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch } else if (capacity > MAXIMUM_CAPACITY) { 133c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch capacity = MAXIMUM_CAPACITY; 134adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } else { 135c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch capacity = roundUpToPowerOfTwo(capacity); 136adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 137c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch makeTable(capacity); 138adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 139adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 140adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 141adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * Constructs a new {@code Hashtable} using the specified capacity and load 142adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * factor. 143f5597e626ecf7949d249dea08c1a2964d890ec11Jesse Wilson * 144adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * @param capacity 145adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * the initial capacity. 146adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * @param loadFactor 147adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * the initial load factor. 148adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 149adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project public Hashtable(int capacity, float loadFactor) { 150c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch this(capacity); 151c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch 152c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch if (loadFactor <= 0 || Float.isNaN(loadFactor)) { 153c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch throw new IllegalArgumentException("Load factor: " + loadFactor); 154adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 155c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch 156c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch /* 157c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch * Note that this implementation ignores loadFactor; it always uses 158438d9883775e6ee31c097e2103a25571d2426cd9Elliott Hughes * a load factor of 3/4. This simplifies the code and generally 159c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch * improves performance. 160c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch */ 161adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 162adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 163adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 164adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * Constructs a new instance of {@code Hashtable} containing the mappings 165adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * from the specified map. 166f5597e626ecf7949d249dea08c1a2964d890ec11Jesse Wilson * 167adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * @param map 168adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * the mappings to add. 169adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 170adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project public Hashtable(Map<? extends K, ? extends V> map) { 171c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch this(capacityForInitSize(map.size())); 172c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch constructorPutAll(map); 173adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 174adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 175c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch /** 176c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch * Inserts all of the elements of map into this Hashtable in a manner 177438d9883775e6ee31c097e2103a25571d2426cd9Elliott Hughes * suitable for use by constructors and pseudo-constructors (i.e., clone, 178c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch * readObject). 179c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch */ 180c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch private void constructorPutAll(Map<? extends K, ? extends V> map) { 181c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch for (Entry<? extends K, ? extends V> e : map.entrySet()) { 182c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch constructorPut(e.getKey(), e.getValue()); 183c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch } 184adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 185adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 186adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 187c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch * Returns an appropriate capacity for the specified initial size. Does 188c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch * not round the result up to a power of two; the caller must do this! 189c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch * The returned value will be between 0 and MAXIMUM_CAPACITY (inclusive). 190adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 191c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch private static int capacityForInitSize(int size) { 192c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch int result = (size >> 1) + size; // Multiply by 3/2 to allow for growth 193c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch 194c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch // boolean expr is equivalent to result >= 0 && result<MAXIMUM_CAPACITY 195c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch return (result & ~(MAXIMUM_CAPACITY-1))==0 ? result : MAXIMUM_CAPACITY; 196adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 197adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 198adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 199adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * Returns a new {@code Hashtable} with the same key/value pairs, capacity 200adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * and load factor. 201f5597e626ecf7949d249dea08c1a2964d890ec11Jesse Wilson * 202adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * @return a shallow copy of this {@code Hashtable}. 203adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * @see java.lang.Cloneable 204adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 205adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project @SuppressWarnings("unchecked") 206c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch @Override public synchronized Object clone() { 207c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch /* 208c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch * This could be made more efficient. It unnecessarily hashes all of 209c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch * the elements in the map. 210c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch */ 211c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch Hashtable<K, V> result; 212adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project try { 213c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch result = (Hashtable<K, V>) super.clone(); 214adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } catch (CloneNotSupportedException e) { 215c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch throw new AssertionError(e); 216adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 217adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 218c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch // Restore clone to empty state, retaining our capacity and threshold 219c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch result.makeTable(table.length); 220c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch result.size = 0; 221c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch result.keySet = null; 222c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch result.entrySet = null; 223c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch result.values = null; 224c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch 225c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch result.constructorPutAll(this); 226c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch return result; 227adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 228adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 229adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 230c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch * Returns true if this {@code Hashtable} has no key/value pairs. 231f5597e626ecf7949d249dea08c1a2964d890ec11Jesse Wilson * 232c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch * @return {@code true} if this {@code Hashtable} has no key/value pairs, 233adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * {@code false} otherwise. 234c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch * @see #size 235adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 236c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch public synchronized boolean isEmpty() { 237c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch return size == 0; 238c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch } 239adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 240c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch /** 241c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch * Returns the number of key/value pairs in this {@code Hashtable}. 242c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch * 243c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch * @return the number of key/value pairs in this {@code Hashtable}. 244c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch * @see #elements 245c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch * @see #keys 246c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch */ 247c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch public synchronized int size() { 248c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch return size; 249c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch } 250c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch 251c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch /** 252c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch * Returns the value associated with the specified key in this 253c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch * {@code Hashtable}. 254c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch * 255c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch * @param key 256c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch * the key of the value returned. 257c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch * @return the value associated with the specified key, or {@code null} if 258c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch * the specified key does not exist. 259c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch * @see #put 260c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch */ 261c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch public synchronized V get(Object key) { 262c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch // Doug Lea's supplemental secondaryHash function (inlined) 263c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch int hash = key.hashCode(); 264c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch hash ^= (hash >>> 20) ^ (hash >>> 12); 265c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch hash ^= (hash >>> 7) ^ (hash >>> 4); 266c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch 267c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch HashtableEntry<K, V>[] tab = table; 268c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch for (HashtableEntry<K, V> e = tab[hash & (tab.length - 1)]; 269c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch e != null; e = e.next) { 270c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch K eKey = e.key; 271c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch if (eKey == key || (e.hash == hash && key.equals(eKey))) { 272c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch return e.value; 273adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 274adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 275c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch return null; 276adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 277adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 278adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 279adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * Returns true if this {@code Hashtable} contains the specified object as a 280adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * key of one of the key/value pairs. 281f5597e626ecf7949d249dea08c1a2964d890ec11Jesse Wilson * 282adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * @param key 283adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * the object to look for as a key in this {@code Hashtable}. 284adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * @return {@code true} if object is a key in this {@code Hashtable}, 285adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * {@code false} otherwise. 286adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * @see #contains 287adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * @see java.lang.Object#equals 288adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 289adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project public synchronized boolean containsKey(Object key) { 290c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch // Doug Lea's supplemental secondaryHash function (inlined) 291c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch int hash = key.hashCode(); 292c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch hash ^= (hash >>> 20) ^ (hash >>> 12); 293c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch hash ^= (hash >>> 7) ^ (hash >>> 4); 294c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch 295c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch HashtableEntry<K, V>[] tab = table; 296c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch for (HashtableEntry<K, V> e = tab[hash & (tab.length - 1)]; 297c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch e != null; e = e.next) { 298c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch K eKey = e.key; 299c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch if (eKey == key || (e.hash == hash && key.equals(eKey))) { 300c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch return true; 301c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch } 302c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch } 303c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch return false; 304adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 305adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 306adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 307adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * Searches this {@code Hashtable} for the specified value. 308f5597e626ecf7949d249dea08c1a2964d890ec11Jesse Wilson * 309adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * @param value 310adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * the object to search for. 311adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * @return {@code true} if {@code value} is a value of this 312adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * {@code Hashtable}, {@code false} otherwise. 313adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 314c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch public synchronized boolean containsValue(Object value) { 315c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch if (value == null) { 31686acc043d3334651ee26c65467d78d6cefedd397Kenny Root throw new NullPointerException("value == null"); 317adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 318c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch 319c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch HashtableEntry[] tab = table; 320c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch int len = tab.length; 321c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch 322c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch for (int i = 0; i < len; i++) { 323c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch for (HashtableEntry e = tab[i]; e != null; e = e.next) { 324c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch if (value.equals(e.value)) { 325c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch return true; 326c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch } 327f5597e626ecf7949d249dea08c1a2964d890ec11Jesse Wilson } 328c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch } 329c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch return false; 330adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 331adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 332adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 333c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch * Returns true if this {@code Hashtable} contains the specified object as 334c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch * the value of at least one of the key/value pairs. 335f5597e626ecf7949d249dea08c1a2964d890ec11Jesse Wilson * 336c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch * @param value 337c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch * the object to look for as a value in this {@code Hashtable}. 338c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch * @return {@code true} if object is a value in this {@code Hashtable}, 339c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch * {@code false} otherwise. 340c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch * @see #containsKey 341c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch * @see java.lang.Object#equals 342adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 343c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch public boolean contains(Object value) { 344c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch return containsValue(value); 345adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 346adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 347adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 348c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch * Associate the specified value with the specified key in this 349c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch * {@code Hashtable}. If the key already exists, the old value is replaced. 350c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch * The key and value cannot be null. 351f5597e626ecf7949d249dea08c1a2964d890ec11Jesse Wilson * 352c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch * @param key 353c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch * the key to add. 354c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch * @param value 355c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch * the value to add. 356c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch * @return the old value associated with the specified key, or {@code null} 357c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch * if the key did not exist. 358c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch * @see #elements 359c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch * @see #get 360c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch * @see #keys 361c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch * @see java.lang.Object#equals 362adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 363c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch public synchronized V put(K key, V value) { 36486acc043d3334651ee26c65467d78d6cefedd397Kenny Root if (key == null) { 36586acc043d3334651ee26c65467d78d6cefedd397Kenny Root throw new NullPointerException("key == null"); 36686acc043d3334651ee26c65467d78d6cefedd397Kenny Root } else if (value == null) { 36786acc043d3334651ee26c65467d78d6cefedd397Kenny Root throw new NullPointerException("value == null"); 368adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 369c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch int hash = secondaryHash(key.hashCode()); 370c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch HashtableEntry<K, V>[] tab = table; 371c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch int index = hash & (tab.length - 1); 372c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch HashtableEntry<K, V> first = tab[index]; 373c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch for (HashtableEntry<K, V> e = first; e != null; e = e.next) { 374c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch if (e.hash == hash && key.equals(e.key)) { 375c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch V oldValue = e.value; 376c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch e.value = value; 377c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch return oldValue; 378adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 379c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch } 380adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 381c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch // No entry for key is present; create one 382c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch modCount++; 383c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch if (size++ > threshold) { 384c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch rehash(); // Does nothing!! 385c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch tab = doubleCapacity(); 386c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch index = hash & (tab.length - 1); 387c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch first = tab[index]; 388adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 389c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch tab[index] = new HashtableEntry<K, V>(key, value, hash, first); 390c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch return null; 391adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 392adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 393adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 394c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch * This method is just like put, except that it doesn't do things that 395c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch * are inappropriate or unnecessary for constructors and pseudo-constructors 396c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch * (i.e., clone, readObject). In particular, this method does not check to 397c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch * ensure that capacity is sufficient, and does not increment modCount. 398adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 399c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch private void constructorPut(K key, V value) { 40086acc043d3334651ee26c65467d78d6cefedd397Kenny Root if (key == null) { 40186acc043d3334651ee26c65467d78d6cefedd397Kenny Root throw new NullPointerException("key == null"); 40286acc043d3334651ee26c65467d78d6cefedd397Kenny Root } else if (value == null) { 40386acc043d3334651ee26c65467d78d6cefedd397Kenny Root throw new NullPointerException("value == null"); 404adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 405c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch int hash = secondaryHash(key.hashCode()); 406c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch HashtableEntry<K, V>[] tab = table; 407c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch int index = hash & (tab.length - 1); 408c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch HashtableEntry<K, V> first = tab[index]; 409c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch for (HashtableEntry<K, V> e = first; e != null; e = e.next) { 410c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch if (e.hash == hash && key.equals(e.key)) { 411c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch e.value = value; 412c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch return; 413adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 414adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 415adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 416c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch // No entry for key is present; create one 417c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch tab[index] = new HashtableEntry<K, V>(key, value, hash, first); 418c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch size++; 419adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 420adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 421adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 422c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch * Copies every mapping to this {@code Hashtable} from the specified map. 423f5597e626ecf7949d249dea08c1a2964d890ec11Jesse Wilson * 424c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch * @param map 425c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch * the map to copy mappings from. 426adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 427c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch public synchronized void putAll(Map<? extends K, ? extends V> map) { 428c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch ensureCapacity(map.size()); 429c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch for (Entry<? extends K, ? extends V> e : map.entrySet()) { 430c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch put(e.getKey(), e.getValue()); 431c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch } 432adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 433adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 434adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 435c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch * Ensures that the hash table has sufficient capacity to store the 436c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch * specified number of mappings, with room to grow. If not, it increases the 437c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch * capacity as appropriate. Like doubleCapacity, this method moves existing 438c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch * entries to new buckets as appropriate. Unlike doubleCapacity, this method 439c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch * can grow the table by factors of 2^n for n > 1. Hopefully, a single call 440c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch * to this method will be faster than multiple calls to doubleCapacity. 441f5597e626ecf7949d249dea08c1a2964d890ec11Jesse Wilson * 442c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch * <p>This method is called only by putAll. 443adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 444c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch private void ensureCapacity(int numMappings) { 445c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch int newCapacity = roundUpToPowerOfTwo(capacityForInitSize(numMappings)); 446c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch HashtableEntry<K, V>[] oldTable = table; 447c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch int oldCapacity = oldTable.length; 448c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch if (newCapacity <= oldCapacity) { 449c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch return; 450c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch } 451c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch 452c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch rehash(); // Does nothing!! 453c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch 454b5bde2fd72189192b52e726a2d606d70c3c8a34bElliott Hughes if (newCapacity == oldCapacity * 2) { 455c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch doubleCapacity(); 456c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch return; 457adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 458c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch 459c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch // We're growing by at least 4x, rehash in the obvious way 460c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch HashtableEntry<K, V>[] newTable = makeTable(newCapacity); 461c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch if (size != 0) { 462c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch int newMask = newCapacity - 1; 463c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch for (int i = 0; i < oldCapacity; i++) { 464c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch for (HashtableEntry<K, V> e = oldTable[i]; e != null;) { 465c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch HashtableEntry<K, V> oldNext = e.next; 466c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch int newIndex = e.hash & newMask; 467c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch HashtableEntry<K, V> newNext = newTable[newIndex]; 468c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch newTable[newIndex] = e; 469c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch e.next = newNext; 470c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch e = oldNext; 471c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch } 472f5597e626ecf7949d249dea08c1a2964d890ec11Jesse Wilson } 473c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch } 474adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 475adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 476adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 477c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch * Increases the capacity of this {@code Hashtable}. This method is called 478c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch * when the size of this {@code Hashtable} exceeds the load factor. 479adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 480c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch protected void rehash() { 481c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch /* 482c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch * This method has no testable semantics, other than that it gets 483c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch * called from time to time. 484c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch */ 485c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch } 486adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 487c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch /** 488c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch * Allocate a table of the given capacity and set the threshold accordingly. 489c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch * @param newCapacity must be a power of two 490c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch */ 491c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch private HashtableEntry<K, V>[] makeTable(int newCapacity) { 492c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch @SuppressWarnings("unchecked") HashtableEntry<K, V>[] newTable 493c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch = (HashtableEntry<K, V>[]) new HashtableEntry[newCapacity]; 494c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch table = newTable; 495c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch threshold = (newCapacity >> 1) + (newCapacity >> 2); // 3/4 capacity 496c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch return newTable; 497c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch } 498adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 499c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch /** 500c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch * Doubles the capacity of the hash table. Existing entries are placed in 501c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch * the correct bucket on the enlarged table. If the current capacity is, 502c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch * MAXIMUM_CAPACITY, this method is a no-op. Returns the table, which 503c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch * will be new unless we were already at MAXIMUM_CAPACITY. 504c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch */ 505c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch private HashtableEntry<K, V>[] doubleCapacity() { 506c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch HashtableEntry<K, V>[] oldTable = table; 507c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch int oldCapacity = oldTable.length; 508c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch if (oldCapacity == MAXIMUM_CAPACITY) { 509c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch return oldTable; 510c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch } 511b5bde2fd72189192b52e726a2d606d70c3c8a34bElliott Hughes int newCapacity = oldCapacity * 2; 512c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch HashtableEntry<K, V>[] newTable = makeTable(newCapacity); 513c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch if (size == 0) { 514c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch return newTable; 515c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch } 516adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 517c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch for (int j = 0; j < oldCapacity; j++) { 518c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch /* 519c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch * Rehash the bucket using the minimum number of field writes. 520c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch * This is the most subtle and delicate code in the class. 521c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch */ 522c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch HashtableEntry<K, V> e = oldTable[j]; 523c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch if (e == null) { 524c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch continue; 525c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch } 526c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch int highBit = e.hash & oldCapacity; 527c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch HashtableEntry<K, V> broken = null; 528c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch newTable[j | highBit] = e; 529c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch for (HashtableEntry<K,V> n = e.next; n != null; e = n, n = n.next) { 530c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch int nextHighBit = n.hash & oldCapacity; 531c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch if (nextHighBit != highBit) { 532c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch if (broken == null) 533c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch newTable[j | nextHighBit] = n; 534c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch else 535c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch broken.next = n; 536c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch broken = e; 537c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch highBit = nextHighBit; 538adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 539adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 540c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch if (broken != null) 541c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch broken.next = null; 542c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch } 543c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch return newTable; 544c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch } 545adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 546c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch /** 547c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch * Removes the key/value pair with the specified key from this 548c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch * {@code Hashtable}. 549c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch * 550c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch * @param key 551c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch * the key to remove. 552c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch * @return the value associated with the specified key, or {@code null} if 553c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch * the specified key did not exist. 554c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch * @see #get 555c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch * @see #put 556c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch */ 557c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch public synchronized V remove(Object key) { 558c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch int hash = secondaryHash(key.hashCode()); 559c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch HashtableEntry<K, V>[] tab = table; 560c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch int index = hash & (tab.length - 1); 561c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch for (HashtableEntry<K, V> e = tab[index], prev = null; 562c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch e != null; prev = e, e = e.next) { 563c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch if (e.hash == hash && key.equals(e.key)) { 564c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch if (prev == null) { 565c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch tab[index] = e.next; 566c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch } else { 567c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch prev.next = e.next; 568f5597e626ecf7949d249dea08c1a2964d890ec11Jesse Wilson } 569c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch modCount++; 570c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch size--; 571c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch return e.value; 572adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 573c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch } 574c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch return null; 575adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 576adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 577c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch /** 578c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch * Removes all key/value pairs from this {@code Hashtable}, leaving the 579c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch * size zero and the capacity unchanged. 580c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch * 581c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch * @see #isEmpty 582c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch * @see #size 583c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch */ 584c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch public synchronized void clear() { 585c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch if (size != 0) { 586c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch Arrays.fill(table, null); 587c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch modCount++; 588c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch size = 0; 589c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch } 590c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch } 591f5597e626ecf7949d249dea08c1a2964d890ec11Jesse Wilson 592c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch /** 593c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch * Returns a set of the keys contained in this {@code Hashtable}. The set 594c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch * is backed by this {@code Hashtable} so changes to one are reflected by 595c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch * the other. The set does not support adding. 596c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch * 597c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch * @return a set of the keys. 598c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch */ 599c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch public synchronized Set<K> keySet() { 600c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch Set<K> ks = keySet; 601c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch return (ks != null) ? ks : (keySet = new KeySet()); 602c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch } 603f5597e626ecf7949d249dea08c1a2964d890ec11Jesse Wilson 604c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch /** 605c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch * Returns a collection of the values contained in this {@code Hashtable}. 606c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch * The collection is backed by this {@code Hashtable} so changes to one are 607c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch * reflected by the other. The collection does not support adding. 608c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch * 609c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch * @return a collection of the values. 610c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch */ 611c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch public synchronized Collection<V> values() { 612c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch Collection<V> vs = values; 613c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch return (vs != null) ? vs : (values = new Values()); 614c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch } 615f5597e626ecf7949d249dea08c1a2964d890ec11Jesse Wilson 616c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch /** 617c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch * Returns a set of the mappings contained in this {@code Hashtable}. Each 618c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch * element in the set is a {@link Map.Entry}. The set is backed by this 619c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch * {@code Hashtable} so changes to one are reflected by the other. The set 620c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch * does not support adding. 621c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch * 622c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch * @return a set of the mappings. 623c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch */ 624c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch public synchronized Set<Entry<K, V>> entrySet() { 625c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch Set<Entry<K, V>> es = entrySet; 626c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch return (es != null) ? es : (entrySet = new EntrySet()); 627c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch } 628f5597e626ecf7949d249dea08c1a2964d890ec11Jesse Wilson 629c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch 630c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch /** 631c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch * Returns an enumeration on the keys of this {@code Hashtable} instance. 632c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch * The results of the enumeration may be affected if the contents of this 633c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch * {@code Hashtable} are modified. 634c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch * 635c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch * @return an enumeration of the keys of this {@code Hashtable}. 636c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch * @see #elements 637c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch * @see #size 638c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch * @see Enumeration 639c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch */ 640c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch public synchronized Enumeration<K> keys() { 641c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch return new KeyEnumeration(); 642c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch } 643c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch 644c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch /** 645c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch * Returns an enumeration on the values of this {@code Hashtable}. The 646c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch * results of the Enumeration may be affected if the contents of this 647c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch * {@code Hashtable} are modified. 648c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch * 649c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch * @return an enumeration of the values of this {@code Hashtable}. 650c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch * @see #keys 651c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch * @see #size 652c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch * @see Enumeration 653c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch */ 654c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch public synchronized Enumeration<V> elements() { 655c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch return new ValueEnumeration(); 656c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch } 657c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch 658c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch /** 659c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch * Note: technically the methods of this class should synchronize the 660c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch * backing map. However, this would require them to have a reference 661438d9883775e6ee31c097e2103a25571d2426cd9Elliott Hughes * to it, which would cause considerable bloat. Moreover, the RI 662c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch * behaves the same way. 663c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch */ 664c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch private static class HashtableEntry<K, V> implements Entry<K, V> { 665c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch final K key; 666c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch V value; 667c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch final int hash; 668c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch HashtableEntry<K, V> next; 669c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch 670c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch HashtableEntry(K key, V value, int hash, HashtableEntry<K, V> next) { 671c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch this.key = key; 672c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch this.value = value; 673c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch this.hash = hash; 674c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch this.next = next; 675f5597e626ecf7949d249dea08c1a2964d890ec11Jesse Wilson } 676f5597e626ecf7949d249dea08c1a2964d890ec11Jesse Wilson 677c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch public final K getKey() { 678c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch return key; 679f5597e626ecf7949d249dea08c1a2964d890ec11Jesse Wilson } 680f5597e626ecf7949d249dea08c1a2964d890ec11Jesse Wilson 681c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch public final V getValue() { 682c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch return value; 683c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch } 684c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch 685c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch public final V setValue(V value) { 686c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch if (value == null) { 68786acc043d3334651ee26c65467d78d6cefedd397Kenny Root throw new NullPointerException("value == null"); 688c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch } 689c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch V oldValue = this.value; 690c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch this.value = value; 691c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch return oldValue; 692c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch } 693c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch 694c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch @Override public final boolean equals(Object o) { 695c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch if (!(o instanceof Entry)) { 696f5597e626ecf7949d249dea08c1a2964d890ec11Jesse Wilson return false; 697f5597e626ecf7949d249dea08c1a2964d890ec11Jesse Wilson } 698c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch Entry<?, ?> e = (Entry<?, ?>) o; 699c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch return key.equals(e.getKey()) && value.equals(e.getValue()); 700f5597e626ecf7949d249dea08c1a2964d890ec11Jesse Wilson } 701f5597e626ecf7949d249dea08c1a2964d890ec11Jesse Wilson 702c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch @Override public final int hashCode() { 703c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch return key.hashCode() ^ value.hashCode(); 704c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch } 705c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch 706c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch @Override public final String toString() { 707c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch return key + "=" + value; 708c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch } 709c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch } 710c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch 711c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch private abstract class HashIterator { 712c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch int nextIndex; 713c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch HashtableEntry<K, V> nextEntry; 714c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch HashtableEntry<K, V> lastEntryReturned; 715c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch int expectedModCount = modCount; 716c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch 717c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch HashIterator() { 718c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch HashtableEntry<K, V>[] tab = table; 719c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch HashtableEntry<K, V> next = null; 720c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch while (next == null && nextIndex < tab.length) { 721c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch next = tab[nextIndex++]; 722f5597e626ecf7949d249dea08c1a2964d890ec11Jesse Wilson } 723c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch nextEntry = next; 724f5597e626ecf7949d249dea08c1a2964d890ec11Jesse Wilson } 725f5597e626ecf7949d249dea08c1a2964d890ec11Jesse Wilson 726c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch public boolean hasNext() { 727c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch return nextEntry != null; 728c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch } 729c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch 730c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch HashtableEntry<K, V> nextEntry() { 731c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch if (modCount != expectedModCount) 732c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch throw new ConcurrentModificationException(); 733c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch if (nextEntry == null) 734c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch throw new NoSuchElementException(); 735c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch 736c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch HashtableEntry<K, V> entryToReturn = nextEntry; 737c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch HashtableEntry<K, V>[] tab = table; 738c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch HashtableEntry<K, V> next = entryToReturn.next; 739c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch while (next == null && nextIndex < tab.length) { 740c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch next = tab[nextIndex++]; 741f5597e626ecf7949d249dea08c1a2964d890ec11Jesse Wilson } 742c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch nextEntry = next; 743c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch return lastEntryReturned = entryToReturn; 744f5597e626ecf7949d249dea08c1a2964d890ec11Jesse Wilson } 745f5597e626ecf7949d249dea08c1a2964d890ec11Jesse Wilson 746c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch HashtableEntry<K, V> nextEntryNotFailFast() { 747c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch if (nextEntry == null) 748f5597e626ecf7949d249dea08c1a2964d890ec11Jesse Wilson throw new NoSuchElementException(); 749c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch 750c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch HashtableEntry<K, V> entryToReturn = nextEntry; 751c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch HashtableEntry<K, V>[] tab = table; 752c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch HashtableEntry<K, V> next = entryToReturn.next; 753c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch while (next == null && nextIndex < tab.length) { 754c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch next = tab[nextIndex++]; 755f5597e626ecf7949d249dea08c1a2964d890ec11Jesse Wilson } 756c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch nextEntry = next; 757c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch return lastEntryReturned = entryToReturn; 758f5597e626ecf7949d249dea08c1a2964d890ec11Jesse Wilson } 759f5597e626ecf7949d249dea08c1a2964d890ec11Jesse Wilson 760f5597e626ecf7949d249dea08c1a2964d890ec11Jesse Wilson public void remove() { 761c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch if (lastEntryReturned == null) 762c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch throw new IllegalStateException(); 763c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch if (modCount != expectedModCount) 764c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch throw new ConcurrentModificationException(); 765c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch Hashtable.this.remove(lastEntryReturned.key); 766c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch lastEntryReturned = null; 767c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch expectedModCount = modCount; 768f5597e626ecf7949d249dea08c1a2964d890ec11Jesse Wilson } 769f5597e626ecf7949d249dea08c1a2964d890ec11Jesse Wilson } 770f5597e626ecf7949d249dea08c1a2964d890ec11Jesse Wilson 771c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch private final class KeyIterator extends HashIterator 772c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch implements Iterator<K> { 773c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch public K next() { return nextEntry().key; } 774c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch } 775c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch 776c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch private final class ValueIterator extends HashIterator 777c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch implements Iterator<V> { 778c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch public V next() { return nextEntry().value; } 779c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch } 780c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch 781c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch private final class EntryIterator extends HashIterator 782c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch implements Iterator<Entry<K, V>> { 783c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch public Entry<K, V> next() { return nextEntry(); } 784c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch } 785c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch 786c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch private final class KeyEnumeration extends HashIterator 787c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch implements Enumeration<K> { 788c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch public boolean hasMoreElements() { return hasNext(); } 789c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch public K nextElement() { return nextEntryNotFailFast().key; } 790c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch } 791c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch 792c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch private final class ValueEnumeration extends HashIterator 793c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch implements Enumeration<V> { 794c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch public boolean hasMoreElements() { return hasNext(); } 795c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch public V nextElement() { return nextEntryNotFailFast().value; } 796adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 797adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 798adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 799c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch * Returns true if this map contains the specified mapping. 800adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 801c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch private synchronized boolean containsMapping(Object key, Object value) { 802c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch int hash = secondaryHash(key.hashCode()); 803c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch HashtableEntry<K, V>[] tab = table; 804c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch int index = hash & (tab.length - 1); 805c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch for (HashtableEntry<K, V> e = tab[index]; e != null; e = e.next) { 806c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch if (e.hash == hash && e.key.equals(key)) { 807c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch return e.value.equals(value); 808c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch } 809adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 810c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch return false; // No entry for key 811adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 812adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 813adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 814c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch * Removes the mapping from key to value and returns true if this mapping 815c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch * exists; otherwise, returns does nothing and returns false. 816adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 817c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch private synchronized boolean removeMapping(Object key, Object value) { 818c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch int hash = secondaryHash(key.hashCode()); 819c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch HashtableEntry<K, V>[] tab = table; 820c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch int index = hash & (tab.length - 1); 821c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch for (HashtableEntry<K, V> e = tab[index], prev = null; 822c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch e != null; prev = e, e = e.next) { 823c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch if (e.hash == hash && e.key.equals(key)) { 824c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch if (!e.value.equals(value)) { 825c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch return false; // Map has wrong value for key 826adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 827c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch if (prev == null) { 828c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch tab[index] = e.next; 829c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch } else { 830c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch prev.next = e.next; 831adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 832c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch modCount++; 833c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch size--; 834c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch return true; 835adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 836adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 837c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch return false; // No entry for key 838adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 839adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 840adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 841c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch * Compares this {@code Hashtable} with the specified object and indicates 842c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch * if they are equal. In order to be equal, {@code object} must be an 843c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch * instance of Map and contain the same key/value pairs. 844f5597e626ecf7949d249dea08c1a2964d890ec11Jesse Wilson * 845c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch * @param object 846c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch * the object to compare with this object. 847c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch * @return {@code true} if the specified object is equal to this Map, 848c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch * {@code false} otherwise. 849c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch * @see #hashCode 850adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 851c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch @Override public synchronized boolean equals(Object object) { 852c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch return (object instanceof Map) && 853c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch entrySet().equals(((Map<?, ?>)object).entrySet()); 854c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch } 855c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch 856c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch @Override public synchronized int hashCode() { 857c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch int result = 0; 858c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch for (Entry<K, V> e : entrySet()) { 859c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch K key = e.getKey(); 860c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch V value = e.getValue(); 861c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch if (key == this || value == this) { 862c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch continue; 863adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 864c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch result += (key != null ? key.hashCode() : 0) 865c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch ^ (value != null ? value.hashCode() : 0); 866adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 867c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch return result; 868adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 869adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 870adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 871c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch * A rough estimate of the number of characters per entry, for use 872c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch * when creating a string buffer in the toString method. 873adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 874c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch private static final int CHARS_PER_ENTRY = 15; 875adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 876adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 877adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * Returns the string representation of this {@code Hashtable}. 878f5597e626ecf7949d249dea08c1a2964d890ec11Jesse Wilson * 879adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * @return the string representation of this {@code Hashtable}. 880adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 881c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch @Override public synchronized String toString() { 882c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch StringBuilder result = new StringBuilder(CHARS_PER_ENTRY * size); 883c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch result.append('{'); 884c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch Iterator<Entry<K, V>> i = entrySet().iterator(); 885c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch boolean hasMore = i.hasNext(); 886c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch while (hasMore) { 887c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch Entry<K, V> entry = i.next(); 888c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch 889c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch K key = entry.getKey(); 890c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch result.append(key == this ? "(this Map)" : key.toString()); 891c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch 892c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch result.append('='); 893c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch 894c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch V value = entry.getValue(); 895c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch result.append(value == this ? "(this Map)" : value.toString()); 896c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch 897c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch if (hasMore = i.hasNext()) { 898c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch result.append(", "); 899c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch } 900adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 901adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 902c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch result.append('}'); 903c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch return result.toString(); 904c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch } 905c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch 906c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch private final class KeySet extends AbstractSet<K> { 907c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch public Iterator<K> iterator() { 908c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch return new KeyIterator(); 909c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch } 910c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch public int size() { 911c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch return Hashtable.this.size(); 912c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch } 913c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch public boolean contains(Object o) { 914c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch return containsKey(o); 915c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch } 916c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch public boolean remove(Object o) { 917c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch synchronized (Hashtable.this) { 918c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch int oldSize = size; 919c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch Hashtable.this.remove(o); 920c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch return size != oldSize; 921adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 922adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 923c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch public void clear() { 924c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch Hashtable.this.clear(); 925c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch } 926c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch public boolean removeAll(Collection<?> collection) { 927c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch synchronized (Hashtable.this) { 928c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch return super.removeAll(collection); 929c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch } 930c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch } 931c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch public boolean retainAll(Collection<?> collection) { 932c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch synchronized (Hashtable.this) { 933c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch return super.retainAll(collection); 934c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch } 935c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch } 936c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch public boolean containsAll(Collection<?> collection) { 937c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch synchronized (Hashtable.this) { 938c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch return super.containsAll(collection); 939c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch } 940c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch } 941c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch public boolean equals(Object object) { 942c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch synchronized (Hashtable.this) { 943c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch return super.equals(object); 944c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch } 945c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch } 946c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch public int hashCode() { 947c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch synchronized (Hashtable.this) { 948c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch return super.hashCode(); 949c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch } 950c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch } 951c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch public String toString() { 952c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch synchronized (Hashtable.this) { 953c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch return super.toString(); 954c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch } 955c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch } 956c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch public Object[] toArray() { 957c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch synchronized (Hashtable.this) { 958c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch return super.toArray(); 959c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch } 960c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch } 961c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch public <T> T[] toArray(T[] a) { 962c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch synchronized (Hashtable.this) { 963c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch return super.toArray(a); 964c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch } 965c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch } 966c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch } 967c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch 968c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch private final class Values extends AbstractCollection<V> { 969c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch public Iterator<V> iterator() { 970c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch return new ValueIterator(); 971c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch } 972c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch public int size() { 973c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch return Hashtable.this.size(); 974c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch } 975c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch public boolean contains(Object o) { 976c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch return containsValue(o); 977c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch } 978c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch public void clear() { 979c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch Hashtable.this.clear(); 980c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch } 981c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch public boolean containsAll(Collection<?> collection) { 982c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch synchronized (Hashtable.this) { 983c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch return super.containsAll(collection); 984c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch } 985c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch } 986c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch public String toString() { 987c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch synchronized (Hashtable.this) { 988c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch return super.toString(); 989c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch } 990c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch } 991c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch public Object[] toArray() { 992c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch synchronized (Hashtable.this) { 993c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch return super.toArray(); 994c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch } 995c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch } 996c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch public <T> T[] toArray(T[] a) { 997c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch synchronized (Hashtable.this) { 998c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch return super.toArray(a); 999c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch } 1000c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch } 1001c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch } 1002c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch 1003c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch private final class EntrySet extends AbstractSet<Entry<K, V>> { 1004c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch public Iterator<Entry<K, V>> iterator() { 1005c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch return new EntryIterator(); 1006c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch } 1007c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch public boolean contains(Object o) { 1008c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch if (!(o instanceof Entry)) 1009c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch return false; 1010c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch Entry<?, ?> e = (Entry<?, ?>) o; 1011c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch return containsMapping(e.getKey(), e.getValue()); 1012c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch } 1013c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch public boolean remove(Object o) { 1014c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch if (!(o instanceof Entry)) 1015c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch return false; 1016c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch Entry<?, ?> e = (Entry<?, ?>)o; 1017c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch return removeMapping(e.getKey(), e.getValue()); 1018c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch } 1019c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch public int size() { 1020c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch return Hashtable.this.size(); 1021c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch } 1022c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch public void clear() { 1023c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch Hashtable.this.clear(); 1024c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch } 1025c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch public boolean removeAll(Collection<?> collection) { 1026c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch synchronized (Hashtable.this) { 1027c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch return super.removeAll(collection); 1028c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch } 1029c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch } 1030c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch public boolean retainAll(Collection<?> collection) { 1031c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch synchronized (Hashtable.this) { 1032c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch return super.retainAll(collection); 1033c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch } 1034c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch } 1035c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch public boolean containsAll(Collection<?> collection) { 1036c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch synchronized (Hashtable.this) { 1037c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch return super.containsAll(collection); 1038c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch } 1039c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch } 1040c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch public boolean equals(Object object) { 1041c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch synchronized (Hashtable.this) { 1042c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch return super.equals(object); 1043c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch } 1044c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch } 1045c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch public int hashCode() { 1046c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch return Hashtable.this.hashCode(); 1047c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch } 1048c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch public String toString() { 1049c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch synchronized (Hashtable.this) { 1050c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch return super.toString(); 1051c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch } 1052c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch } 1053c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch public Object[] toArray() { 1054c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch synchronized (Hashtable.this) { 1055c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch return super.toArray(); 1056c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch } 1057c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch } 1058c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch public <T> T[] toArray(T[] a) { 1059c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch synchronized (Hashtable.this) { 1060c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch return super.toArray(a); 1061c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch } 1062adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 1063adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 1064adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 1065adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 1066c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch * Applies a supplemental hash function to a given hashCode, which defends 1067c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch * against poor quality hash functions. This is critical because Hashtable 1068c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch * uses power-of-two length hash tables, that otherwise encounter collisions 1069c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch * for hashCodes that do not differ in lower or upper bits. 1070c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch */ 1071c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch private static int secondaryHash(int h) { 1072c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch // Doug Lea's supplemental hash function 1073c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch h ^= (h >>> 20) ^ (h >>> 12); 1074c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch return h ^ (h >>> 7) ^ (h >>> 4); 1075c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch } 1076c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch 1077c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch /** 1078c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch * Returns the smallest power of two >= its argument, with several caveats: 1079c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch * If the argument is negative but not Integer.MIN_VALUE, the method returns 1080c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch * zero. If the argument is > 2^30 or equal to Integer.MIN_VALUE, the method 1081c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch * returns Integer.MIN_VALUE. If the argument is zero, the method returns 1082c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch * zero. 1083adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 1084c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch private static int roundUpToPowerOfTwo(int i) { 1085c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch i--; // If input is a power of two, shift its high-order bit right 1086c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch 1087c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch // "Smear" the high-order bit all the way to the right 1088c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch i |= i >>> 1; 1089c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch i |= i >>> 2; 1090c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch i |= i >>> 4; 1091c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch i |= i >>> 8; 1092c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch i |= i >>> 16; 1093c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch 1094c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch return i + 1; 1095adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 1096adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 1097c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch private static final long serialVersionUID = 1421746759512286392L; 1098c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch 1099c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch private static final ObjectStreamField[] serialPersistentFields = { 1100e26ba79900d471d02d656f686926918ef7dc751fElliott Hughes new ObjectStreamField("threshold", int.class), 1101e26ba79900d471d02d656f686926918ef7dc751fElliott Hughes new ObjectStreamField("loadFactor", float.class), 1102c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch }; 1103c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch 1104adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project private synchronized void writeObject(ObjectOutputStream stream) 1105adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project throws IOException { 1106c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch // Emulate loadFactor field for other implementations to read 1107c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch ObjectOutputStream.PutField fields = stream.putFields(); 1108c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch fields.put("threshold", (int) (DEFAULT_LOAD_FACTOR * table.length)); 1109c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch fields.put("loadFactor", DEFAULT_LOAD_FACTOR); 1110c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch stream.writeFields(); 1111c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch 1112c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch stream.writeInt(table.length); // Capacity 1113c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch stream.writeInt(size); 1114c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch for (Entry<K, V> e : entrySet()) { 1115c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch stream.writeObject(e.getKey()); 1116c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch stream.writeObject(e.getValue()); 1117adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 1118adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 1119adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 1120adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project private void readObject(ObjectInputStream stream) throws IOException, 1121adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project ClassNotFoundException { 1122adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project stream.defaultReadObject(); 1123c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch int capacity = stream.readInt(); 1124c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch if (capacity < 0) { 1125c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch throw new InvalidObjectException("Capacity: " + capacity); 1126c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch } 1127c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch if (capacity < MINIMUM_CAPACITY) { 1128c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch capacity = MINIMUM_CAPACITY; 1129c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch } else if (capacity > MAXIMUM_CAPACITY) { 1130c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch capacity = MAXIMUM_CAPACITY; 1131c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch } else { 1132c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch capacity = roundUpToPowerOfTwo(capacity); 1133c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch } 1134c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch makeTable(capacity); 1135c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch 1136c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch int size = stream.readInt(); 1137c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch if (size < 0) { 1138c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch throw new InvalidObjectException("Size: " + size); 1139c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch } 1140c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch 1141c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch for (int i = 0; i < size; i++) { 1142c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch @SuppressWarnings("unchecked") K key = (K) stream.readObject(); 1143c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch @SuppressWarnings("unchecked") V val = (V) stream.readObject(); 1144c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch constructorPut(key, val); 1145adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 1146adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 1147adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project} 1148