Add vtetree.[ch] Don't use a GArray but use calloc'ed memory to speed up

2005-03-02  Kjartan Maraas  <kmaraas@gnome.org>

	* src/Makefile.am: Add vtetree.[ch]
	* src/vte.c: (vte_terminal_draw_row): Don't use a GArray
	but use calloc'ed memory to speed up things further.
	From bug #137864. Patch from Benjamin Otte.
	* src/vtetree.c: (_vte_tree_new), (_vte_tree_destroy),
	(_vte_tree_insert), (_vte_tree_lookup): New file
	* src/vtetree.h: New file
	* src/vtexft.c: (_vte_xft_font_open), (_vte_xft_font_close),
	(_vte_xft_font_for_char), (_vte_xft_char_width): Use the new
	functions to speed up things. From bug #137864. Patch from
	Benjamin Otte. There are still two patches in there that don't
	apply cleanly any more. Will look at those later.
	* vte.spec: Bump version.

7 files changed, 151 insertions, 26 deletions

diff --git a/ChangeLog b/ChangeLog
index 3db792f..e0c9357 100644
--- a/ChangeLog
+++ b/ChangeLog
@@ -1,3 +1,19 @@
+2005-03-02  Kjartan Maraas  <kmaraas@gnome.org>
+
+	* src/Makefile.am: Add vtetree.[ch]
+	* src/vte.c: (vte_terminal_draw_row): Don't use a GArray
+	but use calloc'ed memory to speed up things further.
+	From bug #137864. Patch from Benjamin Otte.
+	* src/vtetree.c: (_vte_tree_new), (_vte_tree_destroy),
+	(_vte_tree_insert), (_vte_tree_lookup): New file
+	* src/vtetree.h: New file
+	* src/vtexft.c: (_vte_xft_font_open), (_vte_xft_font_close),
+	(_vte_xft_font_for_char), (_vte_xft_char_width): Use the new
+	functions to speed up things. From bug #137864. Patch from
+	Benjamin Otte. There are still two patches in there that don't
+	apply cleanly any more. Will look at those later.
+	* vte.spec: Bump version.
+
 2005-02-28  Kjartan Maraas  <kmaraas@gnome.org>
 
 	* src/vte.c: (vte_sequence_handler_send_primary_device_attributes):
diff --git a/src/Makefile.am b/src/Makefile.am
index b8f20f3..dc7973b 100644
--- a/src/Makefile.am
+++ b/src/Makefile.am
@@ -83,6 +83,8 @@ libvte_la_SOURCES = \
 	vteskel.h \
 	vtetc.c \
 	vtetc.h \
+	vtetree.c \
+	vtetree.h \
 	vtexft.c \
 	vtexft.h
 
diff --git a/src/vte.c b/src/vte.c
index 04c930e..b50005e 100644
--- a/src/vte.c
+++ b/src/vte.c
@@ -13732,16 +13732,16 @@ vte_terminal_draw_row(VteTerminal *terminal,
 		      gint x, gint y,
 		      gint column_width, gint row_height)
 {
-	GArray *items;
 	int i, j, fore, nfore, back, nback;
 	gboolean underline, nunderline, bold, nbold, hilite, nhilite, reverse,
 		 selected, strikethrough, nstrikethrough, drawn;
-	struct _vte_draw_text_request item;
+	struct _vte_draw_text_request *items, item;
+	guint item_count = 0;
 	struct vte_charcell *cell;
 
 	/* Allocate an array to hold draw requests. */
-	items = g_array_new(FALSE, FALSE,
-			    sizeof(struct _vte_draw_text_request));
+	/* FIXME: can this get too big for alloca? */
+	items = g_newa (struct _vte_draw_text_request, column_count);
 
 	/* Back up in case this is a multicolumn character, making the drawing
 	 * area a little wider. */
@@ -13804,7 +13804,7 @@ vte_terminal_draw_row(VteTerminal *terminal,
 
 		/* If it's not a local graphic character, or if we couldn't
 		   draw it, add it to the draw list. */
-		g_array_append_val(items, item);
+		items[item_count++] = item;
 
 		/* Now find out how many cells have the same attributes. */
 		j = i + item.columns;
@@ -13876,27 +13876,22 @@ vte_terminal_draw_row(VteTerminal *terminal,
 			item.columns = cell ? cell->columns : 1;
 			item.x = x + ((j - column) * column_width);
 			item.y = y;
-			g_array_append_val(items, item);
+			items[item_count++] = item;
 			j += item.columns;
 		}
 		/* Draw the cells. */
 		vte_terminal_draw_cells(terminal,
-					&g_array_index(items,
-						       struct _vte_draw_text_request,
-						       0),
-					items->len,
+					items,
+					item_count,
 					fore, back, FALSE,
 					bold, underline,
 					strikethrough, hilite, FALSE,
 					column_width, row_height);
-		g_array_set_size(items, 0);
+		item_count = 0;
 		/* We'll need to continue at the first cell which didn't
 		 * match the first one in this set. */
 		i = j;
 	}
-
-	/* Clean up. */
-	g_array_free(items, TRUE);
 }
 
 /* Draw the widget. */
