std-aux: add c_list_insert_sorted()

The strength of CList is of course to use it as a stack of queue,
and only append/remove from the front/tail.

However, since this is an intrusive list, it can also be useful to
just use it to track elements, and -- when necessary -- sort them
via c_list_sort().

If we have a sorted list, we might want to insert a new element
honoring the sort order. This function achieves that.

3 files changed, 212 insertions, 2 deletions

diff --git a/src/libnm-core-impl/tests/test-general.c b/src/libnm-core-impl/tests/test-general.c
index 3a142bc1f2..c2b73b4833 100644
--- a/src/libnm-core-impl/tests/test-general.c
+++ b/src/libnm-core-impl/tests/test-general.c
@@ -1338,6 +1338,7 @@ typedef struct {
 static int
 _c_list_sort_cmp(const CList *lst_a, const CList *lst_b, const void *user_data)
 {
+    const int        MODFIER = user_data ? GPOINTER_TO_INT(user_data) : 0;
     const CListSort *a, *b;
 
     g_assert(lst_a);
@@ -1351,9 +1352,36 @@ _c_list_sort_cmp(const CList *lst_a, const CList *lst_b, const void *user_data)
         return -1;
     if (a->val > b->val)
         return 1;
+
+    switch (MODFIER) {
+    case 0:
+        break;
+    case 1:
+        NM_CMP_DIRECT_PTR(a, b);
+        g_assert_not_reached();
+        break;
+    case 2:
+        NM_CMP_DIRECT_PTR(b, a);
+        g_assert_not_reached();
+        break;
+    default:
+        g_assert_not_reached();
+        break;
+    }
+
     return 0;
 }
 
+static int
+_c_list_sort_cmp_inverse(const CList *lst_a, const CList *lst_b, const void *user_data)
+{
+    int c;
+
+    c = _c_list_sort_cmp(lst_b, lst_a, user_data);
+    g_assert(NM_IN_SET(c, -1, 0, 1));
+    return c;
+}
+
 static void
 _do_test_c_list_sort(CListSort *elements, guint n_list, gboolean headless)
 {
@@ -1411,8 +1439,9 @@ static void
 test_c_list_sort(void)
 {
     const guint        N_ELEMENTS = 10000;
-    guint              n_list, repeat;
-    gs_free CListSort *elements = NULL;
+    gs_free CListSort *elements   = NULL;
+    guint              n_list;
+    guint              repeat;
 
     {
         CList head;
@@ -1441,6 +1470,97 @@ test_c_list_sort(void)
 
 /*****************************************************************************/
 
+static void
+_do_test_c_list_insert_sorted(CListSort *elements, guint n_list, bool append_equal)
+{
+    CList            head;
+    guint            i;
+    const CListSort *el_prev;
+    CListSort       *el;
+
+    c_list_init(&head);
+    for (i = 0; i < n_list; i++) {
+        el      = &elements[i];
+        el->val = nmtst_get_rand_uint32() % (2 * n_list);
+
+        if (nmtst_get_rand_bool()) {
+            c_list_insert_sorted(&head, &el->lst, TRUE, append_equal, _c_list_sort_cmp, NULL);
+        } else {
+            c_list_insert_sorted(&head,
+                                 &el->lst,
+                                 FALSE,
+                                 append_equal,
+                                 _c_list_sort_cmp_inverse,
+                                 NULL);
+        }
+
+        if (nmtst_get_rand_one_case_in(20)) {
+            nm_assert(c_list_is_sorted(&head, TRUE, _c_list_sort_cmp, NULL));
+            if (append_equal) {
+                nm_assert(c_list_is_sorted(&head, TRUE, _c_list_sort_cmp, GINT_TO_POINTER(1)));
+            } else {
+                nm_assert(c_list_is_sorted(&head, TRUE, _c_list_sort_cmp, GINT_TO_POINTER(2)));
+            }
+            nm_assert(c_list_is_sorted(&head, FALSE, _c_list_sort_cmp_inverse, NULL));
+            if (append_equal) {
+                nm_assert(
+                    c_list_is_sorted(&head, FALSE, _c_list_sort_cmp_inverse, GINT_TO_POINTER(1)));
+            } else {
+                nm_assert(
+                    c_list_is_sorted(&head, FALSE, _c_list_sort_cmp_inverse, GINT_TO_POINTER(2)));
+            }
+        }
+    }
+
+    g_assert_cmpint(c_list_length(&head), ==, n_list);
+    g_assert(!c_list_length_is(&head, n_list - 1));
+    g_assert(c_list_length_is(&head, n_list));
+    g_assert(!c_list_length_is(&head, n_list + 1));
+
+    el_prev = NULL;
+    c_list_for_each_entry (el, &head, lst) {
+        if (el_prev) {
+            int c;
+
+            c = _c_list_sort_cmp(&el_prev->lst, &el->lst, NULL);
+            g_assert_cmpint(c, <=, 0);
+            if (c == 0) {
+                if (append_equal)
+                    g_assert(&el_prev->lst < &el->lst);
+                else
+                    g_assert(&el_prev->lst > &el->lst);
+            }
+        }
+        el_prev = el;
+    }
+}
+
+static void
+test_c_list_insert_sorted(void)
+{
+    const guint        N_ELEMENTS = 1000;
+    gs_free CListSort *elements   = NULL;
+    guint              n_list;
+    guint              repeat;
+
+    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_uint32() % 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_insert_sorted(elements, n_list, nmtst_get_rand_bool());
+        }
+    }
+}
+
+/*****************************************************************************/
+
 typedef struct {
     NMDedupMultiObj parent;
     guint           val;
@@ -10838,6 +10958,7 @@ main(int argc, char **argv)
     g_test_add_func("/core/general/test_nm_hash", test_nm_hash);
     g_test_add_func("/core/general/test_nm_g_slice_free_fcn", test_nm_g_slice_free_fcn);
     g_test_add_func("/core/general/test_c_list_sort", test_c_list_sort);
+    g_test_add_func("/core/general/test_c_list_insert_sorted", test_c_list_insert_sorted);
     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_strsplit_set", test_nm_strsplit_set);
diff --git a/src/libnm-std-aux/c-list-util.c b/src/libnm-std-aux/c-list-util.c
index d16bd6b7cc..12cd5f0f6d 100644
--- a/src/libnm-std-aux/c-list-util.c
+++ b/src/libnm-std-aux/c-list-util.c
@@ -182,3 +182,77 @@ c_list_sort(CList *head, CListSortCmp cmp, const void *user_data)
         c_list_relink(head);
     }
 }
+
+/*****************************************************************************/
+
+CList *
+c_list_first_unsorted(CList *list, int ascending, CListSortCmp cmp, const void *user_data)
+{
+    CList *iter_prev = NULL;
+    CList *iter;
+    int    c;
+
+    /* Returns the first element with the wrong sort order,
+     * or NULL, if they are all sorted. */
+
+    c_list_for_each (iter, list) {
+        if (iter_prev) {
+            c = cmp(iter_prev, iter, user_data);
+            if (ascending) {
+                if (c > 0)
+                    return iter;
+            } else {
+                if (c < 0)
+                    return iter;
+            }
+        }
+        iter_prev = iter;
+    }
+
+    return NULL;
+}
+
+void
+c_list_insert_sorted(CList       *list,
+                     CList       *elem,
+                     int          ascending,
+                     int          append_equal,
+                     CListSortCmp cmp,
+                     const void  *user_data)
+{
+    CList *iter;
+
+    /* We iterate the list front-to-end, and insert @elem according
+     * to the sort order @cmp. If @append_equal is TRUE, we will
+     * skip over equal elements and append afterwards. */
+    c_list_for_each (iter, list) {
+        int c;
+
+        c = cmp(iter, elem, user_data);
+
+        if (ascending) {
+            if (c < 0)
+                continue;
+            if (c > 0 || !append_equal)
+                goto out;
+        } else {
+            if (c > 0)
+                continue;
+            if (c < 0 || !append_equal)
+                goto out;
+        }
+
+        for (iter = iter->next; iter != list; iter = iter->next) {
+            c = cmp(iter, elem, user_data);
+            if (c != 0) {
+                /* We'd expect that the list is sorted, so @c should be
+                 * greater than 0. But don't enforce that. */
+                goto out;
+            }
+        }
+        goto out;
+    }
+
+out:
+    c_list_link_before(iter, elem);
+}
diff --git a/src/libnm-std-aux/c-list-util.h b/src/libnm-std-aux/c-list-util.h
index dbfef0f825..4800a3cc11 100644
--- a/src/libnm-std-aux/c-list-util.h
+++ b/src/libnm-std-aux/c-list-util.h
@@ -53,4 +53,19 @@ c_list_length_is(const CList *list, unsigned long check_len)
     for (_iter = c_list_entry((_list)->prev, __typeof__(*_iter), _m); &(_iter)->_m != (_list); \
          _iter = c_list_entry((_iter)->_m.prev, __typeof__(*_iter), _m))
 
+CList *c_list_first_unsorted(CList *list, int ascending, CListSortCmp cmp, const void *user_data);
+
+static inline int
+c_list_is_sorted(CList *list, int ascending, CListSortCmp cmp, const void *user_data)
+{
+    return !c_list_first_unsorted(list, ascending, cmp, user_data);
+}
+
+void c_list_insert_sorted(CList       *list,
+                          CList       *elem,
+                          int          ascending,
+                          int          append_equal,
+                          CListSortCmp cmp,
+                          const void  *user_data);
+
 #endif /* __C_LIST_UTIL_H__ */