util: add stable sort functions

Sometimes (e.g. in lzxpress Huffman encoding, and in some of our
tests: c.f. https://lists.samba.org/archive/samba-technical/2018-March/126010.html)
we want a stable sort algorithm (meaning one that retains the previous
order of items that compare equal).

The GNU libc qsort() is *usually* stable, in that it first tries to
use a mergesort but reverts to quicksort if the necessary allocations
fail. That has led Samba developers to unthinkingly assume qsort() is
stable which is not the case on many platforms, and might not always
be on GNU/Linuxes either.

This adds four functions. stable_sort() sorts an array, and requires
an auxiliary working array of the same size. stable_sort_talloc()
takes a talloc context so it ca create a working array and call
stable_sort(). stable_sort_r() takes an opaque context blob that gets
passed to the compare function, like qsort_r() and ldb_qsort(). And
stable_sort_talloc_r() rounds out the quadrant.

These are LGPL so that the can be used in ldb, which has problems with
unstable sort.

The tests are borrowed and extended from test_ldb_qsort.c.

When sorting non-trivial structs this is roughly as fast as GNU qsort,
but GNU qsort has optimisations for small items, using direct
assignments of rather than memcpy where the size allows the item to be
cast as some kind of int.

Signed-off-by: Douglas Bagnall <douglas.bagnall@catalyst.net.nz>
Reviewed-by: Joseph Sutton <josephsutton@catalyst.net.nz>

1 files changed, 13 insertions, 0 deletions

diff --git a/lib/util/wscript_build b/lib/util/wscript_build
index d26aa4e5843..8eac1013394 100644
--- a/lib/util/wscript_build
+++ b/lib/util/wscript_build
@@ -147,6 +147,13 @@ bld.SAMBA_LIBRARY('genrand',
                   local_include=False,
                   private_library=True)
 
+bld.SAMBA_LIBRARY('stable_sort',
+                  source='stable_sort.c',
+                  deps='replace',
+                  public_deps='talloc',
+                  local_include=False,
+                  private_library=True)
+
 if bld.env.SAMBA_UTIL_CORE_ONLY:
 
     bld.SAMBA_LIBRARY('tevent-util',
@@ -400,3 +407,9 @@ else:
                      cflags="-D USING_CMDLINE_S3",
                      local_include=False,
                      for_selftest=True)
+
+    bld.SAMBA_BINARY('test_stable_sort',
+                     source='tests/test_stable_sort.c',
+                     deps='cmocka replace talloc stable_sort',
+                     local_include=False,
+                     for_selftest=True)