Announce : CList performance patch



Previously, if you selected or deselected 40,000 or more rows in a gtk
application (e.g. gtktest), the application would take up to a minute to
perform the operation.

I fixed the problem by implementing an array (row_array) that mirrors
row_list, and then use the array to perform almost all the g_list_nth
operations. This means that existing applications that use row_list (read
only) should still work perfectly.

The attached file is a patch against the Win32 Gtk sources of 28 August.
It should apply cleanly to the current? sources, but if it does not, let
me know. Currently it only patches gtkclist.c and some work may still be
needed to fix gtkctree.c. If the patch makes it into the sources, I will
undertake to fix ctree, and also clean up clist a bit.

Nic Roets
nic "at" sig.co.za
diff -u -r /old/gtk+/gtk/gtkclist.c /src/gtk+/gtk/gtkclist.c
--- /old/gtk+/gtk/gtkclist.c	Tue Sep 21 16:03:30 1999
+++ /src/gtk+/gtk/gtkclist.c	Wed Sep 22 01:22:20 1999
@@ -926,6 +926,7 @@
   clist->row_height = 0;
   clist->row_list = NULL;
   clist->row_list_end = NULL;
+  clist->row_array = NULL;
 
   clist->columns = 0;
 
@@ -2170,7 +2171,7 @@
   if (column < 0 || column >= clist->columns)
     return -1;
 
-  clist_row = (g_list_nth (clist->row_list, row))->data;
+  clist_row = clist->row_array[row];
 
   return clist_row->cell[column].type;
 }
@@ -2191,7 +2192,7 @@
   if (column < 0 || column >= clist->columns)
     return;
 
-  clist_row = (g_list_nth (clist->row_list, row))->data;
+  clist_row = clist->row_array[row];
 
   /* if text is null, then the cell is empty */
   GTK_CLIST_CLASS_FW (clist)->set_cell_contents
@@ -2221,7 +2222,7 @@
   if (column < 0 || column >= clist->columns)
     return 0;
 
-  clist_row = (g_list_nth (clist->row_list, row))->data;
+  clist_row = clist->row_array[row];
 
   if (clist_row->cell[column].type != GTK_CELL_TEXT)
     return 0;
@@ -2249,7 +2250,7 @@
   if (column < 0 || column >= clist->columns)
     return;
 
-  clist_row = (g_list_nth (clist->row_list, row))->data;
+  clist_row = clist->row_array[row];
   
   gdk_pixmap_ref (pixmap);
   
@@ -2283,7 +2284,7 @@
   if (column < 0 || column >= clist->columns)
     return 0;
 
-  clist_row = (g_list_nth (clist->row_list, row))->data;
+  clist_row = clist->row_array[row];
 
   if (clist_row->cell[column].type != GTK_CELL_PIXMAP)
     return 0;
@@ -2317,7 +2318,7 @@
   if (column < 0 || column >= clist->columns)
     return;
 
-  clist_row = (g_list_nth (clist->row_list, row))->data;
+  clist_row = clist->row_array[row];
   
   gdk_pixmap_ref (pixmap);
   if (mask) gdk_pixmap_ref (mask);
@@ -2351,7 +2352,7 @@
   if (column < 0 || column >= clist->columns)
     return 0;
 
-  clist_row = (g_list_nth (clist->row_list, row))->data;
+  clist_row = clist->row_array[row];
 
   if (clist_row->cell[column].type != GTK_CELL_PIXTEXT)
     return 0;
@@ -2387,7 +2388,7 @@
   if (column < 0 || column >= clist->columns)
     return;
 
-  clist_row = (g_list_nth (clist->row_list, row))->data;
+  clist_row = clist->row_array[row];
 
   if (clist->column[column].auto_resize &&
       !GTK_CLIST_AUTO_RESIZE_BLOCKED(clist))
@@ -2639,6 +2640,8 @@
     {
       clist->row_list = g_list_append (clist->row_list, clist_row);
       clist->row_list_end = clist->row_list;
+      clist->row_array = malloc (sizeof (*clist->row_array));
+      *clist->row_array = clist_row;
     }
   else
     {
@@ -2677,7 +2680,12 @@
 					      clist_row))->next;
       else
 	clist->row_list = g_list_insert (clist->row_list, clist_row, row);
