c-list: add c_list_sort()

Add a stable, recursive merge sort for CList.

This could be improved by doing an iterative implementation.
The recursive implementation's stack depth is not an issue,
as it is bound by O(ln(n)). But an iterative implementation
would safe the overhead of O(n*log(n)) function calls and be
potentially faster.

4 files changed, 312 insertions, 0 deletions

diff --git a/Makefile.am b/Makefile.am
index b540c0c2f7..ed9417a4d6 100644
--- a/Makefile.am
+++ b/Makefile.am
@@ -414,6 +414,7 @@ libnm_core_lib_h_pub_real = \
 libnm_core_lib_h_pub_mkenums = \
 	libnm-core/nm-core-enum-types.h
 libnm_core_lib_h_priv = \
+	shared/nm-utils/c-list-util.h \
 	shared/nm-utils/nm-dedup-multi.h \
 	shared/nm-utils/nm-enum-utils.h \
 	shared/nm-utils/nm-shared-utils.h \
@@ -429,6 +430,7 @@ libnm_core_lib_h_priv = \
 	libnm-core/nm-setting-private.h \
 	libnm-core/nm-utils-private.h
 libnm_core_lib_c_real = \
+	shared/nm-utils/c-list-util.c \
 	shared/nm-utils/nm-dedup-multi.c \
 	shared/nm-utils/nm-enum-utils.c \
 	shared/nm-utils/nm-shared-utils.c \
@@ -4437,6 +4439,8 @@ EXTRA_DIST += \
 	shared/nm-test-libnm-utils.h \
 	shared/nm-test-utils-impl.c \
 	shared/nm-utils/c-list.h \
+	shared/nm-utils/c-list-util.c \
+	shared/nm-utils/c-list-util.h \
 	shared/nm-utils/gsystem-local-alloc.h \
 	shared/nm-utils/nm-glib.h \
 	shared/nm-utils/nm-obj.h \
diff --git a/libnm-core/tests/test-general.c b/libnm-core/tests/test-general.c
index cdee4c574f..20b27de9f5 100644
--- a/libnm-core/tests/test-general.c
+++ b/libnm-core/tests/test-general.c
@@ -25,6 +25,8 @@
 
 #include <string.h>
 
+#include "nm-utils/c-list-util.h"
+
 #include "nm-utils.h"
 #include "nm-setting-private.h"
 #include "nm-utils.h"
