/*
* Copyright (c) 2016, 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.
*/
package jdk.nashorn.internal.objects;
import jdk.nashorn.internal.runtime.Undefined;
import java.util.Collections;
import java.util.HashMap;
import java.util.Map;
A linked hash map used by the ES6 Map and Set objects. As required by the ECMA specification for these objects,
this class allows arbitrary modifications to the base collection while being iterated over. However, note that
such modifications are only safe from the same thread performing the iteration; the class is not thread-safe.
Deletions and additions that occur during iteration are reflected in the elements visited by the iterator (except for deletion of elements that have already been visited). In non-concurrent Java collections such as java.util.LinkedHashMap this would result in a ConcurrentModificationException being thrown.
This class is implemented using a HashMap as backing storage with doubly-linked list nodes as values.
See Also:
/**
* <p>A linked hash map used by the ES6 Map and Set objects. As required by the ECMA specification for these objects,
* this class allows arbitrary modifications to the base collection while being iterated over. However, note that
* such modifications are only safe from the same thread performing the iteration; the class is not thread-safe.</p>
*
* <p>Deletions and additions that occur during iteration are reflected in the elements visited by the iterator
* (except for deletion of elements that have already been visited). In non-concurrent Java collections such as
* {@code java.util.LinkedHashMap} this would result in a {@link java.util.ConcurrentModificationException}
* being thrown.</p>
*
* <p>This class is implemented using a {@link java.util.HashMap} as backing storage with doubly-linked
* list nodes as values.</p>
*
* @see <a href="http://www.ecma-international.org/ecma-262/6.0/#sec-map.prototype.foreach">Map.prototype.forEach</a>
* @see <a href="http://www.ecma-international.org/ecma-262/6.0/#sec-set.prototype.foreach">Set.prototype.forEach</a>
*/
public class LinkedMap {
// We use a plain hash map as our hash storage.
private final Map<Object, Node> data = new HashMap<>();
// The head and tail of our doubly-linked list. We use the same node to represent both the head and the
// tail of the list, so the list is circular. This node is never unlinked and thus always remain alive.
private final Node head = new Node();
A node of a linked list that is used as value in our map. The linked list uses insertion order
and allows fast iteration over its element even while the map is modified.
/**
* A node of a linked list that is used as value in our map. The linked list uses insertion order
* and allows fast iteration over its element even while the map is modified.
*/
static class Node {
private final Object key;
private volatile Object value;
private volatile boolean alive = true;
private volatile Node prev;
private volatile Node next;
Constructor for the list head. This creates an empty circular list.
/**
* Constructor for the list head. This creates an empty circular list.
*/
private Node() {
this(null, null);
this.next = this;
this.prev = this;
}
Constructor for value nodes.
Params: - key – the key
- value – the value
/**
* Constructor for value nodes.
*
* @param key the key
* @param value the value
*/
private Node(final Object key, final Object value) {
this.key = key;
this.value = value;
}
Get the node's key.
Returns: the hash key
/**
* Get the node's key.
* @return the hash key
*/
public Object getKey() {
return key;
}
Get the node's value.
Returns: the value
/**
* Get the node's value.
* @return the value
*/
public Object getValue() {
return value;
}
Set the node's value
Params: - value – the new value
/**
* Set the node's value
* @param value the new value
*/
void setValue(final Object value) {
this.value = value;
}
}
An iterator over the elements in the map.
/**
* An iterator over the elements in the map.
*/
class LinkedMapIterator {
private Node cursor;
private LinkedMapIterator() {
this.cursor = head;
}
Get the next node in this iteration. Changes in the underlying map are reflected in the iteration
as required by the ES6 specification. Note that this method could return a deleted node if deletion
occurred concurrently on another thread.
Returns: the next node
/**
* Get the next node in this iteration. Changes in the underlying map are reflected in the iteration
* as required by the ES6 specification. Note that this method could return a deleted node if deletion
* occurred concurrently on another thread.
*
* @return the next node
*/
public Node next() {
if (cursor != null) {
// If last node is not alive anymore (i.e. has been deleted) go back to the last live node
// and continue from there. This may be the list head, which always remains alive.
while (!cursor.alive) {
assert cursor != head;
cursor = cursor.prev;
}
cursor = cursor.next;
if (cursor == head) {
cursor = null; // We've come full circle to the end
}
}
return cursor;
}
}
Add a key-value pair to the map.
Params: - key – the key
- value – the value
/**
* Add a key-value pair to the map.
* @param key the key
* @param value the value
*/
public void set(final Object key, final Object value) {
Node node = data.get(key);
if (node != null) {
node.setValue(value);
} else {
node = new Node(key, value);
data.put(key, node);
link(node);
}
}
Get the value associated with key. Params: - key – the key
Returns: the associated value, or null if key is not contained in the map
/**
* Get the value associated with {@code key}.
* @param key the key
* @return the associated value, or {@code null} if {@code key} is not contained in the map
*/
public Object get(final Object key) {
final Node node = data.get(key);
return node == null ? Undefined.getUndefined() : node.getValue();
}
Returns true if key is contained in the map. Params: - key – the key
Returns: true if key is contained
/**
* Returns {@code true} if {@code key} is contained in the map.
* @param key the key
* @return {@code true} if {@code key} is contained
*/
public boolean has(final Object key) {
return data.containsKey(key);
}
Delete the node associated with key from the map. Params: - key – the key
Returns: true if key was contained in the map
/**
* Delete the node associated with {@code key} from the map.
* @param key the key
* @return {@code true} if {@code key} was contained in the map
*/
public boolean delete (final Object key) {
final Node node = data.remove(key);
if (node != null) {
unlink(node);
return true;
}
return false;
}
Remove all key-value pairs from the map.
/**
* Remove all key-value pairs from the map.
*/
public void clear() {
data.clear();
for (Node node = head.next; node != head; node = node.next) {
node.alive = false;
}
head.next = head;
head.prev = head;
}
Return the current number of key-value pairs in the map.
Returns: the map size
/**
* Return the current number of key-value pairs in the map.
* @return the map size
*/
public int size() {
return data.size();
}
Get an iterator over the key-value pairs in the map.
Returns: an iterator
/**
* Get an iterator over the key-value pairs in the map.
* @return an iterator
*/
public LinkedMapIterator getIterator() {
return new LinkedMapIterator();
}
private void link(final Node newNode) {
// We always insert at the end (head == tail)
newNode.next = head;
newNode.prev = head.prev;
newNode.prev.next = newNode;
head.prev = newNode;
}
private void unlink(final Node oldNode) {
// Note that we unlink references to the node being deleted, but keep the references from the deleted node.
// This is necessary to allow iterators to go back to the last live node in case the current node has been
// deleted. Also, the forward link of a deleted node may still be followed by an iterator and must not be null.
oldNode.prev.next = oldNode.next;
oldNode.next.prev = oldNode.prev;
oldNode.alive = false;
}
}