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     public boolean equals(NodeList<T> other) {
 205         if (size != other.size) {
 206             return false;
 207         }
 208         for (int i = 0; i < size; i++) {
 209             if (nodes[i] != other.nodes[i]) {
 210                 return false;
 211             }
 212         }
 213         return true;
 214     }
 215 
 216     @SuppressWarnings("unchecked")
 217     @Override
 218     public void clear() {
 219         self.incModCount();
 220         incModCount();
 221         for (int i = 0; i < size; i++) {
 222             update((T) nodes[i], null);
 223         }
 224         clearWithoutUpdate();
 225     }
 226 
 227     void clearWithoutUpdate() {
 228         nodes = EMPTY_NODE_ARRAY;
 229         size = 0;
 230     }
 231 
 232     @Override
 233     @SuppressWarnings("unchecked")
 234     public boolean remove(Object node) {
 235         self.incModCount();
 236         int i = 0;
 237         incModCount();
 238         while (i < size && nodes[i] != node) {
 239             i++;
 240         }
 241         if (i < size) {
 242             T oldValue = (T) nodes[i];
 243             i++;
 244             while (i < size) {
 245                 nodes[i - 1] = nodes[i];
 246                 i++;
 247             }
 248             nodes[--size] = null;
 249             update(oldValue, null);
 250             return true;
 251         } else {
 252             return false;
 253         }
 254     }
 255 
 256     @Override
 257     @SuppressWarnings("unchecked")
 258     public T remove(int index) {
 259         self.incModCount();
 260         T oldValue = (T) nodes[index];
 261         int i = index + 1;
 262         incModCount();
 263         while (i < size) {
 264             nodes[i - 1] = nodes[i];
 265             i++;
 266         }
 267         nodes[--size] = null;
 268         update(oldValue, null);
 269         return oldValue;
 270     }
 271 
 272     boolean replaceFirst(Node node, Node other) {
 273         for (int i = 0; i < size; i++) {
 274             if (nodes[i] == node) {
 275                 nodes[i] = other;
 276                 return true;
 277             }
 278         }
 279         return false;
 280     }
 281 
 282     @Override
 283     public Iterator<T> iterator() {
 284         return new NodeListIterator<>(this, 0);
 285     }
 286 
 287     @Override
 288     public boolean contains(T other) {
 289         for (int i = 0; i < size; i++) {
 290             if (nodes[i] == other) {
 291                 return true;
 292             }
 293         }
 294         return false;
 295     }
 296 
 297     @SuppressWarnings("unchecked")
 298     @Override
 299     public List<T> snapshot() {
 300         return (List<T>) Arrays.asList(Arrays.copyOf(this.nodes, this.size));
 301     }
 302 
 303     @Override
 304     public void snapshotTo(Collection<? super T> to) {
 305         for (int i = 0; i < size; i++) {
 306             to.add(get(i));
 307         }
 308     }
 309 
 310     @SuppressWarnings("unchecked")
 311     public void setAll(NodeList<T> values) {
 312         self.incModCount();
 313         incModCount();
 314         for (int i = 0; i < size(); i++) {
 315             update((T) nodes[i], null);
 316         }
 317         nodes = Arrays.copyOf(values.nodes, values.size());
 318         size = values.size();
 319 
 320         for (int i = 0; i < size(); i++) {
 321             update(null, (T) nodes[i]);
 322         }
 323     }
 324 
 325     @Override
 326     @SuppressWarnings("unchecked")
 327     public <A> A[] toArray(A[] a) {
 328         if (a.length >= size) {
 329             System.arraycopy(nodes, 0, a, 0, size);
 330             return a;
 331         }
 332         return (A[]) Arrays.copyOf(nodes, size, a.getClass());
 333     }
 334 
 335     @Override
 336     public Object[] toArray() {
 337         return Arrays.copyOf(nodes, size);
 338     }
 339 
 340     protected void replace(T node, T other) {
 341         incModCount();
 342         for (int i = 0; i < size(); i++) {
 343             if (nodes[i] == node) {
 344                 nodes[i] = other;
 345                 update(node, other);
 346             }
 347         }
 348     }
 349 
 350     @Override
 351     public int indexOf(Object node) {
 352         for (int i = 0; i < size; i++) {
 353             if (nodes[i] == node) {
 354                 return i;
 355             }
 356         }
 357         return -1;
 358     }
 359 
 360     @Override
 361     public boolean contains(Object o) {
 362         return indexOf(o) != -1;
 363     }
 364 
 365     @Override
 366     public boolean containsAll(Collection<?> c) {
 367         throw new UnsupportedOperationException("not implemented");
 368     }
 369 
 370     @Override
 371     public boolean addAll(Collection<? extends T> c) {
 372         for (T e : c) {
 373             add(e);
 374         }
 375         return true;
 376     }
 377 
 378     public boolean addAll(T[] c) {
 379         for (T e : c) {
 380             add(e);
 381         }
 382         return true;
 383     }
 384 
 385     @Override
 386     public String toString() {
 387         StringBuilder sb = new StringBuilder();
 388         sb.append('[');
 389         for (int i = 0; i < size; i++) {
 390             if (i != 0) {
 391                 sb.append(", ");
 392             }
 393             sb.append(nodes[i]);
 394         }
 395         sb.append(']');
 396         return sb.toString();
 397     }
 398 
 399     @Override
 400     public T first() {
 401         if (size() > 0) {
 402             return get(0);
 403         }
 404         return null;
 405     }
 406 
 407     public SubList<T> subList(int startIndex) {
 408         assert assertInRange(startIndex);
 409         return new SubList<>(this, startIndex);
 410     }
 411 
 412     public static final class SubList<R extends Node> extends AbstractList<R> implements NodeIterable<R>, RandomAccess {
 413         private final NodeList<R> list;
 414         private final int offset;
 415 
 416         private SubList(NodeList<R> list, int offset) {
 417             this.list = list;
 418             this.offset = offset;
 419         }
 420 
 421         @Override
 422         public R get(int index) {
 423             assert index >= 0 : index;
 424             return list.get(offset + index);
 425         }
 426 
 427         @Override
 428         public int size() {
 429             return list.size() - offset;
 430         }
 431 
 432         public SubList<R> subList(int startIndex) {
 433             assert startIndex >= 0 && startIndex < size() : startIndex;
 434             return new SubList<>(this.list, startIndex + offset);
 435         }
 436 
 437         @Override
 438         public Iterator<R> iterator() {
 439             return new NodeListIterator<>(list, offset);
 440         }
 441     }
 442 
 443     private static final class NodeListIterator<R extends Node> implements Iterator<R> {
 444         private final NodeList<R> list;
 445         private final int expectedModCount;
 446         private int index;
 447 
 448         private NodeListIterator(NodeList<R> list, int startIndex) {
 449             this.list = list;
 450             this.expectedModCount = list.modCount;
 451             this.index = startIndex;
 452         }
 453 
 454         @Override
 455         public boolean hasNext() {
 456             assert expectedModCount == list.modCount;
 457             return index < list.size;
 458         }
 459 
 460         @SuppressWarnings("unchecked")
 461         @Override
 462         public R next() {
 463             assert expectedModCount == list.modCount;
 464             return (R) list.nodes[index++];
 465         }
 466 
 467         @Override
 468         public void remove() {
 469             throw new UnsupportedOperationException();
 470         }
 471     }
 472 }