[geany/geany] 32a3df: Use binary search when removing file tags

[Jiří Techet]

Branch:      refs/heads/master
Author:      Jiří Techet <techet at gmail.com>
Committer:   Jiří Techet <techet at gmail.com>
Date:        Thu, 30 Oct 2014 21:08:17 UTC
Commit:      32a3dfab7f6e75f102a2cac79c6ce3eac7c2a216
             https://github.com/geany/geany/commit/32a3dfab7f6e75f102a2cac79c6ce3eac7c2a216

Log Message:
-----------
Use binary search when removing file tags

Even though the binary search requires expensive string comparisons,
there are just log(n) of them to find the tag in the workspace array
and the result is much faster than scanning the array linearly (this
of course works only under the condition that

len(source_file->tags_array) << len(workspace_array)

This is however satisfied for big projects (and doesn't matter for small
projects).

Also make the tm_tags_find() function more user friendly by returning
tagCount 0 when no tags found.


Modified Paths:
--------------
    tagmanager/src/tm_tag.c

Modified: tagmanager/src/tm_tag.c
32 lines changed, 28 insertions(+), 4 deletions(-)
===================================================================
@@ -809,13 +809,36 @@ gboolean tm_tags_sort(GPtrArray *tags_array, TMTagAttrType *sort_attributes,
 void tm_tags_remove_file_tags(TMSourceFile *source_file, GPtrArray *tags_array)
 {
 	guint i;
-	for (i = 0; i < tags_array->len; i++)
+	GPtrArray *to_delete = g_ptr_array_sized_new(source_file->tags_array->len);
+	
+	for (i = 0; i < source_file->tags_array->len; i++)
 	{
-		TMTag *tag = tags_array->pdata[i];
+		guint j;
+		gint tag_count;
+		TMTag **found;
+		TMTag *tag = source_file->tags_array->pdata[i];
+		
+		found = tm_tags_find(tags_array, tag->name, FALSE, TRUE, &tag_count);
 		
-		if (tag != NULL && tag->file == source_file)
-			tags_array->pdata[i] = NULL;
+		for (j = 0; j < tag_count; j++)
+		{
+			if (*found != NULL && (*found)->file == source_file)
+			{
+				/* we cannot set the pointer to NULL now because the search wouldn't work */
+				g_ptr_array_add(to_delete, found);
+				break;
+			}
+			found++;
+		}
 	}
+
+	for (i = 0; i < to_delete->len; i++)
+	{
+		TMTag **tag = to_delete->pdata[i];
+		*tag = NULL;
+	}
+	g_ptr_array_free(to_delete, TRUE);
+
 	tm_tags_prune(tags_array);
 }
 
@@ -1055,6 +1078,7 @@ TMTag **tm_tags_find(const GPtrArray *tags_array, const char *name,
 	int tagMatches=0;
 	TMSortOptions sort_options;
 
+	*tagCount = 0;
 	if ((!tags_array) || (!tags_array->len))
 		return NULL;
 



--------------
This E-Mail was brought to you by github_commit_mail.py (Source: https://github.com/geany/infrastructure).