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, 250 insertions, 0 deletions

diff --git a/lib/util/stable_sort.c b/lib/util/stable_sort.c
new file mode 100644
index 00000000000..47667c4284e
--- /dev/null
+++ b/lib/util/stable_sort.c
@@ -0,0 +1,250 @@
+/*
+   Stable sort routines
+
+   Copyright © Douglas Bagnall <douglas.bagnall@catalyst.net.nz>
+
+     ** NOTE! The following LGPL license applies to this file which is used by
+     ** the ldb library. This does NOT imply that all of Samba is released
+     ** under the LGPL.
+
+   This library is free software; you can redistribute it and/or
+   modify it under the terms of the GNU Lesser General Public
+   License as published by the Free Software Foundation; either
+   version 3 of the License, or (at your option) any later version.
+
+   This library is distributed in the hope that it will be useful,
+   but WITHOUT ANY WARRANTY; without even the implied warranty of
+   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+   Lesser General Public License for more details.
+
+   You should have received a copy of the GNU Lesser General Public
+   License along with this library; if not, see <http://www.gnu.org/licenses/>.
+*/
+
+#include <stdint.h>
+#include <stdlib.h>
+#include <string.h>
+#include <unistd.h>
+#include <talloc.h>
+#include "replace.h"
+#include "stable_sort.h"
+
+static void sort_few(char *array, char *aux,
+		     size_t n,
+		     size_t s,
+		     samba_compare_with_context_fn_t cmpfn,
+		     void *opaque)
+{
+	/* a kind of insertion sort for small n. */
+	int i, j, dist;
+	int cmp;
+	char *a, *b;
+
+	for (i = 1; i < n; i++) {
+		a = &array[i * s];
+		/* leftwards is sorted. look until we find this one's place */
+		for (j = i - 1; j >= 0; j--) {
+			b = &array[j * s];
+			cmp = cmpfn(a, b, opaque);
+			if (cmp >= 0) {
+				break;
+			}
+		}
+		dist = i - 1 - j;
+		if (dist == 0) {
+			/* a is already in the right place */
+			continue;
+		}
+
+		b = &array[(i - dist) * s];
+		memcpy(aux, a, s);
+		memmove(b + s, b, s * dist);
+		memcpy(b, aux, s);
+	}
+}
+
+
+static void merge(char *dest,
+		  char *a, size_t alen,
+		  char *b, size_t blen,
+		  size_t s,
+		  samba_compare_with_context_fn_t cmpfn,
+		  void *opaque)
+{
+	size_t ai = 0;
+	size_t bi = 0;
+	size_t di = 0;
+	while (ai < alen && bi < blen) {
+		int cmp = cmpfn(&a[ai * s], &b[bi * s], opaque);
+		if (cmp <= 0) {
+			memcpy(&dest[di * s], &a[ai * s], s);
+			ai++;
+		} else {
+			memcpy(&dest[di * s], &b[bi * s], s);
+			bi++;
+		}
+		di++;
+	}
+	if (ai < alen) {
+		memcpy(&dest[di * s], &a[ai * s], s * (alen - ai));
+	} else if (bi < blen) {
+		memcpy(&dest[di * s], &b[bi * s], s * (blen - bi));
+	}
+}
+
+
+bool stable_sort_r(void *array, void *aux,
+		   size_t n,
+		   size_t s,
+		   samba_compare_with_context_fn_t cmpfn,
+		   void * opaque)
+{
+	char *src = array, *dest = aux, *tmp = NULL;
+	size_t i, j, k;
+	size_t runsize;
+	if (array == NULL || aux == NULL) {
+		return false;
+	}
+
+	if (n < 20) {
+		sort_few(array, aux, n, s, cmpfn, opaque);
+		return true;
+	}
+
+	if (n > SIZE_MAX / s) {
+		/*
+		 * We will have an integer overflow if we continue.
+		 *
+		 * This means that the *supposed* size of the allocated buffer
+		 * is greater than SIZE_MAX, which is not possible in theory
+		 * or practice, and is a sign the caller has got very
+		 * confused.
+		 */
+		return false;
+	}
+
+	/*
+	 * This is kind of a bottom-up merge sort.
+	 *
+	 * We start but sorting into a whole lot of little runs, using an
+	 * insertion sort which is efficient for small numbers. Empirically,
+	 * on 2 machines, a run size of around 8 seems optimal, but the peak
+	 * is wide, and it seems worth adapting the size to avoid an
+	 * unbalanced final merge at the top. That is, if we pick the right
+	 * runsize now, we will finish with a merge of roughly n/2:n/2, and
+	 * not have to follow that with an merge of roughly n:[a few], which
+	 * we would sometimes do with a fixed size at the lowest level.
+	 *
+	 * The aim is a runsize of n / (a power of 2) rounded up, in the
+	 * target range.
+	 */
+
+	runsize = n;
+	while (runsize > 10) {
+		runsize++;
+		runsize >>= 1;
+	}
+
+	for (i = 0; i < n; i += runsize) {
+		size_t nn = MIN(n - i, runsize);
+		sort_few(&src[i * s], aux, nn, s, cmpfn, opaque);
+	}
+
+	while (runsize < n) {
+		for (i = 0; i < n; i += runsize * 2) {
+			j = i + runsize;
+			if (j >= n) {
+				/*
+				 * first run doesn't fit, meaning this chunk
+				 * is already sorted. We just need to copy
+				 * it.
+				 */
+				size_t nn = n - i;
+				memcpy(&dest[i * s], &src[i * s], nn * s);
+				break;
+			}
+			k = j + runsize;
+			if (k > n) {
+				merge(&dest[i * s],
+				      &src[i * s], runsize,
+				      &src[j * s], n - j,
+				      s,
+				      cmpfn, opaque);
+			} else {
+				merge(&dest[i * s],
+				      &src[i * s], runsize,
+				      &src[j * s], runsize,
+				      s,
+				      cmpfn, opaque);
+			}
+		}
+
+		tmp = src;
+		src = dest;
+		dest = tmp;
+		runsize *= 2;
+	}
+	/*
+	 * We have sorted the array into src, which is either array or aux.
+	 */
+	if (src != array) {
+		memcpy(array, src, n * s);
+	}
+	return true;
+}
+
+
+
+/*
+ * A wrapper that allocates (and frees) the temporary buffer if necessary.
+ *
+ * returns false on allocation error, true otherwise.
+ */
+
+bool stable_sort_talloc_r(TALLOC_CTX *mem_ctx,
+			  void *array,
+			  size_t n,
+			  size_t s,
+			  samba_compare_with_context_fn_t cmpfn,
+			  void *opaque)
+{
+	bool ok;
+	char *mem = talloc_array_size(mem_ctx, s, n);
+	if (mem == NULL) {
+		return false;
+	}
+	ok = stable_sort_r(array, mem, n, s, cmpfn, opaque);
+	talloc_free(mem);
+	return ok;
+}
+
+
+bool stable_sort(void *array, void *aux,
+		 size_t n,
+		 size_t s,
+		 samba_compare_fn_t cmpfn)
+{
+	/*
+	 * What is this magic, casting cmpfn into a different type that takes
+	 * an extra parameter? Is that allowed?
+	 *
+	 * A: Yes. It's fine. The extra argument will be passed on the stack
+	 * or (more likely) a register, and the cmpfn will remain blissfully
+	 * unaware.
+	 */
+	return stable_sort_r(array, aux, n, s,
+			     (samba_compare_with_context_fn_t)cmpfn,
+			     NULL);
+}
+
+
+bool stable_sort_talloc(TALLOC_CTX *mem_ctx,
+			void *array,
+			size_t n,
+			size_t s,
+			samba_compare_fn_t cmpfn)
+{
+	return stable_sort_talloc_r(mem_ctx, array, n, s,
+				    (samba_compare_with_context_fn_t)cmpfn,
+				    NULL);
+}