-
+      
+      clist->row_array = realloc (clist->row_array,
+        sizeof (*clist->row_array) * (clist->rows + 1));
+      memmove (clist->row_array + row + 1, clist->row_array + row,
+        sizeof (*clist->row_array) * (clist->rows - row));
+      clist->row_array[row] = clist_row;
     }
   clist->rows++;
 
@@ -2725,7 +2733,7 @@
   was_selected = 0;
 
   /* get the row we're going to delete */
-  list = g_list_nth (clist->row_list, row);
+  list = clist->row_array[row];
   g_assert (list != NULL);
   clist_row = list->data;
 
@@ -2746,6 +2754,11 @@
     clist->row_list_end = g_list_previous (list);
   g_list_remove (list, clist_row);
 
+  memmove (clist->row_array + row, clist->row_array + row + 1,
+    sizeof (*clist->row_array) * (clist->rows - row));
+  clist->row_array = realloc (clist->row_array,
+    sizeof (*clist->row_array) * clist->rows);
+
   /*if (clist->focus_row >=0 &&
       (row <= clist->focus_row || clist->focus_row >= clist->rows))
       clist->focus_row--;*/
@@ -2805,6 +2818,8 @@
   clist->row_list = NULL;
   clist->row_list_end = NULL;
   clist->rows = 0;
+  free (clist->row_array);
+  clist->row_array = NULL;
   for (list = free_list; list; list = list->next)
     row_delete (clist, GTK_CLIST_ROW (list));
   g_list_free (free_list);
@@ -2865,6 +2880,14 @@
     clist->row_list_end = clist->row_list_end->next;
   clist->rows++;
 
+  if (source_row < dest_row)
+    memmove (clist->row_array + source_row, clist->row_array + source_row + 1,
+      sizeof (*clist->row_array) * (dest_row - source_row - 1));
+  else
+    memmove (clist->row_array + dest_row + 1, clist->row_array + dest_row,
+      sizeof (*clist->row_array) * (source_row - dest_row - 1));
+  clist->row_array[dest_row] = clist_row;
+
   /* sync selection */
   if (source_row > dest_row)
     {
@@ -3010,7 +3033,7 @@
   if (row < 0 || row > (clist->rows - 1))
     return;
 
-  clist_row = (g_list_nth (clist->row_list, row))->data;
+  clist_row = clist->row_array[row];
   clist_row->data = data;
   clist_row->destroy = destroy;
 }
@@ -3027,7 +3050,7 @@
   if (row < 0 || row > (clist->rows - 1))
     return NULL;
 
-  clist_row = (g_list_nth (clist->row_list, row))->data;
+  clist_row = clist->row_array[row];
   return clist_row->data;
 }
 
@@ -3136,7 +3159,7 @@
   if (row < 0 || row >= clist->rows)
     return;
 
-  clist_row = (g_list_nth (clist->row_list, row))->data;
+  clist_row = clist->row_array[row];
 
   if (color)
     {
@@ -3166,7 +3189,7 @@
   if (row < 0 || row >= clist->rows)
     return;
 
-  clist_row = (g_list_nth (clist->row_list, row))->data;
+  clist_row = clist->row_array[row];
 
   if (color)
     {
@@ -3207,7 +3230,7 @@
   if (column < 0 || column >= clist->columns)
     return;
 
-  clist_row = (g_list_nth (clist->row_list, row))->data;
+  clist_row = clist->row_array[row];
 
   if (clist_row->cell[column].style == style)
     return;
@@ -3259,7 +3282,7 @@
   if (row < 0 || row >= clist->rows || column < 0 || column >= clist->columns)
     return NULL;
 
-  clist_row = (g_list_nth (clist->row_list, row))->data;
+  clist_row = clist->row_array[row];
 
   return clist_row->cell[column].style;
 }
@@ -3280,7 +3303,7 @@
   if (row < 0 || row >= clist->rows)
     return;
 
-  clist_row = (g_list_nth (clist->row_list, row))->data;
+  clist_row = clist->row_array[row];
 
   if (clist_row->style == style)
     return;
@@ -3342,7 +3365,7 @@
   if (row < 0 || row >= clist->rows)
     return NULL;
 
-  clist_row = (g_list_nth (clist->row_list, row))->data;
+  clist_row = clist->row_array[row];
 
   return clist_row->style;
 }
