GNOME.org
 

[gtksourceview] Rework GtkSourceMark binary search

commit 3bac7395baadd886ece8376112d1249ba9b8a1b8
Author: Paolo Borelli <pborelli gnome org>
Date:   Sun Jan 27 14:48:19 2013 +0100

    Rework GtkSourceMark binary search
    
    Add SourceMark unit test that was failing with the old implementation
    and rework the implementation to properly deal with multiple source
    marks at the same iter.

 gtksourceview/gtksourcebuffer.c |  197 +++++++++++++++++++++++---------------
 tests/Makefile.am               |    7 ++
 tests/test-mark.c               |   57 +++++++++++
 3 files changed, 183 insertions(+), 78 deletions(-)
---
diff --git a/gtksourceview/gtksourcebuffer.c b/gtksourceview/gtksourcebuffer.c
index 0e66e52..6637283 100644
--- a/gtksourceview/gtksourcebuffer.c
+++ b/gtksourceview/gtksourcebuffer.c
@@ -1640,50 +1640,109 @@ source_mark_remove (GtkSourceBuffer *buffer, GtkSourceMark *mark)
 }
 
 /* Performs a binary search among the source marks in @buffer for the
- * position of the @iter.  Returns the nearest matching mark (its
- * index in the marks array) and optionally the value of the
- * comparision between the given iter and the iter at the returned mark.
+ * position of the @iter.  Returns the index of the mark at the specified
+ * position or nearest before or after depending on @before.
  *
  * Return value: an index in the source marks array or -1 if the array is
- * empty.
+ * empty or if there is no mark before/after the specified position
  */
 static gint
-source_mark_bsearch (GtkSourceBuffer *buffer, GtkTextIter *iter, gint *last_cmp)
+source_mark_bsearch (GtkSourceBuffer *buffer, GtkTextIter *iter, gboolean before)
 {
-	GtkTextIter check_iter;
-	GtkSourceMark **check, **p;
 	GArray *marks = buffer->priv->source_marks;
-	gint n_marks = marks->len;
-	gint cmp, i;
+	GtkSourceMark *check;
+	GtkTextIter check_iter, found_iter;
+	gint cmp, i, min, max;
 
-	if (n_marks == 0)
+	if (marks->len == 0)
 		return -1;
 
-	check = p = &g_array_index (marks, GtkSourceMark *, 0);
-	p--;
-	cmp = 0;
-	while (n_marks)
+	i = min = 0;
+	max = marks->len - 1;
+	while (max >= min)
 	{
-		i = (n_marks + 1) >> 1;
-		check = p + i;
+		i = (min + max) >> 1;
+		check = g_array_index (marks, GtkSourceMark *, i);
 		gtk_text_buffer_get_iter_at_mark (GTK_TEXT_BUFFER (buffer),
 						  &check_iter,
-						  GTK_TEXT_MARK (*check));
+						  GTK_TEXT_MARK (check));
 		cmp = gtk_text_iter_compare (iter, &check_iter);
-		if (cmp > 0)
+		if (cmp < 0)
 		{
-			n_marks -= i;
-			p = check;
+			max = i - 1;
 		}
-		else if (cmp < 0)
-			n_marks = i - 1;
-		else /* if (cmp == 0) */
+		else if (cmp > 0)
+		{
+			min = i + 1;
+		}
+		else
 			break;
 	}
 
