[PATCH 00/10] typed sort of linked lists

llist_mergesort() is a function for sorting linked lists of any type without any dynamic memory allocation. It just requires the programmer to define two accessor functions and doesn't need an embedded struct or magic next pointer placement, which makes it relatively easy to use.

These accessor functions impose function call overhead and a barrier to type checking. This series aims to avoid that by giving the compiler full type information and allow it to inline them. Programmers don't need to write the accessor functions anymore and get to use typed comparison functions -- no more casts from void *. Sorting gets a bit quicker. The cost: Increased binary size.

It starts by making llist_mergesort() leaner without reducing its performance:

  mergesort: unify ranks loops
  mergesort: tighten merge loop

This matters for the next step, which creates the macro version of that function:

  mergesort: add macros for typed sort of linked lists

The next two patches show the impact of using the macro on performance and object text size of the test helper:

  test-mergesort: use DEFINE_LIST_SORT_DEBUG
  test-mergesort: use DEFINE_LIST_SORT

Then all llist_mergesort() callers get converted:

  blame: use DEFINE_LIST_SORT
  commit: use DEFINE_LIST_SORT
  fetch-pack: use DEFINE_LIST_SORT
  packfile: use DEFINE_LIST_SORT

... and the final patch removes the function which has become unused:

  mergesort: remove llist_mergesort()

 Makefile                  |   1 -
 blame.c                   |  30 ++++-------
 commit.c                  |  20 +++----
 fetch-pack.c              |   8 +++
 mergesort.c               |  84 -----------------------------
 mergesort.h               | 108 ++++++++++++++++++++++++++++++++++----
 packfile.c                |  18 ++-----
 remote.c                  |  22 --------
 remote.h                  |   2 -
 t/helper/test-mergesort.c |  34 +++---------
 t/perf/p0071-sort.sh      |   4 +-
 t/t0071-sort.sh           |   2 +-
 12 files changed, 134 insertions(+), 199 deletions(-)
 delete mode 100644 mergesort.c

-- 2.37.1