1 /*
2 * Copyright (c) 2011, 2019, 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 /**
112 * Removes null values from the list.
113 */
114 public void trim() {
115 int newSize = 0;
116 for (int i = 0; i < nodes.length; ++i) {
117 if (nodes[i] != null) {
118 nodes[newSize] = nodes[i];
119 newSize++;
120 }
121 }
122 size = newSize;
123 }
124
125 public boolean isList() {
126 return true;
127 }
128
129 protected abstract void update(T oldNode, T newNode);
130
131 public abstract Edges.Type getEdgesType();
132
133 @Override
134 public final int size() {
135 return size;
136 }
137
138 @Override
139 public final boolean isEmpty() {
140 return size == 0;
141 }
142
143 @Override
144 public boolean isNotEmpty() {
145 return size > 0;
146 }
147
148 @Override
149 public int count() {
150 return size;
151 }
152
153 protected final void incModCount() {
154 modCount++;
155 }
156
157 @SuppressWarnings("unchecked")
158 @Override
159 public boolean add(Node node) {
160 assert node == null || !node.isDeleted() : node;
161 self.incModCount();
162 incModCount();
163 int length = nodes.length;
164 if (length == 0) {
165 nodes = new Node[2];
166 } else if (size == length) {
167 Node[] newNodes = new Node[nodes.length * 2 + 1];
168 System.arraycopy(nodes, 0, newNodes, 0, length);
169 nodes = newNodes;
170 }
171 nodes[size++] = node;
172 update(null, (T) node);
173 return true;
174 }
175
176 @Override
177 @SuppressWarnings("unchecked")
178 public T get(int index) {
179 assert assertInRange(index);
180 return (T) nodes[index];
181 }
182
183 private boolean assertInRange(int index) {
184 assert index >= 0 && index < size() : index + " < " + size();
185 return true;
186 }
187
188 public T last() {
189 return get(size() - 1);
190 }
191
192 @Override
193 @SuppressWarnings("unchecked")
194 public T set(int index, Node node) {
195 incModCount();
196 T oldValue = (T) nodes[index];
197 assert assertInRange(index);
198 update((T) nodes[index], (T) node);
199 nodes[index] = node;
200 return oldValue;
201 }
202
203 public void initialize(int index, Node node) {
204 incModCount();
205 assert index < size();
206 nodes[index] = node;
207 }
208
209 void copy(NodeList<? extends Node> other) {
210 self.incModCount();
211 incModCount();
212 Node[] newNodes = new Node[other.size];
213 System.arraycopy(other.nodes, 0, newNodes, 0, newNodes.length);
214 nodes = newNodes;
215 size = other.size;
216 }
217
218 @Override
219 public boolean equals(Object other) {
220 if (other == this) {
221 return true;
222 }
223 if (other instanceof List<?>) {
224 List<?> otherList = (List<?>) other;
225 if (size != otherList.size()) {
226 return false;
227 }
228 for (int i = 0; i < size; i++) {
229 if (nodes[i] != otherList.get(i)) {
230 return false;
231 }
232 }
233 return true;
234 }
235 return false;
236 }
237
238 @SuppressWarnings("unchecked")
239 @Override
240 public void clear() {
241 self.incModCount();
242 incModCount();
243 for (int i = 0; i < size; i++) {
244 update((T) nodes[i], null);
245 }
246 clearWithoutUpdate();
247 }
248
249 void clearWithoutUpdate() {
250 nodes = EMPTY_NODE_ARRAY;
251 size = 0;
252 }
253
254 @Override
255 @SuppressWarnings("unchecked")
256 public boolean remove(Object node) {
257 self.incModCount();
258 int i = 0;
259 incModCount();
260 while (i < size && nodes[i] != node) {
261 i++;
262 }
263 if (i < size) {
264 T oldValue = (T) nodes[i];
265 i++;
266 while (i < size) {
267 nodes[i - 1] = nodes[i];
268 i++;
269 }
270 nodes[--size] = null;
271 update(oldValue, null);
272 return true;
273 } else {
274 return false;
275 }
276 }
277
278 @Override
279 @SuppressWarnings("unchecked")
280 public T remove(int index) {
281 self.incModCount();
282 T oldValue = (T) nodes[index];
283 int i = index + 1;
284 incModCount();
285 while (i < size) {
286 nodes[i - 1] = nodes[i];
287 i++;
288 }
289 nodes[--size] = null;
290 update(oldValue, null);
291 return oldValue;
292 }
293
294 boolean replaceFirst(Node node, Node other) {
295 for (int i = 0; i < size; i++) {
296 if (nodes[i] == node) {
297 nodes[i] = other;
298 return true;
299 }
300 }
301 return false;
302 }
303
304 @Override
305 public Iterator<T> iterator() {
306 return new NodeListIterator<>(this, 0);
307 }
308
309 @Override
310 public boolean contains(T other) {
311 for (int i = 0; i < size; i++) {
312 if (nodes[i] == other) {
313 return true;
314 }
315 }
316 return false;
317 }
318
319 @SuppressWarnings("unchecked")
320 @Override
321 public List<T> snapshot() {
322 return (List<T>) Arrays.asList(Arrays.copyOf(this.nodes, this.size));
323 }
324
325 @Override
326 public void snapshotTo(Collection<? super T> to) {
327 for (int i = 0; i < size; i++) {
328 to.add(get(i));
329 }
330 }
331
332 @SuppressWarnings("unchecked")
333 public void setAll(NodeList<T> values) {
334 self.incModCount();
335 incModCount();
336 for (int i = 0; i < size(); i++) {
337 update((T) nodes[i], null);
338 }
339 nodes = Arrays.copyOf(values.nodes, values.size());
340 size = values.size();
341
342 for (int i = 0; i < size(); i++) {
343 update(null, (T) nodes[i]);
344 }
345 }
346
347 @Override
348 @SuppressWarnings("unchecked")
349 public <A> A[] toArray(A[] a) {
350 if (a.length >= size) {
351 System.arraycopy(nodes, 0, a, 0, size);
352 return a;
353 }
354 return (A[]) Arrays.copyOf(nodes, size, a.getClass());
355 }
356
357 @Override
358 public Object[] toArray() {
359 return Arrays.copyOf(nodes, size);
360 }
361
362 protected void replace(T node, T other) {
363 incModCount();
364 for (int i = 0; i < size(); i++) {
365 if (nodes[i] == node) {
366 nodes[i] = other;
367 update(node, other);
368 }
369 }
370 }
371
372 @Override
373 public int indexOf(Object node) {
374 for (int i = 0; i < size; i++) {
375 if (nodes[i] == node) {
376 return i;
377 }
378 }
379 return -1;
380 }
381
382 @Override
383 public boolean contains(Object o) {
384 return indexOf(o) != -1;
385 }
386
387 @Override
388 public boolean containsAll(Collection<?> c) {
389 throw new UnsupportedOperationException("not implemented");
390 }
391
392 @Override
393 public boolean addAll(Collection<? extends T> c) {
394 for (T e : c) {
395 add(e);
396 }
397 return true;
398 }
399
400 public boolean addAll(T[] c) {
401 for (T e : c) {
402 add(e);
403 }
404 return true;
405 }
406
407 @Override
408 public String toString() {
409 StringBuilder sb = new StringBuilder();
410 sb.append('[');
411 for (int i = 0; i < size; i++) {
412 if (i != 0) {
413 sb.append(", ");
414 }
415 sb.append(nodes[i]);
416 }
417 sb.append(']');
418 return sb.toString();
419 }
420
421 @Override
422 public T first() {
423 if (size() > 0) {
424 return get(0);
425 }
426 return null;
427 }
428
429 public SubList<T> subList(int startIndex) {
430 assert assertInRange(startIndex);
431 return new SubList<>(this, startIndex);
432 }
433
434 public static final class SubList<R extends Node> extends AbstractList<R> implements NodeIterable<R>, RandomAccess {
435 private final NodeList<R> list;
436 private final int offset;
437
438 private SubList(NodeList<R> list, int offset) {
439 this.list = list;
440 this.offset = offset;
441 }
442
443 @Override
444 public R get(int index) {
445 assert index >= 0 : index;
446 return list.get(offset + index);
447 }
448
449 @Override
450 public int size() {
451 return list.size() - offset;
452 }
453
454 public SubList<R> subList(int startIndex) {
455 assert startIndex >= 0 && startIndex < size() : startIndex;
456 return new SubList<>(this.list, startIndex + offset);
457 }
458
459 @Override
460 public Iterator<R> iterator() {
461 return new NodeListIterator<>(list, offset);
462 }
463 }
464
465 private static final class NodeListIterator<R extends Node> implements Iterator<R> {
466 private final NodeList<R> list;
467 private final int expectedModCount;
468 private int index;
469
470 private NodeListIterator(NodeList<R> list, int startIndex) {
471 this.list = list;
472 this.expectedModCount = list.modCount;
473 this.index = startIndex;
474 }
475
476 @Override
477 public boolean hasNext() {
478 assert expectedModCount == list.modCount;
479 return index < list.size;
480 }
481
482 @SuppressWarnings("unchecked")
483 @Override
484 public R next() {
485 assert expectedModCount == list.modCount;
486 return (R) list.nodes[index++];
487 }
488
489 @Override
490 public void remove() {
491 throw new UnsupportedOperationException();
492 }
493 }
494 }