stdlib/msort.c

   1 /* An alternative to qsort, with an identical interface.
   2    This file is part of the GNU C Library.
   3    Copyright (C) 1992-2023 Free Software Foundation, Inc.
   4
   5    The GNU C Library is free software; you can redistribute it and/or
   6    modify it under the terms of the GNU Lesser General Public
   7    License as published by the Free Software Foundation; either
   8    version 2.1 of the License, or (at your option) any later version.
   9
  10    The GNU C 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    Lesser General Public License for more details.
  14
  15    You should have received a copy of the GNU Lesser General Public
  16    License along with the GNU C Library; if not, see
  17    <https://www.gnu.org/licenses/>.  */
  18
  19 #include <alloca.h>
  20 #include <stdint.h>
  21 #include <stdlib.h>
  22 #include <string.h>
  23 #include <unistd.h>
  24 #include <memcopy.h>
  25 #include <errno.h>
  26 #include <atomic.h>
  27
  28 struct msort_param
  29 {
  30   size_t s;
  31   size_t var;
  32   __compar_d_fn_t cmp;
  33   void *arg;
  34   char *t;
  35 };
  36 static void msort_with_tmp (const struct msort_param *p, void *b, size_t n);
  37
  38 static void
  39 msort_with_tmp (const struct msort_param *p, void *b, size_t n)
  40 {
  41   char *b1, *b2;
  42   size_t n1, n2;
  43
  44   if (n <= 1)
  45     return;
  46
  47   n1 = n / 2;
  48   n2 = n - n1;
  49   b1 = b;
  50   b2 = (char *) b + (n1 * p->s);
  51
  52   msort_with_tmp (p, b1, n1);
  53   msort_with_tmp (p, b2, n2);
  54
  55   char *tmp = p->t;
  56   const size_t s = p->s;
  57   __compar_d_fn_t cmp = p->cmp;
  58   void *arg = p->arg;
  59   switch (p->var)
  60     {
  61     case 0:
  62       while (n1 > 0 && n2 > 0)
  63         {
  64           if ((*cmp) (b1, b2, arg) <= 0)
  65             {
  66               *(uint32_t *) tmp = *(uint32_t *) b1;
  67               b1 += sizeof (uint32_t);
  68               --n1;
  69             }
  70           else
  71             {
  72               *(uint32_t *) tmp = *(uint32_t *) b2;
  73               b2 += sizeof (uint32_t);
  74               --n2;
  75             }
  76           tmp += sizeof (uint32_t);
  77         }
  78       break;
  79     case 1:
  80       while (n1 > 0 && n2 > 0)
  81         {
  82           if ((*cmp) (b1, b2, arg) <= 0)
  83             {
  84               *(uint64_t *) tmp = *(uint64_t *) b1;
  85               b1 += sizeof (uint64_t);
  86               --n1;
  87             }
  88           else
  89             {
  90               *(uint64_t *) tmp = *(uint64_t *) b2;
  91               b2 += sizeof (uint64_t);
  92               --n2;
  93             }
  94           tmp += sizeof (uint64_t);
  95         }
  96       break;
  97     case 2:
  98       while (n1 > 0 && n2 > 0)
  99         {
 100           unsigned long *tmpl = (unsigned long *) tmp;
 101           unsigned long *bl;
 102
 103           tmp += s;
 104           if ((*cmp) (b1, b2, arg) <= 0)
 105             {
 106               bl = (unsigned long *) b1;
 107               b1 += s;
 108               --n1;
 109             }
 110           else
 111             {
 112               bl = (unsigned long *) b2;
 113               b2 += s;
 114               --n2;
 115             }
 116           while (tmpl < (unsigned long *) tmp)
 117             *tmpl++ = *bl++;
 118         }
 119       break;
 120     case 3:
 121       while (n1 > 0 && n2 > 0)
 122         {
 123           if ((*cmp) (*(const void **) b1, *(const void **) b2, arg) <= 0)
 124             {
 125               *(void **) tmp = *(void **) b1;
 126               b1 += sizeof (void *);
 127               --n1;
 128             }
 129           else
 130             {
 131               *(void **) tmp = *(void **) b2;
 132               b2 += sizeof (void *);
 133               --n2;
 134             }
 135           tmp += sizeof (void *);
 136         }
 137       break;
 138     default:
 139       while (n1 > 0 && n2 > 0)
 140         {
 141           if ((*cmp) (b1, b2, arg) <= 0)
 142             {
 143               tmp = (char *) __mempcpy (tmp, b1, s);
 144               b1 += s;
 145               --n1;
 146             }
 147           else
 148             {
 149               tmp = (char *) __mempcpy (tmp, b2, s);
 150               b2 += s;
 151               --n2;
 152             }
 153         }
 154       break;
 155     }
 156
 157   if (n1 > 0)
 158     memcpy (tmp, b1, n1 * s);
 159   memcpy (b, p->t, (n - n2) * s);
 160 }
 161
 162
 163 void
 164 __qsort_r (void *b, size_t n, size_t s, __compar_d_fn_t cmp, void *arg)
 165 {
 166   size_t size = n * s;
 167   char *tmp = NULL;
 168   struct msort_param p;
 169
 170   /* For large object sizes use indirect sorting.  */
 171   if (s > 32)
 172     size = 2 * n * sizeof (void *) + s;
 173
 174   if (size < 1024)
 175     /* The temporary array is small, so put it on the stack.  */
 176     p.t = __alloca (size);
 177   else
 178     {
 179       /* We should avoid allocating too much memory since this might
 180          have to be backed up by swap space.  */
 181       static long int phys_pages;
 182       static int pagesize;
 183
 184       if (pagesize == 0)
 185         {
 186           phys_pages = __sysconf (_SC_PHYS_PAGES);
 187
 188           if (phys_pages == -1)
 189             /* Error while determining the memory size.  So let's
 190                assume there is enough memory.  Otherwise the
 191                implementer should provide a complete implementation of
 192                the `sysconf' function.  */
 193             phys_pages = (long int) (~0ul >> 1);
 194
 195           /* The following determines that we will never use more than
 196              a quarter of the physical memory.  */
 197           phys_pages /= 4;
 198
 199           /* Make sure phys_pages is written to memory.  */
 200           atomic_write_barrier ();
 201
 202           pagesize = __sysconf (_SC_PAGESIZE);
 203         }
 204
 205       /* Just a comment here.  We cannot compute
 206            phys_pages * pagesize
 207            and compare the needed amount of memory against this value.
 208            The problem is that some systems might have more physical
 209            memory then can be represented with a `size_t' value (when
 210            measured in bytes.  */
 211
 212       /* If the memory requirements are too high don't allocate memory.  */
 213       if (size / pagesize > (size_t) phys_pages)
 214         {
 215           _quicksort (b, n, s, cmp, arg);
 216           return;
 217         }
 218
 219       /* It's somewhat large, so malloc it.  */
 220       int save = errno;
 221       tmp = malloc (size);
 222       __set_errno (save);
 223       if (tmp == NULL)
 224         {
 225           /* Couldn't get space, so use the slower algorithm
 226              that doesn't need a temporary array.  */
 227           _quicksort (b, n, s, cmp, arg);
 228           return;
 229         }
 230       p.t = tmp;
 231     }
 232
 233   p.s = s;
 234   p.var = 4;
 235   p.cmp = cmp;
 236   p.arg = arg;
 237
 238   if (s > 32)
 239     {
 240       /* Indirect sorting.  */
 241       char *ip = (char *) b;
 242       void **tp = (void **) (p.t + n * sizeof (void *));
 243       void **t = tp;
 244       void *tmp_storage = (void *) (tp + n);
 245
 246       while ((void *) t < tmp_storage)
 247         {
 248           *t++ = ip;
 249           ip += s;
 250         }
 251       p.s = sizeof (void *);
 252       p.var = 3;
 253       msort_with_tmp (&p, p.t + n * sizeof (void *), n);
 254
 255       /* tp[0] .. tp[n - 1] is now sorted, copy around entries of
 256          the original array.  Knuth vol. 3 (2nd ed.) exercise 5.2-10.  */
 257       char *kp;
 258       size_t i;
 259       for (i = 0, ip = (char *) b; i < n; i++, ip += s)
 260         if ((kp = tp[i]) != ip)
 261           {
 262             size_t j = i;
 263             char *jp = ip;
 264             memcpy (tmp_storage, ip, s);
 265
 266             do
 267               {
 268                 size_t k = (kp - (char *) b) / s;
 269                 tp[j] = jp;
 270                 memcpy (jp, kp, s);
 271                 j = k;
 272                 jp = kp;
 273                 kp = tp[k];
 274               }
 275             while (kp != ip);
 276
 277             tp[j] = jp;
 278             memcpy (jp, tmp_storage, s);
 279           }
 280     }
 281   else
 282     {
 283       if ((s & (sizeof (uint32_t) - 1)) == 0
 284           && ((uintptr_t) b) % __alignof__ (uint32_t) == 0)
 285         {
 286           if (s == sizeof (uint32_t))
 287             p.var = 0;
 288           else if (s == sizeof (uint64_t)
 289                    && ((uintptr_t) b) % __alignof__ (uint64_t) == 0)
 290             p.var = 1;
 291           else if ((s & (sizeof (unsigned long) - 1)) == 0
 292                    && ((uintptr_t) b)
 293                       % __alignof__ (unsigned long) == 0)
 294             p.var = 2;
 295         }
 296       msort_with_tmp (&p, b, n);
 297     }
 298   free (tmp);
 299 }
 300 libc_hidden_def (__qsort_r)
 301 weak_alias (__qsort_r, qsort_r)
 302
 303
 304 void
 305 qsort (void *b, size_t n, size_t s, __compar_fn_t cmp)
 306 {
 307   return __qsort_r (b, n, s, (__compar_d_fn_t) cmp, NULL);
 308 }
 309 libc_hidden_def (qsort)