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 */
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 }
|
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 */
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 }
|