/* * Copyright (c) 2011, 2019, Oracle and/or its affiliates. All rights reserved. * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. * * This code is free software; you can redistribute it and/or modify it * under the terms of the GNU General Public License version 2 only, as * published by the Free Software Foundation. * * This code is distributed in the hope that it will be useful, but WITHOUT * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License * version 2 for more details (a copy is included in the LICENSE file that * accompanied this code). * * You should have received a copy of the GNU General Public License version * 2 along with this work; if not, write to the Free Software Foundation, * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. * * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA * or visit www.oracle.com if you need additional information or have any * questions. */ package org.graalvm.compiler.graph; import java.util.AbstractList; import java.util.Arrays; import java.util.Collection; import java.util.Iterator; import java.util.List; import java.util.RandomAccess; import org.graalvm.compiler.graph.iterators.NodeIterable; public abstract class NodeList extends AbstractList implements NodeIterable, RandomAccess { protected static final Node[] EMPTY_NODE_ARRAY = new Node[0]; protected final Node self; protected Node[] nodes; private int size; protected final int initialSize; protected NodeList(Node self) { this.self = self; this.nodes = EMPTY_NODE_ARRAY; this.initialSize = 0; } protected NodeList(Node self, int initialSize) { this.self = self; this.size = initialSize; this.initialSize = initialSize; this.nodes = new Node[initialSize]; } protected NodeList(Node self, T[] elements) { this.self = self; if (elements == null || elements.length == 0) { this.size = 0; this.nodes = EMPTY_NODE_ARRAY; this.initialSize = 0; } else { this.size = elements.length; this.initialSize = elements.length; this.nodes = new Node[elements.length]; for (int i = 0; i < elements.length; i++) { this.nodes[i] = elements[i]; assert this.nodes[i] == null || !this.nodes[i].isDeleted() : "Initializing nodelist with deleted element : " + nodes[i]; } } } protected NodeList(Node self, List elements) { this.self = self; if (elements == null || elements.isEmpty()) { this.size = 0; this.nodes = EMPTY_NODE_ARRAY; this.initialSize = 0; } else { this.size = elements.size(); this.initialSize = elements.size(); this.nodes = new Node[elements.size()]; for (int i = 0; i < elements.size(); i++) { this.nodes[i] = elements.get(i); assert this.nodes[i] == null || !this.nodes[i].isDeleted(); } } } protected NodeList(Node self, Collection elements) { this.self = self; if (elements == null || elements.isEmpty()) { this.size = 0; this.nodes = EMPTY_NODE_ARRAY; this.initialSize = 0; } else { this.size = elements.size(); this.initialSize = elements.size(); this.nodes = new Node[elements.size()]; int i = 0; for (NodeInterface n : elements) { this.nodes[i] = n.asNode(); assert this.nodes[i] == null || !this.nodes[i].isDeleted(); i++; } } } /** * Removes null values from the list. */ public void trim() { int newSize = 0; for (int i = 0; i < nodes.length; ++i) { if (nodes[i] != null) { nodes[newSize] = nodes[i]; newSize++; } } size = newSize; } public boolean isList() { return true; } protected abstract void update(T oldNode, T newNode); public abstract Edges.Type getEdgesType(); @Override public final int size() { return size; } @Override public final boolean isEmpty() { return size == 0; } @Override public boolean isNotEmpty() { return size > 0; } @Override public int count() { return size; } protected final void incModCount() { modCount++; } @SuppressWarnings("unchecked") @Override public boolean add(Node node) { assert node == null || !node.isDeleted() : node; self.incModCount(); incModCount(); int length = nodes.length; if (length == 0) { nodes = new Node[2]; } else if (size == length) { Node[] newNodes = new Node[nodes.length * 2 + 1]; System.arraycopy(nodes, 0, newNodes, 0, length); nodes = newNodes; } nodes[size++] = node; update(null, (T) node); return true; } @Override @SuppressWarnings("unchecked") public T get(int index) { assert assertInRange(index); return (T) nodes[index]; } private boolean assertInRange(int index) { assert index >= 0 && index < size() : index + " < " + size(); return true; } public T last() { return get(size() - 1); } @Override @SuppressWarnings("unchecked") public T set(int index, Node node) { incModCount(); T oldValue = (T) nodes[index]; assert assertInRange(index); update((T) nodes[index], (T) node); nodes[index] = node; return oldValue; } public void initialize(int index, Node node) { incModCount(); assert index < size(); nodes[index] = node; } void copy(NodeList other) { self.incModCount(); incModCount(); Node[] newNodes = new Node[other.size]; System.arraycopy(other.nodes, 0, newNodes, 0, newNodes.length); nodes = newNodes; size = other.size; } @Override public boolean equals(Object other) { if (other == this) { return true; } if (other instanceof List) { List otherList = (List) other; if (size != otherList.size()) { return false; } for (int i = 0; i < size; i++) { if (nodes[i] != otherList.get(i)) { return false; } } return true; } return false; } @SuppressWarnings("unchecked") @Override public void clear() { self.incModCount(); incModCount(); for (int i = 0; i < size; i++) { update((T) nodes[i], null); } clearWithoutUpdate(); } void clearWithoutUpdate() { nodes = EMPTY_NODE_ARRAY; size = 0; } @Override @SuppressWarnings("unchecked") public boolean remove(Object node) { self.incModCount(); int i = 0; incModCount(); while (i < size && nodes[i] != node) { i++; } if (i < size) { T oldValue = (T) nodes[i]; i++; while (i < size) { nodes[i - 1] = nodes[i]; i++; } nodes[--size] = null; update(oldValue, null); return true; } else { return false; } } @Override @SuppressWarnings("unchecked") public T remove(int index) { self.incModCount(); T oldValue = (T) nodes[index]; int i = index + 1; incModCount(); while (i < size) { nodes[i - 1] = nodes[i]; i++; } nodes[--size] = null; update(oldValue, null); return oldValue; } boolean replaceFirst(Node node, Node other) { for (int i = 0; i < size; i++) { if (nodes[i] == node) { nodes[i] = other; return true; } } return false; } @Override public Iterator iterator() { return new NodeListIterator<>(this, 0); } @Override public boolean contains(T other) { for (int i = 0; i < size; i++) { if (nodes[i] == other) { return true; } } return false; } @SuppressWarnings("unchecked") @Override public List snapshot() { return (List) Arrays.asList(Arrays.copyOf(this.nodes, this.size)); } @Override public void snapshotTo(Collection to) { for (int i = 0; i < size; i++) { to.add(get(i)); } } @SuppressWarnings("unchecked") public void setAll(NodeList values) { self.incModCount(); incModCount(); for (int i = 0; i < size(); i++) { update((T) nodes[i], null); } nodes = Arrays.copyOf(values.nodes, values.size()); size = values.size(); for (int i = 0; i < size(); i++) { update(null, (T) nodes[i]); } } @Override @SuppressWarnings("unchecked") public A[] toArray(A[] a) { if (a.length >= size) { System.arraycopy(nodes, 0, a, 0, size); return a; } return (A[]) Arrays.copyOf(nodes, size, a.getClass()); } @Override public Object[] toArray() { return Arrays.copyOf(nodes, size); } protected void replace(T node, T other) { incModCount(); for (int i = 0; i < size(); i++) { if (nodes[i] == node) { nodes[i] = other; update(node, other); } } } @Override public int indexOf(Object node) { for (int i = 0; i < size; i++) { if (nodes[i] == node) { return i; } } return -1; } @Override public boolean contains(Object o) { return indexOf(o) != -1; } @Override public boolean containsAll(Collection c) { throw new UnsupportedOperationException("not implemented"); } @Override public boolean addAll(Collection c) { for (T e : c) { add(e); } return true; } public boolean addAll(T[] c) { for (T e : c) { add(e); } return true; } @Override public String toString() { StringBuilder sb = new StringBuilder(); sb.append('['); for (int i = 0; i < size; i++) { if (i != 0) { sb.append(", "); } sb.append(nodes[i]); } sb.append(']'); return sb.toString(); } @Override public T first() { if (size() > 0) { return get(0); } return null; } public SubList subList(int startIndex) { assert assertInRange(startIndex); return new SubList<>(this, startIndex); } public static final class SubList extends AbstractList implements NodeIterable, RandomAccess { private final NodeList list; private final int offset; private SubList(NodeList list, int offset) { this.list = list; this.offset = offset; } @Override public R get(int index) { assert index >= 0 : index; return list.get(offset + index); } @Override public int size() { return list.size() - offset; } public SubList subList(int startIndex) { assert startIndex >= 0 && startIndex < size() : startIndex; return new SubList<>(this.list, startIndex + offset); } @Override public Iterator iterator() { return new NodeListIterator<>(list, offset); } } private static final class NodeListIterator implements Iterator { private final NodeList list; private final int expectedModCount; private int index; private NodeListIterator(NodeList list, int startIndex) { this.list = list; this.expectedModCount = list.modCount; this.index = startIndex; } @Override public boolean hasNext() { assert expectedModCount == list.modCount; return index < list.size; } @SuppressWarnings("unchecked") @Override public R next() { assert expectedModCount == list.modCount; return (R) list.nodes[index++]; } @Override public void remove() { throw new UnsupportedOperationException(); } } }