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,95-97,99,2000,01,02,04,07 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, write to the Free
  18    Software Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA
  19    02111-1307 USA.  */
  20
  21 #include <alloca.h>
  22 #include <stdint.h>
  23 #include <stdlib.h>
  24 #include <string.h>
  25 #include <unistd.h>
  26 #include <memcopy.h>
  27 #include <errno.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 (phys_pages == 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           pagesize = __sysconf (_SC_PAGESIZE);
 201         }
 202
 203       /* Just a comment here.  We cannot compute
 204            phys_pages * pagesize
 205            and compare the needed amount of memory against this value.
 206            The problem is that some systems might have more physical
 207            memory then can be represented with a `size_t' value (when
 208            measured in bytes.  */
 209
 210       /* If the memory requirements are too high don't allocate memory.  */
 211       if (size / pagesize > (size_t) phys_pages)
 212         {
 213           _quicksort (b, n, s, cmp, arg);
 214           return;
 215         }
 216
 217       /* It's somewhat large, so malloc it.  */
 218       int save = errno;
 219       tmp = malloc (size);
 220       __set_errno (save);
 221       if (tmp == NULL)
 222         {
 223           /* Couldn't get space, so use the slower algorithm
 224              that doesn't need a temporary array.  */
 225           _quicksort (b, n, s, cmp, arg);
 226           return;
 227         }
 228       p.t = tmp;
 229     }
 230
 231   p.s = s;
 232   p.var = 4;
 233   p.cmp = cmp;
 234   p.arg = arg;
 235
 236   if (s > 32)
 237     {
 238       /* Indirect sorting.  */
 239       char *ip = (char *) b;
 240       void **tp = (void **) (p.t + n * sizeof (void *));
 241       void **t = tp;
 242       void *tmp_storage = (void *) (tp + n);
 243
 244       while ((void *) t < tmp_storage)
 245         {
 246           *t++ = ip;
 247           ip += s;
 248         }
 249       p.s = sizeof (void *);
 250       p.var = 3;
 251       msort_with_tmp (&p, p.t + n * sizeof (void *), n);
 252
 253       /* tp[0] .. tp[n - 1] is now sorted, copy around entries of
 254          the original array.  Knuth vol. 3 (2nd ed.) exercise 5.2-10.  */
 255       char *kp;
 256       size_t i;
 257       for (i = 0, ip = (char *) b; i < n; i++, ip += s)
 258         if ((kp = tp[i]) != ip)
 259           {
 260             size_t j = i;
 261             char *jp = ip;
 262             memcpy (tmp_storage, ip, s);
 263
 264             do
 265               {
 266                 size_t k = (kp - (char *) b) / s;
 267                 tp[j] = jp;
 268                 memcpy (jp, kp, s);
 269                 j = k;
 270                 jp = kp;
 271                 kp = tp[k];
 272               }
 273             while (kp != ip);
 274
 275             tp[j] = jp;
 276             memcpy (jp, tmp_storage, s);
 277           }
 278     }
 279   else
 280     {
 281       if ((s & (sizeof (uint32_t) - 1)) == 0
 282           && ((char *) b - (char *) 0) % __alignof__ (uint32_t) == 0)
 283         {
 284           if (s == sizeof (uint32_t))
 285             p.var = 0;
 286           else if (s == sizeof (uint64_t)
 287                    && ((char *) b - (char *) 0) % __alignof__ (uint64_t) == 0)
 288             p.var = 1;
 289           else if ((s & (sizeof (unsigned long) - 1)) == 0
 290                    && ((char *) b - (char *) 0)
 291                       % __alignof__ (unsigned long) == 0)
 292             p.var = 2;
 293         }
 294       msort_with_tmp (&p, b, n);
 295     }
 296   free (tmp);
 297 }
 298 libc_hidden_def (qsort_r)
 299
 300
 301 void
 302 qsort (void *b, size_t n, size_t s, __compar_fn_t cmp)
 303 {
 304   return qsort_r (b, n, s, (__compar_d_fn_t) cmp, NULL);
 305 }
 306 libc_hidden_def (qsort)