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  }