Pango O(n^2) fix

[Alex Larsson <alexl redhat com>]

This patch fixes the O(n^2) behaviour while breaking long lines in 
pango-layout. For normal cases it does not matter much, but for very long 
lines it can be a 5 times speedup.

/ Alex

Index: pango-layout.c
===================================================================
RCS file: /cvs/gnome/pango/pango/pango-layout.c,v
retrieving revision 1.75
diff -u -p -r1.75 pango-layout.c
--- pango-layout.c	2001/09/24 23:50:09	1.75
+++ pango-layout.c	2001/09/25 23:35:25
@@ -2196,16 +2196,52 @@ imposed_extents (gint              n_cha
  * Line Breaking *
  *****************/
 
+static void shape_tab (PangoLayoutLine  *line,
+		       PangoGlyphString *glyphs);
+
+typedef struct _ItemState ItemState;
+
+struct _ItemState
+{
+  PangoItem *item;
+  PangoGlyphString *glyphs;
+  PangoGlyphUnit  *log_widths;
+  int log_widths_offset;
+  gboolean broke_line;
+};
+
 static void
-insert_run (PangoLayoutLine *line, PangoItem *item, PangoGlyphString *glyphs)
+insert_run (PangoLayoutLine *line, ItemState *state,
+	    const char *text, PangoItem *run_item, gboolean last_run)
 {
   PangoLayoutRun *run = g_new (PangoLayoutRun, 1);
 
-  run->item = item;
-  run->glyphs = glyphs;
+  run->item = run_item;
+
+  if (last_run && !state->broke_line)
+    run->glyphs = state->glyphs;
+  else
+    {
+      run->glyphs = pango_glyph_string_new ();
+      
+      if (text[run_item->offset] == '\t')
+	shape_tab (line, run->glyphs);
+      else
+	pango_shape (text + run_item->offset, run_item->length, &run_item->analysis, run->glyphs);
+    }
 
+  if (last_run)
+    {
+      state->item = NULL;
+      if (state->broke_line)
+	pango_glyph_string_free (state->glyphs);
+      state->glyphs = NULL;
+      g_free (state->log_widths);
+    }
+
+  
   line->runs = g_slist_prepend (line->runs, run);
-  line->length += item->length;
+  line->length += run_item->length;
 }
 
 static void
@@ -2473,40 +2509,66 @@ process_item (PangoLayout     *layout,
 	      int              start_offset,
 	      gboolean         no_break_at_start,
 	      gboolean         no_break_at_end,
+	      ItemState       *state,
 	      int             *remaining_width)
 {
-  PangoGlyphString *glyphs = pango_glyph_string_new ();
   PangoRectangle shape_ink;
   PangoRectangle shape_logical;
   gboolean shape_set;
   int width;
   int length;
   int i;
+  gboolean processing_new_item = FALSE;
 
-  pango_layout_get_item_properties (item, NULL, NULL,
-                                    &shape_ink, &shape_logical, &shape_set);
+  if (!state->item)
+    {
+      state->glyphs = pango_glyph_string_new ();
+      
+      pango_layout_get_item_properties (item, NULL, NULL,
+					&shape_ink,
+					&shape_logical,
+					&shape_set);
 
-  if (shape_set)
-    imposed_shape (item->num_chars, &shape_ink, &shape_logical, glyphs);
-  else if (text[item->offset] == '\t')
-    shape_tab (line, glyphs);
-  else
-    pango_shape (text + item->offset, item->length, &item->analysis, glyphs);
+      if (shape_set)
+	imposed_shape (item->num_chars, &shape_ink, &shape_logical, state->glyphs);
+      else if (text[item->offset] == '\t')
+	shape_tab (line, state->glyphs);
+      else
+	pango_shape (text + item->offset, item->length, &item->analysis, state->glyphs);
+
+      state->log_widths = NULL;
+      state->log_widths_offset = 0;
+      state->broke_line = FALSE;
+      state->item = item;
 
+      processing_new_item = TRUE;
+    }
+  
+  g_assert (state->item == item);
+  
   if (*remaining_width < 0)	/* Wrapping off */
     {
-      insert_run (line, item, glyphs);
+      insert_run (line, state, text, item, TRUE);
+
       return BREAK_ALL_FIT;
     }
-
-  width =0;
-  for (i=0; i < glyphs->num_glyphs; i++)
-    width += glyphs->glyphs[i].geometry.width;
 
+  width = 0;
+  if (processing_new_item)
+    {
+      for (i = 0; i < state->glyphs->num_glyphs; i++)
+	width += state->glyphs->glyphs[i].geometry.width;
+    }
+  else
+    {
+      for (i = 0; i < item->num_chars; i++)
+	width += state->log_widths[state->log_widths_offset + i];
+    }
+  
   if (width <= *remaining_width && !no_break_at_end)
     {
       *remaining_width -= width;
-      insert_run (line, item, glyphs);
+      insert_run (line, state, text, item, TRUE);
 
       return BREAK_ALL_FIT;
     }
@@ -2515,14 +2577,20 @@ process_item (PangoLayout     *layout,
       int num_chars = item->num_chars;
       int break_num_chars = num_chars;
       int break_width = width;
-      PangoGlyphUnit *log_widths = g_new (PangoGlyphUnit, item->num_chars);
-      pango_glyph_string_get_logical_widths (glyphs, text + item->offset, item->length, item->analysis.level, log_widths);
+
+      if (processing_new_item)
+	{
+	  state->log_widths = g_new (PangoGlyphUnit, item->num_chars);
+	  pango_glyph_string_get_logical_widths (state->glyphs,
+						 text + item->offset, item->length, item->analysis.level,
+						 state->log_widths);
+	}
       
       /* Shorten the item by one line break
        */
       while (--num_chars > 0)
 	{
-	  width -= log_widths[num_chars];
+	  width -= (state->log_widths)[state->log_widths_offset + num_chars];
 	  
 	  if (can_break_at (layout, start_offset + num_chars))
 	    {
@@ -2533,8 +2601,6 @@ process_item (PangoLayout     *layout,
 		break;
 	    }
 	}
-
-      g_free (log_widths);
       
       if (no_break_at_start || break_width <= *remaining_width)	/* Succesfully broke the item */
 	{
@@ -2542,8 +2608,8 @@ process_item (PangoLayout     *layout,
 	  
 	  if (break_num_chars == item->num_chars)
 	    {
-	      insert_run (line, item, glyphs);
-	      
+	      insert_run (line, state, text, item, TRUE);
+
 	      return BREAK_ALL_FIT;
 	    }
 	  else
@@ -2554,19 +2620,24 @@ process_item (PangoLayout     *layout,
 
               new_item = pango_item_split (item, length, break_num_chars);
 	      
-	      if (shape_set)
-		imposed_shape (item->num_chars, &shape_ink, &shape_logical, glyphs);
-	      else
-		pango_shape (text + new_item->offset, new_item->length, &new_item->analysis, glyphs);
-	      
-	      insert_run (line, new_item, glyphs);
-	      
+	      state->broke_line = TRUE;
+	      insert_run (line, state, text, new_item, FALSE);
+
+	      state->log_widths_offset += break_num_chars;
+
+	      /* Shaped items should never be broken */
+	      g_assert (!shape_set);
+
 	      return BREAK_SOME_FIT;
 	    }
 	}
       else
 	{
-	  pango_glyph_string_free (glyphs);
+	  state->item = NULL;
+	  pango_glyph_string_free (state->glyphs);
+	  state->glyphs = NULL;
+	  g_free (state->log_widths);
+
 	  return BREAK_NONE_FIT;
 	}
     }
@@ -2581,6 +2652,7 @@ struct _ParaBreakState
   const char *text;
   gint start_offset;
   gint line_start_index;
+  ItemState item_state;
 };
 
 static void
@@ -2629,6 +2701,7 @@ process_line (PangoLayout    *layout,
       result = process_item (layout, line, item, layout->text,
 			     state->start_offset,
 			     !have_break, FALSE,
+			     &state->item_state,
 			     &remaining_width);
 
       switch (result)
@@ -2662,11 +2735,12 @@ process_line (PangoLayout    *layout,
 	    {
 	      /* Reshape run to break */
 	      PangoItem *item = state->items->data;
-
+	      
 	      old_num_chars = item->num_chars;
 	      result = process_item (layout, line, item, layout->text,
 				     state->start_offset,
 				     TRUE, TRUE,
+				     &state->item_state,
 				     &break_remaining_width);
 	      g_assert (result == BREAK_SOME_FIT);
 
@@ -2842,6 +2916,7 @@ pango_layout_check_lines (PangoLayout *l
 	  state.start_offset = start_offset;
 	  state.text = start;
           state.line_start_index = state.text - layout->text;
+	  state.item_state.item = NULL;
 	  
 	  while (state.items)
             process_line (layout, &state);