glib/tests/sort.c

   1 /*
   2  * Copyright (C) 2011 Red Hat, Inc.
   3  *
   4  * SPDX-License-Identifier: LGPL-2.1-or-later
   5  *
   6  * This library is free software; you can redistribute it and/or
   7  * modify it under the terms of the GNU Lesser General Public
   8  * License as published by the Free Software Foundation; either
   9  * version 2.1 of the License, or (at your option) any later version.
  10  *
  11  * This library is distributed in the hope that it will be useful,
  12  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  13  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  14  * Lesser General Public License for more details.
  15  *
  16  * You should have received a copy of the GNU Lesser General Public
  17  * License along with this library; if not, see <http://www.gnu.org/licenses/>.
  18  */
  19
  20 #include <glib.h>
  21
  22 static int
  23 int_compare_data (gconstpointer p1, gconstpointer p2, gpointer data)
  24 {
  25   const gint *i1 = p1;
  26   const gint *i2 = p2;
  27
  28   return *i1 - *i2;
  29 }
  30
  31 static void
  32 test_sort_basic (void)
  33 {
  34   gint *data;
  35   gint i;
  36
  37   data = g_malloc (10000 * sizeof (int));
  38   for (i = 0; i < 10000; i++)
  39     {
  40       data[i] = g_random_int_range (0, 10000);
  41     }
  42
  43   g_qsort_with_data (data, 10000, sizeof (int), int_compare_data, NULL);
  44
  45   for (i = 1; i < 10000; i++)
  46     g_assert_cmpint (data[i -1], <=, data[i]);
  47
  48   g_free (data);
  49 }
  50
  51 static void
  52 test_sort_zero_elements (void)
  53 {
  54   gint *data, *data_copy;
  55   gsize i;
  56
  57   data = g_malloc (100 * sizeof (int));
  58   data_copy = g_malloc (100 * sizeof (int));
  59   for (i = 0; i < 100; i++)
  60     {
  61       data[i] = g_random_int ();
  62       data_copy[i] = data[i];
  63     }
  64
  65   /* 0 elements is a valid case */
  66   g_qsort_with_data (data, 0, sizeof (int), int_compare_data, NULL);
  67
  68   for (i = 0; i < 100; i++)
  69     g_assert_cmpint (data[i], ==, data_copy[i]);
  70
  71   g_free (data);
  72   g_free (data_copy);
  73 }
  74
  75 typedef struct {
  76   int val;
  77   int i;
  78 } SortItem;
  79
  80 typedef struct {
  81   int val;
  82   int i;
  83   int data[16];
  84 } BigItem;
  85
  86 static int
  87 item_compare_data (gconstpointer p1, gconstpointer p2, gpointer data)
  88 {
  89   const SortItem *i1 = p1;
  90   const SortItem *i2 = p2;
  91
  92   return i1->val - i2->val;
  93 }
  94
  95 static void
  96 test_sort_stable (void)
  97 {
  98   SortItem *data;
  99   gint i;
 100
 101   data = g_malloc (10000 * sizeof (SortItem));
 102   for (i = 0; i < 10000; i++)
 103     {
 104       data[i].val = g_random_int_range (0, 10000);
 105       data[i].i = i;
 106     }
 107
 108   g_qsort_with_data (data, 10000, sizeof (SortItem), item_compare_data, NULL);
 109
 110   for (i = 1; i < 10000; i++)
 111     {
 112       g_assert_cmpint (data[i -1].val, <=, data[i].val);
 113       if (data[i -1].val == data[i].val)
 114         g_assert_cmpint (data[i -1].i, <, data[i].i);
 115     }
 116   g_free (data);
 117 }
 118
 119 static void
 120 test_sort_big (void)
 121 {
 122   BigItem *data;
 123   gint i;
 124
 125   data = g_malloc (10000 * sizeof (BigItem));
 126   for (i = 0; i < 10000; i++)
 127     {
 128       data[i].val = g_random_int_range (0, 10000);
 129       data[i].i = i;
 130     }
 131
 132   g_qsort_with_data (data, 10000, sizeof (BigItem), item_compare_data, NULL);
 133
 134   for (i = 1; i < 10000; i++)
 135     {
 136       g_assert_cmpint (data[i -1].val, <=, data[i].val);
 137       if (data[i -1].val == data[i].val)
 138         g_assert_cmpint (data[i -1].i, <, data[i].i);
 139     }
 140   g_free (data);
 141 }
 142
 143 int
 144 main (int argc, char *argv[])
 145 {
 146   g_test_init (&argc, &argv, NULL);
 147
 148   g_test_add_func ("/sort/basic", test_sort_basic);
 149   g_test_add_func ("/sort/zero-elements", test_sort_zero_elements);
 150   g_test_add_func ("/sort/stable", test_sort_stable);
 151   g_test_add_func ("/sort/big", test_sort_big);
 152
 153   return g_test_run ();
 154 }