Fix [b7abf0d817]: ttk::treeview shows O(n^2) destruction time

1 files changed, 20 insertions, 3 deletions

diff --git a/generic/tkImage.c b/generic/tkImage.c
index 1f62ad4..1f026b6 100644
--- a/generic/tkImage.c
+++ b/generic/tkImage.c
@@ -41,6 +41,8 @@ typedef struct Image {
     ClientData widgetClientData;/* Argument to pass to changeProc. */
     struct Image *nextPtr;	/* Next in list of all image instances
 				 * associated with the same name. */
+    struct Image *prevPtr;	/* Previous in list of all image instances
+				 * associated with the same name. */
 } Image;
 
 /*
@@ -644,6 +646,10 @@ Tk_GetImage(
     imagePtr->changeProc = changeProc;
     imagePtr->widgetClientData = clientData;
     imagePtr->nextPtr = modelPtr->instancePtr;
+    if (imagePtr->nextPtr) {
+	imagePtr->nextPtr->prevPtr = imagePtr;
+    }
+    imagePtr->prevPtr = NULL;
     modelPtr->instancePtr = imagePtr;
     return (Tk_Image) imagePtr;
 
@@ -694,11 +700,22 @@ Tk_FreeImage(
     prevPtr = modelPtr->instancePtr;
     if (prevPtr == imagePtr) {
 	modelPtr->instancePtr = imagePtr->nextPtr;
+	if (modelPtr->instancePtr) {
+	    modelPtr->instancePtr->prevPtr = NULL;
+	}
     } else {
-	while (prevPtr->nextPtr != imagePtr) {
-	    prevPtr = prevPtr->nextPtr;
+	if (imagePtr->prevPtr) {
+	    imagePtr->prevPtr->nextPtr = imagePtr->nextPtr;
+	    if (imagePtr->nextPtr) {
+		imagePtr->nextPtr->prevPtr = NULL;
+	    }
+	}
+	if (imagePtr->nextPtr) {
+	    imagePtr->nextPtr->prevPtr = imagePtr->prevPtr;
+	    if (imagePtr->prevPtr) {
+		imagePtr->prevPtr->nextPtr = NULL;
+	    }
 	}
-	prevPtr->nextPtr = imagePtr->nextPtr;
     }
     ckfree(imagePtr);