This program is free software; you can redistribute it and/or modify it
under the terms of the GNU General Public License as published by the Free
Software Foundation; either version 2 of the License, or (at your option)
any later version.
This program is distributed in the hope that it will be useful, but WITHOUT
ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for
more details.
You should have received a copy of the GNU General Public License along
with this program; if not, write to the Free Software Foundation, Inc., 59
Temple Place, Suite 330, Boston, MA 02111-1307 USA
Also add information on how to contact you by electronic and paper mail.
If the program is interactive, make it output a short notice like this when it
starts in an interactive mode:
Gnomovision version 69, Copyright (C) year name of author Gnomovision comes
with ABSOLUTELY NO WARRANTY; for details type 'show w'. This is free
software, and you are welcome to redistribute it under certain conditions;
type 'show c' for details.
The hypothetical commands 'show w' and 'show c' should show the appropriate
parts of the General Public License. Of course, the commands you use may be
called something other than 'show w' and 'show c'; they could even be
mouse-clicks or menu items--whatever suits your program.
You should also get your employer (if you work as a programmer) or your school,
if any, to sign a "copyright disclaimer" for the program, if necessary. Here
is a sample; alter the names:
Yoyodyne, Inc., hereby disclaims all copyright interest in the program
'Gnomovision' (which makes passes at compilers) written by James Hacker.
signature of Ty Coon, 1 April 1989
Ty Coon, President of Vice
This General Public License does not permit incorporating your program into
proprietary programs. If your program is a subroutine library, you may
consider it more useful to permit linking proprietary applications with the
library. If this is what you want to do, use the GNU Library General Public
License instead of this License.
"CLASSPATH" EXCEPTION TO THE GPL
Certain source files distributed by Oracle America and/or its affiliates are
subject to the following clarification and special exception to the GPL, but
only where Oracle has expressly included in the particular source file's header
the words "Oracle designates this particular file as subject to the "Classpath"
exception as provided by Oracle in the LICENSE file that accompanied this code."
Linking this library statically or dynamically with other modules is making
a combined work based on this library. Thus, the terms and conditions of
the GNU General Public License cover the whole combination.
As a special exception, the copyright holders of this library give you
permission to link this library with independent modules to produce an
executable, regardless of the license terms of these independent modules,
and to copy and distribute the resulting executable under terms of your
choice, provided that you also meet, for each linked independent module,
the terms and conditions of the license of that module. An independent
module is a module which is not derived from or based on this library. If
you modify this library, you may extend this exception to your version of
the library, but you are not obligated to do so. If you do not wish to do
so, delete this exception statement from your version.
SAAbstractMap.java 0000664 0000000 0000000 00000072246 14706132271 0037310 0 ustar 00root root 0000000 0000000 ObjectLayout-ObjectLayout-cdd394c/ObjectLayout-examples/src/main/java/org/ObjectLayout/examples/util package org.ObjectLayout.examples.util;
/* Ported from OpenJDK8's java.util.AbstractMap by Gil Tene.
* Copyright (c) 2015, Gil Tene. All rights reserved.
* Please note the LICENSE file in this directory, and the below
* Oracle copyright, GPLv2 license notice, and Classpath EXception.
*/
/*
* Copyright (c) 1997, 2013, Oracle and/or its affiliates. All rights reserved.
* DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
*
* This code is free software; you can redistribute it and/or modify it
* under the terms of the GNU General Public License version 2 only, as
* published by the Free Software Foundation. Oracle designates this
* particular file as subject to the "Classpath" exception as provided
* by Oracle in the LICENSE file that accompanied this code.
*
* This code is distributed in the hope that it will be useful, but WITHOUT
* ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
* FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
* version 2 for more details (a copy is included in the LICENSE file that
* accompanied this code).
*
* You should have received a copy of the GNU General Public License version
* 2 along with this work; if not, write to the Free Software Foundation,
* Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
*
* Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
* or visit www.oracle.com if you need additional information or have any
* questions.
*/
import java.util.*;
/**
* This class provides a skeletal implementation of the Map
* interface, to minimize the effort required to implement this interface.
*
* To implement an unmodifiable map, the programmer needs only to extend this
* class and provide an implementation for the entrySet method, which
* returns a set-view of the map's mappings. Typically, the returned set
* will, in turn, be implemented atop AbstractSet. This set should
* not support the add or remove methods, and its iterator
* should not support the remove method.
*
*
To implement a modifiable map, the programmer must additionally override
* this class's put method (which otherwise throws an
* UnsupportedOperationException), and the iterator returned by
* entrySet().iterator() must additionally implement its
* remove method.
*
*
The programmer should generally provide a void (no argument) and map
* constructor, as per the recommendation in the Map interface
* specification.
*
*
The documentation for each non-abstract method in this class describes its
* implementation in detail. Each of these methods may be overridden if the
* map being implemented admits a more efficient implementation.
*
*
This class is a member of the
*
* Java Collections Framework.
*
* @param the type of keys maintained by this map
* @param the type of mapped values
*
* @author Josh Bloch
* @author Neal Gafter
* @see Map
* @see Collection
* @since 1.2
*/
public abstract class SAAbstractMap implements Map {
/**
* Sole constructor. (For invocation by subclass constructors, typically
* implicit.)
*/
protected SAAbstractMap() {
}
// Query Operations
/**
* {@inheritDoc}
*
* @implSpec
* This implementation returns entrySet().size().
*/
public int size() {
return entrySet().size();
}
/**
* {@inheritDoc}
*
* @implSpec
* This implementation returns size() == 0.
*/
public boolean isEmpty() {
return size() == 0;
}
/**
* {@inheritDoc}
*
* @implSpec
* This implementation iterates over entrySet() searching
* for an entry with the specified value. If such an entry is found,
* true is returned. If the iteration terminates without
* finding such an entry, false is returned. Note that this
* implementation requires linear time in the size of the map.
*
* @throws ClassCastException {@inheritDoc}
* @throws NullPointerException {@inheritDoc}
*/
public boolean containsValue(Object value) {
Iterator> i = entrySet().iterator();
if (value==null) {
while (i.hasNext()) {
Entry e = i.next();
if (e.getValue()==null)
return true;
}
} else {
while (i.hasNext()) {
Entry e = i.next();
if (value.equals(e.getValue()))
return true;
}
}
return false;
}
/**
* {@inheritDoc}
*
* @implSpec
* This implementation iterates over entrySet() searching
* for an entry with the specified key. If such an entry is found,
* true is returned. If the iteration terminates without
* finding such an entry, false is returned. Note that this
* implementation requires linear time in the size of the map; many
* implementations will override this method.
*
* @throws ClassCastException {@inheritDoc}
* @throws NullPointerException {@inheritDoc}
*/
public boolean containsKey(Object key) {
Iterator> i = entrySet().iterator();
if (key==null) {
while (i.hasNext()) {
Entry e = i.next();
if (e.getKey()==null)
return true;
}
} else {
while (i.hasNext()) {
Entry e = i.next();
if (key.equals(e.getKey()))
return true;
}
}
return false;
}
/**
* {@inheritDoc}
*
* @implSpec
* This implementation iterates over entrySet() searching
* for an entry with the specified key. If such an entry is found,
* the entry's value is returned. If the iteration terminates without
* finding such an entry, null is returned. Note that this
* implementation requires linear time in the size of the map; many
* implementations will override this method.
*
* @throws ClassCastException {@inheritDoc}
* @throws NullPointerException {@inheritDoc}
*/
public V get(Object key) {
Iterator> i = entrySet().iterator();
if (key==null) {
while (i.hasNext()) {
Entry e = i.next();
if (e.getKey()==null)
return e.getValue();
}
} else {
while (i.hasNext()) {
Entry e = i.next();
if (key.equals(e.getKey()))
return e.getValue();
}
}
return null;
}
// Modification Operations
/**
* {@inheritDoc}
*
* @implSpec
* This implementation always throws an
* UnsupportedOperationException.
*
* @throws UnsupportedOperationException {@inheritDoc}
* @throws ClassCastException {@inheritDoc}
* @throws NullPointerException {@inheritDoc}
* @throws IllegalArgumentException {@inheritDoc}
*/
public V put(K key, V value) {
throw new UnsupportedOperationException();
}
/**
* {@inheritDoc}
*
* @implSpec
* This implementation iterates over entrySet() searching for an
* entry with the specified key. If such an entry is found, its value is
* obtained with its getValue operation, the entry is removed
* from the collection (and the backing map) with the iterator's
* remove operation, and the saved value is returned. If the
* iteration terminates without finding such an entry, null is
* returned. Note that this implementation requires linear time in the
* size of the map; many implementations will override this method.
*
* Note that this implementation throws an
* UnsupportedOperationException if the entrySet
* iterator does not support the remove method and this map
* contains a mapping for the specified key.
*
* @throws UnsupportedOperationException {@inheritDoc}
* @throws ClassCastException {@inheritDoc}
* @throws NullPointerException {@inheritDoc}
*/
public V remove(Object key) {
Iterator> i = entrySet().iterator();
Entry correctEntry = null;
if (key==null) {
while (correctEntry==null && i.hasNext()) {
Entry e = i.next();
if (e.getKey()==null)
correctEntry = e;
}
} else {
while (correctEntry==null && i.hasNext()) {
Entry e = i.next();
if (key.equals(e.getKey()))
correctEntry = e;
}
}
V oldValue = null;
if (correctEntry !=null) {
oldValue = correctEntry.getValue();
i.remove();
}
return oldValue;
}
// Bulk Operations
/**
* {@inheritDoc}
*
* @implSpec
* This implementation iterates over the specified map's
* entrySet() collection, and calls this map's put
* operation once for each entry returned by the iteration.
*
* Note that this implementation throws an
* UnsupportedOperationException if this map does not support
* the put operation and the specified map is nonempty.
*
* @throws UnsupportedOperationException {@inheritDoc}
* @throws ClassCastException {@inheritDoc}
* @throws NullPointerException {@inheritDoc}
* @throws IllegalArgumentException {@inheritDoc}
*/
public void putAll(Map m) {
for (Map.Entry e : m.entrySet())
put(e.getKey(), e.getValue());
}
/**
* {@inheritDoc}
*
* @implSpec
* This implementation calls entrySet().clear().
*
*
Note that this implementation throws an
* UnsupportedOperationException if the entrySet
* does not support the clear operation.
*
* @throws UnsupportedOperationException {@inheritDoc}
*/
public void clear() {
entrySet().clear();
}
// Views
/**
* Each of these fields are initialized to contain an instance of the
* appropriate view the first time this view is requested. The views are
* stateless, so there's no reason to create more than one of each.
*/
transient volatile Set keySet;
transient volatile Collection values;
/**
* {@inheritDoc}
*
* @implSpec
* This implementation returns a set that subclasses {@link AbstractSet}.
* The subclass's iterator method returns a "wrapper object" over this
* map's entrySet() iterator. The size method
* delegates to this map's size method and the
* contains method delegates to this map's
* containsKey method.
*
* The set is created the first time this method is called,
* and returned in response to all subsequent calls. No synchronization
* is performed, so there is a slight chance that multiple calls to this
* method will not all return the same set.
*/
public Set keySet() {
if (keySet == null) {
keySet = new AbstractSet() {
public Iterator iterator() {
return new Iterator() {
private Iterator> i = entrySet().iterator();
public boolean hasNext() {
return i.hasNext();
}
public K next() {
return i.next().getKey();
}
public void remove() {
i.remove();
}
};
}
public int size() {
return SAAbstractMap.this.size();
}
public boolean isEmpty() {
return SAAbstractMap.this.isEmpty();
}
public void clear() {
SAAbstractMap.this.clear();
}
public boolean contains(Object k) {
return SAAbstractMap.this.containsKey(k);
}
};
}
return keySet;
}
/**
* {@inheritDoc}
*
* @implSpec
* This implementation returns a collection that subclasses {@link
* AbstractCollection}. The subclass's iterator method returns a
* "wrapper object" over this map's entrySet() iterator.
* The size method delegates to this map's size
* method and the contains method delegates to this map's
* containsValue method.
*
* The collection is created the first time this method is called, and
* returned in response to all subsequent calls. No synchronization is
* performed, so there is a slight chance that multiple calls to this
* method will not all return the same collection.
*/
public Collection values() {
if (values == null) {
values = new AbstractCollection() {
public Iterator iterator() {
return new Iterator() {
private Iterator> i = entrySet().iterator();
public boolean hasNext() {
return i.hasNext();
}
public V next() {
return i.next().getValue();
}
public void remove() {
i.remove();
}
};
}
public int size() {
return SAAbstractMap.this.size();
}
public boolean isEmpty() {
return SAAbstractMap.this.isEmpty();
}
public void clear() {
SAAbstractMap.this.clear();
}
public boolean contains(Object v) {
return SAAbstractMap.this.containsValue(v);
}
};
}
return values;
}
public abstract Set> entrySet();
// Comparison and hashing
/**
* Compares the specified object with this map for equality. Returns
* true if the given object is also a map and the two maps
* represent the same mappings. More formally, two maps m1 and
* m2 represent the same mappings if
* m1.entrySet().equals(m2.entrySet()). This ensures that the
* equals method works properly across different implementations
* of the Map interface.
*
* @implSpec
* This implementation first checks if the specified object is this map;
* if so it returns true. Then, it checks if the specified
* object is a map whose size is identical to the size of this map; if
* not, it returns false. If so, it iterates over this map's
* entrySet collection, and checks that the specified map
* contains each mapping that this map contains. If the specified map
* fails to contain such a mapping, false is returned. If the
* iteration completes, true is returned.
*
* @param o object to be compared for equality with this map
* @return true if the specified object is equal to this map
*/
public boolean equals(Object o) {
if (o == this)
return true;
if (!(o instanceof Map))
return false;
Map m = (Map) o;
if (m.size() != size())
return false;
try {
Iterator> i = entrySet().iterator();
while (i.hasNext()) {
Entry e = i.next();
K key = e.getKey();
V value = e.getValue();
if (value == null) {
if (!(m.get(key)==null && m.containsKey(key)))
return false;
} else {
if (!value.equals(m.get(key)))
return false;
}
}
} catch (ClassCastException unused) {
return false;
} catch (NullPointerException unused) {
return false;
}
return true;
}
/**
* Returns the hash code value for this map. The hash code of a map is
* defined to be the sum of the hash codes of each entry in the map's
* entrySet() view. This ensures that m1.equals(m2)
* implies that m1.hashCode()==m2.hashCode() for any two maps
* m1 and m2, as required by the general contract of
* {@link Object#hashCode}.
*
* @implSpec
* This implementation iterates over entrySet(), calling
* {@link Map.Entry#hashCode hashCode()} on each element (entry) in the
* set, and adding up the results.
*
* @return the hash code value for this map
* @see Map.Entry#hashCode()
* @see Object#equals(Object)
* @see Set#equals(Object)
*/
public int hashCode() {
int h = 0;
Iterator> i = entrySet().iterator();
while (i.hasNext())
h += i.next().hashCode();
return h;
}
/**
* Returns a string representation of this map. The string representation
* consists of a list of key-value mappings in the order returned by the
* map's entrySet view's iterator, enclosed in braces
* ("{}"). Adjacent mappings are separated by the characters
* ", " (comma and space). Each key-value mapping is rendered as
* the key followed by an equals sign ("=") followed by the
* associated value. Keys and values are converted to strings as by
* {@link String#valueOf(Object)}.
*
* @return a string representation of this map
*/
public String toString() {
Iterator> i = entrySet().iterator();
if (! i.hasNext())
return "{}";
StringBuilder sb = new StringBuilder();
sb.append('{');
for (;;) {
Entry e = i.next();
K key = e.getKey();
V value = e.getValue();
sb.append(key == this ? "(this Map)" : key);
sb.append('=');
sb.append(value == this ? "(this Map)" : value);
if (! i.hasNext())
return sb.append('}').toString();
sb.append(',').append(' ');
}
}
/**
* Returns a shallow copy of this AbstractMap instance: the keys
* and values themselves are not cloned.
*
* @return a shallow copy of this map
*/
protected Object clone() throws CloneNotSupportedException {
SAAbstractMap result = (SAAbstractMap)super.clone();
result.keySet = null;
result.values = null;
return result;
}
/**
* Utility method for SimpleEntry and SimpleImmutableEntry.
* Test for equality, checking for nulls.
*
* NB: Do not replace with Object.equals until JDK-8015417 is resolved.
*/
private static boolean eq(Object o1, Object o2) {
return o1 == null ? o2 == null : o1.equals(o2);
}
// Implementation Note: SimpleEntry and SimpleImmutableEntry
// are distinct unrelated classes, even though they share
// some code. Since you can't add or subtract final-ness
// of a field in a subclass, they can't share representations,
// and the amount of duplicated code is too small to warrant
// exposing a common abstract class.
/**
* An Entry maintaining a key and a value. The value may be
* changed using the setValue method. This class
* facilitates the process of building custom map
* implementations. For example, it may be convenient to return
* arrays of SimpleEntry instances in method
* Map.entrySet().toArray.
*
* @since 1.6
*/
public static class SimpleEntry
implements Entry, java.io.Serializable
{
private static final long serialVersionUID = -8499721149061103585L;
private final K key;
private V value;
/**
* Creates an entry representing a mapping from the specified
* key to the specified value.
*
* @param key the key represented by this entry
* @param value the value represented by this entry
*/
public SimpleEntry(K key, V value) {
this.key = key;
this.value = value;
}
/**
* Creates an entry representing the same mapping as the
* specified entry.
*
* @param entry the entry to copy
*/
public SimpleEntry(Entry entry) {
this.key = entry.getKey();
this.value = entry.getValue();
}
/**
* Returns the key corresponding to this entry.
*
* @return the key corresponding to this entry
*/
public K getKey() {
return key;
}
/**
* Returns the value corresponding to this entry.
*
* @return the value corresponding to this entry
*/
public V getValue() {
return value;
}
/**
* Replaces the value corresponding to this entry with the specified
* value.
*
* @param value new value to be stored in this entry
* @return the old value corresponding to the entry
*/
public V setValue(V value) {
V oldValue = this.value;
this.value = value;
return oldValue;
}
/**
* Compares the specified object with this entry for equality.
* Returns {@code true} if the given object is also a map entry and
* the two entries represent the same mapping. More formally, two
* entries {@code e1} and {@code e2} represent the same mapping
* if
* (e1.getKey()==null ?
* e2.getKey()==null :
* e1.getKey().equals(e2.getKey()))
* &&
* (e1.getValue()==null ?
* e2.getValue()==null :
* e1.getValue().equals(e2.getValue()))
* This ensures that the {@code equals} method works properly across
* different implementations of the {@code Map.Entry} interface.
*
* @param o object to be compared for equality with this map entry
* @return {@code true} if the specified object is equal to this map
* entry
* @see #hashCode
*/
public boolean equals(Object o) {
if (!(o instanceof Map.Entry))
return false;
Map.Entry e = (Map.Entry)o;
return eq(key, e.getKey()) && eq(value, e.getValue());
}
/**
* Returns the hash code value for this map entry. The hash code
* of a map entry {@code e} is defined to be:
* (e.getKey()==null ? 0 : e.getKey().hashCode()) ^
* (e.getValue()==null ? 0 : e.getValue().hashCode())
* This ensures that {@code e1.equals(e2)} implies that
* {@code e1.hashCode()==e2.hashCode()} for any two Entries
* {@code e1} and {@code e2}, as required by the general
* contract of {@link Object#hashCode}.
*
* @return the hash code value for this map entry
* @see #equals
*/
public int hashCode() {
return (key == null ? 0 : key.hashCode()) ^
(value == null ? 0 : value.hashCode());
}
/**
* Returns a String representation of this map entry. This
* implementation returns the string representation of this
* entry's key followed by the equals character ("=")
* followed by the string representation of this entry's value.
*
* @return a String representation of this map entry
*/
public String toString() {
return key + "=" + value;
}
}
/**
* An Entry maintaining an immutable key and value. This class
* does not support method setValue. This class may be
* convenient in methods that return thread-safe snapshots of
* key-value mappings.
*
* @since 1.6
*/
public static class SimpleImmutableEntry
implements Entry, java.io.Serializable
{
private static final long serialVersionUID = 7138329143949025153L;
private final K key;
private final V value;
/**
* Creates an entry representing a mapping from the specified
* key to the specified value.
*
* @param key the key represented by this entry
* @param value the value represented by this entry
*/
public SimpleImmutableEntry(K key, V value) {
this.key = key;
this.value = value;
}
/**
* Creates an entry representing the same mapping as the
* specified entry.
*
* @param entry the entry to copy
*/
public SimpleImmutableEntry(Entry entry) {
this.key = entry.getKey();
this.value = entry.getValue();
}
/**
* Returns the key corresponding to this entry.
*
* @return the key corresponding to this entry
*/
public K getKey() {
return key;
}
/**
* Returns the value corresponding to this entry.
*
* @return the value corresponding to this entry
*/
public V getValue() {
return value;
}
/**
* Replaces the value corresponding to this entry with the specified
* value (optional operation). This implementation simply throws
* UnsupportedOperationException, as this class implements
* an immutable map entry.
*
* @param value new value to be stored in this entry
* @return (Does not return)
* @throws UnsupportedOperationException always
*/
public V setValue(V value) {
throw new UnsupportedOperationException();
}
/**
* Compares the specified object with this entry for equality.
* Returns {@code true} if the given object is also a map entry and
* the two entries represent the same mapping. More formally, two
* entries {@code e1} and {@code e2} represent the same mapping
* if
* (e1.getKey()==null ?
* e2.getKey()==null :
* e1.getKey().equals(e2.getKey()))
* &&
* (e1.getValue()==null ?
* e2.getValue()==null :
* e1.getValue().equals(e2.getValue()))
* This ensures that the {@code equals} method works properly across
* different implementations of the {@code Map.Entry} interface.
*
* @param o object to be compared for equality with this map entry
* @return {@code true} if the specified object is equal to this map
* entry
* @see #hashCode
*/
public boolean equals(Object o) {
if (!(o instanceof Map.Entry))
return false;
Map.Entry e = (Map.Entry)o;
return eq(key, e.getKey()) && eq(value, e.getValue());
}
/**
* Returns the hash code value for this map entry. The hash code
* of a map entry {@code e} is defined to be:
* (e.getKey()==null ? 0 : e.getKey().hashCode()) ^
* (e.getValue()==null ? 0 : e.getValue().hashCode())
* This ensures that {@code e1.equals(e2)} implies that
* {@code e1.hashCode()==e2.hashCode()} for any two Entries
* {@code e1} and {@code e2}, as required by the general
* contract of {@link Object#hashCode}.
*
* @return the hash code value for this map entry
* @see #equals
*/
public int hashCode() {
return (key == null ? 0 : key.hashCode()) ^
(value == null ? 0 : value.hashCode());
}
/**
* Returns a String representation of this map entry. This
* implementation returns the string representation of this
* entry's key followed by the equals character ("=")
* followed by the string representation of this entry's value.
*
* @return a String representation of this map entry
*/
public String toString() {
return key + "=" + value;
}
}
} SAHashMap.java 0000664 0000000 0000000 00000301120 14706132271 0036412 0 ustar 00root root 0000000 0000000 ObjectLayout-ObjectLayout-cdd394c/ObjectLayout-examples/src/main/java/org/ObjectLayout/examples/util package org.ObjectLayout.examples.util;
/* Ported from OpenJDK8's java.util.HashMap by Gil Tene.
* Copyright (c) 2015, Gil Tene. All rights reserved.
* Please note the LICENSE file in this directory, and the below
* Oracle copyright, GPLv2 license notice, and Classpath EXception.
*/
/*
* Copyright (c) 1997, 2013, Oracle and/or its affiliates. All rights reserved.
* DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
*
* This code is free software; you can redistribute it and/or modify it
* under the terms of the GNU General Public License version 2 only, as
* published by the Free Software Foundation. Oracle designates this
* particular file as subject to the "Classpath" exception as provided
* by Oracle in the LICENSE file that accompanied this code.
*
* This code is distributed in the hope that it will be useful, but WITHOUT
* ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
* FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
* version 2 for more details (a copy is included in the LICENSE file that
* accompanied this code).
*
* You should have received a copy of the GNU General Public License version
* 2 along with this work; if not, write to the Free Software Foundation,
* Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
*
* Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
* or visit www.oracle.com if you need additional information or have any
* questions.
*/
import java.io.IOException;
import java.io.InvalidObjectException;
import java.io.Serializable;
import java.lang.invoke.MethodHandles;
import java.lang.reflect.Constructor;
import java.lang.reflect.ParameterizedType;
import java.lang.reflect.Type;
import java.util.*;
import java.util.function.BiConsumer;
import java.util.function.BiFunction;
import java.util.function.Consumer;
import java.util.function.Function;
import org.ObjectLayout.CtorAndArgs;
import org.ObjectLayout.StructuredArray;
/**
* Hash table based implementation of the Map interface. This
* implementation provides all of the optional map operations, and permits
* null values and the null key. (The HashMap
* class is roughly equivalent to Hashtable, except that it is
* unsynchronized and permits nulls.) This class makes no guarantees as to
* the order of the map; in particular, it does not guarantee that the order
* will remain constant over time.
*
* This implementation provides constant-time performance for the basic
* operations (get and put), assuming the hash function
* disperses the elements properly among the buckets. Iteration over
* collection views requires time proportional to the "capacity" of the
* HashMap instance (the number of buckets) plus its size (the number
* of key-value mappings). Thus, it's very important not to set the initial
* capacity too high (or the load factor too low) if iteration performance is
* important.
*
*
An instance of HashMap has two parameters that affect its
* performance: initial capacity and load factor. The
* capacity is the number of buckets in the hash table, and the initial
* capacity is simply the capacity at the time the hash table is created. The
* load factor is a measure of how full the hash table is allowed to
* get before its capacity is automatically increased. When the number of
* entries in the hash table exceeds the product of the load factor and the
* current capacity, the hash table is rehashed (that is, internal data
* structures are rebuilt) so that the hash table has approximately twice the
* number of buckets.
*
*
As a general rule, the default load factor (.75) offers a good
* tradeoff between time and space costs. Higher values decrease the
* space overhead but increase the lookup cost (reflected in most of
* the operations of the HashMap class, including
* get and put). The expected number of entries in
* the map and its load factor should be taken into account when
* setting its initial capacity, so as to minimize the number of
* rehash operations. If the initial capacity is greater than the
* maximum number of entries divided by the load factor, no rehash
* operations will ever occur.
*
*
If many mappings are to be stored in a HashMap
* instance, creating it with a sufficiently large capacity will allow
* the mappings to be stored more efficiently than letting it perform
* automatic rehashing as needed to grow the table. Note that using
* many keys with the same {@code hashCode()} is a sure way to slow
* down performance of any hash table. To ameliorate impact, when keys
* are {@link Comparable}, this class may use comparison order among
* keys to help break ties.
*
*
Note that this implementation is not synchronized.
* If multiple threads access a hash map concurrently, and at least one of
* the threads modifies the map structurally, it must be
* synchronized externally. (A structural modification is any operation
* that adds or deletes one or more mappings; merely changing the value
* associated with a key that an instance already contains is not a
* structural modification.) This is typically accomplished by
* synchronizing on some object that naturally encapsulates the map.
*
* If no such object exists, the map should be "wrapped" using the
* {@link Collections#synchronizedMap Collections.synchronizedMap}
* method. This is best done at creation time, to prevent accidental
* unsynchronized access to the map:
* Map m = Collections.synchronizedMap(new HashMap(...));
*
* The iterators returned by all of this class's "collection view methods"
* are fail-fast: if the map is structurally modified at any time after
* the iterator is created, in any way except through the iterator's own
* remove method, the iterator will throw a
* {@link ConcurrentModificationException}. Thus, in the face of concurrent
* modification, the iterator fails quickly and cleanly, rather than risking
* arbitrary, non-deterministic behavior at an undetermined time in the
* future.
*
*
Note that the fail-fast behavior of an iterator cannot be guaranteed
* as it is, generally speaking, impossible to make any hard guarantees in the
* presence of unsynchronized concurrent modification. Fail-fast iterators
* throw ConcurrentModificationException on a best-effort basis.
* Therefore, it would be wrong to write a program that depended on this
* exception for its correctness: the fail-fast behavior of iterators
* should be used only to detect bugs.
*
*
This class is a member of the
*
* Java Collections Framework.
*
* @param the type of keys maintained by this map
* @param the type of mapped values
*
* @author Doug Lea
* @author Josh Bloch
* @author Arthur van Hoff
* @author Neal Gafter
* @see Object#hashCode()
* @see Collection
* @see Map
* @see TreeMap
* @see Hashtable
* @since 1.2
*/
public class SAHashMap extends SAAbstractMap
implements Map, Cloneable, Serializable {
private static final long serialVersionUID = 362498820763181265L;
/*
* Implementation notes.
*
* This map usually acts as a binned (bucketed) hash table, but
* when bins get too large, they are transformed into bins of
* TreeNodes, each structured similarly to those in
* java.util.TreeMap. Most methods try to use normal bins, but
* relay to TreeNode methods when applicable (simply by checking
* instanceof a node). Bins of TreeNodes may be traversed and
* used like any others, but additionally support faster lookup
* when overpopulated. However, since the vast majority of bins in
* normal use are not overpopulated, checking for existence of
* tree bins may be delayed in the course of table methods.
*
* Tree bins (i.e., bins whose elements are all TreeNodes) are
* ordered primarily by hashCode, but in the case of ties, if two
* elements are of the same "class C implements Comparable",
* type then their compareTo method is used for ordering. (We
* conservatively check generic types via reflection to validate
* this -- see method comparableClassFor). The added complexity
* of tree bins is worthwhile in providing worst-case O(log n)
* operations when keys either have distinct hashes or are
* orderable, Thus, performance degrades gracefully under
* accidental or malicious usages in which hashCode() methods
* return values that are poorly distributed, as well as those in
* which many keys share a hashCode, so long as they are also
* Comparable. (If neither of these apply, we may waste about a
* factor of two in time and space compared to taking no
* precautions. But the only known cases stem from poor user
* programming practices that are already so slow that this makes
* little difference.)
*
* Because TreeNodes are about twice the size of regular nodes, we
* use them only when bins contain enough nodes to warrant use
* (see TREEIFY_THRESHOLD). And when they become too small (due to
* removal or resizing) they are converted back to plain bins. In
* usages with well-distributed user hashCodes, tree bins are
* rarely used. Ideally, under random hashCodes, the frequency of
* nodes in bins follows a Poisson distribution
* (http://en.wikipedia.org/wiki/Poisson_distribution) with a
* parameter of about 0.5 on average for the default resizing
* threshold of 0.75, although with a large variance because of
* resizing granularity. Ignoring variance, the expected
* occurrences of list size k are (exp(-0.5) * pow(0.5, k) /
* factorial(k)). The first values are:
*
* 0: 0.60653066
* 1: 0.30326533
* 2: 0.07581633
* 3: 0.01263606
* 4: 0.00157952
* 5: 0.00015795
* 6: 0.00001316
* 7: 0.00000094
* 8: 0.00000006
* more: less than 1 in ten million
*
* The root of a tree bin is normally its first node. However,
* sometimes (currently only upon Iterator.remove), the root might
* be elsewhere, but can be recovered following parent links
* (method TreeNode.root()).
*
* All applicable internal methods accept a hash code as an
* argument (as normally supplied from a public method), allowing
* them to call each other without recomputing user hashCodes.
* Most internal methods also accept a "tab" argument, that is
* normally the current table, but may be a new or old one when
* resizing or converting.
*
* When bin lists are treeified, split, or untreeified, we keep
* them in the same relative access/traversal order (i.e., field
* Node.next) to better preserve locality, and to slightly
* simplify handling of splits and traversals that invoke
* iterator.remove. When using comparators on insertion, to keep a
* total ordering (or as close as is required here) across
* rebalancings, we compare classes and identityHashCodes as
* tie-breakers.
*
* The use and transitions among plain vs tree modes is
* complicated by the existence of subclass LinkedHashMap. See
* below for hook methods defined to be invoked upon insertion,
* removal and access that allow LinkedHashMap internals to
* otherwise remain independent of these mechanics. (This also
* requires that a map instance be passed to some utility methods
* that may create new nodes.)
*
* The concurrent-programming-like SSA-based coding style helps
* avoid aliasing errors amid all of the twisty pointer operations.
*/
/**
* The default initial capacity - MUST be a power of two.
*/
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
/**
* The maximum capacity, used if a higher value is implicitly specified
* by either of the constructors with arguments.
* MUST be a power of two <= 1<<30.
*/
static final int MAXIMUM_CAPACITY = 1 << 30;
/**
* The load factor used when none specified in constructor.
*/
static final float DEFAULT_LOAD_FACTOR = 0.75f;
/**
* The bin count threshold for using a tree rather than list for a
* bin. Bins are converted to trees when adding an element to a
* bin with at least this many nodes. The value must be greater
* than 2 and should be at least 8 to mesh with assumptions in
* tree removal about conversion back to plain bins upon
* shrinkage.
*/
static final int TREEIFY_THRESHOLD = 8;
/**
* The bin count threshold for untreeifying a (split) bin during a
* resize operation. Should be less than TREEIFY_THRESHOLD, and at
* most 6 to mesh with shrinkage detection under removal.
*/
static final int UNTREEIFY_THRESHOLD = 6;
/**
* The smallest table capacity for which bins may be treeified.
* (Otherwise the table is resized if too many nodes in a bin.)
* Should be at least 4 * TREEIFY_THRESHOLD to avoid conflicts
* between resizing and treeification thresholds.
*/
static final int MIN_TREEIFY_CAPACITY = 64;
/**
* Basic hash bin node, used for most entries. (See below for
* TreeNode subclass, and in LinkedHashMap for its Entry subclass.)
*/
static class Node implements Map.Entry {
int hash;
K key;
V value;
Node next;
private boolean isSentinel = true;
Node(int hash, K key, V value, Node next) {
this.hash = hash;
this.key = key;
this.value = value;
this.next = next;
this.isSentinel = false;
}
Node() {
}
public void setContents(int hash, K key, V value, Node next) {
this.hash = hash;
this.key = key;
this.value = value;
this.next = next;
this.isSentinel = false;
}
public void setContents(Node e) {
if (e != null) {
this.hash = e.hash;
this.key = e.key;
this.value = e.value;
this.next = e.next;
this.isSentinel = e.isSentinel;
} else {
this.isSentinel = true;
}
}
public boolean isSentinel() {
return isSentinel;
}
public void setSentinel(boolean isSentinel) {
this.isSentinel = isSentinel;
}
public final K getKey() { return key; }
public final V getValue() { return value; }
public final String toString() { return key + "=" + value; }
public final int hashCode() {
return Objects.hashCode(key) ^ Objects.hashCode(value);
}
public final V setValue(V newValue) {
V oldValue = value;
value = newValue;
return oldValue;
}
public final boolean equals(Object o) {
if (o == this)
return true;
if (o instanceof Map.Entry) {
Map.Entry e = (Map.Entry)o;
if (Objects.equals(key, e.getKey()) &&
Objects.equals(value, e.getValue()))
return true;
}
return false;
}
}
/* ---------------- Static utilities -------------- */
/**
* Computes key.hashCode() and spreads (XORs) higher bits of hash
* to lower. Because the table uses power-of-two masking, sets of
* hashes that vary only in bits above the current mask will
* always collide. (Among known examples are sets of Float keys
* holding consecutive whole numbers in small tables.) So we
* apply a transform that spreads the impact of higher bits
* downward. There is a tradeoff between speed, utility, and
* quality of bit-spreading. Because many common sets of hashes
* are already reasonably distributed (so don't benefit from
* spreading), and because we use trees to handle large sets of
* collisions in bins, we just XOR some shifted bits in the
* cheapest possible way to reduce systematic lossage, as well as
* to incorporate impact of the highest bits that would otherwise
* never be used in index calculations because of table bounds.
*/
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
/**
* Returns x's Class if it is of the form "class C implements
* Comparable", else null.
*/
static Class comparableClassFor(Object x) {
if (x instanceof Comparable) {
Class c; Type[] ts, as; Type t; ParameterizedType p;
if ((c = x.getClass()) == String.class) // bypass checks
return c;
if ((ts = c.getGenericInterfaces()) != null) {
for (int i = 0; i < ts.length; ++i) {
if (((t = ts[i]) instanceof ParameterizedType) &&
((p = (ParameterizedType)t).getRawType() ==
Comparable.class) &&
(as = p.getActualTypeArguments()) != null &&
as.length == 1 && as[0] == c) // type arg is c
return c;
}
}
}
return null;
}
/**
* Returns k.compareTo(x) if x matches kc (k's screened comparable
* class), else 0.
*/
@SuppressWarnings({"rawtypes","unchecked"}) // for cast to Comparable
static int compareComparables(Class kc, Object k, Object x) {
return (x == null || x.getClass() != kc ? 0 :
((Comparable)k).compareTo(x));
}
/**
* Returns a power of two size for the given target capacity.
*/
static final int tableSizeFor(int cap) {
int n = cap - 1;
n |= n >>> 1;
n |= n >>> 2;
n |= n >>> 4;
n |= n >>> 8;
n |= n >>> 16;
return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}
/* ---------------- Fields -------------- */
static class NodeTable extends StructuredArray> {
private static final MethodHandles.Lookup lookup = MethodHandles.lookup();
static final Constructor nodeConstructor;
static final CtorAndArgs nodeCtorAndArgs;
static final Constructor nodeTableConstructor;
static final CtorAndArgs nodeTableCtorAndArgs;
static {
try {
nodeConstructor = Node.class.getDeclaredConstructor();
nodeConstructor.setAccessible(true);
nodeCtorAndArgs = new CtorAndArgs(nodeConstructor);
nodeTableConstructor = NodeTable.class.getDeclaredConstructor();
nodeTableConstructor.setAccessible(true);
nodeTableCtorAndArgs = new CtorAndArgs(nodeTableConstructor);
} catch (NoSuchMethodException e) {
throw new RuntimeException(e);
}
}
@SuppressWarnings("unchecked")
public static NodeTable newInstance(final long length) {
return StructuredArray.newInstance(nodeTableCtorAndArgs, nodeCtorAndArgs, length);
// return StructuredArray.newInstance(lookup, NodeTable.class, Node.class, length);
}
}
/**
* The table, initialized on first use, and resized as
* necessary. When allocated, length is always a power of two.
* (We also tolerate length zero in some operations to allow
* bootstrapping mechanics that are currently not needed.)
*/
// transient Node[] table;
transient NodeTable saTable;
/**
* Holds cached entrySet(). Note that AbstractMap fields are used
* for keySet() and values().
*/
transient Set> entrySet;
/**
* The number of key-value mappings contained in this map.
*/
transient int size;
/**
* The number of times this HashMap has been structurally modified
* Structural modifications are those that change the number of mappings in
* the HashMap or otherwise modify its internal structure (e.g.,
* rehash). This field is used to make iterators on Collection-views of
* the HashMap fail-fast. (See ConcurrentModificationException).
*/
transient int modCount;
/**
* The next size value at which to resize (capacity * load factor).
*
* @serial
*/
// (The javadoc description is true upon serialization.
// Additionally, if the table array has not been allocated, this
// field holds the initial array capacity, or zero signifying
// DEFAULT_INITIAL_CAPACITY.)
int threshold;
/**
* The load factor for the hash table.
*
* @serial
*/
final float loadFactor;
/* ---------------- Public operations -------------- */
/**
* Constructs an empty HashMap with the specified initial
* capacity and load factor.
*
* @param initialCapacity the initial capacity
* @param loadFactor the load factor
* @throws IllegalArgumentException if the initial capacity is negative
* or the load factor is nonpositive
*/
public SAHashMap(int initialCapacity, float loadFactor) {
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal initial capacity: " +
initialCapacity);
if (initialCapacity > MAXIMUM_CAPACITY)
initialCapacity = MAXIMUM_CAPACITY;
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal load factor: " +
loadFactor);
this.loadFactor = loadFactor;
this.threshold = tableSizeFor(initialCapacity);
}
/**
* Constructs an empty HashMap with the specified initial
* capacity and the default load factor (0.75).
*
* @param initialCapacity the initial capacity.
* @throws IllegalArgumentException if the initial capacity is negative.
*/
public SAHashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
/**
* Constructs an empty HashMap with the default initial capacity
* (16) and the default load factor (0.75).
*/
public SAHashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}
/**
* Constructs a new HashMap with the same mappings as the
* specified Map. The HashMap is created with
* default load factor (0.75) and an initial capacity sufficient to
* hold the mappings in the specified Map.
*
* @param m the map whose mappings are to be placed in this map
* @throws NullPointerException if the specified map is null
*/
public SAHashMap(Map m) {
this.loadFactor = DEFAULT_LOAD_FACTOR;
putMapEntries(m, false);
}
/**
* Implements Map.putAll and Map constructor
*
* @param m the map
* @param evict false when initially constructing this map, else
* true (relayed to method afterNodeInsertion).
*/
final void putMapEntries(Map m, boolean evict) {
int s = m.size();
if (s > 0) {
if (saTable == null) { // pre-size
float ft = ((float)s / loadFactor) + 1.0F;
int t = ((ft < (float)MAXIMUM_CAPACITY) ?
(int)ft : MAXIMUM_CAPACITY);
if (t > threshold)
threshold = tableSizeFor(t);
}
else if (s > threshold)
resize();
for (Map.Entry e : m.entrySet()) {
K key = e.getKey();
V value = e.getValue();
putVal(hash(key), key, value, false, evict);
}
}
}
/**
* Returns the number of key-value mappings in this map.
*
* @return the number of key-value mappings in this map
*/
public int size() {
return size;
}
/**
* Returns true if this map contains no key-value mappings.
*
* @return true if this map contains no key-value mappings
*/
public boolean isEmpty() {
return size == 0;
}
/**
* Returns the value to which the specified key is mapped,
* or {@code null} if this map contains no mapping for the key.
*
* More formally, if this map contains a mapping from a key
* {@code k} to a value {@code v} such that {@code (key==null ? k==null :
* key.equals(k))}, then this method returns {@code v}; otherwise
* it returns {@code null}. (There can be at most one such mapping.)
*
*
A return value of {@code null} does not necessarily
* indicate that the map contains no mapping for the key; it's also
* possible that the map explicitly maps the key to {@code null}.
* The {@link #containsKey containsKey} operation may be used to
* distinguish these two cases.
*
* @see #put(Object, Object)
*/
public V get(Object key) {
Node e;
return (e = getNode(hash(key), key)) == null ? null : e.value;
}
/**
* Implements Map.get and related methods
*
* @param hash hash for key
* @param key the key
* @return the node, or null if none
*/
final Node getNode(int hash, Object key) {
NodeTable tab; Node first, e; int n; K k;
if ((tab = saTable) != null && (n = (int)tab.getLength()) > 0 &&
(first = tab.get((n - 1) & hash)).isSentinel() != true) {
if (first.hash == hash && // always check first node
((k = first.key) == key || (key != null && key.equals(k))))
return first;
if ((e = first.next) != null) {
// if (first instanceof TreeNode)
// return ((TreeNode)first).getTreeNode(hash, key);
do {
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
} while ((e = e.next) != null);
}
}
return null;
}
/**
* Returns true if this map contains a mapping for the
* specified key.
*
* @param key The key whose presence in this map is to be tested
* @return true if this map contains a mapping for the specified
* key.
*/
public boolean containsKey(Object key) {
return getNode(hash(key), key) != null;
}
/**
* Associates the specified value with the specified key in this map.
* If the map previously contained a mapping for the key, the old
* value is replaced.
*
* @param key key with which the specified value is to be associated
* @param value value to be associated with the specified key
* @return the previous value associated with key, or
* null if there was no mapping for key.
* (A null return can also indicate that the map
* previously associated null with key.)
*/
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
/**
* Implements Map.put and related methods
*
* @param hash hash for key
* @param key the key
* @param value the value to put
* @param onlyIfAbsent if true, don't change existing value
* @param evict if false, the table is in creation mode.
* @return previous value, or null if none
*/
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
NodeTable tab; Node p; int n, i;
if ((tab = saTable) == null || (n = (int)tab.getLength()) == 0)
n = (int)(tab = resize()).getLength();
if ((p = tab.get(i = (n - 1) & hash)).isSentinel() == true)
// tab[i] = newNode(hash, key, value, null);
tab.get(i).setContents(hash, key, value, null);
else {
Node e; K k;
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
// else if (p instanceof TreeNode)
// e = ((TreeNode)p).putTreeVal(this, tab, hash, key, value);
else {
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
// if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
// treeifyBin(tab, hash);
break;
}
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
/**
* Initializes or doubles table size. If null, allocates in
* accord with initial capacity target held in field threshold.
* Otherwise, because we are using power-of-two expansion, the
* elements from each bin must either stay at same index, or move
* with a power of two offset in the new table.
*
* @return the table
*/
final NodeTable resize() {
// Node[] oldTab = table;
NodeTable oldTab = saTable;
int oldCap = (oldTab == null) ? 0 : (int) oldTab.getLength();
int oldThr = threshold;
int newCap, newThr = 0;
if (oldCap > 0) {
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
}
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr << 1; // double threshold
}
else if (oldThr > 0) // initial capacity was placed in threshold
newCap = oldThr;
else { // zero initial threshold signifies using defaults
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
if (newThr == 0) {
float ft = (float)newCap * loadFactor;
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
}
threshold = newThr;
@SuppressWarnings({"rawtypes","unchecked"})
// Node[] newTab = (Node[])new Node[newCap];
NodeTable newTab = NodeTable.newInstance(newCap);
saTable = newTab;
if (oldTab != null) {
for (int j = 0; j < oldCap; ++j) {
Node e;
if ((e = oldTab.get(j)).isSentinel != true) {
// oldTab[j] = null;
// oldTab.get(j).setSentinel(true);
// if (e.next == null)
// newTab[e.hash & (newCap - 1)] = e;
if (e.next == null) {
newTab.get(e.hash & (newCap - 1)).setContents(e);
}
// else if (e instanceof TreeNode)
// ((TreeNode)e).split(this, newTab, j, oldCap);
else { // preserve order
Node loHead = null, loTail = null;
Node hiHead = null, hiTail = null;
Node next;
do {
next = e.next;
if ((e.hash & oldCap) == 0) {
if (loTail == null)
loHead = e;
else
loTail.next = e;
loTail = e;
}
else {
if (hiTail == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
}
} while ((e = next) != null);
if (loTail != null) {
loTail.next = null;
// newTab[j] = loHead;
newTab.get(j).setContents(loHead);
}
if (hiTail != null) {
hiTail.next = null;
// newTab[j + oldCap] = hiHead;
newTab.get(j + oldCap).setContents(hiHead);
}
}
}
}
}
return newTab;
}
/**
* Replaces all linked nodes in bin at index for given hash unless
* table is too small, in which case resizes instead.
*/
// final void treeifyBin(NodeTable tab, int hash) {
// int n, index; Node e;
// if (tab == null || (n = (int)tab.getLength()) < MIN_TREEIFY_CAPACITY)
// resize();
// else if ((e = tab.get(index = (n - 1) & hash)).isSentinel != true) {
// TreeNode hd = null, tl = null;
// do {
// TreeNode p = replacementTreeNode(e, null);
// if (tl == null)
// hd = p;
// else {
// p.prev = tl;
// tl.next = p;
// }
// tl = p;
// } while ((e = e.next) != null);
// if ((tab[index] = hd) != null)
// hd.treeify(tab);
// }
// }
/**
* Copies all of the mappings from the specified map to this map.
* These mappings will replace any mappings that this map had for
* any of the keys currently in the specified map.
*
* @param m mappings to be stored in this map
* @throws NullPointerException if the specified map is null
*/
public void putAll(Map m) {
putMapEntries(m, true);
}
/**
* Removes the mapping for the specified key from this map if present.
*
* @param key key whose mapping is to be removed from the map
* @return the previous value associated with key, or
* null if there was no mapping for key.
* (A null return can also indicate that the map
* previously associated null with key.)
*/
public V remove(Object key) {
Node e;
return (e = removeNode(hash(key), key, null, false, true)) == null ?
null : e.value;
}
/**
* Implements Map.remove and related methods
*
* @param hash hash for key
* @param key the key
* @param value the value to match if matchValue, else ignored
* @param matchValue if true only remove if value is equal
* @param movable if false do not move other nodes while removing
* @return the node, or null if none
*/
final Node removeNode(int hash, Object key, Object value,
boolean matchValue, boolean movable) {
NodeTable tab; Node p; int n, index;
if ((tab = saTable) != null && (n = (int)tab.getLength()) > 0 &&
(p = tab.get(index = (n - 1) & hash)).isSentinel != true) {
Node node = null, e; K k; V v;
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
node = p;
else if ((e = p.next) != null) {
// if (p instanceof TreeNode)
// node = ((TreeNode)p).getTreeNode(hash, key);
// else {
do {
if (e.hash == hash &&
((k = e.key) == key ||
(key != null && key.equals(k)))) {
node = e;
break;
}
p = e;
} while ((e = e.next) != null);
// }
}
if (node != null && (!matchValue || (v = node.value) == value ||
(value != null && value.equals(v)))) {
// if (node instanceof TreeNode)
// ((TreeNode)node).removeTreeNode(this, tab, movable);
// else if (node == p)
// tab[index] = node.next;
if (node == p) {
// We are removign the head of the list. We need to create an
// independent node with the same contents that will be returned.
// Also needs to be passed to afterNodeRemoval().
// Danger. Danger. (what if afterNodeRemoval was holding some links on a specific node)
// XXX GGG TODO
node = new Node(node.hash, node.key, node.value, node.next);
tab.get(index).setContents(node.next);
}
else
p.next = node.next;
++modCount;
--size;
afterNodeRemoval(node);
return node;
}
}
return null;
}
/**
* Removes all of the mappings from this map.
* The map will be empty after this call returns.
*/
public void clear() {
NodeTable tab;
modCount++;
if ((tab = saTable) != null && size > 0) {
size = 0;
for (int i = 0; i < tab.getLength(); ++i)
// tab[i] = null;
tab.get(i).setSentinel(true);
}
}
/**
* Returns true if this map maps one or more keys to the
* specified value.
*
* @param value value whose presence in this map is to be tested
* @return true if this map maps one or more keys to the
* specified value
*/
public boolean containsValue(Object value) {
NodeTable tab; V v;
if ((tab = saTable) != null && size > 0) {
for (int i = 0; i < tab.getLength(); ++i) {
for (Node e = tab.get(i); (e != null) && (!e.isSentinel()); e = e.next) {
if ((v = e.value) == value ||
(value != null && value.equals(v)))
return true;
}
}
}
return false;
}
/**
* Returns a {@link Set} view of the keys contained in this map.
* The set is backed by the map, so changes to the map are
* reflected in the set, and vice-versa. If the map is modified
* while an iteration over the set is in progress (except through
* the iterator's own remove operation), the results of
* the iteration are undefined. The set supports element removal,
* which removes the corresponding mapping from the map, via the
* Iterator.remove, Set.remove,
* removeAll, retainAll, and clear
* operations. It does not support the add or addAll
* operations.
*
* @return a set view of the keys contained in this map
*/
public Set keySet() {
Set ks;
return (ks = keySet) == null ? (keySet = new KeySet()) : ks;
}
final class KeySet extends AbstractSet {
public final int size() { return size; }
public final void clear() { SAHashMap.this.clear(); }
public final Iterator iterator() { return new KeyIterator(); }
public final boolean contains(Object o) { return containsKey(o); }
public final boolean remove(Object key) {
return removeNode(hash(key), key, null, false, true) != null;
}
public final Spliterator spliterator() {
return new KeySpliterator(SAHashMap.this, 0, -1, 0, 0);
}
public final void forEach(Consumer action) {
NodeTable tab;
if (action == null)
throw new NullPointerException();
if (size > 0 && (tab = saTable) != null) {
int mc = modCount;
for (int i = 0; i < tab.getLength(); ++i) {
for (Node e = tab.get(i); ((e != null) && !e.isSentinel()) ; e = e.next)
action.accept(e.key);
}
if (modCount != mc) // lgtm [java/constant-comparison]
throw new ConcurrentModificationException();
}
}
}
/**
* Returns a {@link Collection} view of the values contained in this map.
* The collection is backed by the map, so changes to the map are
* reflected in the collection, and vice-versa. If the map is
* modified while an iteration over the collection is in progress
* (except through the iterator's own remove operation),
* the results of the iteration are undefined. The collection
* supports element removal, which removes the corresponding
* mapping from the map, via the Iterator.remove,
* Collection.remove, removeAll,
* retainAll and clear operations. It does not
* support the add or addAll operations.
*
* @return a view of the values contained in this map
*/
public Collection values() {
Collection vs;
return (vs = values) == null ? (values = new Values()) : vs;
}
final class Values extends AbstractCollection {
public final int size() { return size; }
public final void clear() { SAHashMap.this.clear(); }
public final Iterator iterator() { return new ValueIterator(); }
public final boolean contains(Object o) { return containsValue(o); }
public final Spliterator spliterator() {
return new ValueSpliterator(SAHashMap.this, 0, -1, 0, 0);
}
public final void forEach(Consumer action) {
NodeTable tab;
if (action == null)
throw new NullPointerException();
if (size > 0 && (tab = saTable) != null) {
int mc = modCount;
for (int i = 0; i < tab.getLength(); ++i) {
for (Node e = tab.get(i); ((e != null) && !e.isSentinel()); e = e.next)
action.accept(e.value);
}
if (modCount != mc)
throw new ConcurrentModificationException();
}
}
}
/**
* Returns a {@link Set} view of the mappings contained in this map.
* The set is backed by the map, so changes to the map are
* reflected in the set, and vice-versa. If the map is modified
* while an iteration over the set is in progress (except through
* the iterator's own remove operation, or through the
* setValue operation on a map entry returned by the
* iterator) the results of the iteration are undefined. The set
* supports element removal, which removes the corresponding
* mapping from the map, via the Iterator.remove,
* Set.remove, removeAll, retainAll and
* clear operations. It does not support the
* add or addAll operations.
*
* @return a set view of the mappings contained in this map
*/
public Set> entrySet() {
Set> es;
return (es = entrySet) == null ? (entrySet = new EntrySet()) : es;
}
final class EntrySet extends AbstractSet> {
public final int size() { return size; }
public final void clear() { SAHashMap.this.clear(); }
public final Iterator> iterator() {
return new EntryIterator();
}
public final boolean contains(Object o) {
if (!(o instanceof Map.Entry))
return false;
Map.Entry e = (Map.Entry) o;
Object key = e.getKey();
Node candidate = getNode(hash(key), key);
return candidate != null && candidate.equals(e);
}
public final boolean remove(Object o) {
if (o instanceof Map.Entry) {
Map.Entry e = (Map.Entry) o;
Object key = e.getKey();
Object value = e.getValue();
return removeNode(hash(key), key, value, true, true) != null;
}
return false;
}
public final Spliterator> spliterator() {
return new EntrySpliterator(SAHashMap.this, 0, -1, 0, 0);
}
public final void forEach(Consumer> action) {
NodeTable tab;
if (action == null)
throw new NullPointerException();
if (size > 0 && (tab = saTable) != null) {
int mc = modCount;
for (int i = 0; i < tab.getLength(); ++i) {
for (Node e = tab.get(i); ((e != null) && !e.isSentinel()); e = e.next)
action.accept(e);
}
if (modCount != mc) // lgtm [java/constant-comparison]
throw new ConcurrentModificationException();
}
}
}
// Overrides of JDK8 Map extension methods
@Override
public V getOrDefault(Object key, V defaultValue) {
Node e;
return (e = getNode(hash(key), key)) == null ? defaultValue : e.value;
}
@Override
public V putIfAbsent(K key, V value) {
return putVal(hash(key), key, value, true, true);
}
@Override
public boolean remove(Object key, Object value) {
return removeNode(hash(key), key, value, true, true) != null;
}
@Override
public boolean replace(K key, V oldValue, V newValue) {
Node e; V v;
if ((e = getNode(hash(key), key)) != null &&
((v = e.value) == oldValue || (v != null && v.equals(oldValue)))) {
e.value = newValue;
afterNodeAccess(e);
return true;
}
return false;
}
@Override
public V replace(K key, V value) {
Node e;
if ((e = getNode(hash(key), key)) != null) {
V oldValue = e.value;
e.value = value;
afterNodeAccess(e);
return oldValue;
}
return null;
}
@Override
public V computeIfAbsent(K key,
Function mappingFunction) {
if (mappingFunction == null)
throw new NullPointerException();
int hash = hash(key);
NodeTable tab; Node first; int n, i;
int binCount = 0;
// TreeNode t = null;
Node old = null;
if (size > threshold || (tab = saTable) == null ||
(n = (int)tab.getLength()) == 0)
n = (int)(tab = resize()).getLength();
if ((first = tab.get(i = (n - 1) & hash)).isSentinel() != true) {
// if (first instanceof TreeNode)
// old = (t = (TreeNode)first).getTreeNode(hash, key);
// else {
Node e = first; K k;
do {
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k)))) {
old = e;
break;
}
++binCount;
} while ((e = e.next) != null);
// }
V oldValue;
if (old != null && (oldValue = old.value) != null) {
afterNodeAccess(old);
return oldValue;
}
}
V v = mappingFunction.apply(key);
if (v == null) {
return null;
} else if (old != null) {
old.value = v;
afterNodeAccess(old);
return v;
}
// else if (t != null)
// t.putTreeVal(this, tab, hash, key, v);
// else {
// tab[i] = newNode(hash, key, v, first);
// if (binCount >= TREEIFY_THRESHOLD - 1)
// treeifyBin(tab, hash);
// }
tab.get(i).setContents(hash, key, v, first);
++modCount;
++size;
afterNodeInsertion(true);
return v;
}
public V computeIfPresent(K key,
BiFunction remappingFunction) {
if (remappingFunction == null)
throw new NullPointerException();
Node e; V oldValue;
int hash = hash(key);
if ((e = getNode(hash, key)) != null &&
(oldValue = e.value) != null) {
V v = remappingFunction.apply(key, oldValue);
if (v != null) {
e.value = v;
afterNodeAccess(e);
return v;
}
else
removeNode(hash, key, null, false, true);
}
return null;
}
@Override
public V compute(K key,
BiFunction remappingFunction) {
if (remappingFunction == null)
throw new NullPointerException();
int hash = hash(key);
NodeTable tab; Node first; int n, i;
int binCount = 0;
// TreeNode t = null;
Node old = null;
if (size > threshold || (tab = saTable) == null ||
(n = (int)tab.getLength()) == 0)
n = (int)(tab = resize()).getLength();
if ((first = tab.get(i = (n - 1) & hash)).isSentinel() != true) {
// if (first instanceof TreeNode)
// old = (t = (TreeNode)first).getTreeNode(hash, key);
// else {
Node e = first; K k;
do {
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k)))) {
old = e;
break;
}
++binCount;
} while ((e = e.next) != null);
// }
}
V oldValue = (old == null) ? null : old.value;
V v = remappingFunction.apply(key, oldValue);
if (old != null) {
if (v != null) {
old.value = v;
afterNodeAccess(old);
}
else
removeNode(hash, key, null, false, true);
}
else if (v != null) {
// if (t != null)
// t.putTreeVal(this, tab, hash, key, v);
// else {
// tab[i] = newNode(hash, key, v, first);
// if (binCount >= TREEIFY_THRESHOLD - 1)
// treeifyBin(tab, hash);
// }
tab.get(i).setContents(hash, key, v, first);
++modCount;
++size;
afterNodeInsertion(true);
}
return v;
}
@Override
public V merge(K key, V value,
BiFunction remappingFunction) {
if (value == null)
throw new NullPointerException();
if (remappingFunction == null)
throw new NullPointerException();
int hash = hash(key);
NodeTable tab; Node first; int n, i;
int binCount = 0;
// TreeNode t = null;
Node old = null;
if (size > threshold || (tab = saTable) == null ||
(n = (int)tab.getLength()) == 0)
n = (int)(tab = resize()).getLength();
if ((first = tab.get(i = (n - 1) & hash)).isSentinel() != true) {
// if (first instanceof TreeNode)
// old = (t = (TreeNode)first).getTreeNode(hash, key);
// else {
Node e = first; K k;
do {
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k)))) {
old = e;
break;
}
++binCount;
} while ((e = e.next) != null);
// }
}
if (old != null) {
V v;
if (old.value != null)
v = remappingFunction.apply(old.value, value);
else
v = value;
if (v != null) {
old.value = v;
afterNodeAccess(old);
}
else
removeNode(hash, key, null, false, true);
return v;
}
// if (value != null) {
// if (t != null)
// t.putTreeVal(this, tab, hash, key, value);
// else {
// tab[i] = newNode(hash, key, value, first);
// if (binCount >= TREEIFY_THRESHOLD - 1)
// treeifyBin(tab, hash);
// }
tab.get(i).setContents(hash, key, value, first);
++modCount;
++size;
afterNodeInsertion(true);
// }
return value;
}
@Override
public void forEach(BiConsumer action) {
NodeTable tab;
if (action == null)
throw new NullPointerException();
if (size > 0 && (tab = saTable) != null) {
int mc = modCount;
for (int i = 0; i < tab.getLength(); ++i) {
for (Node