mono/metadata/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 "metadata/sgen-gc.h"
  23
  24 #include <stdlib.h>
  25 #include <string.h>
  26 #include <time.h>
  27 #include <assert.h>
  28
  29 static int
  30 compare_ints (const void *pa, const void *pb)
  31 {
  32         int a = *(const int*)pa;
  33         int b = *(const int*)pb;
  34         if (a < b)
  35                 return -1;
  36         if (a == b)
  37                 return 0;
  38         return 1;
  39 }
  40
  41 typedef struct {
  42         int key;
  43         int val;
  44 } teststruct_t;
  45
  46 static int
  47 compare_teststructs (const void *pa, const void *pb)
  48 {
  49         int a = ((const teststruct_t*)pa)->key;
  50         int b = ((const teststruct_t*)pb)->key;
  51         if (a < b)
  52                 return -1;
  53         if (a == b)
  54                 return 0;
  55         return 1;
  56 }
  57
  58 static void
  59 compare_sorts (void *base, size_t nel, size_t width, int (*compar) (const void*, const void*))
  60 {
  61         size_t len = nel * width;
  62         void *b1 = malloc (len);
  63         void *b2 = malloc (len);
  64
  65         memcpy (b1, base, len);
  66         memcpy (b2, base, len);
  67
  68         qsort (b1, nel, width, compar);
  69         sgen_qsort (b2, nel, width, compar);
  70
  71         assert (!memcmp (b1, b2, len));
  72
  73         free (b1);
  74         free (b2);
  75 }
  76
  77 int
  78 main (void)
  79 {
  80         int i;
  81         for (i = 0; i < 4000; ++i) {
  82                 int a [i];
  83                 int j;
  84
  85                 for (j = 0; j < i; ++j)
  86                         a [j] = i - j - 1;
  87                 compare_sorts (a, i, sizeof (int), compare_ints);
  88         }
  89
  90         srandom (time (NULL));
  91         for (i = 0; i < 2000; ++i) {
  92                 teststruct_t a [200];
  93                 int j;
  94                 for (j = 0; j < 200; ++j) {
  95                         a [j].key = random ();
  96                         a [j].val = random ();
  97                 }
  98
  99                 compare_sorts (a, 200, sizeof (teststruct_t), compare_teststructs);
 100         }
 101
 102         return 0;
 103 }