diff options
Diffstat (limited to '')
-rw-r--r-- | lib/util/tests/test_stable_sort.c | 317 |
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); +} |