* generic/tclParseExpr.c: Use the "parent" field of

        orphan ExprNodes to store the closure of left pointers.  This
        lets us avoid repeated re-scanning leftward for the left
        boundary of subexpressions, which in worst case led to near
        O(N^2) runtime.

2 files changed, 19 insertions, 6 deletions

diff --git a/ChangeLog b/ChangeLog
index 66d2f68..5f34332 100644
--- a/ChangeLog
+++ b/ChangeLog
@@ -1,3 +1,11 @@
+2006-08-29  Don Porter  <dgp@users.sourceforge.net>
+
+	* generic/tclParseExpr.c:	Use the "parent" field of
+	orphan ExprNodes to store the closure of left pointers.  This
+	lets us avoid repeated re-scanning leftward for the left
+	boundary of subexpressions, which in worst case led to near
+	O(N^2) runtime.
+
 2006-08-29  Joe Mistachkin  <joe@mistachkin.com>
 
 	* unix/tclUnixInit.c: Fixed the issue (typo) that was causing
diff --git a/generic/tclParseExpr.c b/generic/tclParseExpr.c
index 4a2ab8d..9dba5a6 100644
--- a/generic/tclParseExpr.c
+++ b/generic/tclParseExpr.c
@@ -12,10 +12,10 @@
  * See the file "license.terms" for information on usage and redistribution of
  * this file, and for a DISCLAIMER OF ALL WARRANTIES.
  *
- * RCS: @(#) $Id: tclParseExpr.c,v 1.40 2006/08/28 16:05:32 dgp Exp $
+ * RCS: @(#) $Id: tclParseExpr.c,v 1.41 2006/08/29 19:04:56 dgp Exp $
  */
 
-#define OLD_EXPR_PARSER 0
+#define OLD_EXPR_PARSER 1
 #if OLD_EXPR_PARSER
 
 #include "tclInt.h"
@@ -2470,9 +2470,14 @@ Tcl_ParseExpr(
 	    }
 
 	    while (1) {
-		otherPtr = lastOrphanPtr;
-		while (otherPtr->left >= 0) {
-		    otherPtr = nodes + otherPtr->left;
+
+		if (lastOrphanPtr->parent >= 0) {
+		    otherPtr = nodes + lastOrphanPtr->parent;
+		} else if (lastOrphanPtr->left >= 0) {
+		    Tcl_Panic("Tcl_ParseExpr: left closure programming error");
+		} else {
+		    lastOrphanPtr->parent = lastOrphanPtr - nodes;
+		    otherPtr = lastOrphanPtr;
 		}
 		otherPtr--;
 
@@ -2567,7 +2572,6 @@ Tcl_ParseExpr(
 
 	    /* Link orphan as left operand of new node */
 	    nodePtr->right = -1;
-	    nodePtr->parent = -1;
 
 	    if (scratch.numTokens >= scratch.tokensAvailable) {
 		TclExpandTokenArray(&scratch);
@@ -2581,6 +2585,7 @@ Tcl_ParseExpr(
 	    scratch.numTokens++;
 
 	    nodePtr->left = lastOrphanPtr - nodes;
+	    nodePtr->parent = lastOrphanPtr->parent;
 	    lastOrphanPtr->parent = nodePtr - nodes;
 	    lastOrphanPtr = nodePtr;
 	    nodesUsed++;