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