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 }