# HG changeset patch
# User Doug Simon <doug.simon@oracle.com>
# Date 1378462544 -7200
# Node ID edf875b3c091f3f0f368689fc402c50cfcab0900
# Parent  6317ef27930dca529312522349b1db5320f56c52
use binary search when looking for the end of Node.extraUsages (GRAAL-452)

diff -r 6317ef27930d -r edf875b3c091 graal/com.oracle.graal.graph/src/com/oracle/graal/graph/Node.java
--- a/graal/com.oracle.graal.graph/src/com/oracle/graal/graph/Node.java	Thu Sep 05 17:34:36 2013 -0700
+++ b/graal/com.oracle.graal.graph/src/com/oracle/graal/graph/Node.java	Fri Sep 06 12:15:44 2013 +0200
@@ -236,11 +236,7 @@
             if (usage1 == null) {
                 return 1;
             }
-            int count = 2;
-            for (int i = 0; i < extraUsages.length && extraUsages[i] != null; i++) {
-                count++;
-            }
-            return count;
+            return 2 + indexOfLastNonNull(extraUsages) + 1;
         }
     }
 
@@ -252,6 +248,40 @@
     }
 
     /**
+     * Finds the index of the last non-null entry in a node array. The search assumes that all
+     * non-null entries precede the first null entry in the array.
+     * 
+     * @param nodes the array to search
+     * @return the index of the last non-null entry in {@code nodes} if it exists, else -1
+     */
+    private static int indexOfLastNonNull(Node[] nodes) {
+        if (nodes.length == 0 || nodes[0] == null) {
+            return -1;
+        }
+        if (nodes[nodes.length - 1] != null) {
+            return nodes.length - 1;
+        }
+
+        // binary search
+        int low = 0;
+        int high = nodes.length - 1;
+        while (true) {
+            int mid = (low + high) >>> 1;
+            if (nodes[mid] == null) {
+                if (nodes[mid - 1] != null) {
+                    return mid - 1;
+                }
+                high = mid - 1;
+            } else {
+                if (mid == nodes.length - 1 || nodes[mid + 1] == null) {
+                    return mid;
+                }
+                low = mid + 1;
+            }
+        }
+    }
+
+    /**
      * Adds a given node to this node's {@linkplain #usages() usages}.
      * 
      * @param node the node to add
@@ -264,42 +294,23 @@
             usage1 = node;
         } else {
             int length = extraUsages.length;
-            int start = extraUsages.length >> 1;
-            if (start < length && extraUsages[start] == null) {
-                start = 0;
-            }
-            for (int i = start; i < length; i++) {
-                if (extraUsages[i] == null) {
-                    extraUsages[i] = node;
-                    return;
+            if (length == 0) {
+                extraUsages = new Node[4];
+                extraUsages[0] = node;
+            } else {
+                int lastNonNull = indexOfLastNonNull(extraUsages);
+                if (lastNonNull == length - 1) {
+                    extraUsages = Arrays.copyOf(extraUsages, length * 2 + 1);
+                    extraUsages[length] = node;
+                } else if (lastNonNull == -1) {
+                    extraUsages[0] = node;
+                } else {
+                    extraUsages[lastNonNull + 1] = node;
                 }
             }
-            extraUsages = Arrays.copyOf(extraUsages, length * 2 + 1);
-            extraUsages[length] = node;
         }
     }
 
-    private Node removeLastUsage() {
-        for (int i = extraUsages.length - 1; i >= 0; --i) {
-            Node n = extraUsages[i];
-            if (n != null) {
-                extraUsages[i] = null;
-                return n;
-            }
-        }
-        if (usage1 != null) {
-            Node n = usage1;
-            usage1 = null;
-            return n;
-        }
-        if (usage0 != null) {
-            Node n = usage0;
-            usage0 = null;
-            return n;
-        }
-        return null;
-    }
-
     /**
      * Removes a given node from this node's {@linkplain #usages() usages}.
      * 
@@ -310,13 +321,17 @@
         // It is critical that this method maintains the invariant that
         // the usage list has no null element preceding a non-null element
         incUsageModCount();
-        if (usage0 == null) {
-            return false;
-        }
         if (usage0 == node) {
             if (usage1 != null) {
-                // usage0 is not the last element
-                usage0 = removeLastUsage();
+                int lastNonNull = indexOfLastNonNull(extraUsages);
+                if (lastNonNull >= 0) {
+                    usage0 = extraUsages[lastNonNull];
+                    extraUsages[lastNonNull] = null;
+                } else {
+                    // usage1 is the last element
+                    usage0 = usage1;
+                    usage1 = null;
+                }
             } else {
                 // usage0 is the last element
                 usage0 = null;
@@ -324,30 +339,28 @@
             return true;
         }
         if (usage1 == node) {
-            if (extraUsages.length != 0 && extraUsages[0] != null) {
-                // usage1 is not the last element
-                usage1 = removeLastUsage();
+            int lastNonNull = indexOfLastNonNull(extraUsages);
+            if (lastNonNull >= 0) {
+                usage1 = extraUsages[lastNonNull];
+                extraUsages[lastNonNull] = null;
             } else {
                 // usage1 is the last element
                 usage1 = null;
             }
             return true;
         }
-        for (int i = extraUsages.length - 1; i >= 0; --i) {
-            Node n = extraUsages[i];
-            if (n != null) {
+        int lastNonNull = indexOfLastNonNull(extraUsages);
+        if (lastNonNull >= 0) {
+            for (int i = 0; i <= lastNonNull; ++i) {
+                Node n = extraUsages[i];
                 if (n == node) {
-                    extraUsages[i] = null;
+                    if (i < lastNonNull) {
+                        extraUsages[i] = extraUsages[lastNonNull];
+                        extraUsages[lastNonNull] = null;
+                    } else {
+                        extraUsages[i] = null;
+                    }
                     return true;
-                } else {
-                    for (int j = 0; j < i; j++) {
-                        if (extraUsages[j] == node) {
-                            // Move the last element to the position of 'node'
-                            extraUsages[j] = n;
-                            extraUsages[i] = null;
-                            return true;
-                        }
-                    }
                 }
             }
         }