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