@@ -3369,7 +3392,7 @@
   if (row < 0 || row >= clist->rows)
     return;
 
-  clist_row = (g_list_nth (clist->row_list, row))->data;
+  clist_row = clist->row_array[row];
 
   if (selectable == clist_row->selectable)
     return;
@@ -3400,7 +3423,7 @@
   if (row < 0 || row >= clist->rows)
     return FALSE;
 
-  return GTK_CLIST_ROW (g_list_nth (clist->row_list, row))->selectable;
+  return clist->row_array[row]->selectable;
 }
 
 void
@@ -3507,7 +3530,7 @@
     case GTK_SELECTION_EXTENDED:
     case GTK_SELECTION_MULTIPLE:
     case GTK_SELECTION_SINGLE:
-      clist_row = g_list_nth (clist->row_list, row)->data;
+      clist_row = clist->row_array[row];
 
       if (!clist_row)
 	return;
@@ -3529,22 +3552,18 @@
 fake_toggle_row (GtkCList *clist,
 		 gint      row)
 {
-  GList *work;
-
-  work = g_list_nth (clist->row_list, row);
-
-  if (!work || !GTK_CLIST_ROW (work)->selectable)
+  if (row < 0 || row >= clist->rows || clist->row_array[row]->selectable)
     return;
   
-  if (GTK_CLIST_ROW (work)->state == GTK_STATE_NORMAL)
-    clist->anchor_state = GTK_CLIST_ROW (work)->state = GTK_STATE_SELECTED;
+  if (clist->row_array[row]->state == GTK_STATE_NORMAL)
+    clist->anchor_state = clist->row_array[row]->state = GTK_STATE_SELECTED;
   else
-    clist->anchor_state = GTK_CLIST_ROW (work)->state = GTK_STATE_NORMAL;
+    clist->anchor_state = clist->row_array[row]->state = GTK_STATE_NORMAL;
   
   if (CLIST_UNFROZEN (clist) &&
       gtk_clist_row_is_visible (clist, row) != GTK_VISIBILITY_NONE)
     GTK_CLIST_CLASS_FW (clist)->draw_row (clist, NULL, row,
-					  GTK_CLIST_ROW (work));
+					  clist->row_array[row]);
 }
 
 static void
@@ -3656,7 +3675,7 @@
       break;
     }
 
-  clist_row = (g_list_nth (clist->row_list, row))->data;
+  clist_row = clist->row_array[row];
 
   if (clist_row->state != GTK_STATE_NORMAL || !clist_row->selectable)
     return;
@@ -3691,7 +3710,7 @@
   if (row < 0 || row > (clist->rows - 1))
     return;
 
-  clist_row = (g_list_nth (clist->row_list, row))->data;
+  clist_row = clist->row_array[row];
 
   if (clist_row->state == GTK_STATE_SELECTED)
     {
@@ -3810,20 +3829,19 @@
 		   gint      row)
 {
   GList *list;
-  GList *work;
   gint i;
 
-  if (row >= 0 && (work = g_list_nth (clist->row_list, row)))
+  if (row >= 0 && row < clist->rows)
     {
-      if (GTK_CLIST_ROW (work)->state == GTK_STATE_NORMAL &&
-	  GTK_CLIST_ROW (work)->selectable)
+      if (clist->row_array[row]->state == GTK_STATE_NORMAL &&
+	  clist->row_array[row]->selectable)
 	{
-	  GTK_CLIST_ROW (work)->state = GTK_STATE_SELECTED;
+	  clist->row_array[row]->state = GTK_STATE_SELECTED;
 	  
 	  if (CLIST_UNFROZEN (clist) &&
 	      gtk_clist_row_is_visible (clist, row) != GTK_VISIBILITY_NONE)
 	    GTK_CLIST_CLASS_FW (clist)->draw_row (clist, NULL, row,
-						  GTK_CLIST_ROW (work));
+						  clist->row_array[row]);
 	}  
     }
 
@@ -3834,14 +3852,14 @@
   for (list = clist->undo_selection; list; list = list->next)
     {
       if ((i = GPOINTER_TO_INT (list->data)) == row ||
-	  !(work = g_list_nth (clist->row_list, i)))
+	  i < 0 || i >= clist->rows)
 	continue;
 
