summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
-rw-r--r--ChangeLog7
-rw-r--r--generic/ttk/ttkTreeview.c40
2 files changed, 37 insertions, 10 deletions
diff --git a/ChangeLog b/ChangeLog
index 937d10a..67e2698 100644
--- a/ChangeLog
+++ b/ChangeLog
@@ -1,3 +1,10 @@
+2010-02-20 Joe English <jenglish@users.sourceforge.net>
+
+ * generic/ttk/ttkTreeview.c: Cache the result of the
+ last call to EndPosition() to avoid quadratic-time behavior
+ in the common cases where the treeview is populated
+ in depth-first or breadth-first order.
+
2010-02-19 Jan Nijtmans <nijtmans@users.sf.net>
* win/tkWinColor.c: remove unused "dataKey" variable
diff --git a/generic/ttk/ttkTreeview.c b/generic/ttk/ttkTreeview.c
index 7fbe6c8..a1380ba 100644
--- a/generic/ttk/ttkTreeview.c
+++ b/generic/ttk/ttkTreeview.c
@@ -1,4 +1,4 @@
-/* $Id: ttkTreeview.c,v 1.36 2010/02/05 21:33:14 jenglish Exp $
+/* $Id: ttkTreeview.c,v 1.37 2010/02/20 21:30:37 jenglish Exp $
* Copyright (c) 2004, Joe English
*
* ttk::treeview widget implementation.
@@ -392,6 +392,7 @@ typedef struct {
TreeColumn *columns; /* Array of column options for data columns */
TreeItem *focus; /* Current focus item */
+ TreeItem *endPtr; /* See EndPosition() */
/* Widget options:
*/
@@ -1031,7 +1032,7 @@ static void TreeviewInitialize(Tcl_Interp *interp, void *recordPtr)
Tcl_InitHashTable(&tv->tree.items, TCL_STRING_KEYS);
tv->tree.serial = 0;
- tv->tree.focus = 0;
+ tv->tree.focus = tv->tree.endPtr = 0;
/* Create root item "":
*/
@@ -1874,16 +1875,33 @@ static TreeItem *InsertPosition(TreeItem *parent, int index)
/* + EndPosition --
* Locate the last child of the specified node.
+ *
+ * To avoid quadratic-time behavior in the common cases
+ * where the treeview is populated in breadth-first or
+ * depth-first order using [$tv insert $parent end ...],
+ * we cache the result from the last call to EndPosition()
+ * and start the search from there on a cache hit.
+ *
*/
-static TreeItem *EndPosition(TreeItem *parent)
+static TreeItem *EndPosition(Treeview *tv, TreeItem *parent)
{
- TreeItem *sibling = parent->children;
- if (sibling) {
- while (sibling->next) {
- sibling = sibling->next;
+ TreeItem *endPtr = tv->tree.endPtr;
+
+ while (endPtr && endPtr->parent != parent) {
+ endPtr = endPtr->parent;
+ }
+ if (!endPtr) {
+ endPtr = parent->children;
+ }
+
+ if (endPtr) {
+ while (endPtr->next) {
+ endPtr = endPtr->next;
}
+ tv->tree.endPtr = endPtr;
}
- return sibling;
+
+ return endPtr;
}
/* + AncestryCheck --
@@ -2556,7 +2574,7 @@ static int TreeviewInsertCommand(
/* Locate previous sibling based on $index:
*/
if (!strcmp(Tcl_GetString(objv[3]), "end")) {
- sibling = EndPosition(parent);
+ sibling = EndPosition(tv, parent);
} else {
int index;
if (Tcl_GetIntFromObj(interp, objv[3], &index) != TCL_OK)
@@ -2696,6 +2714,8 @@ static int TreeviewDeleteCommand(
TreeItem *next = delq->next;
if (tv->tree.focus == delq)
tv->tree.focus = 0;
+ if (tv->tree.endPtr == delq)
+ tv->tree.endPtr = 0;
FreeItem(delq);
delq = next;
}
@@ -2728,7 +2748,7 @@ static int TreeviewMoveCommand(
/* Locate previous sibling based on $index:
*/
if (!strcmp(Tcl_GetString(objv[4]), "end")) {
- sibling = EndPosition(parent);
+ sibling = EndPosition(tv, parent);
} else {
TreeItem *p;
int index;