summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authordgp <dgp@users.sourceforge.net>2006-08-29 19:04:56 (GMT)
committerdgp <dgp@users.sourceforge.net>2006-08-29 19:04:56 (GMT)
commit3ab5cea25b466b9f0a62a47b549593f0b9662551 (patch)
tree5b3a89c0fa189b32a530cd97463af10357ce1a98
parent14399ffc4716be22d31ded0e4cc5c6f2d7235ce7 (diff)
downloadtcl-3ab5cea25b466b9f0a62a47b549593f0b9662551.zip
tcl-3ab5cea25b466b9f0a62a47b549593f0b9662551.tar.gz
tcl-3ab5cea25b466b9f0a62a47b549593f0b9662551.tar.bz2
* 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.
-rw-r--r--ChangeLog8
-rw-r--r--generic/tclParseExpr.c17
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++;