diff options
author | Thomas Haller <thaller@redhat.com> | 2018-01-03 17:04:49 +0100 |
---|---|---|
committer | Thomas Haller <thaller@redhat.com> | 2018-01-03 17:04:49 +0100 |
commit | 81416a8d485c51e01c59a48c296267e3092dd45f (patch) | |
tree | 093a58e5e43b6c25e8864a6691d14da56bf8df12 | |
parent | 1402fa7487b29fc1ea39a6bf7659fee7f30bb0e0 (diff) | |
parent | 916f53ac24ddc57efc2e016778c4996ef3b3d09c (diff) | |
download | NetworkManager-81416a8d485c51e01c59a48c296267e3092dd45f.tar.gz |
c-list: merge branch 'th/c-list-sort-nonrec'
https://github.com/NetworkManager/NetworkManager/pull/50
-rw-r--r-- | libnm-core/tests/test-general.c | 132 | ||||
-rw-r--r-- | shared/nm-utils/c-list-util.c | 88 |
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. |