From 3ab5cea25b466b9f0a62a47b549593f0b9662551 Mon Sep 17 00:00:00 2001
From: dgp <dgp@users.sourceforge.net>
Date: Tue, 29 Aug 2006 19:04:56 +0000
Subject:         * 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.

---
 ChangeLog              |  8 ++++++++
 generic/tclParseExpr.c | 17 +++++++++++------
 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++;
-- 
cgit v0.12