1 /*
2 * Copyright (c) 2011, 2018, 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.
8 *
9 * This code is distributed in the hope that it will be useful, but WITHOUT
10 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
11 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
12 * version 2 for more details (a copy is included in the LICENSE file that
13 * accompanied this code).
14 *
15 * You should have received a copy of the GNU General Public License version
16 * 2 along with this work; if not, write to the Free Software Foundation,
17 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
18 *
19 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
20 * or visit www.oracle.com if you need additional information or have any
21 * questions.
22 */
23
24
25 package org.graalvm.compiler.graph;
26
27 import java.util.AbstractList;
28 import java.util.Arrays;
29 import java.util.Collection;
30 import java.util.Iterator;
31 import java.util.List;
32 import java.util.RandomAccess;
33
34 import org.graalvm.compiler.graph.iterators.NodeIterable;
35
36 public abstract class NodeList<T extends Node> extends AbstractList<T> implements NodeIterable<T>, RandomAccess {
37
38 protected static final Node[] EMPTY_NODE_ARRAY = new Node[0];
39
40 protected final Node self;
41 protected Node[] nodes;
42 private int size;
43 protected final int initialSize;
44
45 protected NodeList(Node self) {
46 this.self = self;
47 this.nodes = EMPTY_NODE_ARRAY;
48 this.initialSize = 0;
49 }
50
51 protected NodeList(Node self, int initialSize) {
52 this.self = self;
53 this.size = initialSize;
54 this.initialSize = initialSize;
55 this.nodes = new Node[initialSize];
56 }
57
58 protected NodeList(Node self, T[] elements) {
59 this.self = self;
60 if (elements == null || elements.length == 0) {
61 this.size = 0;
62 this.nodes = EMPTY_NODE_ARRAY;
63 this.initialSize = 0;
64 } else {
65 this.size = elements.length;
66 this.initialSize = elements.length;
67 this.nodes = new Node[elements.length];
68 for (int i = 0; i < elements.length; i++) {
69 this.nodes[i] = elements[i];
70 assert this.nodes[i] == null || !this.nodes[i].isDeleted() : "Initializing nodelist with deleted element : " + nodes[i];
71 }
72 }
73 }
74
75 protected NodeList(Node self, List<? extends T> elements) {
76 this.self = self;
77 if (elements == null || elements.isEmpty()) {
78 this.size = 0;
79 this.nodes = EMPTY_NODE_ARRAY;
80 this.initialSize = 0;
81 } else {
82 this.size = elements.size();
83 this.initialSize = elements.size();
84 this.nodes = new Node[elements.size()];
85 for (int i = 0; i < elements.size(); i++) {
86 this.nodes[i] = elements.get(i);
87 assert this.nodes[i] == null || !this.nodes[i].isDeleted();
88 }
89 }
90 }
91
92 protected NodeList(Node self, Collection<? extends NodeInterface> elements) {
93 this.self = self;
94 if (elements == null || elements.isEmpty()) {
95 this.size = 0;
96 this.nodes = EMPTY_NODE_ARRAY;
97 this.initialSize = 0;
98 } else {
99 this.size = elements.size();
100 this.initialSize = elements.size();
101 this.nodes = new Node[elements.size()];
102 int i = 0;
103 for (NodeInterface n : elements) {
104 this.nodes[i] = n.asNode();
105 assert this.nodes[i] == null || !this.nodes[i].isDeleted();
106 i++;
107 }
108 }
109 }
110
111 public boolean isList() {
112 return true;
113 }
114
115 protected abstract void update(T oldNode, T newNode);
116
117 public abstract Edges.Type getEdgesType();
118
119 @Override
120 public final int size() {
121 return size;
122 }
123
124 @Override
125 public final boolean isEmpty() {
126 return size == 0;
127 }
128
129 @Override
130 public boolean isNotEmpty() {
131 return size > 0;
132 }
133
134 @Override
135 public int count() {
136 return size;
137 }
138
139 protected final void incModCount() {
140 modCount++;
141 }
142
143 @SuppressWarnings("unchecked")
144 @Override
145 public boolean add(Node node) {
146 assert node == null || !node.isDeleted();
147 self.incModCount();
148 incModCount();
149 int length = nodes.length;
150 if (length == 0) {
151 nodes = new Node[2];
152 } else if (size == length) {
153 Node[] newNodes = new Node[nodes.length * 2 + 1];
154 System.arraycopy(nodes, 0, newNodes, 0, length);
155 nodes = newNodes;
156 }
157 nodes[size++] = node;
158 update(null, (T) node);
159 return true;
160 }
161
162 @Override
163 @SuppressWarnings("unchecked")
164 public T get(int index) {
165 assert assertInRange(index);
166 return (T) nodes[index];
167 }
168
169 private boolean assertInRange(int index) {
170 assert index >= 0 && index < size() : index + " < " + size();
171 return true;
172 }
173
174 public T last() {
175 return get(size() - 1);
176 }
177
178 @Override
179 @SuppressWarnings("unchecked")
180 public T set(int index, Node node) {
181 incModCount();
182 T oldValue = (T) nodes[index];
183 assert assertInRange(index);
184 update((T) nodes[index], (T) node);
185 nodes[index] = node;
186 return oldValue;
187 }
188
189 public void initialize(int index, Node node) {
190 incModCount();
191 assert index < size();
192 nodes[index] = node;
193 }
194
195 void copy(NodeList<? extends Node> other) {
196 self.incModCount();
197 incModCount();
198 Node[] newNodes = new Node[other.size];
199 System.arraycopy(other.nodes, 0, newNodes, 0, newNodes.length);
200 nodes = newNodes;
201 size = other.size;
202 }
203
204 @Override
205 public boolean equals(Object other) {
206 if (other == this) {
207 return true;
208 }
209 if (other instanceof List<?>) {
210 List<?> otherList = (List<?>) other;
211 if (size != otherList.size()) {
212 return false;
213 }
214 for (int i = 0; i < size; i++) {
215 if (nodes[i] != otherList.get(i)) {
216 return false;
217 }
218 }
219 return true;
220 }
221 return false;
222 }
223
224 @SuppressWarnings("unchecked")
225 @Override
226 public void clear() {
227 self.incModCount();
228 incModCount();
229 for (int i = 0; i < size; i++) {
230 update((T) nodes[i], null);
231 }
232 clearWithoutUpdate();
233 }
234
235 void clearWithoutUpdate() {
236 nodes = EMPTY_NODE_ARRAY;
237 size = 0;
238 }
239
240 @Override
241 @SuppressWarnings("unchecked")
242 public boolean remove(Object node) {
243 self.incModCount();
244 int i = 0;
245 incModCount();
246 while (i < size && nodes[i] != node) {
247 i++;
248 }
249 if (i < size) {
250 T oldValue = (T) nodes[i];
251 i++;
252 while (i < size) {
253 nodes[i - 1] = nodes[i];
254 i++;
255 }
256 nodes[--size] = null;
257 update(oldValue, null);
258 return true;
259 } else {
260 return false;
261 }
262 }
263
264 @Override
265 @SuppressWarnings("unchecked")
266 public T remove(int index) {
267 self.incModCount();
268 T oldValue = (T) nodes[index];
269 int i = index + 1;
270 incModCount();
271 while (i < size) {
272 nodes[i - 1] = nodes[i];
273 i++;
274 }
275 nodes[--size] = null;
276 update(oldValue, null);
277 return oldValue;
278 }
279
280 boolean replaceFirst(Node node, Node other) {
281 for (int i = 0; i < size; i++) {
282 if (nodes[i] == node) {
283 nodes[i] = other;
284 return true;
285 }
286 }
287 return false;
288 }
289
290 @Override
291 public Iterator<T> iterator() {
292 return new NodeListIterator<>(this, 0);
293 }
294
295 @Override
296 public boolean contains(T other) {
297 for (int i = 0; i < size; i++) {
298 if (nodes[i] == other) {
299 return true;
300 }
301 }
302 return false;
303 }
304
305 @SuppressWarnings("unchecked")
306 @Override
307 public List<T> snapshot() {
308 return (List<T>) Arrays.asList(Arrays.copyOf(this.nodes, this.size));
309 }
310
311 @Override
312 public void snapshotTo(Collection<? super T> to) {
313 for (int i = 0; i < size; i++) {
314 to.add(get(i));
315 }
316 }
317
318 @SuppressWarnings("unchecked")
319 public void setAll(NodeList<T> values) {
320 self.incModCount();
321 incModCount();
322 for (int i = 0; i < size(); i++) {
323 update((T) nodes[i], null);
324 }
325 nodes = Arrays.copyOf(values.nodes, values.size());
326 size = values.size();
327
328 for (int i = 0; i < size(); i++) {
329 update(null, (T) nodes[i]);
330 }
331 }
332
333 @Override
334 @SuppressWarnings("unchecked")
335 public <A> A[] toArray(A[] a) {
336 if (a.length >= size) {
337 System.arraycopy(nodes, 0, a, 0, size);
338 return a;
339 }
340 return (A[]) Arrays.copyOf(nodes, size, a.getClass());
341 }
342
343 @Override
344 public Object[] toArray() {
345 return Arrays.copyOf(nodes, size);
346 }
347
348 protected void replace(T node, T other) {
349 incModCount();
350 for (int i = 0; i < size(); i++) {
351 if (nodes[i] == node) {
352 nodes[i] = other;
353 update(node, other);
354 }
355 }
356 }
357
358 @Override
359 public int indexOf(Object node) {
360 for (int i = 0; i < size; i++) {
361 if (nodes[i] == node) {
362 return i;
363 }
364 }
365 return -1;
366 }
367
368 @Override
369 public boolean contains(Object o) {
370 return indexOf(o) != -1;
371 }
372
373 @Override
374 public boolean containsAll(Collection<?> c) {
375 throw new UnsupportedOperationException("not implemented");
376 }
377
378 @Override
379 public boolean addAll(Collection<? extends T> c) {
380 for (T e : c) {
381 add(e);
382 }
383 return true;
384 }
385
386 public boolean addAll(T[] c) {
387 for (T e : c) {
388 add(e);
389 }
390 return true;
391 }
392
393 @Override
394 public String toString() {
395 StringBuilder sb = new StringBuilder();
396 sb.append('[');
397 for (int i = 0; i < size; i++) {
398 if (i != 0) {
399 sb.append(", ");
400 }
401 sb.append(nodes[i]);
402 }
403 sb.append(']');
404 return sb.toString();
405 }
406
407 @Override
408 public T first() {
409 if (size() > 0) {
410 return get(0);
411 }
412 return null;
413 }
414
415 public SubList<T> subList(int startIndex) {
416 assert assertInRange(startIndex);
417 return new SubList<>(this, startIndex);
418 }
419
420 public static final class SubList<R extends Node> extends AbstractList<R> implements NodeIterable<R>, RandomAccess {
421 private final NodeList<R> list;
422 private final int offset;
423
424 private SubList(NodeList<R> list, int offset) {
425 this.list = list;
426 this.offset = offset;
427 }
428
429 @Override
430 public R get(int index) {
431 assert index >= 0 : index;
432 return list.get(offset + index);
433 }
434
435 @Override
436 public int size() {
437 return list.size() - offset;
438 }
439
440 public SubList<R> subList(int startIndex) {
441 assert startIndex >= 0 && startIndex < size() : startIndex;
442 return new SubList<>(this.list, startIndex + offset);
443 }
444
445 @Override
446 public Iterator<R> iterator() {
447 return new NodeListIterator<>(list, offset);
448 }
449 }
450
451 private static final class NodeListIterator<R extends Node> implements Iterator<R> {
452 private final NodeList<R> list;
453 private final int expectedModCount;
454 private int index;
455
456 private NodeListIterator(NodeList<R> list, int startIndex) {
457 this.list = list;
458 this.expectedModCount = list.modCount;
459 this.index = startIndex;
460 }
461
462 @Override
463 public boolean hasNext() {
464 assert expectedModCount == list.modCount;
465 return index < list.size;
466 }
467
468 @SuppressWarnings("unchecked")
469 @Override
470 public R next() {
471 assert expectedModCount == list.modCount;
472 return (R) list.nodes[index++];
473 }
474
475 @Override
476 public void remove() {
477 throw new UnsupportedOperationException();
478 }
479 }
480 }