diff options
| -rw-r--r-- | ChangeLog | 8 | ||||
| -rw-r--r-- | generic/tclParseExpr.c | 17 |
2 files changed, 19 insertions, 6 deletions
@@ -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++; |