[PATCH 00/10] typed sort of linked lists

["René Scharfe" <l.s.r@web.de>]

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