SF.net SVN: geany:[5567] trunk/src/symbols.c

[colombanw at users.sourceforge.net]

Revision: 5567
          http://geany.svn.sourceforge.net/geany/?rev=5567&view=rev
Author:   colombanw
Date:     2011-03-05 22:56:55 +0000 (Sat, 05 Mar 2011)

Log Message:
-----------
Improve performances of symbol list updating

Rather than walking the whole tree for each tag to find a possibly
corresponding row, use a hash table as cache.
This is a very significant improvement on large files with many tags,
reducing for example to about 170ms an update that took more than 18s
before.

Also fix merging of tags with same name and scope (probably unlikely to
exist in real-world files, but the tagmanager extract them correctly
and they used to display correctly too).

Modified Paths:
--------------
    trunk/src/symbols.c

Modified: trunk/src/symbols.c
===================================================================
--- trunk/src/symbols.c	2011-03-05 22:55:34 UTC (rev 5566)
+++ trunk/src/symbols.c	2011-03-05 22:56:55 UTC (rev 5567)
@@ -1161,31 +1161,90 @@
 }
 
 
-static gboolean find_iter(GtkTreeStore *store, GtkTreeIter *iter, const TMTag *tag)
+static gboolean tag_equal(gconstpointer v1, gconstpointer v2)
 {
+	const TMTag *t1 = v1;
+	const TMTag *t2 = v2;
+
+	return (t1->type == t2->type && strcmp(t1->name, t2->name) == 0 &&
+			utils_str_equal(t1->atts.entry.scope, t2->atts.entry.scope));
+}
+
+
+/* inspired from g_str_hash() */
+static guint tag_hash(gconstpointer v)
+{
+	const TMTag *tag = v;
+	const signed char *p;
+	guint32 h = 5381;
+
+	h = (h << 5) + h + tag->type;
+	for (p = tag->name; *p != '\0'; p++)
+		h = (h << 5) + h + *p;
+	if (tag->atts.entry.scope)
+	{
+		for (p = tag->atts.entry.scope; *p != '\0'; p++)
+			h = (h << 5) + h + *p;
+	}
+
+	return h;
+}
+
+
+static GHashTable *build_iter_table(GtkTreeStore *store)
+{
 	GtkTreeModel *model = GTK_TREE_MODEL(store);
-	gboolean found = FALSE;
+	GHashTable *table;
+	GtkTreeIter iter;
 
-	if (!gtk_tree_model_get_iter_first(model, iter))
-		return FALSE;
+	table = g_hash_table_new_full(tag_hash, tag_equal,
+			(GDestroyNotify)tm_tag_unref, (GDestroyNotify)gtk_tree_path_free);
+
+	if (!gtk_tree_model_get_iter_first(model, &iter))
+		return table;
 	do
 	{
-		TMTag *candidate;
+		TMTag *tag;
 
-		gtk_tree_model_get(model, iter, SYMBOLS_COLUMN_TAG, &candidate, -1);
-		found = (candidate && candidate->type == tag->type &&
-				 utils_str_equal(candidate->name, tag->name) &&
-				 utils_str_equal(candidate->atts.entry.scope, tag->atts.entry.scope));
-		tm_tag_unref(candidate);
+		gtk_tree_model_get(model, &iter, SYMBOLS_COLUMN_TAG, &tag, -1);
+		if (tag)
+			g_hash_table_insert(table, tag, gtk_tree_model_get_path(model, &iter));
 	}
-	while (!found && next_iter(model, iter));
+	while (next_iter(model, &iter));
 
-	return found;
+	return table;
 }
 
 
-static void add_tree_tag(GeanyDocument *doc, const TMTag *tag, GHashTable *parent_hash)
+static gboolean find_iter(GtkTreeStore *store, GHashTable *iter_hash, const TMTag *tag,
+		GtkTreeIter *iter)
 {
+	GtkTreePath *path;
+
+	path = g_hash_table_lookup(iter_hash, tag);
+	if (path)
+	{
+		GtkTreeIter tmp;
+		gboolean valid;
+
+		if (!gtk_tree_model_get_iter(GTK_TREE_MODEL(store), &tmp, path))
+			return FALSE;
+		gtk_tree_model_get(GTK_TREE_MODEL(store), &tmp, SYMBOLS_COLUMN_VALID, &valid, -1);
+		/* if the row is valid it has already been updated, so it's simply a duplicate */
+		if (!valid)
+		{
+			*iter = tmp;
+			return TRUE;
+		}
+	}
+
+	return FALSE;
+}
+
+
+static void add_tree_tag(GeanyDocument *doc, const TMTag *tag, GHashTable *parent_hash,
+		GHashTable *iter_hash)
+{
 	filetype_id ft_id = doc->file_type->id;
 	GtkTreeStore *tree_store = doc->priv->tag_store;
 	GtkTreeIter *parent = NULL;
@@ -1226,7 +1285,7 @@
 			child = new_iter;
 		}
 
-		if (!find_iter(tree_store, child, tag))
+		if (!find_iter(tree_store, iter_hash, tag, child))
 		{
 			gboolean expand = FALSE;
 
@@ -1271,9 +1330,11 @@
 {
 	const GList *item;
 	GHashTable *parent_hash;
+	GHashTable *iter_hash;
 
 	/* Create a hash table "parent_tag_name":(GtkTreeIter*) */
 	parent_hash = g_hash_table_new_full(g_str_hash, g_str_equal, NULL, g_free);
+	iter_hash = build_iter_table(doc->priv->tag_store);
 
 	/* find and store all parent names in the hash table */
 	for (item = tags; item; item = g_list_next(item))
@@ -1288,8 +1349,9 @@
 	{
 		const TMTag *tag = item->data;
 
-		add_tree_tag(doc, tag, parent_hash);
+		add_tree_tag(doc, tag, parent_hash, iter_hash);
 	}
+	g_hash_table_destroy(iter_hash);
 	g_hash_table_destroy(parent_hash);
 }
 


This was sent by the SourceForge.net collaborative development platform, the world's largest Open Source development site.