-      GTK_CLIST_ROW (work)->state = GTK_STATE_NORMAL;
+      clist->row_array[i]->state = GTK_STATE_NORMAL;
       if (CLIST_UNFROZEN (clist) &&
 	  gtk_clist_row_is_visible (clist, i) != GTK_VISIBILITY_NONE)
 	GTK_CLIST_CLASS_FW (clist)->draw_row (clist, NULL, i,
-					      GTK_CLIST_ROW (work));
+					      clist->row_array[i]);
     }
 }
 
@@ -3961,7 +3979,7 @@
 	  list = list->next;
 	  if (row < i || row > e)
 	    {
-	      clist_row = g_list_nth (clist->row_list, row)->data;
+	      clist_row = clist->row_array[row];
 	      if (clist_row->selectable)
 		{
 		  clist_row->state = GTK_STATE_SELECTED;
@@ -3977,15 +3995,14 @@
 
   if (clist->anchor < clist->drag_pos)
     {
-      for (list = g_list_nth (clist->row_list, i); i <= e;
-	   i++, list = list->next)
-	if (GTK_CLIST_ROW (list)->selectable)
+      for (; i <= e; i++)
+	if (clist->row_array[i]->selectable)
 	  {
 	    if (g_list_find (clist->selection, GINT_TO_POINTER(i)))
 	      {
-		if (GTK_CLIST_ROW (list)->state == GTK_STATE_NORMAL)
+		if (clist->row_array[i]->state == GTK_STATE_NORMAL)
 		  {
-		    GTK_CLIST_ROW (list)->state = GTK_STATE_SELECTED;
+		    clist->row_array[i]->state = GTK_STATE_SELECTED;
 		    gtk_signal_emit (GTK_OBJECT (clist),
 				     clist_signals[UNSELECT_ROW],
 				     i, -1, event);
@@ -3994,9 +4011,9 @@
 				      GINT_TO_POINTER (i));
 		  }
 	      }
-	    else if (GTK_CLIST_ROW (list)->state == GTK_STATE_SELECTED)
+	    else if (clist->row_array[i]->state == GTK_STATE_SELECTED)
 	      {
-		GTK_CLIST_ROW (list)->state = GTK_STATE_NORMAL;
+		clist->row_array[i]->state = GTK_STATE_NORMAL;
 		clist->undo_unselection =
 		  g_list_prepend (clist->undo_unselection,
 				  GINT_TO_POINTER (i));
@@ -4005,15 +4022,14 @@
     }
   else
     {
-      for (list = g_list_nth (clist->row_list, e); i <= e;
-	   e--, list = list->prev)
-	if (GTK_CLIST_ROW (list)->selectable)
+      for (; i <= e; e--)
+	if (clist->row_array[e]->selectable)
 	  {
 	    if (g_list_find (clist->selection, GINT_TO_POINTER(e)))
 	      {
-		if (GTK_CLIST_ROW (list)->state == GTK_STATE_NORMAL)
+		if (clist->row_array[e]->state == GTK_STATE_NORMAL)
 		  {
-		    GTK_CLIST_ROW (list)->state = GTK_STATE_SELECTED;
+		    clist->row_array[e]->state = GTK_STATE_SELECTED;
 		    gtk_signal_emit (GTK_OBJECT (clist),
 				     clist_signals[UNSELECT_ROW],
 				     e, -1, event);
@@ -4022,9 +4038,9 @@
 				      GINT_TO_POINTER (e));
 		  }
 	      }
-	    else if (GTK_CLIST_ROW (list)->state == GTK_STATE_SELECTED)
+	    else if (clist->row_array[e]->state == GTK_STATE_SELECTED)
 	      {
-		GTK_CLIST_ROW (list)->state = GTK_STATE_NORMAL;
+		clist->row_array[e]->state = GTK_STATE_NORMAL;
 		clist->undo_unselection =
 		  g_list_prepend (clist->undo_unselection,
 				  GINT_TO_POINTER (e));
@@ -4121,14 +4137,13 @@
   /* restore the elements between s1 and e1 */
   if (s1 >= 0)
     {
-      for (i = s1, list = g_list_nth (clist->row_list, i); i <= e1;
-	   i++, list = list->next)
-	if (GTK_CLIST_ROW (list)->selectable)
+      for (i = s1; i <= e1; i++)
+	if (clist->row_array[i]->selectable)
 	  {
 	    if (GTK_CLIST_CLASS_FW (clist)->selection_find (clist, i, list))
-	      GTK_CLIST_ROW (list)->state = GTK_STATE_SELECTED;
+	      clist->row_array[i]->state = GTK_STATE_SELECTED;
 	    else
-	      GTK_CLIST_ROW (list)->state = GTK_STATE_NORMAL;
+	      clist->row_array[i]->state = GTK_STATE_NORMAL;
 	  }
 
       top = ROW_TOP_YPIXEL (clist, clist->focus_row);
@@ -4159,11 +4174,10 @@
   /* extend the selection between s2 and e2 */
   if (s2 >= 0)
     {
-      for (i = s2, list = g_list_nth (clist->row_list, i); i <= e2;
-	   i++, list = list->next)
-	if (GTK_CLIST_ROW (list)->selectable &&
-	    GTK_CLIST_ROW (list)->state != clist->anchor_state)
-	  GTK_CLIST_ROW (list)->state = clist->anchor_state;
+      for (i = s2; i <= e2; i++)
+	if (clist->row_array[i]->selectable &&
+	    clist->row_array[i]->state != clist->anchor_state)
+	  clist->row_array[i]->state = clist->anchor_state;
 
       top = ROW_TOP_YPIXEL (clist, clist->focus_row);
 
@@ -5657,7 +5671,7 @@
   /* if the function is passed the pointer to the row instead of null,
    * it avoids this expensive lookup */
   if (!clist_row)
-    clist_row = (g_list_nth (clist->row_list, row))->data;
+    clist_row = clist->row_array[row];
 
   /* rectangle of the entire row */
   row_rectangle.x = 0;
@@ -7299,6 +7313,11 @@
    
   clist->row_list = gtk_clist_mergesort (clist, clist->row_list, clist->rows);
 
+  for (i = 0, list = clist->row_list; i < clist->rows; i++, list = list->next)
+    {
+      clist->row_array[i] = (GtkCList*) list->data;
+    }
+
   work = clist->selection;
 
   for (i = 0, list = clist->row_list; i < clist->rows; i++, list = list->next)
@@ -7572,7 +7591,7 @@
 		{
 		  GTK_CLIST_CLASS_FW (clist)->draw_drag_highlight
 		    (clist,
-		     g_list_nth (clist->row_list, dest_info->cell.row)->data,
+		     clist->row_array[dest_info->cell.row],
 		     dest_info->cell.row, dest_info->insert_pos);
 		  break;
 		}
@@ -7652,8 +7671,7 @@
 	    {
 	      if (dest_info->cell.row >= 0)
 		GTK_CLIST_CLASS_FW (clist)->draw_drag_highlight
-		  (clist, g_list_nth (clist->row_list,
-				      dest_info->cell.row)->data,
+		  (clist, clist->row_array[dest_info->cell.row],
 		   dest_info->cell.row, dest_info->insert_pos);
 
 	      dest_info->insert_pos  = new_info.insert_pos;
@@ -7661,8 +7679,7 @@
 	      dest_info->cell.column = new_info.cell.column;
 	      
 	      GTK_CLIST_CLASS_FW (clist)->draw_drag_highlight
-		(clist, g_list_nth (clist->row_list,
-				    dest_info->cell.row)->data,
+		(clist, clist->row_array[dest_info->cell.row],
 		 dest_info->cell.row, dest_info->insert_pos);
 
 	      gdk_drag_status (context, context->suggested_action, time);
diff -u -r /old/gtk+/gtk/gtkclist.h /src/gtk+/gtk/gtkclist.h
--- /old/gtk+/gtk/gtkclist.h	Tue Sep 21 16:03:30 1999
+++ /src/gtk+/gtk/gtkclist.h	Tue Sep 21 16:59:10 1999
@@ -236,6 +236,7 @@
   GtkSortType sort_type;
   GtkCListCompareFunc compare;
   gint sort_column;
+  GtkCListRow **row_array; /* Added by gtk@sig.co.za to improve performace */
 };
 
 struct _GtkCListClass


[Date Prev][Date Next]   [Thread Prev][Thread Next]   [Thread Index] [Date Index] [Author Index]