mono/unit-tests/test-sgen-qsort.c

   1 /*
   2  * test-sgen-qsort.c: Unit test for quicksort.
   3  *
   4  * Copyright (C) 2013 Xamarin Inc
   5  *
   6  * Licensed under the MIT license. See LICENSE file in the project root for full license information.
   7  */
   8
   9 #include "config.h"
  10
  11 #include <sgen/sgen-gc.h>
  12 #include <sgen/sgen-qsort.h>
  13
  14 #include <stdlib.h>
  15 #include <string.h>
  16 #include <time.h>
  17 #include <assert.h>
  18
  19 static int
  20 compare_ints (const void *pa, const void *pb)
  21 {
  22         int a = *(const int*)pa;
  23         int b = *(const int*)pb;
  24         if (a < b)
  25                 return -1;
  26         if (a == b)
  27                 return 0;
  28         return 1;
  29 }
  30
  31 typedef struct {
  32         int key;
  33         int val;
  34 } teststruct_t;
  35
  36 static int
  37 compare_teststructs (const void *pa, const void *pb)
  38 {
  39         int a = ((const teststruct_t*)pa)->key;
  40         int b = ((const teststruct_t*)pb)->key;
  41         if (a < b)
  42                 return -1;
  43         if (a == b)
  44                 return 0;
  45         return 1;
  46 }
  47
  48 static int
  49 compare_teststructs2 (const void *pa, const void *pb)
  50 {
  51         int a = (*((const teststruct_t**)pa))->key;
  52         int b = (*((const teststruct_t**)pb))->key;
  53         if (a < b)
  54                 return -1;
  55         if (a == b)
  56                 return 0;
  57         return 1;
  58 }
  59
  60 DEF_QSORT_INLINE(test_struct, teststruct_t*, compare_teststructs)
  61
  62 static void
  63 compare_sorts (void *base, size_t nel, size_t width, int (*compar) (const void*, const void*))
  64 {
  65         size_t len = nel * width;
  66         void *b1 = malloc (len);
  67         void *b2 = malloc (len);
  68
  69         memcpy (b1, base, len);
  70         memcpy (b2, base, len);
  71
  72         qsort (b1, nel, width, compar);
  73         sgen_qsort (b2, nel, width, compar);
  74
  75         /* We can't assert that qsort and sgen_qsort produce the same results
  76          * because qsort is not guaranteed to be stable, so they will tend to differ
  77          * in adjacent equal elements. Instead, we assert that the array is sorted
  78          * according to the comparator.
  79          */
  80         for (size_t i = 0; i < nel - 1; ++i)
  81                 assert (compar ((char *)b2 + i * width, (char *)b2 + (i + 1) * width) <= 0);
  82
  83         free (b1);
  84         free (b2);
  85 }
  86
  87 static void
  88 compare_sorts2 (void *base, size_t nel)
  89 {
  90         size_t width = sizeof (teststruct_t*);
  91         size_t len = nel * width;
  92         void *b1 = malloc (len);
  93         void *b2 = malloc (len);
  94
  95         memcpy (b1, base, len);
  96         memcpy (b2, base, len);
  97
  98         qsort (b1, nel, sizeof (teststruct_t*), compare_teststructs2);
  99         qsort_test_struct ((teststruct_t **)b2, nel);
 100
 101         for (size_t i = 0; i < nel - 1; ++i)
 102                 assert (compare_teststructs2 ((char *)b2 + i * width, (char *)b2 + (i + 1) * width) <= 0);
 103
 104         free (b1);
 105         free (b2);
 106 }
 107 int
 108 main (void)
 109 {
 110         int i;
 111         for (i = 1; i < 4000; ++i) {
 112                 int a [i];
 113                 int j;
 114
 115                 for (j = 0; j < i; ++j)
 116                         a [j] = i - j - 1;
 117                 compare_sorts (a, i, sizeof (int), compare_ints);
 118         }
 119
 120         srandom (time (NULL));
 121         for (i = 0; i < 2000; ++i) {
 122                 teststruct_t a [200];
 123                 int j;
 124                 for (j = 0; j < 200; ++j) {
 125                         a [j].key = random ();
 126                         a [j].val = random ();
 127                 }
 128
 129                 compare_sorts (a, 200, sizeof (teststruct_t), compare_teststructs);
 130         }
 131
 132         srandom (time (NULL));
 133         for (i = 0; i < 2000; ++i) {
 134                 teststruct_t a [200];
 135                 teststruct_t *b [200];
 136                 int j;
 137                 for (j = 0; j < 200; ++j) {
 138                         a [j].key = random ();
 139                         a [j].val = random ();
 140                         b [j] = &a[j];
 141                 }
 142
 143                 compare_sorts2 (b, 200);
 144         }
 145         return 0;
 146 }