@@ -77,6 +79,103 @@ G_STATIC_ASSERT (sizeof (bool) <= sizeof (int));
 /*****************************************************************************/
 
 typedef struct {
+	int val;
+	int idx;
+	CList lst;
+} CListSort;
+
+static int
+_c_list_sort_cmp (const CList *lst_a, const CList *lst_b, const void *user_data)
+{
+	const CListSort *a, *b;
+
+	g_assert (lst_a);
+	g_assert (lst_b);
+	g_assert (lst_a != lst_b);
+
+	a = c_list_entry (lst_a, CListSort, lst);
+	b = c_list_entry (lst_b, CListSort, lst);
+
+	if (a->val < b->val)
+		return -1;
+	if (a->val > b->val)
+		return 1;
+	return 0;
+}
+
+static void
+test_c_list_sort (void)
+{
+	guint i, n_list, repeat, headless;
+	CList head, *iter, *iter_prev, *lst;
+	CListSort elements[30];
+	const CListSort *el_prev;
+
+	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);
+				}
+
+				if (headless) {
+					lst = head.next;
+					c_list_unlink (&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) {
+					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);
+			}
+		}
+	}
+}
+
+/*****************************************************************************/
+
+typedef struct {
 	NMDedupMultiObj parent;
 	guint val;
 	guint other;
@@ -6078,6 +6177,7 @@ int main (int argc, char **argv)
 {
 	nmtst_init (&argc, &argv, TRUE);
 
+	g_test_add_func ("/core/general/test_c_list_sort", test_c_list_sort);
 	g_test_add_func ("/core/general/test_dedup_multi", test_dedup_multi);
 	g_test_add_func ("/core/general/test_utils_str_utf8safe", test_utils_str_utf8safe);
 	g_test_add_func ("/core/general/test_nm_in_set", test_nm_in_set);
diff --git a/shared/nm-utils/c-list-util.c b/shared/nm-utils/c-list-util.c
new file mode 100644
index 0000000000..070323c69d
--- /dev/null
+++ b/shared/nm-utils/c-list-util.c
@@ -0,0 +1,165 @@
+/* -*- Mode: C; tab-width: 4; indent-tabs-mode: t; c-basic-offset: 4 -*- */
+/* NetworkManager -- Network link manager
+ *
+ * This library is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU Lesser General Public
+ * License as published by the Free Software Foundation; either
+ * version 2 of the License, or (at your option) any later version.
+ *
+ * This library is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+ * Lesser General Public License for more details.
+ *
+ * You should have received a copy of the GNU Lesser General Public
+ * License along with this library; if not, write to the
+ * Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
+ * Boston, MA 02110-1301 USA.
+ *
+ * (C) Copyright 2017 Red Hat, Inc.
+ */
+
+#include "c-list-util.h"
+
+/*****************************************************************************/
+
+/**
+ * c_list_relink:
+ * @lst: the head list entry
+ *
+ * Takes an invalid list, that has undefined prev pointers.
+ * Only the next pointers are valid, and the tail's next
+ * pointer points to %NULL instead of the head.
+ *
+ * c_list_relink() fixes the list by updating all prev pointers
+ * and close the circular linking by pointing the tails' next
+ * pointer to @lst.
+ *
+ * The use of this function is to do a bulk update, that lets the
+ * list degredate by not updating the prev pointers. At the end,
+ * the list can be fixed by c_list_relink().
+ */
+void
+c_list_relink (CList *lst)
+{
+	CList *ls, *ls_prev;
+
+	ls_prev = lst;
+	ls = lst->next;
+	do {
+		ls->prev = ls_prev;
+		ls_prev = ls;
+		ls = ls->next;
+	} while (ls);
+	ls_prev->next = lst;
+	lst->prev = ls_prev;
+}
+
+/*****************************************************************************/
+
+static CList *
+_c_list_sort (CList *ls,
+              CListSortCmp cmp,
+              const void *user_data)
+{
+	CList *ls1, *ls2;
+	CList head;
+
+	if (!ls->next)
+		return ls;
+
+	/* split list in two halfs @ls1 and @ls2. */
+	ls1 = ls;
+	ls2 = ls;
+	ls = ls->next;
+	while (ls) {
+		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;
+
+	ls2 = _c_list_sort (ls2, cmp, user_data);
+
+	/* merge */
+	ls = &head;
+	for (;;) {
+		/* while invoking the @cmp function, the list
+		 * elements are not properly linked. Don't try to access
+		 * their next/prev pointers. */
+		if (cmp (ls1, ls2, user_data) <= 0) {
+			ls->next = ls1;
+			ls = ls1;
+			ls1 = ls1->next;
+			if (!ls1)
+				break;
+		} else {
+			ls->next = ls2;
+			ls = ls2;
+			ls2 = ls2->next;
+			if (!ls2)
+				break;
+		}
+	}
+	ls->next = ls1 ?: ls2;
+
+	return head.next;
+}
+
+/**
+ * c_list_sort_headless:
+ * @lst: the list.
+ * @cmp: compare function for sorting. While comparing two
+ *   CList elements, their next/prev pointers are in undefined
+ *   state.
+ * @user_data: user data for @cmp.
+ *
+ * Sorts the list @lst according to @cmp. Contrary to
+ * c_list_sort(), @lst is not the list head but a
+ * valid entry as well. This function returns the new
+ * list head.
+ */
+CList *
+c_list_sort_headless (CList *lst,
+                      CListSortCmp cmp,
+                      const void *user_data)
+{
+	if (!c_list_is_empty (lst)) {
+		lst->prev->next = NULL;
+		lst = _c_list_sort (lst, cmp, user_data);
+		c_list_relink (lst);
+	}
+	return lst;
+}
+
+/**
+ * c_list_sort:
+ * @head: the list head.
+ * @cmp: compare function for sorting. While comparing two
+ *   CList elements, their next/prev pointers are in undefined
+ *   state.
+ * @user_data: user data for @cmp.
+ *
+ * Sorts the list @head according to @cmp.
+ */
+void
+c_list_sort (CList *head,
+             CListSortCmp cmp,
+             const void *user_data)
+{
+	if (   !c_list_is_empty (head)
+	    && head->next->next != head) {
+		head->prev->next = NULL;
+		head->next = _c_list_sort (head->next, cmp, user_data);
+		c_list_relink (head);
+	}
+}
diff --git a/shared/nm-utils/c-list-util.h b/shared/nm-utils/c-list-util.h
new file mode 100644
index 0000000000..199583cffc
--- /dev/null
+++ b/shared/nm-utils/c-list-util.h
@@ -0,0 +1,43 @@
+/* -*- Mode: C; tab-width: 4; indent-tabs-mode: t; c-basic-offset: 4 -*- */
+/* NetworkManager -- Network link manager
+ *
+ * This library is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU Lesser General Public
+ * License as published by the Free Software Foundation; either
+ * version 2 of the License, or (at your option) any later version.
+ *
+ * This library is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+ * Lesser General Public License for more details.
+ *
+ * You should have received a copy of the GNU Lesser General Public
+ * License along with this library; if not, write to the
+ * Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
+ * Boston, MA 02110-1301 USA.
+ *
+ * (C) Copyright 2017 Red Hat, Inc.
+ */
+
+#ifndef __C_LIST_UTIL_H__
+#define __C_LIST_UTIL_H__
+
+#include "c-list.h"
+
+/*****************************************************************************/
+
+void c_list_relink (CList *lst);
+
+typedef int (*CListSortCmp) (const CList *a,
+                             const CList *b,
+                             const void *user_data);
+
+CList *c_list_sort_headless (CList *lst,
+                             CListSortCmp cmp,
+                             const void *user_data);
+
+void c_list_sort (CList *head,
+                  CListSortCmp cmp,
+                  const void *user_data);
+
+#endif /* __C_LIST_UTIL_H__ */