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 26package jdk.nashorn.internal.objects; 27 28import jdk.nashorn.internal.runtime.Undefined; 29 30import java.util.Collections; 31import java.util.HashMap; 32import 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 */ 50public 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} 250