# HG changeset patch
# User Bernhard Urban <bernhard.urban@jku.at>
# Date 1387294731 -3600
# Node ID c3ecad078114bf001fa3aa7225f8f9d016ed9d2f
# Parent  79298b99df02544374bedefbf79453d79833fbd2
utils: introduce ArraySet.  use it instead of HashSet at some places

diff -r 79298b99df02 -r c3ecad078114 graal/com.oracle.graal.phases/src/com/oracle/graal/phases/graph/ComputeProbabilityClosure.java
--- a/graal/com.oracle.graal.phases/src/com/oracle/graal/phases/graph/ComputeProbabilityClosure.java	Tue Dec 17 16:09:03 2013 +0100
+++ b/graal/com.oracle.graal.phases/src/com/oracle/graal/phases/graph/ComputeProbabilityClosure.java	Tue Dec 17 16:38:51 2013 +0100
@@ -28,6 +28,7 @@
 import com.oracle.graal.graph.*;
 import com.oracle.graal.nodes.*;
 import com.oracle.graal.nodes.util.*;
+import com.oracle.graal.phases.util.*;
 
 /**
  * Computes probabilities for nodes in a graph.
@@ -58,7 +59,7 @@
     public ComputeProbabilityClosure(StructuredGraph graph) {
         this.graph = graph;
         this.nodeProbabilities = new NodesToDoubles(graph.getNodeCount());
-        this.loopInfos = new HashSet<>();
+        this.loopInfos = new ArraySet<>();
         this.mergeLoops = new IdentityHashMap<>();
     }
 
@@ -75,7 +76,7 @@
      * Assume that paths with a DeoptimizeNode at their end are taken infrequently.
      */
     private void adjustControlSplitProbabilities() {
-        HashSet<ControlSplitNode> result = new HashSet<>();
+        Set<ControlSplitNode> result = new ArraySet<>();
         NodeBitMap visitedNodes = new NodeBitMap(graph);
         for (AbstractDeoptimizeNode n : graph.getNodes(AbstractDeoptimizeNode.class)) {
             if (!(n instanceof DeoptimizeNode) || ((DeoptimizeNode) n).action().doesInvalidateCompilation()) {
@@ -90,7 +91,7 @@
         }
     }
 
-    private static void findParentControlSplitNodes(HashSet<ControlSplitNode> result, AbstractDeoptimizeNode n, NodeBitMap visitedNodes) {
+    private static void findParentControlSplitNodes(Set<ControlSplitNode> result, AbstractDeoptimizeNode n, NodeBitMap visitedNodes) {
         ArrayDeque<FixedNode> nodes = new ArrayDeque<>();
         nodes.push(n);
 
@@ -221,13 +222,13 @@
     private class Probability extends MergeableState<Probability> {
 
         public double probability;
-        public HashSet<LoopInfo> loops;
+        public Set<LoopInfo> loops;
         public LoopInfo loopInfo;
 
-        public Probability(double probability, HashSet<LoopInfo> loops) {
+        public Probability(double probability, Set<LoopInfo> loops) {
             assert probability >= 0.0;
             this.probability = probability;
-            this.loops = new HashSet<>(4);
+            this.loops = new ArraySet<>(4);
             if (loops != null) {
                 this.loops.addAll(loops);
             }
@@ -241,7 +242,7 @@
         @Override
         public boolean merge(MergeNode merge, List<Probability> withStates) {
             if (merge.forwardEndCount() > 1) {
-                HashSet<LoopInfo> intersection = new HashSet<>(loops);
+                Set<LoopInfo> intersection = new ArraySet<>(loops);
                 for (Probability other : withStates) {
                     intersection.retainAll(other.loops);
                 }
@@ -271,7 +272,7 @@
                     assert probability >= 0;
                 }
                 loops = intersection;
-                mergeLoops.put(merge, new HashSet<>(intersection));
+                mergeLoops.put(merge, new ArraySet<>(intersection));
                 probability = Math.max(0.0, probability);
             }
             return true;
diff -r 79298b99df02 -r c3ecad078114 graal/com.oracle.graal.phases/src/com/oracle/graal/phases/schedule/SchedulePhase.java
--- a/graal/com.oracle.graal.phases/src/com/oracle/graal/phases/schedule/SchedulePhase.java	Tue Dec 17 16:09:03 2013 +0100
+++ b/graal/com.oracle.graal.phases/src/com/oracle/graal/phases/schedule/SchedulePhase.java	Tue Dec 17 16:38:51 2013 +0100
@@ -42,6 +42,7 @@
 import com.oracle.graal.phases.graph.*;
 import com.oracle.graal.phases.graph.ReentrantBlockIterator.BlockIteratorClosure;
 import com.oracle.graal.phases.graph.ReentrantBlockIterator.LoopInfo;
+import com.oracle.graal.phases.util.*;
 
 public final class SchedulePhase extends Phase {
 
@@ -178,7 +179,7 @@
         private final Set<LocationIdentity> set;
 
         public KillSet() {
-            this.set = new HashSet<>();
+            this.set = new ArraySet<>();
         }
 
         public KillSet(KillSet other) {
diff -r 79298b99df02 -r c3ecad078114 graal/com.oracle.graal.phases/src/com/oracle/graal/phases/util/ArraySet.java
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/graal/com.oracle.graal.phases/src/com/oracle/graal/phases/util/ArraySet.java	Tue Dec 17 16:38:51 2013 +0100
@@ -0,0 +1,54 @@
+/*
+ * Copyright (c) 2013, 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 com.oracle.graal.phases.util;
+
+import java.util.*;
+
+/**
+ * Mimic a set implementation with an ArrayList. Beneficial for small sets (compared to
+ * {@link HashSet}).
+ */
+public class ArraySet<E> extends ArrayList<E> implements Set<E> {
+    private static final long serialVersionUID = 4476957522387436654L;
+
+    public ArraySet() {
+        super();
+    }
+
+    public ArraySet(int i) {
+        super(i);
+    }
+
+    public ArraySet(Collection<? extends E> c) {
+        super(c);
+    }
+
+    @Override
+    public boolean add(E e) {
+        // avoid duplicated entries
+        if (contains(e)) {
+            return true;
+        }
+        return super.add(e);
+    }
+}
diff -r 79298b99df02 -r c3ecad078114 graal/com.oracle.graal.virtual/src/com/oracle/graal/virtual/phases/ea/PartialEscapeClosure.java
--- a/graal/com.oracle.graal.virtual/src/com/oracle/graal/virtual/phases/ea/PartialEscapeClosure.java	Tue Dec 17 16:09:03 2013 +0100
+++ b/graal/com.oracle.graal.virtual/src/com/oracle/graal/virtual/phases/ea/PartialEscapeClosure.java	Tue Dec 17 16:38:51 2013 +0100
@@ -37,6 +37,7 @@
 import com.oracle.graal.nodes.spi.Virtualizable.EscapeState;
 import com.oracle.graal.nodes.virtual.*;
 import com.oracle.graal.phases.schedule.*;
+import com.oracle.graal.phases.util.*;
 import com.oracle.graal.virtual.nodes.*;
 
 public abstract class PartialEscapeClosure<BlockT extends PartialEscapeBlockState<BlockT>> extends EffectsClosure<BlockT> {
@@ -136,7 +137,7 @@
                 nodeWithState.asNode().replaceFirstInput(frameState, frameState.copyWithInputs());
                 frameState = nodeWithState.getState();
             }
-            final HashSet<ObjectState> virtual = new HashSet<>();
+            final Set<ObjectState> virtual = new ArraySet<>();
             frameState.applyToNonVirtual(new NodeClosure<ValueNode>() {
 
                 @Override