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