summaryrefslogtreecommitdiffstats
path: root/generic
diff options
context:
space:
mode:
authorjenglish <jenglish@flightlab.com>2010-02-20 21:30:37 (GMT)
committerjenglish <jenglish@flightlab.com>2010-02-20 21:30:37 (GMT)
commit9ee03b593e2411cc2c5404b827ecdde22d4d34b4 (patch)
tree283b3006866c2735ac132a532fc0a13e01fec012 /generic
parent93f9e81c61f96535d7370311ef29f4c63c4f13e8 (diff)
downloadtk-9ee03b593e2411cc2c5404b827ecdde22d4d34b4.zip
tk-9ee03b593e2411cc2c5404b827ecdde22d4d34b4.tar.gz
tk-9ee03b593e2411cc2c5404b827ecdde22d4d34b4.tar.bz2
ttk::treeview: 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. (Translation for LM: that means "3X faster!")
Diffstat (limited to 'generic')
-rw-r--r--generic/ttk/ttkTreeview.c40
1 files changed, 30 insertions, 10 deletions
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;