From 091f7ccf9a97aed94383370666b592a57a1b9400 Mon Sep 17 00:00:00 2001
From: Tim Murray <timmurray@google.com>
Date: Fri, 12 Oct 2012 12:02:18 -0700
Subject: Fix cycle detection for SGs.

bug 7318821

Change-Id: I695d7230551d8512c6c3f0c31c57f12498da7036
---
 .../java/android/renderscript/ScriptGroup.java     | 42 +++++++---------------
 1 file changed, 13 insertions(+), 29 deletions(-)

(limited to 'graphics')

diff --git a/graphics/java/android/renderscript/ScriptGroup.java b/graphics/java/android/renderscript/ScriptGroup.java
index 8943f75..7afdb39 100644
--- a/graphics/java/android/renderscript/ScriptGroup.java
+++ b/graphics/java/android/renderscript/ScriptGroup.java
@@ -77,7 +77,6 @@ public final class ScriptGroup extends BaseObj {
         ArrayList<Script.KernelID> mKernels = new ArrayList<Script.KernelID>();
         ArrayList<ConnectLine> mInputs = new ArrayList<ConnectLine>();
         ArrayList<ConnectLine> mOutputs = new ArrayList<ConnectLine>();
-        boolean mSeen;
         int dagNumber;
 
         Node mNext;
@@ -176,39 +175,24 @@ public final class ScriptGroup extends BaseObj {
             mRS = rs;
         }
 
-        private void validateCycleRecurse(Node n, int depth) {
-            n.mSeen = true;
-
-            //android.util.Log.v("RSR", " validateCycleRecurse outputCount " + n.mOutputs.size());
-            for (int ct=0; ct < n.mOutputs.size(); ct++) {
-                final ConnectLine cl = n.mOutputs.get(ct);
+        // do a DFS from original node, looking for original node
+        // any cycle that could be created must contain original node
+        private void validateCycle(Node target, Node original) {
+            for (int ct = 0; ct < target.mOutputs.size(); ct++) {
+                final ConnectLine cl = target.mOutputs.get(ct);
                 if (cl.mToK != null) {
                     Node tn = findNode(cl.mToK.mScript);
-                    if (tn.mSeen) {
+                    if (tn.equals(original)) {
                         throw new RSInvalidStateException("Loops in group not allowed.");
                     }
-                    validateCycleRecurse(tn, depth + 1);
+                    validateCycle(tn, original);
                 }
                 if (cl.mToF != null) {
                     Node tn = findNode(cl.mToF.mScript);
-                    if (tn.mSeen) {
+                    if (tn.equals(original)) {
                         throw new RSInvalidStateException("Loops in group not allowed.");
                     }
-                    validateCycleRecurse(tn, depth + 1);
-                }
-            }
-        }
-
-        private void validateCycle() {
-            //android.util.Log.v("RSR", "validateCycle");
-
-            for (int ct=0; ct < mNodes.size(); ct++) {
-                for (int ct2=0; ct2 < mNodes.size(); ct2++) {
-                    mNodes.get(ct2).mSeen = false;
-                }
-                Node n = mNodes.get(ct);
-                if (n.mInputs.size() == 0) {
-                    validateCycleRecurse(n, 0);
+                    validateCycle(tn, original);
                 }
             }
         }
@@ -327,7 +311,7 @@ public final class ScriptGroup extends BaseObj {
 
             Node nf = findNode(from);
             if (nf == null) {
-                throw new RSInvalidStateException("From kernel not found.");
+                throw new RSInvalidStateException("From script not found.");
             }
 
             Node nt = findNode(to.mScript);
@@ -341,7 +325,7 @@ public final class ScriptGroup extends BaseObj {
             nf.mOutputs.add(cl);
             nt.mInputs.add(cl);
 
-            validateCycle();
+            validateCycle(nf, nf);
             return this;
         }
 
@@ -362,7 +346,7 @@ public final class ScriptGroup extends BaseObj {
 
             Node nf = findNode(from);
             if (nf == null) {
-                throw new RSInvalidStateException("From kernel not found.");
+                throw new RSInvalidStateException("From script not found.");
             }
 
             Node nt = findNode(to);
@@ -376,7 +360,7 @@ public final class ScriptGroup extends BaseObj {
             nf.mOutputs.add(cl);
             nt.mInputs.add(cl);
 
-            validateCycle();
+            validateCycle(nf, nf);
             return this;
         }
 
-- 
cgit v1.1