lib/util/tests/test_stable_sort.c

   1 /*
   2  * Unix SMB/CIFS implementation.
   3  *
   4  * Copyright (C) 2018      Andreas Schneider <asn@samba.org>
   5  * Copyright (C) 2022      Douglas Bagnall   <dbagnall@samba.org>
   6  *
   7  * This program is free software; you can redistribute it and/or modify
   8  * it under the terms of the GNU General Public License as published by
   9  * the Free Software Foundation; either version 3 of the License, or
  10  * (at your option) any later version.
  11  *
  12  * This program is distributed in the hope that it will be useful,
  13  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  14  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  15  * GNU General Public License for more details.
  16  *
  17  * You should have received a copy of the GNU General Public License
  18  * along with this program.  If not, see <http://www.gnu.org/licenses/>.
  19  */
  20
  21 #include <stdarg.h>
  22 #include <stddef.h>
  23 #include <setjmp.h>
  24 #include <cmocka.h>
  25 #include <stdbool.h>
  26 #include "replace.h"
  27 #include <talloc.h>
  28
  29 #include "../stable_sort.h"
  30
  31
  32 static int cmp_integer(int *a, int *b)
  33 {
  34         if (a == NULL || b == NULL) {
  35                 return 0;
  36         }
  37
  38         if (*a > *b) {
  39                 return 1;
  40         }
  41
  42         if (*a < *b) {
  43                 return -1;
  44         }
  45
  46         return 0;
  47 }
  48
  49 static void test_stable_sort(void **state)
  50 {
  51         int a[6] = { 6, 3, 2, 7, 9, 4 };
  52         int tmp[6];
  53         bool ok;
  54         ok = stable_sort(a, tmp,
  55                          6, sizeof(int), (samba_compare_fn_t)cmp_integer);
  56
  57         assert_true(ok);
  58         assert_int_equal(a[0], 2);
  59         assert_int_equal(a[1], 3);
  60         assert_int_equal(a[2], 4);
  61         assert_int_equal(a[3], 6);
  62         assert_int_equal(a[4], 7);
  63         assert_int_equal(a[5], 9);
  64 }
  65
  66 static void test_stable_sort_talloc_short(void **state)
  67 {
  68         int a[6] = { 6, 3, 2, 7, 9, 4 };
  69         int ret;
  70         ret = stable_sort_talloc(NULL, a, 6, sizeof(int),
  71                                  (samba_compare_fn_t)cmp_integer);
  72         assert_true(ret);
  73
  74         assert_int_equal(a[0], 2);
  75         assert_int_equal(a[1], 3);
  76         assert_int_equal(a[2], 4);
  77         assert_int_equal(a[3], 6);
  78         assert_int_equal(a[4], 7);
  79         assert_int_equal(a[5], 9);
  80 }
  81
  82 static void test_stable_sort_talloc_long(void **state)
  83 {
  84         int i, ret;
  85         size_t n = 1500;
  86         TALLOC_CTX *mem_ctx = talloc_new(NULL);
  87         int *a = talloc_array(mem_ctx, int, n);
  88         for (i = 0; i < n; i++) {
  89                 a[i] = n - i;
  90         }
  91
  92         ret = stable_sort_talloc(mem_ctx, a, n, sizeof(int),
  93                                      (samba_compare_fn_t)cmp_integer);
  94         assert_true(ret);
  95
  96         for (i = 0; i < n; i++) {
  97                 assert_int_equal(a[i], 1 + i);
  98         }
  99 }
 100
 101
 102 /*
 103  * Sort an array of structs with:
 104  * - unwieldy uneven size
 105  * - sort key not at the start
 106  * - comparison depends on context
 107  *
 108  * which are things we sometimes do.
 109  */
 110
 111 struct contrived_struct {
 112         char padding_1[13];
 113         int key[3];
 114         char padding_2[18];
 115         size_t *index;
 116 };
 117
 118
 119 static int cmp_contrived_struct(struct contrived_struct *as,
 120                                 struct contrived_struct *bs)
 121 {
 122         int i = *as->index;
 123         int a = as->key[i];
 124         int b = bs->key[i];
 125         return a - b;
 126 }
 127
 128 static int cmp_contrived_struct_rev(struct contrived_struct *as,
 129                                     struct contrived_struct *bs)
 130 {
 131         /* will sort in reverseo order */
 132         int i = *as->index;
 133         int a = as->key[i];
 134         int b = bs->key[i];
 135         return b - a;
 136 }
 137
 138
 139 static void test_stable_sort_talloc_contrived_struct(void **state)
 140 {
 141         int i, ret, prev;
 142         size_t n = 800000;
 143         TALLOC_CTX *mem_ctx = talloc_new(NULL);
 144         size_t key_index = 0;
 145
 146         struct contrived_struct *a = talloc_zero_array(mem_ctx,
 147                                                        struct contrived_struct,
 148                                                        n);
 149
 150         /* we don't really want a good RNG, we want mess and repeated values. */
 151         uint32_t x = 89, y = (uint32_t)-6, z = 11;
 152         for (i = 0; i < n; i++) {
 153                 a[i].index = &key_index;
 154                 a[i].key[0] = (x & 0xffff) - 0x8000;
 155                 a[i].key[1] = z & 255;
 156                 /* key[2] is original order, useful for checking stability */
 157                 a[i].key[2] = i;
 158                 x += z ^ y;
 159                 y *= z + (x + 0x5555);
 160                 z -= x ^ i;
 161         }
 162
 163         /* 1. sort by key[0] */
 164         ret = stable_sort_talloc(mem_ctx, a, n,
 165                                  sizeof(struct contrived_struct),
 166                                  (samba_compare_fn_t)cmp_contrived_struct);
 167         assert_true(ret);
 168         prev = a[0].key[0];
 169         for (i = 1; i < n; i++) {
 170                 int value = a[i].key[0];
 171                 assert_true(value >= prev);
 172                 if (value == prev) {
 173                         /* we can test the stability by comparing key[2] */
 174                         assert_true(a[i].key[2] >= a[i - 1].key[2]);
 175                 }
 176                 prev = value;
 177         }
 178
 179         /* 2. sort by key[1]. key[0] now indicates stability. */
 180         key_index = 1;
 181         ret = stable_sort_talloc(mem_ctx, a, n,
 182                                  sizeof(struct contrived_struct),
 183                                  (samba_compare_fn_t)cmp_contrived_struct);
 184         assert_true(ret);
 185         prev = a[0].key[1];
 186         for (i = 1; i < n; i++) {
 187                 int value = a[i].key[1];
 188                 assert_true(value >= prev);
 189                 if (value == prev) {
 190                         assert_true(a[i].key[0] >= a[i - 1].key[0]);
 191                 }
 192                 prev = value;
 193         }
 194
 195         /*
 196          * 3. sort by key[2]. key[1] would now indicate stability, but we know
 197          * that key[2] has no duplicates, so stability is moot.
 198          */
 199         key_index = 2;
 200         ret = stable_sort_talloc(mem_ctx, a, n,
 201                                  sizeof(struct contrived_struct),
 202                                  (samba_compare_fn_t)cmp_contrived_struct);
 203         assert_true(ret);
 204         prev = a[0].key[2];
 205         for (i = 1; i < n; i++) {
 206                 int value = a[i].key[2];
 207                 assert_true(value > prev);
 208                 prev = value;
 209         }
 210
 211         /*
 212          * 4. sort by key[0] again, using descending sort order. key[2] should
 213          * still be in ascending order where there are duplicate key[0] values.
 214          */
 215         key_index = 0;
 216         ret = stable_sort_talloc(mem_ctx, a, n,
 217                                  sizeof(struct contrived_struct),
 218                                  (samba_compare_fn_t)cmp_contrived_struct_rev);
 219         assert_true(ret);
 220         prev = a[0].key[0];
 221         for (i = 1; i < n; i++) {
 222                 int value = a[i].key[0];
 223                 assert_true(value <= prev);
 224                 if (value == prev) {
 225                         assert_true(a[i].key[2] >= a[i - 1].key[2]);
 226                 }
 227                 prev = value;
 228         }
 229 }
 230
 231
 232
 233 static int cmp_integer_xor_blob(int *_a, int *_b, int *opaque)
 234 {
 235         int a = *_a ^ *opaque;
 236         int b = *_b ^ *opaque;
 237
 238         if (a > b) {
 239                 return 1;
 240         }
 241
 242         if (a < b) {
 243                 return -1;
 244         }
 245
 246         return 0;
 247 }
 248
 249 static void test_stable_sort_talloc_r(void **state)
 250 {
 251         int i;
 252         size_t n = 1500;
 253         TALLOC_CTX *mem_ctx = talloc_new(NULL);
 254         int opaque = 42;
 255         bool ok;
 256         int *a = talloc_array(mem_ctx, int, n);
 257         for (i = 0; i < n; i++) {
 258                 a[i] = (i * 7) & 255;
 259         }
 260
 261         ok = stable_sort_talloc_r(mem_ctx, a, n, sizeof(int),
 262                                   (samba_compare_with_context_fn_t)cmp_integer_xor_blob,
 263                                   &opaque);
 264         assert_true(ok);
 265
 266         for (i = 1; i < n; i++) {
 267                 assert_true((a[i - 1] ^ opaque) <= (a[i] ^ opaque));
 268         }
 269 }
 270
 271
 272 static void test_stable_sort_silly_size(void **state)
 273 {
 274         bool ok;
 275         int a[33] = {0};
 276         int b[33] = {0};
 277
 278         ok = stable_sort(a,
 279                          b,
 280                          (SIZE_MAX / 2) + 2,
 281                          (SIZE_MAX / 2) + 2,
 282                          (samba_compare_fn_t)cmp_integer);
 283         assert_false(ok);
 284 }
 285
 286 static void test_stable_sort_null_array(void **state)
 287 {
 288         bool ok;
 289         int a[33] = {0};
 290
 291         ok = stable_sort(a,
 292                          NULL,
 293                          33,
 294                          sizeof(int),
 295                          (samba_compare_fn_t)cmp_integer);
 296         assert_false(ok);
 297 }
 298
 299
 300
 301
 302
 303 int main(void) {
 304         const struct CMUnitTest tests[] = {
 305                 cmocka_unit_test(test_stable_sort),
 306                 cmocka_unit_test(test_stable_sort_talloc_short),
 307                 cmocka_unit_test(test_stable_sort_talloc_long),
 308                 cmocka_unit_test(test_stable_sort_talloc_contrived_struct),
 309                 cmocka_unit_test(test_stable_sort_talloc_r),
 310                 cmocka_unit_test(test_stable_sort_silly_size),
 311                 cmocka_unit_test(test_stable_sort_null_array),
 312         };
 313         if (!isatty(1)) {
 314                 cmocka_set_message_output(CM_OUTPUT_SUBUNIT);
 315         }
 316         return cmocka_run_group_tests(tests, NULL, NULL);
 317 }