diff --git a/src/vtetree.c b/src/vtetree.c
new file mode 100644
index 0000000..fc08a78
--- /dev/null
+++ b/src/vtetree.c
@@ -0,0 +1,60 @@
+/*
+ * Copyright (C) 2004 Benjamin Otte <otte@gnome.org>
+ *
+ * This is free software; you can redistribute it and/or modify it under
+ * the terms of the GNU Library General Public License as published by
+ * the Free Software Foundation; either version 2 of the License, or
+ * (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful, but
+ * WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+ * General Public License for more details.
+ *
+ * You should have received a copy of the GNU Library General Public
+ * License along with this program; if not, write to the Free Software
+ * Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
+ */
+
+/* The interfaces in this file are subject to change at any time. */
+
+#include "vtetree.h"
+
+VteTree *
+_vte_tree_new(GCompareFunc key_compare_func)
+{
+  VteTree *tree = g_new0 (VteTree, 1);
+  tree->tree = g_tree_new (key_compare_func);
+  return tree;
+}
+
+void 
+_vte_tree_destroy(VteTree *tree)
+{
+  g_tree_destroy (tree->tree);
+  g_free (tree);
+}
+
+void 
+_vte_tree_insert(VteTree *tree, gpointer key, gpointer value)
+{
+  guint index = GPOINTER_TO_UINT (key);
+  
+  if (index < VTE_TREE_ARRAY_SIZE) {
+    tree->array[index] = value;
+    return;
+  }
+  g_tree_insert (tree->tree, key, value);
+}
+
+gpointer
+_vte_tree_lookup(VteTree *tree, gconstpointer key)
+{
+  const guint index = GPOINTER_TO_UINT (key);
+  
+  if (index < VTE_TREE_ARRAY_SIZE)
+    return tree->array[index];
+
+  return g_tree_lookup (tree->tree, key);
+}
+
diff --git a/src/vtetree.h b/src/vtetree.h
new file mode 100644
index 0000000..af4f21a
--- /dev/null
+++ b/src/vtetree.h
@@ -0,0 +1,51 @@
+/*
+ * Copyright (C) 2004 Benjamin Otte <otte@gnome.org>
+ *
+ * This is free software; you can redistribute it and/or modify it under
+ * the terms of the GNU Library General Public License as published by
+ * the Free Software Foundation; either version 2 of the License, or
+ * (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful, but
+ * WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+ * General Public License for more details.
+ *
+ * You should have received a copy of the GNU Library General Public
+ * License along with this program; if not, write to the Free Software
+ * Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
+ */
+
+/* The interfaces in this file are subject to change at any time. */
+
+#ifndef vte_tree_h_included
+#define vte_tree_h_included
+
+#ident "$Id$"
+
+#include <glib.h>
+
+G_BEGIN_DECLS
+
+/* This is an optimiziation for GTrees we use with unicode characters. Since
+ * most characters are in the range [0-128], we store that range in an array
+ * for faster access.
+ * We match the API for GTree here.
+ */
+#define VTE_TREE_ARRAY_SIZE (128)
+
+typedef struct _VteTree VteTree;
+struct _VteTree {
+  GTree *tree;
+  gpointer array[VTE_TREE_ARRAY_SIZE];
+};
+
+VteTree *_vte_tree_new(GCompareFunc key_compare_func);
+void _vte_tree_destroy(VteTree *tree);
+void _vte_tree_insert(VteTree *tree, gpointer key, gpointer value);
+gpointer _vte_tree_lookup(VteTree *tree, gconstpointer key);
+/* extend as needed */
+
+G_END_DECLS
+
+#endif
diff --git a/src/vtexft.c b/src/vtexft.c
index 944496b..1995568 100644
--- a/src/vtexft.c
+++ b/src/vtexft.c
@@ -35,6 +35,7 @@
 #include "vtedraw.h"
 #include "vtefc.h"
 #include "vtexft.h"
