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