glib/gqsort.c

   1 /* GLIB - Library of useful routines for C programming
   2  * Copyright (C) 1991, 1992, 1996, 1997,1999,2004 Free Software Foundation, Inc.
   3  * Copyright (C) 2000 Eazel, Inc.
   4  * Copyright (C) 1995-1997  Peter Mattis, Spencer Kimball and Josh MacDonald
   5  *
   6  * SPDX-License-Identifier: LGPL-2.1-or-later
   7  *
   8  * This library is free software; you can redistribute it and/or
   9  * modify it under the terms of the GNU Lesser General Public
  10  * License as published by the Free Software Foundation; either
  11  * version 2.1 of the License, or (at your option) any later version.
  12  *
  13  * This library is distributed in the hope that it will be useful,
  14  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  15  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  16  * Lesser General Public License for more details.
  17  *
  18  * You should have received a copy of the GNU Lesser General Public
  19  * License along with this library; if not, see <http://www.gnu.org/licenses/>.
  20  */
  21
  22 #include "config.h"
  23
  24 #include <limits.h>
  25 #include <stdlib.h>
  26 #include <string.h>
  27 #include "galloca.h"
  28 #include "gmem.h"
  29
  30 #include "gqsort.h"
  31
  32 #include "gtestutils.h"
  33
  34 /* This file was originally from stdlib/msort.c in gnu libc, just changed
  35    to build inside glib and to not fall back to an unstable quicksort
  36    for large arrays. */
  37
  38 /* An alternative to qsort, with an identical interface.
  39    This file is part of the GNU C Library.
  40    Copyright (C) 1992,95-97,99,2000,01,02,04,07 Free Software Foundation, Inc.
  41    Written by Mike Haertel, September 1988.
  42
  43    The GNU C Library is free software; you can redistribute it and/or
  44    modify it under the terms of the GNU Lesser General Public
  45    License as published by the Free Software Foundation; either
  46    version 2.1 of the License, or (at your option) any later version.
  47
  48    The GNU C Library is distributed in the hope that it will be useful,
  49    but WITHOUT ANY WARRANTY; without even the implied warranty of
  50    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  51    Lesser General Public License for more details.
  52
  53    You should have received a copy of the GNU Lesser General Public
  54    License along with the GNU C Library; if not, see
  55    <http://www.gnu.org/licenses/>.  */
  56
  57
  58 struct msort_param
  59 {
  60   size_t s;
  61   size_t var;
  62   GCompareDataFunc cmp;
  63   void *arg;
  64   char *t;
  65 };
  66
  67 static void msort_with_tmp (const struct msort_param *p, void *b, size_t n);
  68
  69 static void
  70 msort_with_tmp (const struct msort_param *p, void *b, size_t n)
  71 {
  72   char *b1, *b2;
  73   size_t n1, n2;
  74   char *tmp = p->t;
  75   const size_t s = p->s;
  76   GCompareDataFunc cmp = p->cmp;
  77   void *arg = p->arg;
  78
  79   if (n <= 1)
  80     return;
  81
  82   n1 = n / 2;
  83   n2 = n - n1;
  84   b1 = b;
  85   b2 = (char *) b + (n1 * p->s);
  86
  87   msort_with_tmp (p, b1, n1);
  88   msort_with_tmp (p, b2, n2);
  89
  90   switch (p->var)
  91     {
  92     case 0:
  93       while (n1 > 0 && n2 > 0)
  94         {
  95           if ((*cmp) (b1, b2, arg) <= 0)
  96             {
  97               *(guint32 *) tmp = *(guint32 *) b1;
  98               b1 += sizeof (guint32);
  99               --n1;
 100             }
 101           else
 102             {
 103               *(guint32 *) tmp = *(guint32 *) b2;
 104               b2 += sizeof (guint32);
 105               --n2;
 106             }
 107           tmp += sizeof (guint32);
 108         }
 109       break;
 110     case 1:
 111       while (n1 > 0 && n2 > 0)
 112         {
 113           if ((*cmp) (b1, b2, arg) <= 0)
 114             {
 115               *(guint64 *) tmp = *(guint64 *) b1;
 116               b1 += sizeof (guint64);
 117               --n1;
 118             }
 119           else
 120             {
 121               *(guint64 *) tmp = *(guint64 *) b2;
 122               b2 += sizeof (guint64);
 123               --n2;
 124             }
 125           tmp += sizeof (guint64);
 126         }
 127       break;
 128     case 2:
 129       while (n1 > 0 && n2 > 0)
 130         {
 131           guintptr *tmpl = (guintptr *) tmp;
 132           guintptr *bl;
 133
 134           tmp += s;
 135           if ((*cmp) (b1, b2, arg) <= 0)
 136             {
 137               bl = (guintptr *) b1;
 138               b1 += s;
 139               --n1;
 140             }
 141           else
 142             {
 143               bl = (guintptr *) b2;
 144               b2 += s;
 145               --n2;
 146             }
 147           while (tmpl < (guintptr *) tmp)
 148             *tmpl++ = *bl++;
 149         }
 150       break;
 151     case 3:
 152       while (n1 > 0 && n2 > 0)
 153         {
 154           if ((*cmp) (*(const void **) b1, *(const void **) b2, arg) <= 0)
 155             {
 156               *(void **) tmp = *(void **) b1;
 157               b1 += sizeof (void *);
 158               --n1;
 159             }
 160           else
 161             {
 162               *(void **) tmp = *(void **) b2;
 163               b2 += sizeof (void *);
 164               --n2;
 165             }
 166           tmp += sizeof (void *);
 167         }
 168       break;
 169     default:
 170       while (n1 > 0 && n2 > 0)
 171         {
 172           if ((*cmp) (b1, b2, arg) <= 0)
 173             {
 174               memcpy (tmp, b1, s);
 175               tmp += s;
 176               b1 += s;
 177               --n1;
 178             }
 179           else
 180             {
 181               memcpy (tmp, b2, s);
 182               tmp += s;
 183               b2 += s;
 184               --n2;
 185             }
 186         }
 187       break;
 188     }
 189
 190   if (n1 > 0)
 191     memcpy (tmp, b1, n1 * s);
 192   memcpy (b, p->t, (n - n2) * s);
 193 }
 194
 195
 196 static void
 197 msort_r (void *b, size_t n, size_t s, GCompareDataFunc cmp, void *arg)
 198 {
 199   size_t size = n * s;
 200   char *tmp = NULL;
 201   struct msort_param p;
 202
 203   /* For large object sizes use indirect sorting.  */
 204   if (s > 32)
 205     size = 2 * n * sizeof (void *) + s;
 206
 207   if (size < 1024)
 208     /* The temporary array is small, so put it on the stack.  */
 209     p.t = g_alloca (size);
 210   else
 211     {
 212       /* It's large, so malloc it.  */
 213       tmp = g_malloc (size);
 214       p.t = tmp;
 215     }
 216
 217   p.s = s;
 218   p.var = 4;
 219   p.cmp = cmp;
 220   p.arg = arg;
 221
 222   if (s > 32)
 223     {
 224       /* Indirect sorting.  */
 225       char *ip = (char *) b;
 226       void **tp = (void **) (p.t + n * sizeof (void *));
 227       void **t = tp;
 228       void *tmp_storage = (void *) (tp + n);
 229       char *kp;
 230       size_t i;
 231
 232       while ((void *) t < tmp_storage)
 233         {
 234           *t++ = ip;
 235           ip += s;
 236         }
 237       p.s = sizeof (void *);
 238       p.var = 3;
 239       msort_with_tmp (&p, p.t + n * sizeof (void *), n);
 240
 241       /* tp[0] .. tp[n - 1] is now sorted, copy around entries of
 242          the original array.  Knuth vol. 3 (2nd ed.) exercise 5.2-10.  */
 243       for (i = 0, ip = (char *) b; i < n; i++, ip += s)
 244         if ((kp = tp[i]) != ip)
 245           {
 246             size_t j = i;
 247             char *jp = ip;
 248             memcpy (tmp_storage, ip, s);
 249
 250             do
 251               {
 252                 size_t k = (kp - (char *) b) / s;
 253                 tp[j] = jp;
 254                 memcpy (jp, kp, s);
 255                 j = k;
 256                 jp = kp;
 257                 kp = tp[k];
 258               }
 259             while (kp != ip);
 260
 261             tp[j] = jp;
 262             memcpy (jp, tmp_storage, s);
 263           }
 264     }
 265   else
 266     {
 267       if ((s & (sizeof (guint32) - 1)) == 0
 268           && (gsize) (guintptr) b % G_ALIGNOF(guint32) == 0)
 269         {
 270           if (s == sizeof (guint32))
 271             p.var = 0;
 272           else if (s == sizeof (guint64)
 273                    && (gsize) (guintptr) b % G_ALIGNOF(guint64) == 0)
 274             p.var = 1;
 275           else if ((s & (sizeof (void *) - 1)) == 0
 276                    && (gsize) (guintptr) b % G_ALIGNOF(void *) == 0)
 277             p.var = 2;
 278         }
 279       msort_with_tmp (&p, b, n);
 280     }
 281   g_free (tmp);
 282 }
 283
 284 /**
 285  * g_qsort_with_data:
 286  * @pbase: (not nullable): start of array to sort
 287  * @total_elems: elements in the array
 288  * @size: size of each element
 289  * @compare_func: function to compare elements
 290  * @user_data: data to pass to @compare_func
 291  *
 292  * This is just like the standard C qsort() function, but
 293  * the comparison routine accepts a user data argument.
 294  *
 295  * This is guaranteed to be a stable sort since version 2.32.
 296  */
 297 void
 298 g_qsort_with_data (gconstpointer    pbase,
 299                    gint             total_elems,
 300                    gsize            size,
 301                    GCompareDataFunc compare_func,
 302                    gpointer         user_data)
 303 {
 304   msort_r ((gpointer)pbase, total_elems, size, compare_func, user_data);
 305 }