+#include "vtetree.h"
 
 #ifdef ENABLE_NLS
 #include <libintl.h>
@@ -53,8 +54,8 @@ struct _vte_xft_font {
 #endif
 	GArray *patterns;
 	GArray *fonts;
-	GTree *fontmap;
-	GTree *widths;
+	VteTree *fontmap;
+	VteTree *widths;
 };
 
 struct _vte_xft_data
@@ -124,8 +125,8 @@ _vte_xft_font_open(GtkWidget *widget, const PangoFontDescription *fontdesc,
 #endif
 	font->patterns = patterns;
 	font->fonts = g_array_new(TRUE, TRUE, sizeof(XftFont*));
-	font->fontmap = g_tree_new(_vte_xft_direct_compare);
-	font->widths = g_tree_new(_vte_xft_direct_compare);
+	font->fontmap = _vte_tree_new(_vte_xft_direct_compare);
+	font->widths = _vte_tree_new(_vte_xft_direct_compare);
 
 	return font;
 }
@@ -166,9 +167,9 @@ _vte_xft_font_close(struct _vte_xft_font *font)
 	g_array_free(font->fonts, TRUE);
 	font->fonts = NULL;
 
-	g_tree_destroy(font->fontmap);
+	_vte_tree_destroy(font->fontmap);
 	font->fontmap = NULL;
-	g_tree_destroy(font->widths);
+	_vte_tree_destroy(font->widths);
 	font->widths = NULL;
 
 	g_free(font);
@@ -191,7 +192,7 @@ _vte_xft_font_for_char(struct _vte_xft_font *font, gunichar c)
 	g_return_val_if_fail(font->widths != NULL, NULL);
 
 	/* Check if we have a char-to-font entry for it. */
-	i = GPOINTER_TO_INT(g_tree_lookup(font->fontmap, p));
+	i = GPOINTER_TO_INT(_vte_tree_lookup(font->fontmap, p));
 	if (i != 0) {
 		switch (i) {
 		/* Checked before, no luck. */
@@ -225,7 +226,7 @@ _vte_xft_font_for_char(struct _vte_xft_font *font, gunichar c)
 
 	/* Match? */
 	if (i < font->fonts->len) {
-		g_tree_insert(font->fontmap,
+		_vte_tree_insert(font->fontmap,
 			      p,
 			      GINT_TO_POINTER(i + FONT_INDEX_FUDGE));
 		ftfont = g_array_index(font->fonts, XftFont *, i);
@@ -253,7 +254,7 @@ _vte_xft_font_for_char(struct _vte_xft_font *font, gunichar c)
 
 	/* No match? */
 	if (i >= font->patterns->len) {
-		g_tree_insert(font->fontmap,
+		_vte_tree_insert(font->fontmap,
 			      p,
 			      GINT_TO_POINTER(-FONT_INDEX_FUDGE));
 		if (font->fonts->len > 0) {
@@ -288,7 +289,7 @@ _vte_xft_char_width(struct _vte_xft_font *font, XftFont *ftfont, gunichar c)
 	g_return_val_if_fail(font->widths != NULL, 0);
 
 	/* Check if we have a char-to-width entry for it. */
-	i = GPOINTER_TO_INT(g_tree_lookup(font->widths, p));
+	i = GPOINTER_TO_INT(_vte_tree_lookup(font->widths, p));
 	if (i != 0) {
 		switch (i) {
 		case -CHAR_WIDTH_FUDGE:
@@ -306,7 +307,7 @@ _vte_xft_char_width(struct _vte_xft_font *font, XftFont *ftfont, gunichar c)
 		_vte_xft_text_extents(font, ftfont, c, &extents);
 	}
 	i = extents.xOff + CHAR_WIDTH_FUDGE;
-	g_tree_insert(font->widths, p, GINT_TO_POINTER(i));
+	_vte_tree_insert(font->widths, p, GINT_TO_POINTER(i));
 	return extents.xOff;
 }
 
diff --git a/vte.spec b/vte.spec
index 1e82d3e..57c9c51 100644
--- a/vte.spec
+++ b/vte.spec
@@ -1,5 +1,5 @@
 Name: vte
-Version: 0.11.11
+Version: 0.11.12
 Release: 1
 Summary: An experimental terminal emulator.
 License: LGPL