1 /*
   2  * Copyright (c) 2016, Oracle and/or its affiliates. All rights reserved.
   3  * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
   4  *
   5  * This code is free software; you can redistribute it and/or modify it
   6  * under the terms of the GNU General Public License version 2 only, as
   7  * published by the Free Software Foundation.  Oracle designates this
   8  * particular file as subject to the "Classpath" exception as provided
   9  * by Oracle in the LICENSE file that accompanied this code.
  10  *
  11  * This code is distributed in the hope that it will be useful, but WITHOUT
  12  * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
  13  * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  14  * version 2 for more details (a copy is included in the LICENSE file that
  15  * accompanied this code).
  16  *
  17  * You should have received a copy of the GNU General Public License version
  18  * 2 along with this work; if not, write to the Free Software Foundation,
  19  * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
  20  *
  21  * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
  22  * or visit www.oracle.com if you need additional information or have any
  23  * questions.
  24  */
  25 
  26 package jdk.nashorn.internal.objects;
  27 
  28 import jdk.nashorn.internal.runtime.Undefined;
  29 
  30 import java.util.Collections;
  31 import java.util.HashMap;
  32 import java.util.Map;
  33 
  34 /**
  35  * <p>A linked hash map used by the ES6 Map and Set objects. As required by the ECMA specification for these objects,
  36  * this class allows arbitrary modifications to the base collection while being iterated over. However, note that
  37  * such modifications are only safe from the same thread performing the iteration; the class is not thread-safe.</p>
  38  *
  39  * <p>Deletions and additions that occur during iteration are reflected in the elements visited by the iterator
  40  * (except for deletion of elements that have already been visited). In non-concurrent Java collections such as
  41  * {@code java.util.LinkedHashMap} this would result in a {@link java.util.ConcurrentModificationException}
  42  * being thrown.</p>
  43  *
  44  * <p>This class is implemented using a {@link java.util.HashMap} as backing storage with doubly-linked
  45  * list nodes as values.</p>
  46  *
  47  * @see <a href="http://www.ecma-international.org/ecma-262/6.0/#sec-map.prototype.foreach">Map.prototype.forEach</a>
  48  * @see <a href="http://www.ecma-international.org/ecma-262/6.0/#sec-set.prototype.foreach">Set.prototype.forEach</a>
  49  */
  50 public class LinkedMap {
  51 
  52     // We use a plain hash map as our hash storage.
  53     private final Map<Object, Node> data = new HashMap<>();
  54 
  55     // The head and tail of our doubly-linked list. We use the same node to represent both the head and the
  56     // tail of the list, so the list is circular. This node is never unlinked and thus always remain alive.
  57     private final Node head = new Node();
  58 
  59     /**
  60      * A node of a linked list that is used as value in our map. The linked list uses insertion order
  61      * and allows fast iteration over its element even while the map is modified.
  62      */
  63     static class Node {
  64         private final Object key;
  65         private volatile Object value;
  66 
  67         private volatile boolean alive = true;
  68         private volatile Node prev;
  69         private volatile Node next;
  70 
  71         /**
  72          * Constructor for the list head. This creates an empty circular list.
  73          */
  74         private Node() {
  75             this(null, null);
  76             this.next = this;
  77             this.prev = this;
  78         }
  79 
  80         /**
  81          * Constructor for value nodes.
  82          *
  83          * @param key the key
  84          * @param value the value
  85          */
  86         private Node(final Object key, final Object value) {
  87             this.key = key;
  88             this.value = value;
  89         }
  90 
  91         /**
  92          * Get the node's key.
  93          * @return the hash key
  94          */
  95         public Object getKey() {
  96             return key;
  97         }
  98 
  99         /**
 100          * Get the node's value.
 101          * @return the value
 102          */
 103         public Object getValue() {
 104             return value;
 105         }
 106 
 107         /**
 108          * Set the node's value
 109          * @param value the new value
 110          */
 111         void setValue(final Object value) {
 112             this.value = value;
 113         }
 114     }
 115 
 116     /**
 117      * An iterator over the elements in the map.
 118      */
 119     class LinkedMapIterator {
 120 
 121         private Node cursor;
 122 
 123         private LinkedMapIterator() {
 124             this.cursor = head;
 125         }
 126 
 127         /**
 128          * Get the next node in this iteration. Changes in the underlying map are reflected in the iteration
 129          * as required by the ES6 specification. Note that this method could return a deleted node if deletion
 130          * occurred concurrently on another thread.
 131          *
 132          * @return the next node
 133          */
 134         public Node next() {
 135 
 136             if (cursor != null) {
 137                 // If last node is not alive anymore (i.e. has been deleted) go back to the last live node
 138                 // and continue from there. This may be the list head, which always remains alive.
 139                 while (!cursor.alive) {
 140                     assert cursor != head;
 141                     cursor = cursor.prev;
 142                 }
 143 
 144                 cursor = cursor.next;
 145 
 146                 if (cursor == head) {
 147                     cursor = null; // We've come full circle to the end
 148                 }
 149             }
 150 
 151             return cursor;
 152         }
 153     }
 154 
 155     /**
 156      * Add a key-value pair to the map.
 157      * @param key the key
 158      * @param value the value
 159      */
 160     public void set(final Object key, final Object value) {
 161         Node node = data.get(key);
 162         if (node != null) {
 163             node.setValue(value);
 164         } else {
 165             node = new Node(key, value);
 166             data.put(key, node);
 167             link(node);
 168         }
 169     }
 170 
 171     /**
 172      * Get the value associated with {@code key}.
 173      * @param key the key
 174      * @return the associated value, or {@code null} if {@code key} is not contained in the map
 175      */
 176     public Object get(final Object key) {
 177         final Node node = data.get(key);
 178         return node == null ? Undefined.getUndefined() : node.getValue();
 179     }
 180 
 181     /**
 182      * Returns {@code true} if {@code key} is contained in the map.
 183      * @param key the key
 184      * @return {@code true} if {@code key} is contained
 185      */
 186     public boolean has(final Object key) {
 187         return data.containsKey(key);
 188     }
 189 
 190     /**
 191      * Delete the node associated with {@code key} from the map.
 192      * @param key the key
 193      * @return {@code true} if {@code key} was contained in the map
 194      */
 195     public boolean delete (final Object key) {
 196         final Node node = data.remove(key);
 197         if (node != null) {
 198             unlink(node);
 199             return true;
 200         }
 201         return false;
 202     }
 203 
 204     /**
 205      * Remove all key-value pairs from the map.
 206      */
 207     public void clear() {
 208         data.clear();
 209         for (Node node = head.next; node != head; node = node.next) {
 210             node.alive = false;
 211         }
 212         head.next = head;
 213         head.prev = head;
 214     }
 215 
 216     /**
 217      * Return the current number of key-value pairs in the map.
 218      * @return the map size
 219      */
 220     public int size() {
 221         return data.size();
 222     }
 223 
 224     /**
 225      * Get an iterator over the key-value pairs in the map.
 226      * @return an iterator
 227      */
 228     public LinkedMapIterator getIterator() {
 229         return new LinkedMapIterator();
 230     }
 231 
 232     private void link(final Node newNode) {
 233         // We always insert at the end (head == tail)
 234         newNode.next = head;
 235         newNode.prev = head.prev;
 236         newNode.prev.next = newNode;
 237         head.prev = newNode;
 238     }
 239 
 240     private void unlink(final Node oldNode) {
 241         // Note that we unlink references to the node being deleted, but keep the references from the deleted node.
 242         // This is necessary to allow iterators to go back to the last live node in case the current node has been
 243         // deleted. Also, the forward link of a deleted node may still be followed by an iterator and must not be null.
 244         oldNode.prev.next = oldNode.next;
 245         oldNode.next.prev = oldNode.prev;
 246         oldNode.alive = false;
 247     }
 248 
 249 }