-	i = check - &g_array_index (marks, GtkSourceMark *, 0);
-	if (last_cmp)
-		*last_cmp = cmp;
+	if (before)
+	{
+		/* if the binary search match is after the specified iter, go back */
+		while (cmp < 0 && i >= 0)
+		{
+			if (i == 0)
+				return -1;
+
+			i--;
+			check = g_array_index (marks, GtkSourceMark *, i);
+			gtk_text_buffer_get_iter_at_mark (GTK_TEXT_BUFFER (buffer),
+							  &check_iter,
+							  GTK_TEXT_MARK (check));
+			cmp = gtk_text_iter_compare (iter, &check_iter);
+		}
+
+		/* if there are many marks at the given iter, return the last */
+		found_iter = check_iter;
+		while (i < marks->len - 1)
+		{
+			check = g_array_index (marks, GtkSourceMark *, i + 1);
+			gtk_text_buffer_get_iter_at_mark (GTK_TEXT_BUFFER (buffer),
+							  &check_iter,
+							  GTK_TEXT_MARK (check));
+			cmp = gtk_text_iter_compare (&found_iter, &check_iter);
+			if (cmp != 0)
+			{
+				break;
+			}
+			i++;
+		}
+	}
+	else
+	{
+		/* if the binary search match is before the specified iter, go forward */
+		while (cmp > 0 && i < marks->len)
+		{
+			if (i == marks->len - 1)
+				return -1;
+
+			i++;
+			check = g_array_index (marks, GtkSourceMark *, i);
+			gtk_text_buffer_get_iter_at_mark (GTK_TEXT_BUFFER (buffer),
+							  &check_iter,
+							  GTK_TEXT_MARK (check));
+			cmp = gtk_text_iter_compare (iter, &check_iter);
+		}
+
+		/* if there are many marks at the given iter, return the first */
+		found_iter = check_iter;
+		while (i > 0)
+		{
+			check = g_array_index (marks, GtkSourceMark *, i - 1);
+			gtk_text_buffer_get_iter_at_mark (GTK_TEXT_BUFFER (buffer),
+							  &check_iter,
+							  GTK_TEXT_MARK (check));
+			cmp = gtk_text_iter_compare (&found_iter, &check_iter);
+			if (cmp != 0)
+			{
+				break;
+			}
+			i--;
+		}
+	}
 
 	return i;
 }
@@ -1692,19 +1751,18 @@ static void
 source_mark_insert (GtkSourceBuffer *buffer, GtkSourceMark *mark)
 {
 	GtkTextIter iter;
-	gint idx, cmp;
+	gint idx;
 
 	gtk_text_buffer_get_iter_at_mark (GTK_TEXT_BUFFER (buffer),
 					  &iter,
 					  GTK_TEXT_MARK (mark));
 
-	idx = source_mark_bsearch (buffer, &iter, &cmp);
+	idx = source_mark_bsearch (buffer, &iter, TRUE);
 	if (idx >= 0)
 	{
 		/* if the mark we found is at same iter or before
 		 * put our mark after that */
-		if (cmp >= 0)
-			idx++;
+		idx++;
 	}
 	else
 	{
@@ -1839,15 +1897,12 @@ gtk_source_buffer_create_source_mark (GtkSourceBuffer   *buffer,
 	return mark;
 }
 
-GtkSourceMark *
-_gtk_source_buffer_source_mark_next (GtkSourceBuffer *buffer,
-				     GtkSourceMark   *mark,
-				     const gchar     *category)
+static gint
+get_mark_index (GtkSourceBuffer *buffer,
+		GtkSourceMark   *mark)
 {
 	GtkTextIter iter;
-	gint idx, cmp;
-
-	g_return_val_if_fail (GTK_SOURCE_IS_BUFFER (buffer), NULL);
+	gint idx;
 
 	/* TODO: we could speed this up by caching the current
 	 * position in the mark and invalidating the cache when
@@ -1856,11 +1911,10 @@ _gtk_source_buffer_source_mark_next (GtkSourceBuffer *buffer,
 					  &iter,
 					  GTK_TEXT_MARK (mark));
 
-	idx = source_mark_bsearch (buffer, &iter, &cmp);
+	idx = source_mark_bsearch (buffer, &iter, FALSE);
 
 	/* the array should already contain @mark */
-	g_return_val_if_fail (idx >= 0, NULL);
-	g_return_val_if_fail (cmp == 0, NULL);
+	g_assert (idx >= 0);
 
 	/* move up to our mark among the ones at this position */
 	while (mark != g_array_index (buffer->priv->source_marks, GtkSourceMark *, idx))
@@ -1868,6 +1922,20 @@ _gtk_source_buffer_source_mark_next (GtkSourceBuffer *buffer,
 		++idx;
 	}
 
+	return idx;
+}
+
+GtkSourceMark *
+_gtk_source_buffer_source_mark_next (GtkSourceBuffer *buffer,
+				     GtkSourceMark   *mark,
+				     const gchar     *category)
+{
+	gint idx;
+
+	g_return_val_if_fail (GTK_SOURCE_IS_BUFFER (buffer), NULL);
+
+	idx = get_mark_index (buffer, mark);
+
 	while ((guint) ++idx < buffer->priv->source_marks->len)
 	{
 		GtkSourceMark *ret;
@@ -1888,29 +1956,11 @@ _gtk_source_buffer_source_mark_prev (GtkSourceBuffer *buffer,
 				     GtkSourceMark   *mark,
 				     const gchar     *category)
 {
-	GtkTextIter iter;
-	gint idx, cmp;
+	gint idx;
 
 	g_return_val_if_fail (GTK_SOURCE_IS_BUFFER (buffer), NULL);
 
-	/* TODO: we could speed this up by caching the current
-	 * position in the mark and invalidating the cache when
-	 * the marks array changes. For now we always lookup. */
-	gtk_text_buffer_get_iter_at_mark (GTK_TEXT_BUFFER (buffer),
-					  &iter,
-					  GTK_TEXT_MARK (mark));
-
-	idx = source_mark_bsearch (buffer, &iter, &cmp);
-
-	/* the array should already contain @mark */
-	g_return_val_if_fail (idx >= 0, NULL);
-	g_return_val_if_fail (cmp == 0, NULL);
-
-	/* move up to our mark among the ones at this position */
-	while (mark != g_array_index (buffer->priv->source_marks, GtkSourceMark *, idx))
-	{
-		++idx;
-	}
+	idx = get_mark_index (buffer, mark);
 
 	while (--idx >= 0)
 	{
@@ -1947,20 +1997,17 @@ gtk_source_buffer_forward_iter_to_source_mark (GtkSourceBuffer *buffer,
 					       const gchar     *category)
 {
 	GtkTextIter i;
-	gint idx, cmp;
+	gint idx;
 
 	g_return_val_if_fail (GTK_SOURCE_IS_BUFFER (buffer), FALSE);
 	g_return_val_if_fail (iter != NULL, FALSE);
 
 	i = *iter;
 
-	idx = source_mark_bsearch (buffer, &i, &cmp);
+	idx = source_mark_bsearch (buffer, &i, FALSE);
 	if (idx < 0)
 		return FALSE;
 
-	if (cmp >= 0)
-		++idx;
-
 	while ((guint) idx < buffer->priv->source_marks->len)
 	{
 		GtkSourceMark *mark;
@@ -1970,10 +2017,8 @@ gtk_source_buffer_forward_iter_to_source_mark (GtkSourceBuffer *buffer,
 		    0 == strcmp (category, gtk_source_mark_get_category (mark)))
 		{
 			/* update the iter */
-			gtk_text_buffer_get_iter_at_mark (GTK_TEXT_BUFFER (buffer),
-							  &i, GTK_TEXT_MARK (mark));
-
-			if (gtk_text_iter_compare (&i, iter) > 0 )
+			gtk_text_buffer_get_iter_at_mark (GTK_TEXT_BUFFER (buffer), &i, GTK_TEXT_MARK (mark));
+			if (gtk_text_iter_compare (&i, iter) > 0)
 			{
 				*iter = i;
 				return TRUE;
@@ -2006,20 +2051,17 @@ gtk_source_buffer_backward_iter_to_source_mark (GtkSourceBuffer *buffer,
 						const gchar     *category)
 {
 	GtkTextIter i;
-	gint idx, cmp;
+	gint idx;
 
 	g_return_val_if_fail (GTK_SOURCE_IS_BUFFER (buffer), FALSE);
 	g_return_val_if_fail (iter != NULL, FALSE);
 
 	i = *iter;
 
-	idx = source_mark_bsearch (buffer, &i, &cmp);
+	idx = source_mark_bsearch (buffer, &i, TRUE);
 	if (idx < 0)
 		return FALSE;
 
-	if (cmp <= 0)
-		--idx;
-
 	while (idx >= 0)
 	{
 		GtkSourceMark *mark;
@@ -2028,10 +2070,9 @@ gtk_source_buffer_backward_iter_to_source_mark (GtkSourceBuffer *buffer,
 		if (category == NULL ||
 		    0 == strcmp (category, gtk_source_mark_get_category (mark)))
 		{
-			gtk_text_buffer_get_iter_at_mark (GTK_TEXT_BUFFER (buffer),
-							  &i, GTK_TEXT_MARK (mark));
-
-			if (gtk_text_iter_compare (&i, iter) < 0 )
+			/* update the iter */
+			gtk_text_buffer_get_iter_at_mark (GTK_TEXT_BUFFER (buffer), &i, GTK_TEXT_MARK (mark));
+			if (gtk_text_iter_compare (&i, iter) < 0)
 			{
 				*iter = i;
 				return TRUE;
diff --git a/tests/Makefile.am b/tests/Makefile.am
index 663fb16..1e1720e 100644
--- a/tests/Makefile.am
+++ b/tests/Makefile.am
@@ -66,6 +66,13 @@ test_buffer_LDADD = 		\
 	$(DEP_LIBS)			\
 	$(TESTS_LIBS)
 
+UNIT_TEST_PROGS += test-mark
+test_mark_SOURCES = test-mark.c
+test_mark_LDADD = 		\
+	$(top_builddir)/gtksourceview/libgtksourceview-3.0.la \
+	$(DEP_LIBS)			\
+	$(TESTS_LIBS)
+
 UNIT_TEST_PROGS += test-regex
 test_regex_SOURCES = test-regex.c
 test_regex_LDADD = 						\
diff --git a/tests/test-mark.c b/tests/test-mark.c
new file mode 100644
index 0000000..6a30039
--- /dev/null
+++ b/tests/test-mark.c
@@ -0,0 +1,57 @@
+#include <gtk/gtk.h>
+#include <gtksourceview/gtksource.h>
+
+static void
+test_create (void)
+{
+	GtkSourceMark *m;
+
+	m = gtk_source_mark_new ("Mark 1", "test");
+	g_assert_cmpstr ("Mark 1", ==, gtk_text_mark_get_name (GTK_TEXT_MARK (m)));
+	g_assert_cmpstr ("test", ==, gtk_source_mark_get_category (m));
+	g_assert (NULL == gtk_text_mark_get_buffer (GTK_TEXT_MARK (m)));
+	g_assert (NULL == gtk_source_mark_next (m, NULL));
+	g_assert (NULL == gtk_source_mark_prev (m, NULL));
+	g_object_unref (m);
+}
+
+static void
+test_add_to_buffer (void)
+{
+	GtkSourceBuffer *b;
+	GtkSourceMark *m1, *m2, *m3;
+	GtkTextIter i;
+
+	b = gtk_source_buffer_new (NULL);
+	m1 = gtk_source_mark_new ("Mark 1", "test");
+	m2 = gtk_source_mark_new ("Mark 2", "test2");
+	m3 = gtk_source_mark_new ("Mark 3", "test");
+
+	gtk_text_buffer_get_start_iter (GTK_TEXT_BUFFER (b), &i);
+	gtk_text_buffer_add_mark (GTK_TEXT_BUFFER (b), GTK_TEXT_MARK (m1), &i);
+	gtk_text_buffer_add_mark (GTK_TEXT_BUFFER (b), GTK_TEXT_MARK (m2), &i);
+	gtk_text_buffer_add_mark (GTK_TEXT_BUFFER (b), GTK_TEXT_MARK (m3), &i);
+
+	g_assert (m2 == gtk_source_mark_next (m1, NULL));
+	g_assert (m3 == gtk_source_mark_next (m1, "test"));
+	g_assert (NULL == gtk_source_mark_next (m2, "test2"));
+	g_assert (NULL == gtk_source_mark_next (m3, NULL));
+
+	g_assert (m1 == gtk_source_mark_prev (m2, NULL));
+	g_assert (m1 == gtk_source_mark_prev (m3, "test"));
+	g_assert (NULL == gtk_source_mark_prev (m2, "test2"));
+	g_assert (NULL == gtk_source_mark_prev (m1, NULL));
+
+	g_object_unref (b);
+}
+
+int
+main (int argc, char** argv)
+{
+	gtk_test_init (&argc, &argv);
+
+	g_test_add_func ("/Mark/create", test_create);
+	g_test_add_func ("/Mark/add-to-buffer", test_add_to_buffer);
+
+	return g_test_run();
+}
[Date Prev][Date Next]   [Thread Prev][Thread Next]   [Thread Index] [Date Index] [Author Index]