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