1.1 --- a/emul/compact/src/main/java/java/util/Hashtable.java Tue Feb 26 14:55:55 2013 +0100
1.2 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000
1.3 @@ -1,1005 +0,0 @@
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 -}