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 final 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     /**
 109      * An iterator over the elements in the map.
 110      */
 111     class LinkedMapIterator {
 112 
 113         private Node cursor;
 114 
 115         private LinkedMapIterator() {
 116             this.cursor = head;
 117         }
 118 
 119         /**
 120          * Get the next node in this iteration. Changes in the underlying map are reflected in the iteration
 121          * as required by the ES6 specification. Note that this method could return a deleted node if deletion
 122          * occurred concurrently on another thread.
 123          *
 124          * @return the next node
 125          */
 126         public Node next() {
 127 
 128             if (cursor != null) {
 129                 // If last node is not alive anymore (i.e. has been deleted) go back to the last live node
 130                 // and continue from there. This may be the list head, which always remains alive.
 131                 while (!cursor.alive) {
 132                     assert cursor != head;
 133                     cursor = cursor.prev;
 134                 }
 135 
 136                 cursor = cursor.next;
 137 
 138                 if (cursor == head) {
 139                     cursor = null; // We've come full circle to the end
 140                 }
 141             }
 142 
 143             return cursor;
 144         }
 145     }
 146 
 147     /**
 148      * Add a key-value pair to the map.
 149      * @param key the key
 150      * @param value the value
 151      */
 152     public void set(final Object key, final Object value) {
 153         final Node newNode = new Node(key, value);
 154         final Node oldNode = data.put(key, newNode);
 155         if (oldNode != null) {
 156             unlink(oldNode);
 157         }
 158         link(newNode);
 159     }
 160 
 161     /**
 162      * Get the value associated with {@code key}.
 163      * @param key the key
 164      * @return the associated value, or {@code null} if {@code key} is not contained in the map
 165      */
 166     public Object get(final Object key) {
 167         final Node node = data.get(key);
 168         return node == null ? Undefined.getUndefined() : node.getValue();
 169     }
 170 
 171     /**
 172      * Returns {@code true} if {@code key} is contained in the map.
 173      * @param key the key
 174      * @return {@code true} if {@code key} is contained
 175      */
 176     public boolean has(final Object key) {
 177         return data.containsKey(key);
 178     }
 179 
 180     /**
 181      * Delete the node associated with {@code key} from the map.
 182      * @param key the key
 183      * @return {@code true} if {@code key} was contained in the map
 184      */
 185     public boolean delete (final Object key) {
 186         final Node node = data.remove(key);
 187         if (node != null) {
 188             unlink(node);
 189             return true;
 190         }
 191         return false;
 192     }
 193 
 194     /**
 195      * Remove all key-value pairs from the map.
 196      */
 197     public void clear() {
 198         data.clear();
 199         for (Node node = head.next; node != head; node = node.next) {
 200             node.alive = false;
 201         }
 202         head.next = head;
 203         head.prev = head;
 204     }
 205 
 206     /**
 207      * Return the current number of key-value pairs in the map.
 208      * @return the map size
 209      */
 210     public int size() {
 211         return data.size();
 212     }
 213 
 214     /**
 215      * Get an iterator over the key-value pairs in the map.
 216      * @return an iterator
 217      */
 218     public LinkedMapIterator getIterator() {
 219         return new LinkedMapIterator();
 220     }
 221 
 222     private void link(final Node newNode) {
 223         // We always insert at the end (head == tail)
 224         newNode.next = head;
 225         newNode.prev = head.prev;
 226         newNode.prev.next = newNode;
 227         head.prev = newNode;
 228     }
 229 
 230     private void unlink(final Node oldNode) {
 231         // Note that we unlink references to the node being deleted, but keep the references from the deleted node.
 232         // This is necessary to allow iterators to go back to the last live node in case the current node has been
 233         // deleted. Also, the forward link of a deleted node may still be followed by an iterator and must not be null.
 234         oldNode.prev.next = oldNode.next;
 235         oldNode.next.prev = oldNode.prev;
 236         oldNode.alive = false;
 237     }
 238 
 239 }