1 /*
2 * Copyright (c) 1997, 2019, Oracle and/or its affiliates. All rights reserved.
3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
4 *
5 * This code is free software; you can redistribute it and/or modify it
6 * under the terms of the GNU General Public License version 2 only, as
7 * published by the Free Software Foundation. Oracle designates this
8 * particular file as subject to the "Classpath" exception as provided
9 * by Oracle in the LICENSE file that accompanied this code.
10 *
11 * This code is distributed in the hope that it will be useful, but WITHOUT
12 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
13 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
14 * version 2 for more details (a copy is included in the LICENSE file that
15 * accompanied this code).
16 *
17 * You should have received a copy of the GNU General Public License version
18 * 2 along with this work; if not, write to the Free Software Foundation,
19 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
20 *
21 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
22 * or visit www.oracle.com if you need additional information or have any
23 * questions.
24 */
25
26 package org.openjdk.bench.valhalla.corelibs.mapprotos;
27
28 import java.io.IOException;
29 import java.io.InvalidObjectException;
30 import java.io.PrintStream;
31 import java.io.Serializable;
32 import java.lang.reflect.Field;
33 import java.lang.reflect.InvocationTargetException;
34 import java.lang.reflect.Method;
35 import java.util.AbstractCollection;
36 //import java.util.AbstractMap;
37 import java.util.AbstractSet;
38 import java.util.Arrays;
39 import java.util.Collection;
40 import java.util.Collections;
41 import java.util.ConcurrentModificationException;
42 import java.util.Hashtable;
43 import java.util.Iterator;
44 import java.util.Map;
45 import java.util.Objects;
46 import java.util.Optional;
47 import java.util.TreeMap;
48 import java.util.NoSuchElementException;
49 import java.util.Set;
50 import java.util.Spliterator;
51 import java.util.function.BiConsumer;
52 import java.util.function.BiFunction;
53 import java.util.function.Consumer;
54 import java.util.function.Function;
55
56 /**
57 * HashMap using hashing and "open addressing".
58 * Hash entries are inline class instances.
59 * As described in <em>Introduction to Algorithms, 3rd Edition (The MIT Press)</em>,
60 * Section 11 Hash tables and Section 11.4 Open addressing.
61 *
62 * Open addressing is used to locate other entries for keys with the same hash.
63 * If multiple keys have the same hashcode, a rehashing mechanism
64 * is used to place the 2nd and subsequent
65 * key/value pairs at a non-optimal index in the table. Therefore,
66 * finding the entry for a desired key must rehash and examine subsequent
67 * entries until the value is value or it encounters an empty entry.
68 * When an entry is removed, the entry is marked as deleted, (not empty)
69 * to allow the search algorithm to keep looking; otherwise it would terminate
70 * the scan on the deleted entry, when it might be the case for some (other) key
71 * would have that same entry as part of its chain of possible locations for its hash.
72 * The default load factor (.75) should be re-evaluated in light of the open addressing
73 * computations. A higher number would reduce unused (wasted) space at the cost of
74 * increased search times, a lower number would increase unused (wasted) space but
75 * improve search times (assuming even hashcode distributions).
76 * Badly distributed hash values will result in incremental table growth and
77 * linear search performance.
78 * <p></p>
79 * During insertion the Robin Hood hash algorithm does a small optimization
80 * to reduce worst case rehash lengths.
81 * Removal of entries, does a compaction of the following entries to fill
82 * in free entries and reduce entry rehashling lengths based on
83 * "On Deletions in Open Addressing Hashing", by Rosa M. Jimenez and Conrado Martinz.
84 *
85 * <p>
86 * The only allocation that occurs during put operations is for the resizing of the entry table.
87 *
88 * <P>
89 * Hash table based implementation of the {@code Map} interface. This
90 * implementation provides all of the optional map operations, and permits
91 * {@code null} values and the {@code null} key. (The {@code HashMap}
92 * class is roughly equivalent to {@code Hashtable}, except that it is
93 * unsynchronized and permits nulls.) This class makes no guarantees as to
94 * the order of the map; in particular, it does not guarantee that the order
95 * will remain constant over time.
96 *
97 * <p>This implementation provides constant-time performance for the basic
98 * operations ({@code get} and {@code put}), assuming the hash function
99 * disperses the elements properly among the buckets. Iteration over
100 * collection views requires time proportional to the "capacity" of the
101 * {@code HashMap} instance (the number of buckets) plus its size (the number
102 * of key-value mappings). Thus, it's very important not to set the initial
103 * capacity too high (or the load factor too low) if iteration performance is
104 * important.
105 *
106 * <p>An instance of {@code HashMap} has two parameters that affect its
107 * performance: <i>initial capacity</i> and <i>load factor</i>. The
108 * <i>capacity</i> is the number of buckets in the hash table, and the initial
109 * capacity is simply the capacity at the time the hash table is created. The
110 * <i>load factor</i> is a measure of how full the hash table is allowed to
111 * get before its capacity is automatically increased. When the number of
112 * entries in the hash table exceeds the product of the load factor and the
113 * current capacity, the hash table is <i>rehashed</i> (that is, internal data
114 * structures are rebuilt) so that the hash table has approximately twice the
115 * number of buckets.
116 *
117 * <p>As a general rule, the default load factor (.75) offers a good
118 * tradeoff between time and space costs. Higher values decrease the
119 * space overhead but increase the lookup cost (reflected in most of
120 * the operations of the {@code HashMap} class, including
121 * {@code get} and {@code put}). The expected number of entries in
122 * the map and its load factor should be taken into account when
123 * setting its initial capacity, so as to minimize the number of
124 * rehash operations. If the initial capacity is greater than the
125 * maximum number of entries divided by the load factor, no rehash
126 * operations will ever occur.
127 *
128 * <p>If many mappings are to be stored in a {@code HashMap}
129 * instance, creating it with a sufficiently large capacity will allow
130 * the mappings to be stored more efficiently than letting it perform
131 * automatic rehashing as needed to grow the table. Note that using
132 * many keys with the same {@code hashCode()} is a sure way to slow
133 * down performance of any hash table.
134 * TBD: To ameliorate impact, when keys
135 * are {@link Comparable}, this class may use comparison order among
136 * keys to help break ties.
137 *
138 * <p><strong>Note that this implementation is not synchronized.</strong>
139 * If multiple threads access a hash map concurrently, and at least one of
140 * the threads modifies the map structurally, it <i>must</i> be
141 * synchronized externally. (A structural modification is any operation
142 * that adds or deletes one or more mappings; merely changing the value
143 * associated with a key that an instance already contains is not a
144 * structural modification.) This is typically accomplished by
145 * synchronizing on some object that naturally encapsulates the map.
146 *
147 * If no such object exists, the map should be "wrapped" using the
148 * {@link Collections#synchronizedMap Collections.synchronizedMap}
149 * method. This is best done at creation time, to prevent accidental
150 * unsynchronized access to the map:<pre>
151 * Map m = Collections.synchronizedMap(new HashMap(...));</pre>
152 *
153 * <p>The iterators returned by all of this class's "collection view methods"
154 * are <i>fail-fast</i>: if the map is structurally modified at any time after
155 * the iterator is created, in any way except through the iterator's own
156 * {@code remove} method, the iterator will throw a
157 * {@link ConcurrentModificationException}. Thus, in the face of concurrent
158 * modification, the iterator fails quickly and cleanly, rather than risking
159 * arbitrary, non-deterministic behavior at an undetermined time in the
160 * future.
161 *
162 * <p>Note that the fail-fast behavior of an iterator cannot be guaranteed
163 * as it is, generally speaking, impossible to make any hard guarantees in the
164 * presence of unsynchronized concurrent modification. Fail-fast iterators
165 * throw {@code ConcurrentModificationException} on a best-effort basis.
166 * Therefore, it would be wrong to write a program that depended on this
167 * exception for its correctness: <i>the fail-fast behavior of iterators
168 * should be used only to detect bugs.</i>
169 *
170 * <p>This class is a member of the
171 * <a href="{@docRoot}/java.base/java/util/package-summary.html#CollectionsFramework">
172 * Java Collections Framework</a>.
173 *
174 * @param <K> the type of keys maintained by this map
175 * @param <V> the type of mapped values
176 *
177 * @author Doug Lea
178 * @author Josh Bloch
179 * @author Arthur van Hoff
180 * @author Neal Gafter
181 * @see Object#hashCode()
182 * @see Collection
183 * @see Map
184 * @see TreeMap
185 * @see Hashtable
186 * @since 1.2
187 */
188 public class YHashMap<K,V> extends XAbstractMap<K,V>
189 implements Map<K,V>, Cloneable, Serializable {
190
191 private static final long serialVersionUID = 362498820763181265L;
192
193 /*
194 * Implementation notes.
195 *
196 * This map usually acts as a binned (bucketed) hash table.
197 * The concurrent-programming-like SSA-based coding style helps
198 * avoid aliasing errors amid all of the twisty pointer operations.
199 */
200
201 /**
202 * The default initial capacity - MUST be a power of two.
203 */
204 static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
205
206 /**
207 * The maximum capacity, used if a higher value is implicitly specified
208 * by either of the constructors with arguments.
209 * MUST be a power of two <= 1<<30.
210 */
211 static final int MAXIMUM_CAPACITY = 1 << 30;
212
213 /**
214 * The load factor used when none specified in constructor.
215 */
216 static final float DEFAULT_LOAD_FACTOR = 0.75f;
217
218
219 /**
220 * Basic hash bin node, used for most entries.
221 */
222 static inline class YNode<K,V> implements Map.Entry<K,V> {
223 final int hash;
224 final short probes; // maybe only a byte
225 final K key;
226 final V value;
227
228 YNode() {
229 this.hash = 0;
230 this.probes = 0;
231 this.key = null;
232 this.value = null;
233 }
234
235 YNode(int hash, K key, V value, int probes) {
236 this.hash = hash;
237 this.key = key;
238 this.value = value;
239 if (probes > 128)
240 throw new IllegalStateException("YNode probes overflow: " + probes);
241 this.probes = (short)probes;
242 }
243
244 boolean isEmpty() {
245 return probes == 0;
246 }
247
248 boolean isValue() {
249 return probes > 0;
250 }
251
252 boolean isDeleted() {
253 return probes < 0;
254 }
255
256 public final K getKey() { return key; }
257 public final V getValue() { return value; }
258 public final String toString() { return key + "=" + value + ", probes: " + probes; }
259 public final int hashCode() {
260 return Objects.hashCode(key) ^ Objects.hashCode(value);
261 }
262
263 public final V setValue(V newValue) {
264 throw new IllegalStateException("YNode cannot set a value");
265 }
266
267 public final boolean equals(Object o) {
268 if (o == this)
269 return true;
270 if (o instanceof Map.Entry) {
271 Map.Entry<?,?> e = (Map.Entry<?,?>)o;
272 if (Objects.equals(key, e.getKey()) &&
273 Objects.equals(value, e.getValue()))
274 return true;
275 }
276 return false;
277 }
278 }
279
280 inline class YNodeWrapper implements Map.Entry<K,V> {
281 int index;
282
283 YNodeWrapper(int index) {
284 this.index = index;
285 }
286
287 public K getKey() {
288 YNode<K,V> e = table[index];
289 return e.isEmpty() ? null : e.key;
290 }
291
292 public V getValue() {
293 YNode<K,V> e = table[index];
294 return e.isEmpty() ? null : e.value;
295 }
296
297 /**
298 * Replaces the value corresponding to this entry with the specified
299 * value (optional operation). (Writes through to the map.) The
300 * behavior of this call is undefined if the mapping has already been
301 * removed from the map (by the iterator's {@code remove} operation).
302 *
303 * @param value new value to be stored in this entry
304 * @return old value corresponding to the entry
305 * @throws UnsupportedOperationException if the {@code put} operation
306 * is not supported by the backing map
307 * @throws ClassCastException if the class of the specified value
308 * prevents it from being stored in the backing map
309 * @throws NullPointerException if the backing map does not permit
310 * null values, and the specified value is null
311 * @throws IllegalArgumentException if some property of this value
312 * prevents it from being stored in the backing map
313 * @throws IllegalStateException implementations may, but are not
314 * required to, throw this exception if the entry has been
315 * removed from the backing map.
316 */
317 public V setValue(V value) {
318 YNode<K,V> e = table[index];
319 assert e.isValue();
320 table[index] = new YNode(e.hash, e.key, value, 0);
321 return e.value;
322 }
323 }
324 /* ---------------- Static utilities -------------- */
325
326 /**
327 * Computes key.hashCode() and spreads (XORs) higher bits of hash
328 * to lower. Because the table uses power-of-two masking, sets of
329 * hashes that vary only in bits above the current mask will
330 * always collide. (Among known examples are sets of Float keys
331 * holding consecutive whole numbers in small tables.) So we
332 * apply a transform that spreads the impact of higher bits
333 * downward. There is a tradeoff between speed, utility, and
334 * quality of bit-spreading. Because many common sets of hashes
335 * are already reasonably distributed (so don't benefit from
336 * spreading), and because we use trees to handle large sets of
337 * collisions in bins, we just XOR some shifted bits in the
338 * cheapest possible way to reduce systematic lossage, as well as
339 * to incorporate impact of the highest bits that would otherwise
340 * never be used in index calculations because of table bounds.
341 */
342 static final int hash(Object key) {
343 int h;
344 return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
345 }
346
347 /**
348 * Returns a power of two size for the given target capacity.
349 */
350 static final int tableSizeFor(int cap) {
351 int n = -1 >>> Integer.numberOfLeadingZeros(cap - 1);
352 return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
353 }
354
355 /* ---------------- Fields -------------- */
356
357 /**
358 * The table, initialized on first use, and resized as
359 * necessary. When allocated, length is always a power of two.
360 * (We also tolerate length zero in some operations to allow
361 * bootstrapping mechanics that are currently not needed.)
362 */
363 transient YNode<K,V>[] table;
364
365 /**
366 * Holds cached entrySet(). Note that AbstractMap fields are used
367 * for keySet() and values().
368 */
369 transient Set<Map.Entry<K,V>> entrySet;
370
371 /**
372 * The number of key-value mappings contained in this map.
373 */
374 transient int size;
375
376 /**
377 * The number of times this HashMap has been structurally modified
378 * Structural modifications are those that change the number of mappings in
379 * the HashMap or otherwise modify its internal structure (e.g.,
380 * rehash). This field is used to make iterators on Collection-views of
381 * the HashMap fail-fast. (See ConcurrentModificationException).
382 */
383 transient int modCount;
384
385 /**
386 * The next size value at which to resize (capacity * load factor).
387 *
388 * @serial
389 */
390 // (The javadoc description is true upon serialization.
391 // Additionally, if the table array has not been allocated, this
392 // field holds the initial array capacity, or zero signifying
393 // DEFAULT_INITIAL_CAPACITY.)
394 int threshold;
395
396 /**
397 * The load factor for the hash table.
398 *
399 * @serial
400 */
401 final float loadFactor;
402
403 /* ---------------- Public operations -------------- */
404
405 /**
406 * Constructs an empty {@code HashMap} with the specified initial
407 * capacity and load factor.
408 *
409 * @param initialCapacity the initial capacity
410 * @param loadFactor the load factor
411 * @throws IllegalArgumentException if the initial capacity is negative
412 * or the load factor is nonpositive
413 */
414 public YHashMap(int initialCapacity, float loadFactor) {
415 if (initialCapacity < 0)
416 throw new IllegalArgumentException("Illegal initial capacity: " +
417 initialCapacity);
418 if (initialCapacity > MAXIMUM_CAPACITY)
419 initialCapacity = MAXIMUM_CAPACITY;
420 if (loadFactor <= 0 || Float.isNaN(loadFactor))
421 throw new IllegalArgumentException("Illegal load factor: " +
422 loadFactor);
423 this.loadFactor = loadFactor;
424 this.threshold = tableSizeFor(initialCapacity);
425 }
426
427 /**
428 * Constructs an empty {@code HashMap} with the specified initial
429 * capacity and the default load factor (0.75).
430 *
431 * @param initialCapacity the initial capacity.
432 * @throws IllegalArgumentException if the initial capacity is negative.
433 */
434 public YHashMap(int initialCapacity) {
435 this(initialCapacity, DEFAULT_LOAD_FACTOR);
436 }
437
438 /**
439 * Constructs an empty {@code HashMap} with the default initial capacity
440 * (16) and the default load factor (0.75).
441 */
442 public YHashMap() {
443 this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
444 }
445
446 /**
447 * Constructs a new {@code HashMap} with the same mappings as the
448 * specified {@code Map}. The {@code HashMap} is created with
449 * default load factor (0.75) and an initial capacity sufficient to
450 * hold the mappings in the specified {@code Map}.
451 *
452 * @param m the map whose mappings are to be placed in this map
453 * @throws NullPointerException if the specified map is null
454 */
455 public YHashMap(Map<? extends K, ? extends V> m) {
456 this.loadFactor = DEFAULT_LOAD_FACTOR;
457 putMapEntries(m, false);
458 }
459
460 /**
461 * Implements Map.putAll and Map constructor.
462 *
463 * @param m the map
464 * @param evict false when initially constructing this map, else true.
465 */
466 final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) {
467 int s = m.size();
468 if (s > 0) {
469 if (table == null) { // pre-size
470 float ft = ((float)s / loadFactor) + 1.0F;
471 int t = ((ft < (float)MAXIMUM_CAPACITY) ?
472 (int)ft : MAXIMUM_CAPACITY);
473 if (t > threshold)
474 threshold = tableSizeFor(t);
475 } else {
476 // Because of linked-list bucket constraints, we cannot
477 // expand all at once, but can reduce total resize
478 // effort by repeated doubling now vs later
479 while (s > threshold && table.length < MAXIMUM_CAPACITY)
480 resize();
481 }
482
483 for (Map.Entry<? extends K, ? extends V> e : m.entrySet()) {
484 K key = e.getKey();
485 V value = e.getValue();
486 putVal(hash(key), key, value, false);
487 }
488 }
489 }
490
491 /**
492 * Returns the number of key-value mappings in this map.
493 *
494 * @return the number of key-value mappings in this map
495 */
496 public int size() {
497 return size;
498 }
499
500 /**
501 * Returns {@code true} if this map contains no key-value mappings.
502 *
503 * @return {@code true} if this map contains no key-value mappings
504 */
505 public boolean isEmpty() {
506 return size == 0;
507 }
508
509 /**
510 * Returns the value to which the specified key is mapped,
511 * or {@code null} if this map contains no mapping for the key.
512 *
513 * <p>More formally, if this map contains a mapping from a key
514 * {@code k} to a value {@code v} such that {@code (key==null ? k==null :
515 * key.equals(k))}, then this method returns {@code v}; otherwise
516 * it returns {@code null}. (There can be at most one such mapping.)
517 *
518 * <p>A return value of {@code null} does not <i>necessarily</i>
519 * indicate that the map contains no mapping for the key; it's also
520 * possible that the map explicitly maps the key to {@code null}.
521 * The {@link #containsKey containsKey} operation may be used to
522 * distinguish these two cases.
523 *
524 * @see #put(Object, Object)
525 */
526 public V get(Object key) {
527 int hash = hash(key);
528 int i = getNode(hash, key);
529 if (i >= 0) {
530 return table[i].value;
531 }
532 return null; // not found no value
533
534 }
535
536 /**
537 * XImplements Map.get and related methods.
538 *
539 * @param hash hash for key
540 * @param key the key
541 * @return the index of a matching node or -1
542 */
543 private final int getNode(final int hash, Object key) {
544 YNode<K, V>[] tab;
545 final YNode<K, V> first;
546 int n;
547 K k;
548 if ((tab = table) != null && (n = tab.length) > 0) {
549 if ((first = tab[(n - 1) & hash]).isValue() &&
550 first.hash == hash &&
551 ((k = first.key) == key || (key != null && key.equals(k)))) {
552 return (n - 1) & hash;
553 }
554 if (first.isEmpty())
555 return -1;
556 // non-empty table and not first entry
557 final int rehash_hash = getRehash(hash);
558 int h = hash + rehash_hash; // start with next entry
559 for (int probes = 1; probes < tab.length; probes++, h += rehash_hash) {
560 final YNode<K, V> entry;
561 final int index;
562 if (((entry = tab[(index = ((n - 1) & h))]).isValue()) &&
563 entry.hash == hash &&
564 ((k = entry.key) == key || (key != null && key.equals(k))))
565 return index;
566 if (entry.isEmpty())
567 return -1; // search ended without finding the key
568 }
569 throw new RuntimeException("NYI: search exhausted"); // exhausted looking in the table
570 }
571 return -1; // not found; empty table
572 }
573
574 /**
575 * Returns {@code true} if this map contains a mapping for the
576 * specified key.
577 *
578 * @param key The key whose presence in this map is to be tested
579 * @return {@code true} if this map contains a mapping for the specified
580 * key.
581 */
582 public boolean containsKey(Object key) {
583 return getNode(hash(key), key) >= 0;
584 }
585
586 /**
587 * Associates the specified value with the specified key in this map.
588 * If the map previously contained a mapping for the key, the old
589 * value is replaced.
590 *
591 * @param key key with which the specified value is to be associated
592 * @param value value to be associated with the specified key
593 * @return the previous value associated with {@code key}, or
594 * {@code null} if there was no mapping for {@code key}.
595 * (A {@code null} return can also indicate that the map
596 * previously associated {@code null} with {@code key}.)
597 */
598 public V put(K key, V value) {
599 return putVal(hash(key), key, value, false);
600 }
601
602 /**
603 * Implements Map.put and related methods.
604 *
605 * @param hash hash for key
606 * @param key the key
607 * @param value the value to put
608 * @param onlyIfAbsent if true, don't change existing value
609 * @param evict if false, the table is in creation mode.
610 * @return previous value, or null if none
611 */
612 private final V putVal(int hash, K key, V value, boolean onlyIfAbsent) {
613 YNode<K, V>[] tab;
614 YNode<K, V> tp;
615 int n, i;
616 if ((tab = table) == null || (n = tab.length) == 0)
617 n = (tab = resize()).length;
618 // System.out.printf("putVal: h: %8x, k: %s, tab.len: %d%n", hash, key, n);
619 final int rehash_hash = getRehash(hash);
620 int h = hash;
621 int index = 0;
622 for (int probes = 1; probes <= tab.length; probes++, h += rehash_hash) {
623 YNode<K, V> entry;
624
625 entry = tab[(index = ((n - 1) & h))];
626 // System.out.printf("index: %d, probe: %d, e: %s%n", index, probes, entry);
627 if (entry.isEmpty()) {
628 // Absent; insert in the first place it could be added
629 tab[index] = new YNode(hash, key, value, probes);
630 break; // break to update modCount and size
631 }
632
633 if (entry.isValue() && entry.hash == hash &&
634 ((key = entry.key) == key || (key != null && key.equals(key)))) {
635 if (!onlyIfAbsent || entry.value == null)
636 tab[index] = new YNode(hash, key, value, entry.probes);
637 return entry.value;
638 }
639
640 // Robin Hood entry swap if..
641 if (probes > entry.probes) {
642 // The new entry is more needy than the current one
643 tab[index] = new YNode(hash, key, value, probes);
644 hash = entry.hash;
645 key = entry.key;
646 value = entry.value;
647 probes = entry.probes;
648 }
649
650 if (probes >= tab.length) {
651 dumpTable(table, "MAX: key:" + key);
652 throw new IllegalStateException("NYI: putVal table has no free entries");
653 }
654 }
655 // System.out.printf("inserted at %d: k: %s%n", index, tab[index]);
656 ++modCount;
657 if (++size > threshold)
658 resize();
659 return null;
660 }
661
662 /**
663 * Initializes or doubles table size. If null, allocates in
664 * accord with initial capacity target held in field threshold.
665 * Otherwise, because we are using power-of-two expansion, the
666 * elements from each bin must either stay at same index, or move
667 * with a power of two offset in the new table.
668 *
669 * @return the table
670 */
671 final YNode<K,V>[] resize() {
672 YNode<K,V>[] oldTab = table;
673 int oldCap = (oldTab == null) ? 0 : oldTab.length;
674 int oldThr = threshold;
675 int newCap, newThr = 0;
676 if (oldCap > 0) {
677 if (oldCap >= MAXIMUM_CAPACITY) {
678 threshold = Integer.MAX_VALUE;
679 return oldTab;
680 }
681 else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
682 oldCap >= DEFAULT_INITIAL_CAPACITY)
683 newThr = oldThr << 1; // double threshold
684 }
685 else if (oldThr > 0) // initial capacity was placed in threshold
686 newCap = oldThr;
687 else { // zero initial threshold signifies using defaults
688 newCap = DEFAULT_INITIAL_CAPACITY;
689 newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
690 }
691 if (newThr == 0) {
692 float ft = (float)newCap * loadFactor;
693 newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
694 (int)ft : Integer.MAX_VALUE);
695 }
696 threshold = newThr;
697 @SuppressWarnings({"rawtypes","unchecked"})
698 YNode<K,V>[] newTab = (YNode<K,V>[])new YNode[newCap];
699 table = newTab;
700 if (oldTab != null) {
701 for (int i = 0; i < oldCap; ++i) {
702 YNode<K,V> e;
703 if ((e = oldTab[i]).isValue()) {
704 final int ii;
705 if (newTab[ii = (newCap - 1) & e.hash].isEmpty()) {
706 newTab[ii] = new YNode(e.hash, e.key, e.value, 1);
707 } else {
708 final int rehash_hash = getRehash(e.hash);
709 int h = e.hash + rehash_hash;
710 for (int probes = 2; ; probes++, h += rehash_hash) {
711 final int index;
712 if (newTab[(index = ((newCap - 1) & h))].isEmpty()) {
713 newTab[index] = new YNode(e.hash, e.key, e.value, probes);
714 break;
715 }
716 if (probes > newTab.length)
717 throw new IllegalStateException("NYI resize: no support for overflow");
718 }
719 }
720 }
721 }
722 }
723 assert isTableOk() : "Table not ok after resize";
724 return newTab;
725 }
726
727 private void dumpTable(YNode<K, V>[] table, String msg) {
728 System.out.println(msg);
729 for (int i = 0; i < table.length; ++i) {
730 System.out.printf("%3d: %s%n", i, table[i]);
731 }
732 }
733
734 /**
735 * Copies all of the mappings from the specified map to this map.
736 * These mappings will replace any mappings that this map had for
737 * any of the keys currently in the specified map.
738 *
739 * @param m mappings to be stored in this map
740 * @throws NullPointerException if the specified map is null
741 */
742 public void putAll(Map<? extends K, ? extends V> m) {
743 putMapEntries(m, true);
744 }
745
746 /**
747 * Removes the mapping for the specified key from this map if present.
748 *
749 * @param key key whose mapping is to be removed from the map
750 * @return the previous value associated with {@code key}, or
751 * {@code null} if there was no mapping for {@code key}.
752 * (A {@code null} return can also indicate that the map
753 * previously associated {@code null} with {@code key}.)
754 */
755 public V remove(Object key) {
756 Optional<V> o = removeNode(hash(key), key, null, false, true);
757 return o.orElse(null);
758 }
759
760 /**
761 * Implements Map.remove and related methods.
762 *
763 * @param hash hash for key
764 * @param key the key
765 * @param value the value to match if matchValue, else ignored
766 * @param matchValue if true only remove if value is equal
767 * @param movable if false do not move other nodes while removing
768 * @return the node, or null if none
769 */
770 private final Optional<V> removeNode(final int hash, Object key, Object value,
771 boolean matchValue, boolean movable) {
772 YNode<K, V>[] tab;
773 YNode<K, V> entry;
774 V v = null;
775 int curr;
776 int n;
777 if ((tab = table) != null && (n = tab.length) > 0 &&
778 (curr = getNode(hash, key)) >= 0 &&
779 (entry = tab[curr]).isValue() &&
780 ((!matchValue || (v = entry.value) == value ||
781 (value != null && value.equals(v))))) {
782 // found entry; free and compress
783 // System.out.printf("remove index: %d, e: %s%n", curr, entry);
784 ++modCount;
785 --size;
786 final int rehash_hash = getRehash(hash);
787 int h = hash + rehash_hash;
788 for (int probes = 1; probes <= tab.length; probes++, h += rehash_hash) {
789 YNode<K, V> alt;
790 int index;
791 alt = tab[(index = ((n - 1) & h))];
792 if (alt.probes > probes) {
793 // move alt to curr
794 tab[curr] = new YNode(alt.hash, alt.key, alt.value, alt.probes - probes);
795 tab[index] = new YNode();
796 curr = index;
797 probes = 0;
798 } else {
799 return Optional.ofNullable(v);
800 }
801 }
802 throw new IllegalStateException("NYI: removeNode no support for overflow");
803 }
804 return Optional.empty();
805 }
806
807 // Rehash delta based on original hash and always odd.
808 // Does not use current hash to have a consistent stride.
809 private static int getRehash(int hash) {
810 return 3;
811 }
812
813 /**
814 * Removes all of the mappings from this map.
815 * The map will be empty after this call returns.
816 */
817 public void clear() {
818 YNode<K,V>[] tab;
819 modCount++;
820 if ((tab = table) != null && size > 0) {
821 size = 0;
822 for (int i = 0; i < tab.length; i++)
823 tab[i] = YNode.default;
824 }
825 }
826
827 /**
828 * Returns {@code true} if this map maps one or more keys to the
829 * specified value.
830 *
831 * @param value value whose presence in this map is to be tested
832 * @return {@code true} if this map maps one or more keys to the
833 * specified value
834 */
835 public boolean containsValue(Object value) {
836 YNode<K,V>[] tab; V v;
837 if ((tab = table) != null && size > 0) {
838 for (YNode<K,V> te : tab) {
839 if (te.isValue()) {
840 if ((v = te.value) == value ||
841 (value != null && value.equals(v)))
842 return true;
843 }
844 }
845 }
846 return false;
847 }
848
849 /**
850 * Returns a {@link Set} view of the keys contained in this map.
851 * The set is backed by the map, so changes to the map are
852 * reflected in the set, and vice-versa. If the map is modified
853 * while an iteration over the set is in progress (except through
854 * the iterator's own {@code remove} operation), the results of
855 * the iteration are undefined. The set supports element removal,
856 * which removes the corresponding mapping from the map, via the
857 * {@code Iterator.remove}, {@code Set.remove},
858 * {@code removeAll}, {@code retainAll}, and {@code clear}
859 * operations. It does not support the {@code add} or {@code addAll}
860 * operations.
861 *
862 * @return a set view of the keys contained in this map
863 */
864 public Set<K> keySet() {
865 Set<K> ks = keySet;
866 if (ks == null) {
867 ks = new KeySet();
868 keySet = ks;
869 }
870 return ks;
871 }
872
873 /**
874 * Prepares the array for {@link Collection#toArray(Object[])} implementation.
875 * If supplied array is smaller than this map size, a new array is allocated.
876 * If supplied array is bigger than this map size, a null is written at size index.
877 *
878 * @param a an original array passed to {@code toArray()} method
879 * @param <T> type of array elements
880 * @return an array ready to be filled and returned from {@code toArray()} method.
881 */
882 @SuppressWarnings("unchecked")
883 final <T> T[] prepareArray(T[] a) {
884 int size = this.size;
885 if (a.length < size) {
886 return (T[]) java.lang.reflect.Array
887 .newInstance(a.getClass().getComponentType(), size);
888 }
889 if (a.length > size) {
890 a[size] = null;
891 }
892 return a;
893 }
894
895 /**
896 * Fills an array with this map keys and returns it. This method assumes
897 * that input array is big enough to fit all the keys. Use
898 * {@link #prepareArray(Object[])} to ensure this.
899 *
900 * @param a an array to fill
901 * @param <T> type of array elements
902 * @return supplied array
903 */
904 <T> T[] keysToArray(T[] a) {
905 Object[] r = a;
906 YNode<K,V>[] tab;
907 int idx = 0;
908 int i = 0;
909 if (size > 0 && (tab = table) != null) {
910 for (YNode<K,V> te : tab) {
911 if (te.isValue()) {
912 r[idx++] = te.key;
913 }
914 }
915 }
916 return a;
917 }
918
919 /**
920 * Fills an array with this map values and returns it. This method assumes
921 * that input array is big enough to fit all the values. Use
922 * {@link #prepareArray(Object[])} to ensure this.
923 *
924 * @param a an array to fill
925 * @param <T> type of array elements
926 * @return supplied array
927 */
928 <T> T[] valuesToArray(T[] a) {
929 Object[] r = a;
930 YNode<K,V>[] tab;
931 int idx = 0;
932 if (size > 0 && (tab = table) != null) {
933 for (YNode<K,V> te : tab) {
934 if (te.isValue()) {
935 r[idx++] = te.value;
936 }
937 }
938 }
939 return a;
940 }
941
942 final class KeySet extends AbstractSet<K> {
943 public final int size() { return size; }
944 public final void clear() { YHashMap.this.clear(); }
945 public final Iterator<K> iterator() { return new KeyIterator(); }
946 public final boolean contains(Object o) { return containsKey(o); }
947 public final boolean remove(Object key) {
948 return removeNode(hash(key), key, null, false, true).isPresent();
949 }
950 public final Spliterator<K> spliterator() {
951 throw new RuntimeException("KeySet.spliterator");
952 // new KeySpliterator<>(XHashMap.this, 0, -1, 0, 0);
953 }
954
955 public Object[] toArray() {
956 return keysToArray(new Object[size]);
957 }
958
959 public <T> T[] toArray(T[] a) {
960 return keysToArray(prepareArray(a));
961 }
962
963 public final void forEach(Consumer<? super K> action) {
964 YNode<K,V>[] tab;
965 if (action == null)
966 throw new NullPointerException();
967 if (size > 0 && (tab = table) != null) {
968 int mc = modCount;
969 for (YNode<K,V> te : tab) {
970 if (te.isValue()) {
971 action.accept(te.key);
972 }
973 }
974 if (modCount != mc)
975 throw new ConcurrentModificationException();
976 }
977 }
978 }
979
980 /**
981 * Returns a {@link Collection} view of the values contained in this map.
982 * The collection is backed by the map, so changes to the map are
983 * reflected in the collection, and vice-versa. If the map is
984 * modified while an iteration over the collection is in progress
985 * (except through the iterator's own {@code remove} operation),
986 * the results of the iteration are undefined. The collection
987 * supports element removal, which removes the corresponding
988 * mapping from the map, via the {@code Iterator.remove},
989 * {@code Collection.remove}, {@code removeAll},
990 * {@code retainAll} and {@code clear} operations. It does not
991 * support the {@code add} or {@code addAll} operations.
992 *
993 * @return a view of the values contained in this map
994 */
995 public Collection<V> values() {
996 Collection<V> vs = values;
997 if (vs == null) {
998 vs = new Values();
999 values = vs;
1000 }
1001 return vs;
1002 }
1003
1004 final class Values extends AbstractCollection<V> {
1005 public final int size() { return size; }
1006 public final void clear() { YHashMap.this.clear(); }
1007 public final Iterator<V> iterator() { return new ValueIterator(); }
1008 public final boolean contains(Object o) { return containsValue(o); }
1009 public final Spliterator<V> spliterator() {
1010 throw new RuntimeException("Values.spliterator");
1011 //new ValueSpliterator<>(XHashMap.this, 0, -1, 0, 0);
1012
1013 }
1014
1015 public Object[] toArray() {
1016 return valuesToArray(new Object[size]);
1017 }
1018
1019 public <T> T[] toArray(T[] a) {
1020 return valuesToArray(prepareArray(a));
1021 }
1022
1023 public final void forEach(Consumer<? super V> action) {
1024 YNode<K,V>[] tab;
1025 if (action == null)
1026 throw new NullPointerException();
1027 if (size > 0 && (tab = table) != null) {
1028 int mc = modCount;
1029 for (YNode<K,V> te : tab) {
1030 if (!te.isValue()) {
1031 action.accept(te.value);
1032 }
1033 }
1034 if (modCount != mc)
1035 throw new ConcurrentModificationException();
1036 }
1037 }
1038 }
1039
1040 /**
1041 * Returns a {@link Set} view of the mappings contained in this map.
1042 * The set is backed by the map, so changes to the map are
1043 * reflected in the set, and vice-versa. If the map is modified
1044 * while an iteration over the set is in progress (except through
1045 * the iterator's own {@code remove} operation, or through the
1046 * {@code setValue} operation on a map entry returned by the
1047 * iterator) the results of the iteration are undefined. The set
1048 * supports element removal, which removes the corresponding
1049 * mapping from the map, via the {@code Iterator.remove},
1050 * {@code Set.remove}, {@code removeAll}, {@code retainAll} and
1051 * {@code clear} operations. It does not support the
1052 * {@code add} or {@code addAll} operations.
1053 *
1054 * @return a set view of the mappings contained in this map
1055 */
1056 public Set<Map.Entry<K,V>> entrySet() {
1057 Set<Map.Entry<K,V>> es;
1058 return (es = entrySet) == null ? (entrySet = new EntrySet()) : es;
1059 }
1060
1061 final class EntrySet extends AbstractSet<Map.Entry<K,V>> {
1062 public final int size() { return size; }
1063 public final void clear() { YHashMap.this.clear(); }
1064 public final Iterator<Map.Entry<K,V>> iterator() {
1065 return new EntryIterator();
1066 }
1067 public final boolean contains(Object o) {
1068 if (!(o instanceof Map.Entry))
1069 return false;
1070 Map.Entry<?,?> e = (Map.Entry<?,?>) o;
1071 Object key = e.getKey();
1072 int index = getNode(hash(key), key);
1073 return index >= 0 && table[index].equals(e);
1074 }
1075 public final boolean remove(Object o) {
1076 if (o instanceof Map.Entry) {
1077 Map.Entry<?,?> e = (Map.Entry<?,?>) o;
1078 Object key = e.getKey();
1079 Object value = e.getValue();
1080 return removeNode(hash(key), key, value, true, true).isPresent();
1081 }
1082 return false;
1083 }
1084 public final Spliterator<Map.Entry<K,V>> spliterator() {
1085 throw new RuntimeException("EntrySet.spliterator");
1086 // return new EntrySpliterator<>(XHashMap.this, 0, -1, 0, 0);
1087 }
1088 public final void forEach(Consumer<? super Map.Entry<K,V>> action) {
1089 YNode<K,V>[] tab;
1090 if (action == null)
1091 throw new NullPointerException();
1092 if (size > 0 && (tab = table) != null) {
1093 int mc = modCount;
1094 for (YNode<K,V> te : tab) {
1095 if (te.isValue()) {
1096 action.accept(new YNodeWrapper(te.hash & (tab.length - 1)));
1097 }
1098 }
1099 if (modCount != mc)
1100 throw new ConcurrentModificationException();
1101 }
1102 }
1103 }
1104
1105 // Overrides of JDK8 Map extension methods
1106
1107 @Override
1108 public V getOrDefault(Object key, V defaultValue) {
1109 final int index;
1110 return (index = getNode(hash(key), key)) < 0 ? defaultValue : table[index].value;
1111 }
1112
1113 @Override
1114 public V putIfAbsent(K key, V value) {
1115 return putVal(hash(key), key, value, true);
1116 }
1117
1118 @Override
1119 public boolean remove(Object key, Object value) {
1120 return removeNode(hash(key), key, value, true, true).isPresent();
1121 }
1122
1123 @Override
1124 public boolean replace(K key, V oldValue, V newValue) {
1125 int hash, index;
1126 V v;
1127 if ((index = getNode((hash = hash(key)), key)) >= 0 &&
1128 ((v = table[index].value) == oldValue || (v != null && v.equals(oldValue)))) {
1129 table[index] = new YNode<>(hash, key, newValue, table[index].probes);
1130 return true;
1131 }
1132 return false;
1133 }
1134
1135 @Override
1136 public V replace(K key, V value) {
1137 int hash, index;
1138 V v;
1139 if ((index = getNode((hash = hash(key)), key)) >= 0) {
1140 V oldValue = table[index].value;
1141 table[index] = new YNode<>(hash, key, value, table[index].probes);
1142 return oldValue;
1143 }
1144 return null;
1145 }
1146
1147 /**
1148 * {@inheritDoc}
1149 *
1150 * <p>This method will, on a best-effort basis, throw a
1151 * {@link ConcurrentModificationException} if it is detected that the
1152 * mapping function modifies this map during computation.
1153 *
1154 * @throws ConcurrentModificationException if it is detected that the
1155 * mapping function modified this map
1156 */
1157 @Override
1158 public V computeIfAbsent(K key,
1159 Function<? super K, ? extends V> mappingFunction) {
1160 if (mappingFunction == null)
1161 throw new NullPointerException();
1162 int hash = hash(key);
1163 YNode<K,V>[] tab; YNode<K,V> first; int n, i;
1164 int index;
1165
1166 index = getNode(hash, key);
1167 if (index >= 0 && table[index].value != null)
1168 return table[index].value;
1169
1170 int mc = modCount;
1171 V v = mappingFunction.apply(key);
1172 if (mc != modCount) { throw new ConcurrentModificationException(); }
1173 if (v == null) {
1174 return null;
1175 } else if (index >= 0) {
1176 table[index] = new YNode<>(hash, key, v, 1);
1177 return v;
1178 }
1179 putVal(hash, key, v, false);
1180 // TBD: Watch the double counting
1181 modCount = mc + 1;
1182 ++size;
1183 return v;
1184 }
1185
1186 /**
1187 * {@inheritDoc}
1188 *
1189 * <p>This method will, on a best-effort basis, throw a
1190 * {@link ConcurrentModificationException} if it is detected that the
1191 * remapping function modifies this map during computation.
1192 *
1193 * @throws ConcurrentModificationException if it is detected that the
1194 * remapping function modified this map
1195 */
1196 @Override
1197 public V computeIfPresent(K key,
1198 BiFunction<? super K, ? super V, ? extends V> remappingFunction) {
1199 if (remappingFunction == null)
1200 throw new NullPointerException();
1201 V oldValue;
1202 int hash = hash(key);
1203 int index = getNode(hash, key);
1204 if (index >= 0 && (oldValue = table[index].value) != null) {
1205 int mc = modCount;
1206 V v = remappingFunction.apply(key, oldValue);
1207 if (mc != modCount) { throw new ConcurrentModificationException(); }
1208 if (v != null) {
1209 table[index] = new YNode(hash, key, v, table[index].probes);
1210 return v;
1211 }
1212 else
1213 removeNode(hash, key, null, false, true);
1214 }
1215 return null;
1216 }
1217
1218 /**
1219 * {@inheritDoc}
1220 *
1221 * <p>This method will, on a best-effort basis, throw a
1222 * {@link ConcurrentModificationException} if it is detected that the
1223 * remapping function modifies this map during computation.
1224 *
1225 * @throws ConcurrentModificationException if it is detected that the
1226 * remapping function modified this map
1227 */
1228 @Override
1229 public V compute(K key,
1230 BiFunction<? super K, ? super V, ? extends V> remappingFunction) {
1231 if (remappingFunction == null)
1232 throw new NullPointerException();
1233 return super.compute(key, remappingFunction);
1234 }
1235
1236 /**
1237 * {@inheritDoc}
1238 *
1239 * <p>This method will, on a best-effort basis, throw a
1240 * {@link ConcurrentModificationException} if it is detected that the
1241 * remapping function modifies this map during computation.
1242 *
1243 * @throws ConcurrentModificationException if it is detected that the
1244 * remapping function modified this map
1245 */
1246 @Override
1247 public V merge(K key, V value,
1248 BiFunction<? super V, ? super V, ? extends V> remappingFunction) {
1249 return super.merge(key, value, remappingFunction);
1250 }
1251
1252 @Override
1253 public void forEach(BiConsumer<? super K, ? super V> action) {
1254 YNode<K,V>[] tab;
1255 if (action == null)
1256 throw new NullPointerException();
1257 if (size > 0 && (tab = table) != null) {
1258 int mc = modCount;
1259 for (YNode<K,V> te : tab) {
1260 if (te.isValue()) {
1261 action.accept(te.key, te.value);
1262 }
1263 }
1264 // TBD: iterate over overflow
1265
1266 if (modCount != mc)
1267 throw new ConcurrentModificationException();
1268 }
1269 }
1270
1271 @Override
1272 public void replaceAll(BiFunction<? super K, ? super V, ? extends V> function) {
1273 super.replaceAll(function);
1274 }
1275
1276 /* ------------------------------------------------------------ */
1277 // Cloning and serialization
1278
1279 /**
1280 * Returns a shallow copy of this {@code HashMap} instance: the keys and
1281 * values themselves are not cloned.
1282 *
1283 * @return a shallow copy of this map
1284 */
1285 @SuppressWarnings("unchecked")
1286 @Override
1287 public Object clone() {
1288 YHashMap<K,V> result;
1289 try {
1290 result = (YHashMap<K,V>)super.clone();
1291 } catch (CloneNotSupportedException e) {
1292 // this shouldn't happen, since we are Cloneable
1293 throw new InternalError(e);
1294 }
1295 result.reinitialize();
1296 result.putMapEntries(this, false);
1297 return result;
1298 }
1299
1300 // These methods are also used when serializing HashSets
1301 final float loadFactor() { return loadFactor; }
1302 final int capacity() {
1303 return (table != null) ? table.length :
1304 (threshold > 0) ? threshold :
1305 DEFAULT_INITIAL_CAPACITY;
1306 }
1307
1308 /**
1309 * Saves this map to a stream (that is, serializes it).
1310 *
1311 * @param s the stream
1312 * @throws IOException if an I/O error occurs
1313 * @serialData The <i>capacity</i> of the HashMap (the length of the
1314 * bucket array) is emitted (int), followed by the
1315 * <i>size</i> (an int, the number of key-value
1316 * mappings), followed by the key (Object) and value (Object)
1317 * for each key-value mapping. The key-value mappings are
1318 * emitted in no particular order.
1319 */
1320 private void writeObject(java.io.ObjectOutputStream s)
1321 throws IOException {
1322 int buckets = capacity();
1323 // Write out the threshold, loadfactor, and any hidden stuff
1324 s.defaultWriteObject();
1325 s.writeInt(buckets);
1326 s.writeInt(size);
1327 internalWriteEntries(s);
1328 }
1329
1330 /**
1331 * Reconstitutes this map from a stream (that is, deserializes it).
1332 * @param s the stream
1333 * @throws ClassNotFoundException if the class of a serialized object
1334 * could not be found
1335 * @throws IOException if an I/O error occurs
1336 */
1337 private void readObject(java.io.ObjectInputStream s)
1338 throws IOException, ClassNotFoundException {
1339 // Read in the threshold (ignored), loadfactor, and any hidden stuff
1340 s.defaultReadObject();
1341 reinitialize();
1342 if (loadFactor <= 0 || Float.isNaN(loadFactor))
1343 throw new InvalidObjectException("Illegal load factor: " +
1344 loadFactor);
1345 s.readInt(); // Read and ignore number of buckets
1346 int mappings = s.readInt(); // Read number of mappings (size)
1347 if (mappings < 0)
1348 throw new InvalidObjectException("Illegal mappings count: " +
1349 mappings);
1350 else if (mappings > 0) { // (if zero, use defaults)
1351 // Size the table using given load factor only if within
1352 // range of 0.25...4.0
1353 float lf = Math.min(Math.max(0.25f, loadFactor), 4.0f);
1354 float fc = (float)mappings / lf + 1.0f;
1355 int cap = ((fc < DEFAULT_INITIAL_CAPACITY) ?
1356 DEFAULT_INITIAL_CAPACITY :
1357 (fc >= MAXIMUM_CAPACITY) ?
1358 MAXIMUM_CAPACITY :
1359 tableSizeFor((int)fc));
1360 float ft = (float)cap * lf;
1361 threshold = ((cap < MAXIMUM_CAPACITY && ft < MAXIMUM_CAPACITY) ?
1362 (int)ft : Integer.MAX_VALUE);
1363
1364 // Check Map.Entry[].class since it's the nearest public type to
1365 // what we're actually creating.
1366 // SharedSecrets.getJavaObjectInputStreamAccess().checkArray(s, Map.Entry[].class, cap);
1367 @SuppressWarnings({"rawtypes","unchecked"})
1368 YNode<K,V>[] tab = (YNode<K,V>[])new YNode[cap];
1369 table = tab;
1370
1371 // Read the keys and values, and put the mappings in the HashMap
1372 for (int i = 0; i < mappings; i++) {
1373 @SuppressWarnings("unchecked")
1374 K key = (K) s.readObject();
1375 @SuppressWarnings("unchecked")
1376 V value = (V) s.readObject();
1377 putVal(hash(key), key, value, false);
1378 }
1379 }
1380 }
1381
1382 /* ------------------------------------------------------------ */
1383 // iterators
1384
1385 abstract class HashIterator {
1386 int next; // next entry to return
1387 int current; // current entry
1388 int expectedModCount; // for fast-fail
1389
1390 HashIterator() {
1391 expectedModCount = modCount;
1392 YNode<K,V>[] t = table;
1393 current = -1;
1394 next = 0;
1395 if (t != null && size > 0) { // advance to first entry
1396 for (; next < t.length && !t[next].isValue(); next++) {
1397 }
1398 }
1399 }
1400
1401 public final boolean hasNext() {
1402 return table != null && next < table.length;
1403 }
1404
1405 final Entry<K,V> nextNode() {
1406 if (modCount != expectedModCount)
1407 throw new ConcurrentModificationException("ex: " + expectedModCount + " != " + modCount);
1408 if (!hasNext())
1409 throw new NoSuchElementException();
1410 current = next;
1411 assert current >= 0 && current < table.length;
1412
1413 YNode<K,V>[] t = table;
1414 for (++next; next < t.length && !t[next].isValue(); next++) {
1415
1416 }
1417
1418 return new YNodeWrapper(current);
1419 }
1420
1421 public final void remove() {
1422 if (current < 0 || current > table.length)
1423 throw new IllegalStateException();
1424 if (modCount != expectedModCount)
1425 throw new ConcurrentModificationException();
1426 YNode<K, V> p = table[current];
1427 removeNode(p.hash, p.key, null, false, false);
1428 current = -1;
1429 expectedModCount = modCount;
1430 }
1431 }
1432
1433 final class KeyIterator extends HashIterator
1434 implements Iterator<K> {
1435 public final K next() { return nextNode().getKey(); }
1436 }
1437
1438 final class ValueIterator extends HashIterator
1439 implements Iterator<V> {
1440 public final V next() { return nextNode().getValue(); }
1441 }
1442
1443 final class EntryIterator extends HashIterator
1444 implements Iterator<Map.Entry<K,V>> {
1445 public final Map.Entry<K,V> next() { return nextNode(); }
1446 }
1447
1448 /**
1449 * Reset to initial default state. Called by clone and readObject.
1450 */
1451 void reinitialize() {
1452 table = null;
1453 entrySet = null;
1454 keySet = null;
1455 values = null;
1456 modCount = 0;
1457 threshold = 0;
1458 size = 0;
1459 }
1460
1461 // Called only from writeObject, to ensure compatible ordering.
1462 void internalWriteEntries(java.io.ObjectOutputStream s) throws IOException {
1463 YNode<K,V>[] tab;
1464 if (size > 0 && (tab = table) != null) {
1465 for (YNode<K,V> te : tab) {
1466 if (te.isValue()) {
1467 s.writeObject(te.key);
1468 s.writeObject(te.value);
1469 }
1470 }
1471 }
1472 }
1473
1474
1475 /**
1476 * Check each entry in the table.
1477 * - FindNode will find it from the key.
1478 * - the probes value is correct.
1479 */
1480 boolean isTableOk() {
1481 boolean ok = true;
1482 int n;
1483 final YNode<K,V>[] tab;
1484 if ((tab = table) == null || (n = tab.length) == 0)
1485 return ok;
1486 for (YNode<K,V> te : tab) {
1487 if (te.isValue()) {
1488 int hash = hash(te.key);
1489 int origIndex = (n - 1) & hash;
1490 int index = getNode(hash, te.key);
1491 if (index < 0) {
1492 ok = false;
1493 System.out.printf("ERROR: getNode at index: %d did not find " +
1494 "the entry: %s%n", origIndex, te);
1495 } else {
1496 int th;
1497 if ((th = hash(te.key)) != te.hash) {
1498 ok = false;
1499 System.out.printf("ERROR: computed hash not equal stored hash: " +
1500 "expected: %8x, actual: %8x, te: %s%n", te.hash, th, te);
1501 }
1502 final int rehash_hash = getRehash(hash);
1503 int h = hash;
1504 for (int probes = 1; probes < tab.length; probes++, h += rehash_hash) {
1505 int i = (n - 1) & h;
1506 if (i == index) {
1507 if (probes != te.probes) {
1508 ok = false;
1509 System.out.printf("ERROR: computed probes %d not equal recorded probes: " +
1510 "%d for entry: %s%n",
1511 probes, te.probes, te);
1512 }
1513 break;
1514 }
1515 if (probes == 50) {
1516 System.out.printf("probes > 50: te: %s%n");
1517 }
1518 }
1519
1520 }
1521 }
1522 }
1523 return ok;
1524 }
1525
1526 public void dumpStats(PrintStream out) {
1527 out.printf("%s instance: size: %d%n", this.getClass().getName(), this.size());
1528 long size = heapSize();
1529 long bytesPer = size / this.size();
1530 out.printf(" heap size: %d(bytes), avg bytes per entry: %d, table len: %d%n",
1531 size, bytesPer, table.length);
1532 long[] types = entryTypes();
1533 out.printf(" values: %d, empty: %d%n",
1534 types[0], types[1]);
1535 int[] rehashes = entryRehashes();
1536 out.printf(" hash collision histogram: max: %d, %s%n",
1537 rehashes.length - 1, Arrays.toString(rehashes));
1538 if (!isTableOk()) {
1539 dumpTable(table, "Table:");
1540 }
1541 }
1542
1543 private long[] entryTypes() {
1544 long[] counts = new long[2];
1545 for (YNode<K,V> te : table) {
1546 if (te.isEmpty())
1547 counts[1]++;
1548 else
1549 counts[0]++;
1550 }
1551 return counts;
1552 }
1553
1554 // Returns a histogram array of the number of rehashs needed to find each key.
1555 private int[] entryRehashes() {
1556 int[] counts = new int[table.length + 1];
1557 YNode<K,V>[] tab = table;
1558 int n = tab.length;
1559 K key;
1560 for (YNode<K,V> te : tab) {
1561
1562 if (!te.isValue())
1563 continue;
1564 final int rehash_hash = getRehash(te.hash); // arbitrary but at least odd
1565 int h = te.hash;
1566 int count;
1567 for (count = 0; count < tab.length; count++, h += rehash_hash) {
1568 final YNode<K, V> entry;
1569 final int index;
1570 if ((entry = tab[(index = ((n - 1) & h))]).isValue() &&
1571 entry.hash == te.hash &&
1572 ((key = entry.key) == key || (key != null && key.equals(key)))) {
1573 break;
1574 }
1575 }
1576
1577 counts[count]++;
1578 }
1579
1580 int i;
1581 for (i = counts.length - 1; i >= 0 && counts[i] == 0; i--) {
1582 }
1583 counts = Arrays.copyOf(counts, i + 1);
1584 return counts;
1585 }
1586
1587 private long heapSize() {
1588 long acc = objectSizeMaybe(this);
1589 return acc + objectSizeMaybe(table);
1590 }
1591
1592 private long objectSizeMaybe(Object o) {
1593 try {
1594 return (mObjectSize != null)
1595 ? (long)mObjectSize.invoke(null, o)
1596 : 0L;
1597 } catch (IllegalAccessException | InvocationTargetException e) {
1598 return 0L;
1599 }
1600 }
1601
1602 private static boolean hasObjectSize = false;
1603 private static Method mObjectSize = getObjectSizeMethod();
1604
1605 private static Method getObjectSizeMethod() {
1606 try {
1607 Method m = Objects.class.getDeclaredMethod("getObjectSize", Object.class);
1608 hasObjectSize = true;
1609 return m;
1610 } catch (NoSuchMethodException nsme) {
1611 return null;
1612 }
1613 }
1614
1615 }
1616