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