diff options
Diffstat (limited to 'shared/nm-std-aux/c-list-util.c')
| -rw-r--r-- | shared/nm-std-aux/c-list-util.c | 216 |
1 files changed, 103 insertions, 113 deletions
diff --git a/shared/nm-std-aux/c-list-util.c b/shared/nm-std-aux/c-list-util.c index a6741c4c..a5837edd 100644 --- a/shared/nm-std-aux/c-list-util.c +++ b/shared/nm-std-aux/c-list-util.c @@ -1,4 +1,4 @@ -// SPDX-License-Identifier: LGPL-2.1+ +/* SPDX-License-Identifier: LGPL-2.1+ */ /* * Copyright (C) 2017 Red Hat, Inc. */ @@ -24,123 +24,118 @@ * the list can be fixed by c_list_relink(). */ void -c_list_relink (CList *lst) +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; + 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) +_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; + 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) +_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; + 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; + CList *ls1; + CList *ls2; + char ls1_sorted; } SortStack; static CList * -_c_list_sort (CList *ls, - CListSortCmp cmp, - const void *user_data) +_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; + /* 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; + 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. */ + /* 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; - } + 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; + 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; } /** @@ -157,16 +152,14 @@ _backtrack: * list head. */ CList * -c_list_sort_headless (CList *lst, - CListSortCmp cmp, - const void *user_data) +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; + if (!c_list_is_empty(lst)) { + lst->prev->next = NULL; + lst = _c_list_sort(lst, cmp, user_data); + c_list_relink(lst); + } + return lst; } /** @@ -180,14 +173,11 @@ c_list_sort_headless (CList *lst, * Sorts the list @head according to @cmp. */ void -c_list_sort (CList *head, - CListSortCmp cmp, - const void *user_data) +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); - } + 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); + } } |