1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/rt/emul/compact/src/main/java/java/util/Hashtable.java Tue Feb 26 16:54:16 2013 +0100
1.3 @@ -0,0 +1,1005 @@
1.4 +/*
1.5 + * Copyright (c) 1994, 2011, Oracle and/or its affiliates. All rights reserved.
1.6 + * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
1.7 + *
1.8 + * This code is free software; you can redistribute it and/or modify it
1.9 + * under the terms of the GNU General Public License version 2 only, as
1.10 + * published by the Free Software Foundation. Oracle designates this
1.11 + * particular file as subject to the "Classpath" exception as provided
1.12 + * by Oracle in the LICENSE file that accompanied this code.
1.13 + *
1.14 + * This code is distributed in the hope that it will be useful, but WITHOUT
1.15 + * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
1.16 + * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
1.17 + * version 2 for more details (a copy is included in the LICENSE file that
1.18 + * accompanied this code).
1.19 + *
1.20 + * You should have received a copy of the GNU General Public License version
1.21 + * 2 along with this work; if not, write to the Free Software Foundation,
1.22 + * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
1.23 + *
1.24 + * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
1.25 + * or visit www.oracle.com if you need additional information or have any
1.26 + * questions.
1.27 + */
1.28 +
1.29 +package java.util;
1.30 +import java.io.*;
1.31 +
1.32 +/**
1.33 + * This class implements a hash table, which maps keys to values. Any
1.34 + * non-<code>null</code> object can be used as a key or as a value. <p>
1.35 + *
1.36 + * To successfully store and retrieve objects from a hashtable, the
1.37 + * objects used as keys must implement the <code>hashCode</code>
1.38 + * method and the <code>equals</code> method. <p>
1.39 + *
1.40 + * An instance of <code>Hashtable</code> has two parameters that affect its
1.41 + * performance: <i>initial capacity</i> and <i>load factor</i>. The
1.42 + * <i>capacity</i> is the number of <i>buckets</i> in the hash table, and the
1.43 + * <i>initial capacity</i> is simply the capacity at the time the hash table
1.44 + * is created. Note that the hash table is <i>open</i>: in the case of a "hash
1.45 + * collision", a single bucket stores multiple entries, which must be searched
1.46 + * sequentially. The <i>load factor</i> is a measure of how full the hash
1.47 + * table is allowed to get before its capacity is automatically increased.
1.48 + * The initial capacity and load factor parameters are merely hints to
1.49 + * the implementation. The exact details as to when and whether the rehash
1.50 + * method is invoked are implementation-dependent.<p>
1.51 + *
1.52 + * Generally, the default load factor (.75) offers a good tradeoff between
1.53 + * time and space costs. Higher values decrease the space overhead but
1.54 + * increase the time cost to look up an entry (which is reflected in most
1.55 + * <tt>Hashtable</tt> operations, including <tt>get</tt> and <tt>put</tt>).<p>
1.56 + *
1.57 + * The initial capacity controls a tradeoff between wasted space and the
1.58 + * need for <code>rehash</code> operations, which are time-consuming.
1.59 + * No <code>rehash</code> operations will <i>ever</i> occur if the initial
1.60 + * capacity is greater than the maximum number of entries the
1.61 + * <tt>Hashtable</tt> will contain divided by its load factor. However,
1.62 + * setting the initial capacity too high can waste space.<p>
1.63 + *
1.64 + * If many entries are to be made into a <code>Hashtable</code>,
1.65 + * creating it with a sufficiently large capacity may allow the
1.66 + * entries to be inserted more efficiently than letting it perform
1.67 + * automatic rehashing as needed to grow the table. <p>
1.68 + *
1.69 + * This example creates a hashtable of numbers. It uses the names of
1.70 + * the numbers as keys:
1.71 + * <pre> {@code
1.72 + * Hashtable<String, Integer> numbers
1.73 + * = new Hashtable<String, Integer>();
1.74 + * numbers.put("one", 1);
1.75 + * numbers.put("two", 2);
1.76 + * numbers.put("three", 3);}</pre>
1.77 + *
1.78 + * <p>To retrieve a number, use the following code:
1.79 + * <pre> {@code
1.80 + * Integer n = numbers.get("two");
1.81 + * if (n != null) {
1.82 + * System.out.println("two = " + n);
1.83 + * }}</pre>
1.84 + *
1.85 + * <p>The iterators returned by the <tt>iterator</tt> method of the collections
1.86 + * returned by all of this class's "collection view methods" are
1.87 + * <em>fail-fast</em>: if the Hashtable is structurally modified at any time
1.88 + * after the iterator is created, in any way except through the iterator's own
1.89 + * <tt>remove</tt> method, the iterator will throw a {@link
1.90 + * ConcurrentModificationException}. Thus, in the face of concurrent
1.91 + * modification, the iterator fails quickly and cleanly, rather than risking
1.92 + * arbitrary, non-deterministic behavior at an undetermined time in the future.
1.93 + * The Enumerations returned by Hashtable's keys and elements methods are
1.94 + * <em>not</em> fail-fast.
1.95 + *
1.96 + * <p>Note that the fail-fast behavior of an iterator cannot be guaranteed
1.97 + * as it is, generally speaking, impossible to make any hard guarantees in the
1.98 + * presence of unsynchronized concurrent modification. Fail-fast iterators
1.99 + * throw <tt>ConcurrentModificationException</tt> on a best-effort basis.
1.100 + * Therefore, it would be wrong to write a program that depended on this
1.101 + * exception for its correctness: <i>the fail-fast behavior of iterators
1.102 + * should be used only to detect bugs.</i>
1.103 + *
1.104 + * <p>As of the Java 2 platform v1.2, this class was retrofitted to
1.105 + * implement the {@link Map} interface, making it a member of the
1.106 + * <a href="{@docRoot}/../technotes/guides/collections/index.html">
1.107 + *
1.108 + * Java Collections Framework</a>. Unlike the new collection
1.109 + * implementations, {@code Hashtable} is synchronized. If a
1.110 + * thread-safe implementation is not needed, it is recommended to use
1.111 + * {@link HashMap} in place of {@code Hashtable}. If a thread-safe
1.112 + * highly-concurrent implementation is desired, then it is recommended
1.113 + * to use {@link java.util.concurrent.ConcurrentHashMap} in place of
1.114 + * {@code Hashtable}.
1.115 + *
1.116 + * @author Arthur van Hoff
1.117 + * @author Josh Bloch
1.118 + * @author Neal Gafter
1.119 + * @see Object#equals(java.lang.Object)
1.120 + * @see Object#hashCode()
1.121 + * @see Hashtable#rehash()
1.122 + * @see Collection
1.123 + * @see Map
1.124 + * @see HashMap
1.125 + * @see TreeMap
1.126 + * @since JDK1.0
1.127 + */
1.128 +public class Hashtable<K,V>
1.129 + extends Dictionary<K,V>
1.130 + implements Map<K,V>, Cloneable, java.io.Serializable {
1.131 +
1.132 + /**
1.133 + * The hash table data.
1.134 + */
1.135 + private transient Entry[] table;
1.136 +
1.137 + /**
1.138 + * The total number of entries in the hash table.
1.139 + */
1.140 + private transient int count;
1.141 +
1.142 + /**
1.143 + * The table is rehashed when its size exceeds this threshold. (The
1.144 + * value of this field is (int)(capacity * loadFactor).)
1.145 + *
1.146 + * @serial
1.147 + */
1.148 + private int threshold;
1.149 +
1.150 + /**
1.151 + * The load factor for the hashtable.
1.152 + *
1.153 + * @serial
1.154 + */
1.155 + private float loadFactor;
1.156 +
1.157 + /**
1.158 + * The number of times this Hashtable has been structurally modified
1.159 + * Structural modifications are those that change the number of entries in
1.160 + * the Hashtable or otherwise modify its internal structure (e.g.,
1.161 + * rehash). This field is used to make iterators on Collection-views of
1.162 + * the Hashtable fail-fast. (See ConcurrentModificationException).
1.163 + */
1.164 + private transient int modCount = 0;
1.165 +
1.166 + /** use serialVersionUID from JDK 1.0.2 for interoperability */
1.167 + private static final long serialVersionUID = 1421746759512286392L;
1.168 +
1.169 + /**
1.170 + * Constructs a new, empty hashtable with the specified initial
1.171 + * capacity and the specified load factor.
1.172 + *
1.173 + * @param initialCapacity the initial capacity of the hashtable.
1.174 + * @param loadFactor the load factor of the hashtable.
1.175 + * @exception IllegalArgumentException if the initial capacity is less
1.176 + * than zero, or if the load factor is nonpositive.
1.177 + */
1.178 + public Hashtable(int initialCapacity, float loadFactor) {
1.179 + if (initialCapacity < 0)
1.180 + throw new IllegalArgumentException("Illegal Capacity: "+
1.181 + initialCapacity);
1.182 + if (loadFactor <= 0 || Float.isNaN(loadFactor))
1.183 + throw new IllegalArgumentException("Illegal Load: "+loadFactor);
1.184 +
1.185 + if (initialCapacity==0)
1.186 + initialCapacity = 1;
1.187 + this.loadFactor = loadFactor;
1.188 + table = new Entry[initialCapacity];
1.189 + threshold = (int)(initialCapacity * loadFactor);
1.190 + }
1.191 +
1.192 + /**
1.193 + * Constructs a new, empty hashtable with the specified initial capacity
1.194 + * and default load factor (0.75).
1.195 + *
1.196 + * @param initialCapacity the initial capacity of the hashtable.
1.197 + * @exception IllegalArgumentException if the initial capacity is less
1.198 + * than zero.
1.199 + */
1.200 + public Hashtable(int initialCapacity) {
1.201 + this(initialCapacity, 0.75f);
1.202 + }
1.203 +
1.204 + /**
1.205 + * Constructs a new, empty hashtable with a default initial capacity (11)
1.206 + * and load factor (0.75).
1.207 + */
1.208 + public Hashtable() {
1.209 + this(11, 0.75f);
1.210 + }
1.211 +
1.212 + /**
1.213 + * Constructs a new hashtable with the same mappings as the given
1.214 + * Map. The hashtable is created with an initial capacity sufficient to
1.215 + * hold the mappings in the given Map and a default load factor (0.75).
1.216 + *
1.217 + * @param t the map whose mappings are to be placed in this map.
1.218 + * @throws NullPointerException if the specified map is null.
1.219 + * @since 1.2
1.220 + */
1.221 + public Hashtable(Map<? extends K, ? extends V> t) {
1.222 + this(Math.max(2*t.size(), 11), 0.75f);
1.223 + putAll(t);
1.224 + }
1.225 +
1.226 + /**
1.227 + * Returns the number of keys in this hashtable.
1.228 + *
1.229 + * @return the number of keys in this hashtable.
1.230 + */
1.231 + public synchronized int size() {
1.232 + return count;
1.233 + }
1.234 +
1.235 + /**
1.236 + * Tests if this hashtable maps no keys to values.
1.237 + *
1.238 + * @return <code>true</code> if this hashtable maps no keys to values;
1.239 + * <code>false</code> otherwise.
1.240 + */
1.241 + public synchronized boolean isEmpty() {
1.242 + return count == 0;
1.243 + }
1.244 +
1.245 + /**
1.246 + * Returns an enumeration of the keys in this hashtable.
1.247 + *
1.248 + * @return an enumeration of the keys in this hashtable.
1.249 + * @see Enumeration
1.250 + * @see #elements()
1.251 + * @see #keySet()
1.252 + * @see Map
1.253 + */
1.254 + public synchronized Enumeration<K> keys() {
1.255 + return this.<K>getEnumeration(KEYS);
1.256 + }
1.257 +
1.258 + /**
1.259 + * Returns an enumeration of the values in this hashtable.
1.260 + * Use the Enumeration methods on the returned object to fetch the elements
1.261 + * sequentially.
1.262 + *
1.263 + * @return an enumeration of the values in this hashtable.
1.264 + * @see java.util.Enumeration
1.265 + * @see #keys()
1.266 + * @see #values()
1.267 + * @see Map
1.268 + */
1.269 + public synchronized Enumeration<V> elements() {
1.270 + return this.<V>getEnumeration(VALUES);
1.271 + }
1.272 +
1.273 + /**
1.274 + * Tests if some key maps into the specified value in this hashtable.
1.275 + * This operation is more expensive than the {@link #containsKey
1.276 + * containsKey} method.
1.277 + *
1.278 + * <p>Note that this method is identical in functionality to
1.279 + * {@link #containsValue containsValue}, (which is part of the
1.280 + * {@link Map} interface in the collections framework).
1.281 + *
1.282 + * @param value a value to search for
1.283 + * @return <code>true</code> if and only if some key maps to the
1.284 + * <code>value</code> argument in this hashtable as
1.285 + * determined by the <tt>equals</tt> method;
1.286 + * <code>false</code> otherwise.
1.287 + * @exception NullPointerException if the value is <code>null</code>
1.288 + */
1.289 + public synchronized boolean contains(Object value) {
1.290 + if (value == null) {
1.291 + throw new NullPointerException();
1.292 + }
1.293 +
1.294 + Entry tab[] = table;
1.295 + for (int i = tab.length ; i-- > 0 ;) {
1.296 + for (Entry<K,V> e = tab[i] ; e != null ; e = e.next) {
1.297 + if (e.value.equals(value)) {
1.298 + return true;
1.299 + }
1.300 + }
1.301 + }
1.302 + return false;
1.303 + }
1.304 +
1.305 + /**
1.306 + * Returns true if this hashtable maps one or more keys to this value.
1.307 + *
1.308 + * <p>Note that this method is identical in functionality to {@link
1.309 + * #contains contains} (which predates the {@link Map} interface).
1.310 + *
1.311 + * @param value value whose presence in this hashtable is to be tested
1.312 + * @return <tt>true</tt> if this map maps one or more keys to the
1.313 + * specified value
1.314 + * @throws NullPointerException if the value is <code>null</code>
1.315 + * @since 1.2
1.316 + */
1.317 + public boolean containsValue(Object value) {
1.318 + return contains(value);
1.319 + }
1.320 +
1.321 + /**
1.322 + * Tests if the specified object is a key in this hashtable.
1.323 + *
1.324 + * @param key possible key
1.325 + * @return <code>true</code> if and only if the specified object
1.326 + * is a key in this hashtable, as determined by the
1.327 + * <tt>equals</tt> method; <code>false</code> otherwise.
1.328 + * @throws NullPointerException if the key is <code>null</code>
1.329 + * @see #contains(Object)
1.330 + */
1.331 + public synchronized boolean containsKey(Object key) {
1.332 + Entry tab[] = table;
1.333 + int hash = key.hashCode();
1.334 + int index = (hash & 0x7FFFFFFF) % tab.length;
1.335 + for (Entry<K,V> e = tab[index] ; e != null ; e = e.next) {
1.336 + if ((e.hash == hash) && e.key.equals(key)) {
1.337 + return true;
1.338 + }
1.339 + }
1.340 + return false;
1.341 + }
1.342 +
1.343 + /**
1.344 + * Returns the value to which the specified key is mapped,
1.345 + * or {@code null} if this map contains no mapping for the key.
1.346 + *
1.347 + * <p>More formally, if this map contains a mapping from a key
1.348 + * {@code k} to a value {@code v} such that {@code (key.equals(k))},
1.349 + * then this method returns {@code v}; otherwise it returns
1.350 + * {@code null}. (There can be at most one such mapping.)
1.351 + *
1.352 + * @param key the key whose associated value is to be returned
1.353 + * @return the value to which the specified key is mapped, or
1.354 + * {@code null} if this map contains no mapping for the key
1.355 + * @throws NullPointerException if the specified key is null
1.356 + * @see #put(Object, Object)
1.357 + */
1.358 + public synchronized V get(Object key) {
1.359 + Entry tab[] = table;
1.360 + int hash = key.hashCode();
1.361 + int index = (hash & 0x7FFFFFFF) % tab.length;
1.362 + for (Entry<K,V> e = tab[index] ; e != null ; e = e.next) {
1.363 + if ((e.hash == hash) && e.key.equals(key)) {
1.364 + return e.value;
1.365 + }
1.366 + }
1.367 + return null;
1.368 + }
1.369 +
1.370 + /**
1.371 + * The maximum size of array to allocate.
1.372 + * Some VMs reserve some header words in an array.
1.373 + * Attempts to allocate larger arrays may result in
1.374 + * OutOfMemoryError: Requested array size exceeds VM limit
1.375 + */
1.376 + private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
1.377 +
1.378 + /**
1.379 + * Increases the capacity of and internally reorganizes this
1.380 + * hashtable, in order to accommodate and access its entries more
1.381 + * efficiently. This method is called automatically when the
1.382 + * number of keys in the hashtable exceeds this hashtable's capacity
1.383 + * and load factor.
1.384 + */
1.385 + protected void rehash() {
1.386 + int oldCapacity = table.length;
1.387 + Entry[] oldMap = table;
1.388 +
1.389 + // overflow-conscious code
1.390 + int newCapacity = (oldCapacity << 1) + 1;
1.391 + if (newCapacity - MAX_ARRAY_SIZE > 0) {
1.392 + if (oldCapacity == MAX_ARRAY_SIZE)
1.393 + // Keep running with MAX_ARRAY_SIZE buckets
1.394 + return;
1.395 + newCapacity = MAX_ARRAY_SIZE;
1.396 + }
1.397 + Entry[] newMap = new Entry[newCapacity];
1.398 +
1.399 + modCount++;
1.400 + threshold = (int)(newCapacity * loadFactor);
1.401 + table = newMap;
1.402 +
1.403 + for (int i = oldCapacity ; i-- > 0 ;) {
1.404 + for (Entry<K,V> old = oldMap[i] ; old != null ; ) {
1.405 + Entry<K,V> e = old;
1.406 + old = old.next;
1.407 +
1.408 + int index = (e.hash & 0x7FFFFFFF) % newCapacity;
1.409 + e.next = newMap[index];
1.410 + newMap[index] = e;
1.411 + }
1.412 + }
1.413 + }
1.414 +
1.415 + /**
1.416 + * Maps the specified <code>key</code> to the specified
1.417 + * <code>value</code> in this hashtable. Neither the key nor the
1.418 + * value can be <code>null</code>. <p>
1.419 + *
1.420 + * The value can be retrieved by calling the <code>get</code> method
1.421 + * with a key that is equal to the original key.
1.422 + *
1.423 + * @param key the hashtable key
1.424 + * @param value the value
1.425 + * @return the previous value of the specified key in this hashtable,
1.426 + * or <code>null</code> if it did not have one
1.427 + * @exception NullPointerException if the key or value is
1.428 + * <code>null</code>
1.429 + * @see Object#equals(Object)
1.430 + * @see #get(Object)
1.431 + */
1.432 + public synchronized V put(K key, V value) {
1.433 + // Make sure the value is not null
1.434 + if (value == null) {
1.435 + throw new NullPointerException();
1.436 + }
1.437 +
1.438 + // Makes sure the key is not already in the hashtable.
1.439 + Entry tab[] = table;
1.440 + int hash = key.hashCode();
1.441 + int index = (hash & 0x7FFFFFFF) % tab.length;
1.442 + for (Entry<K,V> e = tab[index] ; e != null ; e = e.next) {
1.443 + if ((e.hash == hash) && e.key.equals(key)) {
1.444 + V old = e.value;
1.445 + e.value = value;
1.446 + return old;
1.447 + }
1.448 + }
1.449 +
1.450 + modCount++;
1.451 + if (count >= threshold) {
1.452 + // Rehash the table if the threshold is exceeded
1.453 + rehash();
1.454 +
1.455 + tab = table;
1.456 + index = (hash & 0x7FFFFFFF) % tab.length;
1.457 + }
1.458 +
1.459 + // Creates the new entry.
1.460 + Entry<K,V> e = tab[index];
1.461 + tab[index] = new Entry<>(hash, key, value, e);
1.462 + count++;
1.463 + return null;
1.464 + }
1.465 +
1.466 + /**
1.467 + * Removes the key (and its corresponding value) from this
1.468 + * hashtable. This method does nothing if the key is not in the hashtable.
1.469 + *
1.470 + * @param key the key that needs to be removed
1.471 + * @return the value to which the key had been mapped in this hashtable,
1.472 + * or <code>null</code> if the key did not have a mapping
1.473 + * @throws NullPointerException if the key is <code>null</code>
1.474 + */
1.475 + public synchronized V remove(Object key) {
1.476 + Entry tab[] = table;
1.477 + int hash = key.hashCode();
1.478 + int index = (hash & 0x7FFFFFFF) % tab.length;
1.479 + for (Entry<K,V> e = tab[index], prev = null ; e != null ; prev = e, e = e.next) {
1.480 + if ((e.hash == hash) && e.key.equals(key)) {
1.481 + modCount++;
1.482 + if (prev != null) {
1.483 + prev.next = e.next;
1.484 + } else {
1.485 + tab[index] = e.next;
1.486 + }
1.487 + count--;
1.488 + V oldValue = e.value;
1.489 + e.value = null;
1.490 + return oldValue;
1.491 + }
1.492 + }
1.493 + return null;
1.494 + }
1.495 +
1.496 + /**
1.497 + * Copies all of the mappings from the specified map to this hashtable.
1.498 + * These mappings will replace any mappings that this hashtable had for any
1.499 + * of the keys currently in the specified map.
1.500 + *
1.501 + * @param t mappings to be stored in this map
1.502 + * @throws NullPointerException if the specified map is null
1.503 + * @since 1.2
1.504 + */
1.505 + public synchronized void putAll(Map<? extends K, ? extends V> t) {
1.506 + for (Map.Entry<? extends K, ? extends V> e : t.entrySet())
1.507 + put(e.getKey(), e.getValue());
1.508 + }
1.509 +
1.510 + /**
1.511 + * Clears this hashtable so that it contains no keys.
1.512 + */
1.513 + public synchronized void clear() {
1.514 + Entry tab[] = table;
1.515 + modCount++;
1.516 + for (int index = tab.length; --index >= 0; )
1.517 + tab[index] = null;
1.518 + count = 0;
1.519 + }
1.520 +
1.521 + /**
1.522 + * Creates a shallow copy of this hashtable. All the structure of the
1.523 + * hashtable itself is copied, but the keys and values are not cloned.
1.524 + * This is a relatively expensive operation.
1.525 + *
1.526 + * @return a clone of the hashtable
1.527 + */
1.528 + public synchronized Object clone() {
1.529 + try {
1.530 + Hashtable<K,V> t = (Hashtable<K,V>) super.clone();
1.531 + t.table = new Entry[table.length];
1.532 + for (int i = table.length ; i-- > 0 ; ) {
1.533 + t.table[i] = (table[i] != null)
1.534 + ? (Entry<K,V>) table[i].clone() : null;
1.535 + }
1.536 + t.keySet = null;
1.537 + t.entrySet = null;
1.538 + t.values = null;
1.539 + t.modCount = 0;
1.540 + return t;
1.541 + } catch (CloneNotSupportedException e) {
1.542 + // this shouldn't happen, since we are Cloneable
1.543 + throw new InternalError();
1.544 + }
1.545 + }
1.546 +
1.547 + /**
1.548 + * Returns a string representation of this <tt>Hashtable</tt> object
1.549 + * in the form of a set of entries, enclosed in braces and separated
1.550 + * by the ASCII characters "<tt>, </tt>" (comma and space). Each
1.551 + * entry is rendered as the key, an equals sign <tt>=</tt>, and the
1.552 + * associated element, where the <tt>toString</tt> method is used to
1.553 + * convert the key and element to strings.
1.554 + *
1.555 + * @return a string representation of this hashtable
1.556 + */
1.557 + public synchronized String toString() {
1.558 + int max = size() - 1;
1.559 + if (max == -1)
1.560 + return "{}";
1.561 +
1.562 + StringBuilder sb = new StringBuilder();
1.563 + Iterator<Map.Entry<K,V>> it = entrySet().iterator();
1.564 +
1.565 + sb.append('{');
1.566 + for (int i = 0; ; i++) {
1.567 + Map.Entry<K,V> e = it.next();
1.568 + K key = e.getKey();
1.569 + V value = e.getValue();
1.570 + sb.append(key == this ? "(this Map)" : key.toString());
1.571 + sb.append('=');
1.572 + sb.append(value == this ? "(this Map)" : value.toString());
1.573 +
1.574 + if (i == max)
1.575 + return sb.append('}').toString();
1.576 + sb.append(", ");
1.577 + }
1.578 + }
1.579 +
1.580 +
1.581 + private <T> Enumeration<T> getEnumeration(int type) {
1.582 + if (count == 0) {
1.583 + return Collections.emptyEnumeration();
1.584 + } else {
1.585 + return new Enumerator<>(type, false);
1.586 + }
1.587 + }
1.588 +
1.589 + private <T> Iterator<T> getIterator(int type) {
1.590 + if (count == 0) {
1.591 + return Collections.emptyIterator();
1.592 + } else {
1.593 + return new Enumerator<>(type, true);
1.594 + }
1.595 + }
1.596 +
1.597 + // Views
1.598 +
1.599 + /**
1.600 + * Each of these fields are initialized to contain an instance of the
1.601 + * appropriate view the first time this view is requested. The views are
1.602 + * stateless, so there's no reason to create more than one of each.
1.603 + */
1.604 + private transient volatile Set<K> keySet = null;
1.605 + private transient volatile Set<Map.Entry<K,V>> entrySet = null;
1.606 + private transient volatile Collection<V> values = null;
1.607 +
1.608 + /**
1.609 + * Returns a {@link Set} view of the keys contained in this map.
1.610 + * The set is backed by the map, so changes to the map are
1.611 + * reflected in the set, and vice-versa. If the map is modified
1.612 + * while an iteration over the set is in progress (except through
1.613 + * the iterator's own <tt>remove</tt> operation), the results of
1.614 + * the iteration are undefined. The set supports element removal,
1.615 + * which removes the corresponding mapping from the map, via the
1.616 + * <tt>Iterator.remove</tt>, <tt>Set.remove</tt>,
1.617 + * <tt>removeAll</tt>, <tt>retainAll</tt>, and <tt>clear</tt>
1.618 + * operations. It does not support the <tt>add</tt> or <tt>addAll</tt>
1.619 + * operations.
1.620 + *
1.621 + * @since 1.2
1.622 + */
1.623 + public Set<K> keySet() {
1.624 + if (keySet == null)
1.625 + keySet = Collections.synchronizedSet(new KeySet(), this);
1.626 + return keySet;
1.627 + }
1.628 +
1.629 + private class KeySet extends AbstractSet<K> {
1.630 + public Iterator<K> iterator() {
1.631 + return getIterator(KEYS);
1.632 + }
1.633 + public int size() {
1.634 + return count;
1.635 + }
1.636 + public boolean contains(Object o) {
1.637 + return containsKey(o);
1.638 + }
1.639 + public boolean remove(Object o) {
1.640 + return Hashtable.this.remove(o) != null;
1.641 + }
1.642 + public void clear() {
1.643 + Hashtable.this.clear();
1.644 + }
1.645 + }
1.646 +
1.647 + /**
1.648 + * Returns a {@link Set} view of the mappings contained in this map.
1.649 + * The set is backed by the map, so changes to the map are
1.650 + * reflected in the set, and vice-versa. If the map is modified
1.651 + * while an iteration over the set is in progress (except through
1.652 + * the iterator's own <tt>remove</tt> operation, or through the
1.653 + * <tt>setValue</tt> operation on a map entry returned by the
1.654 + * iterator) the results of the iteration are undefined. The set
1.655 + * supports element removal, which removes the corresponding
1.656 + * mapping from the map, via the <tt>Iterator.remove</tt>,
1.657 + * <tt>Set.remove</tt>, <tt>removeAll</tt>, <tt>retainAll</tt> and
1.658 + * <tt>clear</tt> operations. It does not support the
1.659 + * <tt>add</tt> or <tt>addAll</tt> operations.
1.660 + *
1.661 + * @since 1.2
1.662 + */
1.663 + public Set<Map.Entry<K,V>> entrySet() {
1.664 + if (entrySet==null)
1.665 + entrySet = Collections.synchronizedSet(new EntrySet(), this);
1.666 + return entrySet;
1.667 + }
1.668 +
1.669 + private class EntrySet extends AbstractSet<Map.Entry<K,V>> {
1.670 + public Iterator<Map.Entry<K,V>> iterator() {
1.671 + return getIterator(ENTRIES);
1.672 + }
1.673 +
1.674 + public boolean add(Map.Entry<K,V> o) {
1.675 + return super.add(o);
1.676 + }
1.677 +
1.678 + public boolean contains(Object o) {
1.679 + if (!(o instanceof Map.Entry))
1.680 + return false;
1.681 + Map.Entry entry = (Map.Entry)o;
1.682 + Object key = entry.getKey();
1.683 + Entry[] tab = table;
1.684 + int hash = key.hashCode();
1.685 + int index = (hash & 0x7FFFFFFF) % tab.length;
1.686 +
1.687 + for (Entry e = tab[index]; e != null; e = e.next)
1.688 + if (e.hash==hash && e.equals(entry))
1.689 + return true;
1.690 + return false;
1.691 + }
1.692 +
1.693 + public boolean remove(Object o) {
1.694 + if (!(o instanceof Map.Entry))
1.695 + return false;
1.696 + Map.Entry<K,V> entry = (Map.Entry<K,V>) o;
1.697 + K key = entry.getKey();
1.698 + Entry[] tab = table;
1.699 + int hash = key.hashCode();
1.700 + int index = (hash & 0x7FFFFFFF) % tab.length;
1.701 +
1.702 + for (Entry<K,V> e = tab[index], prev = null; e != null;
1.703 + prev = e, e = e.next) {
1.704 + if (e.hash==hash && e.equals(entry)) {
1.705 + modCount++;
1.706 + if (prev != null)
1.707 + prev.next = e.next;
1.708 + else
1.709 + tab[index] = e.next;
1.710 +
1.711 + count--;
1.712 + e.value = null;
1.713 + return true;
1.714 + }
1.715 + }
1.716 + return false;
1.717 + }
1.718 +
1.719 + public int size() {
1.720 + return count;
1.721 + }
1.722 +
1.723 + public void clear() {
1.724 + Hashtable.this.clear();
1.725 + }
1.726 + }
1.727 +
1.728 + /**
1.729 + * Returns a {@link Collection} view of the values contained in this map.
1.730 + * The collection is backed by the map, so changes to the map are
1.731 + * reflected in the collection, and vice-versa. If the map is
1.732 + * modified while an iteration over the collection is in progress
1.733 + * (except through the iterator's own <tt>remove</tt> operation),
1.734 + * the results of the iteration are undefined. The collection
1.735 + * supports element removal, which removes the corresponding
1.736 + * mapping from the map, via the <tt>Iterator.remove</tt>,
1.737 + * <tt>Collection.remove</tt>, <tt>removeAll</tt>,
1.738 + * <tt>retainAll</tt> and <tt>clear</tt> operations. It does not
1.739 + * support the <tt>add</tt> or <tt>addAll</tt> operations.
1.740 + *
1.741 + * @since 1.2
1.742 + */
1.743 + public Collection<V> values() {
1.744 + if (values==null)
1.745 + values = Collections.synchronizedCollection(new ValueCollection(),
1.746 + this);
1.747 + return values;
1.748 + }
1.749 +
1.750 + private class ValueCollection extends AbstractCollection<V> {
1.751 + public Iterator<V> iterator() {
1.752 + return getIterator(VALUES);
1.753 + }
1.754 + public int size() {
1.755 + return count;
1.756 + }
1.757 + public boolean contains(Object o) {
1.758 + return containsValue(o);
1.759 + }
1.760 + public void clear() {
1.761 + Hashtable.this.clear();
1.762 + }
1.763 + }
1.764 +
1.765 + // Comparison and hashing
1.766 +
1.767 + /**
1.768 + * Compares the specified Object with this Map for equality,
1.769 + * as per the definition in the Map interface.
1.770 + *
1.771 + * @param o object to be compared for equality with this hashtable
1.772 + * @return true if the specified Object is equal to this Map
1.773 + * @see Map#equals(Object)
1.774 + * @since 1.2
1.775 + */
1.776 + public synchronized boolean equals(Object o) {
1.777 + if (o == this)
1.778 + return true;
1.779 +
1.780 + if (!(o instanceof Map))
1.781 + return false;
1.782 + Map<K,V> t = (Map<K,V>) o;
1.783 + if (t.size() != size())
1.784 + return false;
1.785 +
1.786 + try {
1.787 + Iterator<Map.Entry<K,V>> i = entrySet().iterator();
1.788 + while (i.hasNext()) {
1.789 + Map.Entry<K,V> e = i.next();
1.790 + K key = e.getKey();
1.791 + V value = e.getValue();
1.792 + if (value == null) {
1.793 + if (!(t.get(key)==null && t.containsKey(key)))
1.794 + return false;
1.795 + } else {
1.796 + if (!value.equals(t.get(key)))
1.797 + return false;
1.798 + }
1.799 + }
1.800 + } catch (ClassCastException unused) {
1.801 + return false;
1.802 + } catch (NullPointerException unused) {
1.803 + return false;
1.804 + }
1.805 +
1.806 + return true;
1.807 + }
1.808 +
1.809 + /**
1.810 + * Returns the hash code value for this Map as per the definition in the
1.811 + * Map interface.
1.812 + *
1.813 + * @see Map#hashCode()
1.814 + * @since 1.2
1.815 + */
1.816 + public synchronized int hashCode() {
1.817 + /*
1.818 + * This code detects the recursion caused by computing the hash code
1.819 + * of a self-referential hash table and prevents the stack overflow
1.820 + * that would otherwise result. This allows certain 1.1-era
1.821 + * applets with self-referential hash tables to work. This code
1.822 + * abuses the loadFactor field to do double-duty as a hashCode
1.823 + * in progress flag, so as not to worsen the space performance.
1.824 + * A negative load factor indicates that hash code computation is
1.825 + * in progress.
1.826 + */
1.827 + int h = 0;
1.828 + if (count == 0 || loadFactor < 0)
1.829 + return h; // Returns zero
1.830 +
1.831 + loadFactor = -loadFactor; // Mark hashCode computation in progress
1.832 + Entry[] tab = table;
1.833 + for (int i = 0; i < tab.length; i++)
1.834 + for (Entry e = tab[i]; e != null; e = e.next)
1.835 + h += e.key.hashCode() ^ e.value.hashCode();
1.836 + loadFactor = -loadFactor; // Mark hashCode computation complete
1.837 +
1.838 + return h;
1.839 + }
1.840 +
1.841 + /**
1.842 + * Hashtable collision list.
1.843 + */
1.844 + private static class Entry<K,V> implements Map.Entry<K,V> {
1.845 + int hash;
1.846 + K key;
1.847 + V value;
1.848 + Entry<K,V> next;
1.849 +
1.850 + protected Entry(int hash, K key, V value, Entry<K,V> next) {
1.851 + this.hash = hash;
1.852 + this.key = key;
1.853 + this.value = value;
1.854 + this.next = next;
1.855 + }
1.856 +
1.857 + protected Object clone() {
1.858 + return new Entry<>(hash, key, value,
1.859 + (next==null ? null : (Entry<K,V>) next.clone()));
1.860 + }
1.861 +
1.862 + // Map.Entry Ops
1.863 +
1.864 + public K getKey() {
1.865 + return key;
1.866 + }
1.867 +
1.868 + public V getValue() {
1.869 + return value;
1.870 + }
1.871 +
1.872 + public V setValue(V value) {
1.873 + if (value == null)
1.874 + throw new NullPointerException();
1.875 +
1.876 + V oldValue = this.value;
1.877 + this.value = value;
1.878 + return oldValue;
1.879 + }
1.880 +
1.881 + public boolean equals(Object o) {
1.882 + if (!(o instanceof Map.Entry))
1.883 + return false;
1.884 + Map.Entry e = (Map.Entry)o;
1.885 +
1.886 + return (key==null ? e.getKey()==null : key.equals(e.getKey())) &&
1.887 + (value==null ? e.getValue()==null : value.equals(e.getValue()));
1.888 + }
1.889 +
1.890 + public int hashCode() {
1.891 + return hash ^ (value==null ? 0 : value.hashCode());
1.892 + }
1.893 +
1.894 + public String toString() {
1.895 + return key.toString()+"="+value.toString();
1.896 + }
1.897 + }
1.898 +
1.899 + // Types of Enumerations/Iterations
1.900 + private static final int KEYS = 0;
1.901 + private static final int VALUES = 1;
1.902 + private static final int ENTRIES = 2;
1.903 +
1.904 + /**
1.905 + * A hashtable enumerator class. This class implements both the
1.906 + * Enumeration and Iterator interfaces, but individual instances
1.907 + * can be created with the Iterator methods disabled. This is necessary
1.908 + * to avoid unintentionally increasing the capabilities granted a user
1.909 + * by passing an Enumeration.
1.910 + */
1.911 + private class Enumerator<T> implements Enumeration<T>, Iterator<T> {
1.912 + Entry[] table = Hashtable.this.table;
1.913 + int index = table.length;
1.914 + Entry<K,V> entry = null;
1.915 + Entry<K,V> lastReturned = null;
1.916 + int type;
1.917 +
1.918 + /**
1.919 + * Indicates whether this Enumerator is serving as an Iterator
1.920 + * or an Enumeration. (true -> Iterator).
1.921 + */
1.922 + boolean iterator;
1.923 +
1.924 + /**
1.925 + * The modCount value that the iterator believes that the backing
1.926 + * Hashtable should have. If this expectation is violated, the iterator
1.927 + * has detected concurrent modification.
1.928 + */
1.929 + protected int expectedModCount = modCount;
1.930 +
1.931 + Enumerator(int type, boolean iterator) {
1.932 + this.type = type;
1.933 + this.iterator = iterator;
1.934 + }
1.935 +
1.936 + public boolean hasMoreElements() {
1.937 + Entry<K,V> e = entry;
1.938 + int i = index;
1.939 + Entry[] t = table;
1.940 + /* Use locals for faster loop iteration */
1.941 + while (e == null && i > 0) {
1.942 + e = t[--i];
1.943 + }
1.944 + entry = e;
1.945 + index = i;
1.946 + return e != null;
1.947 + }
1.948 +
1.949 + public T nextElement() {
1.950 + Entry<K,V> et = entry;
1.951 + int i = index;
1.952 + Entry[] t = table;
1.953 + /* Use locals for faster loop iteration */
1.954 + while (et == null && i > 0) {
1.955 + et = t[--i];
1.956 + }
1.957 + entry = et;
1.958 + index = i;
1.959 + if (et != null) {
1.960 + Entry<K,V> e = lastReturned = entry;
1.961 + entry = e.next;
1.962 + return type == KEYS ? (T)e.key : (type == VALUES ? (T)e.value : (T)e);
1.963 + }
1.964 + throw new NoSuchElementException("Hashtable Enumerator");
1.965 + }
1.966 +
1.967 + // Iterator methods
1.968 + public boolean hasNext() {
1.969 + return hasMoreElements();
1.970 + }
1.971 +
1.972 + public T next() {
1.973 + if (modCount != expectedModCount)
1.974 + throw new ConcurrentModificationException();
1.975 + return nextElement();
1.976 + }
1.977 +
1.978 + public void remove() {
1.979 + if (!iterator)
1.980 + throw new UnsupportedOperationException();
1.981 + if (lastReturned == null)
1.982 + throw new IllegalStateException("Hashtable Enumerator");
1.983 + if (modCount != expectedModCount)
1.984 + throw new ConcurrentModificationException();
1.985 +
1.986 + synchronized(Hashtable.this) {
1.987 + Entry[] tab = Hashtable.this.table;
1.988 + int index = (lastReturned.hash & 0x7FFFFFFF) % tab.length;
1.989 +
1.990 + for (Entry<K,V> e = tab[index], prev = null; e != null;
1.991 + prev = e, e = e.next) {
1.992 + if (e == lastReturned) {
1.993 + modCount++;
1.994 + expectedModCount++;
1.995 + if (prev == null)
1.996 + tab[index] = e.next;
1.997 + else
1.998 + prev.next = e.next;
1.999 + count--;
1.1000 + lastReturned = null;
1.1001 + return;
1.1002 + }
1.1003 + }
1.1004 + throw new ConcurrentModificationException();
1.1005 + }
1.1006 + }
1.1007 + }
1.1008 +}