c-list: merge branch 'th/c-list-sort-nonrec'

https://github.com/NetworkManager/NetworkManager/pull/50

2 files changed, 139 insertions, 81 deletions

diff --git a/libnm-core/tests/test-general.c b/libnm-core/tests/test-general.c
index 39c6fb6666..c87e52516f 100644
--- a/libnm-core/tests/test-general.c
+++ b/libnm-core/tests/test-general.c
@@ -296,7 +296,6 @@ test_nm_utils_strsplit_set (void)
 
 typedef struct {
 	int val;
-	int idx;
 	CList lst;
 } CListSort;
 
@@ -320,71 +319,86 @@ _c_list_sort_cmp (const CList *lst_a, const CList *lst_b, const void *user_data)
 }
 
 static void
-test_c_list_sort (void)
+_do_test_c_list_sort (CListSort *elements, guint n_list, gboolean headless)
 {
-	guint i, n_list, repeat, headless;
 	CList head, *iter, *iter_prev, *lst;
-	CListSort elements[30];
+	guint i;
 	const CListSort *el_prev;
+	CListSort *el;
 
 	c_list_init (&head);
-	c_list_sort (&head, _c_list_sort_cmp, NULL);
-	g_assert (c_list_length (&head) == 0);
-	g_assert (c_list_is_empty (&head));
-
-	for (repeat = 0; repeat < 10; repeat++) {
-		for (n_list = 1; n_list < G_N_ELEMENTS (elements); n_list++) {
-			for (headless = 0; headless < 2; headless++) {
-				c_list_init (&head);
-				for (i = 0; i < n_list; i++) {
-					CListSort *el;
-
-					el = &elements[i];
-					el->val = nmtst_get_rand_int () % (2*n_list);
-					el->idx = i;
-					c_list_link_tail (&head, &el->lst);
-				}
+	for (i = 0; i < n_list; i++) {
+		el = &elements[i];
+		el->val = nmtst_get_rand_int () % (2*n_list);
+		c_list_link_tail (&head, &el->lst);
+	}
 
-				if (headless) {
-					lst = head.next;
-					c_list_unlink_stale (&head);
-					lst = c_list_sort_headless (lst, _c_list_sort_cmp, NULL);
-					g_assert (lst);
-					g_assert (lst->next);
-					g_assert (lst->prev);
-					g_assert (c_list_length (lst) == n_list - 1);
-					iter_prev = lst->prev;
-					for (iter = lst; iter != lst; iter = iter->next) {
-						g_assert (iter);
-						g_assert (iter->next);
-						g_assert (iter->prev == iter_prev);
-					}
-					c_list_link_before (lst, &head);
-				} else {
-					c_list_sort (&head, _c_list_sort_cmp, NULL);
-				}
+	if (headless) {
+		lst = head.next;
+		c_list_unlink_stale (&head);
+		lst = c_list_sort_headless (lst, _c_list_sort_cmp, NULL);
+		g_assert (lst);
+		g_assert (lst->next);
+		g_assert (lst->prev);
+		g_assert (c_list_length (lst) == n_list - 1);
+		iter_prev = lst->prev;
+		for (iter = lst; iter != lst; iter = iter->next) {
+			g_assert (iter);
+			g_assert (iter->next);
+			g_assert (iter->prev == iter_prev);
+		}
+		c_list_link_before (lst, &head);
+	} else
+		c_list_sort (&head, _c_list_sort_cmp, NULL);
+
+	g_assert (!c_list_is_empty (&head));
+	g_assert (c_list_length (&head) == n_list);
+
+	el_prev = NULL;
+	c_list_for_each (iter, &head) {
+		el = c_list_entry (iter, CListSort, lst);
+		g_assert (el >= elements && el < &elements[n_list]);
+		if (el_prev) {
+			if (el_prev->val == el->val)
+				g_assert (el_prev < el);
+			else
+				g_assert (el_prev->val < el->val);
+			g_assert (iter->prev == &el_prev->lst);
+			g_assert (el_prev->lst.next == iter);
+		}
+		el_prev = el;
+	}
+	g_assert (head.prev == &el_prev->lst);
+}
 
-				g_assert (!c_list_is_empty (&head));
-				g_assert (c_list_length (&head) == n_list);
-
-				el_prev = NULL;
-				c_list_for_each (iter, &head) {
-					CListSort *el;
-
-					el = c_list_entry (iter, CListSort, lst);
-					g_assert (el->idx >= 0 && el->idx < n_list);
-					g_assert (el == &elements[el->idx]);
-					if (el_prev) {
-						g_assert (el_prev->val <= el->val);
-						if (el_prev->val == el->val)
-							g_assert (el_prev->idx < el->idx);
-						g_assert (iter->prev == &el_prev->lst);
-						g_assert (el_prev->lst.next == iter);
-					}
-					el_prev = el;
-				}
-				g_assert (head.prev == &el_prev->lst);
-			}
+static void
+test_c_list_sort (void)
+{
+	const guint N_ELEMENTS = 10000;
+	guint n_list, repeat;
+	gs_free CListSort *elements = NULL;
+
+	{
+		CList head;
+
+		c_list_init (&head);
+		c_list_sort (&head, _c_list_sort_cmp, NULL);
+		g_assert (c_list_length (&head) == 0);
+		g_assert (c_list_is_empty (&head));
+	}
+
+	elements = g_new0 (CListSort, N_ELEMENTS);
+	for (n_list = 1; n_list < N_ELEMENTS; n_list++) {
+		if (n_list > 150) {
+			n_list += nmtst_get_rand_int () % n_list;
+			if (n_list >= N_ELEMENTS)
+				break;
+		}
+		{
+			const guint N_REPEAT = n_list > 50 ? 1 : 5;
+
+			for (repeat = 0; repeat < N_REPEAT; repeat++)
+				_do_test_c_list_sort (elements, n_list, nmtst_get_rand_int () % 2);
 		}
 	}
 }
diff --git a/shared/nm-utils/c-list-util.c b/shared/nm-utils/c-list-util.c
index 070323c69d..44ca26a558 100644
--- a/shared/nm-utils/c-list-util.c
+++ b/shared/nm-utils/c-list-util.c
@@ -58,39 +58,35 @@ c_list_relink (CList *lst)
 /*****************************************************************************/
 
 static CList *
-_c_list_sort (CList *ls,
-              CListSortCmp cmp,
-              const void *user_data)
+_c_list_srt_split (CList *ls)
 {
-	CList *ls1, *ls2;
-	CList head;
+	CList *ls2;
 
-	if (!ls->next)
-		return ls;
-
-	/* split list in two halfs @ls1 and @ls2. */
-	ls1 = ls;
 	ls2 = ls;
 	ls = ls->next;
-	while (ls) {
+	if (!ls)
+		return NULL;
+	do {
 		ls = ls->next;
 		if (!ls)
 			break;
 		ls = ls->next;
 		ls2 = ls2->next;
-	}
-	ls = ls2;
-	ls2 = ls->next;
-	ls->next = NULL;
-
-	/* recurse */
-	ls1 = _c_list_sort (ls1, cmp, user_data);
-	if (!ls2)
-		return ls1;
+	} while (ls);
+	ls = ls2->next;
+	ls2->next = NULL;
+	return ls;
+}
 
-	ls2 = _c_list_sort (ls2, cmp, user_data);
+static CList *
+_c_list_srt_merge (CList *ls1,
+                   CList *ls2,
+                   CListSortCmp cmp,
+                   const void *user_data)
+{
+	CList *ls;
+	CList head;
 
-	/* merge */
 	ls = &head;
 	for (;;) {
 		/* while invoking the @cmp function, the list
@@ -115,6 +111,54 @@ _c_list_sort (CList *ls,
 	return head.next;
 }
 
+typedef struct {
+	CList *ls1;
+	CList *ls2;
+	char ls1_sorted;
+} SortStack;
+
+static CList *
+_c_list_sort (CList *ls,
+              CListSortCmp cmp,
+              const void *user_data)
+{
+	/* reserve a huge stack-size. We need roughly log2(n) entries, hence this
+	 * is much more we will ever need. We don't guard for stack-overflow either. */
+	SortStack stack_arr[70];
+	SortStack *stack_head = stack_arr;
+
+	stack_arr[0].ls1 = ls;
+
+	/* A simple top-down, non-recursive, stable merge-sort.
+	 *
+	 * Maybe natural merge-sort would be better, to do better for
+	 * partially sorted lists. */
+_split:
+	stack_head[0].ls2 = _c_list_srt_split (stack_head[0].ls1);
+	if (stack_head[0].ls2) {
+		stack_head[0].ls1_sorted = 0;
+		stack_head[1].ls1 = stack_head[0].ls1;
+		stack_head++;
+		goto _split;
+	}
+
+_backtrack:
+	if (stack_head == stack_arr)
+		return stack_arr[0].ls1;
+
+	stack_head--;
+	if (!stack_head[0].ls1_sorted) {
+		stack_head[0].ls1 = stack_head[1].ls1;
+		stack_head[0].ls1_sorted = 1;
+		stack_head[1].ls1 = stack_head[0].ls2;
+		stack_head++;
+		goto _split;
+	}
+
+	stack_head[0].ls1 = _c_list_srt_merge (stack_head[0].ls1, stack_head[1].ls1, cmp, user_data);
+	goto _backtrack;
+}
+
 /**
  * c_list_sort_headless:
  * @lst: the list.