Import Debian changes 1.12.2-0ubuntu3

network-manager (1.12.2-0ubuntu3) cosmic; urgency=medium

  * debian/rules:
    - use --with-libnm-glib, the default reversed since that's a legacy
      library but we still need it for unity-control-center

network-manager (1.12.2-0ubuntu2) cosmic; urgency=medium

  * debian/patches/git-newglib-test.patch:
    - backport upstream commit to fix the tests with the new glib 

network-manager (1.12.2-0ubuntu1) cosmic; urgency=medium

  * New upstream version
  * d/p/libnm-register-empty-NMClient-and-NetworkManager-when-loa.patch,
    d/p/e91f1a7d2a6b8400b6b331d5b72287dcb5164a39.patch,
    d/p/git_thunderbolt_connect.patch:
    - removed, those changes are in the new version
  * Backport Debian changes
  * Update symbols file for libnm0
  * Enable iwd support
  * Drop version requirements when oldstable ships a newer version
  * Drop dh_strip override, the dbgsym migration is done
  * Rebase patches
  * Make sure the example server.conf is actually installed
  * Update install path for plugins, it now includes a version number
  * Drop libnl3 build dependency.
    Upstream has copied the code directly from libnl3 for the few functions it
    needs with a few small modifications.
  * Drop libiw build dependency.
    Hasn't been needed for a long time and was simply a left over from older
    releases.
  * Bump Standards-Version to 4.1.5
  * Fix compile error due to NM_AVAILABLE_IN_1_12_2 macro (Closes: #905372)

1 files changed, 66 insertions, 22 deletions

diff --git a/shared/nm-utils/c-list-util.c b/shared/nm-utils/c-list-util.c
index 070323c6..44ca26a5 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.