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  * This library is free software; you can redistribute it and/or
   7  * modify it under the terms of the GNU Library General Public
   8  * License 2.0 as published by the Free Software Foundation;
   9  *
  10  * This library is distributed in the hope that it will be useful,
  11  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  12  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  13  * Library General Public License for more details.
  14  *
  15  * You should have received a copy of the GNU Library General Public
  16  * License 2.0 along with this library; if not, write to the Free
  17  * Software Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
  18  */
  19
  20 #include "config.h"
  21
  22 #include <sgen/sgen-gc.h>
  23 #include <sgen/sgen-qsort.h>
  24
  25 #include <stdlib.h>
  26 #include <string.h>
  27 #include <time.h>
  28 #include <assert.h>
  29
  30 static int
  31 compare_ints (const void *pa, const void *pb)
  32 {
  33         int a = *(const int*)pa;
  34         int b = *(const int*)pb;
  35         if (a < b)
  36                 return -1;
  37         if (a == b)
  38                 return 0;
  39         return 1;
  40 }
  41
  42 typedef struct {
  43         int key;
  44         int val;
  45 } teststruct_t;
  46
  47 static int
  48 compare_teststructs (const void *pa, const void *pb)
  49 {
  50         int a = ((const teststruct_t*)pa)->key;
  51         int b = ((const teststruct_t*)pb)->key;
  52         if (a < b)
  53                 return -1;
  54         if (a == b)
  55                 return 0;
  56         return 1;
  57 }
  58
  59 static int
  60 compare_teststructs2 (const void *pa, const void *pb)
  61 {
  62         int a = (*((const teststruct_t**)pa))->key;
  63         int b = (*((const teststruct_t**)pb))->key;
  64         if (a < b)
  65                 return -1;
  66         if (a == b)
  67                 return 0;
  68         return 1;
  69 }
  70
  71 DEF_QSORT_INLINE(test_struct, teststruct_t*, compare_teststructs)
  72
  73 static void
  74 compare_sorts (void *base, size_t nel, size_t width, int (*compar) (const void*, const void*))
  75 {
  76         size_t len = nel * width;
  77         void *b1 = malloc (len);
  78         void *b2 = malloc (len);
  79
  80         memcpy (b1, base, len);
  81         memcpy (b2, base, len);
  82
  83         qsort (b1, nel, width, compar);
  84         sgen_qsort (b2, nel, width, compar);
  85
  86         assert (!memcmp (b1, b2, len));
  87
  88         free (b1);
  89         free (b2);
  90 }
  91
  92 static void
  93 compare_sorts2 (void *base, size_t nel)
  94 {
  95         size_t len = nel * sizeof (teststruct_t*);
  96         void *b1 = malloc (len);
  97         void *b2 = malloc (len);
  98
  99         memcpy (b1, base, len);
 100         memcpy (b2, base, len);
 101
 102         qsort (b1, nel, sizeof (teststruct_t*), compare_teststructs2);
 103         qsort_test_struct ((teststruct_t **)b2, nel);
 104
 105         assert (!memcmp (b1, b2, len));
 106
 107         free (b1);
 108         free (b2);
 109 }
 110 int
 111 main (void)
 112 {
 113         int i;
 114         for (i = 1; i < 4000; ++i) {
 115                 int a [i];
 116                 int j;
 117
 118                 for (j = 0; j < i; ++j)
 119                         a [j] = i - j - 1;
 120                 compare_sorts (a, i, sizeof (int), compare_ints);
 121         }
 122
 123         srandom (time (NULL));
 124         for (i = 0; i < 2000; ++i) {
 125                 teststruct_t a [200];
 126                 int j;
 127                 for (j = 0; j < 200; ++j) {
 128                         a [j].key = random ();
 129                         a [j].val = random ();
 130                 }
 131
 132                 compare_sorts (a, 200, sizeof (teststruct_t), compare_teststructs);
 133         }
 134
 135         srandom (time (NULL));
 136         for (i = 0; i < 2000; ++i) {
 137                 teststruct_t a [200];
 138                 teststruct_t *b [200];
 139                 int j;
 140                 for (j = 0; j < 200; ++j) {
 141                         a [j].key = random ();
 142                         a [j].val = random ();
 143                         b [j] = &a[j];
 144                 }
 145
 146                 compare_sorts2 (b, 200);
 147         }
 148         return 0;
 149 }