Re: g_s?list_sort doesn't do stable sort
- From: Kristian Hogsberg Kristensen <hogsberg daimi au dk>
- To: Tim Janik <timj gtk org>
- Cc: Gtk+ Developers <gtk-devel-list gnome org>
- Subject: Re: g_s?list_sort doesn't do stable sort
- Date: 29 Sep 2000 16:44:44 +0200
Tim Janik <timj gtk org> writes:
> On 8 Aug 2000, Kristian Hogsberg Kristensen wrote:
>
> >
> > Hi,
> >
> > The g_s?list_sort functions don't do a stable sort of the list
> > elements, that is they don't preserve the order of elements considered
> > equal by the comparison function. The patch to fix this is really
[...]
> ok, i agree mith maciej here.
> you had a typo in your patch though, so if you could
> actually test it out and resubmit it against recent
> CVS (cvs diff -u) that'd be good.
Yeah, that's a bit sloppy, I guess :).
> if i may be so bold, i wouldn't mind if you also cleaned up
> the indentation and missing spaces in the surrounding
> functions ;)
Sure, but they are actually OK, indentation-wise. However, I changed
the function pointer argument to just func instead of compare_func,
since this seems to be convention. Also, is there a reason
g_list_sort_merge shouldn't be publicly available? It's a general
purpose list function, and it is already in the library. I changed it
to g_list_merge and made it public.
Finally, I added test cases for the new merge functions and a test
that checks if g_list_sort now actually does a stable sort.
Btw, the patch below is against glib-1.3.1, since I couldn't get
through to the CVS server.
regards,
Kristian
diff -ur glib-1.3.1-orig/glib.h glib-1.3.1/glib.h
--- glib-1.3.1-orig/glib.h Fri Jul 14 18:31:28 2000
+++ glib-1.3.1/glib.h Fri Sep 29 16:17:24 2000
@@ -1017,8 +1017,11 @@
void g_list_foreach (GList *list,
GFunc func,
gpointer user_data);
+GList* g_list_merge (GList *list1,
+ GList *list2,
+ GCompareFunc func);
GList* g_list_sort (GList *list,
- GCompareFunc compare_func);
+ GCompareFunc func);
gpointer g_list_nth_data (GList *list,
guint n);
#define g_list_previous(list) ((list) ? (((GList *)(list))->prev) : NULL)
@@ -1071,8 +1074,11 @@
void g_slist_foreach (GSList *list,
GFunc func,
gpointer user_data);
-GSList* g_slist_sort (GSList *list,
- GCompareFunc compare_func);
+GSList* g_slist_merge (GSList *list1,
+ GSList *list2,
+ GCompareFunc func);
+GSList* g_slist_sort (GSList *list,
+ GCompareFunc func);
gpointer g_slist_nth_data (GSList *list,
guint n);
#define g_slist_next(slist) ((slist) ? (((GSList *)(slist))->next) : NULL)
diff -ur glib-1.3.1-orig/glist.c glib-1.3.1/glist.c
--- glib-1.3.1-orig/glist.c Tue Apr 18 16:01:33 2000
+++ glib-1.3.1/glist.c Thu Sep 28 17:50:55 2000
@@ -595,85 +595,92 @@
return list;
}
-static GList *
-g_list_sort_merge (GList *l1,
- GList *l2,
- GCompareFunc compare_func)
+GList*
+g_list_merge (GList *list1,
+ GList *list2,
+ GCompareFunc func)
{
- GList list, *l, *lprev;
+ GList list, *last, *lprev;
- l = &list;
+ g_return_val_if_fail (func != NULL, NULL);
+
+ last = &list;
lprev = NULL;
- while (l1 && l2)
+ while (list1 && list2)
{
- if (compare_func (l1->data, l2->data) < 0)
+ if ((*func) (list1->data, list2->data) <= 0)
{
- l->next = l1;
- l = l->next;
- l->prev = lprev;
- lprev = l;
- l1 = l1->next;
+ last->next = list1;
+ last = last->next;
+ last->prev = lprev;
+ lprev = last;
+ list1 = list1->next;
}
else
{
- l->next = l2;
- l = l->next;
- l->prev = lprev;
- lprev = l;
- l2 = l2->next;
+ last->next = list2;
+ last = last->next;
+ last->prev = lprev;
+ lprev = last;
+ list2 = list2->next;
}
}
- l->next = l1 ? l1 : l2;
- l->next->prev = l;
+
+ last->next = list1 ? list1 : list2;
+ last->next->prev = last;
return list.next;
}
GList*
-g_list_sort (GList *list,
- GCompareFunc compare_func)
+g_list_sort (GList *list,
+ GCompareFunc func)
{
- GList *l1, *l2;
+ GList *list1, *list2;
- if (!list)
- return NULL;
- if (!list->next)
+ g_return_val_if_fail (func != NULL, list);
+
+ if (!list || !list->next)
return list;
- l1 = list;
- l2 = list->next;
+ list1 = list;
+ list2 = list->next;
- while ((l2 = l2->next) != NULL)
+ while ((list2 = list2->next) != NULL)
{
- if ((l2 = l2->next) == NULL)
+ if ((list2 = list2->next) == NULL)
break;
- l1 = l1->next;
+ list1 = list1->next;
}
- l2 = l1->next;
- l1->next = NULL;
- return g_list_sort_merge (g_list_sort (list, compare_func),
- g_list_sort (l2, compare_func),
- compare_func);
+ list2 = list1->next;
+ list1->next = NULL;
+
+ return g_list_merge (g_list_sort (list, func),
+ g_list_sort (list2, func),
+ func);
}
GList*
-g_list_sort2 (GList *list,
- GCompareFunc compare_func)
+g_list_sort2 (GList *list,
+ GCompareFunc func)
{
GSList *runs = NULL;
GList *tmp;
+ g_return_val_if_fail (func != NULL, list);
+
/* Degenerate case. */
- if (!list) return NULL;
+ if (!list || !list->next)
+ return list;
/* Assume: list = [12,2,4,11,2,4,6,1,1,12]. */
for (tmp = list; tmp; )
{
GList *tmp2;
for (tmp2 = tmp;
- tmp2->next && compare_func (tmp2->data, tmp2->next->data) <= 0;
+ tmp2->next && (*func) (tmp2->data, tmp2->next->data) <= 0;
tmp2 = tmp2->next)
/* Nothing */;
runs = g_slist_append (runs, tmp);
@@ -689,9 +696,9 @@
dst = src = runs;
while (src && src->next)
{
- dst->data = g_list_sort_merge (src->data,
- src->next->data,
- compare_func);
+ dst->data = g_list_merge (src->data,
+ src->next->data,
+ func);
dstprev = dst;
dst = dst->next;
src = src->next->next;
diff -ur glib-1.3.1-orig/gslist.c glib-1.3.1/gslist.c
--- glib-1.3.1-orig/gslist.c Fri May 19 10:18:29 2000
+++ glib-1.3.1/gslist.c Thu Sep 28 18:08:00 2000
@@ -580,57 +580,58 @@
}
}
-static GSList*
-g_slist_sort_merge (GSList *l1,
- GSList *l2,
- GCompareFunc compare_func)
+GSList*
+g_slist_merge (GSList *list1,
+ GSList *list2,
+ GCompareFunc func)
{
- GSList list, *l;
+ GSList list, *last;
- l=&list;
+ last = &list;
- while (l1 && l2)
+ while (list1 && list2)
{
- if (compare_func(l1->data,l2->data) < 0)
+ if ((*func) (list1->data, list2->data) <= 0)
{
- l=l->next=l1;
- l1=l1->next;
+ last->next = list1;
+ last = last->next;
+ list1 = list1->next;
}
else
{
- l=l->next=l2;
- l2=l2->next;
+ last->next = list2;
+ last = last->next;
+ list2 = list2->next;
}
}
- l->next= l1 ? l1 : l2;
+ last->next = list1 ? list1 : list2;
return list.next;
}
GSList*
g_slist_sort (GSList *list,
- GCompareFunc compare_func)
+ GCompareFunc func)
{
- GSList *l1, *l2;
+ GSList *list1, *list2;
- if (!list)
- return NULL;
- if (!list->next)
+ if (!list || !list->next)
return list;
- l1 = list;
- l2 = list->next;
+ list1 = list;
+ list2 = list->next;
- while ((l2 = l2->next) != NULL)
+ while ((list2 = list2->next) != NULL)
{
- if ((l2 = l2->next) == NULL)
+ if ((list2 = list2->next) == NULL)
break;
- l1=l1->next;
+ list1 = list1->next;
}
- l2 = l1->next;
- l1->next = NULL;
- return g_slist_sort_merge (g_slist_sort (list, compare_func),
- g_slist_sort (l2, compare_func),
- compare_func);
+ list2 = list1->next;
+ list1->next = NULL;
+
+ return g_slist_merge (g_slist_sort (list, func),
+ g_slist_sort (list2, func),
+ func);
}
diff -ur glib-1.3.1-orig/tests/list-test.c glib-1.3.1/tests/list-test.c
--- glib-1.3.1-orig/tests/list-test.c Wed Feb 24 07:14:20 1999
+++ glib-1.3.1/tests/list-test.c Fri Sep 29 16:08:28 2000
@@ -71,6 +71,98 @@
return two-one;
}
+static void
+random_permutation (int *numbers, int length)
+{
+ int i;
+
+ for (i = 0; i < length; i++)
+ numbers[i] = i;
+
+ for (i = 0; i < length; i++)
+ {
+ int tmp, index;
+
+ index = g_random_int_range (i, length);
+ tmp = numbers[i];
+ numbers[i] = numbers[index];
+ numbers[index] = tmp;
+ }
+}
+
+static void
+test_merge (void)
+{
+ GList *list, *l1, *l2, *t;
+ int i, numbers[20];
+
+ random_permutation (numbers, 20);
+ l1 = NULL;
+ l2 = NULL;
+
+ for (i = 0; i < 10; i++)
+ {
+ l1 = g_list_prepend (l1, &numbers[i]);
+ l2 = g_list_prepend (l2, &numbers[i + 10]);
+ }
+
+ l1 = g_list_sort (l1, my_list_compare_one);
+ l2 = g_list_sort (l2, my_list_compare_one);
+ list = g_list_merge (l1, l2, my_list_compare_one);
+ g_assert (g_list_length (list) == 20);
+
+ for (i = 0; i < 20; i++)
+ {
+ t = g_list_nth (list, i);
+ g_assert (*((gint *) t->data) == i);
+ }
+}
+
+static void
+test_sort (void)
+{
+ GList *list, *t, *prev;
+ int i, numbers[20], pairs[20][2];
+
+ random_permutation (numbers, 20);
+ list = NULL;
+
+ for (i = 0; i < 20; i++)
+ list = g_list_prepend (list, &numbers[i]);
+
+ list = g_list_sort (list, my_list_compare_one);
+
+ for (i = 0; i < 20; i++)
+ {
+ t = g_list_nth (list, i);
+ g_assert (*((gint*) t->data) == i);
+ }
+ g_list_free(list);
+
+ for (i = 0; i < 20; i++)
+ {
+ pairs[i][0] = g_random_int_range (0, 5);
+ pairs[i][1] = i;
+ }
+
+ list = NULL;
+ for (i = 0; i < 20; i++)
+ list = g_list_prepend (list, pairs[i]);
+ list = g_list_reverse (list);
+
+ list = g_list_sort (list, my_list_compare_one);
+
+ prev = NULL;
+ for (t = list; t != NULL; t = t->next)
+ {
+ if (prev != NULL && ((int *) prev->data)[0] == ((int *) t->data)[0])
+ g_assert (((int *) prev->data)[1] <= ((int *) t->data)[1]);
+ prev = t;
+ }
+
+ g_list_free (list);
+}
+
int
main (int argc,
char *argv[])
@@ -129,25 +221,10 @@
}
g_list_free (list);
- list = NULL;
- for (i = 0; i < 10; i++)
- list = g_list_prepend (list, &morenums[i]);
-
- list = g_list_sort (list, my_list_compare_two);
-
- /*
- g_print("\n");
- g_list_foreach (list, my_list_print, NULL);
- */
+ test_sort ();
- for (i = 0; i < 10; i++)
- {
- t = g_list_nth (list, i);
- g_assert (*((gint*) t->data) == (9 - i));
- }
-
- g_list_free (list);
+ test_merge ();
return 0;
}
diff -ur glib-1.3.1-orig/tests/slist-test.c glib-1.3.1/tests/slist-test.c
--- glib-1.3.1-orig/tests/slist-test.c Wed Feb 24 07:14:23 1999
+++ glib-1.3.1/tests/slist-test.c Fri Sep 29 16:04:35 2000
@@ -71,6 +71,100 @@
return two-one;
}
+static void
+random_permutation (int *numbers, int length)
+{
+ int i;
+
+ for (i = 0; i < length; i++)
+ numbers[i] = i;
+
+ for (i = 0; i < length; i++)
+ {
+ int tmp, index;
+
+ index = g_random_int_range (i, length);
+ tmp = numbers[i];
+ numbers[i] = numbers[index];
+ numbers[index] = tmp;
+ }
+}
+
+static void
+test_merge (void)
+{
+ GSList *slist, *sl1, *sl2, *st;
+ int i, numbers[20];
+
+ random_permutation (numbers, 20);
+ sl1 = NULL;
+ sl2 = NULL;
+
+ for (i = 0; i < 10; i++)
+ {
+ sl1 = g_slist_prepend (sl1, &numbers[i]);
+ sl2 = g_slist_prepend (sl2, &numbers[i + 10]);
+ }
+
+ sl1 = g_slist_sort (sl1, my_list_compare_one);
+ sl2 = g_slist_sort (sl2, my_list_compare_one);
+ slist = g_slist_merge (sl1, sl2, my_list_compare_one);
+ g_assert (g_slist_length (slist) == 20);
+
+ for (i = 0; i < 20; i++)
+ {
+ st = g_slist_nth (slist, i);
+ g_assert (*((gint *) st->data) == i);
+ }
+
+ g_slist_free (slist);
+}
+
+static void
+test_sort (void)
+{
+ GSList *slist, *st, *prev;
+ int i, numbers[20], pairs[20][2];
+
+ random_permutation (numbers, 20);
+ slist = NULL;
+
+ for (i = 0; i < 20; i++)
+ slist = g_slist_prepend (slist, &numbers[i]);
+
+ slist = g_slist_sort (slist, my_list_compare_one);
+
+ for (i = 0; i < 20; i++)
+ {
+ st = g_slist_nth (slist, i);
+ g_assert (*((gint*) st->data) == i);
+ }
+ g_slist_free(slist);
+
+ for (i = 0; i < 20; i++)
+ {
+ pairs[i][0] = g_random_int_range (0, 5);
+ pairs[i][1] = i;
+ }
+
+ slist = NULL;
+ for (i = 0; i < 20; i++)
+ slist = g_slist_prepend (slist, pairs[i]);
+ slist = g_slist_reverse (slist);
+
+ slist = g_slist_sort (slist, my_list_compare_one);
+
+ prev = NULL;
+ for (st = slist; st != NULL; st = st->next)
+ {
+ if (prev != NULL && ((int *) prev->data)[0] == ((int *) st->data)[0])
+ g_assert (((int *) prev->data)[1] <= ((int *) st->data)[1]);
+ prev = st;
+ }
+
+ g_slist_free (slist);
+}
+
int
main (int argc,
char *argv[])
@@ -128,23 +222,9 @@
g_slist_free(slist);
slist = NULL;
- for (i = 0; i < 10; i++)
- slist = g_slist_prepend (slist, &morenums[i]);
-
- slist = g_slist_sort (slist, my_list_compare_two);
-
- /*
- g_print("\n");
- g_slist_foreach (slist, my_list_print, NULL);
- */
+ test_sort ();
- for (i = 0; i < 10; i++)
- {
- st = g_slist_nth (slist, i);
- g_assert (*((gint*) st->data) == (9 - i));
- }
-
- g_slist_free(slist);
+ test_merge ();
return 0;
}
[
Date Prev][
Date Next] [
Thread Prev][
Thread Next]
[
Thread Index]
[
Date Index]
[
Author Index]
