src/jdk.scripting.nashorn/share/classes/jdk/nashorn/internal/objects/LinkedMap.java - platform/libcore - Git at Google

 /*
  * 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;

 /**
  * <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.
      */
     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.
          */
         private Node() {
             this(null, null);
             this.next = this;
             this.prev = this;
         }

         /**
          * 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.
          * @return the hash key
          */
         public Object getKey() {
             return key;
         }

         /**
          * Get the node's value.
          * @return the value
          */
         public Object getValue() {
             return 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.
      */
     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.
          *
          * @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.
      * @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 {@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 {@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 {@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.
      */
     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.
      * @return the map size
      */
     public int size() {
         return data.size();
     }

     /**
      * 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;
     }

 }
	/*
	* 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;

	/**
	* <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.
	*/
	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.
	*/
	private Node() {
	this(null, null);
	this.next = this;
	this.prev = this;
	}

	/**
	* 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.
	* @return the hash key
	*/
	public Object getKey() {
	return key;
	}

	/**
	* Get the node's value.
	* @return the value
	*/
	public Object getValue() {
	return 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.
	*/
	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.
	*
	* @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.
	* @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 {@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 {@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 {@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.
	*/
	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.
	* @return the map size
	*/
	public int size() {
	return data.size();
	}

	/**
	* 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;
	}

	}