diff options
author | Thomas Haller <thaller@redhat.com> | 2017-12-28 19:53:13 +0100 |
---|---|---|
committer | Thomas Haller <thaller@redhat.com> | 2017-12-29 19:43:06 +0100 |
commit | edb9ae1a1440863bad6a36f9e04035063cc6927c (patch) | |
tree | b932fcf70c9231d080fc49054cdb4982e9f97915 | |
parent | bc2c02cb9fdd18d4005cc3f7e75b57a7cf1017f2 (diff) | |
download | NetworkManager-th/c-list-sort-nonrec.tar.gz |
shared: implement c_list_sort() as non-recursive merge-sortth/c-list-sort-nonrec
This is still the very same approach (in the way the array is split
and how elements are compared). The only difference is that the
recursive implementation is replaced by a non-recursive one.
It's (still) stable, top-down merge-sort.
The non-recursive implementation better, because it avoids the overhead
of the function call to recurse.
-rw-r--r-- | shared/nm-utils/c-list-util.c | 53 |
1 files changed, 40 insertions, 13 deletions
diff --git a/shared/nm-utils/c-list-util.c b/shared/nm-utils/c-list-util.c index 509f4e12ab..8cca84f103 100644 --- a/shared/nm-utils/c-list-util.c +++ b/shared/nm-utils/c-list-util.c @@ -111,26 +111,53 @@ _c_list_srt_merge (CList *ls1, 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) { - CList *ls1, *ls2; - - if (!ls->next) - return ls; - ls1 = ls; - - ls2 = _c_list_srt_split (ls1); - - ls1 = _c_list_sort (ls1, cmp, user_data); - if (!ls2) - return ls1; + /* reserve a huge stack-size. We only need O(log(n)), hence, this + * is much more we will ever need and 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; + } - ls2 = _c_list_sort (ls2, cmp, user_data); +_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; + } - return _c_list_srt_merge (ls1, ls2, cmp, user_data); + stack_head[0].ls1 = _c_list_srt_merge (stack_head[0].ls1, stack_head[1].ls1, cmp, user_data); + goto _backtrack; } /** |