Mercurial > hg > ucx / changeset

     1.1 --- a/src/linked_list.c	Fri May 05 19:07:56 2023 +0200
     1.2 +++ b/src/linked_list.c	Sun May 21 11:52:58 2023 +0200
     1.3 @@ -283,7 +283,7 @@
     1.4  #define CX_LINKED_LIST_SORT_SBO_SIZE 1024
     1.5  #endif
     1.6  
     1.7 -static void *cx_linked_list_sort_merge(
     1.8 +static void cx_linked_list_sort_merge(
     1.9          ptrdiff_t loc_prev,
    1.10          ptrdiff_t loc_next,
    1.11          ptrdiff_t loc_data,
    1.12 @@ -291,7 +291,9 @@
    1.13          void *ls,
    1.14          void *le,
    1.15          void *re,
    1.16 -        cx_compare_func cmp_func
    1.17 +        cx_compare_func cmp_func,
    1.18 +        void **begin,
    1.19 +        void **end
    1.20  ) {
    1.21      void *sbo[CX_LINKED_LIST_SORT_SBO_SIZE];
    1.22      void **sorted = length >= CX_LINKED_LIST_SORT_SBO_SIZE ?
    1.23 @@ -330,11 +332,11 @@
    1.24      }
    1.25      ll_next(sorted[length - 1]) = NULL;
    1.26  
    1.27 -    void *ret = sorted[0];
    1.28 +    *begin = sorted[0];
    1.29 +    *end = sorted[length-1];
    1.30      if (sorted != sbo) {
    1.31          free(sorted);
    1.32      }
    1.33 -    return ret;
    1.34  }
    1.35  
    1.36  void cx_linked_list_sort( // NOLINT(misc-no-recursion) - purposely recursive function
    1.37 @@ -380,8 +382,10 @@
    1.38          re = ll_next(rc);
    1.39  
    1.40          // {ls,...,le->prev} and {rs,...,re->prev} are sorted - merge them
    1.41 -        void *sorted = cx_linked_list_sort_merge(loc_prev, loc_next, loc_data,
    1.42 -                                                 ln + rn, ls, le, re, cmp_func);
    1.43 +        void *sorted_begin, *sorted_end;
    1.44 +        cx_linked_list_sort_merge(loc_prev, loc_next, loc_data,
    1.45 +                                  ln + rn, ls, le, re, cmp_func,
    1.46 +                                  &sorted_begin, &sorted_end);
    1.47  
    1.48          // Something left? Sort it!
    1.49          size_t remainder_length = cx_linked_list_size(re, loc_next);
    1.50 @@ -390,14 +394,13 @@
    1.51              cx_linked_list_sort(&remainder, NULL, loc_prev, loc_next, loc_data, cmp_func);
    1.52  
    1.53              // merge sorted list with (also sorted) remainder
    1.54 -            *begin = cx_linked_list_sort_merge(loc_prev, loc_next, loc_data,
    1.55 -                                               ln + rn + remainder_length,
    1.56 -                                               sorted, remainder, NULL, cmp_func);
    1.57 -        } else {
    1.58 -            // no remainder - we've got our sorted list
    1.59 -            *begin = sorted;
    1.60 +            cx_linked_list_sort_merge(loc_prev, loc_next, loc_data,
    1.61 +                                      ln + rn + remainder_length,
    1.62 +                                      sorted_begin, remainder, NULL, cmp_func,
    1.63 +                                      &sorted_begin, &sorted_end);
    1.64          }
    1.65 -        if (end) *end = cx_linked_list_last(sorted, loc_next);
    1.66 +        *begin = sorted_begin;
    1.67 +        if (end) *end = sorted_end;
    1.68      }
    1.69  }
    1.70