summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorrjohnson <rjohnson>1998-10-13 18:13:05 (GMT)
committerrjohnson <rjohnson>1998-10-13 18:13:05 (GMT)
commit66a2d0b81392599d07859d249372259daef2441c (patch)
tree8f7938e353656771307dd68a16d97c8b59b4e566
parent6b30648b424171905375ec916ab86186a3043dfc (diff)
downloadtk-66a2d0b81392599d07859d249372259daef2441c.zip
tk-66a2d0b81392599d07859d249372259daef2441c.tar.gz
tk-66a2d0b81392599d07859d249372259daef2441c.tar.bz2
Added performance improvement to canvas tag manipulation. This was
a submitted patch.
-rw-r--r--changes8
-rw-r--r--generic/tk.h7
-rw-r--r--generic/tkCanvas.c159
-rw-r--r--generic/tkCanvas.h4
-rw-r--r--tests/canvas.test36
5 files changed, 148 insertions, 66 deletions
diff --git a/changes b/changes
index 3f26b56..bd42a94 100644
--- a/changes
+++ b/changes
@@ -2,7 +2,7 @@ This file summarizes all changes made to Tk since version 1.0 was
released on March 13, 1991. Changes that aren't backward compatible
are marked specially.
-RCS: @(#) $Id: changes,v 1.22 1998/10/10 00:30:34 rjohnson Exp $
+RCS: @(#) $Id: changes,v 1.23 1998/10/13 18:13:05 rjohnson Exp $
3/16/91 (bug fix) Modified tkWindow.c to remove Tk's Tcl commands from
the interpreter when the main window is deleted (otherwise there will
@@ -4260,3 +4260,9 @@ Tcl. See the bind and event man pages for more details. The listbox
and text widgets' default bindings have been updated to understand
MouseWheel events. (RJ)
+10/12/98 (performance improvement) Added hash table to canvas widget
+that holds numeric ids for items. The hash table makes item lookup
+almost constant time which improves certain canvas operations
+(exspecially for canvases with large number items). Thanks to Mark
+Weissman <weissman@gte.com> and Jan Nijtmans <Jan.Nijtmans@wxs.nl>
+for submitting this improvement. (RJ)
diff --git a/generic/tk.h b/generic/tk.h
index de694ae..40c0754 100644
--- a/generic/tk.h
+++ b/generic/tk.h
@@ -12,7 +12,7 @@
* See the file "license.terms" for information on usage and redistribution
* of this file, and for a DISCLAIMER OF ALL WARRANTIES.
*
- * RCS: @(#) $Id: tk.h,v 1.14 1998/10/10 00:30:35 rjohnson Exp $
+ * RCS: @(#) $Id: tk.h,v 1.15 1998/10/13 18:13:06 rjohnson Exp $
*/
#ifndef _TK
@@ -670,10 +670,13 @@ typedef struct Tk_Item {
* pixel drawn in item. Item area
* includes x1 and y1 but not x2
* and y2. */
+ struct Tk_Item *prevPtr; /* Previous in display list of all
+ * items in this canvas. Later items
+ * in list are drawn just below earlier
+ * ones. */
int reserved1; /* This padding is for compatibility */
char *reserved2; /* with Jan Nijtmans dash patch */
int reserved3;
- char *reserved4;
/*
*------------------------------------------------------------------
diff --git a/generic/tkCanvas.c b/generic/tkCanvas.c
index 6574437..c095f7e 100644
--- a/generic/tkCanvas.c
+++ b/generic/tkCanvas.c
@@ -7,11 +7,12 @@
*
* Copyright (c) 1991-1994 The Regents of the University of California.
* Copyright (c) 1994-1995 Sun Microsystems, Inc.
+ * Copyright (c) 1998 by Scriptics Corporation.
*
* See the file "license.terms" for information on usage and redistribution
* of this file, and for a DISCLAIMER OF ALL WARRANTIES.
*
- * RCS: @(#) $Id: tkCanvas.c,v 1.2 1998/09/14 18:23:06 stanton Exp $
+ * RCS: @(#) $Id: tkCanvas.c,v 1.3 1998/10/13 18:13:06 rjohnson Exp $
*/
#include "default.h"
@@ -25,18 +26,19 @@
/*
* The structure defined below is used to keep track of a tag search
- * in progress. Only the "prevPtr" field should be accessed by anyone
- * other than StartTagSearch and NextItem.
+ * in progress. No field should be accessed by anyone other than
+ * StartTagSearch and NextItem.
*/
typedef struct TagSearch {
TkCanvas *canvasPtr; /* Canvas widget being searched. */
Tk_Uid tag; /* Tag to search for. 0 means return
* all items. */
- Tk_Item *prevPtr; /* Item just before last one found (or NULL
- * if last one found was first in the item
- * list of canvasPtr). */
Tk_Item *currentPtr; /* Pointer to last item returned. */
+ Tk_Item *lastPtr; /* The item right before the currentPtr
+ * is tracked so if the currentPtr is
+ * deleted we don't have to start from the
+ * beginning. */
int searchOver; /* Non-zero means NextItem should always
* return NULL. */
} TagSearch;
@@ -353,7 +355,8 @@ Tk_CanvasCmd(clientData, interp, argc, argv)
canvasPtr->flags = 0;
canvasPtr->nextId = 1;
canvasPtr->psInfoPtr = NULL;
-
+ Tcl_InitHashTable(&canvasPtr->idTable, TCL_ONE_WORD_KEYS);
+
Tk_SetClass(canvasPtr->tkwin, "Canvas");
TkSetClassProcs(canvasPtr->tkwin, &canvasClass, (ClientData) canvasPtr);
Tk_CreateEventHandler(canvasPtr->tkwin,
@@ -494,18 +497,18 @@ CanvasWidgetCmd(clientData, interp, argc, argv)
if (isdigit(UCHAR(argv[2][0]))) {
int id;
char *end;
+ Tcl_HashEntry *entryPtr;
id = strtoul(argv[2], &end, 0);
if (*end != 0) {
goto bindByTag;
}
- for (itemPtr = canvasPtr->firstItemPtr; itemPtr != NULL;
- itemPtr = itemPtr->nextPtr) {
- if (itemPtr->id == id) {
- object = (ClientData) itemPtr;
- break;
- }
+ entryPtr = Tcl_FindHashEntry(&canvasPtr->idTable, (char *) id);
+ if (entryPtr != NULL) {
+ itemPtr = (Tk_Item *) Tcl_GetHashValue(entryPtr);
+ object = (ClientData) itemPtr;
}
+
if (object == 0) {
Tcl_AppendResult(interp, "item \"", argv[2],
"\" doesn't exist", (char *) NULL);
@@ -664,7 +667,9 @@ CanvasWidgetCmd(clientData, interp, argc, argv)
Tk_ItemType *typePtr;
Tk_ItemType *matchPtr = NULL;
Tk_Item *itemPtr;
-
+ int isNew = 0;
+ Tcl_HashEntry *entryPtr;
+
if (argc < 3) {
Tcl_AppendResult(interp, "wrong # args: should be \"",
argv[0], " create type ?arg arg ...?\"", (char *) NULL);
@@ -702,6 +707,10 @@ CanvasWidgetCmd(clientData, interp, argc, argv)
goto error;
}
itemPtr->nextPtr = NULL;
+ entryPtr = Tcl_CreateHashEntry(&canvasPtr->idTable,
+ (char *) itemPtr->id, &isNew);
+ Tcl_SetHashValue(entryPtr, itemPtr);
+ itemPtr->prevPtr = canvasPtr->lastItemPtr;
canvasPtr->hotPtr = itemPtr;
canvasPtr->hotPrevPtr = canvasPtr->lastItemPtr;
if (canvasPtr->lastItemPtr == NULL) {
@@ -760,6 +769,7 @@ CanvasWidgetCmd(clientData, interp, argc, argv)
} else if ((c == 'd') && (strncmp(argv[1], "delete", length) == 0)
&& (length >= 2)) {
int i;
+ Tcl_HashEntry *entryPtr;
for (i = 2; i < argc; i++) {
for (itemPtr = StartTagSearch(canvasPtr, argv[i], &search);
@@ -775,16 +785,23 @@ CanvasWidgetCmd(clientData, interp, argc, argv)
if (itemPtr->tagPtr != itemPtr->staticTagSpace) {
ckfree((char *) itemPtr->tagPtr);
}
- if (search.prevPtr == NULL) {
+ entryPtr = Tcl_FindHashEntry(&canvasPtr->idTable,
+ (char *) itemPtr->id);
+ Tcl_DeleteHashEntry(entryPtr);
+ if (itemPtr->nextPtr != NULL) {
+ itemPtr->nextPtr->prevPtr = itemPtr->prevPtr;
+ }
+ if (itemPtr->prevPtr != NULL) {
+ itemPtr->prevPtr->nextPtr = itemPtr->nextPtr;
+ }
+ if (canvasPtr->firstItemPtr == itemPtr) {
canvasPtr->firstItemPtr = itemPtr->nextPtr;
if (canvasPtr->firstItemPtr == NULL) {
canvasPtr->lastItemPtr = NULL;
}
- } else {
- search.prevPtr->nextPtr = itemPtr->nextPtr;
}
if (canvasPtr->lastItemPtr == itemPtr) {
- canvasPtr->lastItemPtr = search.prevPtr;
+ canvasPtr->lastItemPtr = itemPtr->prevPtr;
}
ckfree((char *) itemPtr);
if (itemPtr == canvasPtr->currentItemPtr) {
@@ -1027,7 +1044,7 @@ CanvasWidgetCmd(clientData, interp, argc, argv)
}
}
} else if ((c == 'l') && (strncmp(argv[1], "lower", length) == 0)) {
- Tk_Item *prevPtr;
+ Tk_Item *itemPtr;
if ((argc != 3) && (argc != 4)) {
Tcl_AppendResult(interp, "wrong # args: should be \"",
@@ -1042,18 +1059,17 @@ CanvasWidgetCmd(clientData, interp, argc, argv)
*/
if (argc == 3) {
- prevPtr = NULL;
+ itemPtr = NULL;
} else {
- prevPtr = StartTagSearch(canvasPtr, argv[3], &search);
- if (prevPtr != NULL) {
- prevPtr = search.prevPtr;
- } else {
+ itemPtr = StartTagSearch(canvasPtr, argv[3], &search);
+ if (itemPtr == NULL) {
Tcl_AppendResult(interp, "tag \"", argv[3],
"\" doesn't match any items", (char *) NULL);
goto error;
}
+ itemPtr = itemPtr->prevPtr;
}
- RelinkItems(canvasPtr, argv[2], prevPtr);
+ RelinkItems(canvasPtr, argv[2], itemPtr);
} else if ((c == 'm') && (strncmp(argv[1], "move", length) == 0)) {
double xAmount, yAmount;
@@ -1434,6 +1450,7 @@ DestroyCanvas(memPtr)
* stuff.
*/
+ Tcl_DeleteHashTable(&canvasPtr->idTable);
if (canvasPtr->pixmapGC != None) {
Tk_FreeGC(canvasPtr->display, canvasPtr->pixmapGC);
}
@@ -2162,7 +2179,7 @@ StartTagSearch(canvasPtr, tag, searchPtr)
* will be initialized here. */
{
int id;
- Tk_Item *itemPtr, *prevPtr;
+ Tk_Item *itemPtr, *lastPtr;
Tk_Uid *tagPtr;
Tk_Uid uid;
int count;
@@ -2183,27 +2200,28 @@ StartTagSearch(canvasPtr, tag, searchPtr)
if (isdigit(UCHAR(*tag))) {
char *end;
-
+ Tcl_HashEntry *entryPtr;
+
numIdSearches++;
id = strtoul(tag, &end, 0);
if (*end == 0) {
itemPtr = canvasPtr->hotPtr;
- prevPtr = canvasPtr->hotPrevPtr;
- if ((itemPtr == NULL) || (itemPtr->id != id) || (prevPtr == NULL)
- || (prevPtr->nextPtr != itemPtr)) {
+ lastPtr = canvasPtr->hotPrevPtr;
+ if ((itemPtr == NULL) || (itemPtr->id != id) || (lastPtr == NULL)
+ || (lastPtr->nextPtr != itemPtr)) {
numSlowSearches++;
- for (prevPtr = NULL, itemPtr = canvasPtr->firstItemPtr;
- itemPtr != NULL;
- prevPtr = itemPtr, itemPtr = itemPtr->nextPtr) {
- if (itemPtr->id == id) {
- break;
- }
+ entryPtr = Tcl_FindHashEntry(&canvasPtr->idTable, (char *) id);
+ if (entryPtr != NULL) {
+ itemPtr = (Tk_Item *)Tcl_GetHashValue(entryPtr);
+ lastPtr = itemPtr->prevPtr;
+ } else {
+ lastPtr = itemPtr = NULL;
}
}
- searchPtr->prevPtr = prevPtr;
+ searchPtr->lastPtr = lastPtr;
searchPtr->searchOver = 1;
canvasPtr->hotPtr = itemPtr;
- canvasPtr->hotPrevPtr = prevPtr;
+ canvasPtr->hotPrevPtr = lastPtr;
return itemPtr;
}
}
@@ -2216,7 +2234,7 @@ StartTagSearch(canvasPtr, tag, searchPtr)
*/
searchPtr->tag = NULL;
- searchPtr->prevPtr = NULL;
+ searchPtr->lastPtr = NULL;
searchPtr->currentPtr = canvasPtr->firstItemPtr;
return canvasPtr->firstItemPtr;
}
@@ -2225,18 +2243,18 @@ StartTagSearch(canvasPtr, tag, searchPtr)
* None of the above. Search for an item with a matching tag.
*/
- for (prevPtr = NULL, itemPtr = canvasPtr->firstItemPtr; itemPtr != NULL;
- prevPtr = itemPtr, itemPtr = itemPtr->nextPtr) {
+ for (lastPtr = NULL, itemPtr = canvasPtr->firstItemPtr; itemPtr != NULL;
+ lastPtr = itemPtr, itemPtr = itemPtr->nextPtr) {
for (tagPtr = itemPtr->tagPtr, count = itemPtr->numTags;
count > 0; tagPtr++, count--) {
if (*tagPtr == uid) {
- searchPtr->prevPtr = prevPtr;
+ searchPtr->lastPtr = lastPtr;
searchPtr->currentPtr = itemPtr;
return itemPtr;
}
}
}
- searchPtr->prevPtr = prevPtr;
+ searchPtr->lastPtr = lastPtr;
searchPtr->searchOver = 1;
return NULL;
}
@@ -2267,7 +2285,7 @@ NextItem(searchPtr)
TagSearch *searchPtr; /* Record describing search in
* progress. */
{
- Tk_Item *itemPtr, *prevPtr;
+ Tk_Item *itemPtr, *lastPtr;
int count;
Tk_Uid uid;
Tk_Uid *tagPtr;
@@ -2277,11 +2295,11 @@ NextItem(searchPtr)
* one to return), and return if there are no items left.
*/
- prevPtr = searchPtr->prevPtr;
- if (prevPtr == NULL) {
+ lastPtr = searchPtr->lastPtr;
+ if (lastPtr == NULL) {
itemPtr = searchPtr->canvasPtr->firstItemPtr;
} else {
- itemPtr = prevPtr->nextPtr;
+ itemPtr = lastPtr->nextPtr;
}
if ((itemPtr == NULL) || (searchPtr->searchOver)) {
searchPtr->searchOver = 1;
@@ -2291,12 +2309,12 @@ NextItem(searchPtr)
/*
* The structure of the list has changed. Probably the
* previously-returned item was removed from the list.
- * In this case, don't advance prevPtr; just return
+ * In this case, don't advance lastPtr; just return
* its new successor (i.e. do nothing here).
*/
} else {
- prevPtr = itemPtr;
- itemPtr = prevPtr->nextPtr;
+ lastPtr = itemPtr;
+ itemPtr = lastPtr->nextPtr;
}
/*
@@ -2305,7 +2323,7 @@ NextItem(searchPtr)
uid = searchPtr->tag;
if (uid == NULL) {
- searchPtr->prevPtr = prevPtr;
+ searchPtr->lastPtr = lastPtr;
searchPtr->currentPtr = itemPtr;
return itemPtr;
}
@@ -2314,17 +2332,17 @@ NextItem(searchPtr)
* Look for an item with a particular tag.
*/
- for ( ; itemPtr != NULL; prevPtr = itemPtr, itemPtr = itemPtr->nextPtr) {
+ for ( ; itemPtr != NULL; lastPtr = itemPtr, itemPtr = itemPtr->nextPtr) {
for (tagPtr = itemPtr->tagPtr, count = itemPtr->numTags;
count > 0; tagPtr++, count--) {
if (*tagPtr == uid) {
- searchPtr->prevPtr = prevPtr;
+ searchPtr->lastPtr = lastPtr;
searchPtr->currentPtr = itemPtr;
return itemPtr;
}
}
}
- searchPtr->prevPtr = prevPtr;
+ searchPtr->lastPtr = lastPtr;
searchPtr->searchOver = 1;
return NULL;
}
@@ -2493,14 +2511,16 @@ FindItems(interp, canvasPtr, argc, argv, newTag, cmdName, option)
DoItem(interp, itemPtr, uid);
}
} else if ((c == 'b') && (strncmp(argv[0], "below", length) == 0)) {
+ Tk_Item *itemPtr;
+
if (argc != 2) {
Tcl_AppendResult(interp, "wrong # args: should be \"",
cmdName, option, " below tagOrId", (char *) NULL);
return TCL_ERROR;
}
- (void) StartTagSearch(canvasPtr, argv[1], &search);
- if (search.prevPtr != NULL) {
- DoItem(interp, search.prevPtr, uid);
+ itemPtr = StartTagSearch(canvasPtr, argv[1], &search);
+ if (itemPtr->prevPtr != NULL) {
+ DoItem(interp, itemPtr->prevPtr, uid);
}
} else if ((c == 'c') && (strncmp(argv[0], "closest", length) == 0)) {
double closestDist;
@@ -2773,19 +2793,27 @@ RelinkItems(canvasPtr, tag, prevPtr)
* moved! Switch to insert after its predecessor.
*/
- prevPtr = search.prevPtr;
+ prevPtr = prevPtr->prevPtr;
}
- if (search.prevPtr == NULL) {
+ if (itemPtr->prevPtr == NULL) {
+ if (itemPtr->nextPtr != NULL) {
+ itemPtr->nextPtr->prevPtr = NULL;
+ }
canvasPtr->firstItemPtr = itemPtr->nextPtr;
} else {
- search.prevPtr->nextPtr = itemPtr->nextPtr;
+ if (itemPtr->nextPtr != NULL) {
+ itemPtr->nextPtr->prevPtr = itemPtr->prevPtr;
+ }
+ itemPtr->prevPtr->nextPtr = itemPtr->nextPtr;
}
if (canvasPtr->lastItemPtr == itemPtr) {
- canvasPtr->lastItemPtr = search.prevPtr;
+ canvasPtr->lastItemPtr = itemPtr->prevPtr;
}
if (firstMovePtr == NULL) {
+ itemPtr->prevPtr = NULL;
firstMovePtr = itemPtr;
} else {
+ itemPtr->prevPtr = lastMovePtr;
lastMovePtr->nextPtr = itemPtr;
}
lastMovePtr = itemPtr;
@@ -2803,10 +2831,19 @@ RelinkItems(canvasPtr, tag, prevPtr)
return;
}
if (prevPtr == NULL) {
+ if (canvasPtr->firstItemPtr != NULL) {
+ canvasPtr->firstItemPtr->prevPtr = lastMovePtr;
+ }
lastMovePtr->nextPtr = canvasPtr->firstItemPtr;
canvasPtr->firstItemPtr = firstMovePtr;
} else {
+ if (prevPtr->nextPtr != NULL) {
+ prevPtr->nextPtr->prevPtr = lastMovePtr;
+ }
lastMovePtr->nextPtr = prevPtr->nextPtr;
+ if (firstMovePtr != NULL) {
+ firstMovePtr->prevPtr = prevPtr;
+ }
prevPtr->nextPtr = firstMovePtr;
}
if (canvasPtr->lastItemPtr == prevPtr) {
diff --git a/generic/tkCanvas.h b/generic/tkCanvas.h
index a96fa6b..9dbcd0f 100644
--- a/generic/tkCanvas.h
+++ b/generic/tkCanvas.h
@@ -6,11 +6,12 @@
*
* Copyright (c) 1991-1994 The Regents of the University of California.
* Copyright (c) 1994-1995 Sun Microsystems, Inc.
+ * Copyright (c) 1998 by Scriptics Corporation.
*
* See the file "license.terms" for information on usage and redistribution
* of this file, and for a DISCLAIMER OF ALL WARRANTIES.
*
- * RCS: @(#) $Id: tkCanvas.h,v 1.2 1998/09/14 18:23:07 stanton Exp $
+ * RCS: @(#) $Id: tkCanvas.h,v 1.3 1998/10/13 18:13:06 rjohnson Exp $
*/
#ifndef _TKCANVAS
@@ -208,6 +209,7 @@ typedef struct TkCanvas {
* Postscript for the canvas. NULL means
* no Postscript is currently being
* generated. */
+ Tcl_HashTable idTable; /* Table of integer indices. */
} TkCanvas;
/*
diff --git a/tests/canvas.test b/tests/canvas.test
index 7914668..c37a36a 100644
--- a/tests/canvas.test
+++ b/tests/canvas.test
@@ -3,11 +3,12 @@
# standard fashion for Tcl tests.
#
# Copyright (c) 1995-1996 Sun Microsystems, Inc.
+# Copyright (c) 1998 by Scriptics Corporation.
#
# See the file "license.terms" for information on usage and redistribution
# of this file, and for a DISCLAIMER OF ALL WARRANTIES.
#
-# RCS: @(#) $Id: canvas.test,v 1.3 1998/09/14 18:23:44 stanton Exp $
+# RCS: @(#) $Id: canvas.test,v 1.4 1998/10/13 18:13:07 rjohnson Exp $
if {[info procs test] != "test"} {
source defs
@@ -202,3 +203,36 @@ test canvas-8.1 {canvas arc bbox} {
set pieBox [.c bbox arc3]
list $arcBox $coordBox $pieBox
} {{48 21 100 94} {248 21 300 94} {398 21 500 112}}
+test canvas-9.1 {canvas id creation and deletion} {
+ # With Tk 8.0.4 the ids are now stored in a hash table. You
+ # can use this test as a performance test with older versions
+ # by changing the value of size.
+ set size 15
+
+ catch {destroy .c}
+ set c [canvas .c]
+ for {set i 0} {$i < $size} {incr i} {
+ set x [expr {-10 + 3*$i}]
+ for {set j 0; set y -10} {$j < 10} {incr j; incr y 3} {
+ $c create rect ${x}c ${y}c [expr $x+2]c [expr $y+2]c \
+ -outline black -fill blue -tags rect
+ $c create text [expr $x+1]c [expr $y+1]c -text "$i,$j" \
+ -anchor center -tags text
+ }
+ }
+
+ # The actual bench mark - this code also exercises all the hash
+ # table changes.
+
+ set time [lindex [time {
+ foreach id [$c find withtag all] {
+ $c lower $id
+ $c raise $id
+ $c find withtag $id
+ $c bind <Return> $id {}
+ $c delete $id
+ }
+ }] 0]
+
+ set x ""
+} {}