1 files changed, 317 insertions, 0 deletions
diff --git a/lib/util/tests/test_stable_sort.c b/lib/util/tests/test_stable_sort.c
new file mode 100644
index 0000000..ae4b1f3
--- /dev/null
+++ b/lib/util/tests/test_stable_sort.c
@@ -0,0 +1,317 @@
+/*
+ * Unix SMB/CIFS implementation.
+ *
+ * Copyright (C) 2018      Andreas Schneider <asn@samba.org>
+ * Copyright (C) 2022      Douglas Bagnall   <dbagnall@samba.org>
+ *
+ * This program is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation; either version 3 of the License, or
+ * (at your option) any later version.
+ *
+ * This program 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 General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program.  If not, see <http://www.gnu.org/licenses/>.
+ */
+
+#include <stdarg.h>
+#include <stddef.h>
+#include <setjmp.h>
+#include <cmocka.h>
+#include <stdbool.h>
+#include "replace.h"
+#include <talloc.h>
+
+#include "../stable_sort.h"
+
+
+static int cmp_integer(int *a, int *b)
+{
+	if (a == NULL || b == NULL) {
+		return 0;
+	}
+
+	if (*a > *b) {
+		return 1;
+	}
+
+	if (*a < *b) {
+		return -1;
+	}
+
+	return 0;
+}
+
+static void test_stable_sort(void **state)
+{
+	int a[6] = { 6, 3, 2, 7, 9, 4 };
+	int tmp[6];
+	bool ok;
+	ok = stable_sort(a, tmp,
+			 6, sizeof(int), (samba_compare_fn_t)cmp_integer);
+
+	assert_true(ok);
+	assert_int_equal(a[0], 2);
+	assert_int_equal(a[1], 3);
+	assert_int_equal(a[2], 4);
+	assert_int_equal(a[3], 6);
+	assert_int_equal(a[4], 7);
+	assert_int_equal(a[5], 9);
+}
+
+static void test_stable_sort_talloc_short(void **state)
+{
+	int a[6] = { 6, 3, 2, 7, 9, 4 };
+	int ret;
+	ret = stable_sort_talloc(NULL, a, 6, sizeof(int),
+				 (samba_compare_fn_t)cmp_integer);
+	assert_true(ret);
+
+	assert_int_equal(a[0], 2);
+	assert_int_equal(a[1], 3);
+	assert_int_equal(a[2], 4);
+	assert_int_equal(a[3], 6);
+	assert_int_equal(a[4], 7);
+	assert_int_equal(a[5], 9);
+}
+
+static void test_stable_sort_talloc_long(void **state)
+{
+	int i, ret;
+	size_t n = 1500;
+	TALLOC_CTX *mem_ctx = talloc_new(NULL);
+	int *a = talloc_array(mem_ctx, int, n);
+	for (i = 0; i < n; i++) {
+		a[i] = n - i;
+	}
+
+	ret = stable_sort_talloc(mem_ctx, a, n, sizeof(int),
+				     (samba_compare_fn_t)cmp_integer);
+	assert_true(ret);
+
+	for (i = 0; i < n; i++) {
+		assert_int_equal(a[i], 1 + i);
+	}
+}
+
+
+/*
+ * Sort an array of structs with:
+ * - unwieldy uneven size
+ * - sort key not at the start
+ * - comparison depends on context
+ *
+ * which are things we sometimes do.
+ */
+
+struct contrived_struct {
+	char padding_1[13];
+	int key[3];
+	char padding_2[18];
+	size_t *index;
+};
+
+
+static int cmp_contrived_struct(struct contrived_struct *as,
+				struct contrived_struct *bs)
+{
+	int i = *as->index;
+	int a = as->key[i];
+	int b = bs->key[i];
+	return a - b;
+}
+
+static int cmp_contrived_struct_rev(struct contrived_struct *as,
+				    struct contrived_struct *bs)
+{
+	/* will sort in reverseo order */
+	int i = *as->index;
+	int a = as->key[i];
+	int b = bs->key[i];
+	return b - a;
+}
+
+
+static void test_stable_sort_talloc_contrived_struct(void **state)
+{
+	int i, ret, prev;
+	size_t n = 800000;
+	TALLOC_CTX *mem_ctx = talloc_new(NULL);
+	size_t key_index = 0;
+
+	struct contrived_struct *a = talloc_zero_array(mem_ctx,
+						       struct contrived_struct,
+						       n);
+
+	/* we don't really want a good RNG, we want mess and repeated values. */
+	uint32_t x = 89, y = (uint32_t)-6, z = 11;
+	for (i = 0; i < n; i++) {
+		a[i].index = &key_index;
+		a[i].key[0] = (x & 0xffff) - 0x8000;
+		a[i].key[1] = z & 255;
+		/* key[2] is original order, useful for checking stability */
+		a[i].key[2] = i;
+		x += z ^ y;
+		y *= z + (x + 0x5555);
+		z -= x ^ i;
+	}
+
+	/* 1. sort by key[0] */
+	ret = stable_sort_talloc(mem_ctx, a, n,
+				 sizeof(struct contrived_struct),
+				 (samba_compare_fn_t)cmp_contrived_struct);
+	assert_true(ret);
+	prev = a[0].key[0];
+	for (i = 1; i < n; i++) {
+		int value = a[i].key[0];
+		assert_true(value >= prev);
+		if (value == prev) {
+			/* we can test the stability by comparing key[2] */
+			assert_true(a[i].key[2] >= a[i - 1].key[2]);
+		}
+		prev = value;
+	}
+
+	/* 2. sort by key[1]. key[0] now indicates stability. */
+	key_index = 1;
+	ret = stable_sort_talloc(mem_ctx, a, n,
+				 sizeof(struct contrived_struct),
+				 (samba_compare_fn_t)cmp_contrived_struct);
+	assert_true(ret);
+	prev = a[0].key[1];
+	for (i = 1; i < n; i++) {
+		int value = a[i].key[1];
+		assert_true(value >= prev);
+		if (value == prev) {
+			assert_true(a[i].key[0] >= a[i - 1].key[0]);
+		}
+		prev = value;
+	}
+
+	/*
+	 * 3. sort by key[2]. key[1] would now indicate stability, but we know
+	 * that key[2] has no duplicates, so stability is moot.
+	 */
+	key_index = 2;
+	ret = stable_sort_talloc(mem_ctx, a, n,
+				 sizeof(struct contrived_struct),
+				 (samba_compare_fn_t)cmp_contrived_struct);
+	assert_true(ret);
+	prev = a[0].key[2];
+	for (i = 1; i < n; i++) {
+		int value = a[i].key[2];
+		assert_true(value > prev);
+		prev = value;
+	}
+
+	/*
+	 * 4. sort by key[0] again, using descending sort order. key[2] should
+	 * still be in ascending order where there are duplicate key[0] values.
+	 */
+	key_index = 0;
+	ret = stable_sort_talloc(mem_ctx, a, n,
+				 sizeof(struct contrived_struct),
+				 (samba_compare_fn_t)cmp_contrived_struct_rev);
+	assert_true(ret);
+	prev = a[0].key[0];
+	for (i = 1; i < n; i++) {
+		int value = a[i].key[0];
+		assert_true(value <= prev);
+		if (value == prev) {
+			assert_true(a[i].key[2] >= a[i - 1].key[2]);
+		}
+		prev = value;
+	}
+}
+
+
+
+static int cmp_integer_xor_blob(int *_a, int *_b, int *opaque)
+{
+	int a = *_a ^ *opaque;
+	int b = *_b ^ *opaque;
+
+	if (a > b) {
+		return 1;
+	}
+
+	if (a < b) {
+		return -1;
+	}
+
+	return 0;
+}
+
+static void test_stable_sort_talloc_r(void **state)
+{
+	int i;
+	size_t n = 1500;
+	TALLOC_CTX *mem_ctx = talloc_new(NULL);
+	int opaque = 42;
+	bool ok;
+	int *a = talloc_array(mem_ctx, int, n);
+	for (i = 0; i < n; i++) {
+		a[i] = (i * 7) & 255;
+	}
+
+	ok = stable_sort_talloc_r(mem_ctx, a, n, sizeof(int),
+				  (samba_compare_with_context_fn_t)cmp_integer_xor_blob,
+				  &opaque);
+	assert_true(ok);
+
+	for (i = 1; i < n; i++) {
+		assert_true((a[i - 1] ^ opaque) <= (a[i] ^ opaque));
+	}
+}
+
+
+static void test_stable_sort_silly_size(void **state)
+{
+	bool ok;
+	int a[33] = {0};
+	int b[33] = {0};
+
+	ok = stable_sort(a,
+			 b,
+			 (SIZE_MAX / 2) + 2,
+			 (SIZE_MAX / 2) + 2,
+			 (samba_compare_fn_t)cmp_integer);
+	assert_false(ok);
+}
+
+static void test_stable_sort_null_array(void **state)
+{
+	bool ok;
+	int a[33] = {0};
+
+	ok = stable_sort(a,
+			 NULL,
+			 33,
+			 sizeof(int),
+			 (samba_compare_fn_t)cmp_integer);
+	assert_false(ok);
+}
+
+
+
+
+
+int main(void) {
+	const struct CMUnitTest tests[] = {
+		cmocka_unit_test(test_stable_sort),
+		cmocka_unit_test(test_stable_sort_talloc_short),
+		cmocka_unit_test(test_stable_sort_talloc_long),
+		cmocka_unit_test(test_stable_sort_talloc_contrived_struct),
+		cmocka_unit_test(test_stable_sort_talloc_r),
+		cmocka_unit_test(test_stable_sort_silly_size),
+		cmocka_unit_test(test_stable_sort_null_array),
+	};
+	if (!isatty(1)) {
+		cmocka_set_message_output(CM_OUTPUT_SUBUNIT);
+	}
+	return cmocka_run_group_tests(tests, NULL, NULL);
+}