diff options
| -rw-r--r-- | changes | 8 | ||||
| -rw-r--r-- | generic/tk.h | 7 | ||||
| -rw-r--r-- | generic/tkCanvas.c | 159 | ||||
| -rw-r--r-- | generic/tkCanvas.h | 4 | ||||
| -rw-r--r-- | tests/canvas.test | 36 |
5 files changed, 148 insertions, 66 deletions
@@ -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 "" +} {} |