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