New upstream version 1.32.2

1 files changed, 184 insertions, 0 deletions

diff --git a/src/libnm-std-aux/c-list-util.c b/src/libnm-std-aux/c-list-util.c
new file mode 100644
index 00000000..d16bd6b7
--- /dev/null
+++ b/src/libnm-std-aux/c-list-util.c
@@ -0,0 +1,184 @@
+/* SPDX-License-Identifier: LGPL-2.1-or-later */
+/*
+ * Copyright (C) 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 degenerate 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_srt_split(CList *ls)
+{
+    CList *ls2;
+
+    ls2 = ls;
+    ls  = ls->next;
+    if (!ls)
+        return NULL;
+    do {
+        ls = ls->next;
+        if (!ls)
+            break;
+        ls  = ls->next;
+        ls2 = ls2->next;
+    } while (ls);
+    ls        = ls2->next;
+    ls2->next = NULL;
+    return ls;
+}
+
+static CList *
+_c_list_srt_merge(CList *ls1, CList *ls2, CListSortCmp cmp, const void *user_data)
+{
+    CList *ls;
+    CList  head;
+
+    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;
+}
+
+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. Doing that would be much more complicated,
+     * so it's not done. */
+_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.
+ * @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);